Web caching with consistent hashing 一致性哈希Web 缓存

读这篇文章源自于一致性哈希的开山之作: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)

conshashing  paxos

言归正传:

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 服务器取数据并保存一份副本,可相应浏览器请求