分布式主键算法

一、引言

   分布式主键算法的产生背景主要在于分布式系统的需求。在分布式系统中，由于多个节点同时进行操作，需要有一种机制来确保全局唯一性，避免发生冲突。这种机制就是分布式主键算法。
   在互联网行业中，新开的项目基本都需要进行分库分表，这就需要在不同的表或库中生成的ID都是全局唯一的。此外，对于大型互联网应用来说，除了数据库表的分片外，还需要考虑如何设计能支持高并发、高可用性的分布式系统。
   在这种情况下，分布式主键算法就变得非常重要。它们可以生成全局唯一的ID，这些ID不仅可以在多个表或库之间进行区分，还可以用于构建分布式系统的唯一标识符。

二、常见算法介绍

雪花算法（Snowflake Algorithm）

特性

简单高效：雪花算法是一种相对简单且高效的算法，易于实现。
全局唯一：生成的ID在分布式环境中是全局唯一的。
有序性：ID的生成是有序的，有助于提高数据库索引性能。

详解

   雪花算法将一个64位的整数ID分为三个部分：时间戳、机器ID和序列号。其中，时间戳占用了41位，机器ID占用了10位，序列号占用了12位。算法的工作原理如下：
   时间戳部分记录了生成ID的时间，通常是从系统启动时开始计算的毫秒数。这意味着雪花算法可以在69年内生成不重复的ID。
机器ID标识了不同的分布式节点，最多可以有1024个不同的节点。
   序列号部分用于确保在同一毫秒内生成的ID不会重复。如果在同一毫秒内生成多个ID，序列号部分会自增。
这三个部分的组合确保了雪花算法生成的ID在分布式环境中是唯一且有序的。

优势

高性能：雪花算法生成ID的性能很高，适用于高吞吐量的系统。
相对简单：算法本身相对简单，不需要依赖外部服务。

劣势

时钟同步性要求：算法依赖于时钟同步，如果系统时钟回退可能导致ID重复。
有限的机器ID数：机器ID的位数限制了可分配的机器数量。

UUID（Universally Unique Identifier）

特性

全球唯一：UUID是全球唯一的，不同系统生成的UUID也不会冲突。
分散性：UUID的生成不需要中心化控制，各个节点可以独立生成。

详解

   UUID是128位的全局唯一标识符，通常表示为36个字符的字符串。它的生成不依赖于中心化控制，可以在不同的系统中生成。UUID的生成通常基于随机数或基于MAC地址和时间戳等信息。由于其全局唯一性，UUID在跨系统集成和数据交换中很有用。

优势

全局唯一性：UUID在全球范围内保持唯一。
无需中心化服务：不需要依赖中心化的ID生成服务。

劣势

较大的存储空间：UUID通常是128位的，相比于64位的雪花ID，占用更多的存储空间。
不适合按时间排序：UUID的生成不依赖于时间戳，因此不适合按时间排序的场景。

数据库自增主键

特性

数据库依赖：生成主键依赖于数据库的自增主键机制。
顺序性：生成的主键是有序递增的，有助于提高数据库性能。

详解

   在关系型数据库中，可以使用自增主键列来生成唯一标识符。这种方法需要确保分布式系统中不同节点使用不同的数据库，并且需要数据库引擎的支持。数据库自增主键通常是整数或长整数，它们在插入新数据时会自动递增，保证了唯一性和顺序性。

优势

可靠性：数据库自增主键是数据库引擎控制的，保证了唯一性。
易于维护：不需要额外的分布式算法，易于维护和管理。

劣势

数据库压力：高并发情况下，数据库可能成为性能瓶颈。
不适用于多数据库：在多个数据库实例上生成唯一ID可能需要复杂的配置。

分布式数据库的序列（Sequence）

特性

数据库依赖：依赖于支持序列对象的分布式数据库。
顺序性：生成的序列号是有序的。

详解

   一些分布式数据库（如Oracle）支持序列对象，可以用来生成全局唯一的序列号。这种方法需要数据库的支持，并且需要确保分布式系统中的不同节点都能访问到同一数据库实例。序列号是由数据库引擎控制的，保证了唯一性和有序性。

优势

可靠性：分布式数据库控制序列的生成，保证唯一性。
适用于多数据库：可以在多个分布式数据库实例上使用。

劣势

数据库依赖性：需要依赖特定类型的分布式数据库。
配置复杂：配置和管理分布式数据库可能较为复杂。

基于数据库的分布式唯一ID生成服务

特性

高可用性：这些服务通常具有高可用性和容错性。
可配置性：可以根据需求配置不同的ID生成规则。

详解

   一些公司使用分布式的ID生成服务，例如Twitter的Snowflake服务或美团点评的Leaf服务。这些服务提供了高性能和高可用性的分布式ID生成，通常基于自定义的算法。

优势

高可用性：这些服务通常具有高可用性，不易发生单点故障。
高性能：专门优化的服务通常具有出色的性能。

劣势

引入外部依赖：需要依赖外部服务，增加了系统的复杂性。
配置和维护成本：需要配置和维护分布式ID生成服务。

三、重点算法总结

1.雪花算法详解

   雪花算法（Snowflake Algorithm）是一种用于分布式系统中生成唯一标识符的算法，由Twitter开发。它通过将一个64位的整数ID分为不同的部分，确保在分布式环境中生成的ID不会重复。本文将详细介绍雪花算法的工作原理和结构。

2. 雪花算法的结构

   雪花算法的生成的64位整数ID被分为三个部分，每一部分表示不同的信息，如下所示：
sql| 时间戳 (41位) | 机器ID (10位) | 序列号 (12位) |
以下是各个部分的详细解释：

• 时间戳 (41位)：时间戳占据了ID的高41位，通常是从系统启动开始计算的毫秒数。这意味着雪花算法可以在69年内生成不重复的ID（2^41毫秒约等于69年）。
• 机器ID (10位)：机器ID用于标识不同的分布式机器。每台机器都必须有一个唯一的机器ID，通常在部署前分配。这意味着最多可以有1024个不同的机器。
• 序列号 (12位)：序列号用于确保在同一毫秒内生成的ID不会重复。如果在同一毫秒内生成多个ID，序列号部分会自增，从0开始，最大可达4095。

3. 雪花算法的工作原理

雪花算法的工作原理如下：

1. 当一个新的ID被生成时，算法会记录当前的时间戳（以毫秒为单位）。
2. 如果当前时间与上次生成ID的时间相同，会在序列号部分自增。
3. 如果序列号达到了最大值（4095），则会等待下一毫秒，以确保不会生成重复的ID。
4. 如果当前时间与上次生成ID的时间不同，序列号重置为0。
5. 然后，将各部分的值组合起来，生成一个64位的唯一ID。

4. 优点和限制

优点：

• 全局唯一性：雪花算法生成的ID在分布式环境中是全局唯一的，不会发生重复。
• 有序性：生成的ID具有有序性，有助于提高数据库检索性能。
• 高性能：算法的实现相对简单，生成ID的性能很高。

限制：

• 时钟同步性要求：雪花算法依赖于时钟同步，如果系统时钟回退可能会导致ID重复。
• 有限的机器ID数：机器ID的位数限制了可分配的机器数量，最多只能有1024个不同的机器。
• 时间戳回退限制：由于时间戳占据了41位，所以算法可以在2^41毫秒（约69年）内生成不重复的ID。如果系统运行时间超过了这个限制，可能需要额外的处理来防止时间戳回退问题。

5. 示例

以下是一个示例雪花ID的结构：
| 00011001010111011011001000101010011011111 | 0010101010 |110110000101 || 时间戳 (41位) | 机器ID (10位) | 序列号 (12位) |
   在示例中，时间戳部分占据了前41位，机器ID占据了接下来的10位，序列号占据了最后的12位。这三个部分共同组成了一个唯一的雪花ID。

以下是一个简单的Java实现雪花算法的例子：

public class SnowflakeIdGenerator {
    private final long epoch = 1629331200000L; // 2021-08-20 00:00:00
    private final int dataCenterIdBits = 5;
    private final int workerIdBits = 5;
    private final int sequenceBits = 12;
    private final int maxDataCenterId = ~(-1 << dataCenterIdBits);
    private final int maxWorkerId = ~(-1 << workerIdBits);
    private final int workerIdShift = sequenceBits;
    private final int dataCenterIdShift = sequenceBits + workerIdBits;
    private final int timestampLeftShift = sequenceBits + workerIdBits + dataCenterIdBits;
    private final int sequenceMask = ~(-1 << sequenceBits);
    private final long dataCenterId;
    private final long workerId;
    private long sequence = 0L;
    private long lastTimestamp = -1L;

    public SnowflakeIdGenerator(long dataCenterId, long workerId) {
        if (dataCenterId > maxDataCenterId || dataCenterId < 0) {
            throw new IllegalArgumentException("Data center ID can't be greater than " + maxDataCenterId + " or less than 0");
        }
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException("Worker ID can't be greater than " + maxWorkerId + " or less than 0");
        }
        this.dataCenterId = dataCenterId;
        this.workerId = workerId;
    }

    public synchronized long nextId() {
        long timestamp = System.currentTimeMillis();
        if (timestamp < lastTimestamp) {
            throw new RuntimeException("Clock moved backwards. Refusing to generate id for " + (lastTimestamp - timestamp) + " milliseconds.");
        }
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            sequence = 0L;
        }
        lastTimestamp = timestamp;
        return ((timestamp - epoch) << timestampLeftShift) | (dataCenterId << dataCenterIdShift) | (workerId << workerIdShift) | sequence;
    }

    private long tilNextMillis(long lastTimestamp) {
        long timestamp = System.currentTimeMillis();
        while (timestamp <= lastTimestamp) {
            timestamp = System.currentTimeMillis();
        }
        return timestamp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

在这个例子中，我们定义了一个SnowflakeIdGenerator类，该类具有nextId()方法，用于生成雪花ID。在构造函数中，我们需要传入数据中心ID和工作节点ID，它们是用来唯一标识每个雪花ID的。在nextId()方法中，我们首先获取当前时间戳，并检查它是否比上次生成ID的时间戳更大。如果是，则将序列号重置为0，并更新上次生成ID的时间戳。否则，我们将序列号递增，并检查是否超过了最大序列号。如果超过了最大序列号，则我们将时间戳递增到下一个毫秒。最后，我们将时间戳、数据中心ID、工作节点ID和序列号合并起来，得到最终的雪花ID。

6. 总结

   雪花算法是一种可靠且高效的分布式主键生成算法，已在实际生产中得到广泛应用。通过将时间戳、机器ID和序列号组合在一起，它确保了生成的ID在分布式环境中不会重复。雪花算法的全局唯一性和有序性使其成为分布式系统中的理想选择之一，特别适用于需要生成唯一标识符的场景。
点赞收藏，富婆包养✋✋