设计目的：
在分布式条件下，生成唯一ID，速度快
要求：
-
长度8字节，首位不能使用，故只能使用63bits
-
全局唯一
设计思路：
由于不是集中分配，所以每台机器必须唯一，生成过程中必须要有机器唯一的信息，可以使用：
-
每个机器分配一个唯一机器ID，需要外部机制的依赖如etcd
-
取MAC地址（太长了128bits）
-
取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。
实现思路如下：
-
每个进程在启动的时候，都会生成一个uuid，将此ID作为唯一键，Value为当前进程的worker id，并且维持续Lease
-
维护一个已分配的worker id的bitmap，由于worker id最大为4096，故该bitmap需要空间4096/8 bytes = 512bytes，用来标记已分配的worker id情况。
-
程序每次启动时，需先waitNextSecond（或者0.5s，这个wait时间可以自己根据实际情况需求设定），保证多次重启的情况下，能够有进程的Lease失效。
每次分配的流程如下：
-
都先获取现在集群中所有的进程的worker id分配信息，和该bitmap
-
找出目前已分配到了最大worker id值，在此基础上+1操作，作为此次分配的worker id
-
计算出新的bitmap，用Etcd的事务，写入该bitmap到Etcd中，如果事务失败，重新启动整个流程
-
之后，将自己的uuid作为键，此次分配的worker id作为value，写入到Etcd中，并且维持续Lease
-
过程中如果失败，重新启动整个流程
-
由于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 已满足大多数场景
算法的限制条件：
- 对集群内的进程数量有限制要求
- 对于允许的最大时钟跳变时间有限制
- 强依赖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 ；
网友评论