目錄
1、redis cluster介紹
2、最老土的hash算法和弊端（大量緩存重建）
3、一緻性hash算法（自動緩存遷移）+虛拟節點（自動負載均衡）
不用周遊 --》 hash算法： 緩存位置= hash（key）%n
新增/減少 節點 --》緩存位置失效--》hash環
hash環 節點少--》資料傾斜--》添加虛拟節點
4、redis cluster的hash slot算法
分布式尋址算法
- hash 算法（大量緩存重建）
- 一緻性 hash 算法（自動緩存遷移）+ 虛拟節點（自動負載均衡）
- redis cluster 的 hash slot 算法
1、redis cluster介紹
redis cluster
（1）自動将資料進行分片，每個master上放一部分資料
（2）提供内置的高可用支援，部分master不可用時，還是可以繼續工作的
在redis cluster架構下，每個redis要放開兩個端口号，比如一個是6379，另外一個就是加10000的端口号，比如16379
16379端口号是用來進行節點間通信的，也就是cluster bus的東西，叢集總線。cluster bus的通信，用來進行故障檢測，配置更新，故障轉移授權
cluster bus用了另外一種二進制的協定，主要用于節點間進行高效的資料交換，占用更少的網絡帶寬和處理時間
2、最老土的hash算法（弊端：大量緩存重建）
來了一個 key，首先計算 hash 值，然後對節點數取模。然後打在不同的 master 節點上。一旦某一個 master 節點當機，所有請求過來，都會基于最新的剩餘 master 節點數去取模，嘗試去取資料。這會導緻大部分的請求過來，全部無法拿到有效的緩存，導緻大量的流量湧入資料庫。
3、一緻性hash算法（自動緩存遷移）+虛拟節點（自動負載均衡）
做成一個圓環，解決命中率問題。
一緻性 hash 算法将整個 hash 值空間組織成一個虛拟的圓環，整個空間按順時針方向組織，下一步将各個 master 節點（使用伺服器的 ip 或主機名）進行 hash。這樣就能确定每個節點在其哈希環上的位置。
來了一個 key，首先計算 hash 值，并确定此資料在環上的位置，從此位置沿環順時針“行走”，遇到的第一個 master 節點就是 key 所在位置。
在一緻性雜湊演算法中，如果一個節點挂了，受影響的資料僅僅是此節點到環空間前一個節點（沿着逆時針方向行走遇到的第一個節點）之間的資料，其它不受影響。增加一個節點也同理。
然而，一緻性雜湊演算法在節點太少時，容易因為節點分布不均勻而造成緩存熱點的問題。為了解決這種熱點問題，一緻性 hash 算法引入了虛拟節點機制，即對每一個節點計算多個 hash，每個計算結果位置都放置一個虛拟節點。這樣就實作了資料的均勻分布，負載均衡。一緻性hash算法更詳細的請看這篇：一緻性Hash算法
一緻性hash算法（redis叢集就是這個原理）：
1、我們把全量的緩存空間當做一個環形存儲結構。環形空間總共分成2^32個緩存區，在Redis中則是把緩存key配置設定到16384個slot。
2、每一個緩存key都可以通過Hash算法轉化為一個32位的二進制數，也就對應着環形空間的某一個緩存區。我們把所有的緩存key映射到環形空間的不同位置。
3、我們的每一個緩存節點（Shard）也遵循同樣的Hash算法，比如利用IP做Hash，映射到環形空間當中。
4、如何讓key和節點對應起來呢？很簡單，每一個key的順時針方向最近節點，就是key所歸屬的存儲節點。是以圖中key1存儲于node1，key2，key3存儲于node2，key4存儲于node3。
增加節點時:
當緩存叢集的節點有所增加的時候，整個環形空間的映射仍然會保持一緻性哈希的順時針規則，是以有一小部分key的歸屬會受到影響。
有哪些key會受到影響呢？ 圖中加入了新節點node4，處于node1和node2之間，按照順時針規則，從node1到node4之間的緩存不再歸屬于node2，而是歸屬于新節點node4。是以受影響的key隻有key2。(我了解計算同一個key的hash值不變,但是挂載到不同的節點中,原節點的資料還存在,是以存在資料的備援, 但是實際在測試時這個想法是錯的. 因為在新增加節點的時候, 重新配置設定slot槽點時, 會将原來槽點中儲存的資料會移動到新的節點中, 原來槽點中的資料也已經不存在, 是以不存在資料的備援.)
最終把key2的緩存資料從node2遷移到node4，就形成了新的符合一緻性哈希規則的緩存結構。
删除節點
當緩存叢集的節點需要删除的時候（比如節點挂掉），整個環形空間的映射同樣會保持一緻性哈希的順時針規則，同樣有一小部分key的歸屬會受到影響。
有哪些key會受到影響呢？圖中删除了原節點node3，按照順時針規則，原本node3所擁有的緩存資料就需要“托付”給node3的順時針後繼節點node1。是以受影響的key隻有key4。
最終把key4的緩存資料從node3遷移到node1，就形成了新的符合一緻性哈希規則的緩存結構.
由于node3已經挂掉,原來在node3上的節點緩存的資料不是直接從node3遷移過去,而是在再次查詢時去查詢順時針的後續的後繼節點,因緩存沒有命中而重新整理緩存,重新挂載到新的節點中.
5、每個緩存節點都按照iphash到環形空間,可能出現分布不均的情況,是以為了優化引入了虛拟節點.基于原來的實體節點映射出N個子節點,最後全部映射到環形空間.
如上圖所示，假如node1的ip是192.168.1.109，那麼原node1節點在環形空間的位置就是hash（“192.168.1.109”）。
我們基于node1建構兩個虛拟節點，node1-1 和 node1-2，虛拟節點在環形空間的位置可以利用（IP+字尾）計算，例如：
hash（“192.168.1.109#1”），hash（“192.168.1.109#2”）
此時，環形空間中不再有實體節點node1，node2，隻有虛拟節點node1-1，node1-2，node2-1，node2-2。由于虛拟節點數量較多，緩存key與虛拟節點的映射關系也變得相對均衡了。
4、redis cluster的hash slot算法
redis cluster 有固定的 16384 個 hash slot，對每個 key 計算 CRC16 值，然後對 16384 取模，可以擷取 key 對應的 hash slot。每個節點負責維護一部分槽以及槽所映射的鍵值資料。
redis cluster 中每個 master 都會持有部分 slot，比如有 3 個 master，那麼可能每個 master 持有 5000 多個 hash slot。hash slot 讓 node 的增加和移除很簡單，增加一個 master，就将其他 master 的 hash slot 移動部分過去，減少一個 master，就将它的 hash slot 移動到其他 master 上去。移動 hash slot 的成本是非常低的。用戶端的 api，可以對指定的資料，讓他們走同一個 hash slot，通過 hash tag 來實作。
更加生動的方式展示：
例如：Redis Cluster 采用虛拟槽分區，所有的鍵根據哈希函數映射到 0~16383 整數槽内，計算公式：slot = CRC16（key）& 16384。每個節點負責維護一部分槽以及槽所映射的鍵值資料，如下圖所示：
舉個例子
如上圖
目前叢集有 5 個節點，每個節點平均大約負責 3276 個槽。由于采用高品質的雜湊演算法，每個槽所映射的資料通常比較均勻，将資料平均劃分到 5 個節點進行資料分區。Redis Cluster 就是采用虛拟槽分區。
節點1： 包含 0 到 3276 号哈希槽。
節點2：包含 3277 到 6553 号哈希槽。
節點3：包含 6554 到 9830 号哈希槽。
節點4：包含 9831 到 13107 号哈希槽。
節點5：包含 13108 到 16383 号哈希槽。
是以hash slot的好處是可以像磁盤分區一樣自由配置設定槽位，在配置檔案裡可以指定，也可以讓redis自己選擇配置設定，結果均勻。
這種結構很容易添加或者删除節點。如果增加一個節點 6，就需要從節點 1 ~ 5 獲得部分槽配置設定到節點 6 上。如果想移除節點 1，需要将節點 1 中的槽移到節點 2 ~ 5 上，然後将沒有任何槽的節點 1 從叢集中移除即可。
由于從一個節點将哈希槽移動到另一個節點并不會停止服務，是以無論添加删除或者改變某個節點的哈希槽的數量都不會造成叢集不可用的狀态.
緩存的key hash結果是和slot綁定的，而不是和伺服器節點綁定，是以節點的更替隻需要遷移slot即可平滑過渡。
出處連結：
https://www.jianshu.com/p/fe7b7800473e
https://www.jianshu.com/p/90b3de6288c6