# 6-4: Chord

## INTRODUCTION

* Distributed Hash Table (DHT):
* 是為了解決分散式系統中的 hotspot 問題而提出的概念。
* 整體概念是將資料平均分散在各個 node，需要使用時可以快速找到存放資料的 node。
* 總共有以下四種指標來評斷:
> * Balance: Hash的結果要能夠讓Data平均分散到不同的Node上。這在很多的Hash Function都可以做到
> * Monotonicity:
> 在初始化將Data經過Hash儲存到各個Node A、B、C 中的 A 後，
一個新的Node D 的加入，要嘛Data被重新Hash到原本的 NodeA 中或是新的 NodeD 中，不會被分配到B或是C。
> * Spread: 因為是分散式的環境，Client對於目前全局的Node個數可能不是正確的，不同的Client得到的Node資訊可能不ㄧ樣。因此當Client要藉由DHT將Data儲存到節點上，可能會發生同樣的Data被儲存到不同的Node上。Spread就是這個情況的嚴重程度。
> * Load: 換個角度說上面Spread情況可能也會導致，一個節點A被兩個Client1&2儲存了不同的Data1&2，但是其實Data1&2應該是要在兩個不同的Node上，只因為Client得到的Node資訊錯誤。這會導致節點A的Load增高，因為想要Data1&2的人都會去找他。

* Consistent Hashing:
* 在 node 被新增與刪除時也可以保證 DHT monotonicity 的方法，

* chord 是一種 consistent hashing 的方法，它可以在 $O(logN)$ 的時間內找到某個資料存放的 node，且每個 node 只需要存放 $O(logN)$ 個其他 node 的資訊，且演算法本身是去中心化的，所以不會有單點 fail 的問題。

* 可以將 chord 想像成一種 routing 演算法，要如何從 client query 的 node(source)最快的到達資料存放位置的 node(destination)，其中走的 node 數就被稱為 HOPS。

## RELATED WORK

## SYSTEM MODEL

> 最快速度理解可以參考 [chord](https://ithelp.ithome.com.tw/articles/10226592)

* chord需要滿足以下五個性質:
> * Load balance: 平均分配所有資料到不同的node。
> * Decentralization: node 是 P2P 的架構，沒有 master。
> * Scalability: node 增加時，演算法還是很有效率。
> * Availability: 可以 handle node 的新增與刪除
> * Flexible naming: 應用程式可以選擇任何值當作 key 與 value。

* chord可以用來達成以下服務:
> * **Cooperative mirroring**, in which multiple providers of
content cooperate to store and serve each others’ data. The
participants might, for example, be a set of software development projects, each of which makes periodic releases.
Spreading the total load evenly over all participants’ hosts
lowers the total cost of the system, since each participant
need provide capacity only for the average load, not for
that participant’s peak load. Dabek et al. describe a realization of this idea that uses Chord to map data blocks onto
servers; the application interacts with Chord to achieve
load balance, data replication, and latency-based server selection [9].
> * **Time-shared storage** for nodes with intermittent connectivity. If someone wishes their data to be always available,
but their server is only occasionally available, they can
offer to store others’ data while they are connected, in return for having their data stored elsewhere when they are
disconnected. The data’s name can serve as a key to identify the (live) Chord node responsible for storing the data
item at any given time. Many of the same issues arise as
in the cooperative mirroring application, though the focus
here is on availability rather than load balance.
> * **Distributed indexes** to support Gnutella- or Napster-like
keyword search. A key in this application could be derived
from the desired keywords, while values could be lists of
machines offering documents with those keywords.
> * **Large-scale combinatorial search**, such as code
breaking. In this case, keys are candidate solutions to
the problem (such as cryptographic keys); Chord maps
these keys to the machines responsible for testing them
as solutions

* chord 的使用流程圖:

## CHORD PROTOCOL

### 演算法的概述
* chord 會將所有 node 利用 hash function(SHA-1) hash 成一個 $m$ bits 的整數，並將整個解空間視為是環狀相連的，整體結構大概如下圖，在圖中 $m=6$ 。

* 一般 consistent hash 的做法是將 key 經過 hash 之後，將其稱為 $k$ ，$k$ 就存儲在第一個大於等於其值的 node 上，例如 Fig. 2中 $k = 30$ 就會存在 N32 上。然後每個node存取其的sucessor(下一個node)，每次 query 目前 node 是否包含該 key，如果包含就回傳當前 node 的address，如果不包含就將 request pass 給 sucessor 處理。

* 顯而易見的，這個方法 query 的 worst case 是 $O(N)$，N 是 node 總數, K 是 key 的總數，且每個 node 平均需要 maintain $O(K/N)$ 筆 record，刪除或新增 node 時所要搬運的 record 也需要 $O(K/N)$ 筆。

* 因為上述的缺點，chord 使用的方式是在每個 node 上維護一個叫 finger table 的東西，finger table 內包含當前節點 $N$ 加上 $2^i, \quad i \in[0, m-1]$ hash 到哪個 node 的資訊，下圖(a)是一個範例。

* 新的搜尋演算法如下:
簡單來說就是利用 finger table 可以快速找到最接近目標點的 node，而不需要像上面的方法一樣只能像 linked list 只能前往下一個 node。總體 query 的複雜度是 $O(logN)$。

### 實作細節


* 因為最終的程式是要 run 在 P2P 的某個 node 上，而不是某一個 master node，所以程式需要以單個 node 的 respect 去做設計。
* 流程:
* 程式會先 query 當前是否存在一個 chord 網路，如果有就使用 join 將自己加入該 chord 網路中，如果沒有就自己 create 一個新的 chord 網路。
* 每個 node 會週期性的 call 三個 method，stabilize、fix_fingers、check_predecessor。
* stabilize 用來 maintain 該 node 的 successor 關係。
* fix_fingers 用來維護該 node 的 finger_table，維護的方式是定期 query finger_table 對應的元素 node 編號。
* check_predecessor 用來確認自己的 predecessor 是否死掉。

### Failure and Replication

* 為了處理 node failure 導致 query 有可能會回傳錯誤結果的問題，chord 提供了一個解法是 maintain 多個 successor。
* 原本的作法是每一個 node 只維護一個 successor，修改過後的作法改成維護 $r=\Omega(logN)$ 個 successor，當第一個 successor fail 時可以改 query 第二個 successor。

### Adversarial Attack

* 如果有某些 malicious user 想要將大量資料都存在同一個 node 上，造成整個系統 performance 降低的話，chord 是可以抵禦這樣的攻擊的。
* 因為 chord 會將存入的 data 做 hash 才作為該 data 的編號，而不是使用 data 本身作為 data 的編號，而 hash function 本身就保證了 randomness，hash function 會將資料平均的分散在每個 bucket(node) 中，所以可以避免掉這個攻擊。

### Voluntary Node Departures

* 對於某些 node 是自願離開而不是 failure 的，可以做一些優化讓系統的 performance 變好。
* 要離開的 node 通知其的 successor 與 predecessor 分別修改他們的 predecessor 與 successor 成正確的內容。這樣會比將自願離開的 node 當成 failure node 的作法好上許多。

## SIMULATION RESULTS

* 這個部分使用機率去證明 chord 的效能與建構實際系統並實驗其效能。

## FUTURE WORK

## CONCLUSION

* chord 將搜尋 P2P 系統上的資料存放位置的時間從 $O(N)$ 降低到 $O(logN)$，且每個 node 上只需要存放 $O(logN)$ 的資料。
* 且 chord 這個演算法可以 maintain 到 node 的新增與刪除，不像部分演算法無法處理這部分的 case。