後端工程師面試考什麼 — 從 Hashing 到 Consistent Hashing

分散式快取環境中，十分有可能會碰到需要找到對的 cache server 取得 cache 的情況，畢竟問錯 cache server 不僅拿不到 cache，還十分可能對後端資料庫造成壓力。

所以面試時如果有涉及快取系統架構的問題時，基本的 hashing 或者進階的 consistent hashing 也是必須了解的概念！

本文將介紹 Hashing 與 Consistent hashing 2 種技術，並以實際的 Python 程式碼揭開它們的神秘面紗！

本文環境 #

• Python 3

從 1 個簡單的系統架構談起 #

以下是我曾經面試時，在白板所畫下的系統架構圖的其中 1 個部分：

這是相當簡單、直覺的 Application server, Cache server 與 Database 的架構，在這個架構中使用 Cache server 減輕查詢資料庫所造成的壓力。

不過上述架構存在一些有趣的延伸問題，當時面試官也知道這些問題，所以問：

『這個架構中，Cache server 如果壞了，勢必會對 Database 造成影響，如果是你，你會怎麼解決這個問題？』

當時的我答：

「那再加 1 台 Cache server，如果 1 台掛了，還有另 1 台可以為資料庫擋掉部分壓力。」

面試官又問：

『好，有 2 台 Cache servers 的情況下，Application 要如何知道哪一台 cache server 存有它要的 cache 呢？」

這個問題就帶出本文要談的 Hashing。

雜湊簡介 #

在了解如何解決問題之前，需認識雜湊是什麼。

雜湊是 1 種可以從任何資料單向計算出 1 個稱為雜湊值(hash value, hash code, hash)的技術，而用來產生雜湊值的函數，稱為雜湊函數(hash function)。

它其實就是 1 個經典的 Input, Process, Output 過程。

雜湊有 2 個特點：

1. 相同的輸入值，會產生相同的雜湊值。但是相同的雜湊值，可能是不同的輸入值，此現象稱為雜湊碰撞(collision)。
2. 無法從雜湊值回推原始值，所以任何人都無法從雜湊值逆向回推原本輸入什麼值。

目前常見的雜湊函數有 MD5, SHA-1, SHA-256, SHA-512 等等。

Hash Tables (Hash Maps) 簡介 #

Hash tables / hash maps 是結合雜湊函數並將雜湊除以特定數值取得餘數的技巧，通常用於將任意數值映對(map)到有限空間，例如前文所述將快取資料映對到 2 台快取伺服器其中 1 台的情況，就相當適合使用 hash tables / hash maps，它的算式為：

index = hash_function(input) % size

我們拿使用者的 id 作為 input，並實際用 Python 與 MD5 計算使用者應該要使用哪 1 台 cache server 為例：

from hashlib import md5

servers = {
    0: 'server 1',
    1: 'server 2',
}
idx = int(md5('alice'.encode()).hexdigest(), 16) % len(servers)
print('alice should use cache server ->', servers[idx])

idx = int(md5('groot'.encode()).hexdigest(), 16) % len(servers)
print('groot should use cache server ->', servers[idx])

p.s. int(md5('alice'.encode()).hexdigest(), 16) 是將 16 進位的雜湊值轉成整數

執行結果為：

alice should use cache server -> server 1
groot should use cache server -> server 2

從上述結果來看，系統只要遇到 alice 就會指派使用 cache server 1，如果遇到 groot 就會指派使用 cache server 2。由於雜湊函數相同輸入值會輸出相同雜湊值的特性，所以就算 alice, groot 下次再訪問系統，系統也會指派使用相同的 cache server。

這種方法就能夠解決前述需要知道 cache 在 2 台 cache server 中的哪一台的問題，而且它也是實作方式最簡單的方法。

Hash tables / Hash maps 的問題 #

Hash tables 雖然簡單，但是它也並非完美的解決方案。

它的問題在於新增/刪除節點時，公式中的 size 變了，導致最終計算結果有機會變動，例如從 2 台變成 3 台的情況：

from hashlib import md5

servers = {
    0: 'server 1',
    1: 'server 2',
    2: 'server 3',
}
idx = int(md5('alice'.encode()).hexdigest(), 16) % len(servers)
print('alice should use cache server ->', servers[idx])

idx = int(md5('groot'.encode()).hexdigest(), 16) % len(servers)
print('groot should use cache server ->', servers[idx])

上述執行結果：

alice should use cache server -> server 2
groot should use cache server -> server 2

可以看到 2 台變成 3 台的情況，導致系統判定 alice 應該使用 cache server 2，但 server 2 原本就沒有 alice 的 cache 資料，所以會導致 1 次的 miss，這邊單純以 2 次 requests 來算，miss rate 就變成 50%。（實務上，也可以藉由計算所有現存 cache 資料在新增節點之後會由哪 1 台 cache server 負責，計算出 miss rate。）

當然，這種新增節點所造成的影響，可以直接事先搬遷 cache data 到新的 cache server 以降低對資料庫的影響。

不過，每次新增節點都需要做這件事，其實有點累。

有沒有更好的做法呢？有，就是接下來要介紹的 Consistent Hashing。

Consistent Hashing 簡介 #

Consistent Hashing 最早是 1997 年由 David Karger 等學者所提出的方法，用於分散式的快取系統(distributed caching)，可以減少前述新增/刪除節點所造成的影響。

它的主要概念可以用一張環狀的圖表示：

圖上的 node 代表著可以處理請求的伺服器們，或者說 cache servers。

接下來，我們同樣把資料換算成雜湊值之後，視為環上的一個點，例如換算 alice 與 groot:

最後，要怎麼知道 alice 與 groot 由哪個 node 負責呢？只要從環上往後找最近的 node 即可（要往前找也可以，實作方式可以自由選擇）：

這邊其實也告訴我們 node 也是環上 1 個點，我們也需要算出 node 在環上的位置，才有辦法找到它，所以我們會需要給 node 一個 key / unique name 用來產生雜湊值。

現在再來看 1 個情況，如果新增 1 個節點在 node 1 與 node 2 之間：

你會發現，按照往後查找的規則，alice 與 groot 都不會受到影響！只有 node 1 與 node 4 之間的點會從原本的 node 2 負責，變成由 node 4 負責，不僅影響範圍更好預測之外，影響範圍也受到控制，並不像 hash tables，每個 server 都可能受到波及！

這就是 consistent hashing 的效用！它帶來以下好處：

1. 更好的 Scalability，新增/刪除節點不會全面造成影響，而是視節點在環上的位置而定。
2. 簡化新增/刪除節點所需的操作，由於新增/刪除節點的影響範圍變得十分明確，所以在後端系統可容許的負載範圍內的話，新增/刪除節點甚至可以不需要事先搬遷 cache data。但不建議這樣做，多少搬一些吧！ Production 環境是求穩不是求方便的地方！

不過 consistent hashing 並不是完美的，一如所有的技術都有其缺陷，它也有明顯的壞處：

1. 它需要付出查找 node 的成本代價（談到查找都是代價），Hash tables / Hash maps 的時間複雜度是 O(1)；而 consistent hashing 的時間複雜度為 O(logN)，N 為 node 數（實務上，consistent hashing 多半使用的 binary search 查找）。
2. 增加管理的複雜性。一是雜湊函數並不保證算出來的雜湊值會均勻分布在環上，所以新增/刪除節點，也要新增/刪除在對位置才有作用；二是不同雜湊函數所算出來的數值也不一樣，所以在挑選雜湊函數也要格外注意，否則日後想更換雜湊函數，絕對是系統全面性的問題。

虛擬節點(Virtual Node) #

前文提到雜湊函數不保證算出來的數值會均勻分布之外，我們也很難預測新增的 node 經計算之後的值會落在環上的哪個位置。

為了盡量解決這個問題，就有所謂的虛擬節點，在環上加入多個虛擬節點，這些虛擬的節點背後都對應到 1 個真實節點。

譬如（分佈不均勻是正常的）：

實際上 virtual node 還可以導入權重的概念，讓有些 node 擁有比較多的 virtual nodes，以提高它服務的機率。

實作 1 個 Consistent Hashing #

以下是使用 Python 與 MD5 雜湊函數實作的 consistent hashing：

import hashlib
import bisect

class ConsistentHashing(object):
    def __init__(self):
        self.vnode_num = 50
        self.ring = []
        self.nodes = {}

    def _hash(self, key):
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def add_node(self, node):
        for i in range(self.vnode_num):
            key = self._hash(f'{node}:{i:0>3}')
            self.ring.append(key)
            self.nodes[key] = node
        self.ring.sort()

    def remove_node(self, node):
        for i in range(self.vnode_num):
            key = self._hash(f'{node}:{i:0>3}')
            self.ring.remove(key)
            del self.nodes[key]

    def get_node(self, key):
        if not self.ring:
            return None
        key_hash = self._hash(key)
        idx = bisect.bisect_right(self.ring, key_hash)
        if idx == len(self.ring):
            idx = 0
        return self.nodes[self.ring[idx]]

if __name__ == '__main__':
  ch = ConsistentHashing()
  ch.add_node('node1')
  ch.add_node('node2')
  ch.add_node('node3')
  print('alice ->', ch.get_node('alice'))
  print('groot ->', ch.get_node('groot'))

上述程式碼執行結果如下：

alice -> node3
groot -> node1

接下來解說 ConsistentHashing 重點部分。

首先， __init__(self) 方法中定義 vnode_num 屬性，設定每個 node 在環上會有 50 個虛擬節點。還有 ring 屬性用以儲存每個虛擬節點的雜湊值，最後是將每個虛擬節點雜湊值映對到真實節點的 nodes 屬性：

def __init__(self):
    self.vnode_num = 50
    self.ring = []
    self.nodes = {}

接著是負責轉換雜湊值的 _hash(self, key) 方法，其實就只是將 MD5 雜湊值轉換為整數而已：

def _hash(self, key):
    return int(hashlib.md5(key.encode()).hexdigest(), 16)

再來是負責新增節點的 add_node(self, node) 方法。該方法會用 1 個 for 迴圈製造 50 個虛擬節點，虛擬節點的 key 格式是 f'{node}:{i:0>3}'，如果 node 值為 abc，那麽新增的 50 個虛擬節點 keys 為 abc001 ~ abc050，每個虛擬節點算出來的雜湊值都會放到 ring 屬性中，同時虛擬節點的雜湊值也會作為 nodes 屬性的 key 與 node 進行映對。最後，新增完所有虛擬節點之後，需要對 ring 屬性進行一次排序，確保 ring 裡的元素有序（這也告訴我們雜湊函數產生的值也不保證有序）：

def add_node(self, node):
    for i in range(self.vnode_num):
        key = self._hash(f'{node}:{i:0>3}')
        self.ring.append(key)
        self.nodes[key] = node
    self.ring.sort()

remove_node(self, node) 方法則是算完所有虛擬節點的雜湊值之後，再一一從 ring 屬性與 nodes 屬性刪除而已：

def remove_node(self, node):
    for i in range(self.vnode_num):
        key = self._hash(f'{node}:{i:0>3}')
        self.ring.remove(key)
        del self.nodes[key]

最後的重點是查找 node 的部分。此處會先計算傳進來的 key（例如 alice ）的雜湊值，接著利用 Python 內建 bisect 模組 ，對剛剛計算出來的雜湊值做 binary search，使用 biset_right() 代表從虛擬節點的 list 中找到大於該雜湊值的數的索引值(index)，等同於從環上開始找下 1 個最近的虛擬節點的意思。

如果得到的索引值等於 list 長度，那就代表 ring 屬性的最後 1 個數值依然沒有大於該雜湊值，所以代表它需要使用環上的第 1 個虛擬節點（索引值為 0 ），其餘情況就直接使用找到的虛擬節點所代表的真實節點即可：

def get_node(self, key):
    if not self.ring:
        return None
    key_hash = self._hash(key)
    idx = bisect.bisect_right(self.ring, key_hash)
    if idx == len(self.ring):
        idx = 0
    return self.nodes[self.ring[idx]]

以上，就是 consistent hashing 的實作。此版本屬於精簡版，如果想進一步瞭解，也可以閱讀 uhashring 套件 的程式碼。

總結 #

實際上 hashing 與 consistent hashing 也沒有誰好誰壞，只有適不適合的情境而已。如果是規模較小的系統，也許簡單一點使用 hashing 即可解決問題。如果是需要頻繁增減節點的情況，也許考慮使用 consistent hashing 不失為 1 個好辦法！

以上！

Enjoy!

References #

ultrabug/uhashring: Full featured consistent hashing python library compatible with ketama

Consistent Hashing | System Design

interview backend hashing consistent hashing