分布式缓存布置方案

川长思鸟来 2022-06-17 13:11 178阅读 0赞

*  普通hash分布
 *  一致性hash分布
 *  一致性hash代码示例

有时我们仅布置一台缓存机器（如mencached，redis）是不够的，因此需要分布式缓存。

那么问题来了，当我们布置了多台机器，我们如何确定一个数据应该保存在哪一台机器上？或者说，我们怎么知道我们要查询的数据分布在哪一台机器上？

通常有以下两种方式：

1.  普通hash分布
2.  一致性hash分布

下面以PHP为例

# 普通hash分布 #

普通hash分布很简单，就是将缓存数据的key进行hash运算，直接映射到一台机器上。例如使用以下hash算法：

function mhash($key){ 
        $md5 = substr(md5($key),0,8);
        $seed = 31;
        $hash = 0;
    
        for($i = 0;$i<strlen($md5);$i++){
            $hash = $hash * $seed + ord($md5[$i]);
        }
        return $hash & 0x7FFFFFFF;
    }

hash算法有很多种，上面只是随便列了一种，大家可以另外自行百度其他hash算法。

hash算法计算出来的结果是一个整数，假设我们现在有2台机器，直接将hash得到的结果除以2取余数，可以得到0或者1，直接对应我们的2台机器。

$server_list = [
        '192.168.3.100',
        '192.168.3.101',
    ];
    
    $server = $server_list[mhash($key)%2];

得到服务器ip，就可以进行存取数据的操作了。

# 一致性hash分布 #

当服务器数量会发生变化时，普通hash算法就不可用了。因为hash得到值要除以服务器数量取余数来确定数据存放哪一台，如果服务器数量改变了，最终得到的服务器会不同，就无法精确的存取数据了。

而一致性hash就解决了这个问题，它的原理如下：

我们可以想象现在有一个逆时针的环，然后把多台机器的ip都进行hash运算，最终分布在这个环上，如下图所示的server1，server2，server3（按顺序分布）：

![这里写图片描述][SouthEast]

同时将我们要存储的数据的key也进行hash运算，得出的结果也分布在这个环上，如图中所示的k1~k4。

那么我们就可以把k1和k2的数据存到server2中，k3存到server3中，k4存到server1中。这样我们就找到了数据的归属服务器。

当新增服务器时，假设增加了server5服务器，如下图：

![这里写图片描述][SouthEast 1]

那么我们就将k1搬到server5，k2还是在server2中，其他数据维持不变。这就是一致性hash。

减少一台服务器时，原理和增加服务器是一样的。

> 注意，上图中所示的server的hash值在环上是按顺序排列的，这样我们才能根据大小来找到对应关系。

# 一致性hash代码示例 #

<?php /** * Created by PhpStorm. * User: zhoujun * Date: 2017/4/26 * Time: 20:43 */ function mhash($key){ $md5 = substr(md5($key),0,8); $seed = 31; $hash = 0; for($i = 0;$i<strlen($md5);$i++){ $hash = $hash * $seed + ord($md5[$i]); } return $hash & 0x7FFFFFFF; } class serverHash{ public $server_list = []; public $is_sort = false; /** * @param $server_ip * 新增服务器 */ function addServer($server_ip){ $hash = mhash($server_ip); if(!isset($this->server_list[$hash])){ $this->server_list[$hash] = $server_ip; //要查找key所对应的服务器ip时,需先对服务器进行排序,这里先标记它为未排序状态 $this->is_sort = false; } } /** * @param $key * 查询这个key所对应的服务器ip */ function lookup($key){ $hash = mhash($key); if($this->is_sort == false){ krsort($this->server_list,SORT_NUMERIC); $this->is_sort = true; } foreach ($this->server_list as $pos => $ip){ if($hash >= $pos){ return $ip; } } return end($this->server_list); } } $server = new serverHash(); $server->addServer('192.168.3.100'); echo 'k1所在服务器:'.$server->lookup('k1').PHP_EOL; echo 'k2所在服务器:'.$server->lookup('k2').PHP_EOL; $server->addServer('192.168.3.101'); echo 'k1所在服务器:'.$server->lookup('k1').PHP_EOL; echo 'k2所在服务器:'.$server->lookup('k2').PHP_EOL; echo 'k3所在服务器:'.$server->lookup('k3').PHP_EOL; echo 'k4所在服务器:'.$server->lookup('k4').PHP_EOL; $server->addServer('192.168.3.102'); echo 'k5所在服务器:'.$server->lookup('k5').PHP_EOL; echo 'k6所在服务器:'.$server->lookup('k6').PHP_EOL;

运行结果如下：

k1所在服务器:192.168.3.100
    k2所在服务器:192.168.3.100
    k1所在服务器:192.168.3.101
    k2所在服务器:192.168.3.100
    k3所在服务器:192.168.3.100
    k4所在服务器:192.168.3.101
    k5所在服务器:192.168.3.102
    k6所在服务器:192.168.3.102

[SouthEast]: /images/20220617/7f9b8c55f7af4300aef68f7fe5d7f0f5.png
[SouthEast 1]: /images/20220617/87226c8c0d6d415799de00accaac8f93.png