本文由giantpoplar发表于CSDN，转载请保留本声明。
 
 
“Cache Coherence” V.S. “Memory Consistency” V.S. “Data Consistency”
 
缓存一致性
 
cache coherence 的coherence这个词猜测是体系结构圈为了和memory consistency做区分，用了coherence这个词，但我理解缓存一致性和分布式多副本数据的一致性基本接近，只不过cache coherence是一种同步可靠通信、有全局时钟条件下的强一致(linearizability)。cache一致性协议有MSI，MESI等，虽然处理器的整个内存系统很复杂，但就cache一致性协议来说，比分布式环境下的数据一致要简明一些
 
多核处理器每个核会有私有cache，也就是内存里的一份数据在多个核上可能有了副本，这多个副本，每个核都可能会对一个内存地址有读写操作，每个核是直接读写自己私有的副本，这就要求各个副本上的读写操作顺序要一致，这和分布式环境下的数据一致性很接近。
 
具体的MSI，MESI协议暂不展开写。
 
内存一致性
 
内存一致性说的是共享内存多核处理器访存序的问题，进程对某一个内存地址(和分布式的同一数据多副本的一致性有所区别)的访问序的在多核下暴露出的问题 全部内存读写顺序的正确性问题，单核乱序执行重新排列无关的指令在多核系统中可能出现问题。也就是程序中 Load Store 的(ISA)顺序(冯诺依曼架构下看可以看做内存操作请求的顺序)和Load Store实际执行完成的顺序可能相同、可能不同(这取决于微体系结构的实现)，在多核情况下，程序的正确性可能出问题。有各种一致性模型来表达各种程度的相同不同，相应的有软、硬件机制来确保多核处理器上程序的正确运行。
 
这里只具体写顺序一致性(sequential consistency)模型，更弱的一致性模型在学习过相关资料论文后再做补充。顺序一致性的概念来源于Lamport 1977年的一篇论文How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Program 
 这里写一下论文中给出的阐述 
 看一个互斥协议，问题是多核处理器下多进程并发/并行会使得两个进程都进入临界区么？
 
几点说明写在前面：
 
1，2，3，4，5，6只是标号，数字本身带有的序和问题没联系 
程序里的读写操作都是一条指令的粒度，不是高级语言的一句语句 
P1, P2指处理器
 
-
P1
-
P2
a=0
b=0
…
…
1
a=1
4
b=1
2
IF(b==0) THEN
5
IF(a==0) THEN
(临界区)
(临界区)
3
a=0
6
b=0
ELSE
ELSE
{…}
{…}
 
考虑这个例子，如下事件依次发生
 
1 P1 发出a=1的请求，请求的是内存模块1，内存模块1此时正忙
2 P1 发出取b的请求，请求的是内存模块2，内存模块2此时可用，取b的指令执行
4 P2 发出b=1的请求，请求的是内存模块2，这个请求会在取b执行完成后执行
5 P2 发送取a得请求，请求的是内存模块1，内存模块1此时正忙
 
在这个例子里，这4条指令对同一内存请求顺序是1 ->5 ; 2->4 
 这4条指令执行完成的顺序是什么呢 2->4； 
 如果是 2->4；5 -> 1 这两个处理器会同时进入临界区 
 如果是 2->4；1 -> 5 则不会 
 -> 符号不直接对应happen-before
 
顺序一致性有两个条件：
 
每个处理器按程序序发射内存请求(1->2;4->5)
所有处理器到单个存储器模块的请求依照FIFO序服务。请求的发射过程包含进入FIFO队列。
 
我理解就是说，不管这多个处理器对同一内存的请求顺序如何交叠，都可以，但是内存必须按照请求到达的顺序执行（这里应该隐含着对同一地址先请求（指令发射）的先到达（指令执行）的假设），这样保证上面的互斥协议正确。这样的要求称为顺序一致的要求，是很严格的，会对硬件性能造成影响，其实可以放宽，不必严格按请求顺序执行，但是必须有软件机制来提供正确的互斥协议的实现，上面的护持互斥协议在弱于顺序一致的内存模型下是不正确的。
 
也就是说1，2，4，5的请求可以有C(4,2)=6种交叠方式，每一种都符合顺序一致只要每种情况的执行也是按照这个顺序
 
现在来看这句很拗口的话
 
 
 
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
 
 
似乎这个定义里要求每个核上不同内存地址的请求也要安程序序执行，但是在微体系结构层次，提交时要保持，但是执行时程序序是可以打破的，同一处理器不同地址请求序(乱序发射)和程序序(冯诺依曼ISA序)是否一致，请求序和执行序是否一致，这里似乎没有明说。分布式环境中的一致性是关于同一数据的多个副本上要达成全局一致性，某种角度来讲，如果把内存的请求发射和到达，类比分布式中对一个副本的写/读和向各个副本传播写/读操作，这两者非常类似 //但是感觉还是没有理解二者的本质
 
单核处理器下多进程并发会使得两个进程都进入临界区么？此时表里的P1,P2代指进程。不会有这个问题，内存请求是从同一个核过来，到达顺序和服务顺序一样(单核天然是顺序一致的)，不会有多核中多个请求到达，在执行请求时会涉及调度导致服务顺序和到达顺序不一致的情况。
 
如果你考虑一个多核处理器的内存体系，就会发现这个问题很复杂，cache以及一致性，buffer，pipeline和内存一致性的保证，和分布式的一致性相比，虽然分布式下异步不可靠网络带来了很大挑战，但是现在我觉得处理器的内存系统可以说比分布式环境下的一致性问题更加复杂
 
x86的内存一致模型是顺序一致的TSO，所以在实现一个正确的互斥锁的时候也没有考虑太多，比如没用memory barrier这种东西就对了
 
数据一致性
 
分布式系统为了性能、容错的需要，数据进行多副本冗余是一项很基本的技术。数据一致性说的是一份数据有多个副本，在多个副本上的读写操作的顺序要达成一致，这个一致也有很多不同的强弱要求，产生了众多的强弱一致性模型，这些模型的术语和内存一致性的术语有很大的重叠，可能是历史上并行体系结构和分布式系统两个领域是一伙人在搞？
 
由强到弱的数据一致性模型构成了 数据一致性谱
 
线性一致性和顺序一致性
 
这两种都是称为强一致性
 
线性一致性和顺序一致性都是强一致性
都给客户端提供单副本的假象
Linearizability关乎时间，sequential consistency 关乎程序顺序
 
分布式下强一致是个困难问题，著名的paxos算法挺复杂的，Raft是2014年出的一个可以看作是改良版的算法。
 
线性一致性 Linearizability
 
表现出单副本的行为
读操作返回最近(most recent)的写，和client无关
所有后序读返回相同值，直到下一次写，和client无关
 
最近和所有后序： 由时间确定 
 e.g. 
  
  
 
 
顺序一致性
 
表现出单副本的行为
读操作返回最近(most recent)的写，和client无关
所有后序读返回相同值，直到下一次写，和client无关
 
最近和所有后序： 
 同一个client的操作由时间决定(程序序)； 
 跨client的操作：不由时间决定，我们可以安排某种序，只要保持程序序。
 
从系统外的观察者来看：顺序一致性需要提供操作的全局序，1)工作起来像一个副本，2）来自同一个client的操作顺序被保持
 
e.g.
 
不违背顺序一致
 
-
-
-
-
-
-
P1:
W(x)a
P2:
W(x)b
P3:
R(x)b
R(x)a
P4:
R(x)b
R(x)a
 
这个例子里面，横轴代表时间，时间上虽然W(x)a在前，W(x)b在后，但是其序不一定也如此，所以这个例子并不违背分布式环境下的顺序一致，也再次说明分布式的顺序一致是比内存的顺序一致更弱的一致
 
违背顺序一致
 
-
-
-
-
-
-
P1:
W(x)a
P2:
W(x)b
P3:
R(x)b
R(x)a
P4:
R(x)a
R(x)b
 
不违背顺序一致，违背线性一致
 
-
-
-
-
P1:
W(x)a
W(x)b
P2:
R(x)a
time
——->
——->
——->
 
内存的顺序一致是顺序一致么？
 
内存的顺序一致性和分布式哪一种强一致性是一样的呢？是顺序一致性么？因为分布式环境下没有全局时间，所以分布式数据顺序一致性退化成较弱的一种一致性，而Linearizability和内存的顺序一致性更接近。
 
因果一致性 
 放宽顺序一致性的要求，有因果关联的操作保持顺序，并发的(相互没有因果关联的)写操作可能在不同机器上顺序不同 
 因果关系可以由vector-clock捕捉 
 e.g.
 
违背顺序一致,不违背因果一致
 
-
-
-
-
-
-
-
P1:
W(x)a
W(x)c
P2:
R(x)a
W(x)b
P3:
R(x)a
R(x)c
R(x)b
P4:
R(x)a
R(x)b
R(x)c
 
违背因果一致
 
-
-
-
-
-
-
P1:
W(x)a
P2:
R(x)a
W(x)b
P3:
R(x)b
R(x)a
P4:
R(x)a
R(x)b
 
不违背因果一致
 
-
-
-
-
-
-
P1:
W(x)a
P2:
W(x)b
P3:
R(x)b
R(x)a
P4:
R(x)a
R(x)b
 
最终一致性 
 某些副本的数据已经修改，而另一些副本的数据还没来得及修改。当修改可靠地传播到所有副本，并给予足够的时间，所有副本的数据都将变成新值，取得一致。
 
happen-before
 
理解一致性要理解一个并发系统中的“序”的问题，什么叫先，什么叫后。在分布式系统中，这个问题困难是因为没有完美的全局同步时钟，多核系统中是因为多核的微体系结构上的原因。
 
Lamport在1978年的论文中给出了happen-before的定义，这篇论文非常经典，提出了很多分布式系统中十分重要的概念，此处暂不展开，只谈happen-before。据说这篇文章受相对论启发，了解happen-before有助于理解时间、顺序。
 
happen-before 关系
 
基本假设
 
假设进程的事件(event)形成一个序列(sequence)，单个进程定义为 一组事件的全序(total ordering)
假设进程之间消息(message)的发送(send)和接受(receive)是事件
 
happen-before $\rightarrow$ 是满足以下条件的最小关系(relation)
 
如果a，b是同一个进程的事件，a在b前面 ,那么$a\rightarrow b$
如果a是发送消息进程的发送事件，b是接收该消息进程的接受事件，那么$a\rightarrow b$
如果$a\rightarrow b, b\rightarrow c$，那么$a\rightarrow c$
 
定义$a\nrightarrow	a$ 
 另外，如果两个不同的事件a,b,有 $a\nrightarrow	b, b\nrightarrow	a$,就称a,b是并发的(concurrent)
 
这样从数学上看，happen-before就是一个定义在所有事件上偏序关系，反自反，反对称，传递性都有了，偏序关系中存在不可比的情况，所以有些事件并无先后是并发的，如果在加上限制条件 break tie,那么在这个偏序关系上就可以定义一个全序关系。
 
进程和事件的定义非常general，事件可以是一个子程序的执行、也可以是一条机器指令的执行。
 
消息的发送和接受在分布式系统中很显然。在体系结构方面也有类似之处，考虑单核处理器、冯诺依曼架构中指令顺序执行，其实这些指令并不需要严格一条接着一条指令，所以会有乱序执行，在乱序执行里，如果把同一内存地址的写读看做消息发送接收，其实乱序执行的写后读依赖就和happen-before序十分类似。
 
引用
 
[1].Gharachorloo, Kourosh, et al. Memory consistency and event ordering in scalable shared-memory multiprocessors. Vol. 18. No. 2SI. ACM, 1990. 
 [2].Lamport, Leslie. “Time, clocks, and the ordering of events in a distributed system.” Communications of the ACM 21.7 (1978): 558-565. 
 [3]Lamport, Leslie. “How to make a multiprocessor computer that correctly executes multiprocess progranm.” IEEE transactions on computers 9 (1979): 690-691. 
 [4].Tanenbaum, Andrew S., and Maarten Van Steen. Distributed systems: principles and paradigms. Prentice-Hall, 2007. 
 [5].https://homes.cs.washington.edu/~bornholt/post/memory-models.html 
 [6].https://cse.buffalo.edu/~stevko/courses/cse486/spring15/lectures/23-consistency2.pdf

 
欢迎支持笔者新作：《深入理解Kafka:核心设计与实践原理》和《RabbitMQ实战指南》，同时欢迎关注笔者的微信公众号：朱小厮的博客。
 
 
 
什么是数据一致性?
 
  在数据有多分副本的情况下，如果网络、服务器或者软件出现故障，会导致部分副本写入成功，部分副本写入失败。这就造成各个副本之间的数据不一致，数据内容冲突。 实践中，导致数据不一致的情况有很多种，表现样式也多种多样，比如数据更新返回操作失败，事实上数据在存储服务器已经更新成功。
 
 
CAP定理
 
  CAP定理是2000年，由 Eric Brewer 提出来的。Brewer认为在分布式的环境下设计和部署系统时，有3个核心的需求，以一种特殊的关系存在。这里的分布式系统说的是在物理上分布的系统，比如我们常见的web系统。
   这3个核心的需求是：Consistency，Availability和Partition Tolerance，赋予了该理论另外一个名字 － CAP。
   Consistency：一致性，这个和数据库ACID的一致性类似，但这里关注的所有数据节点上的数据一致性和正确性，而数据库的ACID关注的是在在一个事务内，对数据的一些约束。系统在执行过某项操作后仍然处于一致的状态。在分布式系统中，更新操作执行成功后所有的用户都应该读取到最新值。
   Availability：可用性，每一个操作总是能够在一定时间内返回结果。需要注意“一定时间”和“返回结果”。“一定时间”是指，系统结果必须在给定时间内返回。“返回结果”是指系统返回操作成功或失败的结果。
   Partition Tolerance：分区容忍性，是否可以对数据进行分区。这是考虑到性能和可伸缩性。
   CAP定理认为，一个提供数据服务的存储系统无法同事满足数据一致性、数据可用性、分区容忍性。
   为什么不能完全保证这个三点了，个人觉得主要是因为一旦进行分区了，就说明了必须节点之间必须进行通信，涉及到通信，就无法确保在有限的时间内完成指定的行文，如果要求两个操作之间要完整的进行，因为涉及到通信，肯定存在某一个时刻只完成一部分的业务操作，在通信完成的这一段时间内，数据就是不一致性的。如果要求保证一致性，那么就必须在通信完成这一段时间内保护数据，使得任何访问这些数据的操作不可用。
   如果想保证一致性和可用性，那么数据就不能够分区。一个简单的理解就是所有的数据就必须存放在一个数据库里面，不能进行数据库拆分。这个对于大数据量，高并发的互联网应用来说，是不可接受的。
   在大型网站应用中，数据规模总是快速扩张的，因此可伸缩性即分区容忍性必不可少，规模变大以后，机器数量也会变得庞大，这是网络和服务器故障会频繁出现，要想保证应用可用，就必须保证分布式处理系统的高可用性。所以在大型网站中，通常会选择强化分布式存储系统的可用性(A)和伸缩性§，在某种程度上放弃一致性©。一般来说，数据不一致通常出现在系统高并发写操作或者集群状态不稳（故障恢复、集群扩容等）的情况下，应用系统需要对分布式数据处理系统的数据不一致性有所了解并进行某种意义上的补偿和纠错，以避免出现应用系统数据不正确。
 
 
数据一致性模型
 
  一些分布式系统通过复制数据来提高系统的可靠性和容错性，并且将数据的不同的副本存放在不同的机器，由于维护数据副本的一致性代价高，因此许多系统采用弱一致性来提高性能，一些不同的一致性模型也相继被提出。
 
强一致性： 要求无论更新操作实在哪一个副本执行，之后所有的读操作都要能获得最新的数据。
弱一致性：用户读到某一操作对系统特定数据的更新需要一段时间，我们称这段时间为“不一致性窗口”。
最终一致性：是弱一致性的一种特例，保证用户最终能够读取到某操作对系统特定数据的更新。
 
 
数据一致性实现技术
 
Quorum系统NRW策略
 
  这个协议有三个关键字N、R、W。
 
N代表数据所具有的副本数。
R表示完成读操作所需要读取的最小副本数，即一次读操作所需要参与的最小节点数目。
W表示完成写操作所需要写入的最小副本数，即一次写操作所需要参与的最小节点数目。
 
  该策略中，只需要保证R+W>N，就可以保证强一致性。
   例如：N=3，W=2，R=2，那么表示系统中数据有3个不同的副本，当进行写操作时，需要等待至少有2个副本完成了该写操作系统才会返回执行成功的状态，对于读操作，系统有同样的特性。由于R + W > N，因此该系统是可以保证强一致性的。
   R + W> N会产生类似Quorum的效果。该模型中的读（写）延迟由最慢的R(W)副本决定，有时为了获得较高的性能和较小的延迟，R和W的和可能小于N，这时系统不能保证读操作能获取最新的数据。
   如果R + W > N，那么分布式系统就会提供强一致性的保证，因为读取数据的节点和被同步写入的节点是有重叠的。在关系型数据管理系统中，如果N=2，可以设置为W=2，R=1，这是比较强的一致性约束，写操作的性能比较低，因为系统需要2个节点上的数据都完成更新后才将确认结果返回给用户。
   如果R + W ≤ N，这时读取和写入操作是不重叠的，系统只能保证最终一致性，而副本达到一致的时间则依赖于系统异步更新的实现方式，不一致性的时间段也就等于从更新开始到所有的节点都异步完成更新之间的时间。
 R和W的设置直接影响系统的性能、扩展性与一致性。如果W设置为1，则一个副本完成更改就可以返回给用户，然后通过异步的机制更新剩余的N-W的副本；如果R设置为1，只要有一个副本被读取就可以完成读操作，R和W的值如较小会影响一致性，较大则会影响性能，因此对这两个值的设置需要权衡。
 
 
 
下面为不同设置的几种特殊情况:
 1. 当W=1,R=N时，系统对写操作有较高的要求，但读操作会比较慢，若N个节点中有节点发生故障，那么读操作将不能完成。
 2. 当R=1,W=N时，系统对读操作有较高性能、高可用，但写操作性能较低，用于需要大量读操作的系统，若N个节点中有节点发生故障，那么些操作将不能完成。
 3. 当R=Q,W=Q(Q=N/2+1)时，系统在读写性能之间取得平衡，兼顾了性能和可用性。
 
 
两阶段提交算法
 
  在两阶段提交协议中，系统一般包含两类机器（或节点）：一类为协调者（coordinator），通常一个系统中只有一个；另一类为事务参与者（participants，cohorts或workers），一般包含多个，在数据存储系统中可以理解为数据副本的个数。两阶段提交协议由两个阶段组成，在正常的执行下，这两个阶段的执行过程如下所述：
 
阶段1：请求阶段（commit-request phase，或称表决阶段，voting phase）。
 在请求阶段，协调者将通知事务参与者准备提交或取消事务，然后进入表决过程。在表决过程中，参与者将告知协调者自己的决策：同意（事务参与者本地作业执行成功）或取消（本地作业执行故障）。
阶段2：提交阶段（commit phase）。
 在该阶段，协调者将基于第一个阶段的投票结果进行决策：提交或取消。当且仅当所有的参与者同意提交事务协调者才通知所有的参与者提交事务，否则协调者将通知所有的参与者取消事务。参与者在接收到协调者发来的消息后将执行响应的操作。
 
  举个例子：A组织B、C和D三个人去爬长城：如果所有人都同意去爬长城，那么活动将举行；如果有一人不同意去爬长城，那么活动将取消。用2PC算法解决该问题的过程如下：
 
首先A将成为该活动的协调者，B、C和D将成为该活动的参与者。
阶段1：A发邮件给B、C和D，提出下周三去爬山，问是否同意。那么此时A需要等待B、C和D的邮件。B、C和D分别查看自己的日程安排表。B、C发现自己在当日没有活动安排，则发邮件告诉A它们同意下周三去爬长城。由于某种原因，D白天没有查看邮件。那么此时A、B和C均需要等待。到晚上的时候，D发现了A的邮件，然后查看日程安排，发现周三当天已经有别的安排，那么D回复A说活动取消吧。
阶段2：此时A收到了所有活动参与者的邮件，并且A发现D下周三不能去爬山。那么A将发邮件通知B、C和D，下周三爬长城活动取消。此时B、C回复A“太可惜了”，D回复A“不好意思”。至此该事务终止。
 
  两阶段提交算法在分布式系统结合，可实现单用户对文件（对象）多个副本的修改，多副本数据的同步。其结合的原理如下：
 
客户端（协调者）向所有的数据副本的存储主机（参与者）发送：修改具体的文件名、偏移量、数据和长度信息，请求修改数据，该消息是1阶段的请求消息。
存储主机接收到请求后，备份修改前的数据以备回滚，修改文件数据后，向客户端回应修改成功的消息。如果存储主机由于某些原因（磁盘损坏、空间不足等）不能修改数据，回应修改失败的消息。
客户端接收发送出去的每一个消息回应，如果存储主机全部回应都修改成功，向每存储主机发送确认修改的提交消息；如果存在存储主机回应修改失败，或者超时未回应，客户端向所有存储主机发送取消修改的提交消息。该消息是2阶段的提交消息。
存储主机接收到客户端的提交消息，如果是确认修改，则直接回应该提交OK消息；如果是取消修改，则将修改数据还原为修改前，然后回应取消修改OK的消息。
客户端接收全部存储主机的回应，整个操作成功。
 
  在该过程中可能存在通信失败，例如网络中断、主机宕机等诸多的原因，对于未在算法中定义的其它异常，都认为是提交失败，都需要回滚，这是该算法基于确定的通信回复实现的，在参与者的确定回复（无论是回复失败还是回复成功）之上执行逻辑处理，符合确定性的条件当然能够获得确定性的结果哲学原理。
   缺点：单个A是个严重问题：没有热备机制，A节点宕机了或者链接它的网络坏了会阻塞该事务；吞吐量不行，没有充分发动更多A的力量，一旦某个A第一阶段投了赞成票就得在它上面加独占锁，其他事务不得接入，直到当前事务提交or回滚。
 
分布式锁服务
 
  分布式锁是对数据被外界修改持保守态度，在整个数据处理过程中将数据处于锁定状态，在用户修改数据的同时，其它用户不允许修改。
   采用分布式锁服务实现数据一致性，是在操作目标之前先获取操作许可，然后再执行操作，如果其他用户同时尝试操作该目标将被阻止，直到前一个用户释放许可后，其他用户才能够操作目标。分析这个过程，如果只有一个用户操作目标，没有多个用户并发冲突，也申请了操作许可，造成了由于申请操作许可所带来的资源使用消耗，浪费网络通信和增加了延时。
   采用分布式锁实现多副本内容修改的一致性问题， 选择控制内容颗粒度实现申请锁服务。例如我们要保证一个文件的多个副本修改一致， 可以对整个文件修改设置一把锁，修改时申请锁，修改这个文件的多个副本，确保多个副本修改的一致，修改完成后释放锁；也可以对文件分段，或者是文件中的单个字节设置锁， 实现更细颗粒度的锁操作，减少冲突。
   常用的锁实现算法有Lamport bakery algorithm （俗称面包店算法）， 还有Paxos算法以及乐观锁。下面对其原理做简单概述。
 
1. Lamport面包店算法
 
  是解决多个线程并发访问一个共享的单用户资源的互斥问题的算法。 由Leslie Lamport（英语：Leslie Lamport）发明。
   这个算法也可以称为时间戳策略，或者叫做Lamport逻辑时钟。
   这里先陈述一下这个逻辑时钟的内容：
   我们用分布式系统中的事件的先后关系，用“->”符号来表示，例如：若事件a发生在事件b之前，那么a->b.
   该关系需要满足下列三个条件：
 
如果a和b是同一进程中的事件，a在b之前发生，则a->b
如果事件a是消息发送方，b是接收方，则a->b
对于事件a、b、c,如果有a->b,b->c,则有a->c
 
  注意，对于任何一个事件a，a -> a都是不成立的，也就是说，关系->是反自反的。有了上面的定义，我们也可以定义出“并发”(concurrent)的概念了：
 
 
 
对于事件a、b，如果a -> b，b -> a两个都不成立，那么a和b就是并发的。
 
 
  直观上，上面的->关系非常好理解，即“xxx在xxx之前发生”。也就是说，一个系统在输入I1下，如果有a->b，那么对于这个系统的同一个输入I1，无论重复运行多少次，a也始终发生在b之前；如果在输入I1下a和b是并发的，则表示在同一个输入I1下的不同运行中，a可能在b之前，也可能在b之后，也可能恰好同时发生。也就是，并发并不是指一定同时发生，而是表示一种不确定性。->和并发的概念，就是我们理解一个系统时最基础的概念之一了。
   有了上面的概念，我们可以给系统引入时钟了。这里的时钟就是lamport逻辑时钟。一个时钟，本质上是一个事件到实数（假设时间是连续的）的函数。这个函数将每个事件映射到一个数字，代表这个事件发生的时间。形式一点来说，对于每个进程Pi，都有一个时钟Ci，这个时钟将该进程中的事件a映射到Ci(a)。而整个系统的时钟C=<　C0, C1, …, Cn>，对于一个事件b，假设b属于进程Pj，那么C(b) =Cj(b)。
 
  这里插一句，从这个定义也可以看到大师对分布式系统的理解。分布式系统中不存在一个“全局”的实体。在该系统中，每个进程都是一个相对独立的实体，它们有自己的本地信息（本地Knowledge）。而整个系统的信息则是各个进程的信息的一个聚合。
   有了时钟的一个“本质定义”还不够，我们需要考虑，什么样的时钟是一个有意义的，或者说正确的时钟。其实，有了前文的->关系的定义，正确的时钟应满足的条件已经十分明显了：
   时钟条件：对于任意两个事件a，b，如果a -> b，那么C(a) < C(b)。
   注意，反过来讲这个条件可不成立。如果我们要求反过来也成立，即“如果a -> b为假，那么C(a) < C(b)也为假”，那就等于要求并发事件必须同时发生，这显然是不合理的。
   结合前文->关系的定义，我们可以把上面的条件细化成如下两条：
 
如果a和b是进程Pi中的两个事件，并且在Pi中，a在b之前发生，那么Ci(a) < Ci(b)；
如果a是Pi发送消息m，b是Pj接收消息m，那么Ci(a) < Cj(b)；
 
  上面就定义了合理的逻辑时钟。显然，一个系统可以有无数个合理的逻辑时钟。实现逻辑时钟也相对简单，只要遵守两条实现规则就可以了：
 
每个进程Pi在自己的任何两个连续的事件之间增加Ci值；
如果事件a是Pi发送消息m，那么在m中应该带上时间戳Tm=Ci(a)；如果b是进程Pj接收到消息m，那么，进程Pj应该设置Cj为大于max(Tm,Cj(b))。
 
  有了上面逻辑时钟的定义，我们现在可以为一个系统中所有的事件排一个全序，就是使用事件发生时的逻辑时钟读数进行排序，读数小的在先。当然，此时可能会存在两个事件同时发生的情况。如果要去除这种情况，方法也非常简单：如果a在进程Pi中，b在进程Pj中，Ci(a) = Cj(b)且i < j，那么a在b之前。形式化一点，我们可以把系统事件E上的全序关系“=>”定义为：
   假设a是Pi中的事件，b是Pj中的事件，那么：a => b当且仅当以下两个条件之一成立：
 
Ci(a) < Cj(b)；
Ci(a) = Cj(b) 且 i < j；
 
  Lamport把上面这些数理逻辑时钟的概念以非常直观地类比为顾客去面包店采购。面包店只能接待一位顾客的采购。已知有n位顾客要进入面包店采购，安排他们按照次序在前台登记一个签到号码。该签到号码逐次加1。根据签到号码的由小到大的顺序依次入店购货。完成购买的顾客在前台把其签到号码归0. 如果完成购买的顾客要再次进店购买，就必须重新排队。
   这个类比中的顾客就相当于线程，而入店购货就是进入临界区独占访问该共享资源。由于计算机实现的特点，存在两个线程获得相同的签到号码的情况，这是因为两个线程几乎同时申请排队的签到号码，读取已经发出去的签到号码情况，这两个线程读到的数据是完全一样的，然后各自在读到的数据上找到最大值，再加1作为自己的排队签到号码。为此，该算法规定如果两个线程的排队签到号码相等，则线程id号较小的具有优先权。
   把该算法原理与分布式系统相结合，即可实现分步锁。
   注意这个系统中需要引入时钟同步，博主的意见是可以采用SNTP实现时钟同步（非权威，仅供参考）。
 
2.Paxos算法
 
  该算法比较热门，类似2pc算法的升级版，在此不做赘述，可以自行搜索相关资料。(博主会在之后整理列出)
   需要注意的是这个算法也是Leslie Lamport提出的，由此可见这位大师之牛逼！
   Paxos算法解决的问题是一个分布式系统如何就某个值(决议)达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。节点通信存在两种模型：共享内存(Shared memory)和消息传递(Messages passing)。Paxos算法就是一种基于消息传递模型的一致性算法。BigTable使用一个分布式数据锁服务Chubby，而Chubby使用Paxos算法来保证备份的一致性。
   不仅只用在分布式系统，凡是多个过程需要达成某种一致性的都可以用到Paxos 算法。一致性方法可以通过共享内存（需要锁）或者消息传递实现，Paxos 算法采用的是后者。下面是Paxos 算法适用的几种情况：一台机器中多个进程/线程达成数据一致；分布式文件系统或者分布式数据库中多客户端并发读写数据；分布式存储中多个副本响应读写请求的一致性。
 
3. 采用乐观锁原理实现的同步
 
  我们举个例子说明该算法的实现原理。如一个金融系统，当某个操作员读取用户的数据，并在读出的用户数据的基础上进行修改时（如更改用户帐户余额），如果采用前面的分布式锁服务机制，也就意味着整个操作过程中（从操作员读出数据、开始修改直至提交修改结果的全过程，甚至还包括操作员中途去煮咖啡的时间），数据库记录始终处于加锁状态，可以想见，如果面对几百上千个并发，这样的情况将导致怎样的后果。
   乐观锁机制在一定程度上解决了这个问题。乐观锁，大多是基于数据版本（ Version）记录机制实现。何谓数据版本？即为数据增加一个版本标识，在基于数据库表的版本解决方案中，一般是通过为数据库表增加一个 “version” 字段来实现。读取出数据时，将此版本号一同读出，之后更新时，对此版本号加一。此时，将提交数据的版本数据与数据库表对应记录的当前版本信息进行比对，如果提交的数据版本号大于数据库表当前版本号，则予以更新，否则认为是过期数据。
   对于上面修改用户帐户信息的例子而言，假设数据库中帐户信息表中有一个 version 字段，当前值为 1 ；而当前帐户余额字段（ balance ）为 $100 。
 
操作员 A 此时将其读出（version=1 ），并从其帐户余额中扣除 $50（$100-$50 ）。
在操作员 A 操作的过程中，操作员B也读入此用户信息（ version=1 ），并从其帐户余额中扣除 $20 （ $100-$20 ）。
操作员 A 完成了修改工作，将数据版本号加一（ version=2 ），连同帐户扣除后余额（ balance=$50），提交至数据库更新，此时由于提交数据版本大于数据库记录当前版本，数据被更新，数据库记录 version 更新为 2 。
操作员 B 完成了操作，也将版本号加一（ version=2 ）试图向数据库提交数据（ balance=$80），但此时比对数据库记录版本时发现，操作员 B 提交的数据版本号为 2 ，数据库记录当前版本也为 2 ，不满足 “提交版本必须大于记录当前版本才能执行更新 “ 的乐观锁策略，因此，操作员 B 的提交被驳回。这样，就避免了操作员 B 用基于version=1 的旧数据修改的结果覆盖操作员A 的操作结果的可能。
 
 
欢迎支持笔者新作：《深入理解Kafka:核心设计与实践原理》和《RabbitMQ实战指南》，同时欢迎关注笔者的微信公众号：朱小厮的博客。
 
 

 来源：http://www.blogjava.net/hello-yun/archive/2012/04/27/376744.html
 
 在足球比赛里，一个球员在一场比赛中进三个球，称之为帽子戏法(Hat-trick)。在分布式数据系统中，也有一个帽子原理(CAP Theorem)，不过此帽子非彼帽子。CAP原理中，有三个要素：
 
一致性(Consistency)
可用性(Availability)
分区容忍性(Partition tolerance)
 
 CAP原理指的是，这三个要素最多只能同时实现两点，不可能三者兼顾。因此在进行分布式架构设计时，必须做出取舍。而对于分布式数据系统，分区容忍性是基本要求，否则就失去了价值。因此设计分布式数据系统，就是在一致性和可用性之间取一个平衡。对于大多数web应用，其实并不需要强一致性，因此牺牲一致性而换取高可用性，是目前多数分布式数据库产品的方向。
 
 当然，牺牲一致性，并不是完全不管数据的一致性，否则数据是混乱的，那么系统可用性再高分布式再好也没有了价值。牺牲一致性，只是不再要求关系型数据库中的强一致性，而是只要系统能达到最终一致性即可，考虑到客户体验，这个最终一致的时间窗口，要尽可能的对用户透明，也就是需要保障“用户感知到的一致性”。通常是通过数据的多份异步复制来实现系统的高可用和数据的最终一致性的，“用户感知到的一致性”的时间窗口则取决于数据复制到一致状态的时间。
 
 最终一致性(eventually consistent)
 
 对于一致性，可以分为从客户端和服务端两个不同的视角。从客户端来看，一致性主要指的是多并发访问时更新过的数据如何获取的问题。从服务端来看，则是更新如何复制分布到整个系统，以保证数据最终一致。一致性是因为有并发读写才有的问题，因此在理解一致性的问题时，一定要注意结合考虑并发读写的场景。
 
 从客户端角度，多进程并发访问时，更新过的数据在不同进程如何获取的不同策略，决定了不同的一致性。对于关系型数据库，要求更新过的数据能被后续的访问都能看到，这是强一致性。如果能容忍后续的部分或者全部访问不到，则是弱一致性。如果经过一段时间后要求能访问到更新后的数据，则是最终一致性。
 
 最终一致性根据更新数据后各进程访问到数据的时间和方式的不同，又可以区分为：
 
 
 
因果一致性。如果进程A通知进程B它已更新了一个数据项，那么进程B的后续访问将返回更新后的值，且一次写入将保证取代前一次写入。与进程A无因果关系的进程C的访问遵守一般的最终一致性规则。
“读己之所写（read-your-writes）”一致性。当进程A自己更新一个数据项之后，它总是访问到更新过的值，绝不会看到旧值。这是因果一致性模型的一个特例。
会话（Session）一致性。这是上一个模型的实用版本，它把访问存储系统的进程放到会话的上下文中。只要会话还存在，系统就保证“读己之所写”一致性。如果由于某些失败情形令会话终止，就要建立新的会话，而且系统的保证不会延续到新的会话。
单调（Monotonic）读一致性。如果进程已经看到过数据对象的某个值，那么任何后续访问都不会返回在那个值之前的值。
单调写一致性。系统保证来自同一个进程的写操作顺序执行。要是系统不能保证这种程度的一致性，就非常难以编程了。
 
 
 上述最终一致性的不同方式可以进行组合，例如单调读一致性和读己之所写一致性就可以组合实现。并且从实践的角度来看，这两者的组合，读取自己更新的数据，和一旦读取到最新的版本不会再读取旧版本，对于此架构上的程序开发来说，会少很多额外的烦恼。
 
 从服务端角度，如何尽快将更新后的数据分布到整个系统，降低达到最终一致性的时间窗口，是提高系统的可用度和用户体验非常重要的方面。对于分布式数据系统：
 
N — 数据复制的份数
W — 更新数据是需要保证写完成的节点数
R — 读取数据的时候需要读取的节点数
 
 如果W+R>N，写的节点和读的节点重叠，则是强一致性。例如对于典型的一主一备同步复制的关系型数据库，N=2,W=2,R=1，则不管读的是主库还是备库的数据，都是一致的。
 
 如果W+R<=N，则是弱一致性。例如对于一主一备异步复制的关系型数据库，N=2,W=1,R=1，则如果读的是备库，就可能无法读取主库已经更新过的数据，所以是弱一致性。
 
 对于分布式系统，为了保证高可用性，一般设置N>=3。不同的N,W,R组合，是在可用性和一致性之间取一个平衡，以适应不同的应用场景。
 
如果N=W,R=1，任何一个写节点失效，都会导致写失败，因此可用性会降低，但是由于数据分布的N个节点是同步写入的，因此可以保证强一致性。
如果N=R,W=1，只需要一个节点写入成功即可，写性能和可用性都比较高。但是读取其他节点的进程可能不能获取更新后的数据，因此是弱一致性。这种情况下，如果W<(N+1)/2，并且写入的节点不重叠的话，则会存在写冲突  

一致连续的直白意义是： 若函数 $f$ 一致连续，对于任意两点 $x$ 与 $y$，只要 $x$ 与 $y$ 充分接近，$f(x)$ 与 $f(y)$ 也能够充分接近。
 
邻域定义：
 对于任意实数 $ϵ>0$，总存在实数 $\delta >0$，只要 $\Vert x-y\Vert <\delta$，都有 $\Vert f(x)-f(y)\Vert <ϵ$.
 
海涅-康托尔定理表面：若一个函数在闭区间连续，则该函数也是一致连续的。