分布式ID生成器

需求

在日常的开发中,我们会遇到很多需要id标识某一条数据。例如订单(orderId)、消息(msgId)等等。这样的id需要满足以下两个条件

  • 趋势递增
  • 全局唯一

下面梳理一下技术实现思路,以及优缺点。

database

自增键/自增列

  • 优点
    简单,能保持唯一性和递增性

  • 缺点

    • 可用性难以保证,存在单点问题。现在的数据库架构一般是一主多从,主库负责写,从读负责读,主库挂了就完了。
    • 难扩展,性能有限,id生成的性能上限取决于主库的写性能,如果到达瓶颈,很难扩展。

改进 1

冗余主库,每个主库设置不同的起点,相同的步长。

  • 优点
    解决了写入单点问题,提高了可用性

  • 缺点

    • 失去了绝对递增。可能请求一返回库一的1,3,请求二返回了库二的2,4,(很多情况下并不算是问题)
    • 每个id都写库,性能上还是有瓶颈,难以水平扩展。

改进 2

批量生成id,数据库中保存目前分配出去的最大值。使用双主库保证可用性。

  • 优点
    性能较好,绝对递增,每秒可生成几万个。

  • 缺点

    • 服务单点
    • 服务挂了会出现空洞(当前申请最大id是100,当分配到50时宕机,服务重启后从100开始发号,则51-100号成了空洞,一般情况下也不算是问题)
    • 虽然性能较好,难以水平扩展。

UUID

  • 优点
    本地生成,性能非常好,可以生成全球唯一的id

  • 缺点
    一般是字符串(可以将UUID转成Long),存储空间大,无递增特性

redis

incr()或者使用集群,设置不同的起点调用incrby相同的步长。

  • 优点
    简单,性能比数据库好
  • 缺点
    需要引入Redis依赖,提升了系统的复杂度。同时redis的配置运维成本提升。

类Snowflake

long有64位bite,第一位保持为0,使生成的id均为正数,剩下的63位可以浮动利用。
现在假设按照如下表格划分,可使用 1L<<41/(3600 * 1000 * 8760) = 69.7年,可使用2^10 = 1024台机器,可以产生2^12 = 4096个序列,综合计算可产生2^10 * 2^12 = 400W个id/毫秒。

1 41 10 12
0 时间戳 机器号 序列号
  • 时间戳:生成号码的时间到基准时间间隔的毫秒数,基准时间不一定是19700101,可以自定义为当前时间,也就是在41bit的设置下,从现在开始可以使用69.7年,并非2040年(1970+70)后就不能用了。
  • 机器号:可以在服务启动的时候,使用mac地址在mysql中查找,如果没有则将当前机器注册到mysql中,使用mysql的自增主键。可以是多进程,使用进程号。
  • 序列号:可以使用AtomicLong原子类,无锁性能好,在跨毫秒时,序列号总是归0,会使得序列号为0的ID比较多,导致生成的ID取模后不均匀,所以序列号不是每次都归0,而是归一个0到9的随机数。

图片引用自网络
注:图片引用自网络

  • 优点
    • 时间戳在高位,自增序列在低位,保证趋势递增
    • 可自由分配bit位,非常灵活
  • 缺点
    • 每个服务器的时钟不可能绝对一致,单台服务器可以生成绝对递增的id,但是整个集群只能生成趋势递增的id。
    • 时钟回拨可能生成重复id/不可用

改进

正因为强依赖时钟,类Snowflake方案都会有时钟问题,当出现时钟回拨,可能重复发号。NTP服务器使计算机对其服务器或时钟源做同步化,它可以提供高精准度的时间校正(LAN上与标准间差小于1毫秒,WAN上几十毫秒)
这里需要关注两个问题

  1. 如何感知时钟回拨?

    • 服务启动检查

      服务启动时,获取运行中的机器的平均时间arg,设定可容忍的误差值offset,如果abs(now()-arg<offset我们就认为当前时间准确,启动成功,否则启动失败告警。

    • 服务运行中

      记录上一分配了id的毫秒lastTimestamp,发号时判断系统时间不能小于前者

  2. 回拨后处理方案?

    如果发生了回拨,可以根据业务需求选择不同的处理方式

    • 阻塞等待等时间追上
    • 重试告警
    • 摘除本身节点告警

参考

Leaf——美团点评分布式ID生成系统

作者: wuzhaoyang(John)
出处: http://wuzhaoyang.me/
因为作者水平有限,无法保证每句话都是对的,但能保证不复制粘贴,每句话经过推敲。希望能表达自己对于技术的态度,做一名优秀的软件工程师。