對於 Nebuchadnezzar 中定址問題的一些看法

我最近暫停了開發，為了 Nebuchadnezzar 中的定址問題閱讀了一些論文[1][2][3][4]。在春節前我會面了幾位在 PingCAP 的工程師，他們問我為什麼採用一致性哈希而不採用一些中央定址服務確定數據的位置。一致性哈希是一種 P2P 的定址方法，客戶端可以通過相對固定的信息（比如伺服器列表）確定數據位置，而 PingCAP 開發的 TiKV 則採用一個中央定址集群服務（他們稱為 PD）獲得數據位置。

實際上當時我並不知道如何回答這個問題，因為我還不了解他們的 PD 是如何進行定址的。Google 在它的各種基礎架構系統中使用這種定址方式。看起來這種方式並不會帶來性能問題。PingCAP 聲稱他們的 PD 可以支持每秒百萬次的地址分配，這種性能可以滿足幾乎任何需求。而另一方面，Cassandra，亞馬遜的 Dynamo，微軟的 Trinity 以及斯坦福大學的 RAMCloud 都選擇了一致性哈希作為定址方式。

從 PD 中央定址，或者範圍分片可以獲得的好處是數據可以根據需要集群的伺服器上任意地移動。這就意味著數據可以相對比較容易地順序讀取。如果某個伺服器無法承載一個序列，PD 可以分裂這個序列到其他的伺服器上。客戶端為了獲取數據，需要詢問 PD 數據的位置。在 PingCAP 的 PD 實際實現中，至少需要一次網路通信（如果數據位置被緩存），至多 3 次（如果緩存的位置過時）才能獲得實際的數據內容。

一致性哈希不需要中央服務記錄數據的位置，而客戶端只需要知道伺服器列表以及權重，哈希，排序並成查詢表。客戶端查詢需要對查詢的鍵進行哈希運算，各自在查詢表上做一次二分搜索，就能獲得數據所在的伺服器地址，而集群中的伺服器維護自己的哈希表對應到實際的數據。這當中只會產生一次網路通信開銷，查詢表不會根據維護的數據數量增長，同時查詢表的大小也是可以設置的。一致性哈希的問題在於數據的位置完全由運算出來的哈希的聯合概率分布決定，數據無法任意移動，使得順序讀取變的相當困難。

看起來 PingCAP 考慮過 P2P 的方案但是最後因為實現難度並且額外網路通信並不會對性能帶來太多影響而沒有採用。這是可以理解的，因為 TiKV 是一個基於 RocksDB 開發的鍵值對資料庫，它的數據會即時保存到磁碟上以保證安全性。每一個命令都會潛在地觸發一次磁碟讀寫，而磁碟讀寫時間（1 - 15ms）一般會超過網路通信的時間（< 1ms）,額外的網路通信並不會對性能造成太大影響。另外，因為複製的原因，TiKV 還會有至少一次額外的網路通信用於將數據複製到 follower 節點上。

Nebuchadnezzar 是一個鍵值對資料庫，用於支撐我的 Morpheus 項目。Morpheus 允許用戶在對圖進行增刪查改的同時，還支持進行並行深度優先搜索的圖遍歷。每個圖的點、邊以及元信息都是保存在鍵值對資料庫中的一個單元。在執行圖遍歷的時候，Morpheus 會對所有關聯的點、變以及其他單元在鍵值對資料庫中進行 get 操作。因為圖主要是一種關係型數據數據結構並且它的訪問模式是無法預測的，所以我們可以說它主要是隨機訪問，偶爾順序訪問的模式。因為圖遍歷的模式是隨機的它無法順序存儲，所以使得獲取每一個單元的時間短變得至關重要。在以上的思想下，Nebuchadnezzar 被設計成一個基於內存的，不帶即時寫入磁碟，不內置主從複製的鍵值對資料庫。它有點類似於 Redis 和 memcached，但是原生具備分片和 schema 支持。

低延遲的分散式數據系統在定址問題上相比那些為了安全即時將數據寫入磁碟的資料庫更加敏感。因為我消耗很多精力把單機的延遲降低到 1ms 以下，額外的網路訪問是無法接受的。另外因為大量的隨機訪問，以上提到的 PD 客戶端的緩存機制因為大量的 cache miss 而會很快失效。可以預見採用 PD 的模式無法避免的會有至少 2 次網路通訊，即使採用了批量的方式。另外 PD 的集群是主從複製模式，也就是說定址查詢會集中在一台伺服器上，這樣會潛在地進一步提高延遲。

這個問題使得一致性哈希更加適合 Nebuchadnezzar。定址運行時間只需要 O(log n)，n 是定址表的大小，可以視為一個常量。而網路通信至多只需要一次，使得總延遲更加可控。

但是範圍查詢問題依然存在。儘管 Nebuchadnezzar 是設計成高性能的隨機讀寫資料庫，但是範圍查詢可以建立範圍查詢的索引，對於某些應用場景是非常重要的。這個問題在第一版的 Nebuchadnezzar 並沒有解決，同時也被認為是無法解決的。因為哈希之後數據鍵會失去原本的信息，而無法通過查詢表中進行分為查詢。

實際上存在一些可行方案用於解決基於一致性哈希的範圍查詢。[3] 提供了基於前綴樹的方法，[4] 提供了基於線段樹的方法，可以分別用於字元串和數字的範圍索引。所有這些方案都需要在一致性哈希的查詢表上建立一個新的數據結構，用於追蹤鍵。通過對這些數據結構上進行查詢可以獲得鍵，再通過鍵對進行檢索。

接下來剩下的就是工程上的問題了。我們必須選擇如何將這些數據結構在均勻地分散在集群的伺服器上。幸運的是，以上這些都是樹狀數據結構，所以可以在一台伺服器無法承載時或者按照一定粒度拆成子樹放在其他的伺服器上，並且可以並行執行各類操作。

這個方法也會帶來性能問題，因為在較差情況下可能需要同時聯繫多台伺服器遍歷用於創建或者刪除索引項。這會增加索引有關操作的延遲。其實也可以將索引的過程放在一個不會影響用戶線程的線程中運行，但是這樣用戶也會遇到索引相關的一致性問題。在最終的實現中，我會讓用戶做取捨。

所以我還是會把一致性哈希的設計繼續用於我開發的下一代 Nebuchadnezzar 中，這是一種對性能做出的妥協。下次如果我有時間的話，也許還會在無需低延遲的項目中考慮中央服務定址的方式，比如文件系統。

以上文章內容翻譯自本人的博客 Some thought about addressing problem in Nebuchadnezzar

推薦閱讀：