分布式ID生成方案

分布式项目ID生成是头等问题。
互联网应用中,某个表可能要占用很大的物理存储空间,为了解决该问题,使用数据库分片技术。将一个数据库进行拆分,通过数据库中间件连接。如果数据库中该表选用ID自增策略,则可能产生重复的ID,此时应该使用分布式ID生成策略来生成ID。还有在分布式系统中,经常需要对大量的数据、消息、http请求等进行唯一标识。例如:在分布式系统之间http请求需要唯一标识,调用链路分析的时候需要使用这个唯一标识。这个时候数据自增主键已经不能满足需求,需要一个能够生成全局唯一ID的系统。在美团点评的金融、支付、餐饮、酒店、电影等产品的系统中需要唯一ID标识一条数据或者消息,还有如订单、骑手、优惠券也都需要有唯一ID做标识。

分布式ID基本要求:全局唯一、趋势递增、信息安全、高性能、高可用

  • 全局唯一:不能重复出现ID号,这是基本要求
  • 趋势递增:很多时候但做主键用,MySQL数据库InnoDB,对应BTree数据自增顺序写入,存取效率最高,b+树结构不好经常被打乱重塑,单调递增:保证下一个ID一定大于上一个ID,例如事务版本号、IM增量消息、排序等特殊需求。
  • 信息安全: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,虽然不能保证全局唯一,但每个表唯一,也基本满足需求,缺点就是依赖Oracle。

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

优化方案,MySQL1设置起始值1,步长2,MySQL2设置起始2,步长2
优点:简单,保持定长增量,单表唯一
缺点:高并发性能不佳,水平扩展困难

方案四:Snowflake算法

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

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

精读问题,mysql中bigint可以存储下,其他应用可以程序转换成字符串提供给其他应用。

缺点:

  • 由于“没有一个全局时钟”,每台服务器分配的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方案

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

其他方案

Instagram
MongoDB
滴滴Tinyid方案
百度uid-generator方案

扩展

分库分表方式

  • 垂直切分
    • 垂直分库、垂直分表。垂直分库就是根据业务耦合性,将关联度低的不同表存储在不同的数据库,垂直分表是根据数据库中的列进行拆分,如果某个表字段比较多,可以通过新建一张扩展表,将不常用字段或者长度较大的字段分到扩展表中
  • 水平切分
    • 库内分表、分库分表。库内分表是在同一个库内,将某一个表拆分成几个小表,库内分表只解决了单一表数据量过大的问题,但没有将表分到不同机器的库上,因此并不减轻MySQL数据库的压力,最好通过分库分表来解决。

分库分表问题

  • 事务一致性问题
  • 跨节点join,解决方法:全局表、字段冗余、多次查询数据组装、分片
  • 跨节点分页、排序、函数,解决方法:在不同节点排序,汇总再排序
  • 全局ID避免重复