分布一致性算法

Ⅰ 一致性算法（Paxos、Raft、ZAB)

一致性算法（Paxos、Raft、ZAB)

什么是一致性

1、弱一致性
a、最终一致性
i、DNS（Domain Name System）
j、Gossip（Cassandra的通信协议）

以DNS为例：

2、强一致性
a、同步
b、Paxos
c、(multi-paxos)
d、ZAB(multi-paxos)

DNS 就是一种最终一致性，比如 上图中 增加一条记录： www.hyb.small.com , 我们从其他DNS服务器一时会读取不到，但是过一会就会读取得到了。

数据不能存在单点上。
分布式系统对fault tolerence的一般解决方案是state machine replication 。

准确的来说应该是 state machine replication 的共识（consensus）算法。

paxos其实是一个共识算法，系统的最终一致性，不仅需要达成共识，还会取决于client的行为

主从同步复制

1、Master 接受写请求
2、Master 复制日志到slave
3、Master 等待，直到所有从库返回

问题：

任何一个节点失败，哪怕是从节点（Slave）同步失败，都会导致整个集群不可用，虽然保证了一致性，但是可用性却大大降低

基本想法：
a、多数派：
每次写都保证写入大于N/2个节点，每次读保证从大于N/2个节点中读。
比如5个节点，每次写大于3个节点才算成功；读也是大于3个节点才算成功。

b、多数派还不够！
在并发环境下，无法保证系统正确性，顺序非常重要。比如下图的 Inc 5; Set 0; 执行顺序乱了，结果就会引发错乱。

Lesile Lamport,Latex的发明者。

为描述Paxos算法早昌，Lamport虚拟了一个叫做Paxos的希腊城邦，这个岛按照议会民主制的政治模式制定法律，但是没有人愿意将自己的全部时间和精力放在这种事上，所以无论是议员、议长或者传递消息的时间。

Paxos

1、Basic Paxos
2、Multi Paxos
3、Fast Paxos

强一致性算法---Basic Paxos

角色丛睁晌介绍：

Client:系统外部角色，请求发起者。像民众

Propser: 接渗锋受Client 请求，向集群提出提议(propose)。并在冲突发生时，起到冲突调节的作用。像议员替民众提出议案

Accpetor(Voter): 提议投票和接收者，只有在形成法定人数(Quorum,一般即为majority 多数派)时，提议才会最终接受，像国会。

Learner:提议接受者，backup，备份，对集群一致性没什么影响，像记录员；

步骤、阶段(phases):
1、Phase 1a:Prepare
proposer 提出一个提案，编号为N，此N 大于这个proposer之前提出提案编号，向acceptors请求同意，要求有quorum接受的才行。

2、Phase 1b:Promise
N 必须大于此acceptor之前接受的任何提案编号，才会接受，否则会拒绝。

3、Phase 2a: Accept
如果达到了多数派，proposer会发出accept请求，此请求包含提案编号N ,以及提案内容。

4、Phase 2b:Accepted
如果此acceptor在此期间没有收到任何编号大于N的提案，则接受此提案内容，否则忽略。

流程图如下：

操作步骤如下：
Request;
Prepare(1);
Promise(1,{Va,Vb,Vc});
Accept(1,Vn)
Accepted(1,Vn);
Response;

1、Acceptor部分节点失败，但达到了Quoroms，此时仍然会成功。

如果有一个Acceptor因为各种原因挂掉了，3个Acceptors变成了2个Acceptors，还是满足>n/2 的要求，所以还是会成功。

2、Proposer失败，上一次记录不会被写入Proposer表，然后重新开启一个新的Proposer，来替代上次的Proposer来处理未完成请求，此时编号已经增加为2，也就是Prepare(2)

Basic Paxos when an Proposer fails
如果Proposer 在发送了一条Accept消息之后，但是还没收到Accepted消息之前就挂掉了，只有一个Acceptor接收到了Accept消息。那么整个Paxos协议就没法进行下去了，这时一个新的Leader（Proposer）会被选举出来，重新开始一轮新的共识。

Basic Paxos潜在的问题是：活锁（liveness）或eling

Basic Paxos很有可能出现这种情况：
1、议员A(proposer A)说我们来讨论提案1，大部分议员说：“好，我们来讨论提案1”；
2、但是此时议员A还没有说内容是什么，这时候又来了一个议员B，又来说：“我们来讨论提案2”；这时候大部分还没有接受提案1，提案2的编号是大于提案1的，这时候大部分还没有接受议案2；
3、这时候议员A以为网络断了，然后把编号改下，内容不变然后提出议案3；然后议案4、议案5....
这样就形成了活锁。
解决活锁的方法是用Random的timeout，当两个冲突的时候用一个随机的等待时间；当自己提议未生效时，再发起提议等待几秒。

Basic-Paxos是一个无限循环的2PC，1条日志的确认至少需要2个RTT + 2次落盘（1次是prepare的广播与回复，1次是accept的广播与回复）。

Basic Paxos when multiple Proposers conflict
最后再描述一个最复杂的情况，即有多个Proposers认为他们是Leaders，并不断的发送Prepare请求。为什么会有多个Leaders呢？ 有可能一个Proposer当了一段时间Leader之后挂掉了，新的Proposer被选为Leader继续新的一轮共识。后面挂掉的Proposer又恢复了，它认为自己还是Leader，所以继续发送Prepare请求。

Basic Paxos的问题
难实现（角色太多）、效率低（2轮RPC）、活锁问题

Multi Paxos:
新概念，Leader;唯一的propser，所有请求都需经过此Leader;

只有一个Proposer，没有第二个Proposer； 这个Proposer就是Leader,没人跟他抢;

再者分布式系统必须串行执行所有提议，否则就会出现前面说的顺序问题。

--------First Request(第一次执行)----------
Request
Prepare(N) //选Leader
Promise(N,I,{Va,Vb,Vc})
Accept!(N,I,Vm)
Accepted(N,I,Vm)
Response;

--------Following Request(第二次或者以后)----------
Request
Accept!(N,I,Vm)
Accepted(N,I,Vm)
Response;

第二次或者以后，就不用再选Leader了 直接执行Request 请求，由Leader 发出议案。
如果Leader 挂了 就选下一个总统Leader(N+1)

减少角色，进一步简化，在Basic-Paxos中我们区分了很多角色，有Clients、Proposers、Acceptors、 Learners，实际上Proposers、Acceptors 、Leanrners可以合并成一个，统称为Server，下面是合并之后的序列图。

Multi-Paxos when roles are collapsed and the leader is steady
同样的，当Leader很稳定的时候，我们可以在接下来的执行中忽略Phase 1. 如下图所示：

Raft
1、划分三个子问题
a、Leader Election
b、Log Replication
c、Safely
2、重定义角色
a、Leader
b、Follower
c、Candidate

原理动画解释： http://thesecretlivesofdata.com/raft
场景测试： https://raft.github.io

Raft 是比 Multi Paxos 还要简单的一个版本
一致性并不代表完全正确性！三个可能结果：成功，失败，unknown

详细内容参考：
https://www.jianshu.com/p/6cd41fe0b8f6

强一致性算法--ZAB
基本与raft相同。在一些名词的叫法上有些区别：如ZAB将某一个leader的周期称为epoch，而raft则称为term。实现上也有些许不同：如raft保证日志连续性，心跳方向为leader至follower，ZAB则相反。

Ⅱ 分布式系统常用的一致性算法有哪些

在做服务器负载均衡时候可供选择的负载均衡的算法有很多，包括： 轮循算法（Round Robin）、哈希算法（HASH）、最少连接算法（Least Connection）、响应速度算法（Response Time）、加权法（Weighted ）等。其中哈希算法是最为常用的算法. 典型的应用场景是： 有N台服务器提供缓存服务，需要对服务器进行负载均衡，将请求平均分发到每台服务器上，每台机器负责1/N的服务。 常用的算法是对hash结果取余数 (hash() mod N)：对机器编号从0到N-1，按照自定义的hash()算法，对每个请求的hash()值按N取模，得到余数i，然后将请求分发到编号为i的机器。但这样的算法方法存在致命问题，如果某一台机器宕机，那么应该落在该机器的请求就无法得到正确的处理，这时需要将当掉的服务器从算法从去除，此时候会有(N-1)/N的服务器的缓存数据需要重新进行计算；如果新增一台机器，会有N /(N+1)的服务器的缓存数据需要进行重新计算。对于系统而言，这通常是不可接受的颠簸（因为这意味着大量缓存的失效或者数据需要转移）。那么，如何设计一个负载均衡策略，使得受到影响的请求尽可能的少呢？ 在Memcached、Key-Value Store、Bittorrent DHT、LVS中都采用了Consistent Hashing算法，可以说Consistent Hashing 是分布式系统负载均衡的首选算法。 1、Consistent Hashing算法描述 下面以Memcached中的Consisten Hashing算法为例说明。 由于hash算法结果一般为unsigned int型，因此对于hash函数的结果应该均匀分布在[0,232-1]间，如果我们把一个圆环用232 个点来进行均匀切割，首先按照hash(key)函数算出服务器（节点）的哈希值， 并将其分布到0～232的圆上。 用同样的hash(key)函数求出需要存储数据的键的哈希值，并映射到圆上。然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器（节点）上。 Consistent Hashing原理示意图 新增一个节点的时候，只有在圆环上新增节点逆时针方向的第一个节点的数据会受到影响。删除一个节点的时候，只有在圆环上原来删除节点顺时针方向的第一个节点的数据会受到影响，因此通过Consistent Hashing很好地解决了负载均衡中由于新增节点、删除节点引起的hash值颠簸问题。 Consistent Hashing添加服务器示意图 虚拟节点（virtual nodes）：之所以要引进虚拟节点是因为在服务器（节点）数较少的情况下（例如只有3台服务器），通过hash(key)算出节点的哈希值在圆环上并不是均匀分布的（稀疏的），仍然会出现各节点负载不均衡的问题。虚拟节点可以认为是实际节点的复制品（replicas），本质上与实际节点实际上是一样的（key并不相同）。引入虚拟节点后，通过将每个实际的服务器（节点）数按照一定的比例(例如200倍)扩大后并计算其hash(key)值以均匀分布到圆环上。在进行负载均衡时候，落到虚拟节点的哈希值实际就落到了实际的节点上。由于所有的实际节点是按照相同的比例复制成虚拟节点的，因此解决了节点数较少的情况下哈希值在圆环上均匀分布的问题。 虚拟节点对Consistent Hashing结果的影响 从上图可以看出，在节点数为10个的情况下，每个实际节点的虚拟节点数为实际节点的100-200倍的时候，结果还是很均衡的。 第3段中有这些文字：“但这样的算法方法存在致命问题，如果某一台机器宕机，那么应该落在该机器的请求就无法得到正确的处理，这时需要将当掉的服务器从算法从去除，此时候会有(N-1)/N的服务器的缓存数据需要重新进行计算；” 为何是 (N-1)/N 呢？解释如下： 比如有 3 台机器，hash值 1-6 在这3台上的分布就是： host 1: 1 4 host 2: 2 5 host 3: 3 6 如果挂掉一台，只剩两台，模数取 2 ，那么分布情况就变成： host 1: 1 3 5 host 2: 2 4 6 可以看到，还在数据位置不变的只有2个： 1，2，位置发生改变的有4个，占共6个数据的比率是 4/6 = 2/3这样的话，受影响的数据太多了，势必太多的数据需要重新从 DB 加载到 cache 中，严重影响性能 【consistent hashing 的办法】 上面提到的 hash 取模，模数取的比较小，一般是负载的数量，而 consistent hashing 的本质是将模数取的比较大，为 2的32次方减1，即一个最大的 32 位整数。然后，就可以从容的安排数据导向了，那个图还是挺直观的。 以下部分为一致性哈希算法的一种PHP实现。点击下载

Ⅲ 一致性hash算法

先说一下hash算法，hash算法是将任意长度的二进制值映射为固定长度的二进制值。

在分布式系统中， 可以通过该算法计算哈希值

Hash是一个字符串到正整数的hash映射函数， key是键值（例如服务器ip地址/唯一主机名）， n是键的个数。每当改变服务器数量时， 都会使hash值改变，容错性和扩展性会极差。

一致性hash算法将2的32次方的hash空间组成一个首尾相连的圆环，然后把服务器空败ip地址/唯一主机名作为键进行hash得到一个唯一的hash值，该值就是该服务器在圆环上的位置。数据也通过hash得到一个唯一的hash值，然后把数据放进最近的服务器中（顺时针），如下图。

假如服务器C宕机了， 数据B就会被放在服务器A，其他服务器和数据都不会受到影响。

假如新增服务器D， 数据C会放在服务器D中，其他的都不变。

在服务器节点太少时， 会有数据告亏码倾斜问题，即大部分数据在一个节点上。

为了解决这个问题，引入了虚拟节点。可以在ip地址/唯袜哪一主机名后面加上编号，使一台服务器算出多个hash值，在hash环上增加同一服务器节点，该节点就是虚拟节点；在服务器节点较少时也能实现数据均匀分布。

Ⅳ 分布式存储中，怎样使用paxos算法保证数据的一致性

在分布式系统中，我们经常遇到多数据副本保持一致的问题，在我们所能找到的资料中该问题讲的很笼统，模模糊糊的，把多个问题或分类糅合在一起，难以理解。在思考和翻阅资料后，通俗地把一致性的问题可分解为2个问题：
1、任何一次修改保证数据一致性。
2、多次数据修改的一致性。
在弱一致性的算法，不要求每次修改的内容在修改后多副本的内容是一致的，对问题1的解决比较宽松，更多解决问题2，该类算法追求每次修改的高度并发性，减少多副本之间修改的关联性，以获得更好的并发性能。例如最终一致性，无所谓每次用户修改后的多副本的一致性及格过，只要求在单调的时间方向上，数据最终保持一致，如此获得了修改极大的并发性能。
在强一致性的算法中，强调单次修改后结果的一致，需要保证了对问题1和问题2要求的实现，牺牲了并发性能。本文是讨论对解决问题1实现算法，这些算法往往在强一致性要求的应用中使用。
解决问题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、客户端（协调者）向所有的数据副本的存储主机（参与者）发送：修改具体的文件名、偏移量、数据和长度信息，请求修改数据，该消息是1阶段的请求消息。
2、存储主机接收到请求后，备份修改前的数据以备回滚，修改文件数据后，向客户端回应修改成功的消息。 如果存储主机由于某些原因（磁盘损坏、空间不足等）不能修改数据，回应修改失败的消息。
3、客户端接收发送出去的每一个消息回应，如果存储主机全部回应都修改成功，向每存储主机发送确认修改的提交消息；如果存在存储主机回应修改失败，或者超时未回应，客户端向所有存储主机发送取消修改的提交消息。该消息是2阶段的提交消息。
4、存储主机接收到客户端的提交消息，如果是确认修改，则直接回应该提交OK消息；如果是取消修改，则将修改数据还原为修改前，然后回应取消修改OK的消息。
5、 客户端接收全部存储主机的回应，整个操作成功。
在该过程中可能存在通信失败，例如网络中断、主机宕机等诸多的原因，对于未在算法中定义的其它异常，都认为是提交失败，都需要回滚，这是该算法基于确定的通信回复实现的，在参与者的确定回复（无论是回复失败还是回复成功）之上执行逻辑处理，符合确定性的条件当然能够获得确定性的结果哲学原理。

分布式锁服务

分布式锁是对数据被外界修改持保守态度，在整个数据处理过程中将数据处于锁定状态，在用户修改数据的同时，其它用户不允许修改。
采用分布式锁服务实现数据一致性，是在操作目标之前先获取操作许可，然后再执行操作，如果其他用户同时尝试操作该目标将被阻止，直到前一个用户释放许可后，其他用户才能够操作目标。分析这个过程，如果只有一个用户操作目标，没有多个用户并发冲突，也申请了操作许可，造成了由于申请操作许可所带来的资源使用消耗，浪费网络通信和增加了延时。
采用分布式锁实现多副本内容修改的一致性问题， 选择控制内容颗粒度实现申请锁服务。例如我们要保证一个文件的多个副本修改一致， 可以对整个文件修改设置一把锁，修改时申请锁，修改这个文件的多个副本，确保多个副本修改的一致，修改完成后释放锁；也可以对文件分段，或者是文件中的单个字节设置锁， 实现更细颗粒度的锁操作，减少冲突。
常用的锁实现算法有Lamport bakery algorithm （俗称面包店算法）， 还有Paxos算法。下面对其原理做简单概述。

Lamport面包店算法

是解决多个线程并发访问一个共享的单用户资源的互斥问题的算法。 由Leslie Lamport（英语：Leslie Lamport）发明。
Lamport把这个并发控制算法可以非常直观地类比为顾客去面包店采购。面包店只能接待一位顾客的采购。已知有n位顾客要进入面包店采购，安排他们按照次序在前台登记一个签到号码。该签到号码逐次加1。根据签到号码的由小到大的顺序依次入店购货。完成购买的顾客在前台把其签到号码归0. 如果完成购买的顾客要再次进店购买，就必须重新排队。
这个类比中的顾客就相当于线程，而入店购货就是进入临界区独占访问该共享资源。由于计算机实现的特点，存在两个线程获得相同的签到号码的情况，这是因为两个线程几乎同时申请排队的签到号码，读取已经发出去的签到号码情况，这两个线程读到的数据是完全一样的，然后各自在读到的数据上找到最大值，再加1作为自己的排队签到号码。为此，该算法规定如果两个线程的排队签到号码相等，则线程id号较小的具有优先权。
把该算法原理与分布式系统相结合，即可实现分步锁。

Paxos算法

该算法比较热门，参见WIKI，http://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95
Paxos算法解决的问题是一个分布式系统如何就某个值(决议)达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。节点通信存在两种模型：共享内存(Shared memory)和消息传递(Messages passing)。Paxos算法就是一种基于消息传递模型的一致性算法。BigTable使用一个分布式数据锁服务Chubby，而Chubby使用Paxos算法来保证备份的一致性。

采用乐观锁原理实现的同步

我们举个例子说明该算法的实现原理。如一个金融系统，当某个操作员读取用户的数据，并在读出的用户数据的基础上进行修改时（如更改用户帐户余额），如果采用前面的分布式锁服务机制，也就意味着整个操作过程中（从操作员读出数据、开始修改直至提交修改结果的全过程，甚至还包括操作员中途去煮咖啡的时间），数据库记录始终处于加锁状态，可以想见，如果面对几百上千个并发，这样的情况将导致怎样的后果。
乐观锁机制在一定程度上解决了这个问题。乐观锁，大多是基于数据版本（ 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 的操作结果的可能。
乐观锁机制与分布式系统相结合上， 我整理了伪代码如下：
obj 操作的目标
vlaue 修改的值
atom_update_ver 每个目标上的版本，每次修改该值递增
set( obj, value)
{
//从每个节点上取出修改前的对象版本
get original_ver = obj.atom_update_ver from each node;
//将值赋到每个节点的obj目标
set obj = value from each node;
//条件修改每个节点的obj版本，目标版本加一
//比较和修改操作是原子操作
result = (set obj.atom_update_ver = original_ver + 1
where original_ver + 1 > obj.atom_update_ver
for each node);
if(result == ok)
return set_ok;
else
return set(obj, value);//不成功递归修改

该算法未考虑节点下线、失效等问题，在后续我将分析采用乐观锁原理实现一致性算法，解决问题2、节点失效、通信失败等问题。

Ⅳ 一致性hash算法是什么

一致性哈希算法是在1997年由麻省理工学院提出的一种分布式哈希（DHT）算法。其设计目标是为了解决因特网中的热点（Hot spot)问题，初衷和CARP十分类似。

一致性Hash是一种特殊的Hash算法，由于其均衡性、持久性的映射特点，被广泛的应用于负载均衡领域，如nginx和memcached都采用了一致性Hash来作为集群负载均衡的方案。

一致性哈希算法的目标是，当K个请求key发起请求时。后台增减节点，只会引起K/N的key发生重新映射。即一致性哈希算法，在后台节点稳定时，同一key的每次请求映射到的节点是一样的。而当后台节点增减时，该算法尽量将K个key映射到与之前相同的节点上。

优点

可扩展性。一致性哈希算法保证了增加或减少服务器时，数据存储的改变最少，相比传统哈希算法大大节省了数据移动的开销。

更好地适应数据的快速增长。采用一致性哈希算法分布数据，当数据不断增长时，部分虚拟节点中可能包含很多数据、造成数据在虚拟节点上分布不均衡，此时可以将包含数据多的虚拟节点分裂，这种分裂仅仅是将原有的虚拟节点一分为二、不需要对全部的数据进行重新哈希和划分。

虚拟节点分裂后，如果物理服务器的负载仍然不均衡，只需在服务器之间调整部分虚拟节点的存储分布。这样可以随数据的增长而动态的扩展物理服务器的数量，且代价远比传统哈希算法重新分布所有数据要小很多。

以上内容参考：网络-一致性哈希

Ⅵ 详解分布式共识（一致性）算法Raft

所谓分布式共识（consensus），与 CAP理论 中的一致性（consistency）其实是异曲同工，就是在分布式系统中，所有节点对同一份数据的认知能够达成一致。保证集群共识的算法就叫共识算法，它与一致性协议这个词也经常互相通用。

当今最着名的共识算法就是Paxos算法。它由Leslie Lamport在1990年提出，很长时间以来都是一致性的事实标准。但是它有两个不小的缺点：难以理解和证明，难以在实际工程中实现。Google Chubby的工程师就曾有以下的评论：

于是2014年，来自斯坦福的两位大佬Diego Ongaro与John Ousterhout通过论文 《In Search of an Understandable Consensus Algorithm》 提出了一个新的共识算法Raft。从题目就可以看出，Raft的特点就是容易理解，在此基础上也容易实现，因此在real world中，它的应用也比Paxos要广泛，比较有名的如etcd、Ku等。

Raft为了达到易懂易用的目标，主要做了两件事：一是分解问题（decomposition），即将复杂的分布式共识问题拆分为 领导选举 （leader election）、 日志复制 （log replication）和 安全性 （safety）三个子问题，并分别解决；二是压缩状态空间（state space rection），相对于Paxos算法而言施加了更合理的限制，减少因为系统状态过多而产生的不确定性。

下面先简要介绍共识算法的基础——复制状态机，然后就来按顺序研究Raft是如何解决三个子问题的。

在共识算法中，所有服务器节点都会包含一个有限状态自动机，名为复制状态机（replicated state machine）。每个节点都维护着一个复制日志（replicated logs）的队列，复制状态机会按序输入并执行该队列中的请求，执行状态转换并输出结果。可见，如果能保证各个节点中日志的一致性，那么所有节点状态机的状态转换和输出也就都一致。共识算法就是为了保障这种一致性的，下图示出简单的复制状态机及其相关架构。

根据分布式系统的 Quorum机制 与NRW算法，集群中半数以上节点可用时，就能正确处理分布式事务，因此Raft集群几乎都使用奇数节点，可以防止脑裂并避免浪费资源。采用ZAB协议的ZooKeeper集群也是如此。

在Raft集群中，任意节点同一时刻只能处于领导者（leader）、跟随者（follower）、候选者（candidate）三种状态之一。下图示出节点状态的转移规则。

可见，集群建立时所有节点都是跟随节点。如果在一定时间过后发现没有领导节点，就会切换到候选状态，发起选举。得到多数票的候选者就会成为领导节点。如果候选节点或当前领导节点发现了更新的领导者，就会主动退回跟随状态。

领导节点全权负责管理复制日志，也就是从客户端接收请求，复制到跟随节点，并告诉跟随节点何时可以处理这些请求。如果领导节点故障或断开连接，就会重新进行选举。可见，领导节点的存在大大简化了共识算法的设计。

在上面的图中出现了任期（term）这个词。领导者并不是一直“在位”的，工作一段时间之后，就会选举出新的领导者来接替它。

由上图可见，蓝色表示选举时间段，绿色表示选举出的领导者在位的时间段，这两者合起来即称作一个任期，其计数值是自增的。任期的值就可以在逻辑上充当时间戳，每个节点都会保存一份自己所见的最新任期值，称为currentTerm。另外，如果因为票数相同，没能选出领导，就会立即再发起新的选举。

如果一个或多个跟随节点在选举超时（election timeout）内没有收到领导节点的心跳（一个名为AppendEntries的RPC消息，本意是做日志复制用途，但此时不携带日志数据），就会发起选举流程：

根据其他节点回复的消息，会出现如下三种结果：

获得多数票的节点只要当选，就会立即给其他所有节点发送AppendEntries，避免再次选举。另外，在同一任期内，每个节点只能投一票，并且先到先得（first-come-first-served），也就是会把票投给RequestVote消息第一个到达的那个节点。

至于上面的第三种情况，也就是所谓“split vote”现象，容易在很多跟随者变成候选者时出现，因为没有节点能得到多数票，选举有可能无限继续下去。所以，Raft设置的选举超时并不是完全一样的，而是有些许随机性，来尽量使得投票能够集中到那些较“快”的节点上。

领导节点选举出来后，集群就可以开始处理客户端请求了。前面已经说过，每个节点都维护着一个复制日志的队列，它们的格式如下图所示。

可见，日志由一个个按序排列的entry组成。每个entry内包含有请求的数据，还有该entry产生时的领导任期值。在论文中，每个节点上的日志队列用一个数组log[]表示。

当客户端发来请求时，领导节点首先将其加入自己的日志队列，再并行地发送AppendEntries RPC消息给所有跟随节点。领导节点收到来自多数跟随者的回复之后，就认为该请求可以提交了（见图中的commited entries）。然后，领导节点将请求应用（apply）到复制状态机，并通知跟随节点也这样做。这两步做完后，就不会再回滚。
这种从提交到应用的方式与最基础的一致性协议——两阶段提交（2PC）有些相似，但Raft只需要多数节点的确认，并不需要全部节点都可用。

注意在上图中，领导节点和4个跟随节点的日志并不完全相同，这可能是由于跟随节点反应慢、网络状况差等原因。领导节点会不断地重试发送AppendEntries，直到所有节点上的日志达到最终一致，而不实现强一致性。这就是CAP理论中在保证P的情况下，C与A无法兼得的体现。

日志复制的过程仍然遗留了一个问题：如果领导或者跟随节点发生异常情况而崩溃，如何保证日志的最终一致性？它属于下面的安全性问题中的一部分，稍后会解答它。

安全性是施加在领导选举、日志复制两个解决方案上的约束，用于保证在异常情况下Raft算法仍然有效，不能破坏一致性，也不能返回错误的结果。所有分布式算法都应保障安全性，在其基础上再保证活性（liveness）。

Raft协议的安全性保障有5种，分别是：选举安全性（election safety）、领导者只追加（leader append-only）、日志匹配（log matching）、领导者完全性（leader completeness）、状态机安全性（state machine safety） 。下面分别来看。

选举安全性是指每个任期内只允许选出最多一个领导。如果集群中有多于一个领导，就发生了脑裂（split brain）。根据“领导选举”一节中的描述，Raft能够保证选举安全，因为：

在讲解日志复制时，我们可以明显地看出，客户端发出的请求都是插入领导者日志队列的尾部，没有修改或删除的操作。这样可以使领导者的行为尽量简单化，使之没有任何不确定的行为，同时也作为下一节要说的日志匹配的基础。

日志匹配的具体描述如下。
如果两个节点的日志队列中，两个entry具有相同的下标和任期值，那么：

第一点自然由上一节的“领导者只追加”特性来保证，而第二点则由AppendEntries RPC消息的一个简单机制来保证：每条AppendEntries都会包含最新entry之前那个entry的下标与任期值，如果跟随节点在对应下标找不到对应任期的日志，就会拒绝接受并告知领导节点。

有了日志匹配特性，就可以解决日志复制中那个遗留问题了。假设由于节点崩溃，跟随节点的日志出现了多种异常情况，如下图。

注意图中不是6个跟随节点，而是6种可能的情况。比如a和b是丢失了entry，c和d是有多余的未提交entry，e和f则是既有丢失又有冗余。这时领导节点就会找到两个日志队列中最近一条匹配的日志点，将该点之后跟随节点的所有日志都删除，然后将自己的这部分日志复制给它。例如对于上图中的情况e来说，最近一条匹配的日志下标为5，那么5之后的所有entry都会被删除，被替换成领导者的日志。

领导者完全性是指，如果有一条日志在某个任期被提交了，那么它一定会出现在所有任期更大的领导者日志里。这也是由两点来决定的：

根据这两个描述，每次选举出的领导节点一定包含有最新的日志，因此只存在跟随节点从领导节点更新日志的情况，而不会反过来，这也使得一致性逻辑更加简化，并且为下面的状态机安全性提供保证。

状态机安全性是说，如果一个节点已经向其复制状态机应用了一条日志中的请求，那么对于其他节点的同一下标的日志，不能应用不同的请求。这句话就很拗口了，因此我们来看一种意外的情况。

这里就有问题了，在时刻c的日志与新领导者的日志发生了冲突，此时状态机是不安全的。
为了解决该问题，Raft不允许领导者在当选后提交“前任”的日志，而是通过日志匹配原则，在处理“现任”日志时将之前的日志一同提交。具体方法是：在领导者任期开始时，立刻提交一条空的日志，所以上图中时刻c的情况不会发生，而是像时刻e一样先提交任期4的日志，连带提交任期2的日志。就算此时S1再崩溃，S5也不会重新被选举了。

如果想要更直观地理解Raft，建议参考 这里 ，是一个用动画来描述该算法的网页，形象生动。

Ⅶ 共识算法（分布式下的一致性算法)

共识算法（分布式下的一致性算法)

业务场景：

达到的效果：可以保证在过半节点正常的情况下，所有的写入操作不会丢失。

Zab协议并不保证强一致性，也不是弱一致性，而是在一定限度内的强一致性慎轿山。

缺点：

缺点：

区块链1.0时代：比特币，作用就是去中心化的货币，无国界的货币，并且可以匿名性的洗钱
区块链2.0时代：代表以太坊，引入了智能合约的概念，发挥其 去中心化和不可篡改的特性，可以实现类似于 追溯、拍卖、投票等业务场景。

区块链技术的实用价值：
无国界虚拟货币：比如比特币

模拟一个拍卖（盲拍）的业务场景（发布一个智能合约）：
https://solidity.readthedocs.io/en/latest/solidity-by-example.html#simple-open-auction

普通拍卖可能存在的问题：

商家A对一件商品公开自己要拍卖，智能合约在规定的时间会开始接收竞拍（参与竞拍的人需要支付保证金（以太币）），在竞拍结束之后，价格最高的人会完成支付，帆空其它的买家的保证金会全额退回。
然后成功竞拍者可以线下去找卖家，证明自己的身份，然后获得竞拍品

优点：

工作量证明（ PoW ）通过计算一个数值（ nonce ），使得拼揍上交易数据后内容的 Hash 值满足规定的上限。在节点成功找到满足的Hash值之后，会马上对全网进行广播打包区块，网络的节点收到广播打包区块，会立刻对其进行验证

举个例子，给定的一个基本的字符串”Hello, world!”，我们给出的工作量要求是，可以在这个字符串后面添加一个叫做nonce的整数值，对变更后（添加nonce)的字符串进行SHA256哈希运算，
如果得到的哈希结果（以16进制的形式表示）是以”0000”开头的，则验证通过。为了达到这个工作量证明的目标。我们需要不停的递增nonce值，对得到的新字符串进行SHA256哈希运算。
按照这个规则，我们需要经过4251次计算才能找到恰好前4位为0的哈希散列。计算完之后，然后广播到临近的节点，临近的节点会先验算交易是否合法（金额是否异常），再验证hash值是否满足要求，都满足的话，就会把这个数据块添加到自己的账本中。

优点：

缺点：

计算难度值会因为 股东持有的 币龄而降低，为挖矿无形之中提升了壁垒，股东更容易算出结果值（难度更低），从而避免过度的算力竞争，节省电力，提升系统的稳定性。
因为从人性的角度，股东更不愿意让不安全的现象发生（比如攻击主链)，因为会造成信用降低，从而自己的矿币贬值。让股东拥有更多的记账权，让主链更安全宽中。

扩展可以参考我之前写过的zab专栏博客
https://www.jianshu.com/nb/32551354

Ⅷ raft:分布式一致性算法笔记

在开始下一部分内容之前，可以先玩下 raft演基谈示 ，不过后面第三章的图文解析将用更详细的演示图。

在开始之前，先介绍一个 模拟raft的工具 ,如下图：

这部分内容，会根据不同场景解释第二章中的规则；

场景1：所有节点都正常

场景2：leader节点宕机，剩下4个节点参与选举
四节点选举时，存在两种情况（1、一个候选者获取多数选票，2、两个候选者各获得一半选票），不过这里合并一起讲。

场景3：宕机节点重启，并很快到达选举超时计时
这种情况实际包含了s4正常重新加入集群的情况，只不过前面多了一点插曲

场景4：某个follower节点在某段时间因为网络问题无法收到leader的心跳请求，在这段时间内成为candidate，在发送vote请求时，网络又恢复正常

以上均是不含日志情况下的选举（日志条数一样的情况类似），下面将分析日志条数不一样的场景

首先先模拟场景（这个模拟也是模拟脑裂的场景，只不过这个模拟工具无法实现网络阻隔，但是这难不倒我们，我们可以分步来）

当candidate和follower日志不同的时候，选举情况看似复杂，其实是归结起来就两句话：日志里最后一个log entry的term更大的日志更加新，如果这个term相等，那么最后个log entry 的index更大的日志更新。

场景1、leader固定一个，新增日志顺序复制

场景2、在leader复制完日志收到大多数确认之后，发生网络问题，leader切到其他节点。

那么 往期的多数复制的日志什么时候提交 呢？请看下图：

这里就演示了，即便大多数复制的内容也可能被覆盖。如果在步骤（9）中s1在完成多数节点复制后提交了往期的日志并执行到状态机，但是还没将提交状态同步到其他节点，或者已经同步了状态。此时S5发起的vote请求依然能悉戚成为leader，顺利搏陆碰完成（9）之后的流程，这样就覆盖了已提交的log,与状态机的状态不一致了。
那为什么当期提交就没问题呢？
当期的leader能保证提交当期的日志时最新的，往期的日志leader不能保证是最新的 （比如s5的第四个log entry才是整个集群最新的日志记录）。

那么只有在多数复制后，又有新的当期日志（肯定是所有节点中最新的）提交，才能顺带往往期的一起提交：

3、leader的完整性（Leader Completeness Properties）验证
论文中对leader的完整性（Leader Completeness Properties）用了一个很啰嗦的反证。其实就是只要是leader能确认提交的日志肯定是多数复制了，且当前任期号的日志肯定是最新的日志，那么下一任期选举，一定会有包含该条最新日志的节点参与选举才能有节点得到多数选票，且一定是包含最新日志的节点得到多数选票。

后面的成员配置边和日志压缩等就先不玩了。。。

参考：
http://thesecretlivesofdata.com/raft/
https://raft.github.io/raftscope/index.html
https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md#51-raft-%E5%9F%BA%E7%A1%80
https://zhuanlan.hu.com/p/32052223
https://www.cnblogs.com/xybaby/p/10124083.html
https://blog.csdn.net/ppvqq/article/details/78572898

Ⅸ 一致性哈希算法怎么保证数据的一致性

一致性哈希（Consistent Hashing）和数据一致性没有任何关系，这是个关键的理解错误。
一致性哈希只是保证在分布式结构下，哈希结果不会因为某个 node 挂掉而使得所有的键都不能用。在你的图里面，如果 node2 挂掉了，且没有什么自动错误恢复机制存在的话，读写 node2 的键会失败而不是自动落到 node4 上面，所以不存在数据是否一致的问题

Ⅹ Paxos、Raft、ZAB、Gossip 分布式一致性算法理解

以下各种工程实现都缓猜是一个在CAP之间tradeoff的过程

采用zab算法，满足写强一致性（过半圆哪伏节点），读最终一致性（所有节点）

采用租约机制确保并发写入的顺序性和采用hflush机制实现文件的最小副本可见性，满足写强一致性（满足hfds最小副本数，其它副本hdfs自动异步同步），读最终一致性（所有副本），实现弱分区容错性

kafka 读写都在leader上，配合acks=all，实现了读写强一致性，ISR机制确保了高可用性，副本机制实现了分区容错性

hbase读写rowkey都在特定region上，实现读写强一致性，弱高可用性（region存在单点故障），分区容错性hdfs来实现

redis3.0实现Redis-Cluster，采用Gossip协议进行redis元数据广播，实现了元数据读写最终橘携一致性，并且采用shard-master和shard-slave机制实现高可用性，分区容错性
在分布式系统中，需要提供维护节点元数据信息的机制，所谓元数据是指节点负责哪些数据、主从属性、是否出现故障等状态信息。常见的元数据维护方式分为集中式和无中心式。Redis Cluster 采用 Gossip 协议实现了无中心式。

实现原理同redis-cluster，实现了读写最终一致性，高可用和分区容错性

NameNode与JournalNode Cluster进行数据读写时核心点是需要大多数JN成功返回才可认为本次请求有效
在JournalNode Cluster中所有JN之间完全对等，不存在Primary/Secondary区别，实现原理类似paxos
QJM机制实现的是最终一致性

参考
https://blog.51cto.com/u_15220153/3175592