西电毕业设计要求翻译1万词的参考文献, 本着不做无用功的的态度就翻译了一篇之前一直没来及细看的论文.
摘要
在本文中, 我们描述了ZooKeeper, 一个用于协调分布式应用进程的服务. 由于ZooKeeper是关键基础设施的一部分, 所以ZooKeeper旨在提供一个简单和高性能的内核, 来在客户端建立更复杂的协调原语. 它把群组消息传递、共享寄存器和分布式锁服务等元素整合到一个集中式服务中. ZooKeeper暴露的接口具有共享寄存器的免等待功能, 以及类似于分布式文件系统的缓存失效的事件驱动机制, 以提供一个简单而强大的协调服务. ZooKeeper接口能够实现高性能的服务. 除了无等待的特性外, ZooKeeper还为每个客户端提供了先进先出的请求执行保证, 并为所有改变ZooKeeper状态的请求提供线性化的保证. 这些设计上的决定使我们能够实现一个高性能的处理流水线, 读取请求由本地服务器来满足. 我们表明, 对于目标工作负载, 即2:1 到100:1的读写比, ZooKeeper可以每秒处理几万甚至几十万的事务. 这种性能使ZooKeeper可以被客户端应用程序广泛使用.
介绍
大规模的分布式系统需要不同形式的协调. 配置是一种最基本的协调. 在这种最基本的形式下, 配置只是一个系统进程的参数列表, 更复杂的系统有着动态的配置参数. 组内成员和领导者的选举在分布式系统中也非常常见: 经常, 有些进程需要知道哪些进程是在线的, 这些进程控制着什么. 锁是一种强大的协调原语, 他实现了对关键数据的互斥操作.
协调的一个方法是为不同的协调需求开发服务. 比如, Amazon Simple Queue Service就注重与实现队列. 也有其他的服务用来选举领导者以及配置. 一个更强大的原语可以实现不太强大的原语, 比如Chubby是一个有强大同步能力的锁服务. 然后, 锁可以用来实现领导者选举等原语.
在设计我们的协调服务时, 我们放弃了在服务端实现特定的原语, 而选择暴露一些API, 服务端可以使用这些API来实现它们自己需要的原语. 基于这样的选择, 协调内核出现了, 他可以在不改变服务端核心的情况下实现新的原语. 这种方法让多种形式的协调可以适应不同的应用程序的要求, 而不是让开发人员限制在一套固定的原语上.
在设计ZooKeeper的API时, 我们放弃了阻塞的原语, 比如锁. 阻塞的原语在协调的服务中可以导致运行缓慢, 或者出问题的客户端拖慢快速客户端的性能, 产生负面的影响. 如果处理请求依赖于其他客户端的响应, 那么服务的实现就会更加复杂. 因此, 我们的系统, ZooKeeper实现了一个操作简单的无等待的数据对象的API, 这些对象像文件系统一样被分层管理. 实际上, ZooKeeper的API类似于其他文件系统的API, 如果只看API的签名的话, ZooKeeper似乎和Chubby一样, 只不过没有带锁的方法, open和close. 然而, 实现无等待的数据对象时ZooKeeper和其他的基于阻塞原语的系统最大的区别之一.
虽然无等待的属性对于性能和容错非常重要, 但是他并不足以实现协调. 我们还必须为操作提供顺序保证. 具体地说, 我们发现保证所有操作的先进先出和写的线性一致就能够有效的实现服务, 并且足以实现应用需要的协调原语. 实际上, 我们可以用我们的API对任何数量的进程达成共识, 并且根据Herlihy的层次结构, ZooKeeper实现了一个通用对象.
ZooKeerper服务包括了一个使用复制来达到高可用性和性能的服务器集群. 他的高性能可以保证包含了大量进程的应用程序可以用这样的一个协调内核来管理所有的协调工作. 我们可以使用一个简单的流水线结构来实现ZooKeeper, 并且能支持成百上千的请求, 同时能保证低延迟. 这样的流水线机制本身就可以实现来自一个客户端的操作的先进先出.保证客户端的先进先出顺序可以让客户端能够异步的提交工作, 这样客户端就可以同时开始多个操作. 这样的特性是非常需要的, 比如当新的客户端成为领导者后, 他必须对元数据进行管理和正确的更新, 如果没有这样的功能, 初始化的时间可能就是几秒钟, 而不是毫秒量级的.
为了保证更新的操作满足线性一致性, 我们实现了一个基于领导的原子性广播协议, 叫做Zab. 一个典型的ZooKeeper应用程序的工作负载是被读操作主导的, 因此, 对读操作的拓展是非常必要的. 在ZooKeeper中, 服务器只在本地处理读操作, 不会使用Zab来进行排序.
在客户端缓存数据是非常重要的提升读性能的技术. 比如, 对于一个进程来说, 缓存现在领导者的id是非常有用的, 而不是每次需要知道领导者的时候都去探测ZooKeerper. ZooKeeper使用一个观察机制, 来使得客户端缓存数据, 而不需要直接管理客户端的缓存. 通过这种机制, 客户端可以观察某个特定数据对象的更新, 并且在数据被更新时收到通知. Chubby直接管理客户端的缓存, 为了让所有客户端的缓存失效, 他会在更新时阻塞. 在这种设计下, 如果某个客户端运行缓慢或者出现错误, 这次更新就会被推迟. Chubby使用租约机制来防止一个客户端永远的阻塞整个系统. 但是租约只会控制缓慢的客户端或者运行出错的客户端的影响, ZooKeeper的观察机制能够避免这种问题.
在这片论文中, 我们讨论了我们的设计和实现. 有了ZooKeeper, 我们能够实现我们程序需要的所有同步原语, 即使只有写操作是线性一致的. 为了验证我们的方法是有效的, 我们展示了我们如何用ZooKeeper实现一些同步原语.
总之, 这篇文章的主要贡献是:
- 协调内核. 我们提出了一个无需等待的协调服务, 为分布式系统提供了较为宽松的一致性保证的服务. 特别地, 我们描述了我们对协调内核的设计和实现, 我们已经在许多关键的应用中使用该内核来实现各种协调技术.
- 协调方式. 我们展示了如何使用ZooKeeper来构建更高级别的协调原语, 甚至
- 协调的经验. 我们分享一些我们使用ZooKeeper的方法, 并评估其性能.
ZooKeeper服务
客户端通过API使用ZooKeeper客户端库来想ZooKeeper提交请求. 除了提供API供客户端联系ZooKeeper外, ZooKeeper库还负责管理客户端和服务器之间的网络连接.
在本节中, 我们首先提供一个ZooKeeper服务端高层次描述, 然后讨论了客户端使用的与ZooKeeper服务器交互的API.
术语
在本文中, 我们使用客户端表示ZooKeeper端使用者, 服务器表示提供ZooKeeper服务端进程, znode表示ZooKeeper数据中在内存里的数据节点, 被组织在一个称为数据树的层次结构中. 我们还用术语更新和写来指代所有可能会修改数据树状态的操作. 客户端连接ZooKeeper时会建立一个会话, 并得到一个会话ID, 通过这个会话ID来发送请求.
服务概览
ZooKeeper给所有客户端提供一个数据节点的抽象, 这些数据节点被组织在一个分层管理的命名空间内. znode是这个层次结构里的数据节点, 客户端通过ZooKeeper的API来操作这些节点. 分层的命名空间常常出现在文件系统中, 这是一种很好的抽象方式, 可以更好的组织应用程序的元数据. 要引用一个znode, 我们使用UNIX标志中的文件路径. 比如, 我们用/A/B/C表示znode C, C的父节点是B, B的父节点是A. 所有的znode都保存数据, 并且所有的节点, 除了临时节点, 都可以有子节点.
客户端可以创建两种znode:
- 常规节点. 客户端可以通过显式地创建和删除来操作常规节点.
- 临时节点. 客户端可以创建这些节点. 他们要么显式地删除这些节点, 要么等待系统在会话结束(正常结束或者客户端出错)后自动删除这些节点.
此外, 当创建新的节点时, 客户端可以设置一个顺序标志. 被创建的设置了顺序标志的节点有一个点掉递增的计数器. 如果n是新的节点, p是父节点, 那个n的顺序标志不会小于p下其他的所有节点.
ZooKeeper实现了观察机制watch, 允许客户端在不轮询的情况下收到对象更新的通知. 当一个客户端读一个对象并且设置了观察标志时, 服务器会正常完成操作, 并且保证在数据更新时通知客户端. watch是一个一次性的触发器, 一旦他们被触发, 或者会话被关闭, 他们就失效了. watch只通知数据发生了变化, 但是不提供变化的内容. 比如一个客户端对一个数据设置了watch, 然后这个数据变化了两次, 客户端会收到一次这个数据变化的通知. 会话的变化事件, 比如链接丢失, 也会被发送给watch的回调, 以通知客户端watch的通知可能会被延迟.
数据模型
ZooKeeper的数据模型本质上是一个有着简化API的文件系统, 只包含了对数据的完全读和写. 或者可以看成是一个带有层次结构的键的键值对表. 层次化的命名空间给为不同的应用程序分配不同的子树, 并设置他们的权限带来了方便. 我们还用目录的概念在客户端建立起更高级别的原语, 将在2.4节详细讲到.
不同于文件系统的文件, znode节点并不是为了存储一般文件设计的. 相反, znode可以被映射到客户端应用程序的抽象结构, 通常对应着用来协作的元数据. 例如, 图1中我们有两个子树, 一个给app1, 一个给app2. app1的子树实现了一个简单的组成员协议: 每个客户端进程i代表着 p_i节点, 代表着这个进程还在运行.
虽然znode没有被设计成一般的数据存储, ZooKeeper允许客户端在节点中存储一些元数据或者配置. 例如, 在一个基于领导者的程序中, 让一个程序知道现在的领导者是谁是很有用的. 为了完成这个目标, 我们可以让领导者把这个信息写入到一个固定的znode上. znode也有与自身相关的原信息和时间戳, 以及版本号, 这样可以让客户端追踪数据的变化, 根据节点数据的版本来选择性更新自己的数据.
会话
一个客户端连接到服务器后就会启动一个会话. 会话有一个超时时间. 如果超过这个超时时间服务器还没收到来自客户端的消息, 就会认为这个客户端出错了. 一个会话可能会被客户端显式地结束, 也有可能是服务器认为这个客户端出错了, 就把这个会话结束. 在一个会话内, 客户端会收到一系列他的执行状态的变化. 会话可以让客户端透明的在ZooKeeper集群中从一个客户端转移到另一个客户端, 并在这些服务器之间保持数据.
客户端API
我们展示了ZooKeeper的API的一部分, 并讨论了他们的语义.
create(path, data, flags):
创建一个znode, 路径是path, 存数据data, 返回这个znode的名字. flags可以设置这个节点的类型是临时的还是常规的, 并且设置顺序标志.
delete(path,version):
如果节点的版本是version, 就删除这个节点.
exists(path, watch):
如果这个节点存在, 就返回true. 如果不存在返回false. watch标志允许客户端在这个node上设置watch.
getData(path, watch):
返回数据和元数据, 包括版本信息等. watch标志跟exists的watch一样, 只不过在节点不存在时就不会设置watch.
setData(path, data, version):
如果版本匹配, 就写入data.
getChildren(path, watch):
返回node的子节点列表.
sync(path)
等待这个操作开始时所有未完成的操作传播到客户端连接的服务器上. 目前path参数没用.
所有的操作都有同步和异步的版本. 应用程序在单线程执行操作时可以使用同步操作, 这样这个操作会进行必要的阻塞. 异步的API允许应用程序同时并行进行多个ZooKeeper操作. ZooKeeper客户端保证每个操作的回调都被按顺序调用.
注意ZooKeeper不使用节点的ID来访问节点. 每个请求都包含了要操作的节点的完整路径. 这样不仅简化了API, 也消除了服务器需要额外维护的状态.
每个更新的操作都有一个期望版本号, 能让服务器做条件更新. 如果目前的节点版本号和提供的不匹配, 这个更新就会失败. 如果期望版本号是-1, 就不会做版本检查.
ZooKeeper的保证
ZooKeeper有两个基本的顺序保证:
- 线性写. 所有更新ZooKeeper状态的操作都保证线性一致性, 尊重先后顺序.
- 客户端的先进先出. 一个客户端发送过来的所有请求都是按照顺序执行的.
注意这里的线性一致性不同于Herlihy最初提出的线性一致, 我们称之为异步线性一致(A-linearizability). 在Herlihy最初提出的线性一致中, 一个客户端只能同时发出一个请求, 即客户端是单线程的. 在我们的定义中, 我们允许客户端同时发出多个操作, 因此我们可以选择不保证这些操作的顺序或者保证先进先出的顺序. 我们选择了后者. 注意到所有符合线性化的结果都满足异步线性化, 因为达到异步线性化的系统一定都达到了线性化. 因为只有更新的请求是异步线性化的, ZooKeeper在每个副本上都可以处理读请求. 这样可以让系统在扩大服务器数量时, 性能也可以线性地拓展.
为了理解这两种保证是怎么互相作用的, 考虑以下的场景. 一个包含了一些进程的系统选举一个领导来指挥进程. 当新的领导者接管了这个系统时, 他必须修改大量的参数, 并在完成时通知这些进程. 我们有两个重要的需求:
- 当新领导在更新状态时, 我们不希望其他进程使用正在被改变的配置.
- 如果配置还没更新完新领导就死了, 我们不希望进程使用更新了一半的配置.
注意分布式锁, 比如Chubby提供的锁, 可以让我们完成第一个需求, 但是不能完成第二个需求. 在ZooKeeper中, 新领导可以指定一个路径作为``就绪''节点; 其他进程只有在这个节点存在时才会使用过配置. 这个新领导在改配置之前删掉这个就绪节点, 改完之后新建就绪节点. 所有的这些改变可以通过流水线异步发布来快速的更新配置. 即使一个改变操作的延迟只有2毫秒的量级, 如果操作只能串行的发出, 一个需要更新5000个不同的节点的新的领导者将会话费10秒钟. 如果可以异步发起请求, 这些操作不会花费超过1秒. 因为ZooKeeper的顺序保证, 如果一个线程看到了就绪节点, 说明他能看到所有的修改过的配置. 如果新的领导者还没做完所有配置就死了, 其他进程也不会看到就绪节点, 也就不会用这个配置.
上面的方案还有一个问题, 如果一个进程先看到了就绪节点, 然后新领导者开始修改配置, 然后这个进程开始读取了正在修改的节点怎么办. 这个问题被通知的顺序保证解决了: 如果一个客户端正在watch一个变化, 这个客户端会在他看到修改过的数据之前, 收到一个数据被修改的通知. 因此, 如果一个读到就绪节点的进程请求关注了那个节点, 他可以在他使用修改后的配置之前收到一个数据变化的通知.
当客户端之间有着除了ZooKeeper之外的其他沟通渠道时, 会出现另一个问题. 比如, 两个客户客户端A和B在ZooKeeper中有一个共享的配置, 还有一个共享的沟通管道. 如果A改了ZooKeeper中的配置并通知了B, B就会期待自己重新读取ZooKeeper就可以拿到新配置. 但是如果B联系的ZooKeeper服务器稍微比A的慢了一点, 他就有可能读不到新配置. 用以上的保证, B只要先发起一个写操作, 然后再发起一个读操作, 就可以保证自己拿到最新的数据(写的线性一致保证B的写操作一定晚于A的所有写操作, 客户端的FIFO保证了B的读一定可以读到之前写操作之后的数据). 为了让这个场景更高效, ZooKeeper提供了sync请求: 如果后面跟着的是读操作, 这就构成了一个慢速读操作. sync保证了目前所有的写操作都在读操作之前完成, 这样做省去了一个写的开销. 这个原语与ISIS中的flush原语很相似.
ZooKeeper还有两个可用性和持久性保证: 如果ZooKeeper集群中的大多数服务器在线并互相通信, 整个服务就时可用的. 如果服务对一个操作返回了成功, 那么无论这个系统崩溃了多少次, 只要有足够数量多服务器最终能够恢复, 这些操作都会被保持.
原语的例子
在这一节, 我们展示了如何使用ZooKeeper的API实现更强大的原语. ZooKeeper服务对这些更强大的原语一无所知, 因为这些原语都是使用ZooKeeper的库在客户端上实现的. 一些常见的原语比如组成员管理和配置管理是无需等待的. 对于其他的, 比如说rendezvous原语, 客户端需要等待一个事件. 即使ZooKeeper是无等待的, 我们也可以利用ZooKeeper实现高效的阻塞原语. ZooKeeper的排序保证允许对系统状态进行高效的推理, 而watch机制提供了高效的等待.
配置管理
ZooKeeper可以用来实现在分布式应用程序中动态的配置管理. 一个最简单的配置存储在一个znode中, . 进程以的完整路径名启动. 启动的进程通过读取得到配置并且设置watch标志为true. 如果中的配置更新了, 进程就会收到通知, 并读取新的配置, 然后再次设置watch为true.
注意在这个方案中, 如大多数使用watch的情况一样, watch保证进程拿到的是最新的消息. 比如, 如果一个watch了的进程被通知了更改, 并且在他进行下一次读的时候又发生了三次更改, 这不会影响这个进程的正常工作, 因为这三个更改消息对于进程来说通知的都是这个进程早就知道的信息: 已经过期了.
会合(Rendezvous)
有时候在一些分布式系统中, 系统的最终配置往往是不清楚的. 比如, 一个客户端想要启动一个主进程和一些工作进程, 但是启动进程的工作是由一个调度器完成的, 所以客户端不能提前知道需要给工作进程的一些信息, 比如主进程的地址和端口供他们连接. 我们使用ZooKeeper的会合节点来处理这个事情. 会合节点是由客户端创建的. 客户端把的完整路径作为主进程和工作进程的启动参数传入. 当主进程启动后, 他会把自己的地址和端口写入. 当工作进程启动后, 他们读取并设置watch为true. 如果还没有信息, 工作线程会等待直到被通知已经更新. 如果是一个临时节点, 主进程和工作进程还可以watch, 等待客户端会话结束后被删除, 然后他们就清理自己.
组成员管理
我们使用临时节点来实现组成员资格. 具体来说, 临时节点可以让我们看到创建这个节点的会话状态. 我们首先指定一个节点代表一个组. 当一个组成员启动时, 他会创建一个临时节点在下面. 如果每个进程都有一个独一无二的名字或ID, 就可以用这个名字作为这个节点的名字. 否则, 进程可以创建节点时带有SEQUENTIAL标志, 这样就可以得到一个独一无二的名字. 进程可以把自己的一些信息, 比如地址和端口放入创建的子节点中.
子节点在创建之后, 如果进程正常启动, 他就不需要做任何操作. 如果进程出错或者结束了, 因为是临时节点, 这个节点会自动被删除.
进程通过拿到的子节点列表就可以得到组的在线成员. 如果一个进程想要监控组成员的变化, 可以通过每次获取组成员列表的时候都设置watch标志.
简单的锁
虽然ZooKeeper不是一个锁服务, 但是他可以用来实现锁. 使用ZooKeeper的应用程序通常会只使用根据他们需求定制的原语, 比如上文提到的这些. 这里我们通过展示怎么实现锁来说明ZooKeeper可以实现很多的同步原语.
最简单的锁实现是使用``锁文件''. 这个锁表示为一个节点. 为了得到这个锁, 客户端通过使用EPHEMERAL标志创建一个指定的临时节点. 如果创建成功, 这个客户端就持有了锁. 否则, 客户端可以读取这个锁文件, 并带上watch标记, 这样当锁的拥有者释放锁时, 客户端就会被通知到. 客户端要么显式删除锁文件, 要么等待系统在会话结束自动删除锁文件, 其他客户端发现文件被删除后会自动重试上锁.
虽然这个锁可以用, 但是也有一些问题. 比如, 这个锁会产生惊群效应. 如果有很多客户端等待获取这个锁, 一旦这个锁被释放时他们都回去竞争这个锁, 但是最终也只有一个客户端拿到锁. 并且, 他只实现了互斥锁. 接下来的两个原语展示了如何解决这些问题.
没有惊群效应的简单锁
我们定义了一个锁节点l来实现这个锁. 直观地说, 我们让所有客户端排队, 并且按照请求的时间依次获得锁. 这样, 客户端就可以通过以下的操作来尝试得到锁.
%code
第一行create操作的SEQUENTIAL标记给所有客户端上锁的尝试排序了. 如果客户端的节点时所有节点中最小的, 他就得到了锁. 否则, 节点等待一个已经拥有了锁或者在他前面拿到锁的的节点的更新信息. 通过只watch一个在他之前拿到锁的节点, 就可以在锁被释放或者一个上锁请求被取消时只唤醒一个进程. 当被watch的节点被删除之后, 进程还需要再次判断自己是不是id最小的, 如果时最小的才证明自己拿到了锁. (前面的节点被删除可能是锁被释放, 也有可能是上锁请求被取消.)
释放锁很简单, 就是把那个节点删掉就行. 创建节点时如果创建的是临时节点, 那在进程崩溃时系统会自动删掉这些上锁节点, 相当于自动释放了这些锁.
总之, 这样上锁的方案有以下几个优点:
- 节点的删除只会让一个客户端启动, 因为一个节点只会被一个进程watch, 所以没有惊群效应.
- 没有轮询和超时机制.
- 因为上锁的实现机制, 我们可以通过查看ZooKeeper的数据来观察锁的竞争, 打断上锁, 以及调试上锁时出现的问题.
读写锁
为了实现读写锁, 我们稍微改变了一下上锁的方法, 并且实现了单独的读锁和写锁. 释放锁的方法和全局锁的释放一样.
这个上锁的机制和之前的方法有些许区别. 写锁只是改了个函数名. 因为读锁可以共享, 第三行和第四行变化了一下, 因为只有之前的写锁会阻止一个读锁的上锁. 这里可能会出现惊群效应, 当一个写锁被删掉时, 之后的很多读锁都会被释放. 实际上, 这种惊群效应是我们期望得到的, 这些读锁都应给被释放, 因为之前没有了写锁.
双重屏障
双重屏障允许客户端在计算的开始和结束进行同步. 当有足够多的进程进入到屏障中, 进程就会一起开始他们的计算, 并在完成时离开屏障. 我们在ZooKeeper中使用一个节点代表屏障, 用来表示. 每个进程通过创建一个节点作为的子节点, 并在离开时删除这个子节点来取消注册. 进程可以在的子节点数量超过阈值时进入屏障, 并在所有的进程都删掉自己的子节点时离开屏障. 我们使用watch机制来高效的等待进入屏障和离开屏障. 要进入, 进程需要watch一个在子节点中的就绪节点的存在, 这个节点由创建节点时导致的子节点数量达到阈值的进程创建. 要退出屏障时, 进程可以watch随便watch一个子节点并当他消失时判断是否可以退出.
ZooKeeper应用
我们现在描述一些使用ZooKeeper的应用程序, 并简单的解释怎么使用它. 使用到的原语都会加粗.
抓取服务
爬虫抓取时搜索引擎的一个重要部分, 雅虎抓取了数十亿的网络页面. 抓取服务是雅虎的一部分, 目前已经进入了生产环境. 本质上说, 他有一个主进程来控制抓取页面的进程. 主进程提供给抓取进程配置, 而抓取进程写回他们的状态和健康状况. 使用ZooKeeper来控制抓取服务端好处体现在主进程从错误中恢复, 在出错的情况下保证可用性, 以及对服务器和客户端解耦, 允许他们通过读取ZooKeeper中的状态来把请求发送给健康的服务器. 因此, 文件系统主要使用ZooKeeper来维护 配置元数据, 以及 选举领导者.
图2展示了一个ZooKeeper服务器管理的抓取服务三天内读写的流量. 为了生成这张图, 我们每一秒钟都数了一下操作的数量, 每个点代表着这一秒钟的操作数. 我们发现读操作的流量远大于写操作. 在速度大于每秒1000次请求的时间段, 读写比基本在10:1至100:1之间. 在这个负载中, 读操作有 getData(), getChildren()和 exists(), 发生率依次增加.
Katta
Katta是一个分布式的索引器, 使用ZooKeeper来写作. 这是一个非雅虎程序的例子. Katta使用分片来划分索引的工作. 主服务器把分片后的任务发送给工作服务器, 并且追踪进度. 工作服务器可能会出错, 所以主服务器必须把任务重新分配到分片服务器上. Katta使用ZooKeeper来追踪主服务器和工作服务器的状态( 组成员管理), 处理领导者的崩溃( 领导选举). Katta还使用ZooKeeper来追踪并传播任务的分发( 配置管理).
雅虎信息代理
雅虎信息代理是一个分布式的发布-订阅系统, 这个系统管理数千个主题, 客户端可以在里面发布和接受消息. 这些主题分布在多个服务器上来提供可拓展性. 每个主题都使用主服务器备份的方法来保证消息在多个服务器之间复制, 保证消息的传递. 组成系统的服务器采用一个无共享的分布式结构, 这让协调的正确性非常重要. 系统使用ZooKeeper来管理标题的分配( 配置管理), 处理机器的崩溃( 组成员管理和 故障检测), 以及控制系统操作.
图3展示了信息代理系统的节点数据结构. 每个代理域都有一个名为nodes的节点, 在他之下每个组成信息代理系统的活动的服务器都有一个临时节点. 每个服务器服务器在nodes下的临时节点提供了组成员的信息以及状态信息. 叫做shutdown和migration_prohibited的节点被所有服务器监视着, 并且允许对整个系统的中心化控制. topics目录下每个主题都有一个子节点. 这些主题子节点下面有代表着主服务器和备份服务器的节点, 以及所有订阅这个主题的服务器的节点. 主服务器节点和备份服务器节点不仅允许其他服务器发现现在谁管理着这个标题, 还能处理 领导选举以及服务器崩溃.
ZooKeeper的实现
ZooKeeper通过在每个服务器上复制ZooKeeper的数据提供了高可用性. 我们假设服务器会崩溃, 并且这些有问题的服务器会在之后一段时间重新恢复. 图4展示了ZooKeeper服务的一些高层次的组件. 接收到一个请求时, 服务器会首先进行一些准备工作(请求处理器). 如果这个请求需要在多个服务器上协同(写请求), 就会使用一个共识协议(一个原子广播的实现), 最终所有的服务器都会执行这个操作到被所有服务器复制的ZooKeeper数据库中. 如果是读操作, 服务器可以简单的读取本地数据库的状态并且对请求进行返回.
被复制的数据库是一个内存中的数据库, 包含了整个数据树. 每个树里的节点默认包含最多1MB的数据, 这个上限可以在特殊情况下改变. 对于可恢复性, 我们高效的把所有更新日志写入到硬盘里, 并且强制所有写操作在被应用到内存中数据库前先写入到硬盘里. 实际上, 跟Chubby一样, 我们保存一个包含着所有应用过的操作的回放日志, 并且定期生成内存中数据库的快照.
每个ZooKeeper服务器都直接服务客户端. 客户端每次只向一个服务器提交请求. 向我们之前注意到的一样, 读请求直接从各个服务器的本地的数据库拿到返回. 而修改系统状态的写请求, 会被一个共识协议处理.
作为协议的一部分, 写请求被转发到一个特殊的服务器上, 叫做领导者. 其他的服务器叫做跟随者. 跟随者接受领导者包含状态变化的消息, 并对状态变化达成共识.
请求处理器
因为消息传递层时原子性的, 所以我们保证本地的备份永远不会出现分歧, 尽管在某些时刻一些服务器可能会比其他服务器执行更多的事务. 与从客户端发来的请求不同, 事务是幂等的. 领导者收到写请求之后, 会计算出系统更新后的状态, 并转换成一个带有新状态的事务. 新状态必须要计算, 因为这时候可能会有未写入数据库的事务. 比如一个客户端发出了一个条件的setData请求, 并且请求里的版本号和这个znode将要变为的版本号一样, 那么服务器会产生一个setDataTXN请求, 包含了新的数据, 新的版本号, 以及新的时间戳. 如果发生了错误, 比如版本号不匹配, 或者znode不存在, 会产生一个errorTXN错误.
原子广播
所有更新ZooKeeper状态的请求都会被转发给领导者. 领导者执行这些请求并把这些请求广播出去, 使用一个原子广播协议Zab. 收到请求的服务器会在状态改变后回复客户端. Zab默认使用简单的多数原则来对一个请求进行决议, 所以当大多数服务器工作正常时, Zab和Zookeeper就可以正常工作. 为了实现高吞吐量, ZooKeeper尝试让请求的处理流水线是满的. 流水线上可能会有几千个请求. 因为状态依赖于之前的状态变化, Zab提供了比一般的原子广播更强的顺序保证. 更准确的说, Zab保证一个领导者按照他收到请求的顺序来广播变化, 并且新的领导在收到之前的领导者所有变化之后才开始广播自己的变化.
一些实现细节简化了我们的实现, 并提供了高性能. 我们使用TCP传输, 这样消息的顺序就由网络来保证. 使用Zab选出的领导者作为ZooKeeper的领导者, 这样创建事务和提出事务可以用一个进程. 对于内存数据库, 我们使用WAL记录所有的提议.
备份的数据库
每个备份在内存中都有一个ZooKeeper的状态. 当一个ZooKeeper服务器从崩溃中恢复时, 他需要恢复他的初始状态. 重放所有的消息来恢复状态需要花费很长时间, 所以ZooKeeper使用周期的快照, 每次只需要从一个快照开始恢复一小段消息. 我们把ZooKeeper的快照叫做模糊的快照, 因为我们在生成快照的时候不会去锁住ZooKeeper的状态, 而是在使用深度优先搜索读取每个节点的数据和元数据时做一次原子性的读, 并写入磁盘. 因为最后的模糊快照可能只应用了在生成快照期间产生的变化的子集, 所以最终的快照可能不代表任何时刻的ZooKeeper的状态. 然而, 因为状态是幂等的, 只要我们按照顺序读日志, 我们可以把一个日志执行多次.
比如, 假设一个ZooKeeper系统中有两个节点: /foo和/goo, 值分别为f1和g1. 当一个模糊快照开始创建时, 版本号都是1, 接下来有三个更改操作.
处理完这些操作后, /foo和/goo分别值为f3和g2, 版本号分别为3和2. 然而, 一个模糊快照可能会记录/foo为f3, /goo为g1, 这不是任何一个时刻的ZooKeeper状态. 如果服务器崩溃, 并且从这个快照开始恢复, 最终也能恢复到之前的状态.
客户端-服务器交互
当一个服务器处理写请求时, 他同时发出并清空所有与这次更新相关的观察请求. 服务器按照顺序处理写请求, 并且不会同时处理其他的写和读请求. 这保证了通知的严格一致性. 服务器在本地处理通知, 只有被客户端连接的服务器才会追踪并为客户端触发通知.
读请求在每个服务器本地处理. 每个读请求被处理的时候会被标上一个zxid, 对应着这个服务器看到额最后一个事务. 这个zxid定义了读请求和写请求之间的偏序关系. 通过在服务器本地处理读操作, 我们得到了优秀的读性能, 因为这只是一个内存中的操作, 不设计磁盘和共识协议的运行. 这个设计是我们实现优秀读性能目标的关键.
快速读操作的一个不足的地方是不保证读操作的优先性. 读操作可能会返回一个过期的数据, 即使一个写操作已经被执行了. 不是所有的应用都需要保证这种顺序, 但是有些确实需要. 我们实现了sync原语. 这个原语是阻塞的, 会等待所有机器按照leader的顺序执行所有操作. 为了保证读出来的是最新的数据, 客户端会先调用sync函数, 然后再调用read. 对客户端操作的先进先出顺序和sync原语的保证让客户端的读操作能反映出sync之前所有发起操作的结果. 在我们的实现中, 我们不需要原子的广播sync原语, 只需要在领导者和执行sync的机器之间的请求队列最后加一个sync操作就行. 在本文的工作中, 机器必须保证领导者没有变化. 如果还有没有执行的事务, 跟随者就没办法怀疑领导者. 但是如果没有事务需要被commit, 领导者必须要发起一个空的事务并把sync操作放在空事务之后. 在领导者没有什么负载的时候, 这样做有很好的性质, 不需要额外的广播操作. 在我们的实现中使用了超时机制, 这样领导者就能在追随者放弃他们之前发现自己已经不是领导者了, 所以我们不需要空事务.
ZooKeeper服务器按照每个客户端的FIFO顺序处理请求. 回应的时候包含了与这次响应相关的zxid. 即使是在一段没有活动的时间中, 心跳包也会包含服务器最近一次收到的zxid. 如果客户端连接到了一个新的服务器, 服务器会检查这个客户端最近的zxid和自身的zxid. 如果客户端的zxid比服务器的zxid更新, 服务器在追上客户端的进度之前不会建立链接. 客户端一定可以找到另一个zxid比他更新的服务器, 因为客户端只会看到被大部分服务器都执行的zxid. 这个性质十分重要.
为了检测客户端会话断开, ZooKeeper使用了超时机制. 领导者发现如果一段时间内没有任何服务器从一个客户端收到消息, 就认为这个会话超时了. 如果一个客户端以足够的频率发送消息, 他就没必要发送其他的消息. 否则, 客户端需要在没有太多活动的时期发送心跳包. 如果客户端不能够和服务器通过发送请求或者心跳包建立, 就会通过连接另一个ZooKeeper服务器来重新建立会话. 为了避免会话超时, ZooKeeper客户端库会在闲置s/3秒后发送心跳包, 没有收到服务器响应的2s/3后更换到新的服务器, s是会话的超时时间.