分布式系统中，数据库的自增 ID 显然不能满足需求。

业务系统对 ID 号的需求：
1、全局唯一性：不能出现重复的 ID
2、趋势递增：主键应尽量有序，保证数据库写入性能

ID 生成系统还应做到：
1、平均延迟与 TP999延迟尽可能低
2、可用性
3、高 QPS

UUID

UUID(Universally Unique Identifier)的标准型式包含32个16进制数字，以连字号分为五段，形式为8-4-4-4-12的36个字符。

优点：

  • 生成性能高，本地生成没有网络消耗。

缺点：

  • 不易存储：UUID 太长，很多场景不适用
  • 信息不安全：基于 MAC 地址生成 UUID 的算法可能会造成 MAC 地址泄露，漏洞曾被用于寻找梅丽莎病毒的制作者位置。
  • 不利于 MySQL 索引： UUID 的无序性可能会引起数据位置频繁变动，严重影响性能。

类 snowflake 方案

生成64bit 的整数，16字节
image.png

  • 时间戳是初始时间与当前时间的差，最大间隔69年
  • 基本保持全局唯一，毫秒内并发最大4096个 ID
  • 时间回调可能引起 ID 重复
  • MyCat 和 Sharding-jdbc 均支持雪花算法
  • 5位机房 + 5位机器 最多可配置 2^10 个，也就是 1024 台机器

可以基于雪花算法改进，比如：
把10进制长整型，转为更高进制或自定义进制显示

优点：

  • 毫秒数在高位，自增序列在低位，整个 ID 都是趋势递增的。
  • 不依赖数据库，稳定性、性能都高
  • 可以根据业务特性自定义，灵活

缺点：

  • 强依赖机器时钟，如果机器上时钟回拨，会导致重复或者不可用。

  • 跨毫秒时，序列号总是归0，导致分库分表（取模）不均匀

    • 改进：序列号不是每次都归0，而是归一个随机数，然后再毫秒内累加

      数据库生成

      以MySQL举例，利用给字段设置auto_increment_increment和auto_increment_offset来保证ID自增，每次业务使用下列SQL读写MySQL得到ID号。
      1. begin;
      2. REPLACE INTO Tickets64 (stub) VALUES ('a');
      3. SELECT LAST_INSERT_ID();
      4. commit;
      优点：

  • 实现简单，利用现有数据库功能实现，成本小

  • ID 号单调自增，可以实现一些对 ID 有特殊需求的业务

缺点：

  • 强依赖 DB，当 DB 异常，整个系统不可用。
  • ID 发号性能瓶颈限制在单台 MySQL 的读写性能。
    • 改进：单点批量 ID 生成服务（服务重启会出现空洞，问题不大）
      • 无法水平扩展
        • 改进：使用 keepalived 添加备用服务

也可以使用 Redis 或其他数据库实现

落地实现

滴滴 Tinyid🏆

基于数据库
Tinyid是用Java开发的一款分布式id生成系统，基于数据库号段算法实现，关于这个算法可以参考美团leaf或者tinyid原理介绍。Tinyid扩展了leaf-segment算法，支持了多db(master)，同时提供了java-client(sdk)使id生成本地化，获得了更好的性能与可用性。Tinyid在滴滴客服部门使用，均通过tinyid-client方式接入，每天生成亿级别的id。
https://github.com/didi/tinyid

百度 UidGenerator🏆🏆

基于雪花算法
https://github.com/baidu/uid-generator
UidGenerator是Java实现的, 基于Snowflake算法的唯一ID生成器。UidGenerator以组件形式工作在应用项目中, 支持自定义workerId位数和初始化策略, 从而适用于docker等虚拟化环境下实例自动重启、漂移等场景。 在实现上, UidGenerator通过借用未来时间来解决sequence天然存在的并发限制; 采用RingBuffer来缓存已生成的UID, 并行化UID的生产和消费, 同时对CacheLine补齐，避免了由RingBuffer带来的硬件级「伪共享」问题. 最终单机QPS可达600万。

美团 Leaf

https://github.com/Meituan-Dianping/Leaf
支持雪花算法和数据库
Leaf 最早期需求是各个业务线的订单ID生成需求。在美团早期，有的业务直接通过DB自增的方式生成ID，有的业务通过redis缓存来生成ID，也有的业务直接用UUID这种方式来生成ID。以上的方式各自有各自的问题，因此我们决定实现一套分布式ID生成服务来满足需求。具体Leaf 设计文档见： leaf 美团分布式ID生成服务

目前Leaf覆盖了美团点评公司内部金融、餐饮、外卖、酒店旅游、猫眼电影等众多业务线。在4C8G VM基础上，通过公司RPC方式调用，QPS压测结果近5w/s，TP999 1ms。