ふわふわ時間

0%

# Whodunit

## Proxy cache

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

## A group of caches functions as one

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

## Harvest Cache

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

## Using randomization and hashing

Plaxton and Rajaraman

## Consistent hashing

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

# Howdunit

## 符号说明

• $\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

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

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 集合的并集的大小，其具有上界保证了在不同的节点总数情况下，不会出现单个节点需要储存过多的数据的现象。