分布式ID生成方案

分布式项目ID生成是头等问题

方案一:UUID

组成:日期时间、时钟序列、机器码
优点:

  • 简单,ID独立不易冲突
    缺点:
  • 长度128bit,占用空间多,无序
  • 数据库主键索引一般都是有序的,导致数据库入库压力大。只能作为逻辑主键。对MySQL索引不利
  • Join操作性能比int要低。主键索引性能降低
  • 基于MAC地址生成UUID的算法可能会造成MAC地址泄露

方案二:集中式ID生成器

传统全局生成ID

数据库建一张序列表,每次+1更新入数据库表。或者+100(缓存越大,生成效率越高,当系统关闭时,可能造成的ID浪费也会更多。对于Oracle集中式数据库,应用服务在分布式集群环境下,其他服务器可能也获取了100个id,不能保证多服务器数据入库顺序。对于不需要保证ID完全按入库时间有序的系统还是可以用的,比如Mysql分表分库,还可以保证多个库中的ID不冲突。如果每次+1也就可以支持分布式集群但是性能大打折扣。使用号码段缓存只能保证单台服务器id按时间单调有序。用到的时候才去取ID,而不是启动的时候就去取避免浪费)
频繁访问数据库性能瓶颈

利用数据库自增

1
2
3
4
begin;
REPLACE INTO Tickets (stub) VALUES ('TB1');
SELECT LAST_INSERT_ID();
commit;

数据库强关联,如果两台机器可以把步长设置成2,server1(1,3,4),server2(2,4,6)…
系统水平扩展比较困难,如果要40台电脑怎么办,id没办法单调递增,只能趋势递增,数据库压力大

Redis,ZooKeeper

Redis,ZooKeeper,记录最后分配的ID。

假如一个集群中有5台 Redis。可以初始化每台 Redis 的值分别是1, 2, 3, 4, 5,然后步长都是 5,提高吞吐量。

这种方式最大的缺点是复杂性太高,需要严重依赖第三方服务,而且代码配置繁琐。一般来说,越是复杂的方案,越不可靠,并且测试越痛苦

方案三:利用数据库的自增ID

从1开始,基本可以做到连续递增。Oracle可以用SEQUENCE,MySQL可以用主键的AUTO_INCREMENT,虽然不能保证全局唯一,但每个表唯一,也基本满足需求。

数据库自增ID的缺点是数据在插入前,无法获得ID。数据在插入后,获取的ID虽然是唯一的,但一定要等到事务提交后,ID才算是有效的。有些双向引用的数据,不得不插入后再做一次更新,比较麻烦。
优点:数据库自动编号,速度快,而且是增量增长,按顺序存放,对于检索非常有利,数字型,占用空间小,易排序,在程序中传递也方便
缺点:新老系统集成,导入数据容易冲突。分布式存储表,不同数据库都是自增的会导致主键冲突。

方案四:Snowflake算法

它给每台机器分配一个唯一标识,然后通过时间戳+标识+自增实现全局唯一ID。这种方式好处在于ID生成算法完全是一个无状态机,无网络调用,高效可靠。缺点是如果唯一标识有重复,会造成ID冲突。

生成的全局ID整体上是呈自增趋势的,也就是说整体是粗略有序的。高性能,能快速产生ID。以根据业务需求在前缀或后缀拼接业务标志位

缺点:

  • 由于“没有一个全局时钟”,每台服务器分配的ID是绝对递增的,但从全局看,生成的ID只是趋势递增的(有些服务器的时间早,有些服务器的时间晚)
  • 强依赖机器时钟,如果机器上时钟回拨,会导致发号重复或者服务会处于不可用状态。

方案五:美团Leaf

业务系统对ID号的要求:
全局唯一性:不能出现重复的ID号,既然是唯一标识,这是最基本的要求。
趋势递增:在MySQL InnoDB引擎中使用的是聚集索引,由于多数RDBMS使用B-tree的数据结构来存储索引数据,在主键的选择上面我们应该尽量使用有序的主键保证写入性能。
单调递增:保证下一个ID一定大于上一个ID,例如事务版本号、IM增量消息、排序等特殊需求。
信息安全:如果ID是连续的,恶意用户的扒取工作就非常容易做了,直接按照顺序下载指定URL即可;如果是订单号就更危险了,竞对可以直接知道我们一天的单量。所以在一些应用场景下,会需要ID无规则、不规则。
延迟低
可用性99.999%
高QPS

按号码段获取

biz,max_id,step,desc,update_time
step:只能保证单台服务器获取的id号码单调有序,可以保证单台服务器性能,多台服务器间不能通过序号来判断先后顺序,可能有的服务器获取了100个号码1个小时才用完,另一个服务器1分钟就用完了(server1:10-100,server2 100-200,可能server1已经用到50,server用到170,实际消耗顺序可能是51,171,52,172 整体没办法按时间有序。如果每次取都只+1可以保证发号服务器发出的有序,server1跟server2直接如果时间业也是同步的一般不会出现顺序问题,如果时间不同步也是会出现两个库中id没有按时间递增,但是实际上id是递增的,是server1跟server2的问题)

双buffer优化
不需要在DB取号段的时候阻塞请求线程,即当号段消费到某个点时就异步的把下一个号段加载到内存中.

leaf高可用容灾
主从。MySQL Group Replication,

靠zookeeper实现workerId的自动化租用。弱依赖zk,本机文件系统上缓存一个workerID文件

通过算法解决了时钟回拨问题

forever时间跟zk中最近保存的时间比较,发现有时钟回拨之后自动摘除本身节点并报警

Leaf-snowflake方案

避免大致计算出公司一天的订单量。