一致性哈希的 first paper (maybe) 阅读笔记。

论文地址

1. Whydunit

当大量的客户端同时对单个服务器发起请求时，可能会使该服务器(Hot spots) “swamped” （无法使用）。除此之外，还可能会阻塞该服务附近的网络通信。所以我们需要一个负载均衡算法来有效地避免 Hot spots 的出现。

2. Whodunit

2.1. Proxy cache

使用 proxy 缓存经常被请求的数据，多个客户端共享一个 proxy cache。

  1. 所有用户的请求都发往 proxy
  2. 未命中时，proxy 会把该请求转发至 home server。

缺点：proxy 本身可能会 swamped

2.2. A group of caches functions as one

  1. 用户的请求发往任意一个 cache
  2. 未命中时，使用 IP Multicast 将该请求转发至所有其他的 cache
  3. 未命中时，将该请求转发至 heme server

缺点：cache 之间的通信消息数量不可控

2.3. Harvest Cache

使用树型结构的 cache，root 为 home server

  1. 用户的请求发往邻近的叶节点
  2. 未命中时，将该请求转发至兄弟节点(siblings)
  3. 未命中时，将该请求转发至父节点(parent)

优点：保证了请求只会来自于子节点或兄弟节点

缺点：当所有不同请求同时到来时，至少会有一个请求会到达 root，因此这只是一个缩放的结构，root 无法避免 swamped 的命运

2.4. Using randomization and hashing

Plaxton and Rajaraman

新增一组 virtual cache 集合层，通过 random hash function 在现有的 Caches 和 virtual cache 集合之间建立映射，用户的请求发往任一 virtual cache 集合。如果 virtual cache 集合的负载超过阈值，则创建一个更大的 virtual cache 集合。

优点：请求响应快，因为每个 cache 的负载都在可控范围；负载均衡。

缺点：由于用户的请求发往任一 virtual cache 集合，故小规模的 virtual cache 集合可能会 swamped。

2.5. Random cache trees

下次一定看！

2.6. Consistent hashing

传统 hashing 的局限：

  • 假定节点数是固定的
  • 每个节点需要知道全局信息，使用消息进行同步时，由于延时的存在，节点所保存的全局信息正确性无法保证

Consistent hashing 如何解决这两个问题，将于下文详述。

3. Howdunit

3.1. 符号说明

  • $\mathcal{I}$: set of items，数据
  • $i$: is an item
  • $\mathcal{B}$: set of buckets，类似于 proxy chche
  • $b$: is a bucket
  • view: any subset of the buckets $\mathcal{B}$，模拟节点的增加与删除
  • ranged hash function $f$: $2^{\mathcal{B}} \times \mathcal{I} \rightarrowtail \mathcal{B}$
    • $f(\mathcal{V}, i)$ or $f_{\mathcal{V}}(i)$ is the bucket to which item $i$ is assigned in view $\mathcal{V}$
    • Require: $f_{\mathcal{V}}(\mathcal{I}) \subseteq \mathcal{V}$ for every view $\mathcal{V}$
  • ranged hash family $\mathcal{F}$: is a family of ranged hash functions
  • random ranged hash function: is a function drawn at random from a particular ranged hash family

3.2. 一致性哈希函数应满足的性质介绍

  1. Balance

    A ranged hash family is balanced if, given a particular view $\mathcal{V}$, a set of items,and a randomly chosen function selected from the hash family, with high probability the fraction of items mapped to each bucket is $O(1/|V|)$.

  2. Monotonicity

    • A ranged hash function $f$ is monotone if for all views $\mathcal{V}_1 \subseteq \mathcal{V}2 \subseteq \mathcal{B}, f{\mathcal{V}_2}(i) \in \mathcal{V}1$ implies $f{\mathcal{V}1}(i) = f{\mathcal{V}_2}(i)$.
    • A ranged hash family is monotone if every ranged hash function in it is.

    单调性保证了：如果新增了一个节点，只会有将之前的数据迁移到新节点的操作，而不会有旧节点之间互相迁移的操作。

  3. Spread

    Let $\mathcal{V}1 \dots \mathcal{V}{|V|}$ be a set of views, altogether containing $C$ distinct buckets and each individually containing at least $C/t$ buckets.

    • For a ranged hash function and a particular item $i$, the spread $\sigma(i)$ = $|\{f_{\mathcal{V}_j}(i)\}^{|V|}_{j=1}|$.
    • The spread of a hash function $\sigma(f)$ is the maximum spread of an item.
    • The spread of a hash family is $\sigma$ if with high probability, the spread of a random hash function from the family is $\sigma$.

    Spread 大致意思是指，一个 item 在不同的 view 下会被分配到的 bucket 所组成集合的大小，其越小说明在节点数量发生变化时，需要做的数据迁移操作越少。

  4. Load

    Define a set of $|V|$ views as before.

    • For a ranged hash function $f$ and bucket $b$, the load $\lambda(b) = |\cup_{\mathcal{V}}f^{-1}_{\mathcal{V}}(b)|$. (Note that $f^{-1}_{\mathcal{V}}(b)$) is the set of items assigned to bucket $b$ in view $\mathcal{V}$)
    • The load of a hash function $\lambda(f)$ is the maximum load of a bucket.
    • The load of a hash family is $\lambda$ if with high probability, a randomly chosen hash function has load $\lambda$.

    Load 大致意思是指， 一个 bucket 在不同的 view 下所包含的 items 集合的并集的大小，其具有上界保证了在不同的节点总数情况下，不会出现单个节点需要储存过多的数据的现象。

3.3. 构造一致性哈希函数

//TODO