基于向量时钟模型的NoSQL最终一致性的研究

罗 军，王 宏，李文生

重庆大学 计算机学院，重庆 400044

基于向量时钟模型的NoSQL最终一致性的研究

罗 军，王 宏，李文生

重庆大学 计算机学院，重庆 400044

随着Web 2.0时代的到来和云计算的兴起，传统关系数据库在应付web2.0网站，特别是超大规模和高并发SNS类型的网站时越发显得力不从心，暴露了很多难以克服的问题，NoSQL则由于本身的特点得到了迅速发展。NoSQL（Not Only SQL）是对不同于传统关系数据库的数据库管理系统的统称，它以模式自由的方式存储数据，提供了新型的访问接口，并在扩展性、可用性、灵活性等方面有了很大提高[1]。

作为衡量NoSQL数据库性能的重要指标，最终一致性对NoSQL的应用与发展起着重要作用。因此，如何提高NoSQL数据库最终一致性的性能，值得做深入的研究。

1 NoSQL数据库最终一致性的基本原理

1.1 CAP理论

CAP理论是NoSQL的重要理论基础之一，该理论首先把分布式系统的三个特性做了如下归纳[2-4]：

（1）一致性（Consistency）：分布式系统中的所有数据备份，同一时刻是否具有同样的值。

（2）可用性（Availability）：系统随时都可以进行读写操作，即每一个操作总是能够在确定的时间内返回。

（3）分区容错性（Partition Tolerance）：当集群中的部分结点发生故障，集群是否还能作为一个逻辑整体提供服务。

CAP理论指出，一个分布式系统不可能同时满足一致性、可用性和分区容错性这三个特性，最多只能满足两个[3-4]。对于分布式数据库系统，由于分区容错性是基本要求，因此设计NoSQL系统，就需要在一致性和可用性之间找一个平衡点。如果侧重点在一致性，就必须处理因为系统不可用而导致的写操作失败的情况；若侧重点在可用性，就要考虑读操作不能读到写操作写入的最新值。因此，系统的关注点不同，相应采用的策略也不一样。

NoSQL数据库通常选择放弃强一致性，用最终一致性的思想设计分布式系统[5]，从而使得系统可以达到很高的可用性和扩展性。

1.2 最终一致性

最终一致性是指，在分布式数据库中各结点的数据，不要求每一时刻都严格保持一致，只保证最终一致即可[6]。具体表现为，当分布式数据库接到一个写请求时，只选择结点中的一个或几个（通常在系统设计时确定）执行此操作，然后由这些结点向其他结点发送更新信息（每个结点有一个协调器，负责在数据变化时向其余结点发送同步信息），进而实现所有结点的一致，这就使系统具有了高可用性。然而，强一致性要求所有结点都执行此操作直到每个结点都成功后该写请求才返回成功，因此任何一个结点出了问题都将导致请求失败进而降低系统的可用性，这也印证了CAP理论的表述。

对于最终一致性，定义从更新发生时刻到所有结点都异步更新成功的时刻之间的时间段为不一致窗口[5]。不一致窗口是衡量最终一致性的重要性能指标，它直接反映了系统内数据达成一致的时间。不一致窗口的大小依赖于以下几个因素：数据同步方案、系统负载、交互延迟、副本个数等[6]。

2 问题描述

为了理解方便，设某NoSQL数据库由3个结点A、B、C构成，规定执行写请求的结点数为1。对于系统内某个数据，图1描述了随着时间推移，三个结点的数据变化情况，其中Di为数据状态，mi为数据的更新信息，Qi为请求（清晰起见，图中未显示），图中每个时刻具体情况的描述如下。

t0：初始时刻，A、B、C的数据同为D0。

t1：系统收到写请求Q1，由于设定执行写请求的结点数为1，因此假定A结点被系统指定执行此请求，执行后数据为D1，同时，A的协调器向其他结点发送更新信息m1，此时A的数据与B、C的不同。

t2：B、C收到m1并将数据修改为D1，此时各结点数据一致。t1与t2的时间间隔就是不一致窗口。

t3：系统收到写请求Q2并指定B执行此请求，B将数据D1修改为D2，同时发送m2到A、C结点。

t4：假设m2还未到A、C的时候，即t4时刻，系统收到写请求Q3并指定C执行此请求，C执行后的数据为D3，接着发送m3到A、B。此时，A、B、C的数据分别是D1、D2、D3。

t5：m2到达A、C，将A、C的数据修改为D2，显然，C结点最新的数据D3被D2覆盖了。

t6：m3到达A、B，将A、B的数据修改为D3。

经过分析，发现整个过程存在三个主要问题：（1）数据同步过程中发生了旧数据覆盖新数据的情况，同步信息到达的先后顺序影响了数据的正确性。t5时刻，m2到达C结点，因为无法分辨新旧，D2错误覆盖了D3。（2）各结点数据没有实现最终一致性。t6时刻，A、B、C的数据分别为D3、D3、D2。（3）不一致窗口内的读请求无法处理。t4时刻，结点的数据分别是D1、D2、D3，此时的读操作将无法返回数据并且一直处于等待状态，直到各结点数据一致。

对于同步过程中数据的错误覆盖，试想在NoSQL多结点、高并发读写数据的情况下，同步信息的到达将更难以预料和控制，这就导致不一致窗口的持续变大以及数据的混乱[7]，严重影响最终一致性，并且，对于不一致窗口内的读请求无法处理的情况，目前也没有更好的办法。

图1 结点的数据流程图

3 基于向量时钟模型的最终一致性解决方案

向量时钟模型的基本思想是：为数据引入版本的概念，各结点不只保存数据的值，还有数据的版本信息。版本信息包括版本向量[8]和时间戳[9]，版本向量是一个n维向量，它反映了数据在各个结点被修改的次数[10]，时间戳用以在向量间无直接关系时比较先后顺序[9]。此外，模型还定义了一个“祖先-后代”关系，用来在版本向量不一致时比较其是否存在直接的先后顺序。对比于已有的向量时钟模型，该模型不仅能够判断两个具有因果关系的事件的顺序，又能对全局中任意两个事件（无因果关系的）的顺序进行判断。

3.1 形式化定义

定义1（数据的版本向量）设系统结点数为N，对于一份数据，定义第i个结点持有的版本向量Vi为：

定义2对于版本向量Vi=(a1，a2，…，ak，…，an)，定义Vi[k]为第k个结点对数据的修改次数，值为ak。

定义3对于版本向量Vi和Vj，∀k∈(1，2，…，n)，都有Vi[k]≤Vj[k]，则称Vi标志的数据为Vj标志数据的“祖先”，Vj标志的数据为Vi标志数据的“后代”。

3.2 冲突检测和处理方案

基于向量时钟模型的解决方案的核心思想是：当数据不一致时，首先比较版本向量间是否互为“祖先-后代”关系，如果存在，则“后代”标识的数据较新，如果不存在，则通过比较时间戳的时间先后判别数据顺序，最后做一些版本合并的工作。

通过对NoSQL最终一致性全过程的分析，归纳出三类主要的操作：结点的写操作、同步信息到达后的操作、读操作。定义每类操作的具体规则如下：

（1）结点的写操作。对于结点i，执行写操作时，记录当前时间戳Tnow，更新Vi及Ti：

（2）同步信息到达后的操作。对于同步信息发送方的j结点及接收同步信息的i结点：

①判断Vj是否是Vi的“后代”，若是，说明 j结点的数据是在i结点的基础上修改的新版本，因此将Vj及Tj代替Vi和Ti，比较结束，反之，执行②。

②比较Tj与Ti，如果Tj的时间晚于Ti的时间，表明 j的数据比i的数据新，因此将 j的数据及Tj替换i的数据和Ti，然后执行③，反之，直接执行③。

③比较Vi[j]和Vj[j]的大小，大的直接替换Vi[j]。

（3）读操作。首先读取所有结点的数据，若数据一致，则返回此数据，反之，对不一致的数据采取两两比较的方法，返回最新的数据，比较的规则如下：

①判断Vj和Vi是否互为“祖先-后代”关系，若是，则“后代”标识的数据较新，比较结束，反之，执行②。

②比较Tj与Ti的时间，选出较新的时间戳标识的数据，比较结束。

3.3 冲突检测和处理过程描述

为了对比分析，同样采用上面的例子。基于向量时钟模型的解决方案为数据标识了版本信息，最终一致性的全过程如图2所示（清晰起见，图内省略了数据的时间戳）。

图2 基于向量时钟模型的结点数据流程图

t0：各结点拥有数据，版本向量（0，0，0）表示数据没有被任何结点修改过。

t1：A结点执行Q1，根据结点写操作的规则，执行后数据为 D(1，0，0)，版本向量（1，0，0）表示数据在A结点被修改了

1一次。同时，记录时间戳t1并向其他结点发送更新信息m1。

t2：B、C收到m1，根据同步信息到达后的操作规则，首先检查数据是否是的“后代”，由定义3知，是的后代，因此将数据修改为，同时将时间戳t1代替t0。

t3：B结点执行写请求Q2，将修改为，记录时间戳t2，同时，向A、C结点发送m2。

t4：m2还没有到A、C的t4时刻，C结点处理了Q3请求，将修改记录时间戳t3，同时发送 m3到A、B。此刻，A、B、C的数据分别是、)、。

t5：m2到达A、C。对于A结点，由于新数据是的“后代”，因此用D2和t2替换原数据D1和t1；对于C，原本持有数据，由于与不存在“祖先-后代”关系，于是比较t2和t3，由于t3比t2新，所以D3新于D2，因此D2不会覆盖D3，由于更新信息的发送方是B，比较V2[2]和V3[2]的大小，最终得出处理冲突后的数据为，版本向量（1，1，1）标识此数据在三个结点各被修改一次，判断正确。

t6：m3到达A、B，由上所述，更改后A、B数据都为，此时，系统达到了最终一致性，三个结点都持有最新的数据，并且版本向量（1，1，1）客观反应了数据在各结点的修改次数。

3.4 方案讨论

向量时钟模型的特点在于为数据加入了版本信息，当数据不一致时可以根据版本信息做出正确判断从而避免数据冲突，提升了最终一致性的性能。同时，该方案也存在着不足，首先，版本信息的引入导致系统需要额外的存储空间，当结点数量很多时，对系统的存储空间提出了更高要求，另外，随着时间推移，版本向量将逐渐增大，因此需要定时地将向量清空到初始状态，何时以及如何清空也有待于进一步研究。

4 对比分析

由于两种方案在t5前的时刻各结点对应的数据相同，因此列出t5和t6时刻的数据状态对比如表1。对比分析表明，基于向量时钟模型的方案解决了原方案的问题：（1）避免了数据错误覆盖。t5时刻，C结点数据为，而原方案的数据则是 D2，显然正确反映了数据的值及被修改的信息。（2）系统实现了最终一致性。t6时刻，各结点的数据都为。（3）不一致窗口内的读请求返回较新数据。t4时刻，结点数据各不相同，此时有读请求到达，将对A、B、C两两做比较，最终返回D3给用户。

表1 数据状态对比表

为了便于理解问题的所在，采用了一个简单的实例分析了一致性的全过程，可以得出结论，在NoSQL多结点、高并发读写的复杂情况下，基于向量时钟模型的最终一致性解决方案由于定义了版本信息及冲突处理方案，能够有效解决最终一致性过程中遇到的问题。

5 结束语

研究了NoSQL数据库的最终一致性，分析了最终一致性方案存在的问题，提出了一种基于向量时钟的最终一致性模型，并给出冲突检测和处理方案。对比分析表明，方案很好地解决了问题，在NoSQL的设计过程中具有较好的应用价值。

[1]Neal L.Will NoSQL databases live up to their promise?[J]. Computer，2010，43（2）：12-14.

[2]Johannes E.SQL databases v.NoSQL databases[J].Communications of the ACM，2010，53（4）：10-11.

[3]Rabi P P，Manas R P，Suresh C S.RDBMS to NoSQL：reviewing some next-generation non-relational database’s[J].International Journal of Advanced Engineering Sciences and Technologies，2011，11（1）：15-30.

[4]Xiang Peng，Hou Ruichun，Zhou Zhiming.Cache and consistency in NoSQL[J].Computer Science and Information Technology，2010，6（3）：117-120.

[5]成汝震，尚志恩，刘宏忠，等.分布式系统数据一致性处理的研究[J].计算机科学，2001，28（8）：69-71.

[6]肖迎元，刘云生，邓华锋.适合分布式实时内存数据库的全局一致性模糊备份策略[J].计算机科学，2006，33（8）：151-154.

[7]Leslie L.Time，clocks，and the ordering of events in a distributed system[J].Communicationsofthe ACM，1978，21（7）：558-565.

[8]Martin H.Using vector clocks to visualize communication flow[J].IEEE Computer Society，2010，42（10）：241-247.

[9]董宏，孙永强，候丽敏.抽象事件的时间戳[J].电子学报，1999，27（11）：44-46.

[10]董宏，孙永强.抽象事件的完备逻辑时钟[J].软件学报，1999，10（11）：1169-1173.

LUO Jun,WANG Hong,LI Wensheng

College of Computer Science,Chongqing University,Chongqing 400044,China

Eventual consistency is an important indicator when measuring the performance of NoSQL database,it has a significant influence in the development of NoSQL.In order to solve the problems of eventual consistency,this paper proposes a model based on vector clocks.The model adds a version to data.By importing vector and timestamp,it can mark data with the version. Furthermore,a solution of solving conflicts is presented.By comparative analysis,the solution improves the performance of eventual consistency and has a good application value in the design process of NoSQL database.

NoSQL database;eventual consistency;vector clocks;timestamp

最终一致性作为衡量NoSQL数据库性能的重要指标，对NoSQL的应用与发展起着重要作用。针对最终一致性解决方案存在的问题，提出基于向量时钟的最终一致性模型。模型为数据加入了版本的概念，通过版本向量和时间戳的引入，为数据标识了版本信息，同时给出了冲突检测和处理方案。对比分析表明，方案很好地解决了问题，提高了最终一致性的性能，在NoSQL数据库的设计过程中具有较好的应用价值。

NoSQL数据库；最终一致性；向量时钟；时间戳

A

TP392

10.3778/j.issn.1002-8331.1202-0462

LUO Jun,WANG Hong,LI Wensheng.Research on eventual consistency of NoSQL database based on vector clocks model. Computer Engineering and Applications,2013,49（23）：100-102.

罗军（1961—），男，副教授，主要研究领域为数据库及其办公系统自动化、语义网与知识管理系统；王宏（1987—），男，硕士生。E-mail：wanghong9909@qq.com

2012-02-24

2012-07-12

1002-8331（2013）23-0100-03