search

jollen / blog

Jollen's Blog
http://www.jollen.org/blog
66 stars 4 forks source link

Chord Network #21

Closed jollen closed 7 years ago

jollen commented 7 years ago

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

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

關於 Chord Protocol

Chord[1] 是一個 DHT（distributed hash table）通訊協定，在 peer-to-peer 通訊網路中，DHT 是 "nodes" 的 store，用來儲存 key-value paris。Chord 協定用來指派 key 到 nodes，Chord 協定同時也讓 node 來取代 key 的 value。Chord 於 2001 年誕生於 MIT[2][3]。

Chord Protocol 的主要實作參考是 MIT Chord/DHash，這是一份 C++ 的實作。

Chord Protocols

Chord protocols 分為 5 個部份：

Stabilization 算法

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

Stabilization protocol 的算法分二個部份：

先定義 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 建立時，要執行以下任務：

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

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

Chord for Things

Chord 運用在 Internet of Things 與 Web of Things 的場景為何？

參考文獻

[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] [1] 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 [6] http://zoo.cs.yale.edu/classes/cs722/2011/Jason_chord.pdf

其它資源

[1] http://www.dcs.ed.ac.uk/teaching/cs3/ipcs/chord-desc.html [2] http://slideplayer.com/slide/4418035/ [3] http://www.slideshare.net/imprataap/chord-node-join

jollen commented 7 years ago

closed by #40