一、为什么需要全局唯一ID？

传统的单体架构的时候，我们基本是单库然后业务单表的结构。每个业务表的ID一般我们都是从1增，通过AUTO_INCREMENT=1设置自增起始值，但是在分布式服务架构模式下分库分表的设计，使得多个库或多个表存储相同的业务数据。这种情况根据数据库的自增ID就会产生相同ID的情况，不能保证主键的唯一性。

二、分布式 ID 解决方案

2.1、UUID

UUID （Universally Unique Identifier），通用唯一识别码的缩写。UUID是由一组32位数的16进制数字所构成，所以UUID理论上的总数为 16^32=2^128，约等于 3.4 x 10^38。也就是说若每纳秒产生1兆个UUID，要花100亿年才会将所有UUID用完。

  • UUID 种类

    • 基于时间的UUID - 版本1： 这个一般是通过当前时间，随机数，和本地Mac地址来计算出来，可以通过 org.apache.logging.log4j.core.util包中的 UuidUtil.getTimeBasedUuid()来使用或者其他包中工具。由于使用了MAC地址，因此能够确保唯一性，但是同时也暴露了MAC地址，私密性不够好。
    • DCE安全的UUID - 版本2 DCE（Distributed Computing Environment）安全的UUID和基于时间的UUID算法相同，但会把时间戳的前4位置换为POSIX的UID或GID。这个版本的UUID在实际中较少用到。
    • 基于名字的UUID（MD5）- 版本3 基于名字的UUID通过计算名字和名字空间的MD5散列值得到。这个版本的UUID保证了：相同名字空间中不同名字生成的UUID的唯一性；不同名字空间中的UUID的唯一性；相同名字空间中相同名字的UUID重复生成是相同的。
    • 随机UUID - 版本4 根据随机数，或者伪随机数生成UUID。这种UUID产生重复的概率是可以计算出来的，但是重复的可能性可以忽略不计，因此该版本也是被经常使用的版本。JDK中使用的就是这个版本。
    • 基于名字的UUID（SHA1） - 版本5 和基于名字的UUID算法类似，只是散列值计算使用SHA1（Secure Hash Algorithm 1）算法。

  • 使用UUID作为分布式ID缺点

    • 不易于存储：UUID太长，16字节128位，通常以36长度的字符串表示，很多场景不适用。 信息不安全：基于MAC地址生成UUID的算法可能会造成MAC地址泄露，暴露使用者的位置。
    • 对MySQL索引不利：如果作为数据库主键，在InnoDB引擎下，UUID的无序性可能会引起数据位置频繁变动，严重影响性能，可以查阅 Mysql 索引原理 B+树的知识。

2.2、数据库生成

  • 生成策略

由于分布式数据库的起始自增值一样所以才会有冲突的情况发生，那么我们将分布式系统中数据库的同一个业务表的自增ID设计成不一样的起始值，然后设置固定的步长，步长的值即为分库的数量或分表的数量。


以MySQL举例，利用给字段设置auto_increment_increment和auto_increment_offset来保证ID自增。
auto_increment_offset：表示自增长字段从那个数开始，他的取值范围是1 .. 65535。
auto_increment_increment：表示自增长字段每次递增的量，其默认值是1，取值范围是1 .. 65535。可以根据分配多少库来定义，定义了三个库则设置为3
image.png

  • 缺点
    • 强依赖DB
    • 数据一致性在特殊情况下难以保证
    • ID发号性能瓶颈限制在单台MySQL的读写性能

2.3、Redis 生成

Redis实现分布式唯一ID主要是通过提供像 INCR 和 INCRBY 这样的自增原子命令，由于Redis自身的单线程的特点所以能保证生成的 ID 肯定是唯一有序的。

缺点

  • 单机存在性能瓶颈，无法满足高并发的业务需求
  • 使用集群，也需要设置分段和步长来实现，避免不同实例生成重复ID
  • 为了避免长期自增后数字过大可以通过与当前时间戳组合起来使用

Redis 实现分布式全局唯一ID，它的性能比较高，生成的数据是有序的，对排序业务有利，但是同样它依赖于redis，需要系统引进redis组件，增加了系统的配置复杂性。

2.4、雪花算法（SnowFlake）

  • 介绍

Snowflake，雪花算法是由Twitter开源的分布式ID生成算法，以划分命名空间的方式将 64-bit位分割成多个部分，每个部分代表不同的含义。而 Java中64bit的整数是Long类型，所以在 Java 中 SnowFlake 算法生成的 ID 就是 long 来存储的。

  • 组成结构

    • 第1位占用1bit，其值始终是0，可看做是符号位不使用。
    • 第2位开始的41位是时间戳，41-bit位可表示2^41个数，每个数代表毫秒，那么雪花算法可用的时间年限是(1L<<41)/(1000L360024*365)=69 年的时间。
    • 中间的10-bit位可表示机器数，即2^10 = 1024台机器，但是一般情况下我们不会部署这么台机器。如果我们对IDC（互联网数据中心）有需求，还可以将 10-bit 分 5-bit 给 IDC，分5-bit给工作机器。这样就可以表示32个IDC，每个IDC下可以有32台机器，具体的划分可以根据自身需求定义。
    • 最后12-bit位是自增序列，可表示2^12 = 4096个数。

分布式解决方案之分布式ID - 图2

  • ID 生成过程

    • 1、获取系统时间戳
    • 2、判断是否出现系统时间回拨问题，是则及时抛出异常，避免生成重复ID
    • 3、计算当前毫秒的序例号，如果当前序例号溢出，则需要重新获取时间戳
    • 4、将时间戳 + 工作机器ID + 序列号 拼接

  • 雪花算法时钟回拨问题

2.5、滴滴出品（TinyID）

2.5.1、原理介绍

tinyid是基于数据库发号算法实现的，简单来说是数据库中保存了可用的id号段，tinyid会将可用号段加载到内存中，之后生成id会直接内存中产生。

可用号段在第一次获取id时加载，如当前号段使用达到一定量时，会异步加载下一可用号段，保证内存中始终有可用号段。

(如可用号段1~1000被加载到内存，则获取id时，会从1开始递增获取，当使用到一定百分比时，如20%(默认)，即200时，会异步加载下一可用号段到内存，假设新加载的号段是1001~2000,则此时内存中可用号段为200~1000,1001~2000)，当id递增到1000时，当前号段使用完毕，下一号段会替换为当前号段。依次类推。

2.5.2、db 号段算法

  • 数据表设计 | id | biz_type | max_id | step | version | | —- | —- | —- | —- | —- | | 1 | 1000 | 2000 | 1000 | 0 |

  • 这里我们增加了biz_type，这个代表业务类型，不同的业务的id隔离

  • max_id则是上面的end_id了，代表当前最大的可用id
  • step代表号段的长度，可以根据每个业务的qps来设置一个合理的长度
  • version是一个乐观锁，每次更新都加上version，能够保证并发更新的正确性

2.5.3、简单架构图

image.png

2.5.4、简单架构的问题

  • 当id用完时需要访问db加载新的号段，db更新也可能存在version冲突，此时id生成耗时明显增加
  • db是一个单点，虽然db可以建设主从等高可用架构，但始终是一个单点
  • 使用http方式获取一个id，存在网络开销，性能和可用性都不太好

2.5.5、优化

  • 双号段缓存

对于号段用完需要访问db，我们很容易想到在号段用到一定程度的时候，就去异步加载下一个号段，保证内存中始终有可用号段，则可避免性能波动。

  • 增加多db支持 | id | biz_type | max_id | step | delta | remainder | version | | —- | —- | —- | —- | —- | —- | —- | | 1 | 1000 | 2000 | 1000 | 2 | 0 | 0 |

delta代表id每次的增量，remainder代表余数，例如可以将A，B都delta都设置2，remainder分别设置为0，1则，A的号段只生成偶数号段，B是奇数号段。 通过delta和remainder两个字段我们可以根据使用方的需求灵活设计db个数，同时也可以为使用方提供只生产类似奇数的id序列。

  • 增加tinyid-client
    • 提供本地客户端，向服务端获取可用号段
    • 在本地也构建双号段、id生成，提高性能

2.5.6、最终架构

image.png

  • tinyid提供http和tinyid-client两种方式接入
  • tinyid-server内部缓存两个号段
  • 号段基于db生成，具有原子性
  • db支持多个
  • tinyid-server内置easy-router选择db

2.6、百度 （Uidgenerator）

2.7、美团（Leaf）

2.7.1、Leaf-segment 数据库方案

2.7.2、Leaf-snowflake方案

Leaf-snowflake方案完全沿用 snowflake 方案的bit位设计，对于workerID的分配引入了Zookeeper持久顺序节点的特性自动对snowflake节点配置 wokerID。避免了服务规模较大时，动手配置成本太高的问题。

  • 时间回拨问题处理

分布式解决方案之分布式ID - 图5

参考