基于多管理节点的乐观锁协议

引用本文

郝娉婷, 胡亮, 姜婧妍, 车喜龙. 基于多管理节点的乐观锁协议. 2017, 47(1): 227-234
HAO Ping-ting, HU Liang, JIANG Jing-yan, CHE Xi-long. Optimistic lock protocol of multi-managed nodes. Journal of Jilin University Engineering and Technology Edition, 2017, 47(1): 227-234 复制到剪切板

Permissions

基于多管理节点的乐观锁协议

郝娉婷, 胡亮, 姜婧妍, 车喜龙

吉林大学计算机科学与技术学院,长春 130022

通讯作者:车喜龙(1982-),男,副教授,博士.研究方向:并行计算,机器学习.E-mail:chexilong@jlu.edu.cn

作者简介:郝娉婷(1990-),女,博士研究生.研究方向:分布式计算,计算机网络.E-mail:susan454@sohu.com

基金:欧盟第七框架国际合作项目(GA-2011-295222); 国家自然科学基金项目(61073009); 国家科技支撑计划项目(2014BAH02F03); 吉林省青年科学基金项目(20160520011JH).

摘要

针对悲观锁机制并行性不足的缺点,改进了Zookeeper的悲观锁机制并设计了一种乐观锁协议。通过研究分布式锁机制和Zookeeper的工作原理,提出了一种可以降低总执行时间的乐观锁协议,从理论上与三种不同协议进行了对比和分析,在保证数据一致性的同时,得出乐观锁协议为最优化设计,且对该协议的互斥性、死锁性和公平性加以证明。实验结果表明,乐观锁协议使系统性能有较大幅度提升,并且与其他协议相比,在总执行时间、占有带宽等方面均有一定优势。

关键词: 计算机系统结构; 分布式系统; 分布式锁; 乐观锁; Zookeeper

中图分类号:TP393 文献标志码:A 文章编号:1671-5497(2017)01-0227-08

Optimistic lock protocol of multi-managed nodes

HAO Ping-ting, HU Liang, JIANG Jing-yan, CHE Xi-long

College of Computer Science and Technology, Jilin University, Changchun 130022, China

Abstract

In order to improve the parallelism of pessimistic lock mechanism, an optimistic lock protocol was designed and applied for modifying the original lock mechanism in Zookeeper. By studying the mechanism of distributed lock and the working principle of Zookeeper, the execution time was decreased by the optimistic lock protocol. Theoretically compared with three other protocols, the optimistic lock protocol is the most optimized. Based on ensuring consistency maintenance, the optimistic lock protocol possesses mutual exclusion, non-deadlock and fairness. Simulation results show that the optimistic lock protocol significantly improves the data access performance, and outperforms the other lock protocols in execution time and bandwidth occupancy.

Keyword: computer system architecture; distributed system; distributed lock mechanism; optimistic lock; Zookeeper

Show Figures

0 引言

一个分布式系统^[1]是由若干相对独立的计算机组成。在分布式系统中分布式锁具备同步、互斥等功能, 主要负责保证数据的一致性和对数据的协同访问。很多商业系统(如Oracle parallel server、IBM GPFS、Red Hat GFS等)都使用分布式锁进行管理。

分布式锁^[2]依据并发控制方法可分为悲观锁和乐观锁。悲观锁对用户申请资源操作全部加锁, 而乐观锁对用户申请资源操作部分加锁。锁的思想在分布式系统中应用广泛。在文件管理方面, 文献^[3]采用租约机制调整了分布式并行系统Lustre中锁的粒度; 在数据库方面, 文献^[4]针对加锁粒度提出了基于全局目录的分布式数据库加锁管理算法; 在系统存储方面, 文献^[5]通过实验对比了乐观锁和悲观锁, 结果表明尽管由于用户的重复尝试会导致冲突率较高, 但乐观协调方式的并行性能仍优于悲观协调方式。

目前实现悲观锁思想的典型应用为Zookee-per^[6], 它是Hadoop的一个子项目, Zookeeper采用了基于悲观锁的协调方式并使用Lamport提出Paxos^{[7, 8, 9]}算法作为分布式互斥^[10]基础。Zookeeper具有容错性、高效性、扩展性等特点, 它提供简单的接口便于管理组、选举leader、保证数据一致性等。在一些文章中针对Zookeeper也进行了深入的研究。文献^[11]改进了Zookeeper的同步机制, 改进后的Zookeeper可以在服务端响应用户提交的一连串操作请求。但是在Zookeeper框架下仍存在并行性不足等缺点。

本文的核心工作是将乐观锁的思想运用到分布式集群管理中, 对Zookeeper悲观锁机制进行改进并且设计一种基于多管理节点的乐观锁协议, 该协议在开销较低的基础上增强了锁机制的性能, 提高了分布式系统协调能力和管理的效率。

1 Zookeeper和乐观锁

1.1 分布式锁

Zookeeper提供了一种典型的分布式协调服务, 以锁^[12]的方式管理集群内操作的先后顺序, 保证内容的一致性等, 如图1所示。

	Figure Option View Download New Window
	图1 Zookeeper工作过程Fig.1 Distributed workflow in Zookeeper

“ 下载-修改-上传” 作为计算机领域中的原子操作, 具有普遍研究意义。所以借此操作说明两种锁机制的区别, 并以此作为实验的基准测试。

1.2 Zookeeper悲观锁机制

Zookeeper使用了基于悲观锁的协调方式。当资源R_i被用户U_i占有时, Zookeeper不能接受用户U_j(i¹ j)对R_i的请求, 该请求将被挂起在等待队列, 直到U_j获得R_i。Zookeeper采用层次化目录结构, 每个路径下的Dnode有唯一标识, 本文以(Ri, “ read-modify-write” , SeqID)为语义表示Dnode, L为当前目录下的节点列表。当U_i提出对R_i的请求时, Zookeeper执行悲观锁机制, 如表1所示。

表1 悲观锁算法 Table 1 Pessimistic lock algorithm

表2 乐观锁算法 Table 2 Optimistic lock algorithm

1.3 乐观锁机制

乐观锁机制结合条件存储操作使资源处于无锁状态。系统通过比较U_i请求R_i时的版本号与系统内资源的版本号, 判别请求是否提交成功。乐观锁机制以这样的方式保证了数据的有序性和一致性, 合理地避免了悲观锁机制的长时间等待。

U_i先执行对R_i的修改。同时U_j( )仍然可以对R_i提交, 但是U_j能否成功提交请求需要系统比较版本号之后决定。若U_j提交R_i的版本号大于当前系统内的R_i版本号, 则U_j成功提交并上传R_i; 若失败, 则U_j请求被驳回可进行再次尝试。

2 O-C协议

本文针对悲观锁机制并行性不足的问题, 采用乐观锁的思想改进了Zookeeper, 并设计了基于多管理节点的O-C协议(Optimistic coordin-ation)。

2.1 O-C协议流程

本协议设定以下前提条件:①主要针对资源冲突小的情况; ②不考虑意外终止情况。协议中涉及到的变量定义见表3。协议工作的流程如图2所示, Coordination Server决定用户是否获得请求资源的锁; Data Server负责存储资源。

表3 变量说明 Table 3 Description of variables

	Figure Option View Download New Window
	图2 协议交互流程Fig.2 The coordination between each part in O-C protocol

协议具体步骤如下所示。

第1步 U_i建立到Coordination server的连接。

第2步 U_i向Coordination server提交下载申请, Coordination server将版本号V_s返回给U_i。

第3步 U_i开始从Data server下载资源R_i并在自己的Dnode上用版本号V_s对资源进行标记。(下载时间为t₁)

第4步 U_i修改R_i。(修改数据所用时间为t₂)

第5步 U_i以版本号V_u作为参数向Coordination server提交上传申请, Coordination server查询锁记录表检测是否有U_j(j¹ i)正在写相同资源。Coordination server比较U_i提交的版本号V_u与当前版本号V_s是否相等。最后Coordination S-erver将SameFlag_i(U_j)和VersionMatch返回给U_i。

第6步若SameFlag_i(U_j)=1且VersionMatch=1, 则U_i上传申请被Coordination server驳回, U_i等待t₃时间后重新执行第5步。因为R_i未过期, U_i重新执行第5步。

若SameFlag_i(U_j)=1且VersionMatch=0, 则U_i申请被Coordination server驳回, U_i等待t₄时间后重新执行第2步。因为R_i已过期, U_i重新执行第5步不可能成功。

若SameFlag_i(U_j)=0且VersionMatch=1, 则U_i申请被批准, Coordination server将R_i及U_i作为一个锁独立项添加进锁记录表。

若SameFlag_i(U_j)=0且VersionMatch=0, 则U_i申请被Coordination server驳回, U_i等待t₄时间后重新执行第2步。因为R_i已过期, U_i重新执行第5步不可能成功。

第7步 Data server对原R_i资源重命名, 然后U_i上传修改后的R_i到Data server, 并上传更新成功的标记, 标记文件留在对应资源附近。此时原R_i暂不删除。(上传时间为t₅)

第8步为保证上传过程的正确性, U_i确认更新成功后再删除标记文件和原R_i。若更新成功, U_i得到的返回值为0, 同时, Coordination server生成新的版本号 $\begin{matrix} {V_{s}}^{’} \end{matrix}$ 并查询锁记录表, 删除该U_i对应的锁独立项。然后进入第9步; 若更新失败, U_i得到的返回值为NULL, 返回第5步。

第9步 U_i断开到Coordination server的连接。(执行时间为t₆)

下面将对O-C协议进行详细分析, 协议分析中涉及到的符号说明见表4。

表4 主要符号说明 Table 4 Description of major symbols

针对单个用户的情况, 采用O-C协议对所用时间进行分析:

$T_{s} = (p_{i} + 1) \times (t_{1} + t_{2}) + q_{i} \times t_{3} + p_{i} \times t_{4} + t_{5} + t_{6}$ (1)

式中：

$0 \leq p_{i} \leq \frac{(n - 1) \bar{t_{5}}}{\bar{t_{4}}},$

$0 \leq q_{i} \leq \frac{(n - 1) \bar{t_{5}}}{\bar{t_{3}}} 。$

用户在申请上传资源和下载资源时, 可能会遇到驳回情况, 当该用户最后一个进行操作时, 驳回次数达到上限。

针对多个用户的情况, 采用O-C协议从总时间、失败次数、带宽等方面进行分析:

(1)总时间T_m

依据式(1)得T_m如下

$\begin{matrix} \begin{matrix} T_{m} = n \times \bar{T_{s}} < n \times (\bar{t_{2}} + \bar{t_{1}} + \bar{t_{6}} + \bar{t_{5}}) \\ T_{m} > \bar{t_{1}} + \bar{t_{2}} + \overset{n}{\sum_{i = 1}} p \times \bar{t_{3}} + \overset{n}{\sum_{i = 1}} q \times \bar{t_{4}} + \bar{t_{5}} + \bar{t_{6}} \end{matrix} \end{matrix}$ (2)

当每个用户的上传和下载请求针对同一资源时, 所有用户请求都是串行执行的, 系统花费总时间将达到最大值。当每个用户的上传和下载针对不同资源时, 系统花费总时间将达到最小值。

(2)请求失败的总次数F

$\begin{matrix} F = \overset{n}{\sum_{i = 1}} p_{i} + \overset{n}{\sum_{i = 1}} q_{i} \end{matrix}$ (3)

(3)带宽

$\frac{1}{n} \leq B_{r} \leq 100 %$ (4)

$B_{w} = \frac{1}{n}$ (5)

设定当n个用户同时执行下载或上传任务时, 带宽占用率为100%。当B_r=100%时, 表示参与此过程的所有用户都进行下载操作; 当B_r=1/n时, 表示只有某一个用户在进行下载操作。

4.用户与系统交互次数C_o

$\begin{matrix} C_{o} = n + \overset{n}{\sum_{i = 1}} p_{i} \end{matrix}$ (6)

依据式(6)可得:

$\begin{matrix} n \leq C_{o} \leq (n - 1) \times (1 + \frac{\bar{t_{5}}}{\bar{t_{4}}}) + n \end{matrix}$ (7)

在资源未过期而上传申请失败的情况下, 每个用户尝试的次数也是不确定的。由于用户进行每次操作的时间不同, 系统处理用户的操作请求时间也是不确定的, 所以每次用户申请资源时的等待次数也是不同的。结合式(7)得:

$\begin{matrix} \{\begin{matrix} C_{o} \geq (1 + \frac{\bar{t_{5}}}{\bar{t_{3}}}) \times (n - 1) + n \\ C_{o} \leq (1 + \frac{\bar{t_{5}}}{\bar{t_{4}}} + \frac{\bar{t_{5}}}{\bar{t_{3}}}) \times (n - 1) + n \end{matrix} \end{matrix}$ (8)

2.2 过渡协议的比较

过渡协议按照“ 下载-修改-上传” 逐渐去锁的过程进行演化, 如图3所示, 图中阴影部分表示协议加锁的阶段。协议a表示完全的悲观锁, 协议b、c和d表示3种不同粒度的乐观锁, 其中协议c是本文提出的O-C协议。下面对4种过渡协议进行详细分析。T_m(x)表示多用户情况下采用x协议所用总时间, F(x)表示多用户情况下采用x协议系统中请求失败的总次数, 其中x=a、b、c、d。

	Figure Option View Download New Window
	图3 过渡协议Fig.3 The transition among four types of protocols

2.2.1 协议a

协议a为悲观锁协议。时间为T_m(a), 失败次数为F(a)≤ n, 带宽为B_r=1/n, B_w=1/n, 协议a与系统的交互次数C_o为n≤ C_o≤ 2n+1。

2.2.2 协议b

协议b为在下载阶段解锁的乐观锁协议。U_i在修改资源时系统需要判别U_i是否获得锁, 若系统判别U_i没有获得锁则U_i继续等待或被系统驳回; 若系统判别U_i获得锁则U_i可执行对资源的操作。协议b将下载阶段解锁使T_m(b)< T_m(a)。协议b带宽为1/n≤ B_r≤ 100%, B_w=1/n。协议b与系统的交互次数C_o满足不等式(n-1)× (1+t₅/t₃)+n≤ C_o≤ (n-1)× (1+`t₅/t₃+t₅/t₄)+n。

2.2.3 协议c

协议c为O-C协议。与协议b相比, 由于用户修改阶段彼此独立, 不需要设定锁机制, 使T_m(c)≤ T_m(b), 因此协议c在设计上更为合理。与协议a相比, 协议c将下载和修改阶段解锁使T_m(c)< T_m(a), 但是在资源冲突多的情况下会使T_m(c)增加。协议c带宽为1/n≤ B_r≤ 100%, B_w=1/n。协议c与系统的交互次数C_o满足不等式(n-1)× (1+t₅/t₃+n≤ C_o≤ (n-1)× (1+t₅/t₃+t₅/t₄)+n。

2.2.4 协议d

协议d为在“ 下载-修改-上传” 阶段解锁的乐观锁协议。若U_i在上传后系统判别上传数据无效, U_i重新执行下载-修改-上传过程, 会增加U_i的执行周期, 导致T_m(d)增加且F(d)减少。但在采用协议d的情况下会使系统中资源的副本数量大量增加, 同时由于上传阶段的解锁, 每个用户都可以将自己的资源进行上传, 导致对系统的上传带宽有一定要求。协议d带宽为1/n≤ B_r≤ 100%, B_w=1/n。协议d与系统的交互次数C_o满足不等式(n-1)× (1+`t₅/t₃)+n≤ C_o≤ (n-1)× (1+t₅/t₃+t₅/t₄)+n。

综合以上几点因素对4种过渡协议进行分析和比较, 本文确定协议的重点评测值包括T_m和F, C_o与F存在正关联。带宽为协议辅助测评值, 带宽与每段时间内多用户请求任务的总时间有关。若系统运行的带宽受到实际情况的限制, 系统可对协议进行一定的调整。

3 O-C协议正确性分析

本节从协议的互斥性、无死锁和公平性3个角度证明协议的正确性。证明中涉及到的定义^[13]如下所示。

本文中U_i请求R_i的优先级定义为Pr(R_i)。

定义1 并发(Concurrent):

R_i和R_j是并发的当且仅当R_i在R_j的生存周期内产生或者R_j在R_i的生存周期内产生。

定义2 并发集(Cset):

Cset_i= {R_j| $\begin{matrix} {R_{j}}_{} \end{matrix}$ is concurrent with R_i} U {R_i}。

定义3 并发集首(Cheader_i):

Cheader_i:R_i:Pr(R_i)> Pr(R_j) ∀ R_i, R_j∈ Cset_k, i≠ j。

定义4 并发集尾(Ctailer_i):

Ctailer_i:R_i:Pr(R_i)< Pr(R_j) ∀ R_i, R_j∈ Cset_k, i≠ j。

定义5 前驱(Pred):

Pred:Pred(R_i, Cset_k)= R_j iff R_i, R_j ∈ Cset_k∧ Pr(R_i)< Pr(R_j)∧ ¬ (∃R_k∈ S| (Pr (R_i)< Pr (R_k)< Pr(R_j)))。

定义6.后继(Succ):

Succ:Succ(R_i, Cset_k)= R_j iff R_i, R_j∈ Cset_k∧ Pr(R_i)> Pr(R_j)∧ ¬ (∃R_k∈ S|(Pr(R_i)> Pr(R_k)> Pr(R_j)))。

对互斥性、无死锁和公平性的证明如下所示。

(1)证明用户互斥进入临界区

证明:采用反证法。

假设U_i和U_j占有相同资源R_i, 即∃i∃j(i≠ j)and(SameFlag_i(U_i)=1), and(SameFlag_i(U_j)=1)。则:

Pre(R_i, Cset_k)=Pre(R_j, Cset_k)

Succ(R_i, Cset_k)=Succ(R_j, Cset_k)

综上得出Dnode_i=Dnode_j且U_i和U_j的请求排列于并发集同一位置。依据协议第5步和第6步可知不存在多个用户同时获得对同一资源的锁, 若SameFlag_i(U_i)=1, 则SameFlag_i(U_j)=0。假设不成立, 得证该协议具有互斥性。

(2)证明用户无死锁:

证明:用户U_i在请求资源R_i时有两种情况:SameFlag_i(U_i)=1或SameFlag_i(U_i)=0。当用户间请求的资源无交集时, 系统不存在用户既占有又申请锁的死锁条件。当用户间请求的资源存在交集时, 即SameFlag_i(U_i)=1, SameFlag_j(U_j)=1, 表示U_i请求R_j, U_j请求R_i。分别对请求向未获得的资源进行下载操作和上传操作进行讨论。若U_i需要下载R_j, 根据乐观锁协议在“ 下载-修改-上传” 过程中不对下载过程加锁的特点, U_i会顺利执行完毕。若U_i需要上传R_j, 在协议中, 针对同一资源只有一个用户上传, U_i等待U_j上传完成再进行操作。综上得出该协议不会在运行过程中使系统产生死锁。

(3)公平性

证明:假设U_i请求资源的时间戳为T_i, U_j请求资源的时间戳为T_j且T_i< T_j, U_i请求R_i, U_j请求R_j, 依据协议第5步和第6步, 用户按照FIFS的分配原则获得资源, 因此SameFlag_i(U_i)=1。所以该协议具有公平性。

O-C协议满足互斥性且不会出现用户抢不到锁的情况, 系统通过FIFS的原则决定用户的请求顺序, 从而使O-C协议的正确性得到保证。

4 仿真实验及性能分析

仿真实验中将Zookeeper运行在分布式Server集群上, 以“ 下载-修改-上传” 作为基本操作。按照第三节对4种协议的比较, 协议c在设计上比协议b更合理, 协议d占用带宽和系统存储空间较大且较于协议c无明显优势, 依据分析结果选取两种典型协议, 即标准的悲观锁协议(协议a)和O-C协议(协议c)进行性能的对比。图4~图9中横坐标为实验次数, 纵坐标为每次结果执行50次后, 相应得出的平均结果。且在本实验中用户数目固定, 用户请求开始下载的时间、修改时间以及完成时间皆服从随机分布。实验环境为:Ubuntu11.04操作系统; Intel Core 2 Duo CPU 2.93 GHz。数据采用实验结果性能评价公式定义如下。

	Figure Option View Download New Window
	图4 多用户请求单一资源时的执行时间Fig.4 The execution time

	Figure Option View Download New Window
	图5 多用户请求单一资源时的失败次数Fig.5 The failure time

	Figure Option View Download New Window
	图6 多用户请求多资源时的执行时间Fig.6 The execution time

	Figure Option View Download New Window
	图7 多用户请求多资源时的失败次数Fig.7 The failure time

	Figure Option View Download New Window
	图8 多用户请求单一资源时的执行时间Fig.8 The execution time

	Figure Option View Download New Window
	图9 多用户请求单一资源时的失败次数Fig.9 The failure time

A_t为系统采用悲观锁协议和O-C协议处理任务的总时间比值:

$\begin{matrix} A_{t} = \frac{T_{m} (a)}{T_{m} (c)} \end{matrix}$ (9)

A_f为系统采用O-C协议和悲观锁协议处理任务的失败次数比值:

$\begin{matrix} A_{f} = \frac{F (c)}{F (a)} \end{matrix}$ (10)

A为总体改进性能评测值:

$\begin{matrix} A = \frac{A_{f}}{A_{t}} \end{matrix}$ (11)

若0≤ A< 1, 表示O-C协议相比于悲观锁协议性能较好; 若A≥ 1, 表示O-C协议相比于悲观锁协议性能较差。

针对多用户请求单一资源的情况实验结果见图4和图5。系统采用悲观锁协议的失败次数方差较小, O-C协议在用户冲突较多的情况下, 用户提出的请求被驳回的概率高, 用户需要重新执行, 所以情况变为系统中用户的请求被串行执行, 即只有上一个请求该资源的用户执行完“ 下载-修改-上传” 过程, 下一个用户才能开始执行, O-C协议退化成悲观锁协议, 同时由于O-C协议的内容中增加了用户再次发出请求的等待时间, 使系统执行的总时间和用户访问的次数增加。

针对多用户请求多资源的情况, 实验结果见图6和图7。此时系统在采用O-C协议时用户冲突小。多数情况下, O-C协议的失败次数较系统采用悲观协议有一定减少, 系统执行总时间也明显减少, O-C协议相较于悲观锁协议有明显优势。

针对在仅“ 下载” 与“ 下载-修改-上传” 比例为2:1的条件下多用户请求单一资源的情况, 实验结果见图8和图9。O-C协议在这种情况下, 由于用户间的冲突相较于多用户请求多资源的情况有所提高, 导致A_f均值有一定增加, 但O-C在系统执行任务的总时间上仍有明显优势, 使A_t均值较高, 所以A< 1, 系统采用O-C协议较采用悲观锁协议性能更好。

综合以上3种实验的结果可知, 系统采用O-C协议协调时, 用户等待请求执行的平均时间与总时间的比值约为1.53%左右。说明在实际情况中, 用户等待的时间较短, 只有小概率用户出现长时间等待, 系统出现用户"饿死"情况的概率较低, 同时O-C以小幅度增加的失败次数为代价, 换来系统执行总时时间的较大幅度减少, 从而提高系统整体协调处理任务的性能。

5 结束语

本协议扩大了乐观锁的应用范围, 使其不仅可以应用在数据库等方面, 也可将其应用到不同的分布式环境下。实验结果表明在多用户请求多资源以及存在仅“ 下载” 的情况下, 总时间有较大幅度的减少, 其失败次数也未骤增。再次验证O-C协议在性能上的明显优势。采用O-C协议的系统以较低的代价换取性能的提高, 且系统不会因为带宽等限制因素而影响传输效率。未来将主要针对参数t₃、t₄进行深入研究, 以达到减少冲突率并提高性能的目的。

The authors have declared that no competing interests exist.

参考文献

View Option

[1]	邵佩英. 分布式数据库系统及其应用[M]. 北京: 科学出版社, 2005: 25-31. [本文引用:1]
[2]	伍之昂, 曹杰, 王有权. 一种改进的死锁和活锁避免资源联合分配协议[J]. 电子学报, 2011, 39(11): 19-27. Wu Zhi-ang, Cao Jie, Wang You-quan. An improved deadlock and livelock free protocol for resource co-allocation[J]. Acta Electronica Sinica, 2011, 39(11): 19-27. [本文引用:1]
[3]	钱迎进, 肖侬, 金士尧. Lustre分布式锁管理器的分析与改进[J]. 计算机工程与科学, 2009, 31(A01): 146-149. Qian Ying-jin, Xiao Nong, Jin Shi-yao. Analysis and improvement of Lustre distributed lock manager[J]. Computer Engineering & Sci-Ence 2009, 31(A01): 146-149. [本文引用:1]
[4]	李章兵, 车乌江. 基于全局目录的分布式数据库加锁管理算法[J]. 计算机技术与发展, 2011, 21(9): 245-250. Li Zhang-bing, Che Wu-jiang. Locking management algorithm based on global directory in distributed database[J]. Computer Technology and Development, 2011, 21(9): 245-250. [本文引用:1]
[5]	Carns P, Harms N, Nimpe D, et al. A case for optimistic coordination in HPC storage systems[C]//High Performance Computing, Networking, Storage and Analysis (SCC), Boston, MA, 2012: 48-53. [本文引用:1]
[6]	Hunt P, Nonar M, Junqueira F P, et al. Zookeeper: wait-free coordination for internet-scale systems[C]//Proceedings of the 2010 USENIX Conference on USENIX Annual Technical Conference, 2010, 8: 9-23. [本文引用:1]
[7]	Lamport L. Paxos made simple[J]. ACM Sigact News, 2001, 32(4): 18-25. [本文引用:1]
[8]	Narger D, Lehman E, Leighton T, et al. Consistent hashing and rand om trees: Distributed caching protocols for relieving hot spots on the World Wide Web[C]//Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, EL Paso, TX, 1997: 654-663. [本文引用:1]
[9]	Lamport L. Time, clocks, and the ordering of events in a distributed system[J]. Communications of the ACM, 1978, 21(7): 558-565. [本文引用:1]
[10]	刘丹, 刘心松, 丘志杰, 等. 基于读写特征的分布式互斥算法[J]. 电子学报, 2004, 32(2): 326-329. Liu Dan, Liu Xin-song, Qiu Zhi-jie, et al. A distributed mutual exclusion algorithm based on read/write character[J]. Acta Electronica Sinica, 2004. 32(2): 326-329. [本文引用:1]
[11]	Nalantari B, Schiper A. Addressing the Zookeeper Synchronization Inefficiency[M]. Springer Berlin Heidelberg, 2013: 434-438. [本文引用:1]
[12]	George Coulouris, Jean Dollimore, Tim Kindberg, et al. Distributed Systems: Concepts and Design[M]. 5th Ed, USA: Addison-Wesley, 2011: 1-16. [本文引用:1]
[13]	王征, 刘心松, 李美安. 自适应Ad hoc 分布式互斥算法[J]. 小型微型计算机系统, 2007, 28(8): 1387-1392. Wang Zheng, Liu Xin-song, Li Mei-an. Adaptive distributed mutual exclusion algorithm for Ad Hoc networks[J]. Journal of Chinese Computer Systems, 2007, 28(8): 1387-1392. [本文引用:1]

2005

0.0

... 0 引言一个分布式系统^[1]是由若干相对独立的计算机组成 ...

2011

0.0

... 分布式锁^[2]依据并发控制方法可分为悲观锁和乐观锁 ...

2009

0.0

2011

0.0

2012

0.0

2010

0.0

... 目前实现悲观锁思想的典型应用为Zookee-per^[6],它是Hadoop的一个子项目,Zookeeper采用了基于悲观锁的协调方式并使用Lamport提出Paxos^[7,8,9]算法作为分布式互斥^[10]基础 ...

2001

0.0

1997

0.0

1978

0.0

2004

0.0

. 2004, 32(2):326-329

A distributed mutual exclusion algorithm based on read/write character

基于读写特征的分布式互斥算法

Liu Dan , Liu Xin-song , Qiu Zhi-jie

刘丹, 刘心松, 丘志杰

8010 Division,University of Electronic Science & Technology,Chengdu,Sichuan 610054,China

Based on LK algorithm,a distributed mutual exclusion algorithm—read/write mutual exclusion (RWME) algorithm is presented.It puts different mutual exclusion operations for reading request and writing request.The algorithm belongs to nontoken-based type.It saves the message complexity and still has T synchronization delay.A read/write globe clock stamp which based on Lamport clock stamp is defined for the read/write mutual operations.Using the read/write globe clock stamp,reading and writing requests can access critical sections with fairness and freedom from deadlock or starvation.Proved by performance analysis,the algorithm has high-performance.A correctness proof is provided.

在LK算法基础上,提出一种对读写请求作不同互斥处理的分布式互斥算法——RWME(read/write mutual exclusion)算法.在同步延迟仍为 T 的前提下,降低了传统非令牌类型互斥算法的消息复杂度.在Lamport全局时戳的基础上,定义了适合于读写互斥的全局时戳——读写时戳,并由其来保证各读写进程互斥访问临界区的公平性和正确性.通过对算法的性能分析验证其是高效的,并给出了正确性证明.

2013

0.0

2011

0.0

... 1 分布式锁Zookeeper提供了一种典型的分布式协调服务,以锁^[12]的方式管理集群内操作的先后顺序,保证内容的一致性等,如图1所示 ...

2007

0.0

... 证明中涉及到的定义^[13]如下所示 ...