點評可調整大小雜湊表：Riak Core和隨機切片技術

Riak 雜湊表 · 發表 2018-09-17 07:27:00

摘要：本文要點雜湊表是一種用於管理空間的資料結構。它最初用於單一應用的記憶體，之後應用於大規模的計算叢集。隨著雜湊表在一些新領域的應用，原有的雜湊表大小調整方法存在一些不好的副作用。亞馬遜公司於2007年發表的Dynamo論文提出將一致性...

本文要點

雜湊表是一種用於管理空間的資料結構。它最初用於單一應用的記憶體，之後應用於大規模的計算叢集。
隨著雜湊表在一些新領域的應用，原有的雜湊表大小調整方法存在一些不好的副作用。
亞馬遜公司於2007年發表的Dynamo論文提出將一致性雜湊技術應用於鍵值儲存。Dynamo型別的一致性雜湊很快被Riak Core及其它一些開源分散式系統採納。
Riak Core一致性雜湊的實現具有一系列侷限性，導致在叢集規模更改時出現問題。
隨機切片是一種非常靈活的一致性雜湊技術，避免了Dynamo型別一致性雜湊中存在的所有侷限。

今年秋天，Wallaroo Labs將釋出其分散式流資料處理框架Wallaroo的一系列新功能。其中一項新功能是支援調整計算群集的規模，實現該功能需要一種大小可調整的分散式資料結構。一個好的做法是使用分散式雜湊表。但問題在於，我們應該如何選擇分散式雜湊演算法？

使用一致性雜湊技術建立可調整大小的分散式雜湊表已有20多年的歷史。看上去似乎一致性雜湊能很好地適用於Wallaroo的情況。鑑於此，本文將探討一致性雜湊是否的確適用。文章的結構如下：

簡介一致性雜湊試圖解決的問題，即在實現調整雜湊表大小的同時，儘量降低不必要的資料移動。
概述Riak Core一致性雜湊的實現。
指出Riak Core雜湊在Riak環境中及在滿足Wallaroo對一致性雜湊實現需求上的一些侷限性。
通過大量的示例和插圖，介紹隨機切片（Random Slicing）技術。

引言：問題在於如何調整雜湊表大小

大多數程式員都熟悉雜湊表。對於初次接觸雜湊表的人而言，推薦閱讀維基百科中雜湊表的相關文章。本文中僅對此給出一個概要介紹。非常熟悉雜湊表的讀者可直接跳到本節末尾的圖一。文中還使用了幾個類似的圖，用於說明一致性雜湊方案。

雜湊表是一種組織計算機記憶體的資料結構。對於鍵“key”，如何確定儲存key相關聯值“val”的位置？

下面的虛擬碼來自維基百科文章：

let hash = some_hash_function(key);; hash is an integer
let index = hash modulo array_size;; index is an integer
let val = query_bucket(key, index);; val may be any data type

一個雜湊表通常包含上述三個基本步驟。其中，前兩個步驟首先將key（可以是任意資料型別）轉換為一個非常大的數值（即例子中的變數hash ），然後再轉換為一個相對更小的數值（例子中的變數index ）。後者通常稱為“桶索引”（bucket index），因為它在雜湊表的具體實現中通常使用陣列實現。變數index 的值通常使用取模運算計算得到。

一些型別的雜湊表在一個桶中儲存單個值。因此，桶的總數（即上例中為array_size ）是一個非常重要的常量。但是如果桶的規模是一個常量，那麼我們應該如何調整雜湊表的大小？做法很簡單，允許array_size 作為一個變數而非一個常量即可。但是這時如果繼續使用取模運算計算index 桶的編號，由於array_size 的大小可調整，雜湊表依然存在著問題。

下面，我們將雜湊表的桶數由3改為10，然後檢視一下前24個雜湊值，即從0到23。

圖一使用取模演算法將雜湊值分配給桶的圖示

在圖一的最左端，雜湊值0、1、2、3所指派的桶並未發生變化。但是當取模演算法再次“轉回”到桶0時，此後的指派全部發生了變化。讀者們可以看到一條從“（hash=4, buckets=3）”開始延伸到圖右端的紅色對角線。如果我們調整了桶的數量，那麼該對角線右側的大部分值也相應地發生了移動！

隨著array_size 值的增加，值移動問題會加劇。尤其是當array_size 從$N$ 增加到$N+1$ 時，只有$\frac{1}{N}$ 的值依然位於原來的桶中。而我們希望發生的情況正相反，我們希望只有$\frac{1}{N}$ 的值移動到新桶中。

一致性雜湊是一種能提供預測雜湊表大小調整行為的方法。下面我們介紹一種特定的一致性雜湊實現，並給出雜湊表調整操作。

一致性雜湊和Riak Core簡史

雜湊表傳統上是一種用於組織計算機記憶體空間的資料結構。1997年，阿卡邁公司（Akamai）的研究者們發表了一篇影響深遠的論文，名稱是“一致性雜湊和隨機樹：一種用於全球資訊網上熱點問題的分散式快取協議”（Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web ）。論文提出使用雜湊表實現對另一種型別空間的組織，即HTTP伺服器叢集的快取。

在SOSP 2007上，亞馬遜公司發表了名為“Dynamo：亞馬遜公司的高可用鍵值儲存”（Dynamo: Amazon's Highly Available Key-value Store ）的論文。受該論文的啟發，Basho Technology公司的創始者們創立了一種Dynamo的開源實現，稱為Riak鍵值儲存。在亞特蘭大召開No SQL East 2009大會上，Justin Sheehy通過演講首次公開介紹了Riak 。此後，Riak的核心軟體庫程式碼從Riak資料庫分離出來，並作為獨立的分散式系統平臺使用。

我注意到Damian Gryski在今年（2018年）早期撰寫的一篇部落格文章，“一致性雜湊：演算法上的權衡”（Consistent Hashing: Algorithmic Tradeoffs ）。我推薦大家閱讀該文，文中介紹了一致性雜湊功能的一些其它實現方法，並給出了對比情況。

Riak Core的一致性雜湊演算法

目前有大量介紹如何使用Riak Core一致性雜湊演算法的資料。本文將通過例子做一個概要介紹，目的是為了引出後文對Riak Core雜湊方法侷限性的討論。

文中引用了Justin Sheehy最早演講中使用的幾個示意圖。第一個示意圖顯示了一個具有32個分割槽的雜湊環，各個分割槽分別指派給4個節點。Riak Core使用SHA-1演算法將雜湊字串轉換為整數。SHA-1的輸出大小為160位，可以直接對映到整數範圍$0\cdots 2^{160}-1$ 。

圖二一個具有32個分割槽的Riak環，間隔分別指派給4個節點

在Riak Core的資料模型中，名稱空間被分隔為“桶”（bucket）和“鍵”（key），這不同於我在本文最後一節所使用的定義。本例中使用了名為“artist ”的Riak桶和名為“REM ”的鍵。我們將這兩個字串連線在一起，作為Riak Core一致性雜湊函式的輸入。

在本例中，雜湊環被分隔為同等大小的32個分割槽，平均分配給四個伺服器節點，即每個節點指派了8個分割槽。字串“artist ”+“REM ”通過SHA-1對映到雜湊環中大約4點鐘的位置。可以看到，node3（粉紅色節點）分配給雜湊環該部分。如果不考慮資料副本，那麼我們可以說node3就是負責儲存鍵“artist ”+“REM ”對應值的伺服器。

下面考慮在第二個例子中新增資料副本。如果node3崩潰了，會發生什麼？這時應該如何定位儲存鍵所對應值的副本？

圖三在32個分割槽環上的Riak get查詢

Riak Core使用了多個常量描述資料副本的儲存位置，其中包括每個鍵對應值的副本總數N，以及從資料庫成功獲取鍵的最小伺服器查詢數R。為計算確定對應於單個鍵的所有伺服器，雜湊演算法採用“順時針在環上行走”，直至找到N個不同的伺服器。在例三中，副本集被粉紅色、綠色和橙色伺服器處理（即node3、node0和node1）.

如果圖中的node3（紅叉標識的粉紅色分割槽）已經崩潰，這時Riak Core客戶傳送查詢到N=3的伺服器，node3並不會響應。但是來自node0和node1的副本足以滿足R=2的約束。客戶響應將是成功回覆{ok,Object} 。

Riak Core一致性雜湊演算法的約束和侷限

我曾在Basho Technologies公司任高階軟體工程師達六年。通過自身的一些事後反思，以及與不少Basho前同事的討論，在此我對Riak Core一致性雜湊演算法做出儘量客觀的批評。我支援Basho繼續保留這些我稱之為侷限性甚至可以說是缺陷的問題，因為它們在當時都是合理的權衡考慮。我們現在的看法都是一些後見之明，並且我們也有時間去反思學術界和工業界的新發現。Basho公司於2017年被清算，其原始碼資產出售給英國的Bet365。Riak Core的維護工作仍繼續在其所有者Bet365和Riak開源社群中進行。

下面列出了Riak Core在實現Dynamo風格的一致性雜湊演算法中的一些假設和侷限性。列表的排序是大致按問題在Basho Technologies公司的嚴重性、麻煩程度、觸發客戶支援工單數以及升級情況。

僅使用SHA-1作為字串轉整數的雜湊演算法。
雜湊“環”的整數間隔範圍是0到$2^{160}-1$ 。
分割槽數是固定的。
分割槽數必須是2的指數次冪。
每個分割槽的大小是固定的。
從歷史上看，用於將伺服器指派給雜湊環上各個間隔的“宣告指派”（claim assigment）演算法考慮過於簡單，並存在錯誤，經常在給出節點間不平衡的工作負載。
沒有考慮按“權重值”調整伺服器的容量。所有伺服器均假定是平等的。
不支援對極端“熱門”鍵（類似於Twitter上人氣最旺的“Justin Bieber”帳戶）的隔離。
對“機架可感知”或“出錯域可感知”的副本放置策略缺乏有效的支援。

其中，侷限性1和2並非大問題，它們都與使用SHA-1雜湊演算法相關。160位的有效雜湊範圍足以適用於我所知道的所有Riak用例。有大量Basho客戶想要用其它演算法替換將SHA-1演算法。Basho支援團隊的官方迴應總是，“我們強烈建議您使用SHA-1”。

侷限性3到5曾在一段時間內有影響，但是它們已在很久以前被清除了。這些侷限性的存在，一開始人們的理由是“Dynamo就是這麼做的”。此後理由成為“Riak程式碼最初就是這麼做的”。在建立了Riak Core軟體庫後，理由變成“這都是一些沒有人願意碰的遺留程式碼”。抱歉，在此我不一一展開介紹，具體原因偏離了本文的主題。

侷限性6到9曾對那些優秀的Basho客戶支援工程師和開發人員造成了很大的麻煩，最終影響了Basho的市場和業務發展。存在缺陷的“宣告指派”（侷限性6）導致了嚴重的資料遷移問題，即當資料需要從X個伺服器移動到Y個伺服器時，會在一些機緣巧合的X和Y組合上出現問題。非常難以實現將原來的Riak叢集從一些更舊更慢的硬體遷移到更新更快的機器（侷限性7），因為在雜湊環指派中Riak Core假定所有的機器具有同樣的CPU和磁碟容量。儘管這些缺陷可以通過人工解決，但是幾乎每次都需要Basho支援團隊的參與。

對於“Justin Bieber”現象（侷限性8），即在某個“熱”鍵上的查詢數呈數量級地高於其它鍵，Riak Core對此束手無策。因為Riak Core分割槽的大小是固定的，將同一分割槽的任何鍵作為超級熱鍵，這都會導致效能降低。唯一的緩解方法是遷移到具有更多分割槽的雜湊環，但這樣做違反了侷限性3。該問題可以（在Basho支援的幫助下）人工解決，但是需要做人工干預指派（伺服器按順時針順序指派給雜湊環），將熱鍵分割槽指派給更大更快的機器。

侷限性9是一個長期存在的市場和業務擴充套件問題。為每個物件維持N個副本，對此Riak Core通常很少存在問題。作為一個最終一致的資料庫，Riak為避免出錯採取了一種更保守的做法，即對每個物件製作多於N個副本，然後在自動“切換”過程中複製併合並副本。

但是，Riak Core的宣告指派並不支援“機架可感知”和“出錯域可感知”。通用電力支援、網路路由器及其它通用基礎設施故障，會導致多個副本同時失敗。為支援單個靜態資料中心的配置，有時我們需要手工建立“在雜湊環上順時針行走”的副本選擇策略。一旦機器再次發生改變（或是單個伺服器發生故障），將會違反我們希望的副本放置策略。

回顧Dynamo和Riak Core的一致性雜湊

亞馬遜公司於2007年發表的Dynamo論文影響深遠。Riak採納了Dynamo提出的一致性雜湊技術，並且時至今日依然在使用。此外，Cassandra資料庫使用了一種閉源的變體實現，還有其它一些系統也採納了Dynamo的模式。作為一名業界從業者，讀論文並思考的感覺很美妙，“這個理念非常好！”，“我可以輕鬆地編碼實現它”。但是，我們同樣需要從另一個角度出發，考慮時間和經驗並提出疑問“這還是個好主意嗎？”

我曾在Basho Technology公司維護、支援並擴充套件了Riak的一些子系統。我認為Riak曾在2009年做了大量有用的工作，並且時至2018年看來許多依然是正確的。但其中並不包括Riak的一致性雜湊。我們在上一節中介紹的侷限性，會導致了很多無法避免的實際問題（雖然我們是事後諸葛亮！）。其中一些侷限性的根源出在最初的Dynamo論文。作為業界，我們現在已具備很多經驗，它們來自於Basho及其它一些開源分散式系統。自2007年以來學術研究領域也得到了十多年的發展，完全改進或取代了Dynamo的工作。

Wallaroo Labs決定為Wallraoo尋求一種替代的雜湊技術。我們當前使用的方法稱為“隨機切片”（Random Slicing）技術。下面將做詳細介紹。

隨機切片：另一種一致性雜湊技術

隨機切片是Riak Core一致性雜湊的一種替代技術。隨機切片的論文是由Miranda等研究人員在2014年發表的，論文名是“隨機切片：一種用於大規模儲存系統的高效、可擴充套件的資料放置技術”（Random Slicing: Efficient and Scalable Data Placement for Large-Scale Storage Systems ）。它與Riak Core技術的主要區別在於：

可以使用任何能將字串（以及位元組列表和位元組陣列）對映為整數或浮點數的雜湊函式。
不需要將雜湊空間視覺化地建模為雜湊環。副本放置並非取決於檢視雜湊空間中的近鄰分割槽。
雜湊空間可以具有任意數量的分割槽。
雜湊空間中一個分割槽的規模可以是任意大於零的值。

在我看來，上述差異足以彌補Riak Core一致性雜湊的所有侷限性。下面給出一些示例圖，用於介紹隨機切片的理念。通過這些示例圖，我們將重新檢視上文列出的Riak Core的主要痛點。

首先給出的示意圖（圖四）中，顯示了一個僅涉及三個節點的隨機切片雜湊表的所有可能情況。

圖四三個節點對映的六種隨機切片策略

在圖四顯示的所有六種可能情況中，分配給節點、和的雜湊空間量分別為33.3\%$。最上面顯示的一種情況是最簡單的，即每個節點分配了一個連續的空間。情況2到4看上去非常類似於Riak Core最初的環宣告策略，只是沒有Riak Core的分割槽個數必須是2的指數次冪的侷限性。情況5也稱為“混雜迴圈分割槽”（Assorted Round Robin Partitions），事實上它是前面一些情況的組合，包括：情況2用於0%-50%區間的間隔，情況4用於50%-75%區間的間隔，情況3用於75%-100%區間的間隔。最下面顯示的是對情況4中的間隔做了隨機排序。注意，在其中三種情況下，節點分配了相鄰的間隔！

隨機切片雜湊表隨時間的變化情況

圖四顯示的所有情況，都是在某一時刻的有效雜湊表隨機切片策略。圖五給出了一個雜湊表的大小隨時間變化（沿Y軸從上到下）的例子。

圖五一個簡單例子，隨機切片雜湊表的大小從1個節點調整為4個節點

圖五給出了一種非常不好的情況。我個人並不建議這樣使用隨機切片。此例說明了隨機切片也存在一些並非最優的用法。在本例中，當節點規模依次從一個節點變成兩個節點、從兩個節點變為三個節點、從三個節點變成四個節點時，雜湊空間中變動的鍵的總數約等於$50.0 + (16.7 + 33.3) + (8.3 + 16.6 + 25.0) = 150\%$ 。這大大超過了最優解決方案產生的資料移動。

圖六給出了從一個節點依次增加到四個節點的一種最優轉變，該例中進一步採用了重新加權操作。

從單個節點開始，n0。
以權重weight=1.0新增節點n1。
以權重weight=1.0新增節點n2。
以權重weight=1.0新增節點n3。
下面將節點n3的權重從1.0增大到1.5。例如，節點n3的磁碟容量相比其它節點升級了50%。

圖六隨機切片雜湊表的一系列轉變，節點數依次從一個新增到四個，之後的權重增大50%

在完成第四步之後，全部四個節點都已經使用同一權重新增，每個節點指派的間隔合計25%。每步遷移的資料總量以及合計遷移的資料總量都是最優的，即$50\%+33.3\%+25\%=108.3\%$ 。與圖五給出的非最優情況相比，圖六的步驟避免了大量的資料移動！

在第五步中，節點n3的權重從1.0增大為1.5，分配給n3的雜湊空間總量從25%增大到33.3%。這樣，其餘三個節點必須放棄一些雜湊空間，即每個節點從25%收縮到22.2%。分配的雜湊空間比例正是我們所期望的，即$33.3\%/22.2\%=1.5$ 。

最後，我們看一下圖七給出的轉移情況圖。在一開始，在隨機切片雜湊表中有四個節點。然後我們每次新增三臺伺服器（表示為圖中的一行），共新增四次。最終，隨機切片雜湊表中將包含16個節點。下面，我們使用三種不同的技術檢視雜湊表，即Riak Core一致性雜湊、使用最優切片策略的隨機切片，以及簡單的連續指派策略。

圖七使用三種不同的切片策略，規模依次變為4個節點、7個節點、10個節點、13個節點到16個節點。

下面對圖七給出幾點解釋：

最下方的圖顯示了“簡單連續”（Naïvely Contiguous）策略。每次轉變都會將雜湊空間完全平衡地指派給每個節點，但會導致在每次轉變中產生大量無必要的資料移動。
最上方的圖顯示的是Riak Core策略。每次轉變中的資料遷移是最優的，但分配給單個節點的雜湊空間總量常常是不平衡的
1. 兩種平衡情況：4個節點和16個節點時。所有的節點指派了均等規模的雜湊空間，分別為25%和6.25%。
2. 三種不平衡情況：7個節點、10個節點和13個節點時。
  1. 對於7個節點時，n4和n5指派了三個分割槽，而其它節點指派了兩個分割槽。不平衡因子為1.5。
  2. 在10個節點和13個節點時，n0、n1、n2和n3指派了兩個分割槽，其它節點指派了一個分割槽，不平衡因子是2.0。
中間的圖顯示的是隨機切片策略。對於每次轉變後的節點的均衡情況，以及每次轉變中移動的資料，隨機切片策略均是最優的。

隨機切片和“Justin Bieber”式超級熱鍵

下面以具有四個節點的雜湊表為例，介紹完美的隨機切片策略，就是圖七所顯示的情況。假定我們的Justin Bieber式超級熱鍵準確地對映到雜湊空間的6.00000%處。從圖七中可看到，6%處對映為節點n0。我們知道n0並不能處理Justin Bieber式鍵的全部負載以及所有指派給該節點的其它鍵。

但是，隨機切片允許我們靈活地建立一種非常細微的新分割槽（例如，範圍從6.00000%到6.00001%的分割槽），並指派給n11節點。這裡n11是一臺Cray 11超級計算機，市面上可買到的最快計算節點。這樣問題就解決了！

問題或許得到了解決，但是也可能並未解決。現實世界中我們並沒有Cray 11。但是如果使用一種靈活的佈置策略，是可以解決Justin Bieber問題的。

隨機切片和靈活的佈置策略

Riak Core一致性雜湊存在一個弱點，目前尚未被隨機切片技術解決，那就是佈置策略。但是該問題很容易修復，只需要新增一個間接層級！（該方法由David Wheeler提出，參見維基百科的“Indirection”詞條。

圖六（再次給出）隨機切片雜湊表的一系列轉變，節點從一個新增到四個，之後的權重增大50%

這裡我們重看一下圖六。圖六一開始，顯示了將一個雜湊空間間隔對映到單個節點或單個機器的情況。我們在此換種做法，引入一個間接層，轉而從雜湊空間間隔對映到一種副本安置策略。之後，我們可以定義我們所希望的任一安置策略。例如：

節點n0 -> 策略0：使用Paxos複製（Paxos Replication）狀態機，在節點82、17和22儲存。
節點n1 -> 策略1: 使用鏈複製（Chain Replication）狀態機，在節點77和23上儲存。
節點n2 -> 策略2：使用7+2 RS編碼（Reed-Solomon），去除節點31-39間的編碼條帶化。
節點n3 -> 策略3：傳送資料到位於舊金山的一臺彩色印表機。
節點n11 -> 策略11：使用一種具有81個主備份和二級備份機器的特殊叢集。其中，一臺主伺服器處理Justin鍵值更改問題，其餘80臺只讀快取機器處理由Justin粉絲所導致的工作負載。

如何實現隨機切片？

下面介紹實現隨機切片所需的資料結構、分割槽策略上的考慮，以及隨機切片自身可做的事情。

隨機切片實現：資料結構

如果我們當前就需要編寫一個隨機切片軟體庫，一種解決問題的方法是隻考慮主要的約束。下面列出一些需要考慮的約束：

約束A：我希望單個範圍查詢能達到何種效能？即從單個鍵開始，例如字串或位元組陣列，結束時給出一種隨機切片分割槽。
- 相關問題：我希望隨機切片雜湊表保留多少個分割槽？
約束B：為實現這樣的效能，我願意付出多少記憶體上的代價？
約束C：隨機切片分割槽需要儲存何種型別的資訊？是否需要對映到單個節點名（以字串、IP地址或其它形式？），或是對映為一種更通用的放置策略描述？

約束A用於選擇將字串或位元組陣列對映為整數的雜湊函式，以及選擇用於範圍查詢的資料結構。對於前者，SHA-1等加密雜湊函式是否足夠快？對於後者，是否需要分割槽表搜尋速度O(1)，或是$O(log(N))$ 即足矣（其中，N是雜湊表的分割槽數）？

一併考慮約束A與約束B，可以決定使用哪種資料結構進行範圍查詢。選擇的目標是：給定一個整數V（即所選用的SHA-1等標準雜湊函式的輸出值），那麼如何選取隨機切片分割槽(I,J)使得$I\leqslant V< J$ 。使用間隔樹（interval tree）軟體庫幾乎就能實現上面的工作。同樣，使用平衡樹（Balance Tree）軟體庫可以執行“小於或等於”查詢，即將所有下限值$I$ 插入樹中，然後執行一個小於或等於$V$ 的查詢。一些Trie樹軟體庫中已經包括此類查詢，可為應用在空間與時間的權衡上提供更好的權衡。

如果使用者需要自己編寫程式碼，那麼一個策略是用排序陣列儲存所有的下限值$I$ 。在執行小於或等於查詢時，可使用二分搜尋法查詢陣列，找到所需的下限值。這正是當前Wallaroo使用Pony語言實現的方法，：

class val HashPartitions
let _lower_bounds: Array[U128] = _lower_bounds.create()
let _lb_to_c: Map[U128, String] = _lb_to_c.create()

最初選用的雜湊函式是MD5。MD5效能可滿足Wallaroo需求，並輸出適用的128位值。Pony原生支援無符號128位整數資料和運算。
上面給出的資料結構（程式碼連結）中，使用U128 無符號128位整數陣列儲存每個分割槽間隔的下限值。
使用二分查詢法搜尋下限值（程式碼連結）。
使用下限整數值作為Pony Map型別Map[U128, String] 的鍵。該Map的鍵為一個U128 型別的整數，返回一個String 型別的值。

最終，我們得到一個String 資料型別，它表示了負責輸入鍵的Wallaroo工作程序名。如果需要支援更通用的安置策略，可將String 型別變更為一個表述所需安置策略的Pony物件型別。該方法也可以返回一個整數值，表示安置策略物件陣列的索引。

與之相對比，為簡化了資料結構，Riak Core設定了一些侷限性，包括固定分割槽大小、分割槽數為2的指數次冪等。給定一個大小為$S$ 的雜湊環，SHA-1雜湊值的前$\log_{2}(S)$ 位用作$S$ 分割槽描述符陣列的索引。

隨機切片實現：分割槽安置（即切片應置於何處？）

隨機切片所需的資料結構非常適中。正如在前面圖四和圖七的例子所示，隨機切片的優點主要來自於對雜湊分割槽的巧妙放置和調整大小。那麼我們應該使用哪些演算法？

我們可以從Miranda及其合作者發表的隨機切片論文著手。其中可使用一些解決“裝箱”問題的演算法和策略，儘管標準的裝箱演算法並不允許更改裝箱物體的大小或形狀。

從實用的角度看，如果隨機切片雜湊表的新增操作非常頻繁，那麼就會建立一些範圍非常狹小以至於不能使用底層資料結構表示的分割槽。在幾年前我為Basho編寫的程式碼中（並未被Riak使用），底層資料結構使用了介於0.0到1.0之間的浮點數。對於一次新增一個節點到雜湊表中，如果重複新增運算元十次之後，那麼分割槽範圍會變得非常狹小，以至於無法用雙精度浮點數變量表示間隔值。

一旦無法對分割槽做進一步分片時，必須重新分配部分分割槽，將許多小的分割槽合併為較大的數個分割槽。任何這樣的重新分配操作都需要移動資料，“沒有其它任何理由”，只是為了使分割槽可以重新做切片。如何選擇最小間隔以使得需重新分配的間隔總和最小，同時使建立更大連續分割槽的優點最大化，這裡存在大量值得做進一步研究的優化問題。我們也可以使用另一種方式解決此問題，即升級應用。使用其它一些具有較小最小分割槽規模的資料結構，解決全部升級的麻煩。任何一種方法都可能適用。

隨機切片實現：相關話題

如果我們已經使用了正確的資料結構，並編寫了全部的程式碼實現隨機切片雜湊表，那麼我們是否已經解決了應用中的所有分散式資料問題？雖然我想說是的，但答案是並非如此。還有其它一些事情需要考慮：

隨機分片雜湊表本身的副本。它可使用某種版本編號方式，也可使用某種保留了歷史資訊的模式。
在隨機切片雜湊表發生更改時，如何移動應用的資料。
在應用資料位置發生移動時，如何解決併發訪問應用資料的問題。
如何管理上述1-3問題中可能出現的所有資料爭用問題。

隨機切片並不能解決上述任何問題，也不存在一種所謂“分散式應用+隨機切片=大小可調節的分散式新應用”的單一解決方案。這些問題的解決方案是應用特定的。

結論：隨機切片是Riak Core雜湊方法的巨大進步

希望讀者能認可我的這一說法，即隨機切片方法是一種比Riak Core一致性雜湊更靈活和更有用的雜湊方法。隨機切片可提供跨機器的細粒度負載均衡，同時可最小化在隨機切片雜湊表中新增、刪除或重加權計算機時的資料複製。隨機切片易於擴充套件，支援任意的放置策略。通過在隨機切片對映中新增範圍非常細微的切片，可實現將流量重定向到專用伺服器（或放置策略），解決“Justin Bieber“式超級熱鍵的問題。

Wallaroo Labs將會很快在Wallaroo資料處理流水線中使用隨機切片技術，實現對處理階段的管理。Wallaroo能夠在消除不必要的資料遷移的情況下，調整各個參與者的工作負載。這一點非常重要。雖然我們並不需要多種放置策略，但是使用者大可放心，無論何時何地一旦有此需要，隨機切片將簡化這些策略的實現。

線上參考資料

截至2018年8月，下列URL均可正常訪問。

Bet365，“Riak Core ”。
Decandia等，“Dynamo：亞馬遜公司的高可用鍵值儲存”（Dynamo: Amazon's Highly Available Key-value Store ”），2007年。
Karger等，“一致性雜湊和隨機樹：一種用於全球資訊網上熱點問題的分散式快取協議”（Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web ），1997年。
Metz，Cade，“How Instagram Solved Its Justin Bieber Problem ”，2015年。
Miranda等，“隨機切片：一種用於大規模儲存系統的高效、可擴充套件資料放置技術”（Random Slicing: Efficient and Scalable Data Placement for Large-Scale Storage Systems ），2014年。
Sheehy，Justin，“Riak：控制你的資料，而非讓資料控制你“（Riak: Control your data, don't let it control you ），2009年。
Wallaroo Labs，“Wallaroo ”。
Wikipedia，“Hash Tables ”。
Wikipedia，“Indirection. ”。
Gryski，Damian，“一致性雜湊：演算法上的權衡”（Consistent Hashing: Algorithmic Tradeoffs ），2018年。

作者簡介

Scott Lystig Fritchie曾擔任UNIX系統管理員十多年，從2000年開始在Sendmail公司轉為一名全職程式設計人員。在Sendmail工作期間，有一位同事向他介紹了Erlang，他的世界從此發生了改變。他曾在USENIX、Erlang使用者大會和ACM上發表過論文，並在Code BEAM、Erlang Factory和Ricon上發表過演講。他曾四次擔任ACM Erlang系列研討會的聯合主席。Scott目前居住在美國明尼蘇達州明尼阿波利斯市，在Wallaroo Labs致力於Pony、Python、Go和C等多語言的分散式系統。

檢視英文原文：A Critique of Resizable Hash Tables: Riak Core & Random Slicing