[TOC]

分布式理论

一个分布式系统最多只能满足 C、A、P 这三项中的两项。

CAP理论

C：Consistency，一致性，数据状态转化一致，写操作完成后的读操作，可以获取到最新的值；
A：Availability，可用性，指的是服务一直可用，可以正常响应，或者在规定时间内可以获取到响应；
P：Partition tolerance，分区容错，指的是当有节点故障不连通时(比如网络出问题)，就会分区，但仍然能对外提供服务；

矛盾在于这三个特性不能同时满足，比如

当分布式集群内有两个主从服务发生网络故障，但此时服务仍然可以访问，此时具有分区容错性。

当对主服务对数据进行修改时，由于网络问题，无法同步到从服务，当访问到从服务时，无法获取到最新的值，此时满足可用性，但是无法满足一致性。

当主从服务间网络恢复，写操作的数据虽然能在服务间同步了，但还未同步完成，此时访问从服务无法获取最新值，此时满足了一致性，但是无法满足可用性。

简单概括，只要满足分区容错，就会设置复制集，复制集同时也保证了可用，但是复制集又会有数据同步，此时又有一致性问题

所以，一般只会满足其中两个

1、满足CA舍弃P，也就是满足一致性和可用性，舍弃容错性。但是这也就意味着你的系统不是分布式的了，因为涉及分布式的想法就是把功能分开，部署到不同的机器上，而且如果出现了分区错误，必定会导致部分功能不可用，此时也无法满足A，所以 P 其实是必然存在的，只有单机是CA。

2、满足CP舍弃A，也就是满足一致性和容错性，舍弃可用性。如果你的系统允许有段时间的访问失效等问题，这个是可以满足的。就好比多个人并发买票，后台网络出现故障，你买的时候系统就崩溃了。真正的强一致性在做同步的过程中会阻塞所有请求，导致性能会特别差，此时可用性就降低了，所以像ZooKeeper这种允许同步到一半节点以上就算成功的，不算是真正的强一致性。

3、满足AP舍弃C，也就是满足可用性和容错性，舍弃一致性。这也就是意味着你的系统在并发访问的时候可能会出现数据不一致的情况。

所以为了分布式服务能正常使用，一般时会满足分区容错性和可用性，在一致性上不追求强一致性，而是一个逐渐一致的过程。

BASE理论

BASE理论是对CAP三者均衡的结果，基于CAP理论演化而来，通过牺牲强一致性来获得高可用。

Basically Available（基本可用）: 允许暂时不可用，比如访问时可以等待返回，服务降级，保证核心可用等。
Soft state（软状态）: 允许系统存在中间状态，而该中间状态不会影响系统整体可用性，比如允许复制集副本间的数据存在延时，数据库的数据同步过程。
Eventually consistent（最终一致性）: 系统中的所有数据副本经过一定时间后，最终能够达到一致的状态。

与数据库ACID类似，只是强度减弱了

参考：CAP 定理的含义

关于可靠性、可用性、稳定性

可靠性Reliability：不出事故，故障率低，关注的是系统无故障地持续运行的概率，比如
- MTBF（Mean Time Between Failure）：即平均无故障时间，是指从新的产品在规定的工作环境条件下开始工作到出现第一个故障的时间的平均值。MTBF越长表示可靠性越高，正确工作能力越强。
- MTTR（Mean Time To Repair）：即平均修复时间，是指可修复产品的平均修复时间，就是从出现故障到修复中间的这段时间。MTTR越短表示易恢复性越好。
- MTTF（Mean Time To Failure）：即平均失效时间。系统平均能够正常运行多长时间，才发生一次故障。系统的可靠性越高，平均无故障时间越长。
与可用性的关系：Availability = UpTime/(UpTime+DownTime) = MTBF / (MTBF + MTTR)

可用性Availability：不出事故，如果出事故可以快速恢复，关注的是服务运行持续时间，比如

通俗叫法	可用性级别	年度宕机时间	周宕机时间	每天宕机时间
1个9	90%	36.5天	16.8小时	2.4小时
2个9	99%	87.6小时	1.68小时	14分钟
3个9	99.9%	8.76小时	10.1分钟	86秒
4个9	99.99%	52.6分钟	1.01分钟	8.6秒
5个9	99.999%	5.26分钟，315.36秒	6.05秒	0.86秒

稳定性Stability：服务性能稳定，不时快时慢，关注的是在一个运行周期内，一定压力下，持续操作时间内的出错概率，性能优劣等

分布式事务

一、2PC

二阶段提交其实就是实现XA分布式事务的关键

需要有协调者和参与者，协调者负责调度，参与者负责执行，分两步完成，1：prepare阶段 2：commit阶段。

2PC是强一致性的，保证原子性和隔离性。在执行阶段，节点是处于阻塞状态，直到commit阶段完成，本地事务才会释放资源，因此性能不佳，一般用在强一致性、并发量不大的场景。

正常情况下

prepare阶段：协调者向参与者A、B发送请求执行操作，参与者A、B开启事务，执行操作，但不commit，操作完成后，告诉协调者已经完成。

commit阶段：协调者收到参与者的完成响应，向参与者A、B发送commit请求，参与者A、B收到commit请求后，提交事务，完成操作；如果收到执行失败的响应，则发送回滚请求给参与者A、B，执行回滚。

异常情况下

在协调者等待参与者的完成响应时，协调者或参与者可能宕机，最终会导致数据不一致或阻塞，例如

场景：prepare阶段，协调者正常，参与者宕机，参与者没有收到询问请求，或者协调者没有收到参与者的回应

解决办法：协调者做超时处理，一旦超时，当作失败，向所有节点发送事务终止请求，或者发送重试请求；
场景：commit阶段，正式提交发出后，如果有的参与者没有收到，或者参与者提交/回滚的确认信息没有返回，即参与者的回应超时

解决方法：协调者或者参与者进行重试，或者把参与者标记为问题节点移除集群后回滚
场景：当处于commit阶段时，协调者挂掉或重启，会导致协调者收不到参与者的响应，此时协调者就不清楚commit阶段要发送什么请求过去，或者就不发请求过去了，导致参与者一直阻塞

解决办法：协调者维护一份事务日志，以方便宕机重启后恢复原来的状态，比如重新向参与者查询结果，但无法为参与者设置超时自动操作，因为它并不知道commit阶段自己要进行commit还是回滚
场景：当处于commit阶段时，参与者挂掉后，接收不到协调者的请求，不知道接下来要执行commit还是回滚，协调者也无法在参与者挂掉后进行回滚操作，因为也不知道参与者事务是否已经处理了

解决办法：不断重试，或者 3pc

缺点

性能问题，参与者和协调者需要互相等待，只有当所有节点准备完毕，协调者才会进行全局提交，参与者进行本地事务后才会释放资源，阻塞时间长；
单点故障，协调者一旦发生故障，参与者会一直阻塞；
数据一致性问题，在commit阶段，如果一部分参与者收到提交请求，一部分收不到，此时数据不一致；

二、3PC

3PC实际上就是将prepare阶段拆成两步，preCommit相当于一次保险阶段，作用类似于2PC的二阶段，但是它不是真正的提交。2PC只有协调者超时机制，参与者严重依赖协调者，而3PC引入了参与者超时的机制，使得参与者不用太过依赖协调者，自己有一定的处理权限，解决2PC在commit阶段，协调者在不能处理请求时，参与者一直阻塞的问题，3PC只是缓解了2PC阻塞时间过长的问题，本身也没有完全解决数据不一致的问题；

正常情况下

canCommit阶段：协调者向所有参与者发送请求，参与者开启事务执行操作，将结果返回给协调者，成功完成后响应Yes，进入下一阶段，否则响应No，结束。

preCommit阶段：协调者收到所有参与者的Yes响应，进行本地事务，记录日志，然后发送处理结果的请求给所有参与者，告诉所有参与者进行预提交状态。

如果参与者能收到PreCommit请求，意味着它知道大家都同意提交了，即使在commit阶段出现问题，参与者也可以在超时之后进行事务提交。

commit阶段：协调者收到所有参与者的应答响应，向所有参与者发送commit请求，参与者收到后提交事务，如果协调者发现部分参与者无法执行事务，则向所有参与者发生rollback请求，回滚事务。

异常情况下

如果在preCommit阶段到commit阶段之间，协调者挂了，参与者会在超时后进行事务提交，如果协调者的本意是要rollback，则会产生数据不一致的情况。

三、TCC

补偿事务，每一个操作都要有对应的确认和补偿，类似于2pc，但2pc在于DB层面，TCC在于业务层面，每个业务逻辑都需要实现try-confirm-cancel的操作。

Try阶段：对于操作的数据行，增加字段表示其状态，表示正在操作，预留必须的资源；

Confirm阶段：只操作预留资源，将try阶段中表示数据状态的字段修改为确认状态，表示已经完成操作，操作需要幂等；

Cancel阶段：将try阶段进行的操作进行回滚，操作需要幂等；

通过不断重试，并发的时候还是需要分布式锁，TCC主要是保证业务逻辑的完整性。

比如，在订单创建并减库存的场景中，

Try阶段：订单创建时发出订单创建的事件，此时订单状态是创建中，库存服务接收到后，并不是直接减库存，而是先冻结库存，将要扣减的库存数冻结起来，订单创建完成；

Confirm阶段：订单支付完成后，发出订单支付完成的事件，库存服务接收到后，才是真正的减库存

Cancel阶段：如果在Try阶段出错，则对已执行Try请求的服务执行回滚，对库存进行回滚

TCC可能存在的问题

因为重试的存在，confirm和cancel需要保证幂等，可以使用事务记录表 + 状态来实现，confirm和cancel只有在存在事务记录，且状态为try时才能执行；
try时，需要上锁保证并发安全，之后confirm和cancel就可以不用加锁直接完成，因为try时已经保证了数据的一致性；
空回滚：可能网络或者其他原因，导致参与者cancel早于try之前被接收到（confirm则不会，因为confirm必定是try执行成果之后才会出现），此时可能产生空回滚，同样也可以使用事务记录表 + 状态来保证cancel时可以识别出是否已经执行过try操作；
悬挂：可能因为网络超时等原因，参与者先cancel了，此时事务已经被判定结束，然后才接收到try，导致事务阶段一直处于try阶段，造成资源悬挂，同样也可以使用事务记录表 + 状态来解决，保证已结束的事务不会执行try操作；

四、本地消息表

适合解决分布式最终一致性问题。

事务性消息：本地事务和发送消息是原子性操作；

正常情况下

参与者A正常进行数据库事务并提交，将涉及到对参与者B的操作记录到本地消息表中，相当于一条日志，然后再用一个异步服务，读取该条日志，控制参与者B进行相关操作，完成之后更新这条本地消息的状态。

异步消费操作可以利用RocketMQ事务；

注意：参与者A的数据库操作与日志记录是一个原子性操作。

异常情况下

如果失败了直接重试即可，保证参与者A与B数据最终一致性。

消费者在处理的时候要保证幂等。

https://www.jianshu.com/p/53324ea2df92

http://blog.itpub.net/31556438/viewspace-2649246/

五、SAGA

利用状态机实现，它将一系列分布式操作转化成一系列的本地事务，在每一个本地事务中我们都会更新数据库并且向集群中的其他服务发送一条新的消息来触发下一个本地事务；一旦本地事务因违法业务逻辑而失败，那就会立即触发一系列回滚操作来撤回之前本地事务造成的副作用。

SAGA分为协同和编排两种模式，协同是非中心化的，通过各个服务的本地事务触发下一个服务的本地事务来实现；编排是通过一个中心化的协调节点，来追踪所有子任务的调用情况，根据任务的调用情况来决定调用对应的补偿方案，并在网络请求出现超时时进行重试；

六、简单通过可靠消息和最终一致性方案实现

另外，在可靠消息服务中，更新数据库里的消息和将消息发送给MQ这一个步骤必须保证原子。

一般可靠消息服务可以和MQ一起组合，待确认消息算半消息，其实这种实现就是RocketMQ

注意点：

上游服务给可靠消息服务发送待确认消息的过程中出现问题，此时上游服务可以感知调用异常，就可以直接不执行之后的流程了。
上游服务操作完本地数据库后，通知可靠消息服务确认消息或删除消息时出现问题，此时该消息在可靠消息服务里是待确认状态，在可靠消息服务里定时轮询待确认状态的消息，调用上游服务的接口判断这个消息的状态即可；

如果上游响应该消息成功，可靠消息服务将消息投递到MQ即可，否则，将该消息删除。

像RocketMQ就把这个操作做进了MQ里，这种待确认的消息就叫半消息。

下游服务一直消费消息一直失败，有两种方案：

 1. 可以设置消息可被消费的次数，超过这个次数进死信队列，后面人工干预即可；
 2. 由于该条消息在可靠消息服务里一直是已发送状态，始终未完成，此时可靠消息服务在后台可以有定时任务，将这些消息重新丢到MQ里让下游消费即可，当然下游服务消息是需要保证幂等的；

参考：

http://www.ruanyifeng.com/blog/2018/07/cap.html

https://www.cnblogs.com/jajian/p/10014145.html

https://www.jianshu.com/p/f98e8a8dae6d

分布式算法

为了避免单点故障，常见的多副本复制方案有两种：

去中心化复制，如Gossip

一个n个复制集节点的集群中，任意节点都可以接收写请求，但一个成功的写请求需要w个节点确认，读操作也必须查询至少r个节点。可用性高，但容易造成写冲突。

简单来讲，就是一个节点会周期、随机的将事件广播给其他节点，其他节点收到后也会周期性的广播给其他节点，最终集群上所有节点都能收到消息，是一种去中心化，最终一致性的算法，压力不在来自主节点，而是所有节点都均衡负载，扩展性很好，即使有新节点加入，最终也会被广播到。

当会有个拜占庭问题，就是如果有一个恶意传播节点，将会打乱原本的传播

除了复制方案，另一种是共识算法如Paxos或Raft，保证集群节点高可用和数据一致性。

主从复制，如MySQL、Redis

全同步复制：主节点收到一个写请求后，必须等到全部从节点确认返回后，才能返回给客户端成功，一个节点故障将导致整个系统不可用。保证一致性，但可用性不高。
异步复制：主节点收到一个写请求，立马返回给客户端，异步将请求转发给各个从节点，但主节点如果还未将请求进行转发就故障了，就会导致数据丢失。保证可用性，但一致性不高。
半同步复制：主节点收到一个写请求后，至少有一个从节点或者超过半数节点收到数据，就可以返回客户端，在一致性和可用性上比较平衡。

Paxos算法

Raft算法

感觉像与ZAB协议类似，具体有时间再整理

当Leader宕机之后，只有拥有最新日志的Follower才有资格称为Leader。

关于日志检查，当Follower上的日志与leader不一致时，Leader先找到Follower同它日志一致的index，将其后边的日志一条条覆盖在Follower上。

参考：Raft算法详解

Raft动画演示

分布式锁

利用数据库唯一约束

在数据库新建一个锁表，然后通过操作该表中的数据来实现，表的字段为客户端ID、加锁次数、资源的key，加锁次数 + 客户端ID可以判断是否可重入。

当我们要锁住某个方法或资源的时候，我们就在该表中增加一条记录，想要释放锁的时候就删除这条记录。在insert前先query判断是否存在该记录。

优点：简单，方便理解，且不需要维护额外的第三方中间件(比如Redis,Zk)。

缺点：虽然容易理解但是实现起来较为繁琐，需要自己考虑锁超时，加事务等等。性能局限于数据库，一般对比缓存来说性能较低。对于高并发的场景并不是很适合。

etcd实现

etcd采用raft算法，一个写请求要经过集群多数节点确认，所以一旦分布式锁申请成功返回给client时，锁数据一定是持久化了集群多数节点上，不会出现Redis那种主备异步复制，当主机宕机，从机和主机数据不一致的情况。

事务功能：etcd事务由IF、THEN、ELSE语句组成，可以比较key的修改版本号mod_revision和创建版本号create_revision，因此可以通过创建版本号create_revision检查key是否已存在，当key不存在时，创建版本号为0，此时可以进行put操作。
Lease 功能：可以保证分布式锁的安全性，为锁对应的 key 配置租约，即使锁的持有者因故障而不能主动释放锁，锁也会因租约到期而自动释放，同时也支持续约。此特性解决了client出现crush故障，client与ectd集群网络出现隔离等场景下的死锁问题。一旦Lease TTL，key就会自动释放，确保其他client在TTL过期后能正常申请锁。
watch功能：在实现分布式锁时，如果抢锁失败，可通过 Prefix 机制返回的 KeyValue 列表获得 Revision 比自己小且相差最小的 key（称为 pre-key），对 pre-key 进行监听，因为只有它释放锁，自己才能获得锁，如果 Watch 到 pre-key 的 DELETE 事件，则说明pre-ke已经释放，自己已经持有锁。
prefix功能：例如，一个名为 /mylock 的锁，两个争抢它的客户端进行写操作，实际写入的 key 分别为：key1=”/mylock/UUID1″，key2=”/mylock/UUID2″，其中，UUID 表示全局唯一的 ID，确保两个 key 的唯一性。很显然，写操作都会成功，但返回的 Revision 不一样，通过前缀 /mylock 查询，返回包含两个 key-value 对的的 KeyValue 列表，同时也包含它们的 Revision，通过 Revision 大小，客户端可以判断自己是否获得锁，如果抢锁失败，则等待锁释放（对应的 key 被删除或者租约过期），然后再判断自己是否可以获得锁。并配合上一条的watch功能使用。
reversion功能：如上一条所述，每个 key 带有一个 Revision 号，每进行一次事务加一，因此它是全局唯一的，如初始值为 0，进行一次 put(key, value)，key 的 Revision 变为 1；同样的操作，再进行一次，Revision 变为 2；换成 key1 进行 put(key1, value) 操作，Revision 将变为 3。多线程获取锁时，通过比较reversion的大小即可知道获取的顺序，避免"惊群效应"（指的是当锁被释放，会导致所有监听该key的client都尝试发起事务获取锁，性能较差）。

实现的方案：通过多个client创建prefix相同，名称不同的key，哪个key的revision最小，谁就获得锁。

etcd自带了concurrency包，简化分布式锁、分布式选举、分布式事务的实现。该包的分布式锁实现：当事务发现createRevision的值为0时，会创建一个prefix为/my-lock的key，key的名称为/my-lock+LeaseId，并获取/my-lock prefix下面最早创建的一个key，即revision最小，分布式锁最终由写入该key的client获得，其他client进入等待模式。未获得锁的client通过Watch机制监听prefix相同，revision比自己小的key，只有当revision比自己小的key释放了锁，才有机会获得锁。

优点：

可以通过lease功能和结点健康监测，确保客户端崩溃时，锁一定会被释放。
etcd客户端etcd有相应锁实现，是否满足需求需要进一步查看源码。

缺点：

强一致性带来的必定是写效率上的降低

ZooKeeper实现

基于ZooKeeper的临时节点和顺序的特性。

临时节点具备数据自动删除功能，当client与ZooKeeper连接和session断掉时，相应的临时节点就会被删除。

另外，ZooKeeper也提供Watch特性监听key的变化。

因为创建节点的唯一性，我们可以让多个客户端同时创建一个临时节点，创建成功的就说明获取到了锁。然后没有获取到锁的客户端也像上面选主的非主节点创建一个 watcher 进行节点状态的监听，如果这个互斥锁被释放了（可能获取锁的客户端宕机了，或者那个客户端主动释放了锁）可以调用回调函数重新获得锁。

共享锁：规定所有创建节点必须有序，当你是读请求（要获取共享锁）的话，如果 没有比自己更小的节点，或比自己小的节点都是读请求 ，则可以获取到读锁，然后就可以开始读了。若比自己小的节点中有写请求 ，则当前客户端无法获取到读锁，只能等待前面的写请求完成

排他锁：如果你是写请求（获取独占锁），若 没有比自己更小的节点 ，则表示当前客户端可以直接获取到写锁，对数据进行修改。若发现 有比自己更小的节点，无论是读操作还是写操作，当前客户端都无法获取到写锁 ，等待所有前面的操作完成

Redis实现

单机Redis实现

使用setnx命令，setnx命令表示如果key不存在，则可以set成功，返回1，否则返回0，根据返回值来判断是否加锁成功，注意setnx不支持设置key、value的同时还要设置过期时间，过期时间主要是保证资源占用时间过长后可以释放锁，避免死锁，所以如果要用来加锁，必须使用Lua脚本来保证原子性

1
2
3
4
5


if redis.call('setnx', KEYS[1], KEYS[2]) == 1 then
  redis.call('expire', KEYS[1], KEYS[3])
end

return ok

不过从2.6.12起，set涵盖了setex、setnx功能，并且set本身可以设置过期时间，因此可以使用以下命令进行加锁

命令：SET [key: 资源代表的key] [value: 客户端事务Id] NX PX [时间，EX的单位是秒，PX的单位是毫秒] ，要注意旧版本的setnx命令不支持设置过期时间

解锁，先判断锁是不是自己加的，如果是才可以解锁，即删除该key，需要保证这两个步骤的原子性，否则可能会出现因为查询时间过长导致删掉了别人的锁

1
2
3
4
5


if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

为了保证Redis的高可用，就会部署Redis集群，但在集群环境下还使用上述方案可能会出现锁偶尔失效。比如Redis设置主从节点，一般加锁解锁会在主节点上进行，但是当加锁后，主节点宕机，从节点还未进行同步，从节点提升为主节点，其他服务就有机会获取到锁了，此时就出现了多个服务对同一资源的操作问题；另外，当发生网络分区现象时，Redis可能出现脑裂，出现多个master，使得多个client可以获得锁。

集群Redis实现

RedLock与Redission实现，有空再进行补充，先把RedLock的基本思想简单描述一下

假设有5个Redis节点，

加锁时，顺序在5个节点上申请锁，使用同样的key、value、超时时间，申请锁的超时时间，因为需要同时请求多个节点，避免加锁时间花费过长
当在3个节点上成功申请到锁，且申请锁消耗的时间小于锁的有效时间，就算申请成功。申请锁消耗的时间采用获得锁的当下时间减去加锁请求时的时间戳得到
锁申请到后，锁的有效时间 = 锁的过期时间 - 申请锁获得的时间
如果申请锁失败了，申请成功锁的节点会执行解锁操作，进行重置

参考：

RedLock算法的争议

分布式自增id

数据库自增id

利用MySQL的自增id来实现，服务在需要用到自增id时，会向MySQL发送请求。通过事务的方式，先增长id再进行查询

优点：简单方便

缺点：性能不是很好，还有一个是可用性问题，如果数据库不可用了，会导致其他服务不可用，如果使用主从方式部署，虽然可靠性提升了，但如果主库挂掉后，从库数据没有及时同步，会出现ID重复

解决：使用双主模式，两个主节点的自增序列错开，比如设置节点A的起始值为1，步长为2，节点B的起始值为2，不出为2。但是这种方案又有一个缺点，那就是扩展性不好，假如两个节点不够用了，第三个节点加入时的起始值和步长不好设置

解决：客户端通过号段的方式来获取自增id，每次从数据库获取时不再是获取一个，而是获取一段范围内的一批id，缓存在本地，减少IO和竞争

分段 + 发号器

参考美团的Leaf方案

Leaf是基于MySQL的分布式ID生成方案，简单总结如下：

Leaf为不同的业务设定一个tag，定义不同的号段长和初始值，每个业务获取ID都相互隔离，互不影响；
Leaf发号时是发给proxy，每次发一个号段，以减少MySQL的写压力，proxy会把获取到的号段做缓存；
有了proxy之后如果要对发号器(Leaf)做扩展，直接扩展proxy，并且多分配一些号段即可，无需变更MySQL；
proxy会在号段内号的数量剩余10%时获取下一批，以避免并发获取时卡顿，还能及时补充号源，不怕DB宕机；

proxy消耗完一个号段后，从DB上更新号段，获取下一个范围的号段；

1
2
3
4


Begin
UPDATE table SET max_id=max_id+step WHERE biz_tag=test_tag
SELECT tag, max_id, step FROM table WHERE biz_tag=test_tag
Commit

另一种方案可参考有赞，总结一下就是：

发号器主备部署，对外只有一个实例提供服务，发号器本身的高可用也是通过etcd来实现；
生成的id存储在etcd，使得发号器本身无状态，利用etcd的cp特性，保证数据的一致性，同时也可以解决数据库主从同步导致的id重复问题；
号的生成有两种方式：全局单调自增、类雪花id 两种方案，生成一批id后缓存到本机内存中，有请求进来就发一个id；
发号器预先生成一批id，异步持久化到etcd，复制到半数乃至全部机器上；如果id消耗速度快于异步持久化速度，此时会阻塞；

利用etcd实现发号器的高可用方案：

March 的高可用是利用 etcd 的 ttl 和 watch 实现的。启动时，先尝试创建一个新的带 ttl 的 Node。如果成功，就成为了主节点；如果由于已存在而失败，就成为了备节点。

主节点

定时用前一次请求返回的 index 刷新 Node 的 ttl，保持自己的主节点角色。发现刷新失败时，说明主节点角色已经被抢走，从抢主节点过程重新开始。与此同时，还会等待 demote 请求。收到 demote 请求时，会等待新的主节点信息，然后将自己置为备节点。

备节点

先查询主节点的信息。在备节点收到发号请求时，会按 Redis Cluster 协议重定向到主节点。之后就开始 Watch Node 的变化。检测到变化后，也开始抢主节点过程。

这样，可以做到在主节点发生故障时，最多等待一个 ttl 就能检测到，并完成切换。而在主动切换时，结合客户端，可以做到完全无损，只有毫秒级的阻塞。

此外，每个节点都会存保存各自的带 ttl 的节点信息，同时定时刷新，用于返回给客户端集群信息。每个发号器在每次持久化时，也会携带上上一次持久化获得的 index。一旦不匹配出错，也会将自身重置为备节点。这可以避免网络堵塞或进程僵死造成原主失效而自身却不知道。在发生非预期错误时，HA goroutine 会等待 2 * ttl，以免不断出错造成死循环。此外，备节点也需要能够完成用户认证。但因为认证是不能重定向的，所以还需要检测 etcd 上的用户信息变化，重新同步用户数据。

雪花算法

分布式ID固定是一个long类型的数字，占64位，通过一定的规则编排这64位来实现

-------------------------------------------------------------------
|  bit   | 66 |           65 ~ 24        |  23 ~ 13  |   12 ~ 1   |
| length | 1  |             41           |    10     |     12     |
|  part  |none|         timestamp        |  machine  |  sequence  |
-------------------------------------------------------------------
41位的时间戳可以使用69年，41位的时间戳是精确到毫秒级别的
12位的序列号可以让同一个节点一毫秒内生产4096个ID

一般可以自己调整时间戳、机器id、序列号的位数来控制ID的并发量、使用年限等，满足不同的场景，机器ID可以自己配置在节点上、配置中心、数据库。

优点：简单方便，整型易操作，有需要还可以将整型进行进制转化，转成字符串类型的id

缺点：因为使用到了时间，如果节点上的时钟回拨，会导致ID重复；如果服务部署在docker内，获取时间和机器id要注意；由于机器不同，生成的id是自增的，但是不一定连续；而且还有个问题，前端js是没有long类型的，整型最多支持53位，所以如果返回给前端还要做一次转化。

可以允许 sequence 段溢出，溢出的部分会加到 timestamp 段上去，这样即使在时间戳精度范围内 sequence 耗尽了，也不用阻塞请求，同时也确保即使机器时钟回拨导致的id重复，但这种有个坏处是无法通过id解析出正确的时间戳。

利用ETCD

etcd 能满足不会丢失的，多副本，强一致的全部需求。两种方案：

利用ETCD实现分布式锁，对存储在ETCD中的自增ID加锁实现

利用ETCD的boltdb，boltdb是一个单机支持事务的KV存储，key是reversion，value是key-value，bolted会把每个版本都保存下来，实现多版本机制

用etcdctl通过批量接口写入两条记录：

etcdctl txn <<<'
  put key1 "v1"
  put key2 "v2"

再通过批量接口更新这两条记录：
etcdctl txn <<<'
  put key1 "v12"
  put key2 "v22"

boltdb中其实有了4条数据：
rev={3 0}, key=key1, value="v1"
rev={3 1}, key=key2, value="v2"
rev={4 0}, key=key1, value="v12"
rev={4 1}, key=key2, value="v22"

此时可以发现reversion由两部分组成，第一部分为main rev，每次事务进行会加一，第二部分sub rev，同一个事务中每次操作加一。另外ETCD提供了命令和选项来控制存储的空间问题

利用ZooKeeper

利用ZooKeeper的顺序一致性和原子性，当客户端每次需要自增id时，创建一个持节顺序节点，ZooKeeper为了保证有序，会给这些节点编号，同时ZooKeeper会保证并发时不会产生冲突，创建成功后会返回类似/root/generateid0000000001的结果，再进行截取即可，另外，为了保证不浪费空间，可以用完该znode后进行删除。

缺点：ZooKeeper是CP，不保证完全高可用，另外，由于数据需要再ZooKeeper间进行过半数同步完才算写入成功，性能也一般

利用Redis

使用Redis的incr命令来实现原子性的自增和返回

优点：简单方便

缺点：需要对id进行持久化，虽然Redis本身提供了RDB和AOF，但如果宕机了，仍然有可能出现重复ID，如果为Redis搭建集群，由于Redis主从复制时异步复制的，无法保证master宕机之前将最新的id同步给其他子节点，导致宕机恢复之后可能会产生重复的id，需要针对这种情况做特殊处理，比如当id重复时报特殊错误码，跳过这个错误的id区间。

分布式相关

记录分布式相关的一些理论、技术

分布式理论

CAP理论

BASE理论

关于可靠性、可用性、稳定性

分布式事务

一、2PC

正常情况下

异常情况下

缺点

二、3PC

正常情况下

异常情况下

三、TCC

TCC可能存在的问题

四、本地消息表

五、SAGA

六、简单通过可靠消息和最终一致性方案实现

参考：

分布式算法

去中心化复制，如Gossip

主从复制，如MySQL、Redis

Paxos算法

Raft算法

分布式锁

利用数据库唯一约束

etcd实现

ZooKeeper实现

Redis实现

单机Redis实现

集群Redis实现

分布式自增id

数据库自增id

分段 + 发号器

雪花算法

利用ETCD

利用ZooKeeper

利用Redis