架构 - 缓存集群方案

拼搏现实的明天。 2022-04-15 05:56 358阅读 0赞

### 缓存集群面临的问题 ###

*  **路由**：假设我们的缓存服务器有3台，每台缓存的数据是不相同的，那么我们根据key获取缓存时，该从哪台服务器获取？
 *  **分压**：在新增服务器时，如何让新增的服务器平均的为各服务器减压
 *  **命中率**：在新增服务器后，如何保证命中率尽可能的高？

### 解决方案一：Hash取模路由（不推荐） ###

上面的问题可以通过取模的方式来进行路由，如下

...
    public static String getRoute(String key){ 
        int cacheIndex = key.hashcode() % 2;
        if(cacheIndex == 0){ 
            return "A缓存服务器";
        }
        return "B缓存服务器";
    }
    ...

这样可以对`固定数量`的缓存集群进行路由，如果数量发生改变，例如从2台缓存服务器增加到10台缓存服务器。模2的值和模10的值不一样就会导致路由的结果不正确。路由不正确就会查询数据库，大量的路由不正确就会给数据库增加压力。正因为这种方式在横向扩展的情况下命中率低，所以不推荐此方式进行路由。

### 解决方案二：Hash环路由（推荐） ###

Hash环的基本思路是获取所有的服务器节点hash值，然后获取key的hash，与节点的hash进行对比，找出顺时针最近的节点进行存储和读取。例如有以下服务器：

*  A服务器（hash:100）
 *  B服务器（hash:120）
 *  C服务器（hash:200）

当key的hash为105时，存储在B服务器。当key的hash为121时，存储在C服务器。

**命中率的计算（仅供参考）**  
在《大型网站技术架构》一书中提到hash一致性算法hash环的命中率为n/(n+1)，例如从3台服务器扩展到4台服务器，得到命中率为3/4=0.75。而我始终想不通这个公式。如果节点平均分配，这个命中率应该66.66%至100%之间，折中计算这个命中率也应该是83.33%。思路如下：

> ABC三台服务器，加入D服务器后介于BC之间，那么只会影响C服务器，AB服务器的数据路由不会有问题，只有在C服务器路由的时候可能会路由至D。AB占用数据比例为66.66%，折中计算C服务器有一半的数据还能命中等同于将一个饼平均分成六份，有五份命中，则得到5/6=0.8333。

**思考：为什么不直接全局找出最近的节点，而是要顺时针去找最近的节  
点？**  
如果现在加入D服务器（hash:140），我们希望尽可能的命中率高。假设我们是通过找出最近的节点来路由的。那么key hash在131至170的数据都会落在D服务器，无法命中。如果采用顺时针最近节点的方式路由，那么只有120-140的数据落在D服务器上。而我们在横向扩展时应尽可能高的保证缓存命中率，显然顺时针查找最近节点的方式命中率更高。

**思考：加入的D服务器介于BC之间，按照上面提到的思路可以得出D只会给C分担压力，那么如何让D服务器给AB服务器分担压力？**  
我们可以将一台服务器配置多个节点分布在Hash环上。例如将A服务器分成a1, a2, a3节点，B服务器分成b1, b2, b3节点，C服务器分成c1, c2, c3节点，这些节点都保存了对应的物理服务器信息。假设新加入的3个节点被随机分配在了a1,a2之间，b1,b2之间，c1,c2之间，那么就分别给ABC三台服务器分担了压力。

**关于Hash环路由算法实现如下（仅供参考）**  
`注意一`：命中率跟节点是否平均分布有关，不平均的节点分布将会导致命中率偏高或偏低。  
`注意二`：该类没有经历过项目的磨砺，内容仅供参考。

package caesar.hash;
    
    import java.math.BigInteger;
    import java.security.MessageDigest;
    import java.security.NoSuchAlgorithmException;
    import java.util.*;
    
    /** * Hash路由，适用于缓存集群等不要求命中率为100%的路由 * - 通过hash环实现hash路由 * - 通过节点名称或节点hash值添加节点 * - 通过二分法实现hash查找 * @author Caesar Liu * @date 2018/11/22 10:37 */
    public class HashRoute { 
    
        // hash环，key为节点hashcode，value为节点服务器信息
        private Map<Integer, Object> hashCircle = new HashMap<Integer, Object>();
    
        // 节点hash池，用于查找节点hash值
        private List<Integer> nodeHashPool = new ArrayList<Integer>();
    
        // HashRoute实例
        private static HashRoute instance = null;
    
        private HashRoute(){  }
    
        /** * 获取HashRoute实例 * @return */
        public static HashRoute getInstance(){ 
            synchronized (HashRoute.class){ 
                if(instance == null){ 
                    instance = new HashRoute();
                }
            }
            return instance;
        }
    
        /** * 通过hash值添加节点 * @param nodeHash * @param routeValue */
        public void add(int nodeHash, Object routeValue) throws NoSuchAlgorithmException { 
            this.hashCircle.put(nodeHash, routeValue);
            this.nodeHashPool.add(nodeHash);
        }
    
        /** * 通过名称添加节点 * @param nodeName * @param routeValue */
        public void add(String nodeName, Object routeValue) throws NoSuchAlgorithmException { 
            MessageDigest md = MessageDigest.getInstance("MD5");
            // 为了均匀的将节点分布在hash环中，将节点名称md5后再获取hashcode
            String nodeNameMd5 = new BigInteger(md.digest(nodeName.getBytes())).toString(16);
            this.hashCircle.put(nodeNameMd5.hashCode(), routeValue);
            this.nodeHashPool.add(nodeNameMd5.hashCode());
        }
    
        /** * 提交节点的变更 * - 将节点hash进行升序排序 */
        public void commit(){ 
            Collections.sort(this.nodeHashPool);
        }
    
        /** * 获取路由值 * @return */
        public Object getRouteValue(String key) throws NoSuchAlgorithmException{ 
            MessageDigest md5 = MessageDigest.getInstance("MD5");
            // 为了均匀的存储在集群中，将值（如订单id）进行md5后作为key
            String keyMd5 = new BigInteger(md5.digest(key.getBytes())).toString(16);
            return this.hashCircle.get(this.getNodeHashCode(keyMd5));
        }
    
        /** * 获取节点hashcode * @param key * @return */
        private Integer getNodeHashCode(String key){ 
            int keyHash = key.hashCode();
            // 通过二分法顺时针寻找节点hash值
            int startIndex = 0;
            int endIndex = this.nodeHashPool.size() - 1;
            // 临界点判断（形成Hash闭环并可给二分法提速），如果小于第一个索引值或大于最大索引值，则直接return 0下标节点hash
            if(keyHash <= this.nodeHashPool.get(startIndex)){ 
                return this.nodeHashPool.get(startIndex);
            }
            if(keyHash > this.nodeHashPool.get(endIndex)){ 
                return this.nodeHashPool.get(startIndex);
            }
            while(startIndex <= endIndex){ 
                int index = (startIndex + endIndex) / 2;
                int value = this.nodeHashPool.get(index);
                if(keyHash > value){ 
                    startIndex = index + 1;
                } else if(keyHash < value){ 
                    endIndex = index - 1;
                } else{ 
                    return this.nodeHashPool.get(index);
                }
            }
            // 如果是endIndex左移导致startIndex > endIndex，说明顺时针最近节点hash值为startIndex下的hash值
            // 如果是startIndex右移导致startIndex > endIndex，说明顺时针最近节点hash值为startIndex下的hash值
            return this.nodeHashPool.get(startIndex);
        }
    
        public static void main(String[] args) throws Exception{ 
            // 测试数
            final int TEST_COUNT = 100000;
            // 构造路由对象并添加服务器节点，一台服务器构造五个虚拟节点
            HashRoute hr = HashRoute.getInstance();
            hr.add("node1_1", "node1 uri");
            hr.add("node1_2", "node1 uri");
            hr.add("node1_3", "node1 uri");
            hr.add("node1_4", "node1 uri");
            hr.add("node1_5", "node1 uri");
            hr.add("node2_1", "node2 uri");
            hr.add("node2_2", "node2 uri");
            hr.add("node2_3", "node2 uri");
            hr.add("node2_4", "node2 uri");
            hr.add("node2_5", "node2 uri");
            hr.add("node3_1", "node3 uri");
            hr.add("node3_2", "node3 uri");
            hr.add("node3_3", "node3 uri");
            hr.add("node3_4", "node3 uri");
            hr.add("node3_5", "node3 uri");
            // 将节点变更提交
            hr.commit();
            // 记录原有的存储路由
            Map<String, Object> record = new HashMap<String, Object>();
            for(int i = 0; i < TEST_COUNT; i++){ 
                String key = "" + i;
                record.put(key, hr.getRouteValue(key));
            }
            // 增加一台服务器
            hr.add("node4_1", "node4 uri");
            hr.add("node4_2", "node4 uri");
            hr.add("node4_3", "node4 uri");
            hr.add("node4_4", "node4 uri");
            hr.add("node4_5", "node4 uri");
            hr.commit();
            // 计算命中率
            int matchCount = 0; // 命中数
            for(int i = 0; i < TEST_COUNT; i++){ 
                String key = "" + i;
                Object routeValue = hr.getRouteValue(key);
                // 如果路由结果相等，则视为命中
                if(routeValue.equals(record.get(key))){ 
                    matchCount++;
                }
            }
            System.out.println("命中率: " + (double)(matchCount)/TEST_COUNT);
        }
    
    }

（完）