一致性HASH原理和应用
问题：单机redis20G如何承载500G的cache（考虑redis集群应用）
应用场景
如何对请求与缓存服务器之间进行精准映射,以及优雅的扩展，剔除缓存服务器，提升缓存服务的容错性和扩展性
- 容错性：指当系统中某一个或几个服务器变得不可用时，整个系统是否可以正确高效运行；
- 扩展性：指当加入新的服务器后，整个系统是否可以正确高效运行。
算法概述
一致性哈希将整个哈希空间组织成一个虚拟的圆环，假如整个哈希函数的值空间为0 - 2^32 -1(一个32位的无符号整形)，如下图:整个空间按顺时针方向组织,0和2^32-1在零点中方向重合
第一步：在哈希闭环中确定各台服务器位置
将各台服务器的ip或主机名为关键字通过H函数得到一个哈希值，然后在哈希闭环中标注位置。如下图3台redis服务：
第二步：定位数据访问的服务器
将数据key使用相同的函数H计算出哈希值h，通根据h确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器
例如我们缓存服务器中有A、B、C、D四个key对应的数据对象，经过哈希计算后，在环空间上的位置如下：
容错性与可扩展性分析
假设redis-2宕机：ACD节点并不受影响，只有B节点被重定向至Redis-0
如果我们在系统中增加一台服务器Redis-3 Server：对于C这个key，重新定位至Redis-3 服务器，其他非C的key均不受影响
数据倾斜问题
1. 问题概述
一致性哈希算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜问题，必然造成大量数据集中到Redis-1上，而只有极少量会定位到Redis-0上。如下图
2. 使用虚拟节点解决
对每一个服务节点多计算N个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。在实际应用中，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布
第一步：为每个机器多增加N个虚拟节点
为每个机器多计算三个虚拟节点，分别计算“Redis-1 #1”、“Redis-1 #2”、“Redis-1 #3”、“Redis-0 #1”、“Redis-0 #2”、“Redis-0 #3”的哈希值，于是形成六个虚拟节点:
第二步：将虚拟节点映射到实际节点
数据定位算法不变，只是多了一步虚拟节点到实际节点的映射，例如定位到“Redis-1#1”、“Redis-1#2”、“Redis-1#3”三个虚拟节点的数据均定位到Redis-1上