Nitro's

Apr 18, 2020 - Comments - tech

唯一ID生成算法

前言

唯一ID在互联网大厂的业务线中广泛使用,比如订单号、数据库主键、IM消息序号、交易流水号等等,这些ID的共同特点是唯一标记某一个业务记录或者消息、部分ID自增、全局有序或者局部有序。

UUID作为是一种全局唯一的方案是可供使用的选择之一,但在实际操作中大家一般使用的很少,几个原因:

  1. 16个字节128位占用太多的存储空间不适合用来作为主键;
  2. UUID的版本1基于MAC地址和时间戳,可保证全局唯一,但容易被硬件追踪;
  3. 后续版本使用伪随机数、SHA1又没有前向兼容,用在特定业务的一定范围内使用没有问题,但作为分布式系统的唯一ID不适合。

所以就有了各个互联网大厂分享的各自业务中实现唯一ID的不同算法和系统部署方案,唯一ID算法主要核心聚焦在以下几点:

  • ID位数
  • ID算法原理
  • 全局唯一
  • 全局(局部)趋势有序
  • 时钟回拨问题
  • 外部系统依赖

技术实现汇总

从大厂分享的技术实现汇总如下:

| 厂牌 | 技术方案 | ID位数 | 全局唯一 | 有序 | 时钟回拨 | 外部系统依赖 | | ———|———–|——–|——— |———-|———-|————-| | Twitter | SnowFlake | 64 | 全局唯一 | 局部有序 | block wait | | None | | MongoDB | ObjectId,与SnowFlake类似 | 96 | 全局唯一 | 局部有序 | \ | None | | 百度 | UidGenerator,与SnowFlake类似 | 64 | 全局唯一 | 局部有序 | 兼容 | None || | 微信 | 与SnowFlake类似 | 64 | 全局唯一 | 场景有序 | \ | None | | 美团 | Leaf-segment | 64 | 全局唯一 | 全局有序 | \ | MySQL | | 美团 | Leaf-snowerFlake ,与SnowFlake类似 | 64 | 全局唯一 | 局部有序 | fixed or interrupt |Zookeeper | | 融云 | 自定义 | 80 | 全局唯一 | 场景有序 | \ | None |

技术细节

Twitter

算法

id-twitter-snowflake

  • 1bit - 默认为0
  • 41bit - 毫秒时间戳
  • 10bit - 机器ID
  • 12bit - 自增序列号

最多支持69年,1024台机器,QPS 409.6w/s

参考

Github

Twiiter-Blog

MongoDB

算法

id-mongoDB

  • 32bit - unix timestamp second
  • 24bit - 机器ID
  • 16bit - 进程ID
  • 24bit - 序列号,随机数开始

参考

Github

百度

算法

id-uidgenerator

  • 1bit - 默认为0
  • 28bit - 基于服务启动时间的增加时间,秒
  • 22bit - 服务启动次数
  • 13bit - 自增序列号,QPS 4096/s

参考

Github

微信

算法

uid用户空间内独立自增的64bit ID,支持分区读取、持久化。

参考

Wechat-Blog

美团

算法

Leaf-snowflake,参考SnowerFlaker设计。

Leaf-segment,类似微信方案,bid业务空间内独立自增,支持双buffer预读取、DB持久化。

参考

Meituan-Blog

Github

融云

算法

id-rongyun

  • 42bit - 时间戳,毫秒
  • 12bit - 序列号
  • 4bit - 会话类型
  • 12bit - 会话ID

因为融云本身的业务就是IM消息,所以ID强耦合了他们的IM系统服务,IM消息系统可以参考。

参考

Blog

逝去的哥

comments powered by Disqus