分布式唯一ID生成

设计目的：

在分布式条件下，生成唯一ID，速度快

要求：

• 长度8字节，首位不能使用，故只能使用63bits

• 全局唯一

设计思路：

由于不是集中分配，所以每台机器必须唯一，生成过程中必须要有机器唯一的信息，可以使用：

1. 每个机器分配一个唯一机器ID，需要外部机制的依赖如etcd

2. 取MAC地址（太长了128bits）

3. 取IP地址（可能冲突，不同机器的子网ip可能冲突）

设计参考：

思路，按照生成uuid的思路生成，参考twitter的snow-flake算法来生成

格式

• tag：1bit，不使用

• physic delta time：31bits，当前物理时间的秒-Base时间秒值，最大支持到68年以后，按照某一时间点为Base时间（如项目上线时间），可以hard code到代码中。

• worker node id：12bits，每个进程用的唯一标识 ID

• sequence id：20bits，1s内自增

提供的性能：

每秒最大理论提供获取104w个id生成。

难点及解决：

会出现的问题	解决方案
A. 如果当前时间⼩于记录的上⼀个秒值，则说明这台机器的时钟回拨了	更换worker id
B. 如果当前时间等于记录的上⼀个秒值，则说明这台机器的时钟回拨了	⾃旋⾄下⼀秒
C. 如果这台机器的系统时间在启动之前回拨过，那么有可能出现ID重复的危险	可以重启时候使⽤与上次不同的worker id来避免确定时钟可能回拨的最⼤值，为了防⽌重复id分配，可以等待最⼤回拨时间后分配确定时钟可能回拨的间隔时间，保证不会连续出现回拨！
D. 最后⼀次获取的ID值是否需要保存	可以通过上⾯⽅法C避免持久化保存

（每次启动使⽤不同的worker id弊端：从ID不能确定是哪⼀个机器的进程发送的事务请求。）

限制因素的处理：

由于集群中时钟回拨的时间和次数很难确定，所以我们倾向每次使用不同的worker id来回避这个问题。

这里我们会强依赖Etcd，用来保存进程 的worker id信息和已分配worker id的map。

实现思路如下：

1. 每个进程在启动的时候，都会生成一个uuid，将此ID作为唯一键，Value为当前进程的worker id，并且维持续Lease

2. 维护一个已分配的worker id的bitmap，由于worker id最大为4096，故该bitmap需要空间4096/8 bytes = 512bytes，用来标记已分配的worker id情况。

3. 程序每次启动时，需先waitNextSecond（或者0.5s，这个wait时间可以自己根据实际情况需求设定），保证多次重启的情况下，能够有进程的Lease失效。

   每次分配的流程如下：

   1. 都先获取现在集群中所有的进程的worker id分配信息，和该bitmap

   2. 找出目前已分配到了最大worker id值，在此基础上+1操作，作为此次分配的worker id

   3. 计算出新的bitmap，用Etcd的事务，写入该bitmap到Etcd中，如果事务失败，重新启动整个流程

   4. 之后，将自己的uuid作为键，此次分配的worker id作为value，写入到Etcd中，并且维持续Lease

   5. 过程中如果失败，重新启动整个流程

由于bitmap的延后清除，即当存在已经挂了的进程时，即使其Lease最终消失，但bitmap中仍旧会存在其已经占用，此时我们保持向后递增分配，就可以绕过当前已存在的worker id，保证不会立即复用编号较小的worker id。

由于步骤3会重新生成bitmap，以此来保证Lease已经消失的进程的worker id，可以被回收掉。

我们保证使用最大值+1来分配worker id，如果已经存在到达了4095的worker id我们需要回环去找。即最大值回环向右第一个当前未使用的worker id。并且用Etcd事务保证了更新bitmap的原子性。

正确性分析：

• Lease ，worker id过期时间

• t，重启一次进程，开始获取worker id前等待时间

• N，Lease时间内重启次数为

• n，集群内进程数量

• Range，Worker Id 分配区间

那么，在Lease时间内，单个进程能够重启的次数为：

N = Lease / t ;

那么n个进程，在Lease时间内，可以重启的次数为：

C = N * n ；

即，C = Lease / t * n

C的值的含义就是，在Lease时间内可能消耗掉的worker id的数量最大值。

那么我们只要保证 C < Range 就可以保证Lease时间内是有足够的worker id可以分配给集群中的进程。

举例：

Range = 4096; 分配worker ID 的区间

n = 100 ; 集群中进程数量为 100 个

Lease = 5 s；worker id 的 Lease 时间

t = 0.5 s ; 重启等待时间0.5s

由此，计算出来C的值为：C = 5 / 0.5 * 100 => 1000

4096 > 1000 ，可以满足Lease内的分配需求。

允许的最大时钟跳变：

即最后一次分配worker id复用了第一次分配的worker id经历的时间，也即 worker id 的Range 在多少秒会被使用完。

我们假设集群中的进程断重启。那么理论上，在Range用完时（不回收worker id），可以重启的总次数为：

MaxRestartCount = Range / n ;

重启花费的总时间为：

ReverseTimeCount = MaxRestartCount * t ;

（Lease 必须小于 ReverseTimeCount ，这样 再次循环使用第一次分配的worker id时，才可用。）

故，我们允许的最大时钟跳变为 ReverseTimeCount

举例：

目前我们的Range为【0，4096），也就是可以分配4096个worker id，即 Range = 4096 ；

假设集群中存在100个进程，即 n = 100 ；

假设重启一次时间为0.5s，即 t = 0.5 s

故 ReverseTimeCount = Range/n * t = 20.48 s

允许的最大时钟跳变为 20.48 s 已满足大多数场景

算法的限制条件：

1. 对集群内的进程数量有限制要求
2. 对于允许的最大时钟跳变时间有限制
3. 强依赖Etcd

假设，一个集群4个进程，也就是 n = 4 。

假设我们的Lease 为5 s，重启等待时间为0.5s

那么允许的最大时钟跳变：
（假设目前worker id的数量是4096个）
ReverseTimeCount = 4096 / 4 * 0.5 = 512 s

Lease 内 最大消耗的worker id 数量为：

C = 5 / 0.5 * 4 = 40 个

要保证一个Lease不能消耗完所有worker id并且根据集群时钟同步状况，来控制允许的最大时钟跳变。

如果集群中进程是1000个，那么
C = 5 / 0.5 * 1000 = 10000 ，10000大于4096 ，这个超过了worker id的分配范围。所以此时必须调整 重启等待时间，调长一些。

此时允许的最大时钟调变：
ReverseTimeCount = 4096/1000*0.5 = 4 * 0.5 = 2 s

The End ；