數據分布方式一哈希與一致性哈希詳解

首先，我們來看一下數據分布設計的原則。數據分布設計原則是分布式存儲系統設計的基本原則，指導了哈希和一致性哈希方法的選擇和應用。

數據分布設計原則

實,這裡的數據分布，主要就是數據分片。相信你還記得，我在第24篇文章中與你分享分布式存儲系統的導購時，已經和你提到數據分片技術,它解決了確定數據位置的問題，並著重與你講述了按照數據特徵進行劃分的分片方法。今天，我主要與你講解按照數據範圍,採用哈希一致性哈希等對數據劃分的方法。

假設,現在有上百G數據需要進行分布式存儲，也就是要存儲到不同的節點上。提到這個問題，你可能立刻就會想到很多種方法，比如隨機分布、範圍分布、映射分布等。那麼，我們應該如何選擇到底要使用哪種方法呢?

在分布式數據存儲系統中，存儲方案選型時，通常會考慮數據均勻、數據穩定和節點異構性這三個維度。

從數據均勻的維度考慮，主要包括兩個方面:

不同存儲節點中存儲的數據要儘量均衡，避免讓某一個或某幾個節點存儲壓力過大， 而其他節點卻幾乎沒什麼數據。比如，現在有100G數據，4個同類型節點，通常希望數據存儲時儘可能均衡，比如每個節點存儲25G數據。

另外，用戶訪問也要做到均衡，避免出現某一個或某幾個節點的訪問量很大，但其他節

點卻無人問津的情況。比如，現在有1000個請求，對於上述存儲數據的4個節點，處理用戶訪問請求儘量均衡，比如每個節點處理250個請求，當然這是非常理想的情況,實際情況下，每個節點之間相差不太大即可。

從數據穩定的維度考慮，當存儲節點出現故障需要移除或者擴增時，數據按照分布規則得到的結果應該儘量保持穩定，不要出現大範圍的數據遷移。

比如，現有100G數據，剛開始有4個同類型節點(節點1~4)，每個節點存儲25G數據，現在節點2故障了，也就是說每個節點需要存儲100G/3數據。

數據穩定，就是儘可能只遷移節點2.上的數據到其他節點上,而不需要對大範圍或所有數

據進行遷移存儲。當然，如果有擴展同類型節點，也是儘可能小範圍遷移數據到擴展的節點上。具體的遷移方法，可以採用下文介紹的一致性哈希方法。

從節點異構性的維度考慮，不同存儲節點的硬體配置可能差別很大。比如，有的節點硬體配置很高，可以存儲大量數據，也可以承受更多的請求;但，有的節點硬體配置就不怎麼樣,存儲的數據量不能過多，用戶訪問也不能過多。

如果這種差別很大的節點,分到的數據量、用戶訪問量都差不多,本質就是一種不均衡。 所以，一個好的數據分布算法應該考慮節點異構性。

當然，除了上面這3個維度外,我們一般還會考慮隔離故障域、性能穩定性等因素。隔離故障域，是為了保證數據的可用和可靠性。比如，我們通常通過備份來實現數據的可靠性。但如果每個數據及它的備份，被分布到了同- -塊硬碟或節點上,就有點違背備份的初衷了。所以,一個好的數據分布算法，應該為每個數據映射一組存儲節點，這些節點應該儘量在不同的故障域，比如不同機房、不同機架等。

隔離故障域，是為了保證數據的可用和可靠性。比如，我們通常通過備份來實現數據的可靠性。但如果每個數據及它的備份，被分布到了同一塊硬碟或節點上,就有點違背備份的初衷了。所以,一個好的數據分布算法,應該為每個數據映射一組存儲節點,這些節點應該儘量在不同的故障域，比如不同機房、不同機架等。

性能穩定性是指，數據存儲和查詢的效率要有保證，不能因為節點的添加或者移除，造成存儲或訪問性能的嚴重下降。

了解了數據分布的設計原則後，接下來我們再看看主流的數據分布式方法，哈希和一致性哈希吧。其中，哈希和一致性哈希是數據分布的基礎方法，在不同場景下，數據分布設計的原則需要考慮的維度也不一樣。隨著維度的增加，一致性哈希又可進一 步演進為帶 有限負載的一致性哈希和帶虛擬節 點的一致性哈希方法。

接下來,我們就一起看看這4種方法的具體原理和應用場景吧。

數據分布方法

哈希是指，將數據按照提前規定好的函數(哈希函數)映射到相應的存儲節點，即進行一個哈希計算,得到的結果就是數據應該存儲的節點。

一致性哈希同樣是採用哈希函數， 進行兩步哈希:

1.對存儲節點進行哈希計算，也就是對存儲節點做哈希映射;

2.當對數據進行存儲或訪問時，首先對數據進行映射得到一個結果，然後找到比該結果大的第一個存儲節點,就是該數據應該存儲的地方。我會在下面的內容中，與你詳細介紹其中的原理。

總結來講，哈希是一步計算直接得到相應的存儲節點,而一致性哈希需要兩步才可以找到相應的存儲節點。這,是不是就是&34;與&39;a0&39;a1&39; }、 D3:{ id:400, name:『a3&39;a4&39;a5&39;a6&34;id% 節點個數」，通過計算可以得到每個數據應該存入的節點。在這個例子中，哈希函數是&34;分布式體系結構之非集中式結構:眾生平等」中的相關內容。

一致性哈希方法雖然提升了 穩定性,但隨之而來的均勻性問題也比較明顯，即對後繼節點的負載會變大。有節點退出後，該節點的後繼節點需要承擔該節點的所有負載,如果後繼節點承受不住,便會出現節點故障，導致後繼節點的後繼節點也面臨同樣的問題。

那麼，有沒有更好的方法來解決這個問題呢?

Google在2017年提出了帶有限負載的一致性哈希算法，就對這個問題做了一些優化。帶有限負載的一致性哈希

帶有限負載的一致性哈希方法的核心原理是，給每個存儲節點設置了-個存儲上限值來控制存儲節點添加或移除造成的數據不均勻。當數據按照一致性哈希 算法找到相應的存儲節點時，要先判斷該存儲節點是否達到了存儲上限;如果已經達到了上限，則需要繼續尋找該存儲節點順時針方向之後的節點進行存儲。

我們看看如何用帶有限負載的一致性哈希方法，來實現上述案例的數據存儲吧。

如圖所示，假設每個存儲節點設置的上限值為3,按照-致性哈希算法，當存儲數據D3 (id= 400)時，會發現應該存儲到Node1中,但Node1已經存儲了三個數據DO (id= 100)、D1 (id= 200)和D2 (id= 300) ，達到了存儲上限，因此會存儲到.該節點順時針方向的下一個節點Node2中。當然，在存儲前，也會先檢查Node2是否達到了存儲上限，如果達到了，會繼續尋找其他節點。

帶有限負載的一致性哈希方法比較適合同類型節點、節點規模會發生變化的場景。目前，在Google Cloud Pub/Sub、HAProxy 中已經實現該方法，應用於Google、Vimeo 等公司的負載均衡項目中。

其實,哈希、一致性哈希、帶有限負載的一致性哈希,都沒有考慮節點異構性的問題。如果存儲節點的性能好壞不一, 數據分布方案還按照這些方法的話，實還是沒做到數據的均勻分布。

接下來，我們再看一種主要針對存儲節為異構節點場景的方法，即帶虛擬節點的一致性哈希吧。.

帶虛擬節點的一致性哈希

帶虛擬節點的一致性哈希方法,核心思想是根據每個節點的性能，為每個節點劃分不同數量的虛擬節點，並將這些虛擬節點映射到哈希環中，然後再按照一致性哈希算法進行數據映射和存儲。

假設，Node1性能最差，Node2 性能一般，Node3性能最好。以Node1的性能作為參考基準，Node2是Node1的2倍,Node3是Node1的3倍。

因此，Node1 對應一個虛擬節點Node1_ 1, Node2 對應2個虛擬節點Node2_ 1和Node2_ 2，Node3 對應3個虛擬節點Node3_ 1、Node3_ 2和Node3_ 3.假設,虛擬節點Node1. _1、Node2_ 1、Node2_ 2、Node3_ 1、Node3_ 2、Node3_ 3的哈希值，分別為100、200、 300、 400、 500、600。

那麼,按照帶虛擬節點的哈希一致性方法， 數據D0和D6按順時針方向的下一個虛擬存儲節點為Node 1-1，因此節點Node1將會存儲數據DO (id= 100)和D6 (id =700) ;同理，Node2將會存儲數據D1 (id= 200)和D2 (id= 300)，Node3將會存儲數據D3 (id= 400)、D4 (id= 500) 和D5 (id = 600)

可以看出，帶虛擬節點的一致性哈希方法比較適合異構節點、節點規模會發生變化的場景。目前Memcached緩存系統實現了該方法，我會在第27篇文章中與你詳細分析。

這種方法不僅解決了節點異構性問題，還提高了系統的穩定性。當節點變化時，會有多個節點共同分擔系統的變化，因此穩定性更高。

比如，當某個節點被移除時,對應該節點的多個虛擬節點均會移除,而這些虛擬節點按順時針方向的下一個虛擬節點，可能會對應不同的物理節點,即這些不同的物理節點共同分擔了節點變化導致的壓力。

當然，這種方法引入了虛擬節點,增加了節點規模,從而增加了節點的維護和管理的複雜度,比如新增一個節點或一個節點故障時， 對應到虛擬節點構建的哈希環上需要新增和刪除多個節點，數據的遷移等操作相應地也會很複雜。

四種數據分布方法對比

為方便理解與記憶，我再通過一個表格和你對比分析下這四種方法吧。請注意,以下方法之間的對比都是相對的比較，實際性能優劣與哈希函數的設定以及具體的數據場景密切相關。