魔牛財經 > 魔牛資訊 > 百科大全 > 區塊鏈技術入門 | 分布式哈希表(上篇)

區塊鏈技術入門 | 分布式哈希表(上篇)

DHT 即分布式哈希表,是實現分布式存儲和下載的關鍵技術,現已廣泛應用在P2P網絡中。想要了解分布式哈希表的技術實現,首先需要知道什么是哈希算法和哈希表。

哈希算法簡單來說就是一個函數,這個函數有一些特殊的性質:

1. 無論輸入有多復雜,輸出的長度都是固定的。

2. 無論輸入發生多么微小的變化時,輸出都會與之前完全不同。

3. 無法通過哈希值倒推原信息,也就是不可逆。

哈希表,又稱為散列表,這個表是用來存放鍵值對的。當給文件加密時,不僅僅需要存儲文件的哈希,也需要存儲文件本身。這樣就需要將文件和哈希成對存儲以方便查找。

對于普通的哈希表而言,擴容的代價是很大的。因為普通的 Hash 計算地址方式如下:Hash(Key)%M,擴容之后,元素的位置全變了。有數學證明,擴容成兩倍大小,使得再哈希的元素個數最少,這也是為什么為了減少擴容時元素的移動,總是將哈希表擴容成原來大小的兩倍的原因。

所以哈希表的本質,就是當你尋找某個信息時,最終都是一個將哈希值取余去尋找某個位置的一個過程,但我們也看到了,當有新的節點加入或者舊節點退出時,都需要重新存放鍵值對,當信息量較大的時候就容易導致網絡阻塞。

為了解決節點變動的問題,1997 年麻省理工的 Karger 等人發明了一致性哈希,這才真正讓分布式存儲進入到了一個真正可以規模化應用的階段。

什么是一致性哈希呢?

首先,將哈希值空間組織成一個虛擬的圓環,我們以 SHA256 來舉例。SHA256 有 2^256 個哈希值,將所有可能的哈希值組成一個圓環,從 0 到 2^256?1,按順時針進行排序,并且在 12 點處 0 與 2^256?1 重合。

然后,將各個節點用于存儲的服務器進行一次哈希計算,可以選擇服務器的 IP 地址或者主機名進行哈希計算(為防止主機名重疊一般使用 IP地址,這里很重要),并且按照計算所得哈希將節點服務器按照順序放在圓環的相應位置

image.png

最后,將數據的 key(鍵,即數據的關鍵詞)使用相同的哈希算法計算出哈希值,并確定此數據在環上的位置,從此位置沿環順時針“行走”,第一臺遇到的服務器就是其應該定位到的服務器。

image.png

這樣,當某一節點因為某種原因而停止運作時,只會影響到其逆時針方向上到上一個節點之間的數據,同樣,當新加入了一個節點的時候,也只影響到其逆時針方向上到前一個節點之間的數據。

普通的一致性哈希有沒有缺點呢?當然是有的。總結一下就是:沒有考慮到每臺機器的情況,不能實現很好的負載均衡。

有沒有解決辦法?有,就是虛擬機技術。例如當一個哈希環中只有兩個節點存在:

image.png

可以看到,很有可能出現上圖這種分配不均勻的情況,為了能在不加入物理設備的前提下實現負載均衡,我們將兩個節點的IP后加入一些別的內容(例如#1、#2)再次計算哈希,得到 Node 1.1,Node 1.2,Node 2.1,Node 2.2,使其實現下圖中的情況:

image.png

當這些虛擬節點加入,數據的分配自然要發生變化,當然,這些虛擬機的物理實體只有一個,自然會存到真正的物理實體中,自然就可以讓負載盡量均衡。

IPFS的底層技術中,DHT是非常重要的一環,而之所以IPFS會更加偏好公網固定IP,就是因為固定IP不會改變在哈希環中的位置,進而不會造成因節點變動而產生的額外網絡負載。這也是礦場收益會更高且更加穩定的原因之一。

到此,分布式哈希表DHT的基本技術已經介紹完畢。

(作者:區小白)


【版權聲明】該文章由本站整理于網絡的相關信息,魔牛不擁有所有權,不承擔相關法律責任。
聲明:版權所屬區小白 ,未經授權不得轉載,已經協議授權的媒體下載使用時須注明"稿件來源:區小白 ",違者將依法追究責任。
比特幣實時價格 ¥59975.2929133080
  • 比特幣
  • 實時價格
  • ¥ 59975.2929133080
江苏7位数开奖基本走势图