缓存：无底洞优化。

小咪咪 2022-02-01 12:07 198阅读 0赞

2010年，facebook的Memcache节点已经达到了3000个，承载着TB级别的缓存数据。但开发和运维人员发现一个问题，为了满足业务要求添加了大量新Memcache节点，但是发现性能不但没有好转反而下降了，当时将这种现象称为缓存的“无底洞”现象。  
那么为什么会产生这种现象呢，通常来说添加节点使得Memcache集群性能应该更强了，但事实并非如此。键值数据库由于通常采用哈希函数将key映射到各个节点上，造成key的分布与业务无关，但是由于数据量和访问量的持续增长，造成需要添加大量节点做水平扩容，导致键值分布到更多的节点上，所以无论是Memcache还是Redis的分布式，批量操作通常需要从不同节点上获取，相对于单机批量操作只涉及一次网络操作，分布式批量操作会涉及多次网络时间。  
下图展示了在分布式条件下，一次mget操作需要访问多个Redis节点，需要多次网络时间。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VuX2pva2Vy_size_16_color_FFFFFF_t_70][]

而下图由于所有键值都集中在一个节点上，所以一次批量操作只需要一次网络时间。

# ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VuX2pva2Vy_size_16_color_FFFFFF_t_70 1][]   无底洞问题分析 #

*  客户端一次批量操作会涉及多次网络操作，也就意味着批量操作会随着节点的增多，耗时会不断增大。
 *  网络连接数变多，对节点的性能也有一定影响。

用一句通俗的话总结就是，更多的节点不代表更高的性能，所谓“无底洞”就是说投入越多不一定产出越多。但是分布式又是不可以避免的，因为访问量和数据量越来越大，一个节点根本扛不住，所以如何高效的在分布式缓存中批量操作是一个难点。  
下面介绍如何在分布式条件下优化批量操作。在介绍具体的方法之前，我们来看一下常见的IO优化思路：

*  命令本身的优化，例如优化SQL语句等。
 *  减少网络通信次数。
 *  降低接入成本，例如客户端使用长连接/连接池、NIO等。

这里我们假设命令、客户端连接已经为最优，重点讨论减少网络操作次数。  
以Redis批量获取n个字符串为例，有三种实现方法，如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VuX2pva2Vy_size_16_color_FFFFFF_t_70 2][]

*  客户端n次get：n次网络+n次get命令本身。
 *  客户端1次pipeline get：1次网络+n次get命令本身。
 *  客户端1次mget：1次网络+1次mget命令本身。

上面已经给出了IO的优化思路以及单个节点的批量操作优化方式，下面我们将结合Redis Cluster的一些特性对四种分布式的批量操作方式进行说明。

# 串行命令 #

由于n个key是比较均匀的分布在Redis Cluster的各个节点上，因此无法使用mget命令一次性获取，所以通常来讲要获取n个key的值，最简单的方法就是逐次执行n个get命令，这种操作时间复杂度较高，他的操作时间=n次网络时间+n次命令时间，网络次数是n。很显然这种方案不是最优的，但是实现起来比较简单，如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VuX2pva2Vy_size_16_color_FFFFFF_t_70 3][]

Jedis客户端示例代码如下：

List<String> serialMGet(List<String> keys) {
        // 结果集
        List<String> values = new ArrayList<String>();
        // n次串行get
        for(String key : keys) {
            String value = jedisCluster.get(key);
            values.add(value);
        }
        return values;
    }

# 串行IO #

Redis Cluster使用CRC16算法计算出散列值，再取对16383的余数就可以算出slot值，同时Smart客户端会保存slot和节点的对应关系，有了这两个数据就可以将属于同一个节点的key进行归档，得到每个节点的key子列表，之后对每个节点执行mget或者Pipeline操作，他的操作时间=node次网络时间+n次命令时间，网络次数是node的个数，整个过程如下图所示，很明显这种方案比第一种要好很多，但是如果节点数太多，还是有一定的性能问题。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VuX2pva2Vy_size_16_color_FFFFFF_t_70 4][]  
Jedis客户端示例代码如下：

Map<String, String> serialIOMget(List<String> keys) {
        // 结果集
        Map<String, String> keyValueMap = new HashMap<String, String>();
        // 属于各个节点的key列表，JedisPool要提供基于ip和port的hashcode方法
        Map<JedisPool, List<String>> nodeKeyListMap = new HashMap<JedisPool, List<String>>();
        for(String key : keys) {
            // 使用CRC16本地计算每个key的slot
            int slot = JedisClusterCRC16.getSlot(key);
            // 通过jedisCluster本地slot→node映射获取slot对应的node
            JedisPool jedisPool = jdisCluster.getConnectionHandler().getJedisPoolFromSlot(slot);
            // 归档
            if(nodeKeyListMap.containsKey(jedisPool)) {
                nodeKeyListMap.get(jedisPool).add(key);
            } else {
                List<String> list = new ArrayList<String>();
                list.add(key);
                nodeKeyListMap.put(jedisPool, list);
            }
        }
        // 从每个节点上批量获取，这里使用mget也可以使用pipeline
        for(Entry<JedisPool, List<String>> entry : nodeKeyListMap.entrySet()) {
            JedisPool jedisPool = entry.getKey();
            List<String> nodeKeyList = entry.getValue();
            // 列表变为数组
            String[] nodeKeyArray = nodeKeyList.toArray(new String[nodeKeyList.size()]);
            // 批量获取，可以使用mget或者Pipeline
            List<String nodeValueList = jedisPool.getResource().mget(nodeKeyArray);
            // 归档
            for(int i = 0; i < nodeKeyList.size(); i++) {
                keyValueMap.put(nodeKeyList.get(i), nodeValueList.get(i));
            }
        }
        return keyValueMap;
    }

# 并行IO #

此方案是将方案2中的最后一步改为多线程执行，网络次数虽然还是节点个数，但由于使用多线程网络时间变为O(1)，这种方案会增加编程的复杂度。他的操作时间为：

> max\_slow(node网络时间)+n次命令时间

整个过程如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VuX2pva2Vy_size_16_color_FFFFFF_t_70 5][]

Jedis客户端示例代码如下，只需要将串行IO变为多线程：

Map<String, String> parallelIOMget(List<String> keys) {
        // 结果集
        Map<String, String> keyValueMap = new HashMap<String, String>();
        // 属于各个节点的key列表
        Map<JedisPool, List<String>> nodeKeyListMap = new HashMap<JedisPool,List<String>>();
        ... 和前面一样
        // 多线程mget，最终汇总结果
        for(Entry<JedisPool, List<String>> entry : nodeKeyListMap.entrySet()) {
            // 多线程实现
        }
        return keyValueMap;
    }

# hash\_tag实现 #

Redis Cluster的hash\_tag功能，他可以将多个key强制分配到一个节点上，他的操作时间=1次网络时间+n次命令时间，如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VuX2pva2Vy_size_16_color_FFFFFF_t_70 6][]

如下图所示，所有key属于node2节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VuX2pva2Vy_size_16_color_FFFFFF_t_70 7][]

Jedis客户端示例代码如下：

List<String> hashTagMget(String[] hashTagKeys) {
        return jedisCluster.mget(hashTagKeys);
    }

上面已经对批量操作的四种方案进行了介绍，最后通过下表来对四种方案的优缺点、网络IO次数进行一个总结。

<table style="width:698px;"> 
 <thead> 
  <tr> 
   <th>方案</th> 
   <th>优点</th> 
   <th>缺点</th> 
   <th>网络IO</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>串行命令</td> 
   <td> <p>编程简单</p> <p>如果少量keys，性能可以满足要求</p> </td> 
   <td>大量keys请求延迟严重</td> 
   <td><em>O(keys)</em></td> 
  </tr> 
  <tr> 
   <td>串行IO</td> 
   <td> <p>编程简单</p> <p>少量节点，性能满足要求</p> </td> 
   <td>大量node延迟严重</td> 
   <td><em>O(nodes)</em></td> 
  </tr> 
  <tr> 
   <td>并行IO</td> 
   <td>利用并行特性，延迟取决于最慢的节点</td> 
   <td> <p>编程复杂</p> <p>由于多线程，问题定位可能较难</p> </td> 
   <td><em>O(max_slow(nodes))</em></td> 
  </tr> 
  <tr> 
   <td>hash_tag</td> 
   <td>性能最高</td> 
   <td> <p>业务维护成本较高</p> <p>容易出现数据倾斜</p> </td> 
   <td><em>O(1)</em></td> 
  </tr> 
 </tbody> 
</table>

实际开发中可以根据上表给出的优缺点进行分析，没有最好的方案只有最适合的方案。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VuX2pva2Vy_size_16_color_FFFFFF_t_70]: /images/20220201/d58650741a7548b09ba6b24d9c87c9f3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VuX2pva2Vy_size_16_color_FFFFFF_t_70 1]: /images/20220201/daa78a39687d43bb85686110cf3ccd3a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VuX2pva2Vy_size_16_color_FFFFFF_t_70 2]: /images/20220201/936ac19230ac4313b9fc65f688563d67.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VuX2pva2Vy_size_16_color_FFFFFF_t_70 3]: /images/20220201/f48dd7857d0441f0aa3f457217392e37.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VuX2pva2Vy_size_16_color_FFFFFF_t_70 4]: /images/20220201/6a17e29e9d0e4a539f0d128a8f26da02.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VuX2pva2Vy_size_16_color_FFFFFF_t_70 5]: /images/20220201/a772588ce2fd4e0ebe978e2b96b41d7e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VuX2pva2Vy_size_16_color_FFFFFF_t_70 6]: /images/20220201/9a6de6a760214d2a8fb325b4aa646dc0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VuX2pva2Vy_size_16_color_FFFFFF_t_70 7]: /images/20220201/fbc754844e9e421da687139971a10246.png