流行方案

现在流行的分布式 ID 方案很早就已经稳定了 基本的分布式 ID 都有一下特性

  • 全局唯一
  • 是否递增
  • 能否摆脱单机限制

实现方案

  • 完全依赖数据源方式: —- ID 的生成规则,读取控制完全由数据源控制,常见的如数据库的自增长 ID,序列号等,或 Redis 的 INCR/INCRBY 原子操作产生顺序号等。
  • 半依赖数据源方式: —- IID 的生成规则,有部分生成因子需要由数据源(或配置信息)控制,如 snowflake 算法。
  • 不依赖数据源方式: —- ID 的生成规则完全由机器信息独立计算,不依赖任何配置信息和数据记录,如常见的 UUID,GUID 等。

方案实践

实践方案适用于以上提及的三种实现方式,可作为这三种实现方式的一种补充,旨在提升系统吞吐量,但原有实现方式的局限性依然存在。

MongoDB ObjectId()

MongoDB在 3.2 之前使用了和Snowflake类似的算法,但是后来废弃了。怀疑是在现在全民上容器的环境下,容器里的主机名很多都是localhost该算法使用起来并不理想。

MongoDB 3.2 及其之前

            timestamp                            sequence id
                │            node id    process id    │
                │                │          │         │
                ▼                ▼          ▼         ▼
      ┌─────────────────────┬────────────┬───────┬────────────┐
      │ 0000000.......00000 │ 000...0000 │ 00000 │ 0000...000 │
      └─────────────────────┴────────────┴───────┴────────────┘
              4 byte           3 byte    2 byte     3 byte

MongoDB 3.2 之后

            timestamp          rand number     sequence id
                │                   │                │
                ▼                   ▼                ▼
        ┌────────────────┬───────────────────────┬─────────┐
        │ 000000....0000 │ 0000000......00000000 │ 00...00 │
        └────────────────┴───────────────────────┴─────────┘
              4 byte              5 byte           3 byte

MySQL 自增 ID

优点

  • 使用简单,维护成本低
  • 天然单调递增,某些场景使用很方便

缺点

  • 本身不支持分片之类都操作,无法摆脱单机 TPS 都局限
  • 主从同步切换时很容易出现问题

Redis 自增 ID

如果数据库性能不能支撑业务时可以考虑使用 Redis 来 生成唯一 ID。

例如 订单号 = 日期 + 当日增长序列 - INCR , 或者每次用 INCRBY 批量获取部分 ID。在应用内部分发,等消耗完来再次获取 -

优点

  • 不依赖业务数据库,性能比普通数据库好
  • ID 有序

缺点

  • 需要做一定等编码和配置,工作量较大

UUID

UUID12是通用唯一识别码(Universally Unique Identifier)的缩写,开放软件基金会(OSF)规范定义了包括网卡 MAC 地址、时间戳、名字空间(Namespace)、随机或伪随机数、时序等元素。利用这些元素来生成 UUID。

  • uuid1() 序号 + 时间 + 主机 ID
  • uuid3() 根据传入的参数 HASH
  • uuid4() 全部随机
  • uuid5() 根据传入的参数 SHA-1

优点

  • 性能非常高:本地生成,没有网络消耗。

优点

  • 性能非常高:本地生成,没有网络消耗
  • 以主机信息 HASH 或者 SHA 加密要考虑种子数据碰撞的可能性,
  • MAC 地址加密是可以被跟踪的,历史上有根据 uuid -> mac 地址 找人的案例
  • uuid4 这种全部随机的方式是非常容易被猜中的
  • 现在很多应用的都部署在容器中,它们都主机名和网卡高度相似,这会提高碰撞都几率

Snowflake

Snowflake3 和 python 的 uuid 类似,都是时间戳 + 主机信息 + 时钟序列

unused(1bit)                     datacentor id(5bit)
     │                                     │
     │         timestamp(41bit)            │ worker id(5bit)
     │                │                    │       │
     │                │                    │       │ sequence id(12bit)
     │                │                    │       │         │
     ▼                ▼                    ▼       ▼         ▼
   ┌───┬───────────────────────────────┬───────┬───────┬───────────┐
   │ 0 │ 0000000000.........0000000000 │ 00000 │ 00000 │ 000000000 │
   └───┴───────────────────────────────┴───────┴───────┴───────────┘
  • 1 位,不用。二进制中最高位为 1 的都是负数,但是我们生成的 id 一般都使用整数,所以这个最高位固定是 0
  • 41 位,用来记录时间戳(毫秒)。
    • 41 位可以表示 2^41-12
    • 如果只用来表示正整数(计算机中正数包含 0),可以表示的数值范围是:0 至 2^41-12^41−1,减 1 是因为可表示的数值范围是从 0 开始算的,而不是 1。
    • 也就是说 41 位可以表示 2^41-12^41−1 个毫秒的值,转化成单位年则是(2^41-1) / (1000 _ 60 _ 60 _ 24 _ 365) = 69(2^41−1)/(1000∗60∗60∗24∗365)=69 年
  • 用来记录工作机器 id
    • 可以部署在 2^10=1024 个节点,包括 5 位 datacenterId 和 5 位 workerId
    • 5 位(bit)可以表示的最大正整数是 2^5-1=31 即可以用 0、1、2、3、…31 这 32 个数字,来表示不同的 datecenterId 或 workerId
  • 12 位,序列号,用来记录同毫秒内产生的不同 id。
    • 12 位(bit)可以表示的最大正整数是 2^{12}-1 = 4095−1=4095,即可以用 0、1、2、3、…4094 这 4095 个数字,来表示同一机器同一时间截(毫秒)内产生的 4095 个 ID 序号

优点

  • 不依赖数据库等第三方系统,以服务的方式部署,稳定性更高,生成 ID 的性能也是非常高的
  • 时间戳在高位,序列在地位,整个 ID 是递增的
  • 中间服务器信息部分可以灵活定制

缺点

  • 强制依赖机器时间,如果发生时钟回拨,整个 uuid 可能会出现重复
  • 41 bit 的二进制长度最多能表示 2^41 -1 毫秒即 69 年

大厂方案

百度4、美团5、滴滴6、微信7 各个大厂在分布式ID方面都有轮子,有以下特点。

  • 在服务器信息方面做来可能配置化
  • 时钟偏移都问题得到了解决
  • 与本身业务使用都方式结合严密
  • 高可用
  • 在递增、性能、等方面都做了取舍

总结

方案 顺序性 重复性 存在问题
数据库自增主键 递增 不会重复 数据库宕不可用机
UUID 无序 通过多位随机字符做到极低重复概率 一直可用
Redis 递增 RDB 持久化模式下,会出现重复 Redis 宕机不可用
Snowflake 递增 不会重复 时钟回拨
  • 市面上大多数的方案都大同小异。
  • 任何一件看起来很简单的事情,在海量的访问量下都会变得不简单。
  • 尽量不要过度设计,例如订单系统一天只有 100W 的订单,平均下来一秒的订单在 10 条左右,其实 UUID 就能满足。
  • 很多方案依赖主机等静态信息,使用序注意,不然会回退单机且可能出现重复 ID。
  • 尽量根据实际情况设计,我见过 SHA1(user_id) + timestamp 的 ID 生成算法,实际情况还挺好的。

参考文献


  1. UUID - A Universally Unique IDentifier (UUID) URN Namespace] ↩︎

  2. uuid-python - Python uuid ↩︎

  3. Snowflake - Twitter Snowflake ↩︎

  4. uid-generator - 百度 uid-generator ↩︎

  5. Leaf - 美团 Leaf ↩︎

  6. tinyid - 滴滴 tinyid ↩︎

  7. wechat - 微信序列号生成器架构设计及演变 ↩︎