前言
之前面试，面试官问到一个问题：“在使用redis分片的时候，redis是如何保证结点在增加或减少的时候，使可用结点的缓存数据还有效的？”
当时没有回答上来，后面查找资料，其实就是关于一致性哈希或环型哈希的算法问题。相关基础可以参照一致性哈希所对应的简介及使用场景这个文档。
自己大概总结了一下相关的内容。
Redis部署
因为一致性哈希要与Redis的分片部署配合使用，所以我先说明一下Redis的部署。
主从部署
因为只部署一个Redis结点，会存在单点故障及负载较大的问题，所以我们常用一主二从三哨兵的部署方案。如下图所示：
屏幕快照 2018-12-28 下午4.57.09.png
其中：
- 主结点master做读写操作。
- 从结点slave同步主结点数据做读操作，可以负担一下主结点的压力。
- 哨兵monitor,监控主结点及从结点的状态，当发现主结点异常时，根据算法及监控数据从从结点中选择一个最优的从点做为主结点，并自动切换，当旧的主结点恢复以后，转为从结点。
Redis分片部署
上述部署方案，并不是一致性哈希所能使用的方案。而是当单个主结点无法高效的处理所有数据的时候，就需要将数据能够根据一定的算法均匀的分布在各个结点中。及有多个主从部署，我这里就称为分片部署。如下图所示：
屏幕快照 2018-12-28 下午5.10.27.png
实现
为了将数据能够均匀的分布在每个分片中，是可以使用哈希算法来解决的。但当增加一个分片或删除一个分片，要使数据还能落在原有结点上，就需要一致性哈希算法了。下面我说明一下我具体的实现。
哈希算法
首先需要一个哈希算法，将字符串转换为2的32次方的数字(long)。具体算法的源代码如下：
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
/**
* MurMurHash算法，非加密算法，性能高，比传统的CRC32,MD5，SHA-1等快很多，碰撞率很低。
* http://murmurhash.googlepages.com/
*/
public class HashRingAlgorithm {
/**
* 使用一致性hash环算法计算输入参数
*
* @param key
* 输入参数
* @return 输入参数在环中位置
*/
public static final long hash(String key) {
ByteBuffer buf = ByteBuffer.wrap(key.getBytes());
int seed = 0x1234ABCD;
ByteOrder byteOrder = buf.order();
buf.order(ByteOrder.LITTLE_ENDIAN);
long m = 0xc6a4a7935bd1e995L;
int r = 47;
long h = seed ^ (buf.remaining() * m);
long k;
while (buf.remaining() >= 8) {
k = buf.getLong();
k *= m;
k ^= k >>> r;
k *= m;
h ^= k;
h *= m;
}
if (buf.remaining() > 0) {
ByteBuffer finish = ByteBuffer.allocate(8).order(
ByteOrder.LITTLE_ENDIAN);
finish.put(buf).rewind();
h ^= finish.getLong();
h *= m;
h *= m;
}
h ^= h >>> r;
h *= m;
h ^= h >>> r;
buf.order(byteOrder);
return h;
}
}
当然，也可以使用Java中String类型自带的hashCode方法：
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
实现哈希环
我是用一个java.util.TreeMap来实现。
// 形成环的节点数据
private static TreeMap<Long, String> nodes = new TreeMap<>();
将每个分片的主机名或主机IP加端口等为键值，并为每一个分片结点创建1000个虚拟结点，生成环形哈希值，并存储在TreeMap中。
// 每个真实节点关联的虚拟节点个数
private static int VIRTUAL_NODE_NUM = 1000;
// 每个数据源节点都需要关联虚拟节点
TreeMap<Long, String> nodes = new TreeMap<>();
//装载分库hash环
for (int i = 1; i <= redisNodes.size(); i++) {
String hostName = redisNodes.get(i).getHostName();
for (int n = 0; n < VIRTUAL_NODE_NUM; n++) {
// 一个真实机器节点关联NODE_NUM个虚拟节点
nodes.put(HashRingAlgorithm.hash("SHARD-" + hostName + "-NODE-" + n), hostName);
}
}
从哈希环中取值
将需要存入redis的键通过哈希算法生成哈希值，并调用值入哈希环的TreeMap的tailMap方法。及取出比当前要读写数据的哈希值大的结点信息（顺时针获取哈希环中的分片结点），并取出最近的一个分片结点。
SortedMap<Long, String> tail = nodes.tailMap(HashRingAlgorithm.hash(shardCode));
String hostName;
if (tail.size() == 0) {
// 无列表时取第一个节点（形成环）
hostName = nodes.get(nodes.firstKey());
} else {
// 返回第一个数据库信息
hostName = tail.get(tail.firstKey());
}
