数据一致性算法

① 同时写文件和数据库，如何保证数据一致性

1.计算文件 md5 ；
2.记日志（比如某张表中插入一条记录包含 md5, filepath ；或者日志文件 -> md5 为文件名，内容 filepath ）；

----优化

思考：
考虑到zookeeper的数据庆差一致性原理，有个机制是3PC， paxos算法
leader 选誉睁皮举，server 接受leader 的 事务请求，给予响应，leader 接收到大多数的成功响应，再次给server发送事物提交请求，同时告诉client,事物ok

这是对多节点的一个事物操作，而题目是对单节点的一个事物的操作，事物分早誉为多个步骤。

② 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

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

环割法（一致性 hash）环割法的原理如下：

1. 初始化的时候生成分片数量 X × 环割数量 N 的固定方式编号的字符串，例如 SHARD-1-NODE-1，并计算所有 X×N 个字符串的所有 hash 值。

2. 将所有计算出来的 hash 值放到一个排序的 Map 中，并将其中的所有元素进行排序。

3. 输入字符串的时候计算输入字符串的 hash 值，查看 hash 值介于哪两个元素之间，取小于 hash 值的那个元素对应的分片为数据的分片。

数据比较

下面将通过测试对环割法和跳跃法的性能及均衡性进行对比，说明 DBLE 为何使用跳跃法代替了环割法。

• 数据源：现场数据 350595 条

• 测试经过：

  1. 通过各自的测试方法执行对于测试数据的分片任务。

  2. 测试方法：记录分片结果的方差；记录从开始分片至分片结束的时间；记录分片结果与平均数的最大差值。

  3. 由于在求模法 PartitionByString 的方法中要求分片的数量是 1024 的因数，所以测试过程只能使用 2 的指数形式进行测试，并在 PartitionByString 方法进行测试的时候不对于 MAC 地址进行截断，取全量长度进行测试。

④ 共识算法：Raft

上篇讲到了“拜占庭将军问题”：多个拜占庭将军要如何在可能有叛徒、信使可能被策反或者暗杀的情况下达成是否要进攻的一致性决定？还不了解的先看看上一篇 《拜占庭将军问题》 。这篇主要是介绍简化版拜占庭将军问题的解决方案：Raft 共识算法。

所以将拜占庭将军问题根据常见的工作上的问题进行简化： 假设将军中没有叛军，信使的信息可靠但有可能被暗杀的情况下，将军们如何达成一致性决定？

对于这个简化后的问题，有许多解决方空迹案，第一个被证明的共识算法是 Paxos，由拜占庭将军问题的作者 Leslie Lamport 在1990年提出，最初以论文难懂而出名，后来这哥们在2001重新发了一篇简单版的论文 Paxos Made Simple ，然而还是挺难懂的。

因为 Paxos 难懂，难实现，所以斯坦福大学的教授在2014年发表了新的分布式协议 Raft。与 Paxos 相比，Raft 有着基本相同运行则升效率，但是更容易理解，也更容易被用在系统开发上。

我们还是用拜占庭将军的例子来帮助理解 Raft。

Raft 的解决方案大概可以理解成 先在所有将军中选出一个大将军，所有的决定由大孙亏老将军来做。 选举环节 ：比如说现在一共有3个将军 A, B, C，每个将军都有一个 随机时间 的倒计时器，倒计时一结束，这个将军就会把自己当成大将军候选人，然后派信使去问其他几个将军，能不能选我为总将军？假设现在将军A倒计时结束了，他派信使传递选举投票的信息给将军B和C，如果将军B和C还没把自己当成候选人（倒计时还没有结束），并且没有把选举票投给其他，他们把票投给将军A，信使在回到将军A时，将军A知道自己收到了足够的票数，成为了大将军。在这之后，是否要进攻就由大将军决定，然后派信使去通知另外两个将军，如果在一段时间后还没有收到回复（可能信使被暗杀），那就再重派一个信使，直到收到回复。

故事先讲到这里，希望不做技术方面的朋友可以大概能理解 Raft 的原理，下面从比较技术的角度讲讲 Raft 的原理。

从拜占庭将军的故事映射到分布式系统上，每个将军相当于一个分布式网络节点，每个节点有 三种状态：Follower，Candidate，Leader ，状态之间是互相转换的，可以参考下图，具体的后面说。

每个节点上都有一个倒计时器 (Election Timeout)，时间随机在 150ms 到 300ms 之间。有几种情况会重设 Timeout：

在 Raft 运行过程中，最主要进行两个活动：

假设现在有如图5个节点，5个节点一开始的状态都是 Follower。

在一个节点倒计时结束 (Timeout) 后，这个节点的状态变成 Candidate 开始选举，它给其他几个节点发送选举请求 (RequestVote)

其他四个节点都返回成功，这个节点的状态由 Candidate 变成了 Leader，并在每个一小段时间后，就给所有的 Follower 发送一个 Heartbeat 以保持所有节点的状态，Follower 收到 Leader 的 Heartbeat 后重设 Timeout。

这是最简单的选主情况， 只要有超过一半的节点投支持票了，Candidate 才会被选举为 Leader ，5个节点的情况下，3个节点 (包括 Candidate 本身) 投了支持就行。

一开始已经有一个 Leader，所有节点正常运行。

Leader 出故障挂掉了，其他四个 Follower 将进行重新选主。

4个节点的选主过程和5个节点的类似，在选出一个新的 Leader 后，原来的 Leader 恢复了又重新加入了，这个时候怎么处理？在 Raft 里，第几轮选举是有记录的，重新加入的 Leader 是第一轮选举 (Term 1) 选出来的，而现在的 Leader 则是 Term 2，所有原来的 Leader 会自觉降级为 Follower

假设一开始有4个节点，都还是 Follower。

有两个 Follower 同时 Timeout，都变成了 Candidate 开始选举，分别给一个 Follower 发送了投票请求。

两个 Follower 分别返回了ok，这时两个 Candidate 都只有2票，要3票才能被选成 Leader。

两个 Candidate 会分别给另外一个还没有给自己投票的 Follower 发送投票请求。

但是因为 Follower 在这一轮选举中，都已经投完票了，所以都拒绝了他们的请求。所以在 Term 2 没有 Leader 被选出来。

这时，两个节点的状态是 Candidate，两个是 Follower，但是他们的倒计时器仍然在运行，最先 Timeout 的那个节点会进行发起新一轮 Term 3 的投票。

两个 Follower 在 Term 3 还没投过票，所以返回 OK，这时 Candidate 一共有三票，被选为了 Leader。

如果 Leader Heartbeat 的时间晚于另外一个 Candidate timeout 的时间，另外一个 Candidate 仍然会发送选举请求。

两个 Follower 已经投完票了，拒绝了这个 Candidate 的投票请求。

Leader 进行 Heartbeat， Candidate 收到后状态自动转为 Follower，完成选主。

以上是 Raft 最重要活动之一选主的介绍，以及在不同情况下如何进行选主。
总结：
1.每个节点一直有一个timeout，timeout结束就开始选自己为主节点；
2.主节点会轮询从节点，从节点更新timeout；
3.选举等级机制；

Raft 在实际应用场景中的一致性更多的是体现在不同节点之间的数据一致性，客户端发送请求到任何一个节点都能收到一致的返回，当一个节点出故障后，其他节点仍然能以已有的数据正常进行。在选主之后的复制日志就是为了达到这个目的。

一开始，Leader 和 两个 Follower 都没有任何数据。

客户端发送请求给 Leader，储存数据 “sally”，Leader 先将数据写在本地日志，这时候数据还是 Uncommitted (还没最终确认，红色表示)

Leader 给两个 Follower 发送 AppendEntries 请求，数据在 Follower 上没有冲突，则将数据暂时写在本地日志，Follower 的数据也还是 Uncommitted。

Follower 将数据写到本地后，返回 OK。Leader 收到后成功返回， 只要收到的成功的返回数量超过半数 (包含Leader) ，Leader 将数据 “sally” 的状态改成 Committed。( 这个时候 Leader 就可以返回给客户端了)

Leader 再次给 Follower 发送 AppendEntries 请求，收到请求后，Follower 将本地日志里 Uncommitted 数据改成 Committed。这样就完成了一整个复制日志的过程，三个节点的数据是一致的，

在 Network Partition 的情况下，部分节点之间没办法互相通信，Raft 也能保证在这种情况下数据的一致性。

一开始有 5 个节点处于同一网络状态下。

Network Partition 将节点分成两边，一边有两个节点，一边三个节点。

两个节点这边已经有 Leader 了，来自客户端的数据 “bob” 通过 Leader 同步到 Follower。

因为只有两个节点，少于3个节点，所以 “bob” 的状态仍是 Uncommitted。所以在这里， 服务器会返回错误给客户端

另外一个 Partition 有三个节点，进行重新选主。客户端数据 “tom” 发到新的 Leader，通过和上节网络状态下相似的过程，同步到另外两个 Follower。

因为这个 Partition 有3个节点，超过半数，所以数据 “tom” 都 Commit 了。

网络状态恢复，5个节点再次处于同一个网络状态下。但是这里出现了数据冲突 “bob" 和 “tom"

三个节点的 Leader 广播 AppendEntries

两个节点 Partition 的 Leader 自动降级为 Follower，因为这个 Partition 的数据 “bob” 没有 Commit，返回给客户端的是错误，客户端知道请求没有成功，所以 Follower 在收到 AppendEntries 请求时，可以把 “bob“ 删除，然后同步 ”tom”，通过这么一个过程，就完成了在 Network Partition 情况下的复制日志，保证了数据的一致性。

Raft 是能够实现分布式系统强一致性的算法，每个系统节点有三种状态 Follower，Candidate，Leader。实现 Raft 算法两个最重要的事是：选主和复制日志

参考链接：
Raft 官网： https://raft.github.io/

Raft 原理动画 (推荐看看)： http://thesecretlivesofdata.com/raft/

⑤ 一致性hash算法是什么

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

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

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

构成哈希算法的条件：

从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）。

对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同。

散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小。

哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。

⑥ 一致性算法（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实现。点击下载

⑧ (3)一致性哈希vs哈希取模算法

大数字取模 分散不同桶，两个桶， 2、3、4、5 ，模 2 分桶：

扩容 新桶 ，模 3 来结果：

每次扩展 和 收缩 所有条目分布 重新计算 ，某些场景不可接受。文件 分布 在哪台 哈希算法 决定 ，这个系统想要 加 一台机器时就需要 停 下来等所有文件 重新分布一次 才能对外提供服务，一台机器掉线尽管 只掉一部分数据 ，所有数据访问路由 都会出问题 。 无法平滑的扩缩容 。

无状态化 ，用多瞎轮个桶，  模 7个 ，开始只有两个 3 和 6。同样取模，分到不存在的桶，往下找第一个真实存桶。 2 和 3 分3 桶， 4 和 5分 6 桶。

添加新  编号4桶， 还是模 7 ：

3 号桶取模 小于等于 3 ，4 号桶只需从 6 号桶 拿走属于它数字就可， 只调整一个桶重新分布 。即使有 1 亿个桶，增加减少一个桶也只会影响一个桶的数据分布。

只需 和后面机器同步 数据 就可工作 ，同步到后一台机器再下线。 实现中 可以让每台机器 同步一份自己前面机器的数据 ，即使 掉线也不影响 这部分数据服务。

问题：编号  6 的机桶下线 了， 没有后一个桶了 ，哈希空间做成 环状 ， 数据给 3  ：

一致性哈希还能 实现部分 的分布式系统 无锁化 ， 算法的确定性 ，分到哪个桶也是确定的就 不存在争抢 ， 不需要分布式锁 了。

查找效率：普通的哈希 查询 一次 哈希计算就可以找到对应的桶了  O(1) ，一致性哈希需要将 排好序 的 桶组成 一个 链表 ，一路找下去k 个桶  O(k)

O(k) 对于哈希来说 不能忍 ，这个量级了用哈希没意义，在排好序桶里查询， 二分 把时间复杂度降到 O(logk) ，桶组合需不断增减，链表实现二分肯定不行，用 跳转表快速跳转 也能 实现 O(logk) 

跳转表中， 每个桶记录距离自己 1，2，4 距离的数字所存的桶，不管查询落在哪个节点上，对整个哈希环上任意的查询一次都 可以至少跳过一半的查询空间？ ，这样递归下去很快就可以定位到数据是存在哪个桶上。

上面只是 一种 ，很多一致性哈希 变体 。如选桶：上面顺着数字选 对面 出现 第一个桶 ，其实也可选距离 数字最近桶 ，这样跳转表规则也变。同样跳转表不同算法实现：  CAN，Chord，Tapestry，Pastry 这四种 DHT  

1、如果 6号 (里面有数据)桶突然 宕机 了，是不是里面的数据也丢失了？来不及将桶里的数据往前一个桶移？

答：实际情况会做冗余，画的是一个桶， 实际可能是三个

2、 “一致性” 是扩缩容前后数据在桶里的 分布是一致 的

3、 分布式 系统中怎么 实现服务间的事务 ，目前有哪些通用做法，比如bbo?

用zk或者etcd这种分布式 锁 服务，让接口是 幂等， 可以反复重试

4、增加此类操作会 拖慢集群的性能 。如果某节点上一刻 宕机 ，往后新尺唯数据会进入 下一个节点 ，宕机节点 恢复 ，下一个节点还要同步原属宕机的数据，复杂度为O(nlogn)，会不会代价略高？开源的ketama没有同步数据这一做法，所以本质上只是近似一致性哈希，是不是一个trade-off的选择？

答：这个场景不适合使用一致性哈希吧。以 负载均衡 为例，理论上是认为后台服务器是 无状态 的吧。所以宕机重启 不应该有数据同步 的问题。

处理数据同步，raft强一致方案

对磨困信hash结果取余数 (hash() mod N)：机器编号从 0到N-1 ，hash()值 按N取模 ， 余数i，分发到编号i机器 。致命问题，宕机，落在该机器请求无法处理，有 (N-1)/N 服务器的缓存数据重新计算；为何是 (N-1)/N 呢：3 台机器，hash值 1-6 分布：

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。

N个真实 节点,每个映射成 M个虚拟节 点, M*N个虚拟节点散列在圆环上. 真虚相互交错分布，真down后,平均分到所有节点

访问方法：

写入缓存请求，Key值为K，计算器hash值Hash(K)， Hash(K) 对应于环中的某一个点，没有映射到机器节点，顺时针查找，直到找到有映射机器的节点，确定目标节点，超过2^32找不到，命中第一个。

缺陷：server数量很少时，环中分布不均匀，导致cache到server不均匀

例：用电话号码group by，如移动用户多，就会倾斜，reverse或加随机数解决

hash取模对模数有要求，用奇数不用偶数，数据量大的时模数不好选，用上面办法。

https://zhuanlan.hu.com/p/24440059

https://blog.csdn.net/hunandexingkong/article/details/70241933

⑨ paxos算法是什么

Paxos算法是莱斯利·兰伯特（Leslie Lamport，就是LaTeX中的＂La"，此人现在在微软研究院）于1990年提出的一种基于消息传递的一致性算法。这个算法被认为是类似算法中最有效的。

兰伯特提出的Paxos算法包含2个部分：

一个是Basic Paxos算法，描述的是多节点之间如何就某个值（提案Value）达成共识；

另一个是Multi-Paxos思想，描述的是执行多个Basic Paxos实例，就一系列值达成共识

可因为兰伯特提到的Multi-Paxos思想，缺少代码实现的必要细节（比如怎么选举领导者），所以在理解上比较难。Basic Paxos是Multi-Paxos思想的核心。

(9)数据一致性算法扩展阅读

背景

Paxos算法解决的问题是一个分布式系统如何就某个值（决议）达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点执行相同的操作序列，那么他们最后能得到一个一致的状态。

为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。

一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。因此从20世纪80年代起对于一致性算法的研究就没有停止过。节点通信存在两种模型：共享内存（Shared memory）和消息传递（Messages passing）。Paxos算法就是一种基于消息传递模型的一致性算法。