目錄
Redis主從架構
我們在使用Redis的過程中，為了保證Redis的高可用，我們一般會對Redis做主從復制，組成-或者-Slave的形式，進行數據的讀寫分離，如下圖所示：
-Slave模式
當緩存數據量超過一定的數量時，我們就要對Redis集群做分庫分表的操作。
來個栗子，我們有一個電商平臺，需要使用Redis存儲商品的圖片資源，存儲的格式為鍵值對，key值為圖片名稱，Value為該圖片所在的文件服務器的路徑，我們需要根據文件名，查找到文件所在的文件服務器上的路徑，我們的圖片數量大概在3000w左右，按照我們的規則進行分庫，規則就是隨機分配的，我們以每臺服務器存500w的數量，部署12臺緩存服務器，并且進行主從復制，架構圖如下圖所示：
Redis多主從架構
由于我們定義的規則是隨機的，所以我們的數據有可能存儲在任何一組Redis中，比如我們需要查詢".png"的圖片，由于規則的隨機性，我們需要遍歷所有Redis服務器，才能查詢得到。這樣的結果顯然不是我們所需要的。
所以我們會想到按某一個字段值進行Hash值、取模。所以我們就看看使用Hash的方式是怎么進行的。
使用Hash的Redis集群方案討論
如果我們使用Hash的方式，每一張圖片在進行分庫的時候都可以定位到特定的服務器，示意圖如圖所示：
使用Hash方式的命中緩存
從上圖中，我們需要查詢的是圖.png，由于我們有6臺主服務器，所以計算的公式為：hash(.png) % 6 = 5, 我們就可以定位到是5號主從，這們就省去了遍歷所有服務器的時間，從而大大提升了性能。
使用Hash時遇到的問題
在上述hash取模的過程中，我們雖然不需要對所有Redis服務器進行遍歷而提升了性能。但是，使用Hash算法緩存時會出現一些問題，Redis服務器變動時，所有緩存的位置都會發生改變。
即 對動態擴容和收縮不友好。
比如，現在我們的Redis緩存服務器增加到了8臺，我們計算的公式從hash(.png) % 6 = 5變成了hash(.png) % 8 = ? 結果肯定不是原來的5了。
再者，6臺的服務器集群中，當某個主從群出現故障時，無法進行緩存，那我們需要把故障機器移除，所以取模數又會從6變成了5。我們計算的公式也會變化。
由于上面hash算法是使用取模來進行緩存的，為了規避上述情況，Hash一致性算法就誕生了~~
一致性Hash算法原理
一致性Hash算法也是使用取模的方法，不過，上述的取模方法是對服務器的數量進行取模，而一致性的Hash算法是對2的32方取模。即，一致性Hash算法將整個Hash空間組織成一個虛擬的圓環，Hash函數的值空間為0 ~ 2^32 - 1(一個32位無符號整型)，整個哈希環如下：
Hash圓環
整個圓環以順時針方向組織，圓環正上方的點代表0，0點右側的第一個點代表1，以此類推。
第二步，我們將各個服務器使用Hash進行一個哈希，具體可以選擇服務器的IP或主機名作為關鍵字進行哈希，這樣每臺服務器就確定在了哈希環的一個位置上redis集群數據一致性，比如我們有三臺機器，使用IP地址哈希后在環空間的位置如圖1-4所示：
服務器在哈希環上的位置
現在，我們使用以下算法定位數據訪問到相應的服務器：
將數據Key使用相同的函數Hash計算出哈希值，并確定此數據在環上的位置，從此位置沿環順時針查找，遇到的服務器就是其應該定位到的服務器。
例如，現在有，，三個數據對象，經過哈希計算后，在環空間上的位置如下：
數據對象在環上的位置
根據一致性算法， -> NodeA， -> NodeB, -> NodeC
一致性Hash算法的容錯性和可擴展性
現在，假設我們的Node C宕機了redis集群數據一致性，我們從圖中可以看到，A、B不會受到影響，只有 C對象被重新定位到Node A。所以我們發現，在一致性Hash算法中，如果一臺服務器不可用，受影響的數據僅僅是此服務器到其環空間前一臺服務器之間的數據（這里為Node C到Node B之間的數據），其他不會受到影響。如圖1-6所示：
C節點宕機情況，數據移到節點A上
另外一種情況，現在我們系統增加了一臺服務器Node X，如圖1-7所示：
增加新的服務器節點X
此時對象、沒有受到影響，只有 C重新定位到了新的節點X上。
如上所述：
一致性Hash算法對于節點的增減都只需重定位環空間中的一小部分數據，有很好的容錯性和可擴展性。但是Redis采用的是槽，和hash一致性不是完全相同的。
Redis 集群架構
Redis 將所有數據劃分為 16384 個 slots(槽位)，每個節點負責一部分槽位(可用自己分配)。槽位的信息存儲于每個節點中。
當 Redis 的客戶端來連接集群時，它也會得到一份集群的槽位配置信息并將其緩存在客戶端本地。這樣當客戶端要查找某個 key 時，可以直接定位到目標節點。同時因為槽位的信息可能會存在客戶端與服務器不一致的情況，還需要糾正機制來實現槽位信息的校驗調整。
Redis 集群架構
這里的redis集群，可以想象成一個環，16384個槽分配給若干個節點，每個節點都是像上圖一樣支持主從架構或哨兵架構。
槽位定位算法
Redis 默認會對 key 值使用 crc16 算法進行 Hash 得到一個整數值，然后用這個整數值對 16384 進行取模來得到具體槽位（位運算）。
= CRC16(key) & (16384 - 1)。
跳轉重定位
當客戶端向一個錯誤的節點發出了指令，該節點會發現指令的 key 所在的槽位并不歸自己管理，這時它會向客戶端發送一個特殊的跳轉指令攜帶目標操作的節點地址，告訴客戶端去這個節點去獲取數據。
客戶端收到指令后除了跳轉到正確的節點上去操作，還會同步更新糾正本地的槽位映射表緩存，后續所有 key 將使用新的槽位映射表。【例如在某活動大促期間，增加了 Redis 集群服務器臺數，將槽位分發給了這幾個節點，將導致客戶端緩存的槽位映射表不正確，從而指令錯誤】
set name zhangsan
Redirected to slot [1638] located at 192.168.56.12:8004 OK數據傾斜問題
在一致性Hash算法服務節點太少的情況下，容易因為節點分布不均勻面造成數據傾斜（被緩存的對象大部分緩存在某一臺服務器上）問題，如圖特例：
數據傾斜
這時我們發現有大量數據集中在節點A上，而節點B只有少量數據。為了解決數據傾斜問題，一致性Hash算法引入了虛擬節點機制，即對每一個服務器節點計算多個哈希，每個計算結果位置都放置一個此服務節點，稱為虛擬節點。
具體操作可以為服務器IP或主機名后加入編號來實現，實現如圖所示：
增加虛擬節點情況
數據定位算法不變，只需要增加一步：虛擬節點到實際點的映射。
所以加入虛擬節點之后，即使在服務節點很少的情況下，也能做到數據的均勻分布。
具體實現
算法接口類
public interface IHashService {
Long hash(String key);
}
算法接口實現類
public class HashService implements IHashService {
/**
* MurMurHash算法,性能高,碰撞率低
*
* @param key String
* @return Long
*/
public 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 ^= h >>> r;
h *= m;
h ^= h >>> r;
buf.order(byteOrder);
return h;
}
}
模擬機器節點
public class Node {
private String ip;
private String name;
public Node(String ip, String name) {
this.ip = ip;
this.name = name;
}
public String getIp() {
return ip;
}
public void setIp(String ip) {
this.ip = ip;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
/**
* 使用IP當做hash的Key
*
* @return String
*/
@Override
public String toString() {
return ip;
}
}
一致性Hash操作
public class ConsistentHash {
// Hash函數接口
private final IHashService iHashService;
// 每個機器節點關聯的虛擬節點數量
private final int numberOfReplicas;
// 環形虛擬節點
private final SortedMap circle = new TreeMap();
public ConsistentHash(IHashService iHashService, int numberOfReplicas, Collection nodes) {
this.iHashService = iHashService;
this.numberOfReplicas = numberOfReplicas;
for (T node : nodes) {
add(node);
}
}
/**
* 增加真實機器節點
*
* @param node T
*/
public void add(T node) {
for (int i = 0; i < this.numberOfReplicas; i++) {
circle.put(this.iHashService.hash(node.toString() + i), node);
}
}
/**
* 刪除真實機器節點
*
* @param node T
*/
public void remove(T node) {
for (int i = 0; i < this.numberOfReplicas; i++) {
circle.remove(this.iHashService.hash(node.toString() + i));
}
}
public T get(String key) {
if (circle.isEmpty()) return null;
long hash = iHashService.hash(key);
// 沿環的順時針找到一個虛擬節點
if (!circle.containsKey(hash)) {
SortedMap tailMap = circle.tailMap(hash);
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hash);
}
}
測試類
public class TestHashCircle {
// 機器節點IP前綴
private static final String IP_PREFIX = "192.168.0.";
public static void main(String[] args) {
// 每臺真實機器節點上保存的記錄條數
Map map = new HashMap();
// 真實機器節點, 模擬10臺
List> nodes = new ArrayList>();
for (int i = 1; i <= 10; i++) {
map.put(IP_PREFIX + i, 0); // 初始化記錄
Node node = new Node(IP_PREFIX + i, "node" + i);
nodes.add(node);
}
IHashService iHashService = new HashService();
// 每臺真實機器引入100個虛擬節點
ConsistentHash> consistentHash = new ConsistentHash>(iHashService, 500, nodes);
// 將5000條記錄盡可能均勻的存儲到10臺機器節點上
for (int i = 0; i < 5000; i++) {
// 產生隨機一個字符串當做一條記錄，可以是其它更復雜的業務對象,比如隨機字符串相當于對象的業務唯一標識
String data = UUID.randomUUID().toString() + i;
// 通過記錄找到真實機器節點
Node node = consistentHash.get(data);
// 再這里可以能過其它工具將記錄存儲真實機器節點上，比如MemoryCache等
// ...
// 每臺真實機器節點上保存的記錄條數加1
map.put(node.getIp(), map.get(node.getIp()) + 1);
}
// 打印每臺真實機器節點保存的記錄條數
for (int i = 1; i <= 10; i++) {
System.out.println(IP_PREFIX + i + "節點記錄條數：" + map.get(IP_PREFIX + i));
}
}
}
運行結果如下：