在分布式系统中，生成全局唯一且趋势有序的ID是一大挑战。本文深入探讨了两大互联网公司——百度和美团点评——是如何解决这一问题的。我们将分析它们的分布式ID生成方案，包括架构设计、核心规则以及实现细节。
应用场景：
- 订单系统：在电子商务平台中，每个订单都需要一个唯一的订单号。使用分布式ID可以保证即使在分库分表的情况下，订单号也是全局唯一的。
- 消息队列：分布式消息队列中，每条消息都需要一个唯一的标识符，以避免消息重复或丢失。
- 用户账户和会话管理：为用户账户和会话生成唯一ID，确保用户数据的一致性和安全性。
- 日志记录：在分布式日志系统中，使用分布式ID为每条日志记录生成一个唯一的日志ID，便于日志的追踪和分析。
- 数据分片：在分布式数据库中，分布式ID可以用于数据分片，确保数据在不同的数据库节点之间均匀分布。
- 事件序列号：在事件驱动架构中，分布式ID可以作为事件的序列号，保证事件的顺序性和唯一性。
- 资源标识：对于分布式存储系统中的文件或对象，分布式ID可以作为资源的唯一标识符。
大厂案例
- 美团点评：美团点评开发了名为Leaf的分布式ID生成系统，它提供了号段模式和Snowflake模式两种方式来生成分布式ID，用于订单号、消息ID等多种场景。
- 百度：百度的分布式ID生成方案UID-Generator基于Snowflake算法，支持自定义时间戳和机器ID，用于百度内部的多种业务。
- 滴滴出行：滴滴出行开发了Tinyid，一个基于数据库的分布式ID生成服务，采用异步加双缓存策略，用于生成订单ID和消息ID等。
- Twitter：Twitter开源了Snowflake算法，用于生成分布式系统中的唯一ID，已被广泛采用，包括在滴滴出行的Tinyid中。
- 头条：头条的内容平台使用自定义的分布式ID生成策略，可能基于Snowflake算法，用于生成文章、图集和视频等内容的唯一ID。
1. 百度 UID-Generator
百度的UID-Generator是一个基于Snowflake算法的分布式ID生成服务。它通过以下设计规则来实现高可用、高并发的ID生成：
- 时间戳位：28位，以秒为单位，支持约8.7年的时间范围。
- 工作节点位：22位，支持高达420万个节点。
- 序列号位：13位，确保在同一时间戳内生成的ID是递增的，每秒最多生成8192个ID。
UID-Generator的实现依赖于数据库来分配工作节点ID，并使用内存中的RingBuffer来提高ID生成的吞吐量。它还提供了灵活的配置选项，以适应不同的业务需求。
2. 美团点评 Leaf
美团点评的Leaf是一个高性能的分布式ID生成服务，它采用了两种主要的ID生成模式：
- 号段模式：通过数据库预分配ID号段，减少对数据库的实时访问压力。
- Snowflake模式：类似于Twitter的Snowflake算法，通过时间戳、工作节点和序列号生成ID。
Leaf的设计特别注重系统的可用性和扩展性。它使用双Buffer机制来保证在数据库不可用时仍能持续提供服务，并动态调整号段长度以适应流量变化。
3. 设计规则与实现细节
- 全局唯一性：通过工作节点ID和时间戳的组合来保证。
- 趋势有序性：序列号位确保了在同一毫秒内生成的ID是有序的。
- 高可用性：依赖于数据库的主从复制和中间件的智能切换。
- 高并发支持：通过内存中的缓冲机制和批量ID预分配来实现。
- 低延迟：优化的算法和减少数据库访问操作来降低响应时间。
- 安全性：避免使用连续或可预测的ID，增强系统安全性。
- 可扩展性：通过动态调整号段长度和依赖于分布式架构的特性。
其他分布式ID算法
1. 雪花算法（Snowflake Algorithm）
public class SnowflakeIdWorker {
private final long twepoch = 1288834974657L;
private long sequence = 0L;
private final long machineId;
private long lastTimestamp = -1L;
public SnowflakeIdWorker(long machineId) {
this.machineId = machineId;
}
public synchronized long nextId() {
long timestamp = System.currentTimeMillis();
if (timestamp < lastTimestamp) {
throw new RuntimeException("Clock moved backwards. Refusing to generate id");
}
if (lastTimestamp == timestamp) {
sequence = (sequence + 1) & 4095;
if (sequence == 0) {
timestamp = tilNextMillis(lastTimestamp);
}
} else {
sequence = 0;
}
lastTimestamp = timestamp;
return ((timestamp - twepoch) << 22) |
(machineId << 17) |
sequence;
}
private long tilNextMillis(long lastTimestamp) {
long timestamp = System.currentTimeMillis();
while (timestamp <= lastTimestamp) {
timestamp = System.currentTimeMillis();
}
return timestamp;
}
}
2. UUID（Universally Unique Identifier）
import java.util.UUID;
public class UUIDGenerator {
public static String generateUUID() {
return UUID.randomUUID().toString().replace("-", "");
}
}
3. 数据库自增ID
CREATE TABLE orders (
order_id INT AUTO_INCREMENT PRIMARY KEY,
user_id INT NOT NULL,
product_id INT NOT NULL,
order_date TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
...
);
4. Redis生成序列号
# Redis CLI
INCR unique_id_counter
5. 基于Zookeeper的序列号
import org.apache.zookeeper.ZooDefs;
import org.apache.zookeeper.ZooKeeper;
public class ZookeeperIdGenerator {
private final ZooKeeper zk;
private final String path;
public ZookeeperIdGenerator(ZooKeeper zk, String path) {
this.zk = zk;
this.path = path;
}
public long nextId() throws KeeperException, InterruptedException {
String idPath = zk.create(path, new byte[0], ZooDefs.Ids.OPEN_ACL_UNSAFE, CreateMode.EPHEMERAL_SEQUENTIAL);
return Long.parseLong(idPath.substring(path.length() + 1));
}
}
6. 基于业务特征的ID
public class BusinessFeatureIdGenerator {
private final String businessPrefix;
private long counter = 0;
public BusinessFeatureIdGenerator(String businessPrefix) {
this.businessPrefix = businessPrefix;
}
public synchronized String nextId() {
return businessPrefix + ++counter;
}
}
总结
分布式ID生成是构建大规模分布式系统的基础。百度的UID-Generator和美团点评的Leaf都展示了如何通过巧妙的设计来满足这一需求。它们不仅提供了全局唯一、趋势有序的ID，还保证了系统的高可用性和高并发处理能力。
开源项目链接:
- 百度 UID-Generator: https://github.com/baidu/uid-generator
- 美团点评 Leaf: https://github.com/Meituan-Dianping/Leaf
相关内容