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

常见提问方式： "CAP定理是什么？如何理解一致性Hash算法？"

技术深度： 分布式理论基础、算法原理、实际应用

预计阅读时间：35分钟

🎯 CAP定理

CAP定理基础

CAP定理指出，在分布式系统中，一致性（Consistency）、可用性（Availability）、分区容错性（Partition Tolerance）三者不可能同时满足，最多只能满足其中两个。

三要素详解：

/**
 * CAP定理演示
 */
public class CAPTheoremDemo {
    
    /**
     * 一致性（Consistency）
     * 所有节点在同一时间看到相同的数据
     */
    public void consistencyExample() {
        /*
         * 强一致性示例：
         * 用户在节点A更新了个人信息
         * 立即从节点B查询，必须能看到最新信息
         * 
         * 实现方式：
         * - 同步复制
         * - 分布式锁
         * - 两阶段提交
         */
    }
    
    /**
     * 可用性（Availability）
     * 系统在任何时候都能响应用户请求
     */
    public void availabilityExample() {
        /*
         * 高可用性示例：
         * 即使部分节点故障，系统仍能正常服务
         * 
         * 实现方式：
         * - 冗余备份
         * - 故障转移
         * - 负载均衡
         */
    }
    
    /**
     * 分区容错性（Partition Tolerance）
     * 系统能够容忍网络分区故障
     */
    public void partitionToleranceExample() {
        /*
         * 分区容错示例：
         * 网络故障导致节点间无法通信
         * 系统仍能继续运行
         * 
         * 实现方式：
         * - 数据复制
         * - 分布式一致性算法
         * - 故障检测机制
         */
    }
}

CAP权衡策略

/**
 * 不同系统的CAP选择
 */
@Component
public class CAPTradeoffs {
    
    /**
     * CP系统：选择一致性和分区容错性
     * 牺牲可用性，在网络分区时停止服务
     */
    public void cpSystemExample() {
        /*
         * 典型代表：
         * - MongoDB（强一致性模式）
         * - HBase
         * - Redis Cluster
         * 
         * 适用场景：
         * - 金融交易系统
         * - 库存管理系统
         * - 账户余额系统
         */
    }
    
    /**
     * AP系统：选择可用性和分区容错性
     * 牺牲一致性，允许数据暂时不一致
     */
    public void apSystemExample() {
        /*
         * 典型代表：
         * - Cassandra
         * - DynamoDB
         * - CouchDB
         * 
         * 适用场景：
         * - 社交媒体
         * - 内容分发
         * - 日志收集
         */
    }
}

/**
 * 实际项目中的CAP权衡
 */
@Service
public class PracticalCAPImplementation {
    
    @Autowired
    private DistributedLock distributedLock;
    
    /**
     * CP模式实现：订单创建
     */
    @Transactional
    public Order createOrderCP(CreateOrderRequest request) {
        String lockKey = "order:create:" + request.getUserId();
        
        if (!distributedLock.tryLock(lockKey, 30000)) {
            throw new ServiceUnavailableException("系统繁忙，请稍后重试");
        }
        
        try {
            // 强一致性检查
            if (!checkInventoryConsistency(request.getProductId(), request.getQuantity())) {
                throw new InsufficientStockException("库存不足");
            }
            
            Order order = new Order(request);
            return orderRepository.save(order);
        } finally {
            distributedLock.unlock(lockKey);
        }
    }
    
    /**
     * AP模式实现：用户信息更新
     */
    public void updateUserInfoAP(Long userId, UserInfo userInfo) {
        try {
            // 异步更新所有副本
            CompletableFuture.allOf(
                updateUserInfoAsync("primary", userId, userInfo),
                updateUserInfoAsync("replica1", userId, userInfo),
                updateUserInfoAsync("replica2", userId, userInfo)
            );
        } catch (Exception e) {
            log.warn("部分用户信息更新失败，将通过后台任务同步", e);
            recordFailedUpdate(userId, userInfo);
        }
    }
}

🔄 BASE理论

BASE理论概述

BASE理论是对CAP定理的延伸：

• BA（Basically Available）：基本可用
• S（Soft State）：软状态
• E（Eventually Consistent）：最终一致性

/**
 * BASE理论实现
 */
@Component
public class BASEImplementation {
    
    /**
     * 基本可用（Basically Available）
     */
    @Service
    public class BasicAvailabilityService {
        
        public UserInfo getUserInfo(Long userId) {
            // 尝试从主节点获取
            try {
                return primaryNode.getUserInfo(userId);
            } catch (Exception e) {
                log.warn("Primary node unavailable, trying backup nodes");
            }
            
            // 主节点不可用，尝试备份节点
            for (DataNode backupNode : backupNodes) {
                try {
                    UserInfo userInfo = backupNode.getUserInfo(userId);
                    if (userInfo != null) {
                        userInfo.setDataSource("backup");
                        return userInfo;
                    }
                } catch (Exception e) {
                    log.warn("Backup node {} unavailable", backupNode.getName());
                }
            }
            
            // 返回缓存数据
            return cacheService.getCachedUserInfo(userId);
        }
    }
    
    /**
     * 最终一致性（Eventually Consistent）
     */
    @Service
    public class EventualConsistencyService {
        
        @Transactional
        public void updateUserBalance(Long userId, BigDecimal amount) {
            // 1. 更新主数据
            User user = userRepository.findById(userId);
            user.setBalance(user.getBalance().add(amount));
            userRepository.save(user);
            
            // 2. 发布变更事件
            BalanceChangeEvent event = new BalanceChangeEvent();
            event.setUserId(userId);
            event.setAmount(amount);
            event.setNewBalance(user.getBalance());
            
            messageProducer.send("user.balance.changed", event);
        }
        
        @EventListener
        @Async
        public void handleBalanceChanged(BalanceChangeEvent event) {
            // 异步更新各个副本
            dataNodes.parallelStream().forEach(node -> {
                try {
                    node.updateUserBalance(event.getUserId(), event.getNewBalance());
                } catch (Exception e) {
                    log.error("Failed to sync balance to node: {}", node.getName(), e);
                    recordSyncFailure(node.getName(), event);
                }
            });
        }
        
        // 定时一致性检查
        @Scheduled(fixedRate = 300000)
        public void checkConsistency() {
            List<InconsistentData> inconsistencies = consistencyChecker.findInconsistencies();
            
            for (InconsistentData inconsistency : inconsistencies) {
                repairInconsistency(inconsistency);
            }
        }
    }
}

🔗 一致性Hash算法

算法原理

/**
 * 一致性Hash算法实现
 */
public class ConsistentHash<T> {
    
    private final int virtualNodes;
    private final SortedMap<Long, T> ring = new TreeMap<>();
    private final HashFunction hashFunction;
    
    public ConsistentHash(int virtualNodes, Collection<T> nodes) {
        this.virtualNodes = virtualNodes;
        this.hashFunction = Hashing.murmur3_128();
        
        for (T node : nodes) {
            addNode(node);
        }
    }
    
    /**
     * 添加节点
     */
    public void addNode(T node) {
        for (int i = 0; i < virtualNodes; i++) {
            String virtualNodeName = node.toString() + ":" + i;
            long hash = hashFunction.hashString(virtualNodeName, StandardCharsets.UTF_8).asLong();
            ring.put(hash, node);
        }
        log.info("Added node: {} with {} virtual nodes", node, virtualNodes);
    }
    
    /**
     * 移除节点
     */
    public void removeNode(T node) {
        for (int i = 0; i < virtualNodes; i++) {
            String virtualNodeName = node.toString() + ":" + i;
            long hash = hashFunction.hashString(virtualNodeName, StandardCharsets.UTF_8).asLong();
            ring.remove(hash);
        }
        log.info("Removed node: {}", node);
    }
    
    /**
     * 获取key对应的节点
     */
    public T getNode(String key) {
        if (ring.isEmpty()) {
            return null;
        }
        
        long hash = hashFunction.hashString(key, StandardCharsets.UTF_8).asLong();
        
        // 找到第一个大于等于hash值的节点
        SortedMap<Long, T> tailMap = ring.tailMap(hash);
        
        if (tailMap.isEmpty()) {
            return ring.get(ring.firstKey());
        } else {
            return tailMap.get(tailMap.firstKey());
        }
    }
    
    /**
     * 获取key对应的多个节点（用于副本）
     */
    public List<T> getNodes(String key, int count) {
        if (ring.isEmpty()) {
            return Collections.emptyList();
        }
        
        List<T> nodes = new ArrayList<>();
        Set<T> uniqueNodes = new HashSet<>();
        
        long hash = hashFunction.hashString(key, StandardCharsets.UTF_8).asLong();
        SortedMap<Long, T> tailMap = ring.tailMap(hash);
        
        // 先从tailMap中获取节点
        for (T node : tailMap.values()) {
            if (uniqueNodes.add(node)) {
                nodes.add(node);
                if (nodes.size() >= count) {
                    return nodes;
                }
            }
        }
        
        // 如果不够，从头开始获取
        for (T node : ring.values()) {
            if (uniqueNodes.add(node)) {
                nodes.add(node);
                if (nodes.size() >= count) {
                    return nodes;
                }
            }
        }
        
        return nodes;
    }
}

实际应用场景

/**
 * 一致性Hash在分布式缓存中的应用
 */
@Component
public class DistributedCacheWithConsistentHash {
    
    private ConsistentHash<CacheNode> consistentHash;
    private List<CacheNode> cacheNodes;
    
    @PostConstruct
    public void init() {
        cacheNodes = Arrays.asList(
            new CacheNode("cache-1", "192.168.1.10", 6379),
            new CacheNode("cache-2", "192.168.1.11", 6379),
            new CacheNode("cache-3", "192.168.1.12", 6379)
        );
        
        consistentHash = new ConsistentHash<>(150, cacheNodes);
    }
    
    public void set(String key, Object value) {
        CacheNode node = consistentHash.getNode(key);
        if (node != null) {
            try {
                node.set(key, value);
                log.debug("Set cache: key={}, node={}", key, node.getName());
            } catch (Exception e) {
                log.error("Failed to set cache: key={}, node={}", key, node.getName(), e);
                tryBackupNodes(key, value);
            }
        }
    }
    
    public Object get(String key) {
        CacheNode node = consistentHash.getNode(key);
        if (node != null) {
            try {
                return node.get(key);
            } catch (Exception e) {
                log.error("Failed to get cache: key={}, node={}", key, node.getName(), e);
                return tryGetFromBackupNodes(key);
            }
        }
        return null;
    }
    
    public void addCacheNode(CacheNode newNode) {
        cacheNodes.add(newNode);
        consistentHash.addNode(newNode);
        
        log.info("Added cache node: {}", newNode.getName());
        migrateDataToNewNode(newNode);
    }
    
    public void removeCacheNode(CacheNode nodeToRemove) {
        migrateDataFromRemovedNode(nodeToRemove);
        
        cacheNodes.remove(nodeToRemove);
        consistentHash.removeNode(nodeToRemove);
        
        log.info("Removed cache node: {}", nodeToRemove.getName());
    }
}

public class CacheNode {
    private String name;
    private String host;
    private int port;
    private RedisTemplate<String, Object> redisTemplate;
    
    public void set(String key, Object value) {
        redisTemplate.opsForValue().set(key, value, Duration.ofHours(1));
    }
    
    public Object get(String key) {
        return redisTemplate.opsForValue().get(key);
    }
    
    public Set<String> getAllKeys() {
        return redisTemplate.keys("*");
    }
    
    // 构造函数、equals、hashCode等方法省略...
}

🎲 分布式一致性算法

Raft算法核心概念

/**
 * Raft算法演示
 */
public class RaftAlgorithmDemo {
    
    public enum NodeState {
        FOLLOWER, CANDIDATE, LEADER
    }
    
    public class RaftNode {
        private String nodeId;
        private NodeState state = NodeState.FOLLOWER;
        private int currentTerm = 0;
        private String votedFor = null;
        private List<LogEntry> log = new ArrayList<>();
        
        /**
         * 开始选举
         */
        public void startElection() {
            state = NodeState.CANDIDATE;
            currentTerm++;
            votedFor = nodeId;
            
            log.info("Node {} started election for term {}", nodeId, currentTerm);
            
            int votes = 1; // 自己的票
            for (RaftNode otherNode : otherNodes) {
                if (otherNode.requestVote(currentTerm, nodeId)) {
                    votes++;
                }
            }
            
            if (votes > (totalNodes / 2)) {
                becomeLeader();
            } else {
                state = NodeState.FOLLOWER;
            }
        }
        
        /**
         * 处理投票请求
         */
        public boolean requestVote(int term, String candidateId) {
            if (term < currentTerm) {
                return false;
            }
            
            if (term > currentTerm) {
                currentTerm = term;
                votedFor = null;
                state = NodeState.FOLLOWER;
            }
            
            if (votedFor == null || votedFor.equals(candidateId)) {
                votedFor = candidateId;
                return true;
            }
            
            return false;
        }
        
        /**
         * 成为Leader
         */
        private void becomeLeader() {
            state = NodeState.LEADER;
            log.info("Node {} became leader for term {}", nodeId, currentTerm);
            startHeartbeat();
        }
        
        /**
         * 发送心跳
         */
        private void startHeartbeat() {
            ScheduledExecutorService executor = Executors.newSingleThreadScheduledExecutor();
            executor.scheduleAtFixedRate(() -> {
                if (state == NodeState.LEADER) {
                    for (RaftNode follower : otherNodes) {
                        follower.appendEntries(currentTerm, nodeId);
                    }
                }
            }, 0, 50, TimeUnit.MILLISECONDS);
        }
    }
    
    public static class LogEntry {
        private int term;
        private String command;
        private long timestamp;
        
        // 构造函数和getter/setter省略...
    }
}

💡 面试回答要点

标准回答模板

第一部分：CAP定理

"CAP定理是分布式系统的基础理论，指出一致性、可用性、分区容错性三者不可兼得。
在实际项目中，我们根据业务场景选择：
- 金融系统选择CP，保证数据一致性
- 社交系统选择AP，保证服务可用性
- 通过BASE理论实现最终一致性"

第二部分：一致性Hash

"一致性Hash解决分布式系统中数据分布和负载均衡问题。
核心思想是将数据和节点都映射到Hash环上，通过虚拟节点解决数据倾斜。
在缓存集群中，当节点增减时，只需要迁移少量数据，
大大减少了数据迁移成本。"

第三部分：实际应用

"在我们的项目中：
1. 使用Redis集群实现分布式缓存，采用一致性Hash分片
2. 通过消息队列实现最终一致性
3. 关键业务使用分布式锁保证强一致性
4. 监控系统采用Raft算法保证配置一致性"

核心要点总结：

• ✅ 深入理解CAP定理和BASE理论
• ✅ 掌握一致性Hash算法原理和应用
• ✅ 了解分布式一致性算法（Raft、Paxos）
• ✅ 能够根据业务场景选择合适的一致性策略