一、Redis哈希槽
1、哈希槽介紹
Redis Cluster在設計中沒有使用一緻性哈希（Consistency Hashing），而是使用資料分片引入哈希槽（hash slot）來實作；
一個 Redis Cluster包含16384（0~16383）個哈希槽（補充：為什麼redis叢集的最大槽數是16384個？），存儲在Redis Cluster中的所有鍵都會被映射到這些slot中，叢集中的每個鍵都屬于這16384個哈希槽中的一個。按照槽來進行分片，通過為每個節點指派不同數量的槽，可以控制不同節點負責的資料量和請求數.
目前叢集有3個節點,槽預設是平均分的:
- 節點 A （6381）包含 0 到 5499号哈希槽.
- 節點 B （6382）包含5500 到 10999 号哈希槽.
- 節點 C （6383）包含11000 到 16383号哈希槽.
2、哈希槽計算公式
叢集使用公式slot=CRC16（key）/16384來計算key屬于哪個槽，其中CRC16(key)語句用于計算key的CRC16 校驗和。
3、哈希槽怎麼工作
我們看到的是master節點在 Redis Cluster中的實作時，都存有所有的路由資訊。
當用戶端的key 經過hash運算，發送slot 槽位不在本節點的時候：
- （1）如果是非叢集方式連接配接，則直接報告錯誤給client，告訴它應該通路叢集中那個IP的master主機。
- （2）如果是叢集方式連接配接，則将用戶端重定向到正确的節點上。
注意這裡并不是127.0.0.1:7001 幫client去連接配接127.0.0.1:7003擷取資料的，而是将用戶端請求重定向了。
4、哈希槽的優點
很容易添加或者删除節點：
- 比如如果我想新添加個節點D, 我需要從節點 A, B, C中轉移部分槽到D上即可.
- 如果我像移除節點A,需要将A中得槽移到B和C節點上,然後将沒有任何槽的A節點從叢集中移除即可.
由于從一個節點将哈希槽移動到另一個節點并不會停止服務,是以無論添加删除或者改變某個節點的哈希槽的數量都不會造成叢集不可用的狀态.
5、補充知識
檢視哈希槽分區情況
通過cluster nodes指令，可以清晰看到Redis Cluster中的每一個master節點管理的哈希槽。比如 127.0.0.1:7001 擁有哈希槽 0-5460， 127.0.0.1:7002 擁有哈希槽 5461-10922， 127.0.0.1:7003 擁有哈希槽 10923-16383。
//檢視叢集中，各個master節點的哈希槽分區情況
127.0.0.1:7001> cluster nodes
e51711eb03d 127.0.0.1:[email protected] master - 0 1590126183862 2 connected 5461-10922
68c5fc14287 127.0.0.1:[email protected] master - 0 1590126181856 3 connected 10923-16383
903322e4431 127.0.0.1:[email protected] myself,master - 0 1590126182000 1 connected 0-5460
二、Java一緻性Hash算法實作
1、一緻性哈希介紹
一緻性哈希的主要作用就是用來進行負載均衡，我們設想這麼一個場景，我們有四台伺服器，然後需要将一批資源均勻的配置設定到這四台伺服器上。
2、不含虛拟節點的一緻性哈希
首先我們先想象有這麼一個圓環（也叫哈希環），在哈希環上有2^32個節點；
1、對伺服器（能唯一辨別該服務的屬性，比如伺服器的IP）進行求哈希值，使其落到哈希環，如圖所示Node0-Node3（四個箭頭所示）對應四台伺服器；
2、對我們要配置設定的資源進行求哈希值，同樣落到哈希環上，如圖所示（圖中的星标辨別落在哈希環上的資源）；
3、規定落在哈希環上的資源，配置設定到該資源所在節點順時針遇到的第一個服務節點上，如圖所示；
如果伺服器所在的哈希環上的節點如上圖所示，均勻分布，那自然是最好的，但如果像下圖所示，那麼就會導緻資源的配置設定不均。為了解決這種情況出現的問題，出現了虛拟節點的一緻性哈希。
3、虛拟節點的一緻性哈希
所謂的虛拟節點，就是我們假想出來的節點，将這些虛拟節點映射到哈希環上，然後将這些虛拟節點與實際伺服器進行關聯，例如虛拟節點Node0,Node1與伺服器1關聯，那麼配置設定到Node0,Node1的資源，也即是配置設定到實際的伺服器1上。也就是說我們實際的伺服器有四台，但我們可以将N個虛拟的節點映射到哈希環上，這樣就能通過調節虛拟節點與實際伺服器的關聯關系，來達到調節配置設定到不同伺服器資源的數量的目的。
3.1、一緻性哈希的代碼實作
/**
* 計算哈希值的工具類
*/
public class Hash {
/**
* 使用String自帶的hashCode函數
* @param str
* @return
*/
public static Integer stringHashcode(String str){
int hash = str.hashCode();
if (hash<0){
hash = Math.abs(hash);
}
return hash;
}
/**
* 使用FNV1_32_HASH算法計算hash值
* @param str
* @return
*/
public static Integer FNV1_32_HASH(String str){
final int p = 1677769;
int hash = (int)0;
int len = str.length();
for (int i=0;i<len;i++){
hash = (hash^str.charAt(i))*p;
}
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
if (hash<0){
hash=Math.abs(hash);
}
return hash;
}
}
3.2、不含虛拟節點的實作
/**
* 不帶虛拟節點的一緻性哈希實作
*/
public class HashTest {
private static String[] servers = {"192.168.0.1:8999","192.168.0.2:8999","192.168.0.0.3:8999"};
/**
* key 伺服器的哈希值、
* value 伺服器資訊
*/
private static SortedMap<Integer,String> map = new TreeMap<Integer, String>();
static {
/**
* 将伺服器資訊存放到map中
*/
int size = servers.length;
for (int i = 0;i<size;i++){
int hash = Hash.FNV1_32_HASH(servers[i]);
map.put(hash, servers[i]);
System.out.println("hash="+hash+" "+"server="+servers[i]);
}
}
/**
* 擷取資源所在的節點伺服器
* @param node
* @return
*/
public static String getServer(String node){
Integer hash = Hash.FNV1_32_HASH(node);
//擷取大于目前node的hash值的所有服務節點
SortedMap<Integer, String> sortedMap = map.tailMap(hash);
Integer key = 0;
if (sortedMap.isEmpty()){
//如果沒有比node節點hash值大的服務節點，則取hash值最小的服務節點
key = map.firstKey();
}else{
//擷取過濾出的服務節點的第一個值，也就是從node開始順時針遇到的第一個服務節點
key = sortedMap.firstKey();
}
String server = map.get(key);
return server;
}
public static void main(String[] args) {
String[] index = {"582639584","582639585","582639586","582639587"};
System.out.println("-------------");
int size = index.length;
for(int i=0;i<size;i++){
String server = getServer(index[i]);
System.out.println("index="+index[i] +" hash="+Hash.FNV1_32_HASH(index[i]) +" server="+server);
}
}
}
3.3、帶虛拟節點的代碼實作
/**
* 帶虛拟節點的代碼實作
*/
public class HashVirtualNodeTest {
/**
* 實際的伺服器
*/
private static String[] servers = {"192.168.0.1:8999","192.168.0.2:8999","192.168.0.0.3:8999"};
/**
*每個服務節點對應的虛拟服務節點數目
*/
private final static int virtualNode = 5;
/**
* 哈希環上的虛拟服務節點
* key 虛拟服務節點的hash值
* value 虛拟服務節點名稱
*/
private static SortedMap<Integer,String> virtualNodeMap = new TreeMap<Integer, String>();
static{
/**
* 将虛拟節點放到virtualNodeMap中
* 虛拟節點與實際的伺服器的對應關系
* 伺服器名稱：server
* 虛拟節點名：server&&Node0 server&&Node1 server&&Node2 ...
*/
int len = servers.length;
for (int i=0;i<len;i++){
for(int j=0;j<virtualNode;j++){
String virtualNodeName = servers[i]+"&&"+"Node"+j;
Integer hash = Hash.FNV1_32_HASH(virtualNodeName);
virtualNodeMap.put(hash,virtualNodeName);
System.out.println("hash="+hash+" virtualNode=" +virtualNodeName);
}
}
}
/**
* 擷取一個節點對應的配置設定到的服務節點
* @param node 待查詢的節點
* @return 實際的服務節點名稱
*/
public static String getServer(String node){
Integer hash = Hash.FNV1_32_HASH(node);
//擷取大于目前節點的虛拟節點伺服器
SortedMap<Integer, String> tailMap = virtualNodeMap.tailMap(hash);
Integer key = 0;
if(virtualNodeMap.isEmpty()){
//沒有大于目前節點的虛拟服務節點時，取虛拟服務節點的第一個
key = virtualNodeMap.firstKey();
}else{
//取出大于目前節點的第一個虛拟服務節點
key = tailMap.firstKey();
}
//取出對應的虛拟節點
String virtualNode = virtualNodeMap.get(key);
//擷取實際的服務名稱
String server = virtualNode.split("&&")[0];
return server;
}
public static void main(String[] args){
String[] index = {"582639584","582639585","582639586","582639587","582639588"};
System.out.println("------------------");
int size = index.length;
for (int i=0;i<size;i++){
String server = getServer(index[i]);
System.out.println("index="+index[i]+" hash="+ Hash.FNV1_32_HASH(index[i]) +" server="+server);
}
}
}