HOME
BLOG
TIME
FRIENDS
SAY TO ME
MOOD
TRAVELING
Nginx调度算法——基于指定的key的hash表来实现对请求的调度
2020/08/16 1.3k 4 分钟 点击

这里记录一下Nginx调度算法中的其中一个,基于指定的key的hash表来实现对请求的调度的理解。
首先看图:

在客户端访问uri为/test1.html的文件的时候,Nginx调度服务器会把请求发送到后端缓存服务器上,以便于可以加速用户访问,但是分发到哪个缓存服务器呢?是RS1还是RS2?这是便涉及到了负载均衡的调度算法,我们需要有一个完美的解决办法,来应付这种场景,RS1和RS2的性能不同,所以承担的工作量也不能相同,这里我们假定RS1的性能优秀,需要承担2份工作,RS2比较差一些,承担1份,所以他们的负载比就是2:1。

于是,我们把所以的访问请求分成了三份,RS1两份,RS2一份,但是如何让他们按照2:1来份呢,有一个好办法可以解决。我们把用户访问的uri的名称,比如图中的test1.html,我们把它进行哈希值运算,得出一个值:
1f8fe9b32a77c1d3e2ea294ea22d5026c3f9a685,这个时候再把这个哈希值除以总份数(3份),取他对余数,他的余数无非是0,1,2三种,那我们就规定,余数是0,1的,我们把它调度到RS1上去,余数是2的我们把它调度到RS2上去,这样就解决了调度问题。

但是问题又来了,如果有一台Cache服务器坏了呢?或者想增加一台Cache服务器,那这以前所以的缓存全部都失效了,如果增加一台,变为四台,取余之后是0,1,2,3四种情况,按照以前的规定,就不再是2:1的负载比了。减少一台是同样的道理,也还是不行。我们需要更加自动化的解决方案。于是便有了一致性hash算法。

我们在这里加了一台Cache服务器,它是RS3,我们赋予它们新的权重,2:1:3,这里我们换一个思路,我们先把Cache服务器的IP进行hash运算,得出一个值,然后根据权重,如果Cache服务器权重为2,我们就把这个Cache服务器IP的哈希值先加1,就是这样:hash(RS1IP)+1,然后再弄一个加2的,hash(RS1IP)+2。这样我们就拥有对于RS1服务器的两个虚拟IP值,hash(RS1IP)+1和hash(RS1IP)+2。同样的道理,对于RS2和RS3来说,他们的分别是:hash(RS2IP)+1 ;hash(RS3IP)+1,hash(RS3IP)+2,hash(RS3IP)+3.
然后看下图:

我们从0开始一直到2的32次方-1,由这么多数字构建了一个哈希环,它是由数字围成的。我们就有了调度的服务器IP映射点。

接下来,我们把 hash(RS1IP)+1,hash(RS1IP)+2,hash(RS2IP)+1,hash(RS3IP)+1,hash(RS3IP)+2,hash(RS3IP)+3这些值再一次进行hash运算,得出:
hash( hash(RS1IP)+1),hash( hash(RS1IP)+2),
hash( hash(RS2IP)+1),hash( hash(RS3IP)+1),hash( hash(RS3IP)+2),hash( hash(RS3IP)+3)这些值。我们再使用这些值与2^32进行取余运算,得到的值会密密麻麻的分布在这个哈希环上,上述的6个地址,每一个都这样进行运算,它们的余数都会落到这个环上,而这个时候,我们把用户的uri通过hash运算之后,也和2^32进行取余运算,得到的值也会落到这个hash环上。 那么,uri取余之后这个点靠近哪个IP取余的点,就缓存在谁那里。这里需要顺时针查找,假设一个节点坏了。那么下一次的计算结果就是旁边的邻居。但是邻居的缓存不会受到影响。只是坏掉的A节点会重新去缓存。这样就解决了坏掉一个缓存服务器影响全局的问题。

但是,再要是极端一点呢?假设取余之后的数值全挤在一块,不是均匀的分布在哈希环上,这样就造成了有可能所有的负载全部集中到了一台缓存服务器上,造成哈希环的偏斜。

如何解决呢?一致性hash就解决这个太过凑巧的问题,上述我们使用IP+1来解决的,我们得到了6个IP,这便是我们造成太过凑巧的原因所在,如果我们不把IP个数通过权重的个数来控制呢?我们这样:IP+权重100,就会得到600个IP,这样是不是挤在一起的机会就会小很多呢?这如果还不行,那就IP+权重1000,6000个这样就可以了。

这就是,Nginx调度算法中基于指定的key的hash表来实现对请求的调度对底层原理,不过对于Nginx来实现对话就超级简单啦,只需要在ngx_http_upstream_module模块加参数 hash $request_uri consistent; 就可以啦。

负载均衡