内存数据库并发控制算法的实验研究-赵泓尧，赵展浩，杨皖晴，卢卫，李海翔，杜小勇.pdf

上善若水

276

24页

1次

2022-05-19

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software, 2022,33(3):867−890 [doi: 10.13328/j.cnki.jos.006454] http://www.jos.org.cn

内存数据库并发控制算法的实验研究

∗

赵泓尧

1,2

赵展浩

1,2

杨皖晴

1,2

卢

卫

1,2

李海翔

杜小勇

1,2

(数据工程与知识工程教育部重点实验室(中国人民大学), 北京 100872)

(中国人民大学信息学院, 北京 100872)

(腾讯科技(北京)有限公司计费平台部, 北京 100193)

通信作者: 杜小勇, E-mail: duyong@ruc.edu.cn; 卢卫, E-mail: lu-wei@ruc.edu.cn

摘要: 并发控制算法是数据库系统保证事务执行正确且高效的重要手段, 一直是数据库工业界和学术界研究的

核心问题之一. 将并发控制算法的基本思想归纳为“先定序后检验”, 并基于该思想对现有各类并发控制算法进行

了重新描述和分类总结. 基于在开源内存型分布式事务测试床 3TS 上的实际对比实验, 系统性地探究了各类算法

的优缺点和适用场景, 为面向内存数据库的并发控制算法的后续研究提供参考.

关键词: 数据库系统; 事务处理; 并发控制算法; 3TS; 内存数据库

中图法分类号: TP311

中文引用格式: 赵泓尧, 赵展浩, 杨皖晴, 卢卫, 李海翔, 杜小勇. 内存数据库并发控制算法的实验研究. 软件学报, 2022,

33(3): 867–890. http://www.jos.org.cn/1000-9825/6454.htm

英文引用格式: Zhao HY, Zhao ZH, Yang WQ, Lu W, Li HX, Du XY. Experimental Study on Concurrency Control Algorithms in

In-Memory Databases. Ruan Jian Xue Bao/Journal of Software, 2022, 33(3): 867−890 (in Chinese). http://www.jos.org.cn/

1000-9825/6454.htm

Experimental Study on C oncurrency Co ntrol Algorithms in I n-Memory Da tabase s

ZHAO Hong-Yao

1,2

, ZHAO Zhan-Hao

1,2

, YANG Wan-Qing

1,2

, LU Wei

1,2

, LI Hai-Xiang

, DU Xiao-Yong

1,2

(Key Laboratory of Data Engineering and Knowledge Engineering (Renmin University of China), Ministry of Education, Beijing 100872,

China)

(School of Information, Renmin University of China, Beijing 100872, China)

(Billing Platform Department, Tencent Technology (Beijing) Co. Ltd, Beijing 100193, China)

Abstra ct : The concurrency control algorithm is a key component to guarantee the correctness and efficiency of executing transactions.

Thus far, substantial effort has been devoted to proposing new concurrency controls algorithms in both database industry and academia.

This study abstracts a common paradigm of the state-of-the-art and summarizes the core idea of concurrency control algorithms as

“ordering-and-verifying”. Then, the existing concurrency control algorithms are re-presented following the ordering-and-verifying

paradigm. Based on extensive experiments under an open-source memory-based distributed transaction testbed called 3TS, it is

systematically demonstrated the advantages and disadvantages of the mainstream state-of-the-art concurrency control algorithms. Finally,

the preferable application scenario is summarized for each algorithm and some valuable references are provided for the follow-up research

of concurrency control algorithms used in in-memory databases.

Key words: database system; transaction processing; concurrency control algorithm; 3TS; in-memory database

事务是用户定义的一组数据库操作组成的序列, 是数据库管理系统中的最小执行单元

[1,2]

. 事务概念的提

∗ 基金项目: 国家重点研发计划(2020YFB2104100); 国家自然科学基金(61972403, 61732014); 中央高校基本科研业务费专项

资金(20XNLG22); 中国人民大学-腾讯联合实验室联合项目基金

本文由“数据库系统新型技术”专题特约编辑李国良教授、于戈教授、杨俊教授和范举教授推荐.

收稿时间: 2021-06-30; 修改时间: 2021-07-31; 采用时间: 2021-09-13; jos 在线出版时间: 2021-10-21

868

软件学报 2022 年第 33 卷第 3 期

出, 推动了数据库从实验室中的原型系统转变为现代信息系统不可或缺的基础设施. ACID 理论

[1,2]

定义了数

据库系统事务处理的基本要求, 即数据库中的事务需要具备 4 大特性: 原子性(A)、一致性(C)、隔离性 (I)和持

久性(D). 原子性要求事务的操作要么全做, 要么全不做; 一致性要求事务的执行必须使数据库从一个一致性

状态变迁到另一个一致性状态, 不允许未成功提交事务的临时数据被访问; 隔离性要求事务的执行不能影响

其他事务也不能被其他事务影响; 持久性要求数据库持久化存储已提交事务写入的数据. 数据库系统为了保

证 ACID 特性, 引入故障恢复子系统来保证原子性和持久性, 并引入并发控制子系统来保证一致性和隔离性.

并发控制算法是数据库并发控制子系统的核心, 其目标是对事务进行合理调度, 从而保证事务执行的正

确性. 并发控制算法的效率直接影响着事务处理的性能, 因而设计并实现正确且高效的并发控制算法, 一直

是数据库系统研究的核心课题之一. 当前, 设计并发控制算法做到正确且高效仍面临以下两大挑战.

• 首先, 并发控制算法在保证可串行化隔离级别的前提下, 保证事务处理的高效性是一个挑战. 可串

行化是保证事务正确调度的黄金法则

[1,2]

, 其要求事务的并发执行结果与这些事务的某个串行执行

结果相同. 为了保证可串行化, 并发控制算法需要对事务之间的并发关系进行追踪和维护, 并且基

于这些信息判断事务是否可以提交. 由于可串行化较严格的排序要求, 其势必会导致事务的并发度

受限, 事务的回滚率上升. 因此, 可串行化对并发控制算法的逻辑设计提出了较高的要求.

• 其次, 随着内存数据库的出现和普及, 并发控制算法的处理逻辑需要针对基于内存的数据库架构进

行调整. 相比于传统的磁盘数据库, 内存数据库的差异主要在于数据项、索引以及并发控制算法所

需的元信息等数据的存储上.

¾ 首先, 在磁盘数据库中, 数据项和索引需要存储在磁盘中来防止数据丢失, 而这就使得并发控

制算法的设计需要将访问数据项、索引的磁盘 I/O 开销纳入考虑. 因此, 在磁盘数据库中, 降

低回滚率并提高事务并发度, 可以降低磁盘 I/O 对性能的影响. 内存数据库由于其高速数据存

取的优点, 降低了回滚率和并发度对算法性能的影响. CPU 的计算处理性能反而成为内存数据

库的主要瓶颈, 因此, 并发控制算法本身的处理开销是影响算法性能的一个关键. 以锁机制为

例, 磁盘数据库系统往往会使用细粒度的锁来减少锁争用, 而在内存数据库中就可以使用粗

粒度的锁来减少维护锁的计算开销.

¾ 其次, 磁盘数据库中需要额外在内存中设计存储结构来维护元信息, 这些结构不仅实现复杂,

在获取元信息时也会带来一定的开销. 内存数据库则规避了这一问题, 元信息直接存储在数

据项的头部简化了实现, 同时减少了从复杂结构中获取元信息的开销.

需要说明的是, 从研究并发控制算法的角度看, 采用内存数据库可以更直接地评估并发控制算法的效率,

因为不需要考虑内外存 I/

O 的影响, 而这常常是影响磁盘数据库性能的主要因素. 因此, 并发控制算法的不同

特性导致了其对不同系统架构的适用性不同. 而如何利用内存数据库具备的高速数据读取的优点, 设计并优

化并发控制算法, 是当前的另一大挑战. 例如, 基于时间戳的并发控制算法由于需要有全局递增的时间戳, 在

分布式内存型数据库中会存在时钟分配的性能瓶颈, 从而导致事务执行效率较低.

近年来, 面向内存数据库的并发控制算法研究期望解决这两大挑战. Bamboo

[3]

在两阶段封锁(two-phase

locking, 2PL)算法

[4,5]

的基础上减少了锁等待时间, 优化了 2PL 的算法逻辑, 提升了事务并发度, 从而提升性

能; MaaT

[6]

通过引入动态时间戳调整, 降低事务回滚率, 优化了乐观并发控制(optimisitic concurrency control,

OCC)算法

[7]

的逻辑; Sundial

[8]

引入了 Cache 机制, 在内存型分布式数据库上表现优秀. 而随着越来越多并发控

制算法的提出, 由于算法描述方式各异, 导致并发控制算法理解和实现成本较高. 因而, 在内存数据库设计与

实现时, 针对特定场景对并发控制算法进行选择显得尤为困难. 从 20 世纪 80 年代起, 许多综述研究对并发控

制算法进行了分析和归类. Bernstein 在 1981 年

[5]

就对当时最先进的并发控制算法进行综述和总结. Agrawal 等

人

[9]

、Carey 等人

[10]

、Huang 等人

[11]

的工作则在介绍算法的基础上, 主要通过实验分析了各类算法的性能. 最

近的工作 Deneva

[12]

也测试分析了 6 种并发控制算法在分布式场景下的表现情况. 2020 年, Huang 等人

[13]

和

Tanabe 等人

[14]

则在单机场景下实验分析了算法的性能, 同时研究了影响算法性能的主要因素和优化方法.

of 24

免费下载

软件学报计算机技术

关注

评论