分布式锁服务算法

《分布式锁服务算法》由会员分享，可在线阅读，更多相关《分布式锁服务算法（9页珍藏版）》请在金锄头文库上搜索。

1、分布式锁服务-debby设计与实现 单栋栋，赵东升，樊楷，苏飞 摘要： 我们实现了一个分布式锁服务系统，并能提供可靠的存储服务。系统的接口非常简 单，类似普通文件的接口。我们设计的重点在于系统的可靠性与可用性，而系统的性能放 在次要位置。同时我们也实现paxos协议，并用它为整个系统提供可靠容错的系统日志。 1.背景介绍 随着计算机网络技术的飞速发展，出现了越来越多的分布式系统，我们利用这些系统 已提高现有系统的性能，可用性和稳定性。尽管分布式系统的设计已日趋成熟，但要在分 布式系统中进行协调和信息交流仍然不是一件容易的，特别在松耦合的分布式系统中，所 有的信息传递只能通过网络来完成，必须面临

2、网络丢包、延迟甚至瘫痪等等复杂的问题。 要在这样的系统中都实现可靠的一致性协议来进行信息的交流，对于系统设计而言是非常 困难的，而且有一些是在应用中没有办法实现的。因此，我们希望提供一种非侵入式的服 务来帮助分布式系统各个成员间的动作协调和信息交流，通过使用这一服务，各个分布式 系统的成员可以非常简单的达成同步，而不需要在系统内部加入复杂的协调机制。因此， 我们设计并实现了debby分布式锁服务系统，这是一个类似于提供全文件读写的分布式文 件系统的结构，它设计的目标并非提供海量数据的存储，而是用于提供具有高可靠性和高 可用性的锁服务，同时可以方便高效的信息发布机制。为了保证debby系统的可靠

3、性，我 们的系统设定了5个服务器来组成一个debby实例，只有一个服务器用来向外提供服务， 而其它服务器都作为备份服务，用来在主服务器崩溃时继续提供服务。为了在5个服务器 之间提供一致性保证，我们还在底层实现了Paxos协议，只要有半数以上的debby服务器 能够正常运行，就可以提供服务。 利用debby系统，现在分布式系统可以非常便捷的进行同步协调和信息发布。比如当多 台服务器提供同一服务时，往往需要选择其中一台服务器来作为主服务器，把其他服务器 作为备份服务器，而且当主服务器崩溃时，又要能及时选出新的主服务器来提供服务。如 果没有debby系统，在分布式系统内部实现这样的备份机制非常困难，

4、唯一的办法或许就 是通过Paxos协议来达到一致性，而有的时候甚至Paxos协议也无法派上用场，比如当只 有一个备份服务器的时候。然而利用的debby，实现上述功能变得非常简单，只需要所有 的服务器都到debby系统中去获取一个互斥锁，然后获得锁的服务器就自动成为主服务 器。只要所有的服务器都遵守这一约定，就保证了系统中只会有一个主服务器。debby提 供了非常简单易用的信息发布机制，在获取到互斥锁后，服务器可以通过debby提供的分 布式文件服务，在文件写入自己的地址，其他服务器以及客户就可以非常容易的通过读取 debby文件内容来得到服务器的地址。如果主服务器崩溃，debby系统会自动释放

5、互斥 锁，并且通过事件机制来通知其它服务器来重新选择主服务器。 Google公司已经实现了类似的分布式锁服务系统Chubby，并广泛的应用于内部系统 中，他们的经验表明这样的系统具有非常好的可用性和可靠性，能够给其他分布式应用的 构建带来非常大的帮助。 2.系统设计 2.1整体设计Debby结构图 如图所示，一个debby 服务器可以同时为多个客户端提供服务。客户端通过调用 debby的client library ，和服务器通信。客户端和服务器的通信建立在ICE远程过程调用 的基础上。在服务器端，可以同时有多个debby server，其中一个是leader，另外的是 replica（图中有

6、3个server）。每个debby server上面独立运行服务器端的程序，包括文 件管理，事件管理，Session管理等。服务器端的操作的一致性通过底层的paxos协议来 实现。服务器提交给paxos的操作，都会记录日志信息。 2.2服务器设计 服务器通过向客户端提供接口，并且调用底层的 paxos协议，来实现最终的锁机制， 并提供最终的可靠服务。 2.2.1 服务器的通信部分 服务器通过ICE的远程过程调用机制，来和客户端通信。通过服务器为客户端提供的 接口，debby的客户端库可以连接到服务器，并且得到一个唯一的连接标识。通过这个标 识，客户端库可以关闭连接，创建文件、目录，删除文件、目

7、录，读写文件，注册事件， 删除事件，保持心跳，判断文件的类型等等。当某些操作发生错误的时候，服务器端会向 客户端抛出一个异常。 2.2.2一致性的保证 服务器端通过调用底层的paxos协议，来保证服务器操作的一致性。每次服务器要进 行数据的修改操作的时候，例如创建文件，修改文件，删除文件等，都要把操作提交给 paxos协议，paxos会保证每个操作都在服务器上执行，或者都不能执行。也就是是保证 操作的一致性。 2.2.3 Session的设计每个Session是一个客户端和一个debby服务的关系。通过心跳机制，客户端和服务器 保持联系。在每个心跳到来的时候，服务器会把发生的事件返回给客户端。

8、 2.2.4文件、目录的设计 对于每个Session，debby提供一个简单的文件系统接口，文件和路径的格式类似于 UNIX，例如/ls/foo/dir/file。文件系统向外提供通常的文件系统服务，例如文件、目录的 创建，文件、目录的修改、删除等。debby应该向客户端提供对临时文件进行操作的服 务。临时文件被客户端创建，在Session失效的时候，临时文件应该被删除。 为了方便，以及提高性能，debby的文件和目录都放在内存中，定期进行snapshot，将文 件系统的内容flush到磁盘。在系统恢复的时候，会根据磁盘的内容恢复文件系统。 2.2.5事件机制的设计 对于每个Session，

9、debby提供一个事件管理器，事件管理器会记录客户端已经注册的 事件、和已经发生的事件。对于已经发生的事件，服务器会在每个keepAlive的远程过程 调用的时候，将客户订阅的事件捎带返回，同时在服务器端删除这些已经发生的事件。 2.3客户端设计 利用服务器端提供的接口，我们通过客户端来最终实现锁机制，并向外提供服务。 我 们希望客户端向外提供尽量易于理解的接口，从而可以让用户可以方便的使用debby系统 的服务。 客户端通过ICE库来和服务器进行远程调用，并且通过定期的keepAlive信息保持和服 务器的会话。每次客户端与服务器建立会话后，都得到一个独一无二的句柄，并且以后所 有的操作都通

10、过这一句柄来完成，从而可以在每次操作时判断用户的身份。尽管在应用程 序中，可以有多个对象使用同一个客户端的服务，但在服务器看来，一个客户端只对应唯 一的用户。 客户端向外提供的API可以分为两个部分，一部分是实现类似于普通文件系统的目录操 作，另外一部分则用来提供全文读写、锁服务以及事件注册。 在提供目录操作的部分，我们的接口与普通文件系统非常类似，具体的操作包括 create(),remove(),mkdir(),exist(),isdir(),list()。通过这些操作，用户可以修改系统目录结 构，创建和删除文件和目录。与普通的文件系统不同的是，我们在create接口中提供了是 否创建临时

11、文件的选项，如果创建的是临时文件，那么当这个客户端与服务器失去连接 后，debby服务器会自动删除临时文件。这可以作为一种信息发布的方式，也是我们实现 锁机制利用的底层特性。 我们提供了read()和write()操作来进行全文读写，即一次读或者写整个文件的内容。之 所以这样设计，是因为debby中的文件其主要作用是为了提供一种信息发布的机制，而不 是作为大规模数据的存储。为了防止用户的误用来对debby的整体服务性能造成影响，比 如存储非常大的文件，我们对文件的大小进行了限制，目前暂定为1M。这样规模的文 件，我们可以很方便的只提供全读和全写的操作，由用户自己来确定文件内容的格式。我 们提供

12、了lock()和release()操作来提供锁服务，当多个用户想要获取某个资源时，应当首 先获取对那个资源的锁，才可以安全的使用资源。当完成对资源的使用时，用户应当调用 release()操作来是释放操作，从而使得其它用户可以使用资源。因为Chubby的使用数据 表明几乎所有用户使用的都是互斥锁而非共享锁，因此目前我们只提供互斥锁服务。 我们还提供了事件机制，通过事件机制，用户只需要在某个事件上注册好回调，当事 件发生时，就会自动调用用户注册的回调函数。通过这一机制，用户不需要通过轮询来获 得信息，大大减轻了服务器的负担，使其具有更好的可扩展性。目前我们提供的事件包括 EventCreated

13、, EventRemoved, EventChanged, EventLockChanged, EventArbitrary五 种。前三个事件分别代表目录或文件的创建、删除和改变，这里目录的内容改变指的是目录内文件的创建或删除。第四个事件是指在某个路径上的锁发生改变，包括锁被获取或释 放。第五个事件则是指在一个路径上的所有事件，包括创建、删除、改变以及锁的改变。 2.4 snapshot机制设计 Debby的paxos框架保证了各个replica存放数据的一致性。也支持备份在crush掉之后 恢复。到目前为止，所有的故障恢复均基于log，log存放在稳定存储器（硬盘）中。但由 此引发了新问题：

14、随着系统运行，日志将会越来越多。这有两方面问题：log的存储需要 无限量的磁盘空间，并且更糟的是，这也可能会导致恢复时间越来越长。 这里介绍的snapshot（快照）机制想法很简单。就是要将文件系统的数据结构直接序列 化到磁盘上，这样之前的日志就不再需要了。于是可通知paxos部分将log删除。当然， paxos部分并不知道任何有关的数据结构，因此，application进程必须负责snapshot的执 行。 debby提供了snapshot机制，允许客户端应用程序通知文件系统执行snpsoht操作。用户 应用程序可在任何时间发起snapshot命令。当snapshot操作完成，snapsho

15、t部分应通知 paxos部分以删除其过时的snapshot存储和log。当某台服务器crush掉之后恢复时， snapshot类将负责为其从磁盘中导入最新的文件数据结构，然后重放截断日志，以重建 服务器的服务环境。 当然snapshot机制也增加了一些复杂性：在实现snapshot机制之前，crush掉的服务器在 恢复时只需从其他机器获得最近的log即可进行更新。而实现snapshot机制之后，如需保 持状态的一致性，得包括进最近的log和snapshot复本。 2.5容错日志设计 Debby系统的主要设计目标是高可靠性与高可用性，这主要依靠多台服务器一起运行 来实现。一台机器坏悼都有备份机接

16、替工作，但如果保证系统中的机器数据的一致性是一 个非常大的问题。我们主要用paxos一致性协议，它保证每一时刻，系统中的大部分机 器的状态都是一致的，状态不一致的机器可以通过一定方法恢复到一致的状态。 paxos保证系统的一致性主要靠容错日志，系统的每次操作paxos都会把这个操作记录 在日志中，通过这个日志就能过从错误中恢复。我们的系统中，要写入日志的值就可要对 数据库进行操作的值。 基本的paxos主要分为三个步骤4： 一.有多少机器中通过一些算法选出一个leader 二.选出的leader可以提交决议到系统中，leader发送消息给其它机器，其它机器回 复leader 三.当leader收至半数以上的应答，就发消息给其它机器，表明可以记日志。 基础的paxos协议没有对那个状态不一致的系统进行处理，在我们的容错日志设计中， 有第一与第二步中间加了一步准备阶段。当leader被选出来已后，向其它机器发一个消 息，表明自己是leader，并把当前的系统状态发给大家。其它机器根据leader发过的状态 信息，判断自己的信息是不是最新，返回给leader自己的状态，lead