分布式唯一ID生成讲解

更新于 2024-12-19 分类于 Other-Technologies Waline：阅读次数：本文字数： 3.6k 阅读时长 ≈ 18 分钟

分布式唯一ID生成讲解

简介

在现在的系统设计中，多节点分布式的架构设计已经成为必然，数据会在多个节点上进行存储和处理，就需要能够生成分布式唯一ID，否则会带来数据冲突问题。本文会介绍UUID、雪花算法（Snowflake）以及Seata中的IdWorker共计三种分布式唯一ID的生成方法，并对会它们的原理进行讲解。

UUID

UUID（通用唯一识别码，Universally Unique Identifier）是一种由数字和字母组成的 128 位标识符，UUID 通常表示为 32 个十六进制数字，以-字符分隔成 5 个部分，形式为8-4-4-4-12（表示数字个数），例如：9c84bb00-995b-463f-9d33-96af0d5d85ce。

UUID有多种版本，每种版本的生成方式不同，在java.util.UUID 类提供了生成和操作UUID的方法，采用的是第四版本的UUID，它采用完全随机生成的形式来进行ID的生成。

优点

唯一性：UUID 的 128 位长度和复杂的生成算法保证了其在全球范围内的唯一性，几乎不可能出现重复的情况。
独立性：不依赖于中心服务器或数据库，任何设备在任何时间都可以独立生成 UUID，无需与其他系统进行交互，这使得它在分布式系统中具有很好的适用性。
简单性：生成算法相对简单，不需要复杂的配置或外部依赖，易于实现和使用。

缺点

占用空间大：128 位的长度相对较长，在存储和传输过程中会占用较多的空间，对系统的存储和性能可能会产生一定的影响。
无序性：除了基于时间的 UUID 版本（版本一）外，大多数 UUID 是随机生成的，没有内在的顺序。

在实际情况中，因为UUID 版本四生成快速、简单、安全等原因，UUID 版本四更为常用，但是他带来了一个很大的问题，ID无序性，所以一般数据规模比较大的业务不会使用UUID来进行ID的生成。

有序的 ID 可以使数据库中的索引更加紧凑和高效。例如，在 B+ 树索引中，有序的 ID 可以按照顺序依次插入，减少索引的分裂和合并操作，提高索引的查询速度和插入性能。

Snowflake

雪花算法（Snowflake）是由Twitter 开源的一种高效的分布式唯一 ID 生成算法，Snowflake算法生成的 ID 是一个 64 位的长整型数字，其结构通常为：1 位符号位（恒为0） + 41 位时间戳 + 10 位工作机器 ID + 12 位序列号。

时间戳：41 位时间戳用于记录 ID 生成的时间，精确到毫秒。它可以表示的时间范围大约是 69 年，从某个固定的起始时间开始，随着时间的推移，时间戳不断递增。
工作机器 ID：10 位工作机器 ID 用于标识分布式系统中的不同工作机器或节点。这意味着最多可以支持 1024 个不同的工作机器同时生成 ID。
序列号：12 位序列号用于在同一毫秒内对不同的 ID 进行区分。在同一毫秒内，每个工作机器可以生成最多 4096 个不同的 ID。

雪花算法的生成当中采用了时间戳作为其中的一部分，这是雪花算法能够生成有序递增ID的重要原因，由于采用了时间戳作为其中的一部分，所以还需解决时间回拨问题；

同时它引入了工作机器ID用来标识系统中的每一台机器，在雪花算法的组成当中，因为引入了工作机器ID作为其中的一部分，这使得集群中不同的节点生成的ID是绝对不可能相同的，将分布式唯一ID的生成问题转化为了单节点上局部唯一ID的生成问题。

优点

唯一性：通过时间戳、工作机器 ID 和序列号的组合，能够在分布式系统中保证生成的 ID 具有全局唯一性。
有序性：由于时间戳是单调递增的，所以生成的 ID 在一定程度上也是有序的。
灵活性：可以根据实际需求调整工作机器 ID 和序列号的位数，以适应不同的系统规模和性能要求。

缺点

ID 分配管理复杂：在分布式系统中，需要为每个工作机器分配唯一的工作机器 ID。当系统规模较大，节点数量众多时，工作机器 ID 的分配和管理会变得复杂且容易出错。如果工作机器 ID 分配不当，出现重复的工作机器 ID，就会导致生成的 ID 出现冲突。
突发性能有上限：在雪花算法中，12 位序列号用于在同一毫秒内对不同的 ID 进行区分，每个工作机器在同一毫秒内可以生成最多 4096，在秒杀场景中，大量请求会在同一时间到达，当同一毫秒内生成数量达到上限时，会自旋等待下一个时间戳，雪花算法号称QPS能达到400W（万）/s，但是严格上来说是4096/ms。
时钟敏感：因为ID生成总是和当前操作系统的时间戳绑定的(利用了时间的单调递增性)，因此若操作系统的时钟出现回拨，生成的ID就会重复（服务器会有偶发的”时钟漂移”现象）。

Seata中的IdWorker

Seata的1.4版本以前，Seata内的ID生成器io.seata.common.util.IdWorker的实现基于标准版的雪花算法，在1.4版本以后针对雪花算法进行了一定的优化改良，很好地解决了雪花算法中的2个问题。

时钟敏感问题：ID的生成解除与操作系统时间戳的时刻绑定，生成器只在初始化时获取了系统当前的时间戳，作为初始时间戳，但之后就不再与系统时间戳保持同步了。它之后的递增，只由序列号的递增来驱动。比如序列号当前值是4095，下一个请求进来，序列号+1溢出12位空间，序列号重新归零，而溢出的进位则加到时间戳上，从而让时间戳+1。
突发性能有上限：因为ID的生成解除与操作系统时间戳的时刻绑定，所以对于同一毫秒内生成的ID数量不在有限制，ID的生成数量不在受到同一毫秒只能生成4096个的影响。

Seata生成的ID结构如下：

可以看出相Seata生成的ID结构较于雪花算法来说，时间戳和节点ID换了位置，这样时间戳和序列号在内存上是连在一块的，在实现上就很容易用一个AtomicLong来同时保存它俩，但也造成了ID非全局有序的问题。

Seata中ID的生成解除与操作系统时间戳的时刻绑定，这是一把双刃剑，他的好处是不限制同一毫秒内ID的生成，但是这属于「超前消费」，会不会使得生成器内的时间戳大大超前于系统的时间戳，从而在重启时造成ID重复？理论上如此，但实际几乎不可能。一方面需要系统QPS得持续稳定在400w/s之上，另一方面机器重启恢复也需要时间，同时Seata也做了兜底策略。

/**
 * get next UUID(base on snowflake algorithm), which look like:
 * highest 1 bit: always 0
 * next   10 bit: workerId
 * next   41 bit: timestamp
 * lowest 12 bit: sequence
 * @return UUID
 */
public long nextId() {
    waitIfNecessary();
    long next = timestampAndSequence.incrementAndGet();
    long timestampWithSequence = next & timestampAndSequenceMask;
    return workerId | timestampWithSequence;
}

/**
 * block current thread if the QPS of acquiring UUID is too high
 * that current sequence space is exhausted
 * 如果获取 UUID 的 QPS 过高，导致当前序列空间耗尽，则阻塞当前线程
 * 这使得同一毫秒内的QPS能够高于4096/ms，但当QPS大于400W/s时会阻塞5毫秒，解决超前消费的问题
 */
private void waitIfNecessary() {
    long currentWithSequence = timestampAndSequence.get();
    long current = currentWithSequence >>> sequenceBits;
    long newest = getNewestTimestamp();
    if (current >= newest) {
        try {
            Thread.sleep(5);
        } catch (InterruptedException ignore) {
            // don't care
        }
    }
}

优点

唯一性：通过时间戳、工作机器 ID 和序列号的组合，能够在分布式系统中保证生成的 ID 具有全局唯一性。
高性能：ID生成速率不再受限于4096/ms

缺点

ID 分配管理复杂：同雪花算法。
无序性：相较于雪花算法，将时间戳和节点ID换了位置，导致生成的ID不再全局有序递增。

可以参考Seata中生成ID的思维，但不采用将时间戳和节点ID换位置的方式实现，就能够解决无序性的问题，但会给编码带来一些难度。