分布式唯一 ID 解析

 关注
发布于: 2020 年 06 月 17 日
业界常见解决方案UUIDuuid
1个UUID是1个16字节（128位）的数字； 为了方便阅读，通常将UUID表示成如下的方式：
123e4567-e89b-12d3-a456-426614174000
缺点：
ID太长，占用空间较大
索引效率低
不能保证趋势递增，不适合做DB主键（MySQL聚簇索引下插入不是顺序的，会导致随机IO增多，性能下降）
Snowflake
﻿
缺点：
强依赖机器时间，如果时间回拨Id可能会重复
不是严格的趋势递增，极端情况在机器时间不同步的情况下后生成的Id可能会小于先生成的Id，即只能在worker级别保证递增
服务需要保证workerId唯一（如果需要保证严格唯一的话会比较麻烦，简单可以基于服务IP跟Port来生成，但由于workerId只有10位，因此workerId可能会重复）
Redis生成Id可以使用Redis的原子操作 INCR 或者 INCRBY 来实现
优点：
性能较好
Redis单线程，没有线程安全问题，能保证ID趋势递增
缺点：
如果Redis需要迁移的话，需要保证迁移过程中的数据一致性，难度较大
Redis持久化如果使用RDB，因此Redis重启会丢数据，导致ID重复
美团Leaf原文：https://tech.meituan.com/2017/04/21/mt-leaf.html
Leaf Segment
﻿
使用DB号段保证唯一，Leaf Node启动时或者在号段快用完时会从DB重新申请一段号段。
缺点：
只能保证在Leaf Node级别趋势递增，不能保证全局趋势递增
ID不够随机，能够泄露发号数量的信息，不太安全
DB宕机会造成整个系统不可用
Leaf Snowflake
﻿
ID生成方式类似Snowflake。
workerId使用Zookeeper顺序结点的特性来实现，保证workerId唯一。
周期性上报时间给Zookeeper，启动时做时间检验，时间回拨则告警。
微信序列号生成器原文：https://mp.weixin.qq.com/s/JqIJupVKUNuQYIDDxRtfqA
﻿
﻿
可以看出，微信序列号生成器是在用户级别趋势递增。像微信这么大的消息量，如果像美团Leaf Segment一样在业务级别递增的话，那么序列号生成器肯定会成为性能瓶颈；而且美团Leaf Segment并不能保证全局趋势递增，并不能适用IM Timeline模型。
优点：
Section级别的并发，大大提高了并发
完美解决了IM Timeline模型下需要严格趋势递增ID的问题
缺点：
重客户端，架构复杂，开发维护成本大
百度UidGenerator原文：https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md
基于Snowflake
﻿
使用RingBuffer缓存UID，并通过双RingBuffer+CacheLine补齐方式提高并发，解决了伪共享问题
﻿
workerId由MySQL自增Id分配。
通过借用未来时间来解决Sequence的并发限制，即每秒只能有8192个并发，超过则需要使用未来的时间来生成。
时间不是取的机器时间，而是用启动时间自增来实现。
缺点：
默认可用时间太少，只有8.7年，如果加大时间，workerId又太少（因为workerId用完就丢弃，目前还没提供复用策略）
如果重启的时候时间回拨，虽然能保证ID唯一，但ID可能会变小，不是严格的趋势递增
timeBits & workerBits规则固定，如果不同业务需要不同生成规则需要重新搭建一套
以库的形式提供，使用配置复杂
MongoDB ObjectID原文：https://docs.mongodb.com/v3.2/reference/method/ObjectId/
﻿
1 ~ 4：时间戳
5 ~ 7：机器Host Name的MD5值
8 ~ 9：进程Id
10 ~ 12：递增计数器
缺点：
占用存储空间多
不能保证趋势递增
解决分布式唯一ID的一个想法本方案参考百度UidGenerator，解决了workerId无法复用的问题
使用Snowflake，利用MySQL自增Id分配workerId，并复用workerId；同时利用时间号段保证时间趋势递增
使用Snowflake，64bit的Id设计如下：
﻿
因此，最多有 2^10 = 1024个workerId，分配WorkerId的DB Schema设计如下：
CREATE TABLE IF NOT EXISTS `worker_node_tab`
(
	id BIGINT NOT NULL AUTO_INCREMENT COMMENT 'worker id',
	ip CHAR(64) NOT NULL COMMENT 'host IP',
	port CHAR(64) NOT NULL COMMENT 'host port',
	last_timestamp TIMESTAMP NOT NULL COMMENT 'last timestamp',
	duration_step TIMESTAMP NOT NULL COMMENT 'duration',
	mtime TIMESTAMP NOT NULL COMMENT 'modified time',
	ctime TIMESTAMP NOT NULL COMMENT 'created time',
	PRIMARY KEY(id)
) COMMENT='WorkerID Assigner for UID Generator',ENGINE = INNODB;
﻿
服务启动流程：
往worker_node_tab插入自己的IP&Port等信息，获取DB自增id，设置workerId = id % 1024
从worker_node_tab获取最大的last_timestamp(max_last_timestamp)，并设置timestamp = max_last_timestamp + duration_step
备注：因为百度UidGenerator workerId不会重复，因此不用担心timestamp重复；我们需要复用workerId，因此必须要保证timestamp是趋势递增的
生成Id流程：
sequence += 1
如果sequence还没超过MAX_SEQUENCE(2^12)，则跳到(3)直接生成Id；如果sequence大于等于MAX_SEQUENCE，则设置timestamp += 1, sequence = 0，然后跳到(3)生成Id（timestamp在本地自增，因此不用担心时间回拨的问题）
生成Id：Id = timestamp << (10 + 12) | workerId << 12 | sequence
duration_step可以设置为两天（或更长），每隔一天异步到DB申请一个时间号段（即设置DB last_timestamp += duration_step）；可以做到弱依赖DB
参考Universally unique identifier
Twitter IDs (snowflake)
Leaf——美团点评分布式ID生成系统
万亿级调用系统：微信序列号生成器架构设计及演变
百度UidGenerator
MongoDB ObjectID
﻿