面试重要程度：⭐⭐⭐⭐⭐

真题来源：美团2024春招技术面试

考察重点：分布式系统设计、ID生成算法、高可用架构

预计阅读时间：40分钟

真题背景

面试官： "美团每天产生数十亿订单、用户行为等数据，需要为这些数据生成全局唯一ID。要求ID生成服务支持每秒百万级请求，保证ID全局唯一、趋势递增、高可用。请设计一个分布式ID生成方案，包括多种算法对比、架构设计、容灾方案等。"

考察意图：

• 分布式系统核心组件设计能力
• 多种ID生成算法的理解和选择
• 高并发、高可用架构设计
• 系统容灾和故障处理能力

🎯 需求分析与方案对比

业务需求分析

/**
 * 分布式ID生成需求定义
 */
public class DistributedIdRequirements {
    
    // 性能需求
    public static final long MAX_QPS = 1_000_000;          // 百万级QPS
    public static final int MAX_LATENCY_MS = 5;            // 延迟<5ms
    public static final double AVAILABILITY = 99.99;       // 99.99%可用性
    
    // 功能需求
    public static final boolean GLOBAL_UNIQUE = true;      // 全局唯一
    public static final boolean TREND_INCREASING = true;   // 趋势递增
    public static final boolean NO_DUPLICATE = true;       // 不重复
    public static final int ID_LENGTH = 64;                // 64位长度
    
    // 业务特性
    public static final boolean SORTABLE = true;           // 可排序
    public static final boolean MEANINGFUL = false;        // 无业务含义
    public static final boolean SECURITY = true;           // 安全性（不可预测）
}

ID生成方案对比

/**
 * 分布式ID生成方案对比
 */
@Component
public class IdGenerationComparison {
    
    /**
     * 方案1：数据库自增ID
     */
    public static class DatabaseAutoIncrement {
        
        @Autowired
        private JdbcTemplate jdbcTemplate;
        
        /**
         * 单机数据库自增
         */
        public Long generateId() {
            String sql = "INSERT INTO id_generator (stub) VALUES ('a')";
            KeyHolder keyHolder = new GeneratedKeyHolder();
            
            jdbcTemplate.update(connection -> {
                PreparedStatement ps = connection.prepareStatement(sql, Statement.RETURN_GENERATED_KEYS);
                return ps;
            }, keyHolder);
            
            return keyHolder.getKey().longValue();
        }
        
        /**
         * 多机数据库自增（设置步长）
         */
        public Long generateIdWithStep(int serverId, int serverCount) {
            // 设置自增起始值和步长
            String setAutoIncrement = String.format(
                "ALTER TABLE id_generator AUTO_INCREMENT = %d", serverId);
            String setStep = String.format(
                "SET @@auto_increment_increment = %d", serverCount);
            
            jdbcTemplate.execute(setAutoIncrement);
            jdbcTemplate.execute(setStep);
            
            return generateId();
        }
        
        // 优点：简单易实现，强一致性
        // 缺点：性能瓶颈，单点故障，扩展困难
    }
    
    /**
     * 方案2：UUID
     */
    public static class UUIDGenerator {
        
        /**
         * 标准UUID
         */
        public String generateUUID() {
            return UUID.randomUUID().toString();
        }
        
        /**
         * 压缩UUID（去掉横线）
         */
        public String generateCompactUUID() {
            return UUID.randomUUID().toString().replace("-", "");
        }
        
        /**
         * 数值型UUID
         */
        public Long generateNumericUUID() {
            UUID uuid = UUID.randomUUID();
            return uuid.getMostSignificantBits() ^ uuid.getLeastSignificantBits();
        }
        
        // 优点：本地生成，性能高，无单点故障
        // 缺点：无序，长度长，不适合做主键
    }
    
    /**
     * 方案3：Snowflake算法
     */
    public static class SnowflakeIdGenerator {
        
        // Snowflake算法参数
        private static final long START_TIMESTAMP = 1609459200000L; // 2021-01-01
        private static final long SEQUENCE_BITS = 12;
        private static final long MACHINE_BITS = 10;
        private static final long TIMESTAMP_BITS = 41;
        
        private static final long MAX_SEQUENCE = (1L << SEQUENCE_BITS) - 1;
        private static final long MAX_MACHINE_ID = (1L << MACHINE_BITS) - 1;
        
        private final long machineId;
        private long sequence = 0L;
        private long lastTimestamp = -1L;
        
        public SnowflakeIdGenerator(long machineId) {
            if (machineId > MAX_MACHINE_ID || machineId < 0) {
                throw new IllegalArgumentException("Machine ID out of range");
            }
            this.machineId = machineId;
        }
        
        /**
         * 生成Snowflake ID
         */
        public synchronized long generateId() {
            long currentTimestamp = System.currentTimeMillis();
            
            // 时钟回拨检查
            if (currentTimestamp < lastTimestamp) {
                throw new RuntimeException("Clock moved backwards");
            }
            
            // 同一毫秒内
            if (currentTimestamp == lastTimestamp) {
                sequence = (sequence + 1) & MAX_SEQUENCE;
                if (sequence == 0) {
                    // 序列号用完，等待下一毫秒
                    currentTimestamp = waitNextMillis(currentTimestamp);
                }
            } else {
                sequence = 0L;
            }
            
            lastTimestamp = currentTimestamp;
            
            // 组装ID：时间戳(41位) + 机器ID(10位) + 序列号(12位)
            return ((currentTimestamp - START_TIMESTAMP) << (MACHINE_BITS + SEQUENCE_BITS))
                    | (machineId << SEQUENCE_BITS)
                    | sequence;
        }
        
        private long waitNextMillis(long lastTimestamp) {
            long timestamp = System.currentTimeMillis();
            while (timestamp <= lastTimestamp) {
                timestamp = System.currentTimeMillis();
            }
            return timestamp;
        }
        
        // 优点：高性能，趋势递增，包含时间信息
        // 缺点：依赖机器时钟，机器ID管理复杂
    }
    
    /**
     * 方案4：号段模式
     */
    public static class SegmentIdGenerator {
        
        @Autowired
        private IdSegmentMapper segmentMapper;
        
        private final ConcurrentHashMap<String, SegmentBuffer> segmentBuffers = new ConcurrentHashMap<>();
        
        /**
         * 号段缓冲区
         */
        public static class SegmentBuffer {
            private volatile Segment currentSegment;
            private volatile Segment nextSegment;
            private volatile boolean isLoadingNext = false;
            private final ReentrantLock lock = new ReentrantLock();
            
            public static class Segment {
                private final AtomicLong value;
                private final long maxId;
                private final int step;
                
                public Segment(long currentId, int step) {
                    this.value = new AtomicLong(currentId);
                    this.maxId = currentId + step;
                    this.step = step;
                }
                
                public long getAndIncrement() {
                    return value.getAndIncrement();
                }
                
                public boolean isAvailable() {
                    return value.get() < maxId;
                }
                
                public boolean shouldLoadNext() {
                    return value.get() >= maxId * 0.9; // 使用90%时开始加载下一段
                }
            }
        }
        
        /**
         * 生成ID
         */
        public Long generateId(String bizType) {
            SegmentBuffer buffer = segmentBuffers.computeIfAbsent(bizType, 
                k -> initSegmentBuffer(bizType));
            
            return getIdFromBuffer(buffer, bizType);
        }
        
        private Long getIdFromBuffer(SegmentBuffer buffer, String bizType) {
            while (true) {
                buffer.lock.lock();
                try {
                    Segment segment = buffer.currentSegment;
                    
                    // 检查是否需要加载下一段
                    if (!buffer.isLoadingNext && segment.shouldLoadNext() && buffer.nextSegment == null) {
                        buffer.isLoadingNext = true;
                        // 异步加载下一段
                        CompletableFuture.runAsync(() -> loadNextSegment(buffer, bizType));
                    }
                    
                    // 当前段还有可用ID
                    if (segment.isAvailable()) {
                        return segment.getAndIncrement();
                    }
                    
                    // 当前段用完，切换到下一段
                    if (buffer.nextSegment != null) {
                        buffer.currentSegment = buffer.nextSegment;
                        buffer.nextSegment = null;
                        buffer.isLoadingNext = false;
                        continue;
                    }
                    
                    // 没有下一段，同步加载
                    loadNextSegment(buffer, bizType);
                    
                } finally {
                    buffer.lock.unlock();
                }
            }
        }
        
        private void loadNextSegment(SegmentBuffer buffer, String bizType) {
            try {
                // 从数据库获取新号段
                IdSegment segment = segmentMapper.getNextSegment(bizType);
                buffer.nextSegment = new SegmentBuffer.Segment(segment.getCurrentId(), segment.getStep());
                buffer.isLoadingNext = false;
            } catch (Exception e) {
                log.error("Failed to load next segment for bizType: {}", bizType, e);
                buffer.isLoadingNext = false;
            }
        }
        
        // 优点：高性能，数据库压力小，支持多业务类型
        // 缺点：ID不连续，重启会有空洞
    }
}

🏗️ 架构设计方案

基于Snowflake的分布式ID服务

/**
 * 分布式ID生成服务架构
 */
@SpringBootApplication
public class DistributedIdService {
    
    /**
     * ID生成服务核心组件
     */
    @RestController
    @RequestMapping("/api/id")
    public class IdGeneratorController {
        
        @Autowired
        private IdGeneratorService idGeneratorServ