如何设计一个分布式ID生成器保证ID按时间有序？

chensoul   architecture   distributed

很多业务有生成唯一 ID 并作为数据库主键的需求。数据库会在这个字段上建立聚集索引（参考 MySQL InnoDB），即该字段会影响各条数据再物理存储上的顺序。

ID还要尽可能短，节省内存，让数据库索引效率更高。基本上64位整数能够满足绝大多数的场景，但是如果能做到比64位更短那就更好了。需要根据具体业务进行分析，预估出ID的最大值，这个最大值通常比64位整数的上限小很多，于是我们可以用更少的bit表示这个ID。

查询的时候，往往有分页或者排序的需求，所以需要给每条数据添加一个时间字段，并在其上建立普通索引(Secondary Index)。但是普通索引的访问效率比聚集索引慢，如果能够让ID按照时间粗略有序，则可以省去这个时间字段。为什么不是按照时间精确有序呢？因为按照时间精确有序是做不到的，除非用一个单机算法，在分布式场景下做到精确有序性能一般很差。

这就引出了 ID 生成的三大核心需求：

  • 全局唯一
  • 按照时间粗略有序
  • 尽可能短

下面介绍一些常用的生成 ID 的方法。

UUID

UUID 是一类算法的统称，具体有不同的实现。UUID 的优点是每台机器可以独立产生 ID，理论上保证不会重复，所以天然是分布式的；缺点是生成的 ID 太长，不仅占用内存，而且索引查询效率低。

MongoDB 的 ObjectId 使用的就是 UUID 算法。生成的 ObjectId 占 12 个字节，由以下几个部分组成，

  • 4 个字节表示的 Unix timestamp
  • 3 个字节表示的机器的 ID
  • 2 个字节表示的进程 ID
  • 3 个字节表示的计数器

使用数据库

可以使用数据库中的自增主键来生成ID。将ID生成的过程交给数据库管理，每个节点向数据库插入记录时，数据库会自动分配一个唯一的ID。通过使用数据库的自动递增功能，可以保证ID的唯一性和粗略有序性。

在分布式环境下，可以使用多台数据库协同工作生成 ID。假设用 8 台MySQL服务器协同工作，第一台 MySQL 初始值是 1，每次自增 8，第二台 MySQL 初始值是 2，每次自增 8，依次类推。在数据库前面添加一个负载均衡，每来一个请求，由负载均衡随机地将请求发给 8 台 MySQL 中的任意一个，然后返回一个ID。

Flickr就是这么做的，仅仅使用了两台 MySQL 服务器。可见这个方法虽然简单无脑，但是性能足够好。不过要注意，在 MySQL 中，不需要把所有 ID 都存下来，每台机器只需要存一个 MAX_ID 就可以了。这需要用到 MySQL 的一个 REPLACE INTO 特性。

Flickr 的实现方式如下。

Tickets64 表结构如下：

CREATE TABLE `Tickets64` (
  `id` bigint(20) unsigned NOT NULL auto_increment,
  `stub` char(1) NOT NULL default '',
  PRIMARY KEY  (`id`),
  UNIQUE KEY `stub` (`stub`)
) ENGINE=InnoDB

SELECT * from Tickets64 返回一行，如下所示：

+-------------------+------+
| id                | stub |
+-------------------+------+
| 72157623227190423 |    a |
+-------------------+------+

当我需要一个新的全局唯一 64 位 ID 时，我发出以下 SQL：

REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();

对于两台数据库服务器，分别设置表的自增值（auto_increment_increment）和偏移值（auto_increment_offset）。

TicketServer1:
auto_increment_increment = 2
auto_increment_offset = 1

TicketServer2:
auto_increment_increment = 2
auto_increment_offset = 2

举例：一个数据库服务器设置：自增值为 2，起始值为 1，生成的 ID 为奇数。

SET auto_increment_increment=2;
SET auto_increment_offset=1;

drop table Tickets64;

CREATE TABLE `Tickets64` (
  `id` bigint(20) unsigned NOT NULL auto_increment,
  `stub` char(1) NOT NULL default '',
  PRIMARY KEY  (`id`),
  UNIQUE KEY `stub` (`stub`)
);

SELECT AUTO_INCREMENT FROM information_schema.tables WHERE table_name="Tickets64";

REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();

另一个数据库服务器如何设置？：自增值为 2，起始值为 2，生成的 ID 为偶数。

SET auto_increment_increment=2;
SET auto_increment_offset=2;

drop table Tickets64;

CREATE TABLE `Tickets64` (
  `id` bigint(20) unsigned NOT NULL auto_increment,
  `stub` char(1) NOT NULL default '',
  PRIMARY KEY  (`id`),
  UNIQUE KEY `stub` (`stub`)
);

SELECT AUTO_INCREMENT FROM information_schema.tables WHERE table_name="Tickets64";

REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();

这个方法跟单台数据库比，缺点是 ID 不是严格递增的，只是粗略递增的。不过这个问题不大，我们的目标是粗略有序，不需要严格递增。

Snowflake算法

Twitter 开源的 Snowflake 算法。Snowflake是一种经典的分布式ID生成算法，由Twitter开发。它将64位的ID划分为不同的部分，包括时间戳、数据中心ID、机器ID和序列号。通过在不同的部分分配不同的位数，可以在分布式环境中生成唯一的ID，并且保证了ID的时间粗略有序性。

Instagram 用了类似的方案，41 位表示时间戳，13 位表示 shard Id（一个shard Id对应一台PostgreSQL机器），最低10位表示自增 ID。这个方案用一个 PostgreSQL 集群代替了 Twitter Snowflake 集群，优点是利用了现成的 PostgreSQL。

使用分布式锁

可以使用分布式锁来保证在生成 ID 时的互斥性，从而保证 ID 的有序性。可以使用一些分布式锁的实现，如 ZooKeeper、Redis 等，来协调各个节点的 ID 生成过程。每个节点在生成 ID 之前，首先获取分布式锁，然后按照一定规则生成 ID，释放锁后，下一个节点再获取锁生成ID。

下面是一个基本的使用 ZooKeeper 锁生成分布式 ID 的示例：

  1. 创建ZooKeeper客户端连接：
CuratorFramework client = CuratorFrameworkFactory.newClient("localhost:2181", new ExponentialBackoffRetry(1000, 3));
client.start();
  1. 创建分布式锁：
InterProcessMutex lock = new InterProcessMutex(client, "/id_lock");
  1. 获取锁并生成ID：
int timeoutSeconds = 10; // 设置锁超时时间为10秒

try {
    if (lock.acquire(timeoutSeconds, TimeUnit.SECONDS)) {
        // 成功获取锁
        String distributedID = generateID();
        // 使用生成的ID进行业务操作
        // ...
    } else {
        // 未能在超时时间内获取到锁，进行相应处理
        // ...
    }
} catch (Exception e) {
    // 处理异常
} finally {
    try {
        lock.release(); // 释放锁
    } catch (Exception e) {
        // 处理异常
    }
}

在这个示例中，使用 Curator 框架创建了一个 ZooKeeper 客户端连接，然后创建了一个 InterProcessMutex 对象，该对象表示一个分布式锁。在获取锁之前，节点会尝试获取并持有该锁。只有一个节点可以成功获取到锁，其他节点会阻塞等待。

获取到锁后，可以执行生成 ID 的逻辑，生成唯一的分布式 ID。

在业务操作完成后，通过 release()方法释放锁，使其他节点可以继续获取锁并生成 ID。

通过使用 ZooKeeper 锁，我们可以确保在分布式环境下生成的 ID 是互斥的，并且按照获取锁的顺序生成。这样可以保证生成的 ID 是有序的，并且避免了并发冲突的问题。

Redis 本身并没有提供原生的分布式锁功能，但可以借助 Redis 的原子性操作和过期时间来实现一个简单的分布式锁，并在获取锁时生成分布式 ID。下面是一个使用 Redis 锁生成分布式 ID 的示例代码：

import redis.clients.jedis.Jedis;

public class DistributedIdGenerator {
    private static final String LOCK_KEY = "id_lock";
    private static final int LOCK_EXPIRATION = 10; // 锁的过期时间，单位为秒
    private static final String REDIS_HOST = "localhost";
    private static final int REDIS_PORT = 6379;

    private Jedis jedis;

    public DistributedIdGenerator() {
        jedis = new Jedis(REDIS_HOST, REDIS_PORT);
    }

    public String generateDistributedId() {
        // 获取分布式锁
        boolean lockAcquired = acquireLock(LOCK_KEY, LOCK_EXPIRATION);

        if (lockAcquired) {
            try {
                // 生成ID的逻辑
                String distributedId = generateId();
                // 使用生成的ID进行业务操作
                // ...
                return distributedId;
            } finally {
                // 释放分布式锁
                releaseLock(LOCK_KEY);
            }
        } else {
            // 未能获取到分布式锁，进行相应处理
            // ...
            return null;
        }
    }

    private boolean acquireLock(String lockKey, int expiration) {
        String result = jedis.set(lockKey, "locked", "NX", "EX", expiration);
        return "OK".equals(result);
    }

    private void releaseLock(String lockKey) {
        jedis.del(lockKey);
    }

    private String generateId() {
        // 生成ID的逻辑
        // ...
        return "your_generated_id";
    }
}

在上述示例代码中，我们使用 Jedis 客户端连接 Redis，并定义了获取锁和释放锁的方法 acquireLock() 和 releaseLock()。在 generateDistributedId() 方法中，我们首先尝试获取分布式锁，如果成功获取到锁，则执行生成 ID 的逻辑和业务操作，并在最后释放锁。如果无法获取到锁，则可以根据实际需求进行相应处理。

请注意，上述示例代码是一个简单的实现，仅供参考。在实际使用中，还需要考虑异常处理、分布式锁的可重入性、处理锁超时等情况，以及根据具体的需求和系统架构进行适当的调整。

参考资料

Share this post:

Related content