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

真题来源：美团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 idGeneratorService;
        
        /**
         * 生成单个ID
         */
        @GetMapping("/generate")
        public ResponseEntity<IdResponse> generateId(@RequestParam String bizType) {
            try {
                long id = idGeneratorService.generateId(bizType);
                return ResponseEntity.ok(IdResponse.success(id));
            } catch (Exception e) {
                return ResponseEntity.status(500)
                    .body(IdResponse.error(e.getMessage()));
            }
        }
        
        /**
         * 批量生成ID
         */
        @PostMapping("/batch")
        public ResponseEntity<BatchIdResponse> generateBatchIds(@RequestBody BatchIdRequest request) {
            try {
                List<Long> ids = idGeneratorService.generateBatchIds(
                    request.getBizType(), request.getCount());
                return ResponseEntity.ok(BatchIdResponse.success(ids));
            } catch (Exception e) {
                return ResponseEntity.status(500)
                    .body(BatchIdResponse.error(e.getMessage()));
            }
        }
    }
    
    /**
     * ID生成服务实现
     */
    @Service
    public class IdGeneratorService {
        
        @Autowired
        private WorkerIdAssigner workerIdAssigner;
        
        @Autowired
        private IdGeneratorFactory generatorFactory;
        
        private final ConcurrentHashMap<String, IdGenerator> generators = new ConcurrentHashMap<>();
        
        /**
         * 生成ID
         */
        public long generateId(String bizType) {
            IdGenerator generator = generators.computeIfAbsent(bizType, 
                k -> generatorFactory.createGenerator(bizType));
            
            return generator.generateId();
        }
        
        /**
         * 批量生成ID
         */
        public List<Long> generateBatchIds(String bizType, int count) {
            IdGenerator generator = generators.computeIfAbsent(bizType, 
                k -> generatorFactory.createGenerator(bizType));
            
            List<Long> ids = new ArrayList<>(count);
            for (int i = 0; i < count; i++) {
                ids.add(generator.generateId());
            }
            return ids;
        }
    }
    
    /**
     * Worker ID分配器
     */
    @Component
    public class WorkerIdAssigner {
        
        @Autowired
        private RedisTemplate<String, String> redisTemplate;
        
        private static final String WORKER_ID_KEY = "distributed_id:worker_id";
        private static final int MAX_WORKER_ID = 1023; // 10位最大值
        
        /**
         * 分配Worker ID
         */
        public int assignWorkerId() {
            String serverInfo = getServerInfo();
            
            // 尝试从Redis获取已分配的Worker ID
            String existingWorkerId = redisTemplate.opsForHash()
                .get(WORKER_ID_KEY, serverInfo).toString();
            
            if (existingWorkerId != null) {
                return Integer.parseInt(existingWorkerId);
            }
            
            // 分配新的Worker ID
            for (int workerId = 0; workerId <= MAX_WORKER_ID; workerId++) {
                Boolean success = redisTemplate.opsForHash()
                    .putIfAbsent(WORKER_ID_KEY, String.valueOf(workerId), serverInfo);
                
                if (success) {
                    // 设置心跳保持Worker ID
                    startHeartbeat(workerId, serverInfo);
                    return workerId;
                }
            }
            
            throw new RuntimeException("No available worker ID");
        }
        
        /**
         * 启动心跳保持Worker ID
         */
        private void startHeartbeat(int workerId, String serverInfo) {
            ScheduledExecutorService executor = Executors.newSingleThreadScheduledExecutor();
            executor.scheduleWithFixedDelay(() -> {
                try {
                    redisTemplate.opsForHash().put(WORKER_ID_KEY, String.valueOf(workerId), serverInfo);
                    redisTemplate.expire(WORKER_ID_KEY, Duration.ofMinutes(5));
                } catch (Exception e) {
                    log.error("Failed to send heartbeat for worker ID: {}", workerId, e);
                }
            }, 0, 30, TimeUnit.SECONDS);
        }
        
        private String getServerInfo() {
            try {
                return InetAddress.getLocalHost().getHostAddress() + ":" + 
                       System.getProperty("server.port", "8080");
            } catch (Exception e) {
                return UUID.randomUUID().toString();
            }
        }
    }
}

高可用架构设计

/**
 * 高可用架构组件
 */
@Component
public class HighAvailabilityComponents {
    
    /**
     * 多机房部署策略
     */
    @Component
    public static class MultiDataCenterDeployment {
        
        /**
         * 机房感知的Worker ID分配
         */
        public int assignDataCenterAwareWorkerId(String dataCenter) {
            // 不同机房使用不同的Worker ID范围
            int dcId = getDataCenterId(dataCenter);
            int workerIdStart = dcId * 256; // 每个机房分配256个Worker ID
            int workerIdEnd = workerIdStart + 255;
            
            for (int workerId = workerIdStart; workerId <= workerIdEnd; workerId++) {
                if (tryAssignWorkerId(workerId)) {
                    return workerId;
                }
            }
            
            throw new RuntimeException("No available worker ID in data center: " + dataCenter);
        }
        
        private int getDataCenterId(String dataCenter) {
            // 根据机房名称计算机房ID
            return Math.abs(dataCenter.hashCode()) % 4; // 支持4个机房
        }
    }
    
    /**
     * 容灾与故障恢复
     */
    @Component
    public static class DisasterRecovery {
        
        @Autowired
        private IdGeneratorService idGeneratorService;
        
        /**
         * 健康检查
         */
        @GetMapping("/health")
        public ResponseEntity<HealthStatus> healthCheck() {
            try {
                // 测试ID生成
                long testId = idGeneratorService.generateId("health_check");
                
                return ResponseEntity.ok(HealthStatus.builder()
                    .status("UP")
                    .timestamp(System.currentTimeMillis())
                    .testId(testId)
                    .build());
                    
            } catch (Exception e) {
                return ResponseEntity.status(503)
                    .body(HealthStatus.builder()
                        .status("DOWN")
                        .error(e.getMessage())
                        .timestamp(System.currentTimeMillis())
                        .build());
            }
        }
        
        /**
         * 时钟回拨处理
         */
        public long handleClockBackwards(long lastTimestamp) {
            long currentTimestamp = System.currentTimeMillis();
            long offset = lastTimestamp - currentTimestamp;
            
            if (offset <= 5) {
                // 小幅回拨，等待时钟追上
                try {
                    Thread.sleep(offset + 1);
                    return System.currentTimeMillis();
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                    throw new RuntimeException("Interrupted while waiting for clock", e);
                }
            } else {
                // 大幅回拨，抛出异常
                throw new RuntimeException("Clock moved backwards by " + offset + "ms");
            }
        }
        
        /**
         * 服务降级策略
         */
        @Component
        public static class ServiceDegradation {
            
            private final AtomicBoolean degraded = new AtomicBoolean(false);
            private final Random random = new Random();
            
            /**
             * 降级时使用本地UUID
             */
            public long generateDegradedId() {
                if (degraded.get()) {
                    // 使用时间戳 + 随机数生成临时ID
                    long timestamp = System.currentTimeMillis();
                    int randomPart = random.nextInt(1000000);
                    return timestamp * 1000000 + randomPart;
                }
                
                throw new IllegalStateException("Service not in degraded mode");
            }
            
            /**
             * 触发降级
             */
            public void triggerDegradation() {
                degraded.set(true);
                log.warn("ID generation service degraded to local mode");
            }
            
            /**
             * 恢复正常
             */
            public void recover() {
                degraded.set(false);
                log.info("ID generation service recovered to normal mode");
            }
        }
    }
}

📊 性能优化与监控

性能优化策略

/**
 * 性能优化组件
 */
@Component
public class PerformanceOptimization {
    
    /**
     * 缓存优化
     */
    @Component
    public static class CacheOptimization {
        
        @Autowired
        private RedisTemplate<String, Object> redisTemplate;
        
        private final LoadingCache<String, IdGenerator> generatorCache;
        
        public CacheOptimization() {
            this.generatorCache = Caffeine.newBuilder()
                .maximumSize(1000)
                .expireAfterAccess(Duration.ofHours(1))
                .build(this::createIdGenerator);
        }
        
        /**
         * 缓存ID生成器
         */
        public IdGenerator getCachedGenerator(String bizType) {
            return generatorCache.get(bizType);
        }
        
        /**
         * 预热缓存
         */
        @PostConstruct
        public void warmupCache() {
            List<String> commonBizTypes = Arrays.asList(
                "order", "user", "product", "payment"
            );
            
            commonBizTypes.forEach(bizType -> {
                try {
                    generatorCache.get(bizType);
                } catch (Exception e) {
                    log.warn("Failed to warmup cache for bizType: {}", bizType, e);
                }
            });
        }
    }
    
    /**
     * 批量处理优化
     */
    @Component
    public static class BatchOptimization {
        
        private final BlockingQueue<IdRequest> requestQueue = new LinkedBlockingQueue<>(10000);
        private final ScheduledExecutorService batchProcessor = Executors.newSingleThreadScheduledExecutor();
        
        @PostConstruct
        public void startBatchProcessor() {
            batchProcessor.scheduleWithFixedDelay(this::processBatch, 0, 10, TimeUnit.MILLISECONDS);
        }
        
        /**
         * 异步批量生成ID
         */
        public CompletableFuture<Long> generateIdAsync(String bizType) {
            CompletableFuture<Long> future = new CompletableFuture<>();
            IdRequest request = new IdRequest(bizType, future);
            
            if (!requestQueue.offer(request)) {
                future.completeExceptionally(new RuntimeException("Request queue full"));
            }
            
            return future;
        }
        
        /**
         * 处理批量请求
         */
        private void processBatch() {
            List<IdRequest> batch = new ArrayList<>();
            requestQueue.drainTo(batch, 100);
            
            if (!batch.isEmpty()) {
                // 按业务类型分组
                Map<String, List<IdRequest>> grouped = batch.stream()
                    .collect(Collectors.groupingBy(IdRequest::getBizType));
                
                // 批量生成ID
                grouped.forEach(this::processBizTypeBatch);
            }
        }
        
        private void processBizTypeBatch(String bizType, List<IdRequest> requests) {
            try {
                IdGenerator generator = getCachedGenerator(bizType);
                
                for (IdRequest request : requests) {
                    long id = generator.generateId();
                    request.getFuture().complete(id);
                }
                
            } catch (Exception e) {
                requests.forEach(request -> 
                    request.getFuture().completeExceptionally(e));
            }
        }
    }
    
    /**
     * 监控指标
     */
    @Component
    public static class MetricsCollector {
        
        @Autowired
        private MeterRegistry meterRegistry;
        
        private final Counter idGenerationCounter;
        private final Timer idGenerationTimer;
        private final Gauge qpsGauge;
        
        public MetricsCollector() {
            this.idGenerationCounter = Counter.builder("id.generation.count")
                .description("Total ID generation count")
                .register(meterRegistry);
                
            this.idGenerationTimer = Timer.builder("id.generation.duration")
                .description("ID generation duration")
                .register(meterRegistry);
                
            this.qpsGauge = Gauge.builder("id.generation.qps")
                .description("ID generation QPS")
                .register(meterRegistry, this, MetricsCollector::getCurrentQps);
        }
        
        /**
         * 记录ID生成指标
         */
        public void recordIdGeneration(String bizType, long duration) {
            idGenerationCounter.increment(Tags.of("bizType", bizType));
            idGenerationTimer.record(duration, TimeUnit.MILLISECONDS, Tags.of("bizType", bizType));
        }
        
        private double getCurrentQps() {
            // 计算当前QPS
            return idGenerationCounter.count() / 
                   (System.currentTimeMillis() - startTime) * 1000;
        }
    }
}

💡 面试回答要点

标准回答模板

第一部分：方案选择

"分布式ID生成主要有四种方案：
1. 数据库自增：简单但性能差，有单点问题
2. UUID：性能好但无序，不适合做主键
3. Snowflake：性能好且有序，推荐方案
4. 号段模式：数据库压力小，适合多业务场景

综合考虑选择Snowflake算法，64位结构：
时间戳(41位) + 机器ID(10位) + 序列号(12位)"

第二部分：架构设计

"整体架构包括：
1. 负载均衡：Nginx/LVS分发请求
2. ID服务集群：多实例部署，无状态设计
3. Worker ID管理：Redis分配和管理机器ID
4. 配置中心：统一管理配置参数
5. 监控告警：实时监控QPS、延迟等指标"

第三部分：高可用保障

"高可用策略：
1. 多机房部署：不同机房使用不同Worker ID范围
2. 故障转移：健康检查 + 自动摘除故障节点
3. 时钟回拨：小幅等待，大幅抛异常
4. 服务降级：异常时使用本地UUID生成
5. 容量规划：支持水平扩展"

第四部分：性能优化

"性能优化手段：
1. 批量处理：合并请求减少网络开销
2. 本地缓存：缓存生成器实例
3. 异步处理：请求队列 + 批量生成
4. 连接池：复用数据库和Redis连接
5. JVM调优：G1GC + 合理堆内存配置"

核心要点总结：

• ✅ 深入理解多种分布式ID生成算法的优缺点
• ✅ 掌握Snowflake算法原理和实现细节
• ✅ 具备高并发、高可用系统架构设计能力
• ✅ 理解分布式系统的容灾和性能优化策略