郭 璇， 周 浩， 罗文辉

(武汉理工大学 自动化学院， 武汉 430070)

基于OCC-DA-MCP算法的Redis并发控制

郭 璇*， 周 浩， 罗文辉

(武汉理工大学 自动化学院， 武汉 430070)

该文以提高Redis内存数据库的并发性能为目的，通过研究现有的内存数据库并发控制算法，然后结合Redis架构，设计并实现了基于OCC-DA-MCP算法的Redis并发控制.仿真结果表明，该算法在一定程度上改善了现有Redis并发控制算法存在的浪费的执行和不必要的重启等问题.

并发控制； Redis； 内存数据库

Redis(Remote Dictionary Server)，是一个使用ANSI C语言编写、基于键值对(Key-Value)数据存储的内存数据库[1]，并能够提供多种语言的API.Redis的应用非常的广泛，目前国内的大型互联网公司如新浪、淘宝，国外的Fickr、Github等均在使用Redis的缓存服务[2].

并发控制是指在多线程数据请求下，保证数据库一致性和完整性的机制.由于Redis是一种单线程机制的内存数据库，理论上来说不存在并发和锁的概念，高并发对同一个键的操作会进行排队处理，其命令会一条一条依次执行.但是，利用Redis客户端对Redis进行并发访问时可能会出现连接超时、数据转换错误、阻塞、客户端意外关闭连接等问题，这些问题的出现都可能会影响Redis的性能.

本文通过分析OCC-DA并发控制算法，以及结合Redis内存数据库的特点，提出了基于OCC-DA的改良算法，在Redis的高并发实际应用中有很重要的实用意义.

1 内存数据库并发控制研究

1.1 并发控制算法概述

并发控制是指在多个用户同时对服务器执行数据操作时，能够确保并纠正由并发操作导致的错误，用于保护数据库完整性的各种技术，其基本单位是事务.并发机制的不正确可能会导致服务器数据的丢失、不可重复读取等问题.

内存数据库作为一个共享资源，不同的客户端可以随时的对其进行数据访问，为了最大限度的利用数据库里的资源，就应该允许多个客户端并行的对数据库的数据进行访问.对于实际的系统，可能会出现多个客户端并发操作同一个数据的情况，如果没有相应的机制来控制并发操作，很可能会对数据造成误操作，破坏数据库的一致性，因此，并发控制效果是衡量内存数据库性能的重要指标之一.

并发控制主要有悲观控制和乐观控制[3]，其技术手段有时间戳、封锁、多版本和快照隔离等.基于锁的并发控制属于悲观并发控制算法，使用该类算法时，事务没有获取锁之前无法访问数据对象，悲观并发控制算法较为常见的有2PL-HP、2PL-PI、2PL-CPI等；乐观并发控制算法的事务执行分为三个阶段：读阶段、验证阶段和写阶段，该类算法主要有OCC-BC、OCC-Sacrifice、OCC-Wait、OOC-TI、OCC-DA等.本文针对OCC-DA算法进行研究.

1.2 并发控制算法存在的不足

在对实时事务进行并发控制时，会考虑到事务的优先级和截止期两个主要因素，根据在这两个因素上的不同侧重点，两类算法分别存在不同的影响算法性能的问题.

1) 悲观控制算法的主要问题有：浪费的等待和浪费的重启.

浪费的重启：考虑到事务的优先级，悲观控制算法会在低优先级的事务与高优先级的事务发生冲突时重启低优先级的事务，如果在重启低优先级的事务后，高优先级的事务因为错过截止期而导致事务中止，那么低优先级事务的重启就是浪费的重启.

浪费的等待：如果低优先级的事务与高优先级的事务发生冲突时进入等待状态，而在等待期间高优先级的事务因为错过截止期而导致事务中止，那么低优先级的事务的等待就是浪费的等待.

2) 乐观控制算法的主要问题有：浪费的执行和不必要的重启.

浪费的执行：主要有两种可能导致该问题的原因.一个是如果事务因为错过时间截止期而中止了，那么该事务的所有执行时间都是浪费的；另一个是如果事务因为数据访问冲突而重启了，那么事务之前的执行都是浪费的.

不必要的重启：如果一个事务在验证阶段被重启了，且该事务如果不重启的话仍然能保证事务调度的可串行性，那么这种重启就是不必要的.

2 基于OCC-DA-MCP的Redis并发控制

2.1 Redis并发控制

Redis对于并发控制的处理，主要是基于其相应的事务操作[4].内部原理是通过命令将一组数据库操作命令集合起来，一次全部执行.使用的命令有：MULTI(开启事务)；EXEC(执行事务)、DISCARD(取消事务)、WATCH(监视数据).Redis事务中所有的操作都会被序列化，并且有序的执行.

Redis使用的是检查设置算法(check-and-set，OCC-CS)处理并发的问题，这是一种乐观并发控制算法.当一个请求开启事务对某个数据进行操作时，会首先使用WATCH命令来监视这个数据，如果事务执行前数据值被修改了，那么事务就会被取消.假设事务T1使用WATCH命令监控了数据D的值，OCC-CS算法的具体描述如下：

if(D.oldvalue!=D.newvalue)

DISCARD T1;

else

EXEC T1;

其中，D.oldvalue是开启事务时D的值，D.newvalue是执行事务前D的值.在该算法中，优先对数据进行操作的事务会成功提交，并未考虑事务真正的优先级，且在实际的使用中会出现大量的事务重启，因此并不适用于实际的实时数据库.

2.2 OCC-DA并发控制

乐观动态调整串行化(Dynamic Adjustment of Serialization Order，OCC-DA)算法[5]，使用动态的时间戳(SOT)来标识事务，每个数据对象有读和写两个时间戳.对于事务来说，只有在其动态时间戳的值比数据对象的时间戳大时，才能对数据对象进行操作，否则事务必须重启.假定事务T1和T2，冲突事务集合T_set，数据对象D，大致的验证阶段算法描述如下：

Validate(T1){

if(T1.TS

RESTART T1；

if(T1.Priority

RESTART T1；

else

RESTART T2；

UPDATE D.WTS；

UPDATE D.RTS；

EXEC T1;

}

其中，RESTART表示重启事务，UPDATE表示更新时间戳.OCC-DA算法会根据优先级来决定冲突事务的重启，同时可以动态调整串行化的顺序，降低事务重启的概率.

2.3 OCC-DA-MCP并发控制

传统的OCC-DA算法在进行并行控制时，由于没有对事务时间截止期的验证，在事务发生冲突导致重启后可能会造成事务浪费的执行.而且在OCC-DA算法中，虽然有对于实时事务的优先级的描述，但是对于事务的重要度(即事务对实时数据库系统的价值)和实时数据的一致性这两点是没有考虑到的.针对OCC-DA算法的缺点，本文通过加入事务重要度、时间截止期和数据一致性的描述，提出了乐观多条件优先级动态调整串行化(OCC-Dynamic Adjustment of Serialization Multi Condition Pririoty，OCC-DA-MCP)并发控制算法.

OCC-DA-MCP算法中有3个事务集合：重要事务(Critic_Set)、活动事务(Active_Set)和搁置事务(Idle_Set).重要事务是执行等级最高的事务，算法总是会优先执行该集合中的事务，该事务的判定方法有两种，一个是硬实时事务，另一个是优先级达到重要事务判定阈值(PThreshold)的软实时事务和固实时事务，这类事务可以看作是优先级处于顶端的活动事务；活动事务会与验证事务进行冲突检测，算法在产生冲突时会依据优先级和时间截止期等条件对集合中事务的动态时间戳进行调整；搁置事务是截止期比较长，可以暂时等待的事务.设置活动事务和搁置事务两个集合，可以减少算法进行冲突检测时事务的数量，从而减少系统资源上的开销.

OCC-DA-MCP算法在OCC-DA算法的基础上加入了对事务重要度的描述，这样可以更大程度的保证重要事务的执行.同时在乐观控制的事务三阶段处理思想上，加入了事务分类阶段，这样做可以提高并发控制算法处理重要事务的能力.各阶段的描述如下：

1) 分类阶段

该阶段首先检测事务是否合法，通过合法性检测的事务会根据实时事务的类型来进行分类，如果事务不是重要事务，那么会根据事务的时间截止期将事务放入不同的集合中.假定实时事务T1，该阶段的具体算法描述如下：

if(Check(T1)){

if(T1.T==“硬实时事务” OR T1.P>PT)

Critic_Set.Add(T1);

else{

if(T1.Deadline > PThreshold)

Active_Set.Add(T1);

else

Idle_Set.Add(T1);

}

}

else

DISCARD T1;

其中，Check表示检测事务是否合法，Add表示在相应的事务集合中加入该事务.

2) 读阶段

事务在进入重要事务集合或者活动事务集合时会开始该阶段.在该阶段，事务会将需要操作的各数据的值读入局部变量区中，并将所有写操作的结果都保存在局部变量区中，同时验证事务操作数据的内部一致性.算法描述如下：

ReadPhase(T);

foreach(D∈T.DATA)

if(!CheckInConsistency(D))

DISCARD T;

其中，ReadPhase表示事务进入读阶段后，将需要操作的数据读到局部变量区并进行相关的操作，CheckInConsistency的作用是验证数据的内部一致性，如果不满足内部一致性，会返回假，此时事务会直接中止.

3) 验证阶段

验证阶段会对事务进行有效性的检测，同时会进行数据的外部一致性检测，判定是否可以将局部变量区中的数据复制到实时数据库中，如果判定通过，事务会进入写阶段.

假定事务T1处于验证阶段，事务T2是活动事务集合中的任意事务，以及数据对象D.将所有满足SOT(T2)SOT(T1)的事务集合记作BTS(T1)，当T1在读阶段读取D时，令TR(T1，D)=WTS(D).事务的验证阶段一共分为5步执行.

第1步：检测数据的外部一致性.如果D.ST+D.TI>TC，TC表示系统当前的时间，数据D满足外部一致性，否则不满足，当数据的外部一致性失效时，事务会中止.

第2步：检测验证事务是否和已提交的事务发生了冲突.如果SOT(T1)

第3步：检测验证事务的写操作是否都有效.如果SOT(T1)

第4步：检测验证事务与活动事务的数据访问冲突.比较验证事务T1的写数据集合与ATS(T1)集合中的活动事务T2的读数据集合，如果发生了冲突，则将冲突事务T2添加到冲突集合CT(T1)中.

第5步：检测活动事务与验证事务的数据访问冲突.比较BST(T1)或者CT(T1)中的活动事务T2的写数据集合与验证事务T1的读写集合，如果存在交集，则说明T2与T1发生了冲突.此时必须进行冲突解决，根据优先级和时间截止期选择被重启的事务.

根据事务验证阶段的执行内容，用WS(T)表示事务的写集合，RS(T)表示事务的读集合，事务验证阶段的算法描述如下：

Validate(T1){

if(D.ST+D.TI>TC)

DISCARD T1;

else{

if(T2∈Active_Set)

foreach(D∈RS(T1))

if(SOT(T1)

RESTART T1;

foreach(D∈WS(T1))

if(SOT(T1)

RESTART T1;

CT(T1).Clear;

if(T2∈ATS(T1))

foreach(D∈WS(T1))

if(D∈RS(T2))

CT(T1).Add(T2);

if(T2∈BTS(T1) || T2∈CT(T1)){

foreach(D∈RS(T1))

if(D∈WS(T2))

Conflict_Solve(T1，T2);

foreach(D∈WS(T1))

if(D∈WS(T2))

Conflict_Solve(T1，T2);

}

}

}

其中,Clear表示清空事务集合，Conflict_Solve表示事务冲突的解决.OCC-DA算法采用的是优先级的方式来解决冲突，低优先级的事务总是会首先重启，这样可以简化算法的执行，但是可能会出现浪费的执行的情况.例如，验证事务T1的优先级比活动事务T2的优先级低，且T1和T2出现了读写冲突，此时OCC-DA算法会直接重启T1，但是T2后来执行时超过了时间截止期，这样就导致了浪费的执行，同时，如果T2的时间截止期还比较充裕，而T1重启后离时间截止期也比较近，这样就导致了T1的执行是浪费的.因此在设计冲突解决策略时，OCC-DA-MCP算法引入了执行时间和时间截止期两个参数来避免浪费的执行.该阶段算法描述如下：

Conflict_Solve(T1，T2){

if(T1.P>T2.P)

ASS(T1).Add(T2);

else{

if(T2.AST-TC>Factor×T2.ET)

ASS(T1).Add(T2);

else if(T2.AST-TC

DISCARD T2

else

RESTART T1;

}

}

其中，ASS表示需要调整动态时间戳的事务，在写阶段会对该集合中的事务进行时间戳调整.Factor是T2剩余时间截止期的比例系数，实验表明取1.3～1.5时策略的效果比较好.

4) 写阶段

事务通过验证阶段后会进入写阶段，到达写阶段的事务总是会被提交.事务在该阶段会首先更新数据的读写时间戳和ASS集合中事务的时间戳，然后将局部变量区中的数据复制到实时数据库中，即完成提交.该阶段的算法描述如下：

foreach(T∈ASS(T1))

T.SOT=TC;

foreach(D∈RS(T1))

D.RTS=TC;

foreach(T∈WS(T1))

D.WTS=TC;

EXEC WS(T1);

3 并发控制性能分析

通过搭建的测试环境对相应的并发控制算法进行性能测试，取相同参数下的仿真实验10次结果的平均值作为一次实验的真正结果.测试中使用的参数，主要参考了以前的文献[6]，事务生成时优先级是根据最早截止期优先的策略分配的[7].表1中反映了系统的负载状态和事务的部分特性设置.

表1 实验参数及对应值

1) 截止期计算公式

DeadLine=AT+uniform(MinSlack，

MaxSlack) × ET，

(1)

式中，AT表示的是事务到达的时间，ET表示的是事务执行的时间，uniform是均匀分布函数.

2) 事务错失率计算公式

M_Ratio=Num_Miss ÷ Num_Total，

(2)

式中，M_Ratio是事务的截止期错失率，Num_Miss表示错失截止期的事务个数，Num_Total表示总的事务个数.

图1 WP为0.2时事务错失率Fig.1 Transaction miss rate when WP=0.2

图2 WP为0.3时事务错失率Fig.2 Transaction miss rate when WP=0.3

将WP值分别设置为0.2和0.3，并将事务到达率设置为变化量.如图1所示，此时WP为0.2，当系统事务到达率小于300，即负载较低时，OCC-DA算法和OCC-DA-MCP算法都能表现出比较好的性能，事务错失率几乎为零.随着事务到达率的

增加，OCC-CS算法性能降低的比较快，而OCC-DA算法和OCC-DA-MCP算法的错失率比OCC-CS算法要低很多，即性能要好很多.

如图2所示，此时WP为0.3，同一种算法的事务错失率总体趋势和WP为0.2时是一致的，即随着事务到达率的增加，事务错失率也增加.但是相较于WP为0.2时，OCC-DA-MCP算法能够比OCC-DA算法表现出更好的性能.由此可见，随着WP值的增加，OCC-DA-MCP算法能够更好的提高Redis的并发性能.

4 结束语

针对Redis并发控制性能低的问题，本文在参考OCC-DA算法的基础上，结合事务优先权和实时数据一致性，提出了改进算法OCC-DA-MCP.试验结果表明，OCC-DA-MCP算法能够提高Redis的并发性能.

[1] 黄健宏. Redis 设计与实现[M].北京：机械工业出版社， 2014．

[2] 曾超宇， 李金香. Redis在高速缓存系统中的应用[J].微型机与应用， 2013，32(12)：11-13．

[3] 祁 鑫， 王文海. 实时数据库系统并发控制机制综述[J].化工自动化及仪表， 2006，33(1)：47-50．

[4] 赖 歆. 基于Redis的分布式锁的实现方案[J].信息通信， 2016，166(10)：83-84．

[5] 边 远， 杨 静， 卢大勇. 一种改进的动态调整串行化顺序算法[J].计算机工程， 2008，34(3)：108-110．

[6] 刘云生， 夏家莉， 许贵平. 嵌入式数据库系统的事务调度[J].软件学报， 2002，13(8)：1692-1697．

[7] INDRAKSHI R.Real-time update of access control policies[J].Data and Knowledge Engineering， 2004，49(3)：287-309．

OCC-DA-MCPalgorithmbasedconcurrencycontrolofRedis

GUO Xuan, ZHOU Hao, LUO Wenhui

(School of Automation, Wuhan University of Technology, Wuhan 430070, China)

In order to improve the concurrency performance of Redis memory database, the existing memory database concurrency control (OCC-DA-MCP) algorithm is studied in the present work. And then Redis concurrency control is desighend and realized in combination of Redis architecture with OCC-DA-MCP algorithm. The simulation results show that the algorithm, to a certain extent, improves the problems of existing Redis concurrency control algorithm such as wasteful execution and unnecessary restart.

concurrency control; Redis; memory database

2017-05-11.

国家高技术研究发展计划项目(863计划-2015AA015904)．

*E-mail: 498820227@qq.com.

10.19603/j.cnki.1000-1190.2017.06.006

1000-1190(2017)06-0760-05

TP311.133.1

A