文档章节

Zab vs. Paxos

guhanjie
 guhanjie
发布于 2017/04/20 11:00
字数 2275
阅读 356
收藏 1

首先,本文基于阅读该篇文章https://cwiki.apache.org/confluence/display/ZOOKEEPER/Zab+vs.+Paxos而产生的自我理解,不正之处请读者指正。

文章不长,我将其摘录如下:

Is Zab just a special implementation of Paxos?

No, Zab is a different protocol than Paxos, although it shares with it some key aspects, as for example:

  • A leader proposes values to the followers
  • Leaders wait for acknowledgements from a quorum of followers before considering a proposal committed (learned)
  • Proposals include epoch numbers, which are similar to ballot numbers in Paxos

The main conceptual difference between Zab and Paxos is that it is primarily designed for primary-backup systems, like Zookeeper, rather than for state machine replication.

What is the difference between primary-backup and state machine replication?

A state machine is a software component that processes a sequence of requests. For every processed request, it can modify its internal state and produce a reply. A state machine is deterministic in the sense that, given two runs where it receives the same sequence of requests, it always makes the same internal state transitions and produces the same replies.

A state machine replication system is a client-sever system ensuring that each state machine replica executes the same sequence of client requests, even if these requests are submitted concurrently by clients and received in different orders by the replicas. Replicas agree on the execution order of client requests using a consensus algorithm like Paxos. Client requests that are sent concurrently and overlap in time can be executed in any order. If a leader fails, a new leader that executes recovery is free to arbitrarily reorder any uncommitted request since it is not yet completed.

In the case of primary-backup systems, such as Zookeeper, replicas agree on the application order of incremental (delta) state updates, which are generated by a primary replica and sent to its followers. Unlike client requests, state updates must be applied in the exact original generation order of the primary, starting from the original initial state of the primary. If a primary fails, a new primary that executes recovery cannot arbitrarily reorder uncommitted state updates, or apply them starting from a different initial state.

In conclusion, agreement on state updates (for primary-backup systems) requires stricter ordering guarantees than agreement on client requests (for state machine replication systems).

What are the implications for agreement algorithms?

Paxos can be used for primary-backup replication by letting the primary be the leader. The problem with Paxos is that, if a primary concurrently proposes multiple state updates and fails, the new primary may apply uncommitted updates in an incorrect order. An example is presented in our DSN 2011 paper (Figure 1). In the example, a replica should only apply the state update B after applying A. The example shows that, using Paxos, a new primary and its follows may apply B after C, reaching an incorrect state that has not been reached by any of the previous primaries.

A workaround to this problem using Paxos is to sequentially agree on state updates: a primary proposes a state update only after it commits all previous state updates. Since there is at most one uncommitted update at a time, a new primary cannot incorrectly reorder updates. This approach, however, results in poor performance.

Zab does not need this workaround. Zab replicas can concurrently agree on the order of multiple state updates without harming correctness. This is achieved by adding one more synchronization phase during recovery compared to Paxos, and by using a different numbering of instances based on zxids.

 

然后,来谈谈自己的理解

Zab是分布式数据主备系统的实现算法,Paxos是分布式一致性状态机的实现算法。

一直以来,都想给Paxos定一个清晰的问题域,现在有了:

为了保证我们的系统服务的高可用性,我们提出了分布式系统,通过主-备的部署架构来实现当前主服务节点挂掉后,备服务节点马上提供服务。

然而,某些服务是具有数据/状态依赖的(如数据库、状态机),为了保证上层客户看到的数据一致性,我们需要保证主备服务节点的数据一致,由此,提出了“分布式一致性”这个概念。

那么,如何才能保证主备节点上数据/状态的一致呢?

我们想到了有限状态机:它是一个负责接收和处理一序列请求的服务组件,在分布式的多个节点上,每个状态机从一个相同的初始状态出发,执行相同的指令序列,最终各个节点上的输出状态是一致的。

我们利用有限状态机部署在主备系统上,来实现数据/状态的一致性。

为此,我们需要保证每个节点的状态机上每次的执行指令都是一致的。

我们可以把每一条执行指令看作是一个议案,在一个网络通信不可靠(消息可能丢失、延迟、重发),节点可能崩溃的分布式环境中,如何能够确保一个议案被整个环境中的节点唯一(表示一个议案最终只有一个结果chosen)且一致(表示大家共同决定且公认的,所有人最终都可以知道这个议案的结果)地确定?由此,提出了“分布式一致性算法Paxos”。

分布式系统中有限状态机上的每一条执行指令的确定都是一次Paxos过程,我们称这个行为为一个“Paxos instance”(Paxos实例)。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Paxos算法具体如何实现,参见Paxos论文及相关

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

有了有限状态机,有了Paxos算法保证每条执行指令都是一致的,仍然存在一个问题:指令执行的顺序问题。

commit sequence is not the same as submit sequence,即客户端提交命令(submit)的顺序与状态机服务执行命令(commit)的顺序可能存在不一致。比如客户端可能并发提交命令,而网络请求也可能乱序到达服务端,主节点可能崩溃,后升为主的节点并不知道之前的指令序列。

有限状态机它只保证以一个初始状态出发,执行相同的指令序列,最终输出状态是一致的。但是,它并不保证客户端提交命令的顺序序列。

具体示例:

初始状态为0,客户端提交指令序列如:+1,*2,每个状态机都执行相同的指令序列,但是指令执行顺序不同,得出的结果就不一样,对于上层客户而言,数据/状态就损坏了。

比如上面:若执行顺序按照客户端提交序列,应该是0+1==>1,1*2==>2,最终客户想看到2的输出,但是如果执行顺序反了,就变成0*2==>0,0+1==>1,最终结果是1,虽然状态机能够保证每个节点上结果都是1,但是对客户而言,这个结果是错误的。

那么,如何解决呢?

存在这么一种解决方案:某一指令必须在它之前所有指令执行(commit)之后才能提交(submit/propose),这样即使服务中节点易主,因为当前只有一条指令待执行,因此不存在多条指令执行的顺序问题。

但是,这么做极大地降低了系统执行吞吐量和性能。

因此有了下面的这个解决方案:

Zookeeper是一个分布式数据/状态主备系统,它提出了一个Zab(Zookeeper Atomic Broadcast)算法,来解决上面的问题。

核心的实现技术如下:

利用递增的zxid来保证客户端提交到ZK服务上的指令顺序(zxid充当了时间维度上的唯一性指标),zxid在Leader节点上创建生成并返回给客户端(此为客户端提交命令到ZK服务上的顺序凭证,也就是可能现实中C1先发送的命令,但是由于网络延迟等原因,最终C2的命令先到达了ZK服务端,那么C2提交的命令在前,zxid较小,也就是说客户端提交命令的顺序是以服务端Leader接收到请求的顺序为定),正常情况下Leader节点在整个集群中只有一个,因此,通过这种方式可以统一客户端提交命令的顺序(submit sequence),后续所有状态机上的执行都需要严格按照这个zxid递增顺序执行,这样就保证了指令执行的顺序问题。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

现在,状态机、Paxos保证单个指令一致、Zab原子广播保证多个指令执行的顺序,最后还剩下一个问题,就是如何“同步”。

主备节点对相同指令序列执行是有延迟的,虽然上面的元素保证了最终各个节点数据/状态的一致,但是某个时刻可能存在多个节点上数据/状态并没有达到一致,因此还需要一个同步的过程,在主-备节点上进行点对点心跳检测保持通信,并在向客户端提供数据/状态之前,在主备之间实施一个同步过程。

 

© 著作权归作者所有

guhanjie
粉丝 5
博文 3
码字总数 5114
作品 0
上海
程序员
私信 提问
zookeeper 入门系列 – 理论基础 – zab 协议

原文出处:笨狐狸 上一章讨论了paxos算法,把paxos推到一个很高的位置。但是,paxos有没有什么问题呢?实际上,paxos还是有其自身的缺点的: 1. 活锁问题。在base-paxos算法中,不存在leade...

笨狐狸
2018/03/31
0
0
ZAB协议和Paxos算法

前言 在上一篇文章Paxos算法浅析中主要介绍了Paxos一致性算法应用的场景,以及对协议本身的介绍;Google Chubby是一个分布式锁服务,其底层一致性实现就是以Paxos算法为基础的;但这篇文件并...

ksfzhaohui
2016/12/27
4.8K
1
一致性协议浅析:从逻辑时钟到Raft

前言 春节在家闲着没事看了几篇论文,把一致性协议的几篇论文都过了一遍。在看这些论文之前,我一直有一些疑惑,比如同样是有Leader和两阶段提交,Zookeeper的ZAB协议和Raft有什么不同,Pax...

正研
02/18
0
0
Zookeeper概念学习系列之zab协议

但是,paxos有没有什么问题呢?实际上,paxos还是有其自身的缺点的。   1. 活锁问题。在base-paxos算法中,不存在leader这样的角色,于是存在这样一种情况,即P1提交了一个proposal n1并且...

技术小哥哥
2017/01/29
0
0
Zookeeper的一致性协议:Zab

Zookeeper使用了一种称为Zab(Zookeeper Atomic Broadcast)的协议作为其一致性复制的核心,据其作者说这是一种新发算法,其特点是充分考虑了Yahoo的具体情况:高吞吐量、低延迟、健壮、简单...

小报童
2013/01/06
523
0

没有更多内容

加载失败,请刷新页面

加载更多

java通过ServerSocket与Socket实现通信

首先说一下ServerSocket与Socket. 1.ServerSocket ServerSocket是用来监听客户端Socket连接的类,如果没有连接会一直处于等待状态. ServetSocket有三个构造方法: (1) ServerSocket(int port);...

Blueeeeeee
今天
6
0
用 Sphinx 搭建博客时,如何自定义插件?

之前有不少同学看过我的个人博客(http://python-online.cn),也根据我写的教程完成了自己个人站点的搭建。 点此:使用 Python 30分钟 教你快速搭建一个博客 为防有的同学不清楚 Sphinx ,这...

王炳明
昨天
5
0
黑客之道-40本书籍助你快速入门黑客技术免费下载

场景 黑客是一个中文词语,皆源自英文hacker,随着灰鸽子的出现,灰鸽子成为了很多假借黑客名义控制他人电脑的黑客技术,于是出现了“骇客”与"黑客"分家。2012年电影频道节目中心出品的电影...

badaoliumang
昨天
15
0
很遗憾,没有一篇文章能讲清楚线程的生命周期!

(手机横屏看源码更方便) 注:java源码分析部分如无特殊说明均基于 java8 版本。 简介 大家都知道线程是有生命周期,但是彤哥可以认真负责地告诉你网上几乎没有一篇文章讲得是完全正确的。 ...

彤哥读源码
昨天
17
0
jquery--DOM操作基础

本文转载于:专业的前端网站➭jquery--DOM操作基础 元素的访问 元素属性操作 获取:attr(name);$("#my").attr("src"); 设置:attr(name,value);$("#myImg").attr("src","images/1.jpg"); ......

前端老手
昨天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部