分布式ID

干货都在参考文献里,我只是总结了一下我自己吸收的。

分布式ID

分布式ID,可以理解为分布式系统的数据的唯一标识。概况起来,通常需要满足以下几个条件:

  • 唯一性
  • 有序
    对数据库中的数据按时间进行排序是很常见的需求,通常在表中有GMT_CREATE和GMT_MODIFIED字段,通过在这些字段上建立普通索引(non-cluster index),可以在一定程度上加快排序的速度。但相比聚集索引,普通索引的访问效率还是比较慢的,所以可以通过在主键上建立聚集索引来实现排序。
  • 有意义的
    比如,ID中可能会包含一些业务信息,用于标识所属业务
  • 可反解
    一个 ID 生成之后,就会伴随着信息终身,排错分析的时候,我们需要查验。这时候一个可反解的ID可以帮上很多忙,从哪里来的,什么时候出生的。就好比身份证,我们从身份证号上可以分析出这个人的出身年月。
常见方法
  • 使用数据库的auto_increment

    • 优点:
      • 简单
    • 缺点:

      • 只能满足唯一性和有序,不能生成有业务含义和需要可反解的ID
      • 可用性差,单机嘛,挂了就不可用了
      • 可扩展性差,ID生成是写操作,单个数据库的写性能是有限的,需要扩展,这种方案没啥可扩展性。
    • 改进方案:

      • 增加主库,避免写入单点,提高性能
      • 数据水平切分,保证各库生成的ID不重复
        aaa
        如图所示,可以增加2个库,每个库设置不同的ID起始值,以及相同的增长步长。这种方案虽然提高了可用性和可扩展性,保证了唯一性,但是不能保证有序,因为可能先调用了DB-0,生成0,3,然后调用DB-1生成1.
  • 批量ID生成服务
    数据库使用双master保证可用性,数据库中只存储当前ID的最大值,例如0。ID生成服务假设每次批量拉取6个ID,服务访问数据库,将当前ID的最大值修改为5,这样应用访问ID生成服务索要ID,ID生成服务不需要每次访问数据库,就能依次派发0,1,2,3,4,5这些ID了,当ID发完后,再将ID的最大值修改为11,就能再次派发6,7,8,9,10,11这些ID了,于是数据库的压力就降低到原来的1/6了。为了解决服务单点问题,增加了一个备用服务,当主服务挂掉时,备服务自动切换(业界应该有实现方案,我还不懂)。
    bbb
    • 优点:
      • 高可用
    • 缺点:
      • 只能满足唯一性和有序,不能生成有业务含义和需要可反解的ID
      • 如果服务挂了,服务重启起来之后,继续生成ID可能会不连续,中间出现空洞(服务内存是保存着0,1,2,3,4,5,数据库中max-id是5,分配到3时,服务重启了,下次会从6开始分配,4和5就成了空洞,不过这个问题也不大)。如果用的是高可用的第三方缓存来保存这些中间值,应该可以避免这个问题。
      • 性能有限,无法水平扩展。
  • UUID
    • 优点:
      • 简单
      • 快,无性能问题
    • 缺点
      • 只能保证唯一性(其实也不一定唯一,只是重复的概率很小[1]),其它都保证不了,没有业务含义,无序
      • 比较长,占用空间大。
  • 类snowflake算法
    snowflake是twitter开源的分布式ID生成算法,其核心思想是:一个long型的ID,使用其中41bit作为毫秒数,10bit作为机器编号,12bit作为毫秒内序列号。这个算法单机每秒内理论上最多可以生成1000*(2^12),也就是400W的ID,完全能满足业务的需求。

    借鉴snowflake的思想,结合各公司的业务逻辑和并发量,可以实现自己的分布式ID生成算法。比如可以在中间加入2个bit的业务标识等。具体位数要怎么安排需根据具体业务要求来计算。如果要达到精确的有序,就要对 Sequence 进行并发控制,性能上肯定会打折。所以经常会有的一个选择就是,在这个秒的级别上不再保证顺序,而整个 ID 则只保证时间上的有序,也叫做K-sorted。后一秒的 ID肯定比前一秒的大,但同一秒内可能后取的ID比前面的号小。
    这里有个需要注意的地方是,就是分配给time的bit位数,这个time使用的单位有关系。那时间用秒还是毫秒呢?其实不用毫秒的时候就可以把空出来的10bit 送给 Sequence,但整个ID 的精度就下降了。峰值速度是更现实的考虑。Sequence 的空间决定了峰值的速度,而峰值也就意味着持续的时间不会太久。这方面,每秒100万比每毫秒1000限制更小。
参考:

[1] Universally unique identifier
[2] 细聊分布式ID生成方法
[3] 业务系统需要什么样的ID生成器
[4] Introducing Icicle: a distributed, k-sortable unique ID generation system using Redis and Lua
[5] 基于redis的分布式ID生成器
[6] Sharding & IDs at Instagram
[7] MySQL :: There is a Sequence to Generate Unique Value for Sharding Key
[8] OneProxy :: 如何生成生成分库分表下的主键值?可以使用分布式Sequence服务!