一、常见算法
1.1 UUID
总共包含32个16进制数字，分为五段。
- 优点：性能高，本地生成、没有网络消耗。
- 缺点：不易存储，UUID太长；基于MAC地址生成，可能会泄露MAC地址。
1.2 雪花算法
实现方案是划分命名空间，将64bit划分成多段，分别标识机器、时间等信息。
雪花算法示意图
第0位：用于标识正负，没有使用。
第1~41位：共41位，用于标识事件戳，单位是毫秒，可以支撑2^41（约69年）。
第42~52位：共10位，前5位表示机房id，后5位代表机器id。
第53~64位：共12位，用来表示序列号自增，代表每台机器每毫秒能产生的最大ID数（2^12=4096）。
优点：毫秒数在高位，自增序列在低位，整个id都是趋势递增，无依赖数据库或第三方系统，稳定性更好。
缺点：依赖机器时钟，如果出现时钟回拨，会导致生成重复id。
1.3 第三方实现的唯一ID
- Mongdb objectID，它也可以算作是和 snowflake 类似方法，通过“时间+机器码+pid+inc”共 12 个字节，通过 4+3+2+3 的方式最终标识成一个 24长度的十六进制字符
- Seata内置的UUID生成器，完整类名为：io.seata.common.util.IdWorker
1.4 基于数据库生成
基于mysql实现：
优点：实现简单，利用现有数据库实现，ID单调自增，存储空间消耗较小。
缺点：并发量低，存在数据库单点问题，每次获取id都要访问数据库，增加数据库压力。
基于redis实现：
通过incr命令实现原子自增，但是redis存在数据丢失风险，可能会产生重复id。
二、分布式ID
美团的Leaf方案：
Leaf-segment：
美团Leaf-segment方案，将mysql的每次只获取一个id，改成批量获取，用完之后再批量获取。
Leaf-segment数据库表
biz_tag:业务标识，区分业务使用
max_id:该biz_tag目前被分配的ID号段最大值
step:每次分配的号段长度
多服务架构示意图
优点:便于扩展（只要插入一条数据，就是对应一个业务的唯一ID），容灾性高（预先读取了一批数据进行缓存）
缺点:
- 生成的id不随机，能够泄露发号数量；
- 数据库宕机会造成整个系统不可用；
- 数据波动大，当号段使用完后，再重新获取阶段，会产生大量的I/O阻塞。
双Buffer优化：leaf服务内部有两个号段缓存区segment。当前号段已下发10%时，将开启另一个线程去更新下一个号段。当前号段发送完毕，切换到下一个号段，循环往复。
双buffer实现不间断取号
Leaf-snowflake：
针对leaf-segment生成的id号可以统计出号段数，美团提出Leaf-snowflake算法。
Leaf-snowflake方案完全沿用snowflake方案的bit位设计，即是“1+41+10+12”的方式组装 ID 号。对于 workerID 的分配，当服务集群数量较小的情况下，完全可以手动配置。Leaf 服务规模较大，动手配置成本太高。所以使用 Zookeeper 持久顺序节点的特性自动对 snowflake 节点配置 wokerID。Leaf-snowflake 是按照下面几个步骤启动的：
- 启动 Leaf-snowflake 服务，连接 Zookeeper，在 leaf_forever 父节点下检查自己是否已经注册过（是否有该顺序子节点）。
- 如果有注册过直接取回自己的workerID（zk顺序节点生成的int类型ID号），启动服务。
-
如果没有注册过，就在该父节点下面创建一个持久顺序节点，创建成功后取回顺序号当做自己的 workerID 号，启动服务。
弱依赖zookeeper：除了每次去zk拿数据外，还在本机缓存了一个workerID文件，当zk出现问题，使用缓存也能确保服务正常。
image.png
解决时钟回拨问题：
1.如果是新节点，通过RPC请求得到所有节点的系统时间，计算平均时间sum(time)/nodeSize。如果本机时间和平均值不相等，则启动失败并报警。
2.如果是老节点，就和zk节点记录的时间比较，如果小于则发生了时钟回拨，服务启动失败并报警。
image.png
网友评论