Consistent Hashing Algorithm: 應用情境、原理與實作範例

前言

在設計一個分散式系統 (Distributed systems) 的架構時,基於提高系統資料 (Data) 承載量的需求,我們就會需要一個機制,將資料分送給不同的服務節點 (Service nodes) 處理。在我們公司的產品:OWL Monitoring System 中,我們也有這樣的設計。我們的系統是以 Open source 的監控系統 Open-Falcon 做為基底而開發的。在此系統的設計當中,被觀察的電腦叢集 (Computer clusters) 傳送大量的資料給 Open-Falcon 系統核心。Open-Falcon 系統收到這些資料之後,將使用這些資料來判斷是否達到觸發警報的條件,同時也將這些資料以時間軸為維度製作圖表。我們必須將這些資料分派到不同的服務節點才有辦法處理這樣大量的資料。

然而在這樣的情境底下卻有一個棘手的問題:我們希望一台被觀察的伺服器 (Server) 中同一個被監控項目(如 cpu.idle)總是能夠被送到同一台服務節點處理。假如我們是隨機分送被監控項目的資料給任何一個服務節點,同一個被監控項目在不同的時間點上的資料將可能被分送到不同的服務節點處理。當我們需要以時間軸為維度來畫圖,或是判斷某一時間區間之內是否達到觸發警報的條件的時候,我們就必須將這些分散在不同服務節點上的資料彙整在一起才能處理。如果照著這樣的想法去設計系統,則很容易產生瓶頸 (Bottleneck) 或是 Single point of failure 的問題。然而,如果我們能保證同一個被監控項目的資料總是被分送到同一個服務節點處理,那麼服務節點只需要根據自己獲得的資料,便能判斷該被監控項目的資料是否達到觸發警報的條件,或是將資料在時間軸上製作圖表。這種做法並不需要將資料從各處彙整在一個節點,因此可避免了上述的問題。那要我們要怎麼盡量保證資料總是被分送到同一個服務節點呢?Open-Falcon 使用 Consistent Hashing Algorithm 來解決這個問題。我們將在本篇介紹 Consistent Hashing 的原理,並搭配 Open-Falcon 中所採用的 Go 語言的 Consistent Hashing 套件 (Package) 的實作程式碼來解說。

Consistent Hashing Algorithm

Hash Table

在提及 Consistent Hashing 之前,我們先來複習一下以前在演算法這門課所學到的 Hash table 的概念。Hash table 是一個 Abstract Data Type (ADT),它的優點是通常可以用比較快的時間完成 Search operation 的動作。我們先來解釋 Hash table 會用到的術語以及其運作的方式。當我們想對一個 Hash table 做存取的動作時,首先會需要一個輸入的參數,我們稱之為 Key。我們會利用一個稱作 Hash function 的函式,將此 Key 映射 (Map) 至一個 Hash value。 Hash value 是用來當作 Index 的。這個 Index 決定存取的動作會找到的是哪一個 Slot。而 Slot 代表的是電腦中的記憶體位置 (Memory location)。我們透過 Key 所要找的 Value 就存放在這個 Slot 之中。

Hashing: 實現資料與服務節點的映射關係

在分散式系統中,我們可以將待處理的資料當作 Key,最後找到的 Value 就是資料將要被分送到的服務節點。同樣地,Open-Falcon 監控系統當中,我們也可以把一台機器上的一個被監控項目的資料當作一個 Key,最後找到的 Value 就是此被監控項目的資料所要分送到的服務節點。Open-Falcon 利用 Consistent Hashing 演算法來實現這樣的映射關係,其原因在於此演算法有一個最大的特點:當服務節點增加或減少的時候,Key 與 Value 的映射關係變動較小。如果因為服務節點的增減,導致系統將大部份被監控項目的資料送往和原本不同的服務節點,那麼便會在增加或減少服務節點的當下產生問題:對於同一個被監控項目,增加或減少服務節點之前與之後的資料,並不是給同一個服務節點處理。而 Consistent Hashing 的優點就是它能盡量保持大部份的資料都能送往和原本相同的服務節點。我們以數字來舉例說明 Consistent Hashing 的運作方式比其他的方式還要適合的原因。

Consistent Hashing 的優點

在大多數設計 Hash function 的例子當中,我們都會希望 Hash function 能盡量讓每個slot的可能性都一樣,才能避免 Collision 的發生。最常見且淺顯易懂的例子就是用算餘數的方式。假設服務節點的數量為N,Hash function 的計算方法如下:

hash_function(key) = key mod N

如果把這種 Hash function 應用在分散式系統中會有什麼問題呢?假設我們總共有 23 個服務節點,也就是 N = 23。這 23 個服務節點就相當於 Hash table 中的 23 個 Slots。一個隨機的 key 映射到每個 slot 的機率都是 1/23。假設今天系統增加了一個服務節點,也就是 N 改為 24,則每個 key 只會有 1/24 的機率被分配到原本的 Slot。假設今天我們減少了一個服務節點,也就是 N = 22,則每個 key 只會有 1/23 的機率被分配到原本的 Slot。這表示大部份的資料在服務節點數量改變之後都會被分送到不同的服務節點。然而如果使用 Consistent Hashing 的方法,根據維基百科裡面的算法,在此範例中增加一個服務節點,則每個 key 只有 1/24 的機率會改變映射關係;減少一個節點,則每個 key 只有 1/23 的機率會改變映射關係。

Consistent Hashing 的運作方式與實作程式碼

為了瞭解他的運作方式,我們舉個例子來說明。我們先想像有一個 hash values 的空間 (Space),其範圍是 0 ~ 2^32-1,也就相當於 Unsigned integer 的範圍。我們把此 Space 圖像化,成為一個依照順時針方向遞增的環 (Consistent Hash Ring),如下圖:

我們假設有3台服務節點分別是 ServiceNode-1, ServiceNode-2, ServiceNode-3,我們可以把這三台機器名稱的字串當作參數,並利用某個函數把它轉換成三個 Unsigned integers,當作存放這些代表服務節點的字串的 Slots 的 Indexes。這個函數我們先姑且稱之為 Pre-hashing。實作上,我們常常需要將 Keys 或者 Hash values 以 Unsigned integer 的型態 (Type) 呈現,而 Pre-hashing 做的事情就是把那些不是 Unsigned integers 的物件轉為 Unsigned integers。我們先把代表這三台服務節點的 Indexes 放在這個 Consistent Hash Ring 上呈現如下圖:

在套件的程式碼中,這樣的動作被實作在 func add() 之中:

func (c *Consistent) add(elt string) {
    for i := 0; i < c.NumberOfReplicas; i++ {
        c.circle[c.hashKey(c.eltKey(elt, i))] = elt
    }
    c.members[elt] = true
    c.updateSortedHashes()
    c.count++
}

在此套件中,服務節點皆以字串的方式代表。add() 函式中的 circle 所代表的就是 Consistent Hash Ring,存在上面的資料就是代表服務節點的字串,而存取 circle 所使用的 Indexes 就是服務節點 Slots 的 Indexes。而此函式使用到的 hashKey() 就是上面所提及的 Pre-hashing 函式。它把字串轉為 Unsigned integers,做為 Slots 的 Indexes,並當作存取 circle 的 Indexes。在 add() 中,我們可以發現這裡面有一個 for 迴圈,使得一個字串最後在 circle 中存入多個 Indexes。這部分是虛擬服務節點的實作,我們到後面再提。

接下來我們要說明的是在 Consistent Hashing 中的 Hash function 要怎麼根據 Keys 找到 Hash values。實作上,Keys 必須是一個 Unsigned integers。假設今天我們是要為被監控項目的資料找一個服務節點,則我們必須先把這份資料透過上面提過的 Pre-hashing 函式轉換成一個 Unsigned integer 來當作代表這份資料的 Key,我們把這個 Key 放到 Consistent Hash Ring 中呈現,如下圖標示為綠色的部分:

接著,Consistent Hashing 的做法是找「沿著順時鐘方向走,遇到的第一個 Index」。我們從這個 Unsigned integer 的所在位置沿著順時鐘方向走,遇到的第一個代表服務節點的 Index 就是這個 Key 所映射的 Hash value。這個 Hash value 代表著存放某個服務節點的 Slot 的 Index。找到了這個 Slot,就表示找到了這份被監控項資料所對應的服務節點了。如圖中標示土黃色的部分:

這樣的動作被實作在 func Get() 之中:

func (c *Consistent) Get(name string) (string, error) {
    c.RLock()
    defer c.RUnlock()
    if len(c.circle) == 0 {
        return "", ErrEmptyCircle
    }
    key := c.hashKey(name)
    i := c.search(key)
    return c.circle[c.sortedHashes[i]], nil
}

此函式先用 hashKey() 這個實作 Pre-hashing 的函式把型態為字串的參數轉為型態為 Unsigned integer 的 Key,再利用 search() 函式以 Key 為參數,進行Binary search。search() 函式所搜尋的對象是 sortedHashes 這個 Slice。在 sortedHashes 中存的是排序過的服務節點的 Indexes。找到了 Key 所對應的 Index 後,Get() 函式最後根據此 Index 回傳在 circle 上代表服務節點的字串。

解釋了 Consistent Hashing 的運作方式之後,我們來討論增加或減少服務節點的情況。假設我們今天增加了一個服務節點 ServiceNode-4,則只有圖中標示黃色區間的 Keys 會因為 ServiceNode-4 的加入而找到不同的 Hash values:

假設我們今天把 ServiceNode-2 給移除,只有圖中標示黃色區間的 Keys 會因此而找到不同的 Hash values:

根據以上的例子,我們並不難觀察出 Consistent Hashing 的做法的確能比一般的方式更能保持原本的 Keys 與 Values 之間的映射關係。

虛擬服務節點 (Virtual Service Nodes)

如果此系統的服務節點很少,就表示這些節點在 Consistent Hash Ring 上所對應的 Indexes 數量很少。舉個例子,假設今天只有兩個服務節點 ServiceNode-1, ServiceNode-2,而它們的 Indexes 的分佈很有可能並不平均。如圖所示,綠色區間的 Keys 都會找到 ServiceNode-1 的 Index 做為其 hash values,而只有紅色區間的 Keys 會找到 ServiceNode-2:

這個問題將造成服務節點的資料承載量不平均。所以以實際面來說,Consistent Hashing 的實作通常會搭配一些虛擬的服務節點。舉個例子,我們假設每一個服務節點都擁有 4 個複製品 (replicas),這 4 個複製品也都各自經由 Pre-hashing 函式算出它們的 Indexes。然而,這多出來的 4 個複製品的 Indexes 所代表的 Slots 其實裡面存的是原本的服務節點的字串。如下圖:

當 Consistent Hash Ring 中的 indexes 數量變多,分佈不均勻的機會較小,服務節點的承載量不均勻的情況就可以改善了。

虛擬服務節點的機制被實作在 func add() 裡面的 for 迴圈之中:

    for i := 0; i < c.NumberOfReplicas; i++ {
        c.circle[c.hashKey(c.eltKey(elt, i))] = elt
    }

裡面的 for 迴圈會執行的次數由 NumberOfReplicas 的值所決定,其意義就是複製品的數量。對於每個輸入的代表一個服務節點的字串,add() 函式利用 eltKey() 函式與 hashKey() 函式製作了數目為 NumberOfReplicas 的 Indexes,使得一個服務節點的字串最後存在 circle 上共 NumberOfReplicas 個位置 。