做网站多少钱大概,邯郸网站建设xy0310,江门网站推广深圳公司,泌阳县住房和城乡建设局网站转载#xff1a;http://developer.51cto.com/art/201805/574334.htm
Zookeeper 是最终一致性的#xff0c;由于多副本#xff0c;以及保证大多数成功的 Zab 协议#xff0c;当一个客户端进程写入一个新值#xff0c;另一个客户端进程不能保证马上就会读到#xff0c;但能…转载http://developer.51cto.com/art/201805/574334.htm
Zookeeper 是最终一致性的由于多副本以及保证大多数成功的 Zab 协议当一个客户端进程写入一个新值另一个客户端进程不能保证马上就会读到但能保证最终会读到这个值。
Zookeeper 的 Zab 协议类似于 Paxos 协议并且提供了强一致性。
每当听到这两种说法我都想纠正一下。Zookeeper 是顺序一致性Sequential Consistency的但解释起来比较复杂下面和大家一起讨论下我的看法。
什么是 Sequetial Consistency
从 Zookeeper 的文档中我们可以看到里面明确写出它的一致性是 Sequential Consistency。
那么什么是 Sequential Consistency 呢
Sequential Consistency 是 Lamport 在 1979 年首次提出的。论文中定义当满足下面这个条件时就是 Sequential Consistency
the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.
这段英文定义很晦涩这是 Lamport 大神的一贯风格严谨但晦涩Paxos 协议也是如此。
我第一次看到时的感觉是“这是什么鬼”为啥每个英文单词我都认识但就是不知道他在说什么
我们先看看这篇论文的标题和定义中出现的一个关键词来说明一下 Sequential Consistency 的应用范围。
论文的标题和定义中包含“multiprocessor”这个词multiprocessor 是多核处理器的意思。
从这个关键字来看Sequential Consistency 是用来定义多核处理器和跑在多核处理器上的程序的一个特性。
Lamport 这篇论文的标题可以翻译成“如何让具有多核处理器的计算机正确执行多进程程序”。
也就是说如果一个多核处理器具有 Sequential Consistency 的特性这个多核处理器就可以正确运行后面我会解释这个正确运行是什么意思也就是本文后面讲到的 Sequential Consistency 的作用。
从这个标题我们还可以看出Sequential Consistency 应该是个并发编程Concurrent Programming领域的概念。
但我们现在常常在分布式系统领域讨论 Sequential Consistency比如本文主要讨论的 ZookeeperZookeeper 很明显是一个分布式系统的一致性。
实际上多核处理器上运行的多个程序其实也是一种分布式系统Lamport在他的这篇 TimeClocksand the Ordering of Events in a Distributed System 分布式系统的开山之作中也阐述了这个观点。
所以虽然 Sequential Consistency 最早在并发编程中提出但是它可以应用在分布式系统中比如本文讨论的 Zookeeper 这种分布式存储系统。
另外一个比较重要的 Linearizability线性一致性也是在并发编程中最早提出的目前也被广泛应用在分布式系统领域中。
接下来我们尝试翻译一下上文那段晦涩的定义做这段翻译让我找到了上学时做阅读理解的感觉。
我先不直接翻译因为就算我把它翻译成中文估计很多人还是会有“为啥每个中文字我都懂还是不知道在说什么”的感觉。
首先我来解释一下个别的词。首先“any execution”是什么意思你有多个程序Program在多核处理器上运行例如你有两个程序。
第一个程序叫 P1它的代码如下 P1_write(x); P1_read(y);
第二个程序叫 P2代码如下 P2_write(u); P2_read(v);
从理论上来讲两个程序运行在两个独立处理器的核上有多少种执行的可能我列举其中几种来举例说明。
第一种 P1---write(x)--------read(y)-------- P2-----------write(u)-------read(v)-
第二种 P1----------write(x)-read(y)-------- P2--write(u)----------------read(v)-
第三种 P1---read(y)----------write(x)------ P2-----------write(u)---------read(v)-
我们有 24 种可能的执行顺序也就是这四个操作任意的排列组合也就是4!24。
类似第一种和第二种这样的可能性很好理解。为什么会出现像第三种这样的可能的执行呢
那是因为就算在同一个程序中由于处理会有多级的缓存以及处理器中 coherence 的存在虽然你的程序中是先 write 后 read在内存中真正生效的顺序也有可能是先 read 后 write。
其实还会出现类似下面这样的执行两个操作在两个处理器上同时执行。 P1--write(x)-read(y)-------- P2--write(u)--------read(v)-
如果加上同时运行的这种情况那就有更多种可能性。我的算术不太好这里就不继续算下去了因为到底有多少个不重要重要的是要知道有很多种可能性。
那么定义中的“any execution”就是指任意一种可能的执行在定义中也可以理解为所有的这些可能的执行。
接着我们再来解释一个词——“sequential order”。什么叫 sequential order我们来翻一下英语词典感觉更像在做阅读理解了。
sequential连续的相继的有顺序的
order命令顺序规则[贸易] 定单
sequential order——有顺序的顺序这又是什么鬼
其实 sequential 是有一个接一个的意思在处理器的这种上下文中sequential 就是指操作operartion一个接一个地执行也就是顺序执行并且没有重叠。
order 是指经过一定的调整让某样东西按照一定的规则变得有序。比如在算法中的排序算法就是 ordering就是让数组这个东西按照从大到小或从小到大的规则变得有序。
那么 sequential order 就是指让操作operation按照一个接一个这样的规则排列并且没有重叠。
再说回上文的例子如果把四个操作按一个接一个的规则排列这时就可以得到 4的排列组合个可能的排列order同样的有多少个不重要。
比如 P1_write(x);P1_read(y);P2_write(u);P2_read(v); P1_read(y);P1_write(x);P2_write(u);P2:read(v); P2_write(u);P2_read(v);P1_read(y);P1:write(x);
我这里只列举其中三个其他的大家可以自己排一下。
重点来了其实 sequential order 就是让这四个操作按照一个接一个的顺序执行并且没有重叠。
注意这个排列不是真实的执行真实的执行是 any execution这里说的是逻辑上的假设也就是为什么定义有一个 as if。
做了这么多的铺垫下面我们开始翻译定义中的第一句话
任意一种可能的执行效果与所有的处理器上的某一种操作按照顺序排列执行的效果是一样的。
注意some 在这里是指“某一种”的意思不是一些因为 order 是单数真的是在做阅读理解。
这句话的意思就是说一个处理器要满足这个条件就只能允许满足这个条件的那些可能的执行存在其他不满足的可能的执行都不会出现。
从第一句话中我们可以看出一种多核处理器要想满足 Sequential Consistency那么多个程序在多个核运行效果“等同”于在一个核上顺序执行所有操作的效果是差不多的。
如果这样的话其实多核的威力基本就消失了。所以无论是从 Lamport 写这篇论文的 1979 年还是现在没有任何一个现实的多核处理器实现了 Sequential Consistency。
那么为什么 Lamport 大神提出这样一个不现实的概念呢要注意 Lamport 写这篇论文时并没有把它引申到分布式系统领域就是针对多核处理器、并发编程领域提出的我们稍后再论述。
这里还要注意的一点是在我的翻译里用了“效果”一词但实际上英文原文中用的是“result结果”一词。那效果和结果有什么区别吗我们解释一下什么叫执行结果。
不管是任何真实的执行还是某种经过顺序排序后的假设执行程序会产生一定的结果比如 print 出来的结果result。实际上定义中说的是结果一样。
如果定义中用“效果”的话那这个定义就只是一个定性的定义如果用“结果”的话那这个定义就是一个定量的定义。定量的也就是说可以通过数学证明的。
从这点我们可以看出大神就是不一样任何理论都是可以通过数学证明为正确的。本文后面还会提到证明的事情我们这里再卖个关子。
到这里关于定义的第一句更准确的翻译就是
任意一种可能的执行的结果与某一种所有的处理器上的操作按照顺序排列执行的结果是一样的。
这里我们还要注意一点结果一样就意味着如果有人真的要实现一种 Sequential Consistency 的多核处理器的话因为要保证结果一样所以他是有一定的空间来优化而不会完全是一个按顺序执行的效果。
但是估计这种优化也是非常有限的。好了终于把最难的第一句话解释完了大家可以松口气第二句就非常简单了。
我们还是先解释第二句中出现的一个词——“sequence”。刚刚解释过的 sequential order 是顺序排序就是按一个接一个排序。
其实这是一个动作动作会产生结果它的结果产生了一个操作operation的队列。第二句中出现的 sequence 就是指这个操作operation的队列。
好那第二句的翻译就是
并且每个独立的处理器的操作都会按照程序指定的顺序出现在操作队列中。
也就是说如果程序里是先write(x)后read(y)那么只有满足这个顺序的操作队列是符合条件的。
这样我们刚刚说的很多可能的执行就少了很多这里我也就不计算少了多少还是那句话数量不重要反正是有而且变少了。
那么第二句话意味着什么意味着如果一个多核处理器实现了 Sequential Consistency那这种多核处理器基本上就告别自缓行存车了。
这里我还要继续卖关子连缓存这种最有效提高处理器性能的优化都没了大神为什么要提出这个概念
好了到这里我们可以把两句翻译合起来完整看一下
任意一种可能的执行的结果与某一种所有的处理器上的操作按照顺序排列执行的结果是一样的并且每个独立的处理器的操作都会按照程序指定的顺序出现在操作队列中。
从这个定义中我们可以看出此概念的核心就是 sequential order这也就是为什么 Lamport 老爷子把这种一致性模型称之为 Sequential Consistency。
可以说这个命名是非常贴切的不知道这种贴切对于以英语为母语的人来说是不是更好理解一些应该不会出现“顺序的顺序是什么鬼”这种情况。如果你看完本文也觉得 sequential 很贴切的话那就说明我讲清楚了。
接下来我们举个具体的例子再来说明一下 execution A P0 writex1------------------------------- P1 -------write x2---------------------- P2 -----------------read x1--read x2 P3 -----------------read x1--read x2 sequetial order: P0_write x1,P3_read x1,P4_read x1,P1_write x2,P3_read x2,P4_read x2 execution B P0 write1------------------------------- P1 -------write x2---------------------- P2 -----------------read x2--read x1 P3 -----------------read x2--read x1 sequetial order: P1_write x2,P3_read x2,P4_read x2,P0_write x1,P3_read x1,P4_read x1 execution C P0 write1------------------------------- P1 -------write x2---------------------- P2 -----------------read x1--read x2 P3 -----------------read x2--read x1 sequetial order: 你找不出一个符合定义中2个条件的一种order。
sequetial order: 你找不出一个符合定义中2个条件的一种order。
所以说如果一个多核处理器只允许 execution A 和 B 出现不允许 C 出现那么这个多核处理器就是 Sequetial Consistency 的如果它允许 C 出现那它就不是 Sequetial Consistency。
到这里我们已经完整地解释完什么是 Sequetial Consistency。但是细心的朋友可能会问如果你的 program 是多线程的程序怎么办那我们再把定义中最后的一个细节解释一下program 这个词。
program 是指可以直接运行在处理器上的指令序列。这个并不是 program 的严格定义但是我要指出的是这个 program 是在操作系统都没有的远古时代就存在的概念在上文的定义中 prgram 就是指那个时代的 program。
这个 program 里没有进程、线程的概念这些概念都是在有了操作系统之后才出现的。因为没有操作系统也没有内存空间的概念。
不像我们现在所说的程序program不同的程序有自己独立的内存地址空间。我们这里内存memory对于不同的 program 来说是 shared。
另外需要注意的是 program 可以用来说明各种程序不管你是操作系统内核还是应用程序都适用。
Sequential Consistency 是分布式领域的概念
刚刚我们说了Sequential Consistency 虽然是针对并发编程领域提出的但实际上它是分布式领域的概念特别是分布式存储系统。
在 Distributed systemPrinciples and Paradigms 作者Andrew S.Tanenbaum, Maarten Van Steen作者稍微修改了一下 Lamport 的定义让这个定义更贴近分布式领域中的概念。
我们来看一下作者是怎么改的
The result of any execution is the same as if the (read and write) operations by all processes on the data store were executed in some sequential order and the operations of-each individual process appear in this sequence in the order specified by its program.
作者把 processor 换成了 process并且加了 on the data store 这个限定在 Lamport 的定义里没有这个限定其实默认指的是 memory内存。
process 就是指进程以 Zookeeper 为例就是指访问 Zookeeper 的应用进程。program 也不是那么底层的概念也是基于操作系统的应用程序了。
Sequential Consistency 的作用
好了下面该揭晓我上面卖的两个关子了。在 Lamport 的论文中给出了一个小例子如下 process 1 a : 1; if b 0 then critical section: a : 0 else ... fi process 2 b : 1; if a 0 then critical section: b : 0 else ... fi
Lamport 在论文中说如果一种多核处理满足 Sequential Consistency 的条件那么最多只有一个程序能够进入 critical section。
在论文中Lamport 老爷子并没有解释为什么最多只有一个程序能够进入 critical section。
而是把这个证明留给了论文的读者就像我们常见的教科书中的课后习题一样。
Lamport 老爷子应该是认为这个证明太简单了不需要花费笔墨来证明它。Sequential Consistency 这篇论文只有不到两页 A4 纸是我见过的最短的论文。
这是 Lamport 一贯的做事风格他的 Paxos 论文中有很多细节都是一笔带过的给读者留下无尽的遐想瞎想。
假设现在我们已经证明这个是正确的虽然我也没去证明论文给出了两个参考文献用于证明那这个例子说明了什么呢
大家也许注意到了这个例子没有用到任何锁但它实现了 critical sectioncritical section 是一种多线程 synchronization 机制。
如果多核处理器是 Sequential Consistency 的那么你写的并发程序“天然就是正确的”。
但是处理器的设计者为了追求性能将保证程序正确的任务丢给程序开发者。
只在硬件级别提供了一些 fence、cas 等指令基于这些指令操作内核和语言基础库实现了各种 synchronization 机制用来保证操作系统的正确性和应用程序的正确性。
程序员必须小心谨慎地使用线程和这些 synchronization 机制否则就会出各种意想不到的问题。如果你没有 debug 一个多线程 Bug 连续加班两天那说明你是大神。
这些指令都是具有更高一致性级别也就是 linearizability虽然一致性级别高但只是个别指令的处理器整体只是实现了比 Sequential Consistency 低很多的一致性级别。所以实现难度大大降低了。
虽然 Lamport 老爷子的 Sequential Consistency 概念在 Concurrent Programming 领域中还没有实际意义但却给我们指出了程序员的天堂在哪里。
在程序员的天堂里没有多车线来程车编往程只要写程序就行。你面试的时候不会再有人问你多线程编程不会再问你各种锁。
在分布式领域中Sequential Consistency 更实际一些。Zookeeper 就实现了 Sequential Consistency。
同理这应该也是可以证明的但目前还没发现有 Zookeeper 社区有任何论文来证明这个。
如果你已经明白上面解释的定义就可以想清楚 Zookeeper 是 Sequential Consistency欢迎大家一起来探讨。
为何 Zookeeper 要实现 Sequential Consistency
实际上Zookeeper 的一致性更复杂一些Zookeeper 的读操作是 Sequential Consistency 的Zookeeper 的写操作是 linearizability 的。
关于这个说法Zookeeper 的官方文档中没有写出来但在社区的邮件组有详细的讨论。
另外在 Modular Composition of Coordination Services 这篇关于 Zookeeper 的论文中也有提到这个观点这篇论文不是 Zookeeper 的主流论文但全面分析了 Zookeeper 的特性以及 Zookeeper 跨机房方案饿了么的 Zookeeper 异地多活改造也参考了这篇论文中的一些观点。
我们可以这么理解 Zookeeper从整体read 操作write 操作上来说是 Sequential Consistency写操作实现了 linearizability。
通过简单的推理我们可以得出 Lamport 论文中的小例子在 Zookeeper 中也是成立的。我们可以这样实现分布式锁。
但 Zookeeper 官方推荐的分布式实现方法并没有采用这个方式而是利用了 Zookeeper 的 linearizability 特性实现了分布式锁。
为什么 Zookeeper 要实现 Sequential ConsistencyZookeeper 最核心的功能是用来做 coordination service也就是用来做分布式锁服务在分布式的环境下Zookeeper 本身怎么做到“天然正确”
没有其他的 synchronization 机制保证 Zookeeper 是正确的所以只要 Zookeeper 实现了 Sequential Consistency那它自身就可以保证正确性从而对外提供锁服务。
