# 6-4. Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web

## Introduction

* 這篇論文想要解決的是分散式系統中的熱點問題(hot spot)，因此想出一個叫 DHT(Distributed Hash Table) 的東西來解決它。
* hot spot:
* 在分散式系統中，當多個 client 同時被導向同一個 server，而不是平均分散到其他 server 去處理 request，那該 server 就被稱為 hot spot。
* hot spot 會導致系統的效能沒有得到妥善的運用，且造成 user 等待的 latency 顯著的提高。
* 提出一種方法是將資料平均 hash 到某個 bucket(server)，這樣就可以避免 hot spot 的問題。
* 但傳統的 hash function 例如下列公式在分散式系統是行不通的，因為 N (server 數量) 時常會變動，只要 N 一變動所有的 data 都需要做 remap。
* $$\ hash(data)\ mod\ N$$

## Model

* Objective:
* 基本: 避免同一台伺服器被大量的 request 淹沒。
* 額外: 讓每台 server 使用的盡可能小的 memory，並且讓 request 的latency 盡可能的低。

## Consistent hashing

### Definition

> 作者从四个方面讨论了好的 Consistent Hash Function 应该满足的性质：
> * Balance：元素应当尽量均匀地分布到不同的桶内 (with high probability)
> * Monotonicity：当增加新的桶时，元素只可能从旧桶移动到新桶，而不可能从旧桶移动到其它旧桶
> * Spread：在不同的用户眼里，相同的元素可能被散列到不同的桶中，我们称之为不同的观点。Spread 要求总的观点数量必须有一个上限。好的 Consistent Hash Function 应当让 spread 尽量小。
> * Load：类似 spread，Load 性质是针对不同的用户，但它规定的是单个桶中不同元素数量的上限，即每个桶中的，至少有一个用户认为其中含有的，元素数量存在上限。好的 Consitent Hash Function 应当让这个上限尽量小。

### Construction

> 作者提出一种构建好的 Consistent Hash Function 的方法：
> 假设我们有两个随机的函数 $\gamma_B, \gamma_I$，
> $\gamma_B$ 将 buckets 映射到区间 $[0,1]$
> $\gamma_I$ 将 items 映射到区间 $[0,1]$ 上
> 那么一个好的 Consistent Hash Function 可以定义为
$$f_V(i) = min(|\gamma_B(b)-\gamma_I(i)|)$$
> 即将 item 放在距离它最近的 bucket 中。这里的 V 代表着不同的观点，由于观点数量会随着 buckets 的增减而增加，每个观点的内容会随着 buckets 的增减而变化，因此这个 Consistent Hash Function 并不是一个静态的、固定的函数。
> 这里还有一点，$\gamma_B$ 通常需要将每个 bucket 映射到 $[0, 1]$ 区间的多个点上。假设整个区间上的 bucket 数量上限为 $C$ ，那么 $\gamma_B$ 需要将每个 bucket 映射到 $klogC$ 个点上，其中 $k$ 为常数，且 $\gamma_B$ 在映射单个 bucket 的不同点时，是相互独立的。
* 上面這個 function 代表的意思是將 data hash 後存放在最接近的 server 的意義，只是 data 與 server 都將會被 hash 到區間 $[0, 1]$ 上。

### Implementation

> 实现思路
> 材料：哈希函数： $H(x)：string→[0,max]$

> 方案：将每个节点哈希到区间 $[0,max]$ 上随机的 $k$ 个点，将所有节点的所有哈希值排序后保存在一个数组 $A$ 中。每次新来一个请求，就将请求的 ID 哈希到区间 $[0, max]$ 上的某个点，然后利用二分查找找到比 $k$ 大的最小点，后者对应的节点就是目标实例。

> 算法复杂度分析：

> | 操作 | 时间复杂度 |
> | -------- | -------- |
> | AddNode | $O(klog(n))$ |
> | DelNode | $O(klog(n))$ |
> | Get | $O(logkn)$ |

## Conclusion

* DHT 可以成為一個很好的 load balance 的機制，適合用在 DNS 或 label server 上。
* 關於 DHT 的概念可以參考 [DHT](https://ithelp.ithome.com.tw/articles/10226170)。

## Reference

* [論文導讀](https://zhenghe.gitbook.io/open-courses/papers-we-love/consistent-hashing-and-random-trees-1997)
* [DHT 概念](https://ithelp.ithome.com.tw/articles/10226170)