P2P系统
作为传统的客户端–服务器模式的另外一种可替代方式，P2P（peer-to-peer）架构提供了一种可行的方案，P2P系统中的很多技术都已经在数据中心中得到了成功应用。P2P系统的主要目标是在数百万并发用户的情况下，确保数十亿对象的可用性，如音乐文件。为了实现上述目标，必须在物理网络之上构建一层虚拟的或逻辑的覆盖（overlay）网络。抽象地讲，覆盖构建了不同站点之间的相互通信方式以及数据存储方式。最简单的形式是一个对象可以看成是一个键–值对。覆盖提供了对象检索方法，并支持两种基本操作：给定一个键和值，可以把键–值元组插入（insert）到覆盖中，同时，给定一个键值，可以查询（lookup）并返回对应的值。覆盖一般可以表示成图的形式，以站点为节点，用边来连接不同的站点，可以分为结构化覆盖和非结构化覆盖。
非结构化覆盖没有在节点间的逻辑图上增加任何特定的结构。集中式方案是这种P2P设计的最简单实现，最早由Napster[Carlsson and Gustavsson, 2001]加以应用，Napster方案用一个中央服务器来存储所有的键值和用来标识这些键值所在网络节点的数据库。每次键–值元组的查找都需要访问中央服务器。Napster于1999年发布，最高同时150万用户在线，2001年7月由于法律问题关闭。
除此之外，Gnutella（http://en.wikipedia.org/wiki/Gnutella）使用了分布式设计，每个节点都有若干个邻居，并且在本地数据库中存储若干个键。当需要查找键k时，某个站点首先检查自己的本地数据库，判断k是否在本地。如果在本地，则直接返回相应的值，否则，该站点递归地询问邻居站点。通常情况下，需要使用一个限制阈值来限定消息的无限制传播。
另外一方面，结构化覆盖在不同的节点上强加了具有良好定义的数据结构。这种数据结构一般称作分布式哈希表（Distributed Hash Table, DHT），DHT可以将对象映射到不同的站点，并且，给定相应的键，DHT可以快速检索相应的数据对象。特别是，在结构化覆盖中，边是按照特定的规则选择的，数据被存储在预先确定的站点上。通常情况下，每一个站点负责维护一个表，该表存储了用于查找操作的下一跳（next-hop）。我们将用一种非常流行的称为Chord[Stoica et al., 2001]的P2P系统来对结构化覆盖进行举例说明。在Chord中，每一个节点都使用一致性哈希函数（如SHA-1）进行哈希，哈希到一个m位的标识符空间中（2m个ID），其中，m一般取160。所有的站点依据各自的ID号被组织成一个逻辑环。键也被哈希到相同的标识符空间中，键（及其相应的值）存储在后继节点中，即下一个具有较大ID的节点。
一致性哈希可以确保：对任何n个节点和k个键的集合，一个节点最多负责个(1+∈)k/n键。另外，当一个新的节点加入或离开时，O(k/n)个键需要移动。为了支持高效和可扩展的查询，系统中的每一个节点都需要维护一个查询表（finger table）。节点n的查询表的第i个元素是第一个后继节点或者等于n+2i。图2-8展示了针对不同的网络规模，一个给定节点的路由表中的指针。换句话说，第i个指针沿着环指向1/2(m–i)方向。当接收到一个针对id项的查询时，节点首先检查是否存储在本地。如果不在本地，则将该查询往前发送给其查询表中最大的节点。假设Chord环中的节点呈正态分布，每一步中搜索空间的节点数量减半。因此，查询跳数的期望值是O(logn)，其中，n是Chord环中节点的数量。
