读这篇文章源自于一致性哈希的开山之作：Consistent hashing and random trees: Distributed caching protocol for relieving hot spots on World Wide Web。在STOC 上下了原文后觉得估计得花和The part-time parliament 差不多时间来读吧，以后有必要深入学习再看吧！一致性哈希Web 缓存是与开山之作同一作者David Karger 1999年所写 。

STOC 会议上有许多经典的算法，但很多有晦涩难看懂没有引起大家的注意，直到某个采用了该算法的应用得到大家的认可，该算法才得以为大家所接受。分布式一致性Paxos 算法也是这样。（下面左图是consistent hash 开山作引用情况，右边是The part-time parliament 每年引用量，可见在这些牛文在引用量巅峰期之前都有几年的沉寂期，来自CiteSeerX）

言归正传：

problem

congested network and swmaped servers 集中式缓存存在问题

related work

cooperating cache 将缓存复制到不同的机器，存在数据复制和副本一致性问题

hashing 缓存通过哈希保存到不同机器上，存在扩展性以及churn 问题：当一个节点失效或新增一个节点会导致大量失效和缓存的迁移，比如 7×i+4 mod 24 到 7×i+4 mod 23

our work

浏览器上添加哈希函数，将URL 资源定向到动态变化的可用缓存，无副本且减少失效率

consistent hashing

假设有n 个缓存节点，根据其哈希结果使用二叉树进行组织

our system

组成：1.actual cache system  2.user’ browsers   3.domain name server

浏览器对URL 进行哈希得到虚拟地址，返回给DNS 服务器

DNS 服务器通过客户端的虚拟地址查到到对应的缓存节点物理地址IP

缓存节点从原始Web 服务器取数据并保存一份副本，可相应浏览器请求