dhtphp两万字深度介绍散布式体系道理一文入魂

副本协议是贯穿全体分布式系统的理论核心。

副本同等性

分布式系统通过副本掌握协议，使得从系统外部读取系统内部各个副本的数据在一定的约束条件下相同，称之为副本同等性(consistency)。
副本同等性是针对分布式系统而言的，不是针对某一个副本而言。

强同等性(strong consistency)：任何时候任何用户或节点都可以读到最近一次成功更新的副本数据。
强同等性是程度最高的同等性哀求，也是实践中最难以实现的同等性。
单调同等性(monotonic consistency)：任何时候，任何用户一旦读到某个数据在某次更新后的值，这个用户不会再读到比这个值更旧的值。
单调同等性是弱于强同等性却非常实用的一种同等性级别。
由于常日来说，用户只关心从己方视角不雅观察到的同等性，而不会关注其他用户的同等脾气况。
会话同等性(session consistency)：任何用户在某一次会话内一旦读到某个数据在某次更新后的值，这个用户在这次会话过程中不会再读到比这个值更旧的值。
会话同等性通过引入会话的观点，在单调同等性的根本上进一步放松约束，会话同等性只担保单个用户单次会话内数据的单调修正，对付不同用户间的同等性和同一用户不同会话间的同等性没有保障。
实践中有许多机制恰好对应会话的观点，例如php 中的session 观点。
终极同等性(eventual consistency)：终极同等性哀求一旦更新成功，各个副本上的数据终极将达 到完备同等的状态，但达到完备同等状态所须要的韶光不能保障。
对付终极同等性系统而言，一个用户只要始终读取某一个副本的数据，则可以实现类似单调同等性的效果，但一旦用户改换读取的副本，则无法保障任何同等性。
弱同等性(week consistency)：一旦某个更新成功，用户无法在一个确定韶光内读到这次更新的值，且纵然在某个副本上读到了新的值，也不能担保在其他副本上可以读到新的值。
弱同等性系统一样平常很难在实际中利用，利用弱同等性系统须要运用方做更多的事情从而使得系统可用。
1.3 衡量分布式系统的指标性能：系统的吞吐能力，指系统在某一韶光可以处理的数据总量，常日可以用系统每秒处理的总的数据量来衡量；系统的相应延迟，指系统完成某一功能须要利用的韶光；系统的并发能力，指系统可以同时完成某一功能的能力，常日也用QPS(query per second)来衡量。
上述三个性能指标每每会相互制约，追求高吞吐的系统，每每很难做到低延迟；系统均匀相应韶光较永劫，也很难提高QPS。
可用性：系统的可用性(availability)指系统在面对各种非常时可以精确供应做事的能力。
系统的可用性可以用系统停做事的韶光与正常做事的韶光的比例来衡量，也可以用某功能的失落败次数与成功次数的比例来衡量。
可用性是分布式的主要指标，衡量了系统的鲁棒性，是系统容错能力的表示。
可扩展性：系统的可扩展性(scalability)指分布式系统通过扩展集群机器规模提高系统性能（吞吐、延迟、并发）、存储容量、打算能力的特性。
好的分布式系统总在追求“线性扩展性”，也便是使得系统的某一指标可以随着集群中的机器数量线性增长。
同等性：分布式系统为了提高可用性，总是不可避免的利用副本的机制，从而引发副本同等性的问题。
越是强的同等的性模型，对付用户利用来说利用起来越大略。
2 分布式系统事理2.1 数据分布办法

所谓分布式系统顾名思义便是利用多台打算机协同办理单台打算机所不能办理的打算、存储等问题。
单机系统与分布式系统的最大的差异在于问题的规模，即打算、存储的数据量的差异。
将一个单机问题利用分布式办理，首先要办理的便是如何将问题拆解为可以利用多机分布式办理，使得分布式系统中的每台机器卖力原问题的一个子集。
由于无论是打算还是存储，其问题输入工具都是数据，以是如何拆遣散布式系统的输入数据成为分布式系统的基本问题。

哈希办法

哈希分布数据的缺陷同样明显，突出表现为可扩展性不高，一旦集群规模须要扩展，则险些所有的数据须要被迁移并重新分布。
工程中，扩展哈希分布数据的系统时，每每使得集群规模成倍扩展，按照数据重新打算哈希，这样原来一台机器上的数据只需迁移一半到另一台对应的机器上即可完成扩展。

针对哈希办法扩展性差的问题，一种思路是不再大略的将哈希值与机器做除法取模映射，而是将对应关系作为元数据由专门的元数据做事器管理.同时，哈希值取模个数每每大于机器个数，这样同一台机器上须要卖力多个哈希取模的余数。
但须要以较繁芜的机制掩护大量的元数据。
哈希分布数据的另一个缺陷是，一旦某数据特色值的数据严重不均，随意马虎涌现“数据倾斜”（data skew）问题。

哈希分布数据的另一个缺陷是，一旦某数据特色值的数据严重不均，随意马虎涌现“数据倾斜”（data skew）问题

按数据范围分布

按数据范围分布是另一个常见的数据分布式，将数据按特色值的值域范围划分为不同的区间，使得集群中每台（组）做事器处理不同区间的数据。

工程中，为了数据迁移等负载均衡操作的方便，每每利用动态划分区间的技能，使得每个区间中做事的数据量只管即便的一样多。
当某个区间的数据量较大时，通过将区间“分裂”的办法拆分为两个区间，使得每个数据区间中的数据量都只管即便坚持在一个较为固定的阈值之下。

一样平常的，每每须要利用专门的做事器在内存中掩护数据分布信息，称这种数据的分布信息为一种元信息。
乃至对付大规模的集群，由于元信息的规模非常弘大，单台 打算机无法独立掩护，须要利用多台机器作为元信息做事器。

按数据量分布

数据量分布数据与详细的数据特色无关，而是将数据视为一个顺序增长的文件，并将这个文件按照某一较为固定的大小划分为多少数据块（chunk），不同的数据块分布到不同的做事器上。
与按数据范围分布数据的办法类似的是，按数据量分布数据也须要记录数据块的详细分布情形，并将该分布信息作为元数据利用元数据做事器管理。

由于与详细的数据内容无关，按数据量分布数据的办法一样平常没有数据倾斜的问题，数据总是被均匀切分并分布到集群中。
当集群须要重新负载均衡时，只需通过迁移数据块即可完成。
集群扩容也没有太大的限定，只需将部分数据库迁移到新加入的机器上即可以完成扩容。
按数据量划分数据的缺陷是须要管理较为繁芜的元信息，与按范围分布数据的办法类似，当集群规模较大时，元信息的数据量也变得很大，高效的管理元信息成为新的课题。

同等性哈希

同等性哈希（consistent hashing）是另一个种在工程中利用较为广泛的数据分布办法。
同等性哈希最初在P2P 网络中作为分布式哈希表（DHT）的常用数据分布算法。
同等性哈希的基本办法是利用一个哈希函数打算数据或数据特色的哈希值，令该哈希函数的输出值域为一个封闭的环，即哈希函数输出的最大值是最小值的前序。
将节点随机分布到这个环上，每个节点卖力处理从自己开始顺时针至下一个节点的全部哈希值域上的数据。

利用同等性哈希的办法须要将节点在同等性哈希环上的位置作为元信息加以管理，这点比直策应用哈希分布数据的办法要繁芜。
然而，节点的位置信息只于集群中的机器规模干系，其元信息的量常日比按数据范围分布数据和按数据量分布数据的元信息量要小很多。

为此一种常见的改进算法是引入虚节点（virtual node）的观点，系统初始时就创建许多虚节点，虚节点的个数一样平常远大于未来集群中机器的个数，将虚节点均匀分布到同等性哈希值域环上，其功能与基本同等性哈希算法中的节点相同。
为每个节点分配多少虚节点。
操作数据时，首先通过数据的哈希值在环上找到对应的虚节点，进而查找元数据找到对应的真实节点。
利用虚节点改进有多个优点。
首先，一旦某个节点不可用，该节点将使得多个虚节点不可用，从而使得多个相邻的真实节点负载失落效节点的压里。
同理，一旦加入一个新节点，可以分配多个虚节点，从而使得新节点可以 负载多个原有节点的压力，从全局看，较随意马虎实现扩容时的负载均衡。

副本与数据分布

分布式系统容错、提高可用性的基本手段便是利用副本。
对付数据副本的分布办法紧张影响系统的可扩展性。
一种基本的数据副本策略因此机器为单位，多少机器互为副本，副本机器之间的数据完备相同。
这种策略适用于上述各种数据分布办法。
其优点是非常大略，其缺陷是规复数据的效率不高、可扩展性也不高。

更得当的做法不因此机器作为副本单位，而是将数据拆为较合理的数据段，以数据段为单位作为副本。
实践中，常常使得每个数据段的大小只管即便相等且掌握在一定的大小以内。
数据段有很多不同的称谓，segment，fragment，chunk，partition 等等。
数据段的选择与数据分布办法直接干系。
对付哈希分数据的办法，每个哈希分桶后的余数可以作为一个数据段，为了掌握数据段的大小，常常使得分桶个数大于集群规模。
一旦将数据分为数据段，则可以以数据段为单位管理副本，从而副本与机器不再硬干系，每台机器都可以卖力一定数据段的副本。

一旦副本分布与机器无关，数据丢失后的规复效率将非常高。
这是由于，一旦某台机器的数据丢失，其上数据段的副本将分布在全体集群的所有机器中，而不是仅在几个副本机器中，从而可以从全体集群同时拷贝规复数据，而集群中每台数据源机器都可以以非常低的资源做拷贝。
作为规复数据源的机器纵然都限速1MB/s，若有100 台机器参与规复，规复速率也能达到100MB/s。
再者，副本分布与机器无关也利于集群容错。
如果涌现机器宕机，由于宕机机器上的副本分散于全体集群，其压力也自然分散到全体集群。
末了，副本分布与机器无关也利于集群扩展。
理论上，设集群规模 为N 台机器，当加入一台新的机器时，只需从各台机器上迁移1/N – 1/N+1 比例的数据段到新机器即实现了新的负载均衡。
由于是从集群中各机器迁移数据，与数据规复同理，效率也较高。
工程中，完备按照数据段建立副本会引起须要管理的元数据的开销增大，副本掩护的难度也相应增大。
一种折中的做法是将某些数据段组成一个数据段分组，按数据段分组为粒度进行副本管理。
这样做可以将副本粒度掌握在一个较为得当的范围内。

本地化打算

在分布式系统中，数据的分布办法也深深影响着打算的分布办法。
在分布式系统中计算节点和保存打算数据的存储节点可以在同一台物理机器上，也可以位于不同的物理机器。
如果打算节点和存储节点位于不同的物理机器则打算的数据须要通过网络传输，此种办法的开销很大，乃至网络带宽会成为系统的总体瓶颈。
另一种思路是，将打算只管即便调度到与存储节点在同一台物理机器上的打算节点上进行，这称之为本地化打算。
本地化打算是打算调度的一种主要优化，其表示了一种主要的分布式调度思想：“移动数据不如移动打算”。

数据分布办法的选择

在实际工程实践中，可以根据需求及履行繁芜度合理选择数据分布办法。
其余，数据分布办法是可以灵巧组合利用的，每每可以兼备各种办法的优点，收到较好的综合效果。

例：数据倾斜问题，在按哈希分数据的根本上引入按数据量分布数据的办法，办理该数据倾斜问题。
按用户id 的哈希值分数据，当某个用户id 的数据量特殊大时，该用户的数据始终落在某一台机器上。
此时，引入按数据量分布数据的办法，统计用户的数据量，并按某一阈值将用户的数据切为多个均匀的数据段，将这些数据段分布到集群中去。
由于大部分用户的数据量不会超过阈值，以是元数据中仅仅保存超过阈值的用户的数据段分布信息，从而可以掌握元数据的规模。
这种哈希分布数据办法与按数据量分布数据办法组合利用的方案，在某真实系统中利用，取得了较好的效果。

2.2 基本副本协议

副本掌握协议指按特定的协议流程掌握副本数据的读写行为，使得副本知足一定的可用性和同等性哀求的分布式协议。
副本掌握协议要具有一定的对抗非常状态的容错能力，从而使得系统具有一定的可用性，同时副本掌握协议要能供应一定同等性级别。
由CAP 事理（在2.9 节详细剖析）可知，要设计一种知足强同等性，且在涌现任何网络非常时都可用的副本协议是不可能的。
为此，实际中的副本掌握协议总是在可用性、同等性与性能等各要素之间按照详细需求折中。

副本掌握协议可以分为两大类：“中央化(centralized)副本掌握协议”和“去中央化(decentralized)副本掌握协议”。

中央化副本掌握协议

中央化副本掌握协议的基本思路是由一个中央节点折衷副本数据的更新、掩护副本之间的同等性。
图给出了中央化副本协议的通用架构。
中央化副本掌握协议的优点是协议相对较为大略，所有的副本相关的掌握交由中央节点完成。
并发掌握将由中央节点完成，从而使得一个分布式并发掌握问题，简化为一个单机并发掌握问题。
所谓并发掌握，即多个节点同时须要修正副本数据时，须要办理“写写”、“读写”等并发冲突。
单机系统上常用加锁等办法进行并发掌握。
对付分布式并发掌握，加锁也是一个常用的方法，但如果没有中央节点统一进行锁管理，就须要完备分布式化的锁系统，会使得协议非常繁芜。
中央化副本掌握协议的缺陷是系统的可用性依赖于中央化节点，当中心节点非常或与中央节点通信中断时，系统将失落去某些做事（常日至少失落去更新做事），以是中央化副本掌握协议的缺陷正是存在一定的停做事韶光。

primary-secondary 协议

在primary-secondary 类型的协议中，副本被分为两大类，个中有且仅有一个副本作为primary 副本，除primary 以外的副本都作为secondary 副本。
掩护primary 副本的节点作为中央节点，中央节点卖力掩护数据的更新、并发掌握、折衷副本的同等性。

Primary-secondary 类型的协议一样平常要办理四大类问题：数据更新流程、数据读取办法、Primary 副本的确定和切换、数据同步（reconcile）。

数据更新基本流程数据更新都由primary 节点折衷完成。
外部节点将更新操作发给primary 节点primary 节点进行并发掌握即确定并发更新操作的先后顺序primary 节点将更新操作发送给secondary 节点primary 根据secondary 节点的完成情形决定更新是否成功并将结果返回外部节点

在工程实践中，如果由primary 直接同时发送给其他N 个副本发送数据，则每个 secondary 的更新吞吐受限于primary 总的出口网络带宽，最大为primary 网络出口带宽的1/N。
为理解决这个问题，有些系统（例如，GFS），利用接力的办法同步数据，即primary 将更新发送给第一 个secondary 副本，第一个secondary 副本发送给第二secondary 副本，依次类推。

数据读取办法

数据读取办法也与同等性高度干系。
如果只须要终极同等性，则读取任何副本都可以知足需求。
如果须要会话同等性，则可以为副本设置版本号，每次更新后递增版本号，用户读取副本时验证版本号，从而担保用户读到的数据在会话范围内单调递增。
利用primary-secondary 比较困难的是实现强同等性。

由于数据的更新流程都是由primary 掌握的，primary 副本上的数据一定是最新的，以是 如果始终只读primary 副本的数据，可以实现强同等性。
如果只读primary 副本，则secondary 副本将不供应读做事。
实践中，如果副本不与机器绑定，而是按照数据段为单位掩护副本，仅有primary 副本供应读做事在很多场景下并不会造出机器资源摧残浪费蹂躏。

将副本分散到集群中个，假设primary 也是随机的确定的，那么每台机器上都有一些数据的primary 副本，也有另一些数据段的secondary 副本。
从而某台做事器实际都供应读写做事。

由primary 掌握节点secondary 节点的可用性。
当primary 更新某个secondary 副本不堪利时，primary 将该secondary 副本标记为不可用，从而用户不再读取该不可用的副本。
不可用的 secondary 副本可以连续考试测验与primary 同步数据，当与primary 完成数据同步后，primary 可以副本标记为可用。
这种办法使得所有的可用的副本，无论是primary 还是secondary 都是可读的，且在一个确定的韶光内，某secondary 副本要么更新到与primary 同等的最新状态，要么被标记为不可用，从而符合较高的同等性哀求。
这种办法依赖于一个中央元数据管理系统，用于记录哪些副本可用，哪些副本不可用。
某种意义上，该办法通过降落系统的可用性来提高系统的同等性。
primary 副本的确定与切换

在primary-secondary 类型的协议中，另一个核心的问题是如何确定primary 副本，尤其是在原primary 副当地点机器涌现宕机等非常时，须要有某种机制切换primary 副本，使得某个secondary 副本成为新的primary 副本。

常日的，在primary-secondary 类型的分布式系统中，哪个副本是primary 这一信息都属于元信息，由专门的元数据做事器掩护。
实行更新操作时，首先查询元数据做事器获取副本的primary 信息，从而进一步实行数据更新流程。

由于分布式系统中可靠的创造节点非常是须要一定的探测韶光的，这样的探测韶光常日是10 秒级别，这也意味着一旦primary 非常，最多须要10 秒级别的创造韶光，系统才能开始primary 的切换，在这10 秒韶光内，由于没有primary，系统不能供应更 新做事，如果系统只能读primary 副本，则这段韶光内乃至不能供应读做事。
从这里可以看到，primary-backup 类副本协议的最大缺陷便是由于primary 切换带来的一定的停做事韶光。

数据同步

不一致的secondary 副本须要与primary 进行同步（reconcile）。

常日不一致的形式有三种：一、由于网络分解等非常，secondary 上的数据掉队于primary 上的数据。
二、在某些协议下，secondary 上的数据有可能是脏数据，须要被丢弃。
所谓脏数据是由于primary 副本没有进行某一更新操作，而secondary 副本上反而进行的多余的修正操作，从而造成secondary 副本数据缺点。
三、secondary 是一个新增加的副本，完备没有数据，须要从其他副本上拷贝数据。

对付第一种secondary 数据掉队的情形，常见的同步办法是回放primary 上的操作日志（常日是redo 日志），从而追上primary 的更新进度。
对付脏数据的情形，较好的做法是设计的分布式协议不产生脏数据。
如果协议一定有产生脏数据的可能，则也该当使得产生脏数据的概率降到非常低得情形，从而一旦发生脏数据的情形可以大略的直接丢弃有脏数据的副本，这样相称于副本没有数据。
其余，也可以设计一些基于undo 日志的办法从而可以删除脏数据。
如果secondary 副本完备没有数据，则常见的做法是直接拷贝primary 副本的数据，这种方法每每比回放日志追更新进度的方法快很多。
但拷贝数据时primary 副本须要能够连续供应更新做事，这就哀求primary 副本支持快照(snapshot)功能。
即对某一刻的副本数据形成快照，然后拷贝快照，拷贝完成后利用回放日志的办法追快照形成后的更新操作。

去中央化副本掌握协议

去中央化副本掌握协议没有中央节点，协议中所有的节点都是完备对等的，节点之间通过平等协商达到同等。
从而去中央化协议没有由于中央化节点非常而带来的停做事等问题。

去中央化协议的最大的缺陷是协议过程常日比较繁芜。
尤其当去中央化协议须要实现强同等性时，协议流程变得繁芜且不随意马虎理解。
由于流程的繁芜，去中央化协议的效率或者性能一样平常也较中央化协议低。
一个不恰当的比方便是，中央化副本掌握协议类似专制制度，系统效率高但高度依赖于中央节点，一旦中央节点非常，系统受到的影响较大；去中央化副本掌握协议类似民主制度，节点集体协商，效率低下，但个别节点的非常不会对系统总体造成太大影响。

2.3 Lease 机制

Lease 机制是最主要的分布式协议，广泛运用于各种实际的分布式系统中。

基于lease 的分布式cache 系统

基本的问题背景如下：在一个分布式系统中，有一个中央做事器节点，中央做事器存储、掩护着一些数据，这些数据是系统的元数据。
系统中其他的节点通过访问中央做事器节点读取、修正其上的元数据。
由于系统中各种操作都依赖于元数据，如果每次读取元数据的操作都访问中央做事器 节点，那么中央做事器节点的性能成为系统的瓶颈。
为此，设计一种元数据cache，在各个节点上 cache 元数据信息，从而减少对中央做事器节点的访问，提高性能。
另一方面，系统的精确运行严格依赖于元数据的精确，这就哀求各个节点上cache 的数据始终与中央做事器上的数据同等，cache 中的数据不能是旧的脏数据。
末了，设计的cache 系统要能最大可能的处理节点宕机、网络中断等非常，最大程度的提高系统的可用性。

为此，利用lease 机制设计一套cache 系统，其基本事理为如下。
中央做事器在向各节点发送数据时同时向节点颁发一个lease。
每个lease 具有一个有效期，和信用卡上的有效期类似，lease 上的 有效期常日是一个明确的韶光点，例如12:00:10，一旦真实时间超过这个韶光点，则lease 过期失落效。
这样lease 的有效期与节点收到lease 的韶光无关，节点可能收到lease 时该lease 就已经由期失落效。
这里首先假设中央做事器与各节点的时钟是同步的，不才节中谈论时钟不同步对lease 的影响。
中央做事器发出的lease 的含义为：在lease 的有效期内，中央做事器担保不会修正对应数据的值。
因此，节点收到数据和lease 后，将数据加入本地Cache，一旦对应的lease 超时，节点将对应确当地cache 数据删除。
中央做事器在修正数据时，首先壅塞所有新的读要求，并等待之前为该数据发出的所有lease 超时过期，然后修正数据的值。

基于lease 的cache，客户端节点读取元数据

判断元数据是否已经处于本地cache 且lease 处于有效期内1.1 是：直接返回cache 中的元数据1.2 否：向中央做事器节点要求读取元数据信息1.2.1 做事器收到读取要求后，返回元数据及一个对应的lease 1.2.2 客户端是否成功收到做事器返回的数据 1.2.2.1 失落败或超时：退出流程，读取失落败，可重试1.2.2.2 成功：将元数据与该元数据的lease 记录到内存中，返回元数据基于lease 的cache，客户端节点修正元数据流程2.1 节点向做事器发起修正元数据要求。
2.2 做事器收到修正要求后，壅塞所有新的读数据要求，即吸收读要求，但不返回数据。
2.3 做事器等待所有与该元数据干系的lease 超时。
2.4 做事器修正元数据并向客户端节点返回修正成功。

上述机制可以担保各个节点上的cache 与中央做事器上的中央始终同等。
这是由于中央做事器节点在发送数据的同时付与了节点对应的lease，在lease 有效期内，做事器不会修正数据，从而客户端节点可以放心的在lease 有效期内cache 数据。
上述lease 机制可以容错的关键是：做事器一旦 发出数据及lease，无论客户端是否收到，也无论后续客户端是否宕机，也无论后续网络是否正常，做事器只要等待lease 超时，就可以担保对应的客户端节点不会再连续cache 数据，从而可以放心的修正数据而不会毁坏cache 的同等性。

上述根本流程有一些性能和可用性上的问题，但可以很随意马虎就优化改性。
优化点一：做事器在修正元数据时首先要壅塞所有新的读要求，造成没有读做事。
这是为了防止发出新的lease 从而引起不断有新客户端节点持有lease 并缓存着数据，形成“活锁”。
优化的方法很大略，做事器在进入修正数据流程后，一旦收到读要求则只返回数据但不颁发lease。
从而造成在修正流程实行的过程中，客户端可以读到元数据，只是不能缓存元数据。
进一步的优化是，当进入修正流程，做事器颁发的lease 有效期限选择为已发出的lease 的最大有效期限。
这样做，客户端可以连续在做事器进入修正流程后连续缓存元数据，但做事器的等待所有lease 过期的韶光也不会由于颁发新的lease 而不断延长。

末了，=cache 机制与多副本机制的差异。
Cache 机制与多副本机制的相似之处都 是将一份数据保存在多个节点上。
但Cache 机制却要大略许多，对付cache 的数据，可以随时删除丢弃，并命中cache 的后果仅仅是须要访问数据源读取数据；然而副本机制却不一样，副本是不能随意丢弃的，每失落去一个副本，做事质量都不才降，一旦副本数低落到一定程度，则每每做事将不再可用。

lease 机制的剖析

lease 的定义：Lease 是由颁发者付与的在某一有效期内的承诺。
颁发者一旦发出lease，则无论接管方是否收到，也无论后续吸收方处于何种状态，只要lease 不过期，颁发者一定严守承诺；另一方面，吸收方在lease 的有效期内可以利用颁发者的承诺，但一旦lease 过期，吸收方一定不能连续利用颁发者的承诺。

Lease 机制具有很高的容错能力。
首先，通过引入有效期，Lease 机制能否非常好的容错网络非常。
Lease 颁发过程只依赖于网络可以单向通信，纵然吸收方无法向颁发者发送，也不影响lease 的颁发。
由于lease 的有效期是一个确定的韶光点，lease 的语义与发送lease 的详细韶光无关，以是 同一个lease 可以被颁发者不断重复向接管方发送。
纵然颁发者偶尔发送lease 失落败，颁发者也可以 大略的通过重发的办法办理。
一旦lease 被吸收方成功接管，后续lease 机制不再依赖于网络通信，纵然网络完备中断lease 机制也不受影响。
再者，Lease 机制能较好的容错节点宕机。
如果颁发者宕机，则宕机的颁发者常日无法改变之前的承诺，不会影响lease 的精确性。
在颁发者机规复后，如果颁发者规复出了之前的lease 信息，颁发者可以连续遵守lease 的承诺。
如果颁发者无法规复lease 信息，则只需等待一个最大的lease 超时时间就可以使得所有的lease 都失落效，从而不毁坏lease机制。

例如上节中的cache 系统的例子中，一旦做事器宕机，肯定不会修正元数据，重新规复后，只需等待一个最大的lease 超时时间，所有节点上的缓存信息都将被清空。
对付接管方宕机的情形，颁发者 不须要做更多的容错处理，只需等待lease 过期失落效，就可以收回承诺，实践中也便是收回之前授予的权限、身份等。
末了，lease 机制不依赖于存储。
颁发者可以持久化颁发过的lease 信息，从而在 宕机规复后可以使得在有效期的lease 连续有效。
但这对付lease 机制只是一个优化，如之前的剖析，纵然颁发者没有持久化lease 信息，也可以通过等待一个最大的lease 韶光的办法使得之前所有颁发 的lease 失落效，从而担保机制连续有效。

Lease 机制依赖于有效期，这就哀求颁发者和吸收者的时钟是同步的。
一方面，如果颁发者的 时钟比吸收者的时钟慢，则当吸收者认为lease 已经由期的时候，颁发者依旧认为lease 有效。
吸收者可以用在lease 到期前申请新的lease 的办法办理这个问题。
另一方面，如果颁发者的时钟比吸收 者的时钟快，则当颁发者认为lease 已经由期的时候，吸收者依旧认为lease 有效，颁发者可能将lease 颁发给其他节点，造成承诺失落效，影响系统的精确性。
对付这种时钟不同步，实践中的常日做法是将颁发者的有效期设置得比吸收者的略大，只需大过期钟偏差就可以避免对lease 的有效性的影响。

基于lease 机制确定节点状态

分布式协议依赖于对节点状态认知的全局同等性，即一旦节点Q 认为某个节点 A 非常，则节点A 也必须认为自己非常，从而节点A 停滞作为primary，避免“双主”问题的涌现。
办理这种问题有两种思路，第一、设计的分布式协议可以容忍“双主”缺点，即不依赖于对节点状 态的全局同等性认识，或者全局同等性状态是全体协商后的结果；第二、利用lease 机制。
对付第一 种思路即放弃利用中央化的设计，而改用去中央化设计，超过本节的谈论范畴。
下面着重谈论利用 lease 机制确定节点状态。

由中央节点向其他节点发送lease，若某个节点持有有效的lease，则认为该节点正常可以供应服 务。
用于例2.3.1 中，节点A、B、C 依然周期性的发送heart beat 报告自身状态，节点Q 收到heart beat 后发送一个lease，表示节点Q 确认了节点A、B、C 的状态，并许可节点在lease 有效期内正常工 作。
节点Q 可以给primary 节点一个分外的lease，表示节点可以作为primary 事情。
一旦节点Q 希望切换新的primary，则只需等前一个primary 的lease 过期，则就可以安全的颁发新的lease 给新的 primary 节点，而不会涌现“双主”问题。

在实际系统中，若用一个中央节点发送lease 也有很大的风险，一旦该中央节点宕机或网络非常，则所有的节点没有lease，从而造成系统高度不可用。
为此，实际系统总是利用多个中央节点互为副本，成为一个小的集群，该小集群具有高可用性，对外供应颁发lease 的功能。
chubby 和zookeeper 都是基于这样的设计。

lease 的有效期韶光选择

工程中，常选择的lease 时长是10 秒级别，这是一个经由验证的履历值，实践中可以作为参考并综合选择得当的时长。

2.4 Quorum 机制

先做这样的约定：更新操作（write）是一系列顺序的过程，通过其他机制确定更新操作的顺序（例如primary-secondary 架构中由primary 决定顺序），每个更新操作记为wi， i 为更新操作单调递增的序号，每个wi 实行成功后副本数据都发生变革，称为不同的数据版本，记 作vi。
假设每个副本都保存了历史上所有版本的数据。

write-all-read-one

Write-all-read-one（简称WARO）是一种最大略的副本掌握规则，顾名思义即在更新时写所有的副本，只有在所有的副本上更新成功，才认为更新成功，从而担保所有的副本同等，这样在读取数据时可以读任一副本上的数据。

由于更新操作须要在所有的N 个副本上都成功，更新操作才能成 功，以是一旦有一个副本非常，更新操作失落败，更新做事不可用。
对付更新做事，虽然有N 个副本， 但系统无法容忍任何一个副本非常。
另一方面，N 个副本中只要有一个副本正常，系统就可以供应读做事。
对付读做事而言，当有N 个副本时，系统可以容忍N-1 个副本非常。
从上述剖析可以创造WARO 读做事的可用性较高，但更新做事的可用性不高，乃至虽然利用了副本，但更新做事的可用性等效于没有副本。

Quorum 定义

在Quorum 机制下，当某次更新操作wi 一旦在所有N 个副本中的W 个副本上都成功，则就称 该更新操作为“成功提交的更新操作”，称对应的数据为“成功提交的数据”。
令R>N-W，由于更新 操作wi 仅在W 个副本上成功，以是在读取数据时，最多须要读取R 个副本则一定能读到wi 更新后 的数据vi 。
如果某次更新wi 在W 个副本上成功，由于W+R>N，任意R 个副本组成的凑集一定与 成功的W个副本组成的凑集有交集，以是读取R 个副本一定能读到wi 更新后的数据vi。
如图 2-10， Quorum 机制的事理可以文森图表示。

某系统有5 个副本，W=3，R=3，最初5 个副本的数据同等，都是v1，某次更新操作 w2 在前3 副本上成功，副本情形变成（v2 v2 v2 v1 v1）。
此时，任意3 个副本组成的凑集中一定包括 v2。
在上述定义中，令W=N，R=1，就得到WARO，即WARO 是Quorum 机制的一种特例。
与剖析WARO 相似，剖析Quorum 机制的可用性。
限定Quorum 参数为W+R=N+1。
由于更新 操作须要在W 个副本上都成功，更新操作才能成功，以是一旦N-W+1 个副本非常，更新操作始终无法在W 个副本上成功，更新做事不可用。
另一方面，一旦N-R+1 个副本非常，则无法担保一定可以读到与W 个副本有交集的副本凑集，则读做事的同等性低落。

再次强调：仅仅依赖quorum 机制是无法担保强同等性的。
由于仅有quorum 机制时无法确定最新已成功提交的版本号，除非将最新已提交的版本号作为元数据由特定的元数据做事器或元数据集群管理，否则很难确定最新成功提交的版本号。
不才一节中，将谈论在哪些情形下，可以仅仅 通过quorum 机制来确定最新成功提交的版本号。

Quorum 机制的三个别系参数N、W、R 掌握了系统的可用性，也是系统对用户的做事承诺：数据最多有N 个副本，但数据更新成功W 个副本即返回用户成功。
对付同等性哀求较高的Quorum 系统，系统还该当承诺任何时候不读取未成功提交的数据，即读取到的数据都是曾经在W 个副本上成功的数据。

读取最新成功提交的数据

Quorum 机制只需成功更新N 个副本中的W 个，在读取R 个副本时，一定可以读到最新的成功提交的数据。
但由于有不堪利的更新情形存在，仅仅读取R 个副本却不一定能确定哪个版本的数据 是最新的已提交的数据。
对付一个强同等性Quorum 系统，若存在个数据少于W 个，假设为X 个，则连续读取其他副本，直若成功读取到W 个 该版本的副本，则该数据为最新的成功提交的数据；如果在所有副本中该数据的个数肯定不满 足W 个，则R 中版本号第二大的为最新的成功提交的副本。
例：在读取到（v2 v1 v1）时，连续读取剩余的副本，若读到剩余两个副本 为（v2 v2）则v2 是最新的已提交的副本；若读到剩余的两个副本为（v2 v1）或（v1 v1）则v1 是最新成功提交的版本；若读取后续两个副本有任一超时或失落败，则无法判断哪个版本是最新的成功提交的版本。

可以看出，在纯挚利用Quorum 机制时，若要确定最新的成功提交的版本，最多须要读取R+ （W-R-1）=N 个副本，当涌现任一副本非常时，读最新的成功提交的版本这一功能都有可能不可用。
实际工程中，该当只管即便通过其他技能手段，回避通过Quorum 机制读取最新的成功提交的版本。
例如，当quorum 机制与primary-secondary 掌握协议结合利用时，可以通过读取primary 的办法读取到最新的已提交的数据。

基于Quorum 机制选择primary副本

读取数据时依照同等性哀求的不同可以有不同的做法：如果须要强同等性的急速读取到最新的成功提交的数据，则可以大略的只读取primary 副本上的数据即可，也可以通过上节的办法读取；如果须要会话同等性，则可以根据之前已经读到的数据版本号在各个副本上进行选择性读取；如果只须要弱同等性，则可以选择任意副本读取。

在primary-secondary 协议中，当primary 非常时，须要选择出一个新的primary，之后secondary 副本与primary 同步数据。
常日情形下，选择新的primary 的事情是由某一中央节点完成的，在引入 quorum 机制后，常用的primary 选择办法与读取数据的办法类似，即中央节点读取R 个副本，选择 R 个副本中版本号最高的副本作为新的primary。
新primary 与至少W 个副本完成数据同步后作为新的primary 供应读写做事。
首先，R 个副本中版本号最高的副本一定蕴含了最新的成功提交的数据。
再者，虽然不能确定最高版本号的数是一个成功提交的数据，但新的primary 在随后与secondary 同 步数据，使得该版本的副本个数达到W，从而使得该版本的数据成为成功提交的数据。

例：在N=5，W=3，R=3 的系统中，某时候副本最大版本号为（v2 v2 v1 v1 v1），此时v1 是系统的最新的成功提交的数据，v2 是一个处于中间状态的未成功提交的数据。
假设此刻原primary 副本非常，中央节点进行primary 切换事情。
这类“中间态”数据究竟作为“脏数据”被删除，还是作为新的数据被同步后成为生效的数据，完备取决于这个数据能否参与新primary 的选举。
下面分别剖析这两种情形。

第一、如图 2-12，若中央节点与个中3 个副本通信成功，读取到的版本号为（v1 v1 v1），则任 选一个副本作为primary，新primary 以v1 作为最新的成功提交的版本并与其他副本同步，当与第1、第2 个副本同步数据时，由于第1、第2 个副本版本号大于primary，属于脏数据，可以按照2.2.2.4 节中先容的处理脏数据的办法办理。
实践中，新primary 也有可能与后两个副本完成同步后就供应数据做事，随后自身版本号也更新到v2，如果系统不能担保之后的v2 与之前的v2 完备一样，则新 primary 在与第1、2 个副本同步数据时不但要比较数据版本号还须要比较更新操作的详细内容是否一样。

第二、若中央节点与其他3 个副本通信成功，读取到的版本号为（v2 v1 v1），则选取版本号为 v2 的副本作为新的primary，之后，一旦新primary 与其他2 个副本完成数据同步，则符合v2 的副 本个数达到W 个，成为最新的成功提交的副本，新primary 可以供应正常的读写做事。

2.5 日志技能

日志技能是宕机规复的紧张技能之一。
日志技能最初利用在数据库系统中。
严格来说日志技能不是一种分布式系统的技能，但在分布式系统的实践中，却广泛利用了日志技能做宕机规复，甚 至如BigTable 等系统将日志保存到一个分布式系统中进一步增强了系统容错能力。

Redo Log 与Check point

设计一个高速的单机查询系统，将数据全部存放在内存中以实现高速的数据查询，每次更新操作更新一小部分数据（例如 key-value 中的某一个key）。
现在问题为利用日志技能实现该内存查询系统的宕机规复。
与数据库的事务不同的是，这个问题模型中的每个成功的更新操作都会生效。
这也等效为数据库的每个事务只有一个更新操作，且每次更新操作都可以也必须立即提交（Auto commit）。

Redo Log将更新操作的结果（例如Set K1=1，则记录K1=1）以追加写（append）的办法写入磁盘的 日志文件按更新操作修正内存中的数据返回更新成功

从Redo Log 的流程可以看出，Redo 写入日志的是更新操作完成后的结果（虽然本文不谈论Undo Log，这点是与Undo Log 的差异之一），且由于是顺序追加写日志文件，在磁盘等对顺序写有力的 存储设备上效率较高。

用Redo Log 进行宕机规复非常大略，只须要“回放”日志即可。

流程2.5.2：Redo Log 的宕机规复

从头读取日志文件中的每次更新操作的结果，用这些结果修正内存中的数据。

从Redo Log 的宕机规复流程也可以看出，只有写入日志文件的更新结果才能在宕机后规复。
这也是为什么在Redo Log 流程中须要先更新日志文件再更新内存中的数据的缘故原由。
如果先更新内存中的数据，那么用户急速就能读到更新后的数据，一旦在完成内存修正与写入日志之间发生宕机，那么末了一次更新操作无法规复，但之前用户可能已经读取到了更新后的数据，从而引起不一致的问题。

Check point

。
在简化的模型下，check point 技能的过程即将内存中的数据以某种易于重新加载的数据组织办法完全的dump 到磁盘，从而减少宕机规复时须要回放的日志数据。

流程：check point

向日志文件中记录“Begin Check Point”将内存中的数据以某种易于重新加载的数据组织办法dump 到磁盘上向日志文件中记录“End Check Point” 在check point 流程中，数据可以连续按照流程2.5.1 被更新，这段过程中新更新的数据可以dump 到磁盘也可以不dump 到磁盘，详细取决于实现。
例如，check point 开始时k1=v1，check point 过程 中某次更新为k1 = v2，那么dump 到磁盘上的k1 的值可以是v1 也可以是v2。

流程：基于check point 的宕机规复流程

将dump 到磁盘的数据加载到内存。
从后向前扫描日志文件，探求末了一个“End Check Point”日志。
从末了一个“End Check Point”日志向前找到最近的一个“Begin Check Point”日志，并回 放该日志之后的所有更新操作日志。
No Undo/No Redo log

若数据掩护在磁盘中，某批更新由多少个更新操作组成，这些更新操作须要原子生效，即要么同时生效，要么都不生效。

0/1 目录技能中有两个目录构造，称为目录0(Directory 0)和目录1(Directory 1)。
另有一个构造称为主记录（Master record）记录当前正在利用的目录称为活动目录。
主记录中要么记录利用目录0，要么记录利用目录1。
目录0 或目录1 中记录了各个数据的在日志文件中的位置。
0/1 目录的数据更新过程始终在非活动目录上进行，只是在数据生效前，将主记录中的0、1 值反转，从而切换主记录。

流程：0/1 目录数据更新流程

将活动目录完全拷贝到非活动目录。
对付每个更新操作，新建一个日志项记录操作后的值，并在非活动目录中将相应数据的位置修正为新建的日志项的位置。
原子性修正主记录：反转主记录中的值，使得非活动目录生效。

0/1 目录的更新流程非常大略，通过0、1 目录的主记录切换使得一批修正的生效是原子的。
0/1 目录将批量事务操作的原子性通过目录手段归结到主记录的原子切换。
由于多条记录的原子修正一样平常较难实现而单条记录的原子修正每每可以实现，从而降落了问题实现的难度。
在工程中0/1 目录的思想利用非常广泛，其形式也不局限在上述流程中，可以是内存中的两个数据构造来回切换，也可以是磁盘上的两个文件目录来回生效切换。

2.6 两阶段提交协议

两阶段提交协议是一种经典的强同等性中央化副本掌握协议。
虽然在工程中该协议有较多的问题，但研究该协议能很好的理解分布式系统的几个范例问题。

流程描述

两阶段提交协议是一种范例的“中央化副本掌握”协议。
在该协议中，参与的节点分为两类：一个中央化折衷者节点（coordinator）和N 个参与者节点（participant）。
每个参与者节点即上文背景先容中的管理数据库副本的节点。

两阶段提交的思路比较大略，在第一阶段，折衷者讯问所有的参与者是否可以提交事务（请参与者投票），所有参与者向折衷者投票。
在第二阶段，折衷者根据所有参与者的投票结果做出是否事务可以全局提交的决定，并关照所有的参与者实行该决定。
在一个两阶段提互换程中，参与者不能改变自己的投票结果。
两阶段提交协议的可以全局提交的条件是所有的参与者都赞许提交事务，只要有一个参与者投票选择放弃(abort)事务，则事务必须被放弃。

流程：两阶段提交折衷者流程

写本地日志“begin_commit”，并进入WAIT 状态；向所有参与者发送“prepare ”；等待并吸收参与者发送的对“prepare ”的相应；3.1 若收到任何一个参与者发送的“vote-abort ”；3.1.1 写本地“global-abort”日志，进入ABORT；3.1.2 向所有的参与者发送“global-abort ”；3.1.3 进入ABORT 状态；3.2 若收到所有参与者发送的“vote-commit”；3.2.1 写本地“global-commit”日志，进入COMMIT 状态；3.1.2 向所有的参与者发送“global-commit ”；等待并吸收参与者发送的对“global-abort ”或“global-commit ”的确认相应，一旦收到所有参与者的确认，写本地“end_transaction” 日志流程结束。

流程：两阶段提交折衷者流程

写本地日志“init”记录，进入INIT 状态等待并接管折衷者发送的“prepare ”，收到后 2.1 若参与者可以提交本次事务 2.1.1 写本地日志“ready”，进入READY 状态 2.1.2 向折衷者发送“vote-commit” 2.1.4 等待折衷者的2.1.4.1 若收到折衷者的“global-abort”2.1.4.1.1 写本地日志“abort”，进入ABORT 状态2.1.4.1.2 向折衷者发送对“global-abort”的确认 2.1.4.2 若收到折衷者的“global-commit”2.1.4.1.1 写本地日志“commit”，进入COMMIT 状态 2.1.4.1.2 向折衷者发送对“global-commit”的确认 2.2 若参与者无法提交本次事务 2.2.1 写本地日志“abort”，进入ABORT 状态 2.2.2 向折衷者发送“vote-abort” 2.2.3 流程对该参与者结束 2.2.4 若后续收到折衷者的“global-abort”可以相应纵然流程结束，但任何时候收到折衷者发送的“global-abort”或“global-commit”也都要发送一个对应的确认。
非常处理宕机规复折衷者宕机规复 折衷者宕机规复后，首先通过日志查找到宕机前的状态。
如果日志中末了是“begin_commit”记录，解释宕机前折衷者处于WAIT 状态，折衷者可能已经发送过“prepare ”也可能还没发送，但折衷者一定还没有发送过“global-commit ”或“global-abort ”，即事务的全局状态还没有确定。
此时，折衷者可以重新发送“prepare ” 连续两阶段提互换程，纵然参与者已经发送过对“prepare ”的相应，也不过是再次重传之前的相应而不会影响协议的同等性。
如果日志中末了是“global-commit”或“global-abort”记录，解释宕机前折衷者处于COMMIT 或ABORT 状态。
此时折衷者只需重新向所有的参与者发送“global-commit ”或“global-abort ”就可以连续两阶段提互换程。
参与者宕机规复参与者宕机规复后，首先通过日志查找宕机前的状态。
如果日志中末了是“init”记录，解释参与者处于INIT 状态，还没有对本次事务做出投票选择，参与者可以连续流程等待折衷者发送的“prepare ”。
如果日志中末了是“ready”记录，解释参与者处于REDAY 状态，此时解释参与者已经就本次 事务做出了投票选择，但宕机前参与者是否已经向折衷者发送“vote-commit”并不可知。
以是此时参与者可以向折衷者重发“vote-commit”，并连续协议流程。
如果日志中末了是“commit”或“abort”记录，解释参与者已经收到过折衷者的“global-commit ”（处于COMMIT 状态）或者“global-abort ”（处于ABORT 状态）。
至于是否向折衷者发 送过对“global-commit”或“global-abort”的确认则未知。
但纵然没有发送过确认，由于折衷者会不断重发“global-commit”或“global-abort”，只需在收到这些时发送确认既可，不影响协议的全局同等性。
协议剖析

两阶段提交协议在工程实践中真正利用的较少，紧张缘故原由有以下几点：

两阶段提交协议的容错能力较差。
从上文的剖析可以看出，两阶段提交协议在某些情形下存在流程无法实行下去的情形，且也无法判断流程状态。
在工程中好的分布式协议每每总是可以在即使发生非常的情形下也能实行下去。
例如，回顾Lease 机制（2.3 ），一旦lease 发出，无论涌现任何非常，Lease 做事器节点总是可以通过韶光剖断出Lease 是否有效，也可以用等待Lease 超时的方法收回Lease 权限，全体Lease 协议的流程不存在任何流程被壅塞而无法实行下去的情形。
与Lease 机制的大略有效比较，两阶段提交的协议显得较为繁芜且容错能力差。
两阶段提交协议的性能较差。
一次成功的两阶段提交协议流程中，折衷者与每个参与者 之间至少须要两轮交互4 个“prepare”、“vote-commit”、“global-commit”、“确认global-commit”。
过多的交互次数会降落性能。
另一方面，折衷者须要等待所有的参与者的投票结果，一旦存在较慢的参与者，会影响全局流程实行速率。

虽然存在一些改进的两阶段提交协议可以提高容错能力和性能，然而这类协议依旧是在工程中利用较少的一类协议，其理论价值大于实践意义。

2.7 MVCC

MVCC(Multi-version Cocurrent Control，多版本并发掌握)技能。
MVCC 技能最初也是在数据库系统中被提出，但这种思想并不局限于单机的分布式系统，在分布式系统中同样有效。

MVCC 即多个不同版本的数据实现并发掌握的技能，其基本思想是为每次事务天生 一个新版本的数据，在读数据时选择不同版本的数据即可以实现对事务结果的完全性读取。
在利用MVCC 时，每个事务都是基于一个已生效的根本版本进行更新，事务可以并行进行，从而可以产生一种图状构造。

根本数据的版本为1，同时产生了两个事务：事务A 与事务B。
这两个事务都各自对数据进行了一些本地修正（这些修正只有事务自己可见，不影响真正的数据），之后事务A 首先提交，天生数据版本2；基于数据版本2，又发起了事务C，事务C 连续提交，天生了数据版 本3；末了事务B 提交，此时势务B 的结果须要与事务C 的结果合并，如果数据没有冲突，即事务 B 没有修正事务A 与事务C 修正过的变量，那么事务B 可以提交，否则事务B 提交失落败。
MVCC 的流程过程非常类似于SVN 等版本掌握系统的流程，或者说SVN 等版本掌握系统便是 利用的MVCC 思想。
事务在基于根本数据版本做本地修正时，为了不影响真正的数据，常日有两种做法，一是将根本数据版本中的数据完备拷贝出来再修正，SVN 即利用了这种方法，SVN check out 即是拷贝的过程；二是每个事务中只记录更新操作，而不记录完全的数据，读取数据时再将更新操作运用到用根本版本的数据从而打算出结果，这个过程也类似SVN 的增量提交。

2.8 Paxos协议

Paxos 协议是少数在工程实践中证明的强同等性、高可用的去中央化分布式协议。
Paxos 协议的流程较为繁芜，但其基本思想却不难明得，类似于人类社会的投票过程。
Paxos 协议中，有一组完备对等的参与节点（称为accpetor），这组节点各自就某一事宜做出决议，如果某个决议得到了超过半数节点的赞许则生效。
Paxos 协议中只要有超过一半的节点正常，就可以事情，能很好对抗宕机、网络分解等非常情形。

角色

Proposer：提案者。
Proposer 可以有多个，Proposer 提出议案（value）。
所谓value，在工程中可以是任何操作，例如“修正某个变量的值为某个值”、“设置当前primary 为某个节点”等等。
Paxos 协议中统一将这些操作抽象为value。
不同的Proposer 可以提出不同的乃至抵牾的value，例如某个Proposer 发起“将变量X 设置为1”，另一个Proposer 发起“将变量X 设置为2”，但对同一轮Paxos 过程，最多只有一个value 被批准。
Acceptor：批准者。
Acceptor 有N 个，Proposer 提出的value 必须得到超过半数(N/2+1)的Acceptor 批准后才能通过。
Acceptor 之间完备对等独立。
Learner：学习者。
Learner 学习被批准的value。
所谓学习便是通过读取各个Proposer 对value 的选择结果，如果某个value 被超过半数Proposer 通过，则Learner 学习到了这个value。
回顾（2.4 ） 不难明得，这里类似Quorum 机制，某个value 须要得到W=N/2 + 1 的Acceptor 批准，从而学习者须要至少读取N/2+1 个Accpetor，至多读取N 个Acceptor 的结果后，能学习到一个通过的value。
上述三类角色只是逻辑上的划分，实践中一个节点可以同时充当这三类角色。

流程

Paxos 协议一轮一轮的进行，每轮都有一个编号。
每轮Paxos 协议可能会批准一个value，也可 能无法批准一个value。
如果某一轮Paxos 协议批准了某个value，则往后各轮Paxos 只能批准这个 value。
上述各轮协议流程组成了一个Paxos 协议实例，即一次Paxos 协议实例只能批准一个value，这也是Paxos 协议强同等性的主要表示。
每轮Paxos 协议分为阶段，准备阶段和批准阶段，在这两个阶段Proposer 和Acceptor 有各自的处理流程。

流程：Proposer 的流程 （准备阶段）

向所有的Acceptor 发送“Prepare(b)”；这里b 是Paxos 的轮数，每轮递增如果收到任何一个Acceptor 发送的“Reject(B)”，则对付这个Proposer 而言本轮Paxos 失落败，将轮数b 设置为B+1 后重新步骤1；（批准阶段，根据收到的Acceptor 的作出不同选择）如果吸收到的Acceptor 的“Promise(b, v_i)”达到N/2+1 个（N 为Acceptor 总数，除法取整， 下同）；v_i 表示Acceptor 最近一次在i 轮批准过value v。
3.1 如果收到的“Promise(b, v)”中，v 都为空，Proposer 选择一个value v，向所有Acceptor 广播Accept(b, v)；3.2 否则，在所有收到的“Promise(b, v_i)”中，选择i 最大的value v，向所有Acceptor 广播Accept(b，v)；如果收到Nack(B)，将轮数b 设置为B+1 后重新步骤1；

流程：Accpetor 流程 （准备阶段）

接管某个Propeser 的Prepare(b)。
参数B 是该Acceptor 收到的最大Paxos 轮数编号；V 是Acceptor 批准的value，可以为空 1.1 如果b>B，回答Promise(b, V_B)，设置B=b; 表示担保不再接管编号小于b 的提案。
1.2 否则，回答Reject(B) （批准阶段）吸收Accept(b, v)， 2.1 如果b < B, 回答Nack(B)，暗示proposer 有一个更大编号的提案被这个Acceptor 吸收了 2.2 否则设置V=v。
表示这个Acceptor 批准的Value 是v。
广播Accepted 。
例子

基本例子里有5 个Acceptor，1 个Proposer，不存在任何网络、宕机非常。
我们着重稽核各个Accpetor 上变量B 和变量V 的变革，及Proposer 上变量b 的变革。

初始状态Proposer 向所有Accpetor 发送“Prepare(1)”，所有Acceptor 精确处理，并回答Promise(1, NULLProposer 收到5 个Promise(1, NULL)，知足多余半数的Promise 的value 为空，此时发送 Accept(1, v1)，个中v1 是Proposer 选择的Value。
此时，v1 被超过半数的Acceptor 批准，v1 即是本次Paxos 协议实例批准的Value。
如果Learner 学习value，学到的只能是v1

在同一个Paxos 实例中，批准的Value 是无法改变的，纵然后续Proposer 以更高的序号发起Paxos 协议也无法改变value。
Paxos 协议的核心就在于“批准的value 无法改变”，这也是全体协议精确性的根本。

Paxos 协议是被人为设计出来，其设计过程也是协议的推导过程。
Paxos 协议利用了Quorom 机 制，选择的W=R=N/2+1。
大略而言，协议便是Proposer 更新Acceptor 的过程，一旦某个Acceptor 成功更新了超过半数的Acceptor，则更新成功。
Learner 按Quorum 去读取Acceptor，一旦某个value 在超过半数的Proposer 上被成功读取，则解释这是一个被批准的value。
协议通过引入轮次，使得高轮次的发起抢占低轮次的发起来避免去世锁。
协议设计关键点是如何知足“在一次Paxos 算法实例过程中只批准一个Value”这一约束条件。

2.9 CAP

CAP 理论的定义很大略，CAP 三个字母分别代表了分布式系统中三个相互抵牾的属性：

Consistency (同等性)：CAP 理论中的副本同等性特指强同等性（1.3.4 ）；Availiablity(可用性)：指系统在涌现非常时已经可以供应做事；Tolerance to the partition of network (分区容忍)：指系统可以对网络分区（1.1.4.2 ）这种非常情 况进行容错处理；

CAP 理论指出：无法设计一种分布式协议，使得同时完备具备CAP 三个属性，即1)该种协议下的副本始终是强同等性，2)做事始终是可用的，3)协议可以容忍任何网络分区非常；分布式系统协议只能在CAP 这三者间所有折中。

热力学第二定律解释了永动机是不可能存在的，不要去梦想设计永动机。
与之类似，CAP 理论的意义就在于明确提出了不要去梦想设计一种对CAP 三大属性都完备拥有的完美系统，由于这种系统在理论上就已经被证明不存在。

Lease 机制: Lease 机制捐躯了部分非常情形下的A，从而得到了完备的C 与很好的P。
Quorum 机制: Quorum 机制，在CAP 三大成分中都各做了折中，有一定的C，有较好 的A，也有较好的P，是一种较为平衡的分布式协议。
两阶段提交协议: 两阶段提交系统具有完备的C，很糟糕的A，很糟糕的P。
Paxos 协议：同样是强同等性协议，Paxos 在CAP 三方面较之两阶段提交协议要精良得多。
Paxos 协议具有 完备的C，较好的A，较好的P。
Paxos 的A 与P 的属性与Quorum 机制类似，由于Paxos 的协议本 身就具有Quorum 机制的成分。

分享自：https://maimai.cn/article/detail?fid=1387195565&efid=tc4VEvx26dkpXT-lqpMzkA&use_rn=1