怎么分析一致性HASH算法

今天就跟大家聊聊有關(guān)怎么分析一致性HASH算法，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結(jié)了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。

一致性HASH算法研究

1.引言

在研究Ceph CRUSH算法時(shí)，看到有文章說它是一種特殊的一致性HASH算法，于是我便開始研究一致性HASH算法做先期準(zhǔn)備，發(fā)現(xiàn)理念確實(shí)接近，區(qū)別在于虛擬節(jié)點(diǎn)和物理節(jié)點(diǎn)的映射辦法不同，這是Ceph的核心算法，非常關(guān)鍵,此處不表，下文分解。

2.一致性HASH的出現(xiàn)背景及其優(yōu)勢(shì)

在分布式系統(tǒng)中，常常利用HASH算法進(jìn)行數(shù)據(jù)分布，目的是希望將數(shù)據(jù)均勻的分布到各節(jié)點(diǎn)，分擔(dān)壓力，尤其是在緩存系統(tǒng)中。一個(gè)典型的設(shè)計(jì)如下：

2.1場(chǎng)景說明

為了提升系統(tǒng)性能，解決數(shù)據(jù)庫的性能瓶頸，設(shè)置N個(gè)緩存服務(wù)器，將應(yīng)用和數(shù)據(jù)庫進(jìn)行隔離，每個(gè)緩存服務(wù)器負(fù)責(zé)數(shù)據(jù)庫1/N的數(shù)據(jù)。應(yīng)用程序在訪問數(shù)據(jù)時(shí)，根據(jù)關(guān)鍵字計(jì)算得到hash值，并根據(jù)一定規(guī)則找到數(shù)據(jù)所在的緩存節(jié)點(diǎn)。

2.2最簡(jiǎn)單模型

最簡(jiǎn)單的辦法是，采用hash(key) mode N的辦法計(jì)算文件落在的服務(wù)器位置，那么在Find Cache Server步驟中，需要增加一個(gè)取摸操作，存在的問題是：
集群添加機(jī)器，計(jì)算公式變?yōu)閔ash(key) / (N + newAddedCount)
集群退出機(jī)器，計(jì)算公式變?yōu)閔ash(key) / (N - removedCount)
由于計(jì)算公式的分母變化，計(jì)算值也都將發(fā)生變化。通過取摸運(yùn)算，找到的節(jié)點(diǎn)錯(cuò)誤，緩存將失效。我們需要一種方法，當(dāng)對(duì)集群擴(kuò)容，或者從集群中移除失效機(jī)器時(shí)，只會(huì)導(dǎo)致少量的數(shù)據(jù)失效，可以很快的在正常的機(jī)器或者新增的機(jī)器上重新構(gòu)建起緩存。

2.3 一致性HASH模型

基于這個(gè)想法，一些專業(yè)人士更提出了明確的要求，并形成論文 一致性HASH論文

2.3.1 一致性HASH基本設(shè)計(jì)思路

一致性哈希構(gòu)造了一個(gè)hash環(huán)，將服務(wù)器節(jié)點(diǎn)映射到環(huán)上，將obj也映射到環(huán)上，將他們至于同一個(gè)空間中（0~2^32-1），針對(duì)每一個(gè)對(duì)象，順時(shí)針查找第一個(gè)>=hash(obj)的節(jié)點(diǎn)，就是它要存放的目標(biāo)系統(tǒng)，如果沒有找到，按照順時(shí)針，就回歸到第一個(gè)服務(wù)器。

![ 在上圖實(shí)例中，根據(jù)一致性HASH規(guī)則，分配后的結(jié)果如下：
obj1 ~ obj3歸屬于Cache Server B；
obj4 ~ obj7歸屬于Cache Server C;
obj8~obj11歸屬于Cache Server A.正是按照上述規(guī)則分析下來的結(jié)果。

但是存在一個(gè)數(shù)據(jù)分布不均衡的問題，在下圖中可以看到，大量的數(shù)據(jù)會(huì)落在服務(wù)器A上，但是B,C上只有少量數(shù)據(jù)。數(shù)據(jù)分布明顯不平衡。

為了解決數(shù)據(jù)不均衡的問題，一致性HASH中引入了虛擬節(jié)點(diǎn)，將對(duì)象均勻的映射到虛擬節(jié)點(diǎn)，再將虛擬節(jié)點(diǎn)映射到物理節(jié)點(diǎn)。

通過設(shè)置大量的虛擬節(jié)點(diǎn)，將數(shù)據(jù)平均分布到虛擬節(jié)點(diǎn)上，最終達(dá)到平均分布到物理節(jié)點(diǎn)上的效果。此處的關(guān)鍵點(diǎn)是：通過為每個(gè)物理節(jié)點(diǎn)配置虛擬節(jié)點(diǎn)，所有的虛擬節(jié)點(diǎn)可以平均的散布到hash環(huán)上此處一看使用的hash函數(shù)；另外看物理節(jié)點(diǎn)設(shè)置的虛擬節(jié)點(diǎn)數(shù)量；

此處，一致性hash是符合我們的期望的：

1、平衡性(Balance)：hash后的結(jié)果能夠平均分布，比如在存儲(chǔ)中，數(shù)據(jù)可以平均分布到各節(jié)點(diǎn)，不會(huì)出現(xiàn)個(gè)別節(jié)點(diǎn)數(shù)據(jù)量特別少，個(gè)別特別多的情況；
2、單調(diào)性(Monotonicity)：當(dāng)新增或者移除節(jié)點(diǎn)時(shí)，要么映射到原來的位置，或者映射到新節(jié)點(diǎn)；不會(huì)映射到無效節(jié)點(diǎn)；

2.3.2 數(shù)據(jù)分布均衡測(cè)試

為了測(cè)試一致性hash算法的特性以及虛擬節(jié)點(diǎn)對(duì)數(shù)據(jù)分布平衡的影響，我用C++實(shí)現(xiàn)了一個(gè)一致性hash算法，進(jìn)行統(tǒng)計(jì)試驗(yàn)。

1. 在相同的測(cè)試數(shù)據(jù)，相同的物理節(jié)點(diǎn)下，測(cè)試不同虛擬節(jié)點(diǎn)數(shù)量下，數(shù)據(jù)的分布情況： 測(cè)試樣本：10000條URL記錄，用作對(duì)象名稱，作為hash函數(shù)的輸入 采用的hash函數(shù)：c++11中默認(rèn)的std::hash() 數(shù)據(jù)中虛擬節(jié)點(diǎn)數(shù)量參數(shù)是指每個(gè)物理節(jié)點(diǎn)對(duì)應(yīng)的虛擬節(jié)點(diǎn)數(shù)量。

1節(jié)點(diǎn)
101.71.4.31:80  764
101.71.4.32:80  2395
101.71.4.33:80  1478
101.71.4.34:80  786
101.71.4.35:80  4577

10節(jié)點(diǎn)
101.71.4.31:80  1139
101.71.4.32:80  4862
101.71.4.33:80  1484
101.71.4.34:80  1243
101.71.4.35:80  1272

100節(jié)點(diǎn)
101.71.4.31:80  2646
101.71.4.32:80  2576
101.71.4.33:80  1260
101.71.4.34:80  705
101.71.4.35:80  2813

512虛擬節(jié)點(diǎn)
101.71.4.31:80  2015
101.71.4.32:80  2038
101.71.4.33:80  1948
101.71.4.34:80  2128
101.71.4.35:80  1871

1024虛擬節(jié)點(diǎn)
101.71.4.31:80  2165
101.71.4.32:80  1389
101.71.4.33:80  2045
101.71.4.34:80  2123
101.71.4.35:80  2278

2048節(jié)點(diǎn)
101.71.4.31:80  1976
101.71.4.32:80  1939
101.71.4.33:80  1892
101.71.4.34:80  2164
101.71.4.35:80  2029


4096節(jié)點(diǎn)
101.71.4.31:80  1972
101.71.4.32:80  2139
101.71.4.33:80  2095
101.71.4.34:80  1879
101.71.4.35:80  1915

從數(shù)據(jù)可以看到，隨著對(duì)應(yīng)的虛擬節(jié)點(diǎn)越來越多，數(shù)據(jù)的分布也越來越平衡，但是虛擬節(jié)點(diǎn)到達(dá)一定數(shù)量后，到達(dá)了瓶頸，畢竟不可能實(shí)現(xiàn)絕對(duì)的平衡。

2.通過增加或者移除節(jié)點(diǎn)，查看數(shù)據(jù)的移動(dòng)情況： 移除節(jié)點(diǎn) 采用1024虛擬節(jié)點(diǎn)的情況下，使32節(jié)點(diǎn)失效，得到如下的統(tǒng)計(jì)結(jié)果：

101.71.4.31:80  2392
101.71.4.33:80  2374
101.71.4.34:80  2635
101.71.4.35:80  2599

我對(duì)記錄文件進(jìn)行了對(duì)比，發(fā)現(xiàn)31,33,34,35原來各自屬于自身的數(shù)據(jù)沒變，多出來的是32上的數(shù)據(jù)，被平均分布到了還有效的四臺(tái)機(jī)器。

增加節(jié)點(diǎn)，采用1024虛擬節(jié)點(diǎn)的情況下，增加36節(jié)點(diǎn)，得到如下結(jié)果：

101.71.4.31:80  1726
101.71.4.32:80  1271
101.71.4.33:80  1776
101.71.4.34:80  1743
101.71.4.35:80  1768
101.71.4.36:80  1716

我對(duì)記錄文件進(jìn)行了對(duì)比，發(fā)現(xiàn)31,32，33,34,35上的數(shù)據(jù)還是以前屬于他的數(shù)據(jù)，但是各自有部分遷移到了36機(jī)器上。

這兩個(gè)實(shí)驗(yàn)都說明了一致性Hash的單調(diào)性。

2.3.3 一致性hash算法實(shí)現(xiàn)

//構(gòu)建帶虛擬節(jié)點(diǎn)的hash環(huán)，對(duì)每個(gè)真實(shí)的物理節(jié)點(diǎn)，配置若干虛擬節(jié)點(diǎn)，并進(jìn)行排序
for (RNode node : rnodes)
{
	for (int i = 1; i <= virtual_node_count; i++)
	{
		VNode vnode;
		vnode.ip_port = node.ip_port + "#" + to_string(i);
		vnode.id = myhash(vnode.ip_port);  //虛擬節(jié)點(diǎn)在hash環(huán)上的映射
		circle.push_back(vnode);
		node.virtual_nodes.push_back(vnode);
	}
}

sort(circle.begin(), circle.end(), cmpVNode);

//計(jì)算每個(gè)URL落在那個(gè)虛擬節(jié)點(diǎn)
VNode getLocation(string url, vector<VNode>& vnodes)
{
	VNode tmp;
	tmp.id = myhash(url.c_str());
	vector<VNode>::iterator iter =  std::lower_bound(vnodes.begin(), vnodes.end(), tmp, cmpVNode);

	if (iter == vnodes.end())
	{
		return vnodes[0];
	}else 
	{
		return *iter;
	}
}

//根據(jù)虛擬節(jié)點(diǎn)，找到對(duì)應(yīng)物理節(jié)點(diǎn)
string real_node = getRealNodeInfo(vnode);

3.CRUSHMAP的進(jìn)一步研究

研究一致性HASH的目的是為了更好的理解Ceph CRUSHMAP算法，此處簡(jiǎn)單說明Ceph中對(duì)象是如何映射到具體設(shè)備的某塊硬盤上。 在Ceph中，每個(gè)對(duì)象都屬于某個(gè)PG，我把這些PG理解為一致性哈希中的虛擬節(jié)點(diǎn)，目的是為了讓對(duì)象分布更均勻。 而pg是如何映射到OSD呢。在上文中，這種映射關(guān)系比較簡(jiǎn)單，就是多對(duì)一，在ceph中則比較復(fù)雜，因?yàn)橛成潢P(guān)系依賴于集群的拓?fù)浣Y(jié)構(gòu),而每個(gè)對(duì)象都還有多副本,需要指定的映射算法，計(jì)算出pg所在的主OSD以及副本OSD。

看完上述內(nèi)容，你們對(duì)怎么分析一致性HASH算法有進(jìn)一步的了解嗎？如果還想了解更多知識(shí)或者相關(guān)內(nèi)容，請(qǐng)關(guān)注億速云行業(yè)資訊頻道，感謝大家的支持。