分布式ID生成方案详解

时间：2024-02-24 13:02:39

目录

引言

一. UUID（Universally Unique Identifier）

UUID版本

版本1 UUID

版本4 UUID

UUID用途

二、数据库自增ID

三. 基于Redis的方案

四. Twitter的snowflake算法

五、百度UidGenerator

结语

引言

在分布式系统中，生成唯一标识符（ID）是一个常见的需求。在这篇博客中，我们将介绍几种常见的分布式ID生成方案，包括UUID、Snowflake算法、基于数据库的方案和基于Redis的方案。我们将深入探讨每种方案的原理、优缺点，并提供相应的代码示例。

一. UUID（Universally Unique Identifier）

UUID（Universally Unique Identifier）是一种标准化的128位数字（16字节）格式，通常用32个十六进制数字表示。UUID的目的是让分布式系统中的多个节点生成的标识符在时间和空间上都是唯一的。

UUID通常由以下几部分组成：

  1. 时间戳：占据前32位，表示生成UUID的时间戳。
  2. 时钟序列号：占据接下来的16位，保证在同一时刻生成的UUID的唯一性。
  3. 全局唯一的节点标识符：占据最后的48位，通常是机器的MAC地址。

UUID的生成方法有多种，其中比较常见的是基于当前时间戳和随机数生成。Java中可以使用java.util.UUID类来生成UUID，示例如下：

import java.util.UUID;

public class UUIDGenerator {
    public static void main(String[] args) {
        UUID uuid = UUID.randomUUID();
        System.out.println("Generated UUID: " + uuid.toString());
    }
}

这段代码将生成一个类似于550e8400-e29b-41d4-a716-446655440000的UUID。由于UUID的唯一性和随机性，通常用于分布式系统中的唯一标识符，例如作为数据库表的主键。 

二、数据库自增ID


使用数据库的id自增策略，如 MySQL 的 auto_increment。并且可以使用两台数据库分别设置不同
步长，生成不重复ID的策略来实现高可用。
优点：数据库生成的ID绝对有序，高可用实现方式简单
缺点：需要独立部署数据库实例，成本高，有性能瓶颈

在许多关系型数据库中，自增ID是一种常见的用于唯一标识表中记录的方式。下面我将以MySQL为例，介绍如何在数据库中使用自增ID。

首先，我们需要创建一个带有自增ID的表。以下是一个简单的示例表的创建语句：

CREATE TABLE users (
    id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(50) NOT NULL,
    email VARCHAR(100) NOT NULL
);

在这个例子中，id 列被定义为自增列，并且被指定为主键。每次向表中插入一条记录时，id 列都会自动递增，确保每个记录都有唯一的ID。

接下来，我们可以通过插入数据来演示自增ID的工作原理：

INSERT INTO users (name, email) VALUES ('Alice', 'alice@example.com');
INSERT INTO users (name, email) VALUES ('Bob', 'bob@example.com');
INSERT INTO users (name, email) VALUES ('Charlie', 'charlie@example.com');

查询表中的数据：

SELECT * FROM users;

输出应该类似于：

+----+---------+------------------+
| id | name    | email            |
+----+---------+------------------+
| 1  | Alice   | alice@example.com|
| 2  | Bob     | bob@example.com  |
| 3  | Charlie | charlie@example.com|
+----+---------+------------------+

每次插入一条记录时，id 列都会自动递增。这就是自增ID的基本工作原理。

三. 基于Redis的方案

Redis的所有命令操作都是单线程的，本身提供像 incr 和 increby 这样的自增原子命令，所以能保
证生成的 ID 肯定是唯一有序的。
优点：不依赖于数据库，灵活方便，且性能优于数据库；数字ID天然排序，对分页或者需要排
序的结果很有帮助。
缺点：如果系统中没有Redis，还需要引入新的组件，增加系统复杂度；需要编码和配置的工作
量比较大。
考虑到单节点的性能瓶颈，可以使用 Redis 集群来获取更高的吞吐量。假如一个集群中有5台
Redis。可以初始化每台 Redis 的值分别是1, 2, 3, 4, 5，然后步长都是 5。

在 Redis 中生成自增 ID 通常可以通过使用 INCR 命令实现。INCR 命令会将存储在指定键中的数字递增 1，并返回递增后的值。你可以利用这个特性来实现一个简单的自增 ID 生成器。以下是一个基本的示例：

import redis.clients.jedis.Jedis;

public class RedisIdGenerator {
    private Jedis jedis;

    public RedisIdGenerator() {
        this.jedis = new Jedis("localhost");
    }

    public long getNextId(String key) {
        return jedis.incr(key);
    }

    public static void main(String[] args) {
        RedisIdGenerator idGenerator = new RedisIdGenerator();
        String key = "my_id_counter";

        // 使用示例
        for (int i = 0; i < 5; i++) {
            long id = idGenerator.getNextId(key);
            System.out.println("Generated ID: " + id);
        }
    }
}

在这个示例中，我们首先创建了一个 RedisIdGenerator 类，该类包含一个 getNextId 方法，用于生成下一个自增 ID。在 main 方法中，我们创建了一个实例，并连续调用 getNextId 方法来生成 ID。

需要注意的是，这只是一个简单的示例。在实际应用中，你可能需要考虑并发访问时的线程安全性，以及如何处理 Redis 连接的创建和关闭等问题。

四. Twitter的snowflake算法

Twitter的Snowflake算法是一种用于生成分布式唯一ID的算法，它可以在分布式系统中生成全局唯一的ID。Snowflake算法的核心思想是将一个64位的long型的ID分成多个部分，包括时间戳、机器ID和序列号。具体来说，Snowflake算法的ID结构如下：

 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| unused |   timestamp   |   worker ID  | sequence
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  • 位表示未使用的位，可根据需要保留或用于其他用途。
  • 41位表示时间戳，可以表示的时间范围为2^41 / 1000 / 60 / 60 / 24 = 69年左右。
  • 10位表示机器ID，可以用来区分不同的机器。
  • 12位表示序列号，可以用来区分同一机器同一时间戳内生成的不同ID。

Snowflake算法生成ID的过程如下：

  1. 获取当前时间戳，单位是毫秒。
  2. 使用配置的机器ID。
  3. 如果当前时间戳与上一次生成ID的时间戳相同，则使用序列号加1；否则序列号重置为0。
  4. 将时间戳、机器ID和序列号合并生成最终的ID。

Snowflake算法的优点是生成的ID是递增的、趋势递增的，并且可以根据需要提取出生成ID的时间戳和机器ID。然而，Snowflake算法也有一些缺点，例如在高并发情况下可能会出现ID重复的情况，需要适当的措施来避免这种情况的发生。

Snowflake 算法是 Twitter 开源的一种分布式唯一 ID 生成算法，用于生成全局唯一的 ID。它的核心思想是将 ID 分为不同的部分，包括时间戳、机器 ID 和序列号。下面是一个详细的实现：

public class SnowflakeIdGenerator {
    private final long twepoch = 1288834974657L; // 起始时间戳，可以根据实际需求调整
    private final long workerIdBits = 5L; // 机器 ID 的位数
    private final long datacenterIdBits = 5L; // 数据中心 ID 的位数
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits); // 最大机器 ID
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits); // 最大数据中心 ID
    private final long sequenceBits = 12L; // 序列号的位数
    private final long workerIdShift = sequenceBits; // 机器 ID 左移位数
    private final long datacenterIdShift = sequenceBits + workerIdBits; // 数据中心 ID 左移位数
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits; // 时间戳左移位数
    private final long sequenceMask = -1L ^ (-1L << sequenceBits); // 序列号掩码

    private long workerId;
    private long datacenterId;
    private long sequence = 0L;
    private long lastTimestamp = -1L;

    public SnowflakeIdGenerator(long workerId, long datacenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException("Worker ID 必须介于 0 和 " + maxWorkerId + " 之间");
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException("Datacenter ID 必须介于 0 和 " + maxDatacenterId + " 之间");
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }

    public synchronized long nextId() {
        long timestamp = timeGen();

        if (timestamp < lastTimestamp) {
            throw new RuntimeException("时钟回拨发生在 " + (lastTimestamp - timestamp) + " 毫秒内");
        }

        if (timestamp == lastTimestamp) {
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            sequence = 0L;
        }

        lastTimestamp = timestamp;

        return ((timestamp - twepoch) << timestampLeftShift)
                | (datacenterId << datacenterIdShift)
                | (workerId << workerIdShift)
                | sequence;
    }

    private long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    private long timeGen() {
        return System.currentTimeMillis();
    }

    public static void main(String[] args) {
        SnowflakeIdGenerator idGenerator = new SnowflakeIdGenerator(1, 1);

        // 使用示例
        for (int i = 0; i < 5; i++) {
            long id = idGenerator.nextId();
            System.out.println("Generated ID: " + id);
        }
    }
}

在这个实现中，我们首先定义了 Snowflake 算法中需要用到的各种参数和位移操作。然后，我们实现了一个 nextId 方法来生成下一个 ID。在 main 方法中，我们创建了一个 SnowflakeIdGenerator 实例，并连续调用 nextId 方法来生成 ID。

需要注意的是，Snowflake 算法中的时间戳部分可以根据实际需求进行调整，以确保生成的 ID 在不同时间内仍然是唯一的。

五、百度UidGenerator

百度的 UIDGenerator 是一个分布式唯一 ID 生成器，类似于 Twitter 的 Snowflake 算法，但在细节上有所不同。以下是一个简化的实现，展示了其基本原理：

import java.util.concurrent.atomic.AtomicLong;

public class BaiduUidGenerator {
    private final long twepoch = 1288834974657L; // 起始时间戳，可以根据实际需求调整
    private final long workerIdBits = 10L; // 机器 ID 的位数
    private final long sequenceBits = 12L; // 序列号的位数

    private final long workerIdShift = sequenceBits; // 机器 ID 左移位数
    private final long timestampLeftShift = sequenceBits + workerIdBits; // 时间戳左移位数
    private final long sequenceMask = -1L ^ (-1L << sequenceBits); // 序列号掩码

    private final long workerId;
    private volatile long lastTimestamp = -1L;
    private volatile long sequence = 0L;

    public BaiduUidGenerator(long workerId) {
        if (workerId < 0 || workerId >= (1 << workerIdBits)) {
            throw new IllegalArgumentException("Worker ID 必须介于 0 和 " + ((1 << workerIdBits) - 1) + " 之间");
        }
        this.workerId = workerId;
    }

    public synchronized long nextId() {
        long timestamp = timeGen();

        if (timestamp < lastTimestamp) {
            throw new RuntimeException("时钟回拨发生在 " + (lastTimestamp - timestamp) + " 毫秒内");
        }

        if (timestamp == lastTimestamp) {
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            sequence = 0L;
        }

        lastTimestamp = timestamp;

        return ((timestamp - twepoch) << timestampLeftShift)
                | (workerId << workerIdShift)
                | sequence;
    }

    private long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    private long timeGen() {
        return System.currentTimeMillis();
    }

    public static void main(String[] args) {
        BaiduUidGenerator uidGenerator = new BaiduUidGenerator(1);

        // 使用示例
        for (int i = 0; i < 5; i++) {
            long id = uidGenerator.nextId();
            System.out.println("Generated ID: " + id);
        }
    }
}

在这个实现中，我们首先定义了 BaiduUidGenerator 类，其中包含了与 Snowflake 算法类似的参数和位移操作。然后，我们实现了一个 nextId 方法来生成下一个 ID。在 main 方法中，我们创建了一个 BaiduUidGenerator 实例，并连续调用 nextId 方法来生成 ID。

需要注意的是，这只是一个简化的实现，实际应用中可能需要根据具体需求进行调整和优化。

结语

以上是几种常见的分布式ID生成方案，每种方案都有其适用的场景，开发人员可以根据实际需求选择合适的方案。

相关文章