Consistent_Hashing_and_Random_Trees翻译
本文会挑拣该论文的部分章节进行翻译，旨在理解一致性hash的背景由来和原理。在此感谢百度翻译让翻译工作如此简单
一致性Hash和随机树：一种用于缓解网络热点的分布式缓存协议
摘要
我们描述了一系列适用于分布式网络的缓存协议，这些协议可以用来减少或消除网络中热点的出现。我们的协议特别适用于大型网络，如Internet。因为大型网络中热点造成的延迟可能非常严重，并且不可能每个服务器都拥有有关整个网络当前状态的完整信息。本协议很容易使用现有的网络协议（如TCP/IP）实现，并且只需要很少的开销。本协议与局部控制（local control，局部控制是指cache结点可以自主处理请求，无需协调其他结点参与处理，可以理解为是无中心结构优势的一种体现）结合高效地利用现有资源，并随着网络的增长而平滑扩容。
我们的缓存协议基于一种特殊的哈希，我们称之为一致哈希。粗略地说，一致性哈希函数是一个随函数范围变化而变化最小的函数。通过开发良好的一致性哈希函数，我们能够开发缓存协议，而不需要用户对网络具有当前甚至一致的视图。我们相信，一致的散列函数最终可能被证明在其他应用程序中有用，例如分布式NameServer或仲裁系统。
1. 介绍
在本文中，我们描述了分布式网络的缓存协议，可以用来减少或消除“热点”的发生。当大量客户端希望同时从单个服务器访问数据时，热点随时都会出现。如果服务器没有能力同时处理所有这些客户端的请求，那么将会导致服务降级或不可用。
我们大都经历过网络环境下的热点现象。一个Web站点可能突然变热，导致其在短时间内接收到远超其处理能力的请求数。事实上，一个站点在收到洪峰的请求时，往往会导致它服务不可用。另外，这些大量流量也会阻塞其附近的网络，干扰附近站点的流量。随着网络使用的增加，热点的发生和影响也随之增加。最近网络热点的著名例子包括苏梅克-列维9号彗星与木星的碰撞的JPL网站、IBM在Deep Blue-Kasparov国际象棋巡回赛期间的网站，以及选举当晚的几个政治网站。在其中一些情况下，一个网站长达数小时甚至数天拒绝用户访问。其他例子包括被识别为“每日网站”的网站和提供流行软件新版本的网站。
我们的工作最初是由万维网上的热点问题推动的。我们相信我们开发的工具也会与大部分的Client-Server架构模型相关，因为Internet上的集中式服务器（如域名服务器、多播服务器和内容标签服务器）也容易受到热点的影响。
1.1 过去的成果
当前已经有人提出了几种克服热点的方法。大多数应用程序使用某种复制策略在整个Internet上存储热页的副本；这把为热页提供服务的工作分散到多个服务器上。在一种已经广泛使用的方法中，多个客户机共享一个代理缓存。所有的用户请求都通过代理进行转发，代理试图保留频繁请求的页面的副本。它尝试使用缓存副本来满足请求；如果失败，它会将请求转发到主服务器。这种方案的困境在于，如果有更多的用户共享同一个缓存，那么会有更多的好处，但是缓存本身很容易被淹没（被某种缓存算法清理，如LRU，LFU）。
Malpani等人通过将一组缓存作为一个整体来解决这个问题。用户对页面的请求被定向到任意缓存。如果页面存储在那里，它将返回给用户。否则，缓存会通过一个称为“IP多播”的特殊协议将请求转发给所有其他缓存。如果页面没有缓存，请求将转发到页面的主页。这种技术的缺点是，随着参与缓存的数量的增加，即使使用多播，缓存之间的消息数量也会变得不可管理。我们在本文中开发的一个工具，一致性哈希，提供了一种实现这种分布式缓存的方法，而不需要缓存一直通信。我们将在第4节中讨论这一点。
Chankhunthod等人开发了Harvest缓存，这是一种使用缓存树的更具可伸缩性的方法。用户通过询问附近的叶缓存来获取页面。如果此缓存及其同级都没有该页，则请求将转发到缓存的父级。如果树中没有缓存存储页面，则请求最终到达根目录并转发到页面的主页。缓存会把它获得的任何页面的副本都保留一段时间。缓存树的优点是缓存仅从其子级（和同级）接收页请求，从而确保不会有太多的请求同时到达。因此，短时间内对一个页面的多个请求只会导致一个请求打到该页面的主服务器，且不会使缓存过载。在理论上，至少有一个缺点是所有页都使用同一棵树，这意味着根目录对整个缓存树中请求的每个不同页至少接收一个请求。如果不同页面请求的数量增长过大，这可能会淹没根目录，这意味着此方案还存在潜在的扩展问题。
Plaxton和Rajaraman展示了如何通过使用随机化和散列来平衡所有缓存之间的负载。特别是，它们为每个页面使用一个由越来越大的“虚拟缓存站点”组成的层次结构，并使用随机哈希函数将每个虚拟站点的责任分配给网络中的实际缓存。客户端向层次结构中每个集合中的随机元素发送请求。集群接收分配给他的缓存页，但当其发现自身负载过重时，会将页复制到下一个较大集群的某些成员。这样即使对于热点页面也能给出快速响应，因为缓存该页面的最大集群不会过载。它还提供了良好的负载平衡，因为加载某个页面的小集群很可能隶属于加载另一个页面的大集群。Plaxton和Rajaraman的技术也是容错的。
然而，Plaxton/Rajaraman算法有缺点。例如，由于他们的算法将每个页面请求的一个副本发送给每个集合中的一个随机元素，因此热点页面的小集合肯定会被淹没。事实上，该算法将缓存丢失作为一种特性，因为缓存丢失用于触发复制。这在他们的同步并行系统模型中运行得很好，在同步并行系统模型中，假定一个被淹没的缓存结点只处理接收到的部分输入消息，其他消息仍按正常方式进行处理。然而，在互联网上，缓存丢失的后果要严重得多。甚至不能依靠被淹没的机器迅速恢复。此外，大量随机机器的有意涌入很可能会被这些机器的所有者视为不利因素。Plaxton/Rajaraman算法还要求所有通信都是同步的或messages具有优先级，并且可用的缓存集是固定的，并且所有用户都知道。
1.2 我们的贡献
在这里，我们描述了两种数据复制工具，并使用它们给出了一种缓存算法，该算法克服了预放弃方法的缺点，并且具有一些额外的、理想的属性。
我们的第一个工具，随机缓存树，结合了Chankhunthod等人和Plaxton/Rajaraman使用的结构的各个方面。像Chankhunthod等人一样，我们使用缓存树来合并请求。与Plaxton和Rajaraman一样，我们通过为每个页面使用不同的树并通过随机哈希函数将树节点分配给缓存来平衡负载。通过将Chankhunthod等人和Plaxton/Rajaraman的最佳特性与我们自己的方法相结合，我们可以防止任何服务器被高概率淹没，这是Chankhunthod等人或Plaxton/Rajaraman都不具备的特性。此外，我们的协议还展示了如何通过只缓存请求了足够次数的页面来最小化内存需求（而不显著增加缓存未命中率）。
我们认为缓存树所引入的额外延迟在实践中应该非常小。请求页面的时间会随树的深度而倍增。但是，页面请求通常占用的时间很少，因此额外的延迟不是很大。页的返回可以通过管道进行；缓存不需要等到它接收到整个页之后才将数据发送到树中的子页。因此，返回一个页面也只需要稍微长一点。总之，用户看到的附加延迟很小。
我们的第二个工具是一个新的哈希方案，我们称之为一致的散列。这种散列方案与Plaxton/Rajaraman和其他实际系统中使用的散列方案有很大不同。典型的基于散列的方案可以很好地通过已知的固定服务器集合分散负载。然而，互联网并没有固定的机器集合。取而代之的是，机器会因崩溃或进入网络而进出集群。更糟糕的是，关于哪些机器起作用的信息在网络中传播得很慢，因此客户机可能对哪些机器可以复制数据有不兼容的“视图”。这使得标准散列变得毫无用处，因为它依赖于客户机约定哪些缓存负责为特定页面提供服务。例如，Feeley等人为工作站网络实现了一个分布式全局共享内存系统，该系统使用分布在机器之间的哈希表来解析引用。每次一台新机器加入网络时，都需要一个中央服务器将一个完全更新的哈希表重新分发给所有机器。
一致性哈希可能有助于解决此类问题。像大多数散列方案一样，一致性散列将一组项目分配给buckets，这样每个bin接收的项目数大致相同。与标准散列方案不同，bucket集合中的一个小更改不会导致Key到bucket的完全重新映射。此外，将项目散列到稍微不同的bucket集合中，只会为bucket分配稍微不同的项目。我们将一致性哈希应用到我们的缓存树方案中，并展示了即使每个客户机只知道所有缓存机器中的一小部分，该方案如何工作良好。Litwin等人提出的一种哈希函数，允许按顺序一次添加一个桶。但是，我们的哈希函数允许按任意顺序添加bucket。另一个我们可以改进的方案是Devine[2]。此外，我们认为，一致性哈希在其他应用程序（如仲裁系统或分布式名称服务器）中也很有用，在这些应用程序中，具有不同网络视图的多台计算机必须在没有通信的情况下为一个对象商定一个公共存储位置。
1.3 章节简述
在第2节中，我们描述了我们的Web模型和热点问题。我们的模型必然过于简单化，但足够丰富，可以开发和分析我们认为在实践中可能有用的协议。在第3节中，我们描述了我们的随机树方法，并将其用于缓存协议中，该协议在简化模型下有效地消除了热点。独立于第3节，在第4节中，我们介绍了我们的一致散列方法，并使用它来解决不同简化模型下涉及不一致视图的热点问题。
在第5节中，我们将展示如何将这两种技术有效地结合起来。在第6节中，我们提出了一个简单的延迟模型，该模型描述了互联网上机器的分层集群。我们表明，我们的协议可以很容易地扩展到工作在这个更真实的延迟模型。在第7节和第8节中，我们分别考虑了故障和协议随时间的行为。在第9节中，我们讨论了一些扩展和开放问题。
1.4 关于随机化和散列的一点注记
在一些地方，我们使用散列函数将对象映射到一个范围。为清楚起见，我们假设这些函数以真正随机的方式映射对象，即一致和独立地映射对象。实际上，具有有限独立性的哈希函数更容易实现，因为它们节省了空间和随机性。我们用类似于文献[11]的方法证明了本文的所有定理，它们只具有有限的独立性。然而，在这个扩展的摘要中，我们只说明了结果所需的独立程度。假设独立性有限的证明将出现在本文的完整版本中。
4. 一致性Hash
在本节中，我们将定义一种新的哈希技术，称为一致哈希。我们通过参考一个简单的互联网数据复制方案来促生这项技术。考虑一个服务器，它有大量其他客户端可能要访问的对象。在客户机和服务器之间引入一层缓存以减少服务器上的负载是很自然的。在这种方案中，对象应该分布在各个缓存中，这样每个缓存负责大致相等的份额。此外，客户机需要知道要为特定对象查询哪个缓存。最明显的方法是散列。服务器可以使用散列函数将对象均匀分布在缓存中。客户机可以使用哈希函数来发现哪个缓存存储对象。现在考虑一下，当一组活动缓存机器发生变化时，或者当每个客户机都知道一组不同的缓存时，会发生什么（这种情况在互联网上是非常合理的）。如果分布是用一个经典的散列函数（例如，线性同余函数x -> ax + b (mod p) ）完成的，这种一致性将是灾难性的。当hash函数的范围（例子中的p）发生变化，几乎所有的项都需要rehash到新的位置。这导致突然之间所有缓存的数据都失效了，因为客户机正在另一个位置查找它。
一致性哈希解决了不同“视图”的问题。我们将视图定义为特定客户机知道的缓存集。我们假设，虽然视图可能不一致，但它们是实质性的：每台机器都知道当前正在运行的缓存中有一个恒定的部分。客户机使用一致的哈希函数将对象映射到其视图中的一个缓存。我们分析并构造具有以下一致性属性的哈希函数。首先，有一个“平滑”属性。当一台机器被添加到缓存集或从缓存集中删除时，必须移动到新缓存的对象的预期比例是保持缓存间负载平衡所需的最小值。其次，在所有客户机视图中，一个对象很少会被分配到多个缓存，我们称之为“s pread”。类似地，在所有客户机视图中，一个缓存也很少接受差异较大的不同对象，我们称这个属性为“load”。
因此，一致散列解决了上面讨论的问题。“spread”属性意味着即使存在不一致的全局视图，对给定对象的引用也只指向少数缓存机器。将一个对象分发到这个小的缓存集将确保所有客户机都可以访问，而不需要使用大量的存储。“load”属性意味着没有一个缓存被分配不合理数量的对象。“平滑度”属性意味着缓存机器集的平滑变化与缓存对象位置的平滑演变相匹配。
由于有许多方法可以将上述一致性概念形式化，因此我们将不对其进行精确定义。相反，在第4.4节中，我们定义了一个“范围散列函数”，然后精确地定义了几个捕获不同“一致性”方面的量。在第4.2节中，我们构造了实际的哈希函数，在一定程度上展示了这四个函数。在第4.4节中，我们讨论了一致性哈希的其他方面，尽管与本文不同，但这表明了该理论背后的一些丰富性。
4.1 定义
// TODO