Ngnix负载均衡策略包含Hash算法，就是通过Hash算法将请求hash求值，根据hash值定向到服务器。
假定有n台服务器，过来一个请求o后，通过如下方式选择服务器。
Hash(0) mod n
这种方式在增加或删除服务器时会导致请求寻址错误。
Hash(o) mod (n+1) 增加一台机器时
Hash(o) mod (n-1) 删除一台机器时
简介
Hash一致性算法(Consistent hashing）能够有效解决通过hash方式服务器变化时的寻址错误
Hash空间
Hash函数会将值映射成32bit的key。我们可以将映射区间想象成一个圆，从0开始， 2^32-1结束。
hash空间
对象映射
将对象通过hash取值后，散列到hash空间。假设有4个object对象，通过hash后，散列到hash空间的结果见下图：
对象映射
设备映射
将设备通过hash取值后，这样就可以与对象一样散列到相同的hash空间。假设有3个设备，通过hash后，散列到hash空间的结果见下图：
设备映射
对象寻找设备
现在所有的对象和设备都分布在相同的hash空间，我们就按照如下规则，将对象映射到设备上。
规则：将对象顺时针方向移动，找到一个设备，则将该对象保存在这个设备上。
当增加一台设备时，则只有该设备逆时针方向第一个相邻设备之间的对象会受到影响，需要重新寻找设备。比如增加一台设备D时，结果详见下图：
增加设备
当删除一台设备时，则只有该设备顺时针方向第一个相邻设备之间的对象会受到影响，需要重新寻找设备。比如删除一台设备B时，结果详见下图：
删除设备
非均匀分布
当设备数量比较少时，会导致对象寻找服务器不均衡现象发生。例如上图设备C需要保存object2，object3，object4三个对象，而设备A只需要保存object1。
为了解决非均匀分布问题，提出了虚拟节点。
所谓的虚拟节点就是真实节点的备份集，每个真实节点包含一些虚拟节点。当增加真实节点时，相应的就在hash空间创建一些虚拟节点；当删除真实节点时，也相应的从hash空间删除对应的虚拟节点。
假定有两台设备A，C。现在引入虚拟节点，设定每个真实节点对应2个虚拟节点，则整个hash空间存在4个虚拟节点。其中CacheA1和CacheA2代表真实节点A，CacheC1和CacheC2代表真实节点C。结果如下图：
虚拟节点
那么对象与虚拟节点的映射关系如下：
objec1->cache A2; objec2->cache A1; objec3->cache C1; objec4->cache C2
当我们获取到虚拟节点后，就能获取到真实节点了。如下图：
虚拟节点与真实节点映射
二、 Hash一致性算法在Nginx中的应用
问题1：总共有多少个虚拟节点，一个真实节点对应多少个虚拟节点？
累加真实节点的权重，算出总的权重值total_weight，虚拟节点的个数一般为total_weight * 160。一个权重为weight的真实节点，对应的虚拟节点数为weight * 160。
问题2：对于每个真实节点，如何创建对应的虚拟节点？
第一步：真实节点的server成员是其server指令的第一个参数，首先把它解析为HOST和PORT。
base_hash = crc32(HOST 0 PORT)
一个真实节点对应weight * 160个虚拟节点，对于每个虚拟节点来说，base_hash都是一样的。
第二步：为了使每个虚拟节点的hash值都不同，又引入了PREV_HASH，它是上一个虚拟节点的hash值。
hash = crc32(base_hash PREV_HASH)
第三步：虚拟节点的server成员，指向真实节点的server成员。如此一来，通过比较虚拟节点和真实节点的server成员是否相同，可以判断它们是否是相对应的。
网友评论