小红书Java面试被问：如何设计一个分布式ID生成器

分布式ID生成器设计方案

一、设计需求分析

核心需求

1. 全局唯一性：分布式环境下生成的ID必须全局唯一

2. 趋势递增：有利于数据库索引性能

3. 高可用性：服务必须7×24小时可用

4. 低延迟：生成速度要快，通常在毫秒级

5. 高QPS：支持高并发请求

6. 可扩展性：能够随着业务增长平滑扩展

7. 时间有序性：能够反映生成时间顺序

常见场景

• 订单ID、用户ID、消息ID

• 数据库主键、分片键

• 日志追踪、事件序列号

二、主流方案对比

1.UUID

java

复制

下载

// 优点：简单、无中心化 // 缺点：无序、存储空间大（128位）、索引性能差 UUID uuid = UUID.randomUUID(); // 示例：123e4567-e89b-12d3-a456-426614174000

2.数据库自增ID

sql

复制

下载

-- 单数据库 CREATE TABLE id_generator ( id bigint(20) NOT NULL AUTO_INCREMENT, PRIMARY KEY (id) ); -- 多数据库（步长设置） -- DB1: 1, 3, 5, 7... -- DB2: 2, 4, 6, 8...

3.Redis INCR

redis

复制

下载

INCR global:id # 返回递增数字

4.Snowflake算法（推荐）

java

复制

下载

// Twitter Snowflake：64位ID结构 // 0 | 41位时间戳 | 5位数据中心ID | 5位机器ID | 12位序列号 // 生成示例：467246781939384320

5.Leaf（美团）

• 基于Snowflake优化

• 支持号段模式和Snowflake模式

• 解决时钟回拨问题

6.TinyID（滴滴）

• 基于数据库号段模式优化

• 双Buffer预加载

• HTTP Restful接口

三、Snowflake详细设计

1.ID结构设计（64位）

text

复制

下载

┌────────────── 1位符号位（始终为0） ──────────────┐ ├────────────── 41位时间戳（毫秒） ───────────────┤ ├────────── 5位数据中心ID（0-31） ───────────┤ ├─────────── 5位机器ID（0-31） ─────────────┤ └─────────── 12位序列号（0-4095） ────────────┘

2.各字段计算

java

复制

下载

public class SnowflakeIdGenerator { // 各部分位数 private static final long SEQUENCE_BITS = 12L; // 序列号占12位 private static final long WORKER_ID_BITS = 5L; // 机器ID占5位 private static final long DATACENTER_ID_BITS = 5L; // 数据中心占5位 // 最大值计算 private static final long MAX_SEQUENCE = ~(-1L << SEQUENCE_BITS); // 4095 private static final long MAX_WORKER_ID = ~(-1L << WORKER_ID_BITS); // 31 private static final long MAX_DATACENTER_ID = ~(-1L << DATACENTER_ID_BITS); // 31 // 偏移量 private static final long WORKER_ID_SHIFT = SEQUENCE_BITS; // 12 private static final long DATACENTER_ID_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS; // 17 private static final long TIMESTAMP_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS + DATACENTER_ID_BITS; // 22 // 起始时间戳（自定义：2024-01-01） private static final long EPOCH = 1704067200000L; // 成员变量 private long workerId; // 机器ID private long datacenterId; // 数据中心ID private long sequence = 0L; // 序列号 private long lastTimestamp = -1L; // 上次生成时间 }

3.核心生成逻辑

java

复制

下载

public synchronized long nextId() { long timestamp = timeGen(); // 时钟回拨处理 if (timestamp < lastTimestamp) { throw new RuntimeException( String.format("时钟回拨，拒绝生成ID。上次时间：%d，当前时间：%d", lastTimestamp, timestamp)); } // 同一毫秒内的序列号递增 if (lastTimestamp == timestamp) { sequence = (sequence + 1) & MAX_SEQUENCE; if (sequence == 0) { // 当前毫秒序列号用尽 timestamp = tilNextMillis(lastTimestamp); // 等待下一毫秒 } } else { sequence = 0L; // 新的毫秒，序列号重置 } lastTimestamp = timestamp; // 组合各部分生成最终ID return ((timestamp - EPOCH) << TIMESTAMP_SHIFT) | (datacenterId << DATACENTER_ID_SHIFT) | (workerId << WORKER_ID_SHIFT) | sequence; } private long tilNextMillis(long lastTimestamp) { long timestamp = timeGen(); while (timestamp <= lastTimestamp) { timestamp = timeGen(); } return timestamp; } private long timeGen() { return System.currentTimeMillis(); }

4.时钟回拨解决方案

java

复制

下载

public class SnowflakeWithBackup { // 方案1：等待时钟追上 private long waitForClock(long lastTimestamp) { long timestamp = timeGen(); while (timestamp <= lastTimestamp) { try { Thread.sleep(lastTimestamp - timestamp); } catch (InterruptedException e) { Thread.currentThread().interrupt(); } timestamp = timeGen(); } return timestamp; } // 方案2：使用备份Worker ID private long backupWorkerId; private boolean usingBackup = false; // 方案3：记录回拨事件并报警 private void handleClockBackward(long lastTimestamp, long currentTimestamp) { log.error("检测到时钟回拨，偏移量：{}ms", lastTimestamp - currentTimestamp); // 发送报警、记录监控指标 metrics.recordClockBackward(); } }

四、号段模式设计（Segment Mode）

1.数据库设计

sql

复制

下载

CREATE TABLE id_segment ( biz_tag VARCHAR(128) NOT NULL COMMENT '业务标签', max_id BIGINT NOT NULL COMMENT '当前最大ID', step INT NOT NULL COMMENT '号段长度', version BIGINT NOT NULL COMMENT '乐观锁版本号', description VARCHAR(256) COMMENT '描述', update_time TIMESTAMP DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP, PRIMARY KEY (biz_tag) ) ENGINE=InnoDB;

2.双Buffer优化

java

复制

下载

public class DoubleBufferSegment { private SegmentBuffer currentBuffer; // 当前使用的Buffer private SegmentBuffer nextBuffer; // 预备Buffer private volatile boolean loadingNext = false; // 是否正在加载下一个Buffer // 获取ID public synchronized Long getNextId() { // 当前Buffer用完且下一个Buffer已准备好 if (currentBuffer.isExhausted() && nextBuffer.isReady()) { currentBuffer = nextBuffer; nextBuffer = new SegmentBuffer(); loadingNext = false; } // 当前Buffer快用完时，异步加载下一个Buffer if (currentBuffer.isNearlyExhausted() && !loadingNext) { loadingNext = true; loadNextBufferAsync(); } return currentBuffer.getAndIncrement(); } // 异步加载下一个号段 private void loadNextBufferAsync() { executorService.submit(() -> { Segment newSegment = loadSegmentFromDB(); nextBuffer.fill(newSegment); }); } }

3.数据库更新逻辑

sql

复制

下载

-- 乐观锁更新号段 UPDATE id_segment SET max_id = max_id + step, version = version + 1 WHERE biz_tag = #{bizTag} AND version = #{oldVersion};

五、高可用架构设计

1.服务部署架构

text

复制

下载

┌─────────────────────────────────────────────────────┐ │ 负载均衡器 (Nginx/LVS) │ └─────────────────────────────────────────────────────┘ │ ┌───────────┼───────────┐ ▼ ▼ ▼ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │ ID生成服务1 │ │ ID生成服务2 │ │ ID生成服务3 │ │ WorkerID=1 │ │ WorkerID=2 │ │ WorkerID=3 │ └─────────────┘ └─────────────┘ └─────────────┘ │ │ │ └───────────┼───────────┘ │ ┌───────────▼───────────┐ │ 配置中心/注册中心 │ │ (ZooKeeper/etcd) │ └───────────────────────┘ │ ┌───────────▼───────────┐ │ 数据库集群 │ │ (MySQL/Redis) │ └───────────────────────┘

2.Worker ID动态分配

java

复制

下载

public class DynamicWorkerIdAssigner { private ZooKeeper zkClient; private String workerIdPath = "/snowflake/workers"; public long assignWorkerId() throws Exception { // 尝试创建临时有序节点 String createdPath = zkClient.create( workerIdPath + "/worker-", null, ZooDefs.Ids.OPEN_ACL_UNSAFE, CreateMode.EPHEMERAL_SEQUENTIAL ); // 解析节点序号作为Worker ID String sequenceStr = createdPath.substring( createdPath.lastIndexOf('-') + 1); long workerId = Long.parseLong(sequenceStr) % (MAX_WORKER_ID + 1); // 监听节点变化，实现故障转移 zkClient.getChildren(workerIdPath, event -> { if (event.getType() == EventType.NodeChildrenChanged) { reassignWorkerId(); } }); return workerId; } }

六、性能优化策略

1.本地缓存优化

java

复制

下载

public class LocalIdCache { private ConcurrentHashMap<String, BlockingQueue<Long>> cacheMap; private int cacheSize = 1000; public void preloadIds(String bizTag, int count) { List<Long> ids = fetchIdsFromDB(bizTag, count); BlockingQueue<Long> queue = cacheMap.computeIfAbsent( bizTag, k -> new LinkedBlockingQueue<>(cacheSize)); queue.addAll(ids); } public Long getId(String bizTag) { BlockingQueue<Long> queue = cacheMap.get(bizTag); Long id = queue.poll(); if (id == null) { // 同步加载一批ID preloadIds(bizTag, 100); id = queue.poll(); } return id; } }

2.批量生成优化

java

复制

下载

public class BatchIdGenerator { // 批量生成ID，减少网络和数据库开销 public List<Long> generateBatch(int batchSize) { List<Long> ids = new ArrayList<>(batchSize); for (int i = 0; i < batchSize; i++) { ids.add(nextId()); } return ids; } // 异步批量预生成 public void preGenerateAsync() { executorService.submit(() -> { while (!Thread.currentThread().isInterrupted()) { if (idQueue.size() < THRESHOLD) { List<Long> batch = generateBatch(BATCH_SIZE); idQueue.addAll(batch); } Thread.sleep(100); } }); } }

七、监控与运维

1.关键监控指标

java

复制

下载

public class IdGeneratorMetrics { // 计数器 private Meter generatedIds; // ID生成速率 private Meter failedGenerations; // 生成失败次数 private Histogram latency; // 生成延迟分布 // 仪表盘 private Gauge cacheHitRate; // 缓存命中率 private Gauge queueSize; // 待处理队列大小 // 特殊事件 private Counter clockBackwards; // 时钟回拨次数 private Counter workerIdChanges; // Worker ID变更次数 }

2.故障应对策略

java

复制

下载

public class FaultToleranceHandler { // 降级策略：当Snowflake不可用时，降级到UUID public String generateIdWithFallback() { try { return String.valueOf(snowflakeGenerator.nextId()); } catch (Exception e) { log.warn("Snowflake故障，降级到UUID", e); metrics.recordFallback(); return UUID.randomUUID().toString().replace("-", ""); } } // 限流保护 public Long generateIdWithRateLimit() { if (!rateLimiter.tryAcquire()) { throw new RateLimitException("ID生成服务限流"); } return snowflakeGenerator.nextId(); } }

八、选型建议

根据场景选择方案：

最终建议架构：

text

复制

下载

对于大多数互联网公司，推荐： 1. 中小型业务：使用美团Leaf的号段模式 2. 大型业务：使用Leaf-Snowflake混合模式 3. 关键业务：双机房部署 + 故障自动切换

九、实施步骤

1. 第一阶段：实现基础Snowflake算法

2. 第二阶段：添加Worker ID动态分配

3. 第三阶段：实现号段模式作为备选

4. 第四阶段：添加监控报警和降级策略

5. 第五阶段：多机房部署和容灾演练

十、注意事项

1. 时钟同步：所有服务器必须使用NTP同步时钟

2. Worker ID管理：确保Worker ID不重复

3. ID长度考虑：JavaScript处理53位整数安全，超过需要字符串传递

4. 数据迁移：如果更换ID生成方案，需要考虑历史数据兼容

5. 安全防护：防止ID被猜测，敏感业务可考虑加密ID