← 返回首页
🌐

分布式ID生成雪花算法

📂 architecture ⏱ 6 min 1072 words
架构分布式系统分布式ID雪花算法

分布式ID生成雪花算法

为什么需要分布式ID

在分布式系统中，传统的数据库自增ID方案存在以下问题：

  1. 单点故障：数据库宕机导致ID生成失败
  2. 性能瓶颈：高并发下数据库成为瓶颈
  3. 数据安全：自增ID暴露业务信息
  4. 扩展困难：分库分表后ID可能重复

常见分布式ID方案

UUID

// UUID生成
public class UUIDGenerator {
    
    public static String generateUUID() {
        return UUID.randomUUID().toString().replace("-", "");
    }
    
    public static Long generateUUIDAsLong() {
        UUID uuid = UUID.randomUUID();
        return uuid.getMostSignificantBits() & Long.MAX_VALUE;
    }
}

// 使用示例
String id = UUIDGenerator.generateUUID(); // "550e8400e29b41d4a716446655440000"
Long longId = UUIDGenerator.generateUUIDAsLong(); // 正数Long值

优点：

缺点：

数据库自增

-- 创建序列表
CREATE TABLE id_generator (
    id BIGINT AUTO_INCREMENT PRIMARY KEY,
    biz_type VARCHAR(64) NOT NULL,
    max_id BIGINT NOT NULL,
    step INT NOT NULL,
    update_time TIMESTAMP DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP
);

-- 初始化业务类型
INSERT INTO id_generator (biz_type, max_id, step) VALUES ('order', 0, 1000);

-- 获取批量ID
SELECT max_id, step FROM id_generator WHERE biz_type = 'order' FOR UPDATE;
UPDATE id_generator SET max_id = max_id + step WHERE biz_type = 'order';

// 数据库自增ID生成器
@Component
public class DatabaseIdGenerator {
    
    private final JdbcTemplate jdbcTemplate;
    private final Map<String, IdRange> idRanges = new ConcurrentHashMap<>();
    
    public Long generateId(String bizType) {
        IdRange range = idRanges.get(bizType);
        
        if (range == null || range.isExhausted()) {
            range = fetchNewRange(bizType);
            idRanges.put(bizType, range);
        }
        
        return range.next();
    }
    
    private IdRange fetchNewRange(String bizType) {
        // 获取新的ID范围
        IdRange range = jdbcTemplate.queryForObject(
            "SELECT max_id, step FROM id_generator WHERE biz_type = ? FOR UPDATE",
            new Object[]{bizType},
            (rs, rowNum) -> new IdRange(
                rs.getLong("max_id"),
                rs.getLong("step")
            )
        );
        
        // 更新数据库
        jdbcTemplate.update(
            "UPDATE id_generator SET max_id = max_id + step WHERE biz_type = ?",
            bizType
        );
        
        return range;
    }
    
    private static class IdRange {
        private long current;
        private final long max;
        
        public IdRange(long start, long step) {
            this.current = start;
            this.max = start + step;
        }
        
        public synchronized long next() {
            if (current >= max) {
                throw new IdExhaustedException("ID range exhausted");
            }
            return current++;
        }
        
        public boolean isExhausted() {
            return current >= max;
        }
    }
}

Redis自增

// Redis自增ID生成器
@Component
public class RedisIdGenerator {
    
    private final StringRedisTemplate redisTemplate;
    
    public Long generateId(String bizType) {
        String key = "id:" + bizType;
        return redisTemplate.opsForValue().increment(key);
    }
    
    public Long generateId(String bizType, long step) {
        String key = "id:" + bizType;
        Long id = redisTemplate.opsForValue().increment(key, step);
        return id - step + 1; // 返回范围的起始值
    }
}

雪花算法

雪花算法（Snowflake）是Twitter开源的分布式ID生成算法，它生成一个64位的Long型ID。

ID结构

0 | 41位时间戳 | 5位数据中心ID | 5位工作机器ID | 12位序列号

// 雪花算法实现
public class SnowflakeIdGenerator {
    
    // 起始时间戳 (2020-01-01 00:00:00)
    private final long twepoch = 1577836800000L;
    
    // 各部分的位数
    private final long workerIdBits = 5L;
    private final long datacenterIdBits = 5L;
    private final long sequenceBits = 12L;
    
    // 最大值
    private final long maxWorkerId = ~(-1L << workerIdBits);  // 31
    private final long maxDatacenterId = ~(-1L << datacenterIdBits);  // 31
    private final long sequenceMask = ~(-1L << sequenceBits);  // 4095
    
    // 位移
    private final long workerIdShift = sequenceBits;
    private final long datacenterIdShift = sequenceBits + workerIdBits;
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
    
    // 组件
    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 must be between 0 and " + maxWorkerId);
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException("Datacenter ID must be between 0 and " + maxDatacenterId);
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }
    
    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 (timestamp == lastTimestamp) {
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                // 序列号用完，等待下一毫秒
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            sequence = 0L;
        }
        
        lastTimestamp = timestamp;
        
        // 组装ID
        return ((timestamp - twepoch) << timestampLeftShift) |
                (datacenterId << datacenterIdShift) |
                (workerId << workerIdShift) |
                sequence;
    }
    
    private long tilNextMillis(long lastTimestamp) {
        long timestamp = System.currentTimeMillis();
        while (timestamp <= lastTimestamp) {
            timestamp = System.currentTimeMillis();
        }
        return timestamp;
    }
    
    // 从ID中提取信息
    public long extractTimestamp(long id) {
        return (id >> timestampLeftShift) + twepoch;
    }
    
    public long extractDatacenterId(long id) {
        return (id >> datacenterIdShift) & maxDatacenterId;
    }
    
    public long extractWorkerId(long id) {
        return (id >> workerIdShift) & maxWorkerId;
    }
    
    public long extractSequence(long id) {
        return id & sequenceMask;
    }
}

使用示例

// 创建雪花算法生成器
@Component
public class SnowflakeIdService {
    
    private final SnowflakeIdGenerator generator;
    
    public SnowflakeIdService(@Value("${snowflake.worker-id:1}") long workerId,
                              @Value("${snowflake.datacenter-id:1}") long datacenterId) {
        this.generator = new SnowflakeIdGenerator(workerId, datacenterId);
    }
    
    public Long generateId() {
        return generator.nextId();
    }
    
    public void analyzeId(long id) {
        System.out.println("Timestamp: " + new Date(generator.extractTimestamp(id)));
        System.out.println("Datacenter ID: " + generator.extractDatacenterId(id));
        System.out.println("Worker ID: " + generator.extractWorkerId(id));
        System.out.println("Sequence: " + generator.extractSequence(id));
    }
}

// 使用
@Service
public class OrderService {
    
    @Autowired
    private SnowflakeIdService idService;
    
    public Order createOrder(CreateOrderRequest request) {
        Long orderId = idService.generateId();
        // 使用orderId创建订单
        return new Order(orderId, request);
    }
}

时钟回拨问题

时钟回拨可能导致ID重复，需要处理这个问题。

// 处理时钟回拨
public class SnowflakeIdGeneratorWithClockBackward {
    
    private long lastTimestamp = -1L;
    private long clockBackwardCount = 0;
    private final long maxClockBackward = 5; // 最大允许回拨5毫秒
    
    public synchronized long nextId() {
        long timestamp = System.currentTimeMillis();
        
        // 时钟回拨处理
        if (timestamp < lastTimestamp) {
            long backward = lastTimestamp - timestamp;
            
            if (backward <= maxClockBackward) {
                // 在允许范围内，等待时间追上
                clockBackwardCount++;
                timestamp = waitUntilClockCatchUp(lastTimestamp);
            } else {
                // 回拨过大，抛出异常
                throw new RuntimeException("Clock moved backwards. Refusing to generate id for " +
                        backward + " milliseconds");
            }
        }
        
        // 其他逻辑...
        return generateId(timestamp);
    }
    
    private long waitUntilClockCatchUp(long lastTimestamp) {
        long timestamp = System.currentTimeMillis();
        while (timestamp <= lastTimestamp) {
            timestamp = System.currentTimeMillis();
        }
        return timestamp;
    }
}

雪花算法变种

美团Leaf

// Leaf Segment模式
public class LeafSegment {
    
    private long maxNum;
    private long step;
    private long currentNum;
    private long nextStep;
    
    public LeafSegment(long maxNum, long step) {
        this.maxNum = maxNum;
        this.step = step;
        this.currentNum = 0;
        this.nextStep = 0;
    }
    
    public synchronized long nextId() {
        if (currentNum >= maxNum) {
            // 当前号段用完，切换到下一个号段
            currentNum = nextNum();
            nextStep = step;
        }
        
        return currentNum++;
    }
    
    private long nextNum() {
        // 获取新的号段
        return fetchNextSegment();
    }
}

// Leaf Snowflake模式
public class LeafSnowflake {
    
    private final SnowflakeIdGenerator snowflake;
    private final ZkClient zkClient;
    
    public LeafSnowflake(long workerId, long datacenterId) {
        this.snowflake = new SnowflakeIdGenerator(workerId, datacenterId);
        this.zkClient = new ZkClient("zookeeper:2181");
        
        // 注册workerId
        registerWorkerId();
    }
    
    private void registerWorkerId() {
        // 从ZooKeeper获取workerId
        String path = "/snowflake/" + datacenterId;
        List<String> children = zkClient.getChildren(path);
        
        // 找到可用的workerId
        for (int i = 0; i < 32; i++) {
            String workerPath = path + "/" + i;
            if (!zkClient.exists(workerPath)) {
                // 创建临时节点
                zkClient.createEphemeral(workerPath, InetAddress.getLocalHost().getHostName());
                this.workerId = i;
                break;
            }
        }
    }
    
    public long nextId() {
        return snowflake.nextId();
    }
}

方案对比

方案 性能 可用性 有序性 长度 适用场景
UUID 高 高 无序 128位 分布式环境，无需有序
数据库自增 中等 低 有序 64位 单机或小规模系统
Redis自增 高 中等 有序 64位 需要简单有序ID
雪花算法 高 高 有序 64位 分布式系统，高并发

最佳实践

  1. 选择合适的方案：根据业务需求选择合适的ID生成方案
  2. 处理异常：处理时钟回拨、ID耗尽等异常情况
  3. 监控告警：监控ID生成器的状态和性能
  4. 数据迁移：考虑数据迁移时的ID兼容性
  5. 安全考虑：避免ID暴露敏感业务信息