聊聊几种分布式全局唯一ID生成方案

缘起

在分布式微服务体系架构下，有十分多的状况咱们需求生成一个大局仅有的 ID 来做标识，比方：

• 需求分库分表的状况下，分库或分表会导致表本事的自增键不具有仅有性。
• 较长的事务链路涉及到多个微服务之间的调用，需求一个仅有 ID 来标识比方订单 ID、消息 ID、优惠券 ID、分布式事务大局事务 ID。

关于大局仅有 ID 来说，通常具有以下特色：

• 大局仅有性：ID 不会重复，这个是大局仅有 ID 最基本的特性
• 趋势递加：考虑到相似 MySQL 数据存储是依据 B+ 树的聚簇索引，非趋势递加会导致写入功能受到影响。
• 单调递加：确保上一个 ID 的巨细必定小于下一个 ID，关于某些有排序需求的场景有必定的必要性，比方 IM 消息触到达端，或许便是单纯的有需求依据 ID 进行排序的需求。
• 信息安全：假如 ID 能够被简略的枚举出来，那么有潜在的数据安全问题。而且假如是订单号的场景，经过订单号的简略相减就预估出当天的订单量的话，会导致商业数据泄漏。

能够发现 1 是咱们必须去确保的，2 尽或许确保，3 和 4 必定程度上是互斥的，无法经过一个计划来实现。而且在这个根底上，大局仅有 ID 的生成需求做到高功能（TP999 的响应耗时要尽或许小）以及高安稳性（可用性 5 个 9）。

常见计划

通常来说大局仅有 ID 的生成计划也分几类：

• 单机自行生成，不依靠其他服务，来确保大局仅有性。
• 运用集群，运用服务的事务场景内确保大局仅有 ID。
• 独立服务供给通用的出产大局仅有 ID 的才能。

下面来详细介绍业界常见的一些计划：

UUID

UUID 是通用仅有识别码（Universally Unique Identifier）的缩写，开放软件基金会（OSF）规范定义了包含网卡MAC地址、时刻戳、姓名空间（Namespace）、随机或伪随机数、时序等元素。运用这些元素来生成 UUID。

UUID 一共有 5 个版别：

• 版别1 – 依据时刻的 UUID：主要依靠当时的时刻戳及机器 mac 地址，因而能够确保全球仅有性。
• 版别2 – 分布式安全的 UUID：将版别1的时刻戳前四位换为 POSIX 的 UID 或 GID，很少运用。
• 版别3 – 依据姓名空间的 UUID（MD5 版）：依据指定的姓名空间/姓名生成 MD5 散列值得到，规范不引荐。
• 版别4 – 依据随机数的 UUID：依据伪随机数，生成 16byte 随机值填充 UUID。重复机率与随机数产生器的质量有关。
• 版别5 – 依据姓名空间的 UUID（SHA1版）：将版别 3 的散列算法改为 SHA1。

大家多数状况下运用的是 v4 版别，Node.js 的 uuid 包支持所有版别的 uuid 生成。Java 的 UUID.randomUUID() 是依据 v4 版别，UUID.nameUUIDFromBytes() 是依据 v3 版别。

UUID 的优势：

• 本地生成，不依靠外部服务，生成的功能也还不错。

UUID 的劣势：

• v1 版别存在信息安全问题，直接将 mac 地址暴露出去，这个缝隙曾被用于寻找梅丽莎病毒的制作者位置。
• v3、v5 都是在命名空间 + 称号输入的状况下能够输出一致的 UUID，不适合用于仅有 ID 生成。
• v4 版别假如依据伪随机数，理论上会存在呈现重复的概率。
• 通常在数据库中存储为字符串，相比整型会花费更多存储空间。
• 字符串无法确保有序，在 MySQL 依据 B+ 树的聚簇索引结构下，写入功能不佳。

在一些简略场景下，关于功能的要求不严格，而且体系并发不高的状况下，运用 UUID 或许是最简略、最低本钱的计划。

数据库自增键

数据库主键自增这个是大家都十分了解的功用，在分库分表的场景下，依靠单表主键自增显然没法确保仅有性。但也并不是完全不能运用，比方一个一致的 ID 生成服务，背后建若干张 sequence 表专门用于 ID 的生成，每台机器对应不同的 sequence 表，而且每个 sequence 表设置不同的自增初始值和一致的自增步长，比方 2 台机器的状况下，一台自增初始值为 1，一台自增初始值为 2，自增步长都为 2，就相当于每台机器回来的是一个等差数列，且每台机器回来的等差数列之间不会重复。

这种计划满意的是趋势递加，但不是肯定的单调递加，一起也有显着的缺点：

• 扩展性较差，假如服务需求扩容，自增起始值和自增步长都需求全体重新设置。
• 强依靠数据库，数据库挂了整个服务不可用，且数据库的 IO 功能会成为整个服务的瓶颈。

但其实这些缺点并非无法处理，有一个 “批量发号” 思维的处理计划：

TDDL Sequence

这里经过介绍我司 TDDL Sequence 的计划来解说 “批量发号” 的思维。其实依然是自增初始值结合自增步长的思路，但核心思路是经过运用层来代理 ID 的自增。仅仅在数据库中记载当时场景的 ID 最大值，经过在运用侧设置了自增步长，每次经过数据库拿到当时场景的 ID 起始值，就在本地得到了一个“号段”，此时更新数据库记载当时最新的 ID 最大值，之后这个 “号段” 保护在内存中，ID 自增经过在内存中自增后直接回来，当这个 “号段” 耗费殆尽后，再重复之前的操作，得到一个新的号段。
举个比方，当时场景下，运用装备的自增步长为 1000，且当时数据库中 ID 最大值为 1000，那么第一次请求数据库，会将当时场景的 ID 最大值更新到 2000，并得到号段 [1000, 2000)，在这个区间内的自增 ID 悉数经过内存生成，当生成到 2000 的时分，再次请求数据库，将当时场景的 ID 最大值更新为 3000，并在内存中保护号段 [2000, 3000)。

CREATE TABLE `sequence` (
  `id` BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,
  `name` VARCHAR(64) NOT NULL,
  `value` BIGINT NOT NULL,
  `gmt_create` TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
  `gmt_modified` TIMESTAMP NOT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `uk_unique_name` (`name`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

但假如自增是在内存中执行的，是否会存在多台机器请求到同一 “号段” 导致呈现重复 ID 呢？这个部分是经过在请求数据库阶段的乐观锁实现的，因为当时机器确定运用这个号段前，会更新数据库当时最大 ID 值，经过乐观锁机制，假如拿老的最大 ID 值更新没有成功，意味着需求再去尝试取下一个 “号段”，直到成功更新数据库记载为止。这个过程的时序如下：

别的也不需求担心因为运用重启导致内存中保护号段丢掉的问题，因为发动后必定会请求一个新号段，仅仅或许会存在一些 ID 的糟蹋，但这个问题通常能够疏忽。

Leaf-segment

美团 Leaf-segment 的思路其实几乎和 TDDL Sequence 十分相似，不再额定阐明。不过针对号段耗费殆尽后会同步请求数据库，对功能 TP999 目标有必定影响，故其设计了 “双 Buffer优化” 计划，本质上便是在监控号段现已耗费到比方 20% 的状况下，就会提早经过异步的方式拉取下一个号段，防止号段耗费殆尽后的数据库 IO 对功能 TP999 目标的影响。

滴滴也曾开源了 tinyid，其生成 ID 的思维和上述计划几乎一致，就不再赘述。

类雪花算法

雪花算法是 Twitter 工程师提出的生成大局仅有 ID 的计划，它运用固定的 64 位二进制表明一个 ID，最后能够经过长整型的数据类型存储这个 ID。第一位为保存位，固定为 0，后面 41 位是 时刻戳位，表明当时时刻戳，那么算一下最多能够表明 （1L<<41）/(1000L*3600*24*365)=69 年的时刻，再后面 10 位是 机器标识位，能够分别表明 1024 台机器。最后的 12 位为 序列号位，或许是自增序列位，能够表明 4096 个 ID，理论上 snowflake 计划的 QPS 约为 409.6w/s，这种分配方式能够确保在任何一个 IDC 的任何一台机器在恣意毫秒内生成的 ID 都是不同的。
之所以标题叫 “类雪花算法”，原因是位数的分配，实践是能够自己调整的。比方单元化架构，多地分别有不同的机房，或许一个集群的机器数量超越了 1024 台，那么都能够依据实践状况去调整，比方需求单元化架构但一个运用的机器数量不或许超越 1024 台，那么能够将本来的 10 位机器位拿出两位来表明单元，8 位去标识机器。这个通常依据自己事务的实践状况能够灵活调整。
类雪花算法因为依靠本地时刻，会有一个知名的时刻回拨问题：

时刻回拨问题

所谓时刻回拨，即当时得到的本地时刻小于了之前获取的本地时刻，感觉时针被“回拨”了。那么什么状况下或许呈现时刻回拨问题呢？

• 人工设置
• NTP 网络时刻同步

人工设置的状况不多做解说，一般也很少产生。NTP 网络时刻同步是一个时刻同步协议，C/S 架构，服务器经过从威望设备（原子钟、GPS）获取到当时时刻后，一起考虑传输时刻差进行时刻校准后得到当时的准确时刻。首要咱们日常家用的时钟，包含机器上的时钟通常是石英原料，石英原料的时钟精度虽然能够满意家用，但实践存在差错，也就意味着经过网络时刻同步后的时刻或许会呈现回拨现象。
这里不得不说到闰秒问题，什么是闰秒？

为确定时刻，世界上有两种常用的时刻计量体系：依据地球自转的世界时（UT）和依据原子振荡周期的世界原子时（TAI）。因为两种测量方法不同，随着时刻推移，两个计时体系成果会呈现差异，因而有了和谐世界时的概念。 和谐世界时以世界原子时秒长为根底，在时刻上尽量接近世界时。1972年的世界计量大会决定，当世界原子时与世界时的时刻相差到达0.9秒时，和谐世界时就增加或减少 1 秒，以尽量接近世界时，这个修正被称作闰秒。

简略表达，便是地球自转速率自身不是一个安稳的值，为了磨平差错，世界时或许会呈现减少 1 秒的状况，而网络时刻同步又会去同步世界时，所以便产生了时刻回拨问题。
过去现已有几个知名的因为闰秒导致的毛病：2012 年实施闰秒时，引发了 Reddit 的大规模毛病，以及 Mozilla、LinkedIn、Yelp 和航空预订服务 Amadeus 的相关问题。2017 年，Cloudflare 的一个闰秒毛病使这家网络根底设备公司的一部分客户的服务器离线。
总之时刻回拨问题无法防止，关于强依靠本地时刻的计算，都需求考虑时刻回拨问题的处理。

闰秒将在 2035 年被取消，喜大普奔。

Leaf-snowflake

美团的 Leaf-snowflake 是依据雪花算法的 ID 生成计划，经过独立的集群服务对外供给才能，其机器标识位依靠 Zookeeper 生成，机器本地会备份一份成果用于 Zookeeper 的灾备。
首要记载上一次生成 ID 的时刻戳，假如本次的时刻戳还小于上次的，那么阐明产生时刻回拨，假如时刻误差较小，则等候这个时刻差过去，再进行生成，不然抛出异常拒绝服务，而且将当时机器剔除。

//产生了回拨，此刻时刻小于上次发号时刻
if (timestamp < lastTimestamp) {
    long offset = lastTimestamp - timestamp;
    if (offset <= 5) {
        try {
            //时刻误差巨细小于5ms，则等候两倍时刻
            wait(offset << 1);//wait
            timestamp = timeGen();
            if (timestamp < lastTimestamp) {
                //仍是小于，抛异常并上报
                throwClockBackwardsEx(timestamp);
            }    
        } catch (InterruptedException e) {  
            throw  e;
        }
    } else {
        //throw
        throwClockBackwardsEx(timestamp);
    }
}
//分配ID       

Seata UUID

Seata 的 UUID 生成器是依据雪花算法改进的，针对上述的时刻回拨问题进行了处理，一起也进一步突破了本来雪花算法的功能瓶颈。
时刻回拨问题本质是每次生成 ID 都会依靠本地时刻，Seata UUID 生成器改进成了仅在运用发动是记载当时的时刻戳，之后的出产就不再依靠，时刻戳位的更新改成了依靠序列号位的溢出，每次当序列号位溢出（即已到达 4096）后将时刻戳位进位。

这样的改动相当于即处理了时钟回拨问题，也突破了 4096/ms 的出产功能瓶颈，相当于有 53 位参加递加。

那么这样的改动是否有问题？因为在并发较高的状况下，会呈现 超前消费，消费速率超越 4096/ms 的状况下，时刻戳位的进位速度以及超越了当时时刻戳的值，那么这个时分运用重启再拿当时的时刻戳作为初始值，是否就会呈现大量重复 ID 的状况呢？没错，理论或许，但这个问题实践被 Seata 疏忽了，原因是假如真的继续是这样的 QPS，瓶颈不就不再 UUID 生成器了，Seata 服务自身就撑不住。

当然因为每次生成的 ID 对本地时刻不再是强依靠了，那么意味着这个 ID 在有限范围内是可被枚举的，不过因为是用在分布式事务的场景下，这个问题能够疏忽。

总结

假如场景简略，直接运用 UUID 即可。假如仅是因为数据量比较大，需求分库分表，那么相似 TDDL Sequence 的计划也完全满足。除此之外，需求详细问题详细分析：

• 假如仅有 ID 要落库，且可预见的会无限增长（比方是一个通用服务），需求一个定长 ID 来确保数据库字段长度的确定性，倾向于考虑类雪花算法的计划。
• 假如判断服务需求承载的并发较高，则最好不要考虑 UUID 的计划。
• 假如事务场景强依靠 ID 进行排序的，必须要求 ID 单调递加，则挑选类雪花算法的计划。