文章目錄

• 分布式存儲
• • 順序分區(qū) Sequential partitioning
  • 哈希分區(qū) Hash partitioning
  • • 方案總覽
    • 節(jié)點取余分區(qū) Hashing
    • 一致性哈希分區(qū) Consistent hashing
    • • 初始化
      • 節(jié)點的擴容與縮容
    • 虛擬哈希分區(qū)
    • 虛擬哈希分區(qū) (Version2)
  • 順序分區(qū) VS 哈希分區(qū)

---

分布式存儲

了解Redis集群原理之前我們先來梳理一下分布式存儲的相關知識

拆分在算法中是一個非常重要的思想，當你的數據集巨大時，你可以按照特定的規(guī)則將大數據拆分成小數據集，降低因數據量增長過大帶來的問題。

基本方案有兩種：順序分布 & 哈希分布 。 需要根據具體業(yè)務選擇分片方式

數據分區(qū)雖好 ，但是有沒有哪些棘手的問題要處理呢？ 當然有了，比如

• 自動負載均衡

  分布式存儲系統(tǒng)需要自動識別負載高的節(jié)點，當某臺機器的負載高時，自動將其上的部分數據遷移到其他機器。

• 一致性

  分片后數據可能分布在不同存儲服務器上，無法使用數據庫自帶的單機事務，需通過分布式應用事務一致性模型來解決

---

順序分區(qū) Sequential partitioning

從名字上也很好理解順序分布的含義， 就是將大表按一定順序劃分為連續(xù)的子表，然后將子表按一定策略分配到存儲節(jié)點上。

舉個簡單的例子

優(yōu)點呢？

可順序讀

缺點呢？

數據可能分布不均勻

數據量大的時候，為了性能 ，需要使用索引來記錄子表信息

---

哈希分區(qū) Hash partitioning

方案總覽

節(jié)點取余分區(qū) Hashing

通過數據的某個特征計算哈希值，并將哈希值與集群中的服務器建立映射關系，從而將不同數據分布到不同服務器上。

hash(object) % N

舉個例子：

假設這個時候我要添加一個節(jié)點 ，我們拿 1-10 來說，來計算下從3個節(jié)點到4個節(jié)點的遷移率

先 1 % 3 ， 2 % 3 … 10 % 3 , 算出來 在哪個分區(qū)，如下圖左側 （0 ，1 ，2 三個分區(qū)）

重新對4進行 1 %4 ， 2 % 4 … 10 % 4, 計算后 ，如右側

比對一下， 只有 1 (分區(qū)0) 和 2 （分區(qū)1） 這兩個值 還在原來的分區(qū)里 ，其余8個數字 都遷移到了其他的分區(qū)中。

解釋下遷移率 是指： 你的這個緩存區(qū)域中已經沒有數據了，需要DB查詢，回寫到緩存，80%的數據都要這樣重新構建…

---

咋解決呢？

稍微挫一點的方案 翻倍擴容 ，遷移率可以降低到 50%

我們還是那1-10 這10個數字，3個分區(qū)變6個分區(qū)來計算下遷移率

原來1 % 3 ， 2 % 3 … 10 % 3 , 算出來 在哪個分區(qū)
翻倍擴容 重新對6進行 1 %6 ， 2 % 6 … 10 % 6, 計算

建議： 看場景，如果你的業(yè)務對緩存依賴沒這沒強，查不到從DB查就是，并發(fā)也不高，也不是不可以，畢竟這個最簡單。

當然了，最好不用，太古老

---

一致性哈希分區(qū) Consistent hashing

剛才根據節(jié)點數量來分區(qū)的方式，缺點也看到了，遷移率太高。 剛才的翻倍擴容的方案也差強人意，有沒有更好的呢？ 那就是 Consistent hashing

我們使用 哈希環(huán)來解決 slot 數發(fā)生變化時，盡量減少數據的移動。

一致性哈希算法在1997年由麻省理工學院的Karger等人在解決分布式Cache中提出的.

初始化

• 首先求出節(jié)點 的哈希值 （比如可以選擇服務器的ip或主機名作為關鍵字進行哈希），并將其配置到0～2^32的環(huán)上
• 然后采用同樣的方法求出存儲數據的鍵的哈希值，并映射到相同的環(huán)上
• 緊接著從數據映射到的位置開始順時針查找，將數據保存到找到的第一個服務器上。
• 如果超過2^32仍然找不到服務器，就會保存到第一個節(jié)點上

---

節(jié)點的擴容與縮容

節(jié)點取余的算法當節(jié)點動態(tài)的調整大大的影響緩存的命中率，但Consistent Hashing中，只有在環(huán)上增加服務器的地點逆時針方向的第一個節(jié)點上的鍵會受到影響

舉個例子： 假設我們要在node1 和 node2 之間 增加一個 node5節(jié)點，看看哪些數據會受到影響？

增加node5 后

是不是 右上方的 兩條數據 你下次再查找的時候 ，你會去node5找 （因為這兩條數據的下一個節(jié)點是node5 ,已經不是node2了），找不到，失效了，會重新從數據源獲取，重新構建。

仍然存在小規(guī)模的失效，但比第一種hash算法，如果節(jié)點很多，這種影響的數據范圍降低了很多。

總結下 ：

客戶端分片: hash + 順時針（優(yōu)化取余）

節(jié)點伸縮：只影響鄰近節(jié)點，但是還有數據遷移

翻倍伸縮： 保證最小遷移數據和負債均衡 ， 這個其實還是有可能數據分部不均勻，比如你4個節(jié)點，大部分的key做hash以后，有可能集中在node1 和 nod2上，node3 和 node4 只有少量的數據，所以還是建議翻倍擴容。 這個就是我們常說的： 服務節(jié)點少時數據傾斜的問題。

綜上所述，一致性哈希算法對于節(jié)點的增減都只需重定位環(huán)空間中的一小部分數據，具有較好的容錯性和可擴展性。

另外，一致性哈希算法在服務節(jié)點太少時，容易因為節(jié)點分部不均勻而造成數據傾斜問題

---

虛擬哈希分區(qū)

為了解決一致性hash在節(jié)點數量比較少的情況下出現(xiàn)數據傾斜問題，一致性哈希算法引入了虛擬節(jié)點機制，即對每一個服務節(jié)點計算多個哈希，每個計算結果位置都放置一個此服務節(jié)點，稱為虛擬節(jié)點。

如何搞這些虛擬節(jié)點呢？ 可以在服務器ip或主機名的后面增加編號來實現(xiàn)。例如上面的情況，可以為每臺服務器計算三個虛擬節(jié)點，于是可以分別計算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值，于是形成六個虛擬節(jié)點：

同時數據定位算法不變，只是多了一步虛擬節(jié)點到實際節(jié)點的映射，例如定位到“Node A#1”、“Node A#2”、“Node A#3”三個虛擬節(jié)點的數據均定位到Node A上。

這樣就解決了服務節(jié)點少時數據傾斜的問題。在實際應用中，通常將虛擬節(jié)點數設置為32甚至更大，因此即使很少的服務節(jié)點也能做到相對均勻的數據分布。

import java.util.Collection; import java.util.HashSet; import java.util.Iterator; import java.util.Set; import java.util.SortedMap; import java.util.SortedSet; import java.util.TreeMap; import java.util.TreeSet;public class ConsistentHash<T> {private final int numberOfReplicas;// 節(jié)點的復制因子,實際節(jié)點個數 * numberOfReplicas =// 虛擬節(jié)點個數private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();// 存儲虛擬節(jié)點的hash值到真實節(jié)點的映射public ConsistentHash( int numberOfReplicas,Collection<T> nodes) {this.numberOfReplicas = numberOfReplicas;for (T node : nodes){add(node);}}public void add(T node) {for (int i = 0; i < numberOfReplicas; i++){// 對于一個實際機器節(jié)點 node, 對應 numberOfReplicas 個虛擬節(jié)點/** 不同的虛擬節(jié)點(i不同)有不同的hash值,但都對應同一個實際機器node* 虛擬node一般是均衡分布在環(huán)上的,數據存儲在順時針方向的虛擬node上*/String nodestr =node.toString() + i;int hashcode =nodestr.hashCode();System.out.println("hashcode:"+hashcode);circle.put(hashcode, node);}}public void remove(T node) {for (int i = 0; i < numberOfReplicas; i++)circle.remove((node.toString() + i).hashCode());}/** 獲得一個最近的順時針節(jié)點,根據給定的key 取Hash* 然后再取得順時針方向上最近的一個虛擬節(jié)點對應的實際節(jié)點* 再從實際節(jié)點中取得 數據*/public T get(Object key) {if (circle.isEmpty())return null;int hash = key.hashCode();// node 用String來表示,獲得node在哈希環(huán)中的hashCodeSystem.out.println("hashcode----->:"+hash);if (!circle.containsKey(hash)) {//數據映射在兩臺虛擬機器所在環(huán)之間,就需要按順時針方向尋找機器SortedMap<Integer, T> tailMap = circle.tailMap(hash);hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();}return circle.get(hash);}public long getSize() {return circle.size();}/** 查看表示整個哈希環(huán)中各個虛擬節(jié)點位置*/public void testBalance(){Set<Integer> sets = circle.keySet();//獲得TreeMap中所有的KeySortedSet<Integer> sortedSets= new TreeSet<Integer>(sets);//將獲得的Key集合排序for(Integer hashCode : sortedSets){System.out.println(hashCode);}System.out.println("----each location 's distance are follows: ----");/** 查看相鄰兩個hashCode的差值*/Iterator<Integer> it = sortedSets.iterator();Iterator<Integer> it2 = sortedSets.iterator();if(it2.hasNext())it2.next();long keyPre, keyAfter;while(it.hasNext() && it2.hasNext()){keyPre = it.next();keyAfter = it2.next();System.out.println(keyAfter - keyPre);}}public static void main(String[] args) {Set<String> nodes = new HashSet<String>();nodes.add("A");nodes.add("B");nodes.add("C");ConsistentHash<String> consistentHash = new ConsistentHash<String>(2, nodes);consistentHash.add("D");System.out.println("hash circle size: " + consistentHash.getSize());System.out.println("location of each node are follows: ");consistentHash.testBalance();String node =consistentHash.get("apple");System.out.println("node----------->:"+node);}}

---

虛擬哈希分區(qū) (Version2)

剛才虛節(jié)點這種靠數量取勝的策略增加了存儲這些虛節(jié)點信息所需要的空間。

在Redis Cluster中使用了一種比較特殊的方法來解決分布不均的問題，改進了這些數據分布的算法，將環(huán)上的空間均勻的映射到一個線性空間，這樣，就保證分布的均勻性。

---

順序分區(qū) VS 哈希分區(qū)

---

總結

以上是生活随笔為你收集整理的Redis进阶-分布式存储 Sequential partitioning Hash partitioning的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。