Nginx upstream_consistent_hash 一致性哈希避免大量缓存失效

Nginx upstream_consistent_hash 一致性哈希避免大量缓存失效

哈希负载均衡原理

ngx_nginx 普通的hash算法支持配置server接收到的请求会的数量和server数量变化之间会有变化。尤其是在负载均衡配置的upstream server数量发生增长后，造成产生的请求可能会在后端的upstream server中并不均匀，有的upstream server负载很低，有的upstream server负载较高，这样的负载均衡的效果比较差，可能对upstream server造成不良的影响。由此，产生了一致性hash算法来均衡。下面介绍的是upstream_hash模块实现的一致性Hash算法。

Hash负载均衡算法带来的问题

这里做个简化，将客户端的key和hash算法都简化。正常情况下没有宕机的时候客户端的key=5,6,7,8,9通过hash算法key%5对应到上游服务器server0,1,2,3,4。通过key%5的算法决定的客户端的请求具体的落到了上游服务器哪台server上面。（不过这是以简化的方式来说明问题，通俗易懂）

可以看到当一台server宕机以后，比如下线了一台server4，或者扩容了一台server5。都会导致以前的key它的路由的server发生变化，比如下线了server4，那么hash算法就变成了key%4，之前的算法key%5就失效了。导致key=5的客户端原本路由到server0上变成了路由到server1，同理增加一台后果也类似。这样的结果是在上游服务有缓存的情况下会导致缓存大量失效，特别面对的是大流量的场景下面，某一台server的缓存经常被命中使得该server能够服务于这么多的用户。由于更改了hash算法以及上游服务server的数量会导致一瞬间所有的server缓存几乎都失效了，这样会引发恶性的连锁反应！！！！！

如何去解决这样的问题呢？这个就需要通过一致性hash算法来解决

一致性Hash算法避免大量缓存失效

当后端是缓存服务器时，经常使用一致性哈希算法来进行负载均衡。使用一致性哈希的好处在于，增减集群的缓存服务器时，只有少量的缓存会失效，回源量较小。在nginx+ats / haproxy+squid等CDN架构中，nginx/haproxy所使用的负载均衡算法便是一致性哈希。

通过一致性Hash算法可以缓解我们扩容或者宕机的时候我们的路由不要大规模的发生变化，当我们上游服务是使用缓存的时候，不会导致大范围的缓存失效。当然它并不能解决扩容或者宕机之后所有节点的路由都不会发生变化，这个是解决不了的，当然也没有必要去解决。当我们上游应用含有缓存的时候一致性Hash算法可以避免大量的缓存失效。

那么为什么一致性hash算法能改善这种情况呢？

因为对于hash(k)的范围在int范围，所以我们将0~2^32作为一个环。其步骤为： 1，求出每个服务器的hash（服务器ip）值，将其配置到一个 0~2^n 的圆环上（n通常取32）。 2，用同样的方法求出待存储对象的主键 hash值，也将其配置到这个圆环上，然后从数据映射到的位置开始顺时针查找，将数据分布到找到的第一个服务器节点上。其分布如图：

这是一致性hash算法的基本原理，接下来我们看一下，此算法是如何解决我们上边说的缓存系统的扩展或者节点宕机导致的缓存失效的问题。比如:再加入一个redis节点：

如上图，当我们加入redis node5之后，影响的范围只有黄色标出的那部分，不会造成全局的变动。

除了上边的优点，其实还有一个优点：对于热点数据，如果发现node1访问量明显很大，负载高于其他节点，这就说明node1存储的数据是热点数据。这时候，为了减少node1的负载，我们可以在热点数据位置再加入一个node，用来分担热点数据的压力。 雪崩效应，接下来我们来看一下，当有节点宕机时会有什么问题。如下图：

如上图，当B节点宕机后，原本存储在B节点的k1，k2将会迁移到节点C上，这可能会导致很大的问题。如果B上存储的是热点数据，将数据迁移到C节点上，然后C需要承受B+C的数据，也承受不住，也挂了。。。。然后继续CD都挂了。这就造成了雪崩效应。 上面会造成雪崩效应的原因分析： 如果不存在热点数据的时候，每台机器的承受的压力是M/2(假设每台机器的最高负载能力为M)，原本是不会有问题的，但是，这个时候A服务器由于有热点数据挂了，然后A的数据迁移至B，导致B所需要承受的压力变为M（还不考虑热点数据访问的压力），所以这个失败B是必挂的，然后C至少需要承受1.5M的压力。。。。然后大家一起挂。。。 所以我们通过上面可以看到，之所以会大家一起挂，原因在于如果一台机器挂了，那么它的压力全部被分配到一台机器上，导致雪崩。

怎么解决雪崩问题呢，这时候需要引入虚拟节点来进行解决。

虚拟节点，我们可以针对每个实际的节点，虚拟出多个虚拟节点，用来映射到圈上的位置，进行存储对应的数据。如下图：

如上图：A节点对应A1，A2，BCD节点同理。这时候，如果A节点挂了，A节点的数据迁移情况是:A1数据会迁移到C2，A2数据迁移到D1。这就相当于A的数据被C和D分担了，这就避免了雪崩效应的发送，而且虚拟节点我们可以自定义设置，使其适用于我们的应用。

如果还不清楚看下面

说一致性哈希是什么，那我们肯定需要告诉面试官为啥要用一致性哈希，直接使用哈希不香？有什么问题嘛？

我先用个简单的例子让大伙看一波为啥使用一致性哈希

现在我们有一个分布式缓存，需要存放6w张美女照片，别问我干啥，就是存着

三节点存储image

方案1:直接采用哈希算法，对每个图片进行分片

哈希

余数正好对应每个机器节点

这样子会出现什么问题？

通过哈希算法，每个key可以寻址对应服务器，假设发过来的请求为key01，计算公式为hash(key01)%3

经过计算后寻址编号为1的服务器节点，如下图所示

节点1服务器

此时加入新的服务器节点，就会出现路由失败的情况。此时从三个节点变化为4个节点，之前的hash(kley01)%3=1就变化为 hash(key-01) % 4 = X，因为取模运算发生了变化，所以这个 X 大概率不是 1，这时你再查询，就会找不到数据了，因为 key-01 对应的数据，存储在节点 A 上，而不是节点 B。同样的道理，如果我们需要下线 1 个服务器节点（也就是缩容），也会存在类似的可能查询不到数据的问题

对于这个问题怎么解决呢

我们就需要迁移数据，基于新的计算公式 hash(key-01) % 4 ，来重新对数据和节点做映射。需要注意的是，数据的迁移成本是非常高的。

如何解决这个问题---一致性哈希

一致性哈希也是使用了取模运算，但是和传统的取摸运算不同，一致性哈希算法是对2^32 - 1进行取模运算

即使这些数据均匀，但是数据的活跃度不同，存放热点数据多的节点访问量非常大，就很容易的达到CPU瓶颈。一致性哈希算法即将整个哈希值空间组织成一个虚拟的圆环---哈希环

通过哈希算法，将节点映射到哈希环上，通常是节点主机名，ip地址等如下图

哈希环

在寻址的过程就只需要两步

将key作为参数执行c-hash计算出哈希值，确定key在环的位置从这个位置沿着哈希环顺时针走，遇到的第一个节点即key对应的节点

如下图所示

寻址案例

从上图可以发现，key01对应节点A，key03对应节点C，如果此时C宕机了，只需要将key03定位到节点A即可，key01和key02并不需要改变。所以一致性哈希算法在增加和减少节点的时候，只需要重新定位一小部分数据而不需要重新定位所有数据，这样就实现了"增加/减少节点需要大规模迁移"这个问题

节点B失效

如果节点比较少，是不是很容易就将请求数据打到一个节点呢？

这个问题即"数据倾斜问题"，由于节点的不均匀是的大量你的请求访问到节点A上，造成负载不均衡。

数据倾斜

鉴于这个问题引入了虚拟节点，简单的来说通过增加节点的个数来缓解节点的不均匀现象

所谓虚拟节点即对每个服务器节点计算多个哈希值，假设一个真实的节点有2个虚拟节点，此时我的三个节点就共有6个虚拟节点，如下图所示

引入虚拟节点

此时如果在环上顺时针寻找虚拟节点，假设key01选择虚拟节点nodeB02，那么此时将请求映射到真是节点B即可

所以通过虚拟节点扩充节点数量的方式解决节点较少情况下数据倾斜的问题，代价非常小，只需要增加一个字典map维护真实节点和虚拟节点的映射关系即可

ngx_$remote_addr：可以根据客户端ip映射 consistent_hash $request_uri： 根据客户端请求的uri映射 consistent_hash $args：根据客户端携带的参数进行映射

指令 语法：consistent_hash variable_name 默认值：none 上下文：upstream

配置upstream采用一致性hash作为负载均衡算法，并使用配置的变量名作为hash输入。

安装# wget unzip master.zip # ./configure --add-module=./3thparty/ngx_make# make install# wget unzip master.zip # ./configure --add-module=./3thparty/ngx_make# make install例子 upstream somestream { consistent_hash $request_uri; server 10.50.1.3:11211; server 10.50.1.4:11211; server 10.50.1.5:11211; } ... server { listen 80; server_name localhost; location / { default_type text/html; set $memcached_key $request_uri; memcached_pass somestream; error_page 500 404 405 = @fallback; } location @fallback { root /srv/ fastcgi_intercept_errors on; error_page 404 = @404; set $script $uri; set $path_info ""; include /usr/local/nginx/conf/fastcgi_params; fastcgi_param SCRIPT_FILENAME /srv/ fastcgi_param SCRIPT_NAME $script; fastcgi_param REQUEST_URI $uri; fastcgi_pass 127.0.0.1:9000; } }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。