可扩展的内容寻址网络
概要
哈希表它映射键到职- 在现代的网络系统中是一个必要的构建块。我们相信类似的功能对于大规模的分布式系统有着相同的价值。在这篇论文中，我们介绍了内容寻址网络（CAN）作为一个分布式基建，类似哈希表的功能在类似互联网的规模。CAN是可扩展的，容错和完全自组织的。我们通过模拟演示了它的可扩展性，健壮性和低延迟特性。
1 介绍
一个哈希表是一个数据结构它有效的映射了键到值，并且作为核心构建块在软件系统的实现中提供服务。我们认为许多大规模的分布式系统同样可以在哈希表功能中收益。我们使用名词内容寻址网络（CAN）来表述这样的分布式网络扩展哈希表。
可能是当前网络系统最好的例子是p2p文件系统比如Napster和Gnutella。在这些系统中，文件存储在终端用户机器上（对等）而不是中心服务，和传统的模型不同，文件直接在对等节点之间传输。这个p2p系统已经变得很受欢迎。Napster于1999年年中推出，到2000年12月，软件已经被5000万个用户下载让他变成了网络上发展最快的程序。新的文件共享系统比如Scour，FreeNet，Ohaha，Jungle Monkey和Mojonation也在之后去年被提出。
尽管对这些共享文件系统的商业潜力仍然有一定的怀疑，我们认为快速和广泛的部署表明他们对p2p系统具有重要的优势。p2p设计使用了大量的资源 - 据观察，通过Napster发布的内容在一天超过了7TB空间，而不需要集中的计划或者巨额投资在硬件贷款或者机架的空间。因此点对点文件系统共享可能会为应用程序带来新的内容分发模型，比如软件分布，文件共享和静态网络内容交付。
不幸的是大部分当前的p2p设计是不可扩展的。例如在自然的中心服务存储所有文件的可用索引于Napster用户社区内。为了检索文件，用户使用目标文件的已知名字和获得的用户机器存储需要文件的ip地址来进行查询。文件直接被从用户机器进行下载。因此，尽管Napster使用点对点通信模型进行实际的文件传输，但定位文件的过程仍然非常集中。这同时是昂贵的（扩展中心目录）vulnerable（因为这是一个故障单点）。Gnutella进一步，去中心化了文件的定位过程。Gnutella网络中的用户自组织到一个应用程序级网格中，在这个网格上，对文件的请求被泛洪在一定范围内。对每个请求进行泛红是不可扩展的，因为泛洪限制了一些点，可能无法找到系统中实际的内容。我们从这个问题开始调查：是否可以创建一个可扩展的点对点文件分发系统？我们很快认识到，中心化的系统是使用映射文件名的方式来在系统中定位的。也就是说，p2p文件传输过程本质上是可扩展的，但是困难的部分是找到从谁那里检索文件的对等体。因此一个可扩展的p2p系统需求，只少是一个可伸缩的索引机制。我们叫这个索引系统内容寻址网络，在论文中提出了CAN的设计。
然而CAN的应用不被p2p系统所限制。CAN也可以被用在大规模的存储管理系统中比如OceanStore [10], Farsite [1], Publius [13].这些系统都需要搞笑的插入和检索在大规模分布式存储基建中的内容；一个扩展的索引机制是这个基建的基本机制。事实上，正如我们在第5节中讨论的那样，OceanStore系统已经在其核心设计中包含了CAN（虽然基于Plaxton算法[15]的OceanStore CAN与我们在这里提出的略有不同）
另一个对于CAN来说潜在的应用是构建广泛的命名服务（不像DNS）将任意方案与名称解析过程解耦，从而支持任意的、与位置无关的命名方案。
我们对can的兴趣是基于这样一种信念：一种类似哈希表的抽象将为互联网系统开发人员提供一种强大的设计工具，使新的应用程序和通信模型成为可能。然而这篇论文中我们的重点不是CAN的使用而是它的设计。在[17]中我们描述了一些细节，一个可能的应用，我们称之为grass-roots内容分发系统，它利用了我们的CAN工作。
如我们说的，CAN类似于哈希表；在CAN上执行的基础操作是插入，查询和删除（key，value）对。在我们的设计中，CAN是许多独立节点组成的。每个CAN节点存储整个哈希表的存储块（被叫做zone）。对特定key的请求（插入查询或删除）被路由到中间CAN节点并转发到维护这个key的CAN节点。我们的CAN设计是完全分布式的（它包括没有中性化控制和配置协调的形式），可扩展的（节点只维护控制状态的小部分，而无关系统中节点的数量），和容错（节点可以绕过故障节点进行路由。不像DNS或者IP路由，我们的设计），不像DNS或者IP路由系统我们的设计没有加强任何形式的命名结构来实现可扩展性。最后我们的设计可以完全在应用级别实现。
如下我们在第二章描述了CAN的基础设计，在第3节中更详细地描述和评估该设计，并在第4节中讨论我们的结果。我们讨论了相关工作在第5节和第6节的未来工作方向。
2 设计
首先我们使用基础的形式描述我们的内容寻址网络。在第三章我们提出了额外的设计特性它提升了性能和鲁棒性。
我们的设计中心围绕着虚拟的d维的笛卡尔坐标空间在一个d环面。这个坐标系是完全逻辑的域任何物理坐标没有关系。在任何时间点，整个坐标空间在系统中的所有节点之间动态划分，让每个节点在整体空间中有个人的独特的区域。例如图1展示了2五个CAN节点中的个维度的[0,1] x [0,1]坐标空间。
虚拟坐标空间使用键值对存储如下：为了存储对（K1，V1）键K1使用均匀哈希函数确定映射。为了检索K1对应的条目，任何节点可以使用相同的确定的哈希函数来映射K1到定点P，并且它们从点P检索响应的值。如果点P不属于请求节点或者它的近邻，请求必须通过CAN基础结构路由，直到到达点P所在的区域 。
数据是在覆盖网络中字字珠的，它代表着虚拟坐标空间。节点学习并维护那些与自己相邻坐标区域的节点的IP地址。坐标中这组近邻充当坐标路由表，使该空间之间任意节点的路由成为可能。
我们将描述我们设计的三个部分：CAN路由，CAN坐标覆盖的构建，和维护CAN的覆盖。
2.1 CAN中的路由
直觉上，内容寻址网络中的路由通过从源头到目标的笛卡尔空间沿着直线工作。CAN节点维护一个协调路由表，它持有IP地址和在坐标空间中的直接的邻居的每个虚拟协调区域。在d维坐标空间中，俩个节点是邻居，如果他们的坐标张成空间在d上重叠。例如，在图2中，节点5是节点1的邻居，因为它的坐标区域在Y轴上与1重叠，在x轴上相邻。另一方面节点6不是1的邻居，因为坐标区域在x轴和y轴上。这个纯本地的邻居状态是足够在空间中的任意俩个点之间路由：一个CAN消息包括了目标协调。使用它的它的邻居协调集，通过简单的贪心转发到最近的于目标点的邻居，一个节点路由一个消息朝着它的目标。图2展示了简单的路由路径。
对于一恶搞d维空间分割成n个相等的区域，平均路由长度是$(d/4)(n^{1/d})$跳并且独立的节点维护2d个邻居，我们可以增加节点的数量（也就是区域）而不增加每个节点的状态，其中平均路径长度增长为$O(n^{1/d})$.
记住，许多不同的路径在俩个点，因此一个节点或多个节点的故障，节点会自动沿着下一个最优路径路由。
然而，如果一个节点在某个方向上失去了所有的邻居，修复机制在2.3章中描述，还没有重建空间中的空洞，贪心转发可能会暂时失败。在这个例子中，一个节点可能使用扩展环搜索（使用无状态的，可控制的泛洪CAN覆盖网络）来定位一个比自身近的目标节点。消息然后被转发到最接近的节点，从中恢复贪心转发。
2.2 CAN 构建
如上所述，整个CAN空间被分配给当前空间的现有节点。为了允许CAN逐步增长，一个新的节点加入系统必须指派它在坐标空间中的拥有的一部分。这通过现有的节点对半划分被指派到的区域，留下一般另一半给信的节点。
过程分为三个步骤
- 首先新的节点必须找到已经在CAN中的节点。
- 接下来使用CAN路由机制，它找到一个将要被切分区域的节点，最后，切分区域的邻居必须被通知，这样路由可以被包含在新的节点。
一个新的CAN节点首先发现一些当前在系统中节点的IP地址。CAN的运行不依赖它们完成的细节，但是我们使用相同的启动机制比如YOID[4].
和在YOID一样，我们假设CAN由相关的DNS域名。一个启动节点维护CAN列表的一部分节点，这些节点存活在当前的系统中。[4]中描述了保持该列表合理更新的简单技术。
为了加入CAN，一个新的节点查找CAN在DNS中的域名来检索一个引导节点的IP地址。引导节点然后使用几个在当前系统中随机选择节点的IP地址。
找到一个区域
新的节点然后随机的选择空间中的点P并且发送一个加入请求到点P。这个消息通过已有的CAN节点发送到点P。每个CAN节点然后使用CAN路由机制来转发消息，直到它达到区域P所在的节点。
然后当前节点奖其区域分成俩半，并将其中一般分给新的节点。分裂是通过假设特定的维度顺序来确定沿着哪个维度分裂，因此区域可以在节点离开时重新合并。对于2维空间，第一个切分的维度是X维，然后是Y 以此类推。半个区域键值对也被转发到新的节点。
加入路由
获得了它的区域，新节点得到了之前节点的邻居集合的IP地址。这个集合是之前节点邻居的子集加上那个节点自身。类似的之前的节点更新它的邻居集合以消除不会长期成为邻居的这些节点。最后新的和老的节点邻居必须被告知空间的重新分配。系统中的每个节点发送直接的更新信息，然后定期刷新，然后将它们分配给所有的邻居区域。这个软状态风格的更新确保了它们的邻居能快速了解到更改，并相应地更新它们自身的邻居集。图2和图3展示了新节点（节点7）在俩个维度的CAN中的例子。
新节点的添加只影响坐标空间中非常小的位置上的现有节点。添加新节点仅影响坐标空间非常小的局部中的少量现有节点。节点维护的邻居数量仅取决于坐标空间的维度，与系统中的节点总数无关。因此，节点的插入只会影响O(节点维度)的现存节点，这对大数量的节点是重要的。
2.3 节点的离开恢复和CAN维护
当节点离开CAN，我们需要确保占用的区域被剩余的节点接管。实现这个操作的常规过程是明确的交付它的区域以及相关的键值对数据库给他的邻居。如果邻居的一个区域可以与离开节点的区域合并成一个有效的单区域，那就完成。如果不能，那么将该区域交给当前最小的邻居，然后该节点临时处理这俩个区域。
CAT也需要对于网络和节点故障的健壮，其中一个或多个节点无法访问。这是通过立即接管算法处理的，该算法确保一个故障节点的一个邻居接管该区域。然后在这个例子中，离开节点持有的键值对将会丢失，直到数据的持有者刷新状态。
在常规情况下，一个节点定期的发送更新消息到每个它的邻居节点，还有他邻居节点的区域坐标。如果长期没有收到邻居节点发来的心跳说明邻居节点出现了故障。
一旦一个节点明确了邻居已经死亡，它开始启动接管机制并启动接管计时器。故障节点的每个邻居将独立地执行此操作，并根据节点自身区域的容量比例初始化计时器。当计时器到期时，一个节点发送TAKEOVER消息，将自己的区域卷传递给所有失败节点的邻居。在接收到接管消息时，如果消息中的区域容量小于自己的区域容量，则节点取消自己的计时器。使用这个方法，一个邻居节点有效的选择一个仍然活跃但是体积相对较小的邻居节点。
在涉及多个相邻节点同时失效的场景下，节点故障探测是必要的，但是只有不到一半的故障节点的邻居任可以到达。如果一个节点在这种情况下接管了一个区域，CAN的状态可能不一致。在这个例子中，在出发修复机制之前，节点对非故障区域以外的节点进行扩展环搜索，从而最终重建足够的邻居以安全发起接管。
最终，正常的离开过程和立即接管算法都可能导致一个节点持有多个区域。为了防止空间进一步的碎片化，我们采用了一种背景区域重分配算法，我们在附录A中描述，运行以保证CAN倾向于每个节点返回同一个区域。
3 设计改进
我们在上文描述的基础的CAN算法提供了低的每个节点状态(O(d))对于一个d维度空间以及端路径的长度为$O(dn^{1/d})$跳，在d维空间和n个节点中。这个适用于CAN路径中的跳数。这是一个应用级别的跳数，不是IP级别的跳数，每一条的延迟可能会很大；回想一下CAN中相邻的节点彼此之间可能会有很多长距离的IP跳。查找的总延迟的平均是CAN跳数的平均值乘以每个CAN跳的平均值。我们希望实现与请求者和持有秘钥的CAN节点之间底层路径延迟在很小范围内相当的延迟。
在这一章节中我们描述了一些设计技术，它们主要目标是降低CAN路由的延迟。在路由和数据可用性方面许多这些技术都提供了改进CAN健壮性的额外优势，这并非偶然。简单来说，我们试图减少路径延迟的策略时减少路径长度和每个CAN跳的延迟。我们对基本设计做的最后一个改进是添加简单的负载均衡机制。（在章节3.7中和3.8中描述）
首先，我们分别描述和评估每个设计特性，然后在第4节中讨论它们如何共同影响整体性能。在我们有更丰富的部署经验，并且更好地了解应用程序需求之前，我们不准备决定这些权衡
3.1 多个维度的坐标空间
第一个观察是我们设计不限制坐标空间的维度。增加CAN的坐标维度可以减少路由路径的长度，以及路径延迟对于坐标路由表的大小小幅度增加。
图4衡量了在路由路径长度上增加维度的代价。我们绘制增加坐标空间CAN节点数量随着不同维度的数字增加。对于一个n个节点和d维度的系统，我们看到路径长度随着$O(d(n^{1/d}))$增加，与完全划分坐标空间解析结果一致。
因为增加维度的数量意味着节点有多个邻居，路由容错性也得到了提高，因为节点有更多的潜在的下一跳节点，当一个或多个相邻节点崩溃时，可以沿着这些节点路由消息。
3.2 现实的：多坐标空间
第二个观察是，我们在系统中的每个节点中维护多个独立的坐标空间。我们可以把这些坐标空间叫做“reality”。因此对于具有r个现实的CAN，单个及诶单倍分配r个坐标区域，每个真实上有一个，并且r个独立的邻居集。
哈希表的内容被重复在每个reality上。这提升了数据的可用性。例如，假设指向特定的指针要存储在坐标位置（x,y,z）。由四个独立的现实，这个指针将存储在坐标对应的四个不同的节点上，因此只有当四个点都不可用时它才不可用。多个真实也提高了路由容错性，因为在一个现实中路由故障的情况下，消息可以继续使用剩余的现实路由。
进一步，在一些路由上，因为哈希表的内容被复制在每个相关的路由到(x,y,z)转换到(x,y,z)。一个给定的节点在每个现实中拥有一个区域，每个区域都是不同的，坐标在空间中的位置可能是遥远的。因此一个独立的节点有能力到达在单个挑中协调空间中遥远的点，从而大大缩短了平均路径长度。为了转发一个信息，一个节点现在检查它每个真实上的的所有邻居并且将消息转发给最接近目的地的邻居。图5展示了对于不同数量的真实，增加的节点数量。在图中我们可以看到，现实大大缩短了路径长度。因此使用多个显式减少路径长度，从而减少总体CAN的路径延迟。
多个维度vs多个现实
无论是增加维度数量或者现实的数量都能减少路径长度，但是增加每个节点的状态和维护的流量。在这里我们比较这些特性带来的相对改进。
图6绘制了路径长度与增加维度和现实情况下每个节点维护的平均邻居数量的关系。我们看到对于相同数量的邻居，增加空间的维度所减少的路径好于增加现实的数量。但是，不应该从这些测试中得出多维比多个现实更有价值的结论，因为多个现实提供了其他好处，例如改进的数据可用性和容错性。确切的说，我们需要了解的是，如果为了提高路由效率的主要目的而增加每个节点的平均邻居状态。那么正确的方法是增加坐标维度d而不是现实数量r。
3.3 更好的CAN路由度量
在2.1中描述的路由度量，是用笛卡尔距离表示的，一个可以通过让每个节点测量网络级往返时间来改进该度量，以便更好地反映底层IP拓扑的每个邻居的RTT。对于一个给定的维度，一个信息被转发到进程于RTT的最大比率的节点。这有利于低延迟路径，并帮助应用程序级别的CAN路由避免不必要的长跳。
不像增加维度或者现实的数量，RTT加权路由目标是减少路径上单个跳的延迟，而不是减少路径的长度。我们评估RTT加权路由有效性的指标是每一跳的延迟，通过将整个路径延迟除以路径长度获得
为了量化路由度量的影响，我们使用了传输域内链路延迟为100ms的TransitSub拓扑，stub-transit链路10ms， intra-stub域链路1ms。在我们模拟的拓扑中，随机选择的源-目标节点直接的底层IP网络路径的平均端到端延迟为115ms。表1比较了有RTT加权和没有RTT加权时平均每条的延迟。这些延迟在测试运行中取平均值，CAN中节点的数量范围在$2^8-2^{18}$之间。
如我们所看到的，虽然没有RTT加权路由的每条延迟与底层网络延迟匹配，RTT加权路由降低了每跳的延迟在24-40%之间，更高的维度提供更多的下一跳转发的选择。
3.4 过载的坐标区域
到目前为止，我们的设计假设在任何时间点分配给系统中的一个节点。我们现在通过允许多个节点共享一个坐标。共享同一个区域的节点称为对等节点。我们定义了一个系统参数MAXPEERS，每个区域允许的最大对等节点数（我们（我们想象这个值通常会很低，3或4）。
使用区域过载，一个节点维护除了邻居列表外海维护对等节点。同时一个节点必须知道在自己拥有区域中的所有对等节点，但是它不需要跟踪邻近区域内的所有对等体。相反节点从每个相邻区域的对等体中选择一个邻居。因此，区域过载不会增加单个节点必须保存的邻居信息的数量，但是需要为MAXPREERS对等节点保持额外的状态。
过载碍于的实现方式如下：当一个新的节点A加入系统，和之前一样，它发现一个存在的节点B，它打算占据这个节点B的区域。不是和之前提到直接分裂做法，节点b首先检查是否有少数的MAXPEERS 对等节点。如果是这样新节点A仅加入B区域没有任何空间分裂。节点A观察到它的对等列表和它坐标的邻居列表。来自A服务的定期软状态更新通知A的对等体和邻居它已进入系统。
如果区域满了（已经有了MAXPEERS个节点），那么区域像之前一样被切分。节点B通知每个在对等列表，那个空间要切分了。使用确定性的规则（例如，IP地址的顺序），对等节点列表上的节点和新节点A将自己平均分配到现在分裂区域的俩半。和之前一样，A从初始对等节点的邻居列表。
周期性的，一个及诶单发送它的协调邻居发送请求，以获取对等节点的列表，然后测量它所有邻居的RTT，并且维护最低延迟的RTT，就像区域中的邻居一样。因此，随着时间的推移，一个节点会测量到每个相邻区域中所有节点的往返时间，并保留其坐标邻居集中最近（延迟最低）的节点。在引导进入系统后，一个节点可以执行这个RTT测量操作使用极低的间隔，以避免不必要地产生大量的控制流量。
这里的复制应该指的是数据分片
散列表本身的内容可以在区域内的节点之间分割或复制。复制提供了更高的可用性，但是每个节点上的数据大小增加了
MAXPREES的一倍（因为整个空间现在被划分的更少，因此更大的区域）必须在对等节点之间保持数据一致性。另一方面，分区数据在对等节点之间对数据进行分区不需要一致性机制或数据存储，但也不能提高可用性。
超载提供了很多优势：
- 减少了路径长度（跳数），一次减少了路径的延迟，因为在每个区域防止多个节点与减少系统中的节点具有相同的效果。
- 减少了每跳的延迟，因为节点可以在选择邻居节点时有多种选择，并且可以选择延迟更近的邻居。表2列出了增加MAXPEERS对系统大小的平均每跳延迟，在$2^8-2^{18}$个节点的范围中，节点具有相同的底3.3节中的Transit-Stub仿真拓扑。我们看到，每个区域防止4个节点可以将每跳的延迟减少约45%。
- 提升错误容忍，提高了容错能力，因为只有当一个区域中的所有节点同时崩溃时，该区域才是空的（在这种情况下，仍然需要第2.3节的修复过程）。
消极的一面是，过载区增加了系统的复杂性，因为节点必须额外跟踪一组对等节点。
3.5 多哈希函数
对于提升数据的可用性，可以使用k个不同的哈希函数来映射单个键到坐标空间k个位置，并且坐标复制单个键值对在k个系统中不同的节点，只有当所有的副本同事不可用时。键值对才是不可用的。此外，对于特定哈希表的条目的查询可能同时发送到k个节点而减少了平均延迟。图7展示了查询延迟，即查询键值对的时间，位不同数量的哈希函数增加节点数量。
当然，这些优势是一增加键值对数据库的大小为代价的，数据库和查询流量（在并行查询的情况下）增加k倍。
不是查询所有的k个节点一个节点可能会选择坐标空间中最接近的节点检索一个条目。
3.6 CAN覆盖网络的拓扑敏感结构
CAN构建机制描述在2.2章。 随机分配节点到分区，CAN上节点的邻居不需要拓扑邻近的底层IP网络。这可能会导致奇怪的路由场景，例如，伯克利的CAN在欧洲有其他的邻居节点，因此，它到达斯坦福附近的一个节点的路径可能会穿越遥远的欧洲节点。虽然前几节中描述的设计机制视图提高在现有覆盖网络下的路径选择，但他们不是图改善网络结构本身。在这一章节，我们在试图构建出与底层IP拓扑一致的CAN拓扑网络。
我们的初始模式假设一定存在一个众所周知的机制（例如，DNS根命名服务）作为互联网上的地标。我们基于CAN节点与这组地标的相对距离实现了一组分布式分组的形式。每个CAN节点测量到每个地标的往返时间，并按RTT增加的顺序对地标进行排序。因此根据其对不同地标的延迟测量，每个节点有关联的排序。对于有m个地标m!的排序是可能的。我们将空间坐标划分为m!个相等大小区域，每个对应单独的一个顺序。我们当前（有些原始的）方案是将空间划分为m!部分原理如下：假设循环维度是固定的（即xyzxyzx...）我们首先沿着第一个维度划分空间位m个部分，然后沿着第二个维度进行细分到m-1个，每一份又进一部分层m-2部分，以此类推。之前，一个新的节点在整个坐标空间中的随机位置加入CAN。现在一个新的节点在与其他地标排序相关的坐标空间部分中随机加入CAN。
就是每个节点都选几个地标，看自己距离地标的位置在全局排第几名，然后取多个坐标，由相同顺序的点就是和自己距离接近的点。
该方案背后的原理是拓扑上接近的点可能具有相同的顺序，将位于坐标空间的同一部分，因此坐标空间中互联网上的连狙可能在拓扑上接近。
我们用来评估上述分组方案的度量CAN网络上的延迟与IP网络上的平均延迟之比。我们叫这个延迟stretch。图8比较了使用和不使用上述地标排序方案构建的can的拉伸。我们使用与之前相同的Transit-Stub拓扑（第3.3节）和随机放置的4个地标，唯一的限制是它们之间必须至少相距5跳。可以看到，地标排序极大地改善了路径延迟。
上述分组策略的结果是，坐标空间不再均匀地填充。因为某些排序（箱）比其他排序更有可能发生，对应的坐标空间也更密集，导致节点之间的负载略微不均。后台的负载均衡技术（在附录A中描述）其中超载节点将其空间的一部分交给负载较轻的节点可以解决这个问题。
这个结果令人鼓舞，我们将继续研究拓扑，链路的延迟分布，地标的数量和其他上述模式的影响。地标排序工作正在进行中。本文不作进一步的讨论和利用。
3.7 更多统一的分区
当一个新节点加入，一个JOIN信息被发送到空间中随机点的拥有者。这个现存的节点不仅知道自己的区域坐标，也知道他的邻居。因此它不是直接分割自己的区域，而是首先将自己区域的体积与坐标空间中相邻的体积进行比较。为了容纳新节点而且分的区域是具有最大卷的区域。
因此这种容量平衡检查视图在所有节点上实现更统一的空间分区，并且可以使用或不适用在3.6节中的地标排序方案。因此键值对使用一致的哈希函数划分穿过协调空间，节点区域的体积表示节点必须存储的键值对数据库大小，因此表明了节点上的负载。因此为了实现负载均衡，需要对空间进行统一分区。
记住这并不是充分的不平衡分区，因为因为一些键值对会比其他对更受欢迎，从而给承载这些对节点带来更高的负载。这类似于网络的热点问题。在3.8章我们描述了缓存和副本技术，它可以用来缓解CAN中的热点问题。
如果整个坐标空间的总体积为 VT，系统中的总节点数为 n，那么在理想的划分情况下，每个节点应当被分配体积 VT / n 的区域。我们用 V 来表示 VT / n。我们在具有 $2^16$（65,536）个节点的系统上进行了模拟，分别在启用和未启用均匀划分（uniform partitioning）功能的情况下，统计每个节点被分配的区域体积。在每次实验结束时，我们计算每个节点的区域体积，并绘制了不同区域体积的分布情况。
图 9 展示了不同可能的区域体积（以 V 为单位）在 X 轴上的分布，以及 Y 轴上对应的节点百分比。从图中可以看出，在没有均匀划分功能的情况下，仅有 40% 的节点 被分配了接近 V 体积的区域；而启用了均匀划分后，这个比例提升到了 近 90%，同时，最大区域体积也从 8V 下降到了 2V。毫不意外的是，随着维度（dimensions）的增加，空间划分的均匀性进一步提升。
3.8对于热点管理的缓存和复制技术
就像在网络上的文件一样CAN中的特定键值对比其他键值对访问的更加频繁，从而使持有这些流行数据键的节点过载。为了确保非常受欢迎的数据键广泛可用，我们借用了一些通常应用于web的缓存和复制技术。
- 缓存：除了主数据存储之外（即用哈希进入坐标区域的数据键），CAN节点维护最近访问数据键的缓存。在朝着目标转发数据之前，节点先检查数据键是否在自己的缓存中，本身可以满足请求，无需进一步转发。因此为数据键提供服务的缓存数量与它的流行程度成正比，并且数据键的行为使它更广泛地可用。
- 复制：如果某个节点发现对于特定数据键的请求负载过重，则可以在每个相邻节点上复制该数据键。复制是一种主动推出流行数据键的方式，而不是缓存，它是一个请求数据键的自然序列。因此，流行数据键最终在原始存储节点周围的区域内复制。持有所请求数据键副本的及诶单，在一定概率下，可以选择满足请求或在途中转发请求，从而导致负载分布在整个区域，而不仅仅是沿外围。
与此类模式一样，缓存和复制的数据键应该有一个相关的生存时间字段，并最终从缓存中过期。
4 设计总览
5 相关工作
6 讨论
目前为止，内容寻址网络解决了俩个主要的问题：可扩展的路由和索引。我们的仿真结果验证了我们整体设计的可扩展性-对于一个有超过26万个及诶单的CAN，我们可以以小于IP路径延迟的俩倍进行路由。
实现一个全面的CAN系统时，还需要解决额外的问题。一个重要的开放问题是设计一个安全的CAN来抵抗拒绝服务攻击。这是一个特别困难的问题，因为（与Web不同）恶意节点不仅可以作为恶意客户端，还可以作为恶意服务器或路由器。许多正在进行的研究和工业项目都在研究构建既安全又能抵抗拒绝服务攻击的大规模分布式系统的问题
未来工作的其他相关问题包括扩展我们的CAN算法来处理可变内容，以及搜索技术的设计[8,21]，例如围绕我们的CAN索引机制构建的关键字搜索。
我们对探索设计的可扩展性感兴趣，以及进行真正大规模实验（数十万个节点）的难度，导致我们通过模拟初步评估我们的CAN设计。现在，模拟已经让我们对设计的伸缩特性有了一些了解，我们正在与其他人合作，着手一个实现项目，构建一个使用CAN进行分布式索引的文件共享应用程序。