01 分布式统一 id 设计

Wu Jun 2019-03-22 22:09:15
08 系统设计 > 1 通用设计

一、业界现状

1 汽车之家

1)id 方案

自增 id

现有数据从 4 位到 6 位,目前最大 320w+

2)实例
作品 id URL 类型
3200292 https://chejiahao.autohome.com.cn/info/3200292 轻文
3200293 https://chejiahao.autohome.com.cn/info/3200293 视频
3200294 https://chejiahao.autohome.com.cn/info/3200294 文章
3292759 https://chejiahao.autohome.com.cn/info/3292759 车单
2037191 https://chejiahao.autohome.com.cn/info/2037191 音频
3)推断

汽车之家作品是同一张表,只是文章类型不同

2 今日头条

1)id 方案

类 snowflake 方案:

2)实例
文章

文章 id 长 19 位,换为 2 进制 63 位。
前 31 转为 10 进制,作为秒级时间戳换算出id时间,与页面上的发布时间基本相同。
后 32 位未知,10 位 +12 位 0+10 位组成。

类型 头条文章id id时间戳 id时间 发布时间 id二进制后32位
视频 6652080479031788035 1548808179 2019-01-30 08:29:39 2019-01-30 08:55 10010010000000000000001000000011
视频 6651915175337132551 1548769691 2019-01-29 21:48:11 2019-01-29 21:48 11001110000000000000001000000111
文章 6651399498713006604 1548649626 2019-01-28 12:27:06 2019-01-28 12:27:06 01111100000000000000001000001100
文章 6651346820406444547 1548637361 2019-01-28 09:02:41 2019-01-28 12:07:26 01011100010000000000001000000011
图集 6651206373847597572 1548604661 2019-01-27 23:57:41 2019-01-27 23:57:41 00011001000000000000001000000100
图集 6651200467252544004 1548603285 2019-01-27 23:34:45 2019-01-27 23:34:45 11011100100000000000001000000100
微头条

微头条 id 长 16 位,换为 2 进制 51 位。
前 31 转为 10 进制,作为秒级时间戳换算出 id 时间,与页面上的发布时间基本相同。

微头条 id id 时间戳 id 时间 发布时间 id 二进制后 20 位
1623874174038023 1548647092 2019-01-28 11:44:52 2019-01-28 11:44:52 11011011000000000111
1623812987883539 1548588741 2019-01-27 19:32:21 2019-01-27 19:32:21 00110001000000010011
1623613645991950 1548398633 2019-01-25 14:43:53 2019-01-25 14:43:54 11110011000000001110
1620450619072515 1545382136 2018-12-21 16:48:56 2018-12-21 16:48:56 01101010000000000011
3)推断

3 美团

美团 Leaf 声称在美团内部服务包含金融、支付交易、餐饮、外卖、酒店旅游、猫眼电影等众多业务线。查找了一下,对外暴露的数据中还未发现 snowflake 痕迹。

1)详情页
猫眼电影——连续自增
榛果民宿——不连续自增
美团美食——不明
2)订单号
外卖 下单时间
5026 0271 7642 2612 7 2018-09-02 17:46:03
6233 7340 1594 0462 2018-07-17 18:34:11
3962 9431 3190 0632 1 2018-07-15 11:52:55
2273 5322 6921 7033 5 2017-06-30 11:39:01
团购 下单时间
4401257372 2018-05-21 14:33
3808118372 2017-07-21 17:35
2330035104 2016-02-11 10:59

二、snowflake 算法

1 简介

snowflake 是 twitter 开源的分布式 ID 生成算法,基于 Thrift,发布于 2010 年。因与自身机器架构依赖过深,twitter已于2014年宣布弃用最初版本,下一版本还未开源。详见 github

2 核心思想

一个 long 型的 ID 有 64 bit,划分不同含义:

3 类 snowflake 算法

采用 snowflake 算法思想,类 snowflake 算法根据各自业务需要,做出了不同改动。比如改变了位数占比,添加了业务线等其他信息

厂商 长度 组合 说明
美团Leaf 64位 1+41+10+12 完全沿用 snowflake 方案的 bit 位设计
百度UidGenerator 64位 1+28+22+13 1 符号位 + 28 秒级时间差(最多可支持约8.7年)+22位机器号(最多可支持约420w次机器启动)+13位序列号
今日头条-文章 64位 1+31+32 1 符号位 +31秒级时间戳 +32位其他
今日头条-微头条 52位 1+31+20 1 符号位 +31秒级时间戳 +20位其他
附:位数对应
二进制 45-47位 48-50位 51-54位 55-57位 58-60位 61-64位
十进制 14位 15位 16位 17位 18位 19位

三、id 设计参考

1 时间

1)时间类型
2)时间精度
3)支持时长
类型 毫秒 支持时长
时间戳 31位 41位 可用到2038年
时间戳 32位 42位 可用到2106年
时间差 30位 40位 能支持34年
时间差 31位 41位 能支持68年

2 序列号

单位时间(秒、毫秒)支持的并发量,秒级时间可以取大一点,毫秒取小一点

位数 并发量/时间单位
14 1.6w
12 4k
10 1k

3 机器号

纯机器号,或,机房号+机器号

1)物理机
2)虚拟机

4 其他含义位

业务线、备用拓展位……

5 id设计举例

1符号位 + 30位秒数时间差 + 7位序列号 + 16位机器号 = 54位

能用34年,单机每秒生成128的id,支持单机重启6.5w次,初始id长度为12,最终随时间增加,最长到16位

四、问题

1 时钟回拨问题

若机器出现时钟回拨,会产生重复id

1)启动时回拨

启动时获取其他机器的时间,计算出平均时间后,将本机时间与平均时间比较,若超过阈值则启动失败。

2)运行时回拨
  1. 直接拒绝,抛异常
  2. 若回拨时间小于阈值,则睡眠,等时钟追上
  3. 若回拨时间大于阈值,直接拒绝服务并报错
  4. 或若回拨时间大于阈值,更换机器号
  5. 或若回拨时间大于阈值,利用拓展位

2 id里是否需要业务线?

  1. 美团 Leaf 声称在内部服务众多业务线,但 id 里没有业务线设计
  2. 头条文章和微头条的最终页前缀相同,但 id 长度不同,可能是通过长度区分业务线的

五、一个实现

uid-generator-spring-boot-starter