设计分布式唯一id生成

1. 生成全局唯一id

什么时候需要生成全局唯一id

db不帮你自动生成的时候。比如：

• db做了分库分表，没帮你自动生成，你又需要一个全局唯一的业务id
• 没走db，比如请求到了后端要生成一个traceId

如何设计全局唯一id生成服务

a. 不依赖第三方唯一id生成服务，利用业务db的特性来生成id
比如业务的“订单表”做了分库分表后，想要全局唯一的订单id，就让分库后每个库按不同的起点和步长做递增。这样订单系统就不用依赖发号服务了，自己解决问题

image

缺点是db扩缩容时候太复杂。
另一个思路是每个分表有一个前缀，在分表内自增
这样其实可以避免扩缩容麻烦的问题，比如sharding策略是预先分1000个表，每个表的id有个通用前缀，表内id自增

b. 非中心化方案，机器标识(比如mac地址）作为命名空间，通过命名空间保证唯一
比如:

• UUID（有很多种，有用Mac地址的。https://baike.baidu.com/item/UUID/5921266?fr=aladdin ）
  不过拿来做db主键有些缺点，比如太长，比如没有趋势递增性，对B+ tree存储不够cache friendly

• snowflake(时间戳+命名空间+序列号，时间戳放前面以便全局趋势递增）

c. 中心化方案，实现一个唯一id生成服务，基于写操作线性一致的存储
比如用mysql自增特性做个发号器服务
比如随机，往线性化存储里cas写，写成功就算申请到id
如果吞吐量过大、对存储有压力，可以在存储上面加个cache，预先从存储申请多个id（号段）。这个cache就不需要用redis等，起个java程序做进程内cache即可

2. 生成“趋势递增”的全局唯一id

什么场景需要趋势递增？

• 对b+树类的db来说cache friendly
  不过这种场景其实没有全局趋势递增需求，可以分表递增，每个分表id为 sharding前缀+自增id。用不到全局趋势递增

• 拿来排序查最新数据
  比如查最新消息，不用新增个时间戳字段、建索引，直接按id排序查最新的100条：

select * from message order by message-id limit 100

再比如nosql之类的在时间戳字段上加索引很难，分页查最新数据的时候，只想按id查
https://www.w3cschool.cn/architectroad/architectroad-distributed-id.html

方案

• 基于一个中心化的存储，套一层号段cache
  比如美团Leaf-segment
  https://tech.meituan.com/2017/04/21/mt-leaf.html

• 非中心化方案
  时间戳放到id的最前面，比如snowflake的 时间戳+workerId(命名空间）+序列号
  如果是key/value存储，想取同一个key最新数据，可以[同样的前缀key][反向时间戳]，方便分页取最新的数据。参考http://hbase.apache.org/book.html#reverse.timestamp

Q: 类snowflake算法基于时间戳+命名空间，时钟回拨怎么办？
（发生闰秒、NTP时钟同步等情况都可能导致时钟回拨）
a. 外接存储记录最新时间戳，检测回拨。比如美团外接了个zk
b. 最终往线性化存储里写的时候检测重复，重复就报错重来
c. 多加几个命名空间，让概率小到忽略不计

Q: snowflake里的workerId咋生成
a. 基于线性化存储
比如美团方案，外接一个zk，每个机器顺序取workerId（依赖机器）;
但是这样太重了，可以把workerId换成业务id，思想是通过命名空间减少冲突概率，而不是绝对唯一

b. 没必要一定用机器id，本质上只是加个命名空间，加几个业务字段作为命名空间就行
我们之前用到的方案是id里面除了时间戳还加上一些uid、业务类型、随机数之类的字段，作为命名空间，减少冲突概率

3. 生成全局单调递增的唯一id

什么场景需要

• 版本号类的需求，比如做diff、判断先后顺序等
• 拿id排序，业务不接受趋势递增，要求严格递增

方案

• 中心化方案。基于一个写操作线性一致的存储
  性能不够可以套个单节点cache，通过选举fo来提高可用性
  image.png
  见https://www.w3cschool.cn/architectroad/architectroad-distributed-id.html

Q: 分布式关系库能否自动生成全局单调递增的唯一id?
看Tidb的只是单机递增，没法保证全局单调递增：
https://docs.pingcap.com/zh/tidb/stable/auto-increment

4. 介于“趋势递增”和“全局单调递增”之间的保证

“趋势递增”和“全局单调递增”这两种保证处于两个极端，能否给出介于两者之间的保证？

• sharding内单调递增
  比如mysql分表后，每个分表sharding内递增
  比如上文说的Tidb

• 单Insert语句内单调递增

• session内单调递增

• 单client所有请求生成的id单调递增
  以上两个用Lamport timestamp可以实现，得到的全序id符合因果序

Reference

架构 细聊分布式ID生成方法
Leaf——美团点评分布式ID生成系统
https://www.liaoxuefeng.com/article/1280526512029729