[Flowchain 專欄] 一分鐘看 IoT Blockchain (Part 4)：認識 Chord 通訊協定

Flowchain 使用一個稱為 Chord 的 P2P 通訊協定，flowchain-chord 是一份 Node.js 的實作。

近來受到相當程度討論的去中心化（Decentralized）概念，則是基於 Peer-to-Peer 通訊網路的分散式系統。Peer-to-Peer 的研究在 2000 年左右，就已經有相關的研究論文發表。Decentralized 與 Block Store 的觀念，在這裡論文裡已經被提出討論。可見這二個目前廣為討論的觀念（Decentralized 與 Block Store）都不是新鮮技術了。

關於 DHT 與 Chord Protocol

Chord[1] 是一個 DHT（distributed hash table）通訊協定，在 peer-to-peer 通訊網路中，DHT 指的是節點（nodes）的 store，用來儲存「資料的負責節點」。因此，Chord 協定能讓 P2P 網路尋找 Data 的負責節點，Chord 協定同時也維護所謂的指向表（Finger Table）來提升尋找節點的效能。Chord 於 2001 年誕生於 MIT[2][3]。

除了 Chord 外，連同其它 3 個 P2P 演算法：CAN、Tapestry 與 Pastry，被稱為 P2P 的 4 大原始演算法。P2P 演算法會維護一份稱為 DHT 的表格，這個表格便是用來紀錄「資料的負責節點」；以 Chord 為例，如果有一筆資料 D1 被送進 P2P 網路裡，負責處理這筆資料的節點稱為 successor，以 sucessor(D1) 來表示，successor() 函數將傳遞進來的資料做 Hash 運算，以 successor(D1)=key1 來表示。

簡而言之，P2P 透過 DHT 來找到負責處理資料的人。Flowchain 區塊鏈就是使用 Chord 來維護 DHT；關於 Chord Protocol 的研究，會參考 MIT Chord/DHash 的原始實作。這是一份 C++ 的實作，Flowchain 則是使用 JavaScript 重新實作了一份輕量化的 Chord 協定。

Chord Protocols

Chord protocols 分為 5 個部份：

• Basic query
• Finger table
• Node join
• Stabilization
• Failures and replication

Stabilization 算法

這是 Chord protocol 最重要的一個環節，根據 Chord protocol 的規範：

• Stabilization protocol 是週期性地（periodically）在背景執行
• 更新 finger table 與 successor pointers

以 JavaScript 來實現 stabilization protocol 的方式：

• 使用 setInterval 實現週期性執行（理論上這可以有更好的 scheduling 實現）

Stabilization protocol 的算法分二個部份：

• Stabilize()
• Nofity()

先定義 Stabilized() 與 Notify() 的訊息：

// 定義訊息類型
var FIND_PREDECESSOR = 0;
var NOTIFY_PREDECESSOR = 1;

其中，Stabilized() 負責向 successor 請求它的 predecessor，並決定 predecessor 是否要成為新的 sucessor：

setInterval(function Stabilize() {
// 請求 predecessor，並將 predecessor 做為新的 successor
    send(successor, {type: FIND_SUCCESSOR, next: next_finger});
}, 1000);

此外，Notify() 負責告知 sucessor 我是它的 node，讓 successor 能更新 finger table：

setInterval(function check_predecessor_and_stabilize() {
// 向 successor 請求 predecessor
    send(successor, {type: NOTIFY_PREDECESSOR});
}, 1000);

Node join

新的 node 建立時，要執行以下任務：

• 初始化 node 的 predecessor 與 finger table
• 通知其它 nodes 更新 predecessors 與 finger table
• 從 sucessor 取得 responsible keys

Finger Table

Finger table 是 Chord 的搜尋演算法。Node 可以經由 finger table 來找到任意節點。Finger table 的演算法設計，搜尋節點的關鍵，它可以避免線性（linear）搜尋的做法。每一個 node 都會有 finger table，finger table 的第 i 個 entry 紀錄的是 sucessor( (n + 2^(i-1)) mod 2^m )。

• m 是 ring 長度，也就是finger table 的長度。這是 Chord network 的最大（最多）節點數量。
• successor 與 predecessor 是重要的觀念。

Finger table 是一個 hash ring 的結構。Chord 經由 predecessor 的觀念，來簡化 join 與 leave 的機制[2]。

小結

要以 P2P Topology 方式建構 IoT Blockchain，對於 P2P 演算法的深入研究，絕對是一項基本功。

References

[1]: Chord, https://en.wikipedia.org/wiki/Chord_(peer-to-peer)

[2]: I. Stoica, et al, Chord: A scalable peer-to-peer lookup service for internet applications

[3]: LibraRing: An Architecture for Distributed Digital Libraries Based on DHTs, http://scholar.harvard.edu/files/ecdl05.pdf

[4]: CS138, http://cs.brown.edu/courses/cs138/s15/content/projects/chord.pdf

[5]: Distributed Hash Tables, http://merlot.usc.edu/cs551-m05/lectures/tentative/20a_chord.pdf