光与影的个人博客

NEUCoder

0%

ZooKeeper论文总结

发表于 更新于 分类于 ，

分布式消息中间件-ZooKeeper

线性一致性（linearizability）

线性一致性是指分布式系统面对网络延迟和系统故障保证不同分布之间的数据一致性，使分布式系统在客户端看起来就像一个没有副本的单机系统。

  • 也成为 原子一致性（atomic consistency），强一致性（strong consistency），立即一致性（immediate consistency） 或 外部一致性（external consistency ）。

  • 换一个角度：一旦新的值被写入或读取，所有后续的读都会看到写入的值，直到它被再次覆盖

线性一致性例子如下：

  • 其中Client B最后一个读取请求读到了2，由于Client A在其时间点前的一个读读到了最新的写入4，所以Client B的读取结果违背了线性一致性
  • 通过记录所有请求和响应的时序，并检查它们是否可以排列成有效的顺序，通过该方式判断系统是否满足线性一致性

可串行化（Serializability） VS 线性一致性（Linearizability）

两者衡量的问题：

  1. 可串行化针对的是多个并发数据库事务，这些并发事务之间没有特定的顺序。可串行化指的是可以找到任意一个可行事务执行顺序，使得数据库的状态改变符合实际情况。（ multi-operation, multi-object, arbitrary total order）
  2. 线性一致性针对的是多个具有严格时序的事务，事务的发生顺序由全局时钟（也可能是逻辑时钟）衡量。线性一致性指的是按照事务之间的时序，判断按照该时序，系统状态变化是否出现冲突（single-operation, single-object, real-time order）

另外两者应用领域不同：

  1. 可串行化对应数据库ACID属性中的 “I”，即isolation 数据库的隔离性
  2. 线性一致性对应分布式系统CAP理论中的“C”，即Cosistency 分布式系统的一致性

可串行化 + 线性一致性 = 数据库的强一致性

  1. 数据库中基于两阶段锁定的一致性保证同时满足 可串行化 和 线性一致性
  2. 可串行化的快照隔离（数据库的弱一致性，不太理解） 无法保证 线性一致性

我的简单理解:

  1. 可串行化就是一个单机系统的概念，单机系统中在执行顺序确定的情况下结果必然是确定的，只有可能在并发条件下才可能出现不一致的问题，可串行化就是说寻求一个顺序使得并发请求结果保持一致。
  2. 线性一致性是分布式系统中的概念，由于不同备份之间存在版本差距，即使是顺序确定的一系列请求（访问了不同服务器上不同版本的副本）也可能出现，后发出请求反而读到了旧值的情况，线性一致性是寻求一个顺序使得分布式系统中具有确定顺序的请求出现结果冲突的问题（在分布式全局逻辑时钟衡量下也可能出现并发情况，此时与串行化一致）

Zookeeper

ZooKeeper is essentially a service) for distributed systems offering a hierarchical key-value store, which is used to provide a distributed configuration service, synchronization service), and naming registry for large distributed systems (see Use cases).[3] ZooKeeper was a sub-project of Hadoop but is now a top-level Apache project in its own right.

ZooKeeper是一个分布式应用程序协调服务(coordination service)，为分布式应用提供配置管理、成员管理以及分布式锁等服务（人如其名），其底层基于Fast Paxos一致性算法，下面通过论文对ZooKeeper原理进行了解和研究。

基本架构

ZooKeeper使用znode作为元数据存储节点，其中znode以类似于unix文件系统的树型组织（如下图），每个znode拥有自己的命名空间

  • znode不存储实际的数据，而是存储协调分布式应用的相关元数据（如配置）或仅仅通过znode实现协调功能（分布式锁）
  • client通过Zookeerper提供的API修改znode元数据或者添加/删除znode 实现分布式协调原语

znode分为以下不同类型：

  1. Regular：普通节点。由client主动创建和删除
  2. Ephemeral：临时节点。同样由client主动创建和删除，但是当创建该节点的client的session结束时，节点自动删除（容错）

另外创建znode时，可显式指定znode带有序列号(sequential flag)

  • 该机制保证新创建的znode的sequential flag在父节点所有儿子节点中最大
  • sequential flag可以方便的实现读写锁、无羊群效应（herd effect）的排他锁

zookeeper提供了znode的watch机制，允许client主动监视znode的状态变更（异步）

  • client 可对指定znode进行watch标记，当该znode状态修改时（删除、修改配置等），zookeeper发送消息提醒client

  • watch配合其他机制可方便实现一系列分布式写作原语（分布式锁）

  • 我认为 watch机制也是ZooKeeper把自己称为 wait free的原因之一

zookeeper将与client的交互定义为session

  • 在session内，当ZooKeeper超过一定时间（session timeout）未收到client的请求，ZooKeeper会主动结束session
  • client也可主动关闭session，否则通过发送heartbeat请求维持session不会timeout

ZooKeeper基本操作

ZooKeeper本身采用主从复制的形式（如下图），实现高可用分布式协调服务，其中ZooKeeper主要包括两种操作

  1. 写请求：接收到请求的follower服务器转发给leader，由leader运行共识算法得到共识后，提交当前写请求，并最终会在所有副本上写入
  2. 读请求：接收到请求的server直接读取本地数据，返回读取结果

不难看出ZooKeeper处理读请求的方法可能会导致client读到stale数据，ZooKeeper设计中接受这种程度一致性，其基本保证为

  1. Linearizable writes(线性一致写)：明显写请求通过共识算法后才提交，能够保证在所有副本上实现写的线性一致性
  2. FIFO client order：所有来自同一个客户端请求保证按照请求发送顺序执行（client视角的线性一致性：即client不会出现先读到新数据，后读到旧数据的情况，每次读都保证至少和上次读取新旧程度相同的数据）

由性质2可以得到，ZooKeeper的设计目标并没有读写线性一致性，仅仅保证单客户端的线性一致性，然而在处理读请求时仅仅时简单的读取本地数据无法保证性质二

  • 例如：client从一个最新的server上读取数据，该服务器宕机，client被分配到另一个数据不是最新的server,此时新的读请求会读到stale数据
  • 针对此Zookeeper为处理的每个请求打上当前服务器已提交的写请求的zxid(zxid用来标记写请求的顺序),当client与新server建立session时，server会在确认自己至少拥有client的zxid相同新鲜程度数据的情况下，才与client建立session，否则等待直到数据更新到至少相同新鲜程度（as recent as the client）
  • 由于共识算法的作用，大多数server必定带有最新更新，这就保证了client最终一定会找到可以建立连接的server

Atomic Broadcast-Zab

Zab-ZooKeeper Atomic Broadcast，论文中只是引用了一下，这里简单介绍一下原理：

  1. 正常状态下与fast paxios区别不大，leader收到一个事务（transaction）,为事务带上序列号和当前leader的epoch号（ 64位zxid,32epoch,32序列号），之后发送到所有的follower,多数通过即提交
  2. leader和follower通过heartbeat信息交互，当一方超过一定时间未收到另一方的heartbeat，即认为另一方失效，当follower认为leader失效时，其进入错误恢复阶段
  3. 恢复模式（选主）：和raft类似，follower向其他follower发送选举请求，投票超过半数，成为新的leader（类似于gossip，follower之间不断pk，直到出现一个过半选票）
  4. 同步阶段：leader将最新zxid发送给follower,follower根据zxid与leader保持状态同步

zab基于TCP实现leader到follower请求的fifo管道

snapshot

ZooKeeper使用一种 fuzzy snapshot的方式进行系统快照

  1. 在进行快照的过程中，服务器继续响应请求
  2. 得到的快照可能处于中间状态，所以叫fuzzy snapshot

在启用快照时为了避免fuzzy snapshot导致的状态不正确问题，ZooKeeper通过Zab重传操作（ Zookeeper状态变更是幂等，所以即使重复执行也保证状态正常变更），保证最终状态与系统崩溃前一致

Client API

ZooKeeper为Client提供了操作znode基本API，类似于文件系统的增删改查操作，每个操作均包括同步和非同步版本

  1. create(path, data, flags)：创建znode，其中flag用来指定znode类型：rugular,ephemeral,sequential
  2. delete(path, version)：删除znode
  3. exists(path, watch): 判断znode是否存在
  4. getData(path, watch): 获得znode中存储的元数据
  5. setData(path, data, version)：修改znode中元数据
  6. getChildren(path, watch)： 获得当前路径的所有子znode
  7. sync(path)：主动同步命令（path无关）

通过以上API，Client可以方便的实现多种分布不是协调原语

  1. 分布式互斥锁：基本原理是通过一个znode或者多个同父节点的znode实现锁

  2. Double Barrier：我理解的是双重同步，实现多个进程的同步。基于特定路径子znode的增删。

  3. 配置管理/成员管理：znode代表逻辑上的节点，通过znode修改删除等实现管理功能

实际应用

ZooKeeper已经成功的应用于分布式用服务，论文中举了几个例子

  1. The Fetching Service：Yahoo的搜索引擎通过该服务实现数十亿级的网页爬取，该服务器有master和fecher组成，其中master管理fetcher的配置信息，fetcher进行网页的爬取并向master汇报自身状态信息。
    • 使用ZooKeeper目标：master容错，master配置职责解耦
    • 用到的原语：配置管理、主节点选举
  2. Katta：分布式索引器，Katta将检索过程分布在不同的服务器上
    • 使用ZooKeeper目标：master容错，master配置职责解耦，成员容错
    • 用到的原语：配置管理、主节点选举、成员管理

总结

ZooKeeper通过特殊的文件系统+zab算法实现了一个可定制化的分布式协作服务，在我看来ZooKeeper最大的优点在于屏蔽了底层共识算法的复杂细节，为分布式协作提供了简单、通用而又高度可定制化的实现接口。