Communications of CCF 2008/11
开放式对等网络存储系统
所面临的挑战
*
代亚非 田 敬 杨 智北京大学
引言
对等网络（Peer to Peer ，P2P ）存储系统是分布式系统的一种应用形式。一般意义上，它应该具有以下属性：（1）采用对等网络技术实现节点间的通信、资源查找和数据传输；（2）基于用户节点的磁盘空间构成广域网上海量的存储系统；（3）用户的离开和加入原则上是自由的。为便于后面的讨论，我们在这里先定义两种不同类型的对等网络系统：封闭式系统（Closed system ）和开放式系统（Open System ）。
封闭式系统是指系统具有较为严格的中心认证、审计及管理功能，从而保证系统中节点的持续运行。该系统中的节点可以认为相对稳定，虽然可能出现暂时错误，但是会及时修复并重新回到系统中，且不会随意退出系统，节点之间协作关系良好。这类系统的代表是PlanetLab 。它是一个由遍布世界的研究机构捐献的机器构成的覆盖网络，每个节点由专人负责维护，节点可靠性和可用性较高。在PlanetLab 上搭建的存储系统包括OceanStore 的
原型系统Pond 和“Total Recal ”等。
开放式系统是指系统中每个节点可以随意加入或退出系统，其节点不保证持续在线提供服务。相对于封闭系统，开放系统中的临时错误（节点暂不在线）和永久错误（节点退出系统）出现更加频繁，节点之间的合作度很低，甚至有不少理性用户1。开放式对等网络系统节点的频繁加入或退出导致系统为了保证一致性和数据可用性，需要在后台消耗大量的带宽、CPU 和存储空间等资源来不断进行修复和维护。这对系统而言是一个非常大的负担，尤其是对个人电脑而言，会明显影响用户的使用体验。这类系统的典型代表是用户的个人电脑所组成的网络，例如文件共享系统Gnutella 2、纳普斯特（Napster 3）、Overnet 4、KaZaA 5和天网Maze 6等。
本文所讨论的对等网络存储系统特指由低成本的PC 机所构成的开放系统。谷歌文件系统（Google File System ，GFS ）是低成本构建存储系统成功的经典案例。它用来存储搜索引擎搜集的成千上万的网页，并为用户提供大容量的邮箱以及图片和文档的存储。该文件系
* 本论文工作受国家973项目资助，项目编号为2004CB318204
1
即其行为以追求自身利益的最大化为目标的用户，他们会尽量减少自己提供的服务却设法获取最大利益。2
简单又方便的网络交换文件软件。3
第一个被广泛应用的对等网络（Peer-to-Peer，P2P）音乐共享服务。4
一个文件共享程序。5
一款点对点文件共享工具。6
北京大学研发的天网MAZE文件系统
关键词 对等网络 存储系统 可用性
中国计算机学会通讯 第4卷 第11期 2008年11月
特别报道／Special Report
Communications of CCF 2008/11统的成功展示了低端存储的需求和广阔的发展
前景。然而，这种文件系统模式属于封闭式的
存储系统，使用了成千上万系统可控制的专用
服务器，而非用户节点。它面临的系统故障是
由硬件故障、网络故障或者软件故障引起的，
而非由于用户自由加入和退出引起的。因此，
谷歌文件系统模式没有解决对等网络存储系统
的全部问题。
对等网络存储作为存储系统的一种形
式，应该具有高可用性、高可靠性、高一致性
以及高效性；作为一种分布式系统，必须具有
可扩展、异构、透明等分布式系统的特征；而
作为对等网络系统必然呈现出节点频繁变化的
动态性。在这些综合因素形成的高动态环境
下，存储系统的经典问题呈现出新的特点和新
的问题，从而构成了对等网络存储独特的研究
领域。
研究现状
早期的对等网络存储系统研究[1-6]的主要
内容是设计结构化对等网络路由算法、采用纠
删码（erasure code）的冗余方式以及拜占庭协
议（Byzantine Agreement，BA）7等一致性维
护措施，动态性并不是其重点。
开始重视对等网络系统动态性研究的工
作是“Total Recall”项目[7][8]。针对系统中数
据的可用性，该项目研究了副本冗余和纠删码
冗余两种方式对提高数据可用性的作用。同类
研究还包括香港学者林（Lin，音译）等人[9]
重新考察了纠删码对对等网络存储系统可用性
的影响。通过对可用性组合概率的渐进分析，
他们发现在高动态环境下纠删码可能会降低数
据的可用性。2005年，美国麻省理工学院的学
者罗德里格斯（Rodrigues）等人[10]从系统可
行性的角度分析了这两种方式对可靠性和可用
性的影响，指出了纠删码方式优势的局限性。
系统中的可用性和可靠性是与数据的存
放有着密切的关系的。这方面的很多工作[11-14]
主要是研究如何优化副本存放的位置，例如，
将重要的数据放置在高可用的节点上，为经常
收到访问的数据提供高可用性策略，以及给不
经常访问的数据提供可接受的可用性策略。
为了保证系统的可靠性，需要多余副本
来屏蔽临时性错误，当副本低于阈值时创建新
的副本。阈值的设定和存活结点的估计是对等
网络系统的难题。在文献[12,15,16]等分析中
指出，采用固定时间阈值可作为判断永久错误
的条件，但是如何选择阈值是一个难题。2006
年，加州大学伯克利分校（UC Berkeley）的
邱丙坤（Byung-Gon Chun，音译）和哈基姆·
韦瑟斯庞（Hakim Weatherspoon）同美国麻省
理工学院及莱斯（Rice）大学的多个研究者又
提出了一个广域网的复制算法Carbonite[17]，以
PlanetLab环境为基础，提供了遇到错误就修
复的积极修复方案，但该方案只适用于较低动
态的存储环境。斯里兰·拉曼博汉德兰（Sriram
Ramabhadran）等人[18]对对等网络中有冗余的
状态（state）的存活寿命（连续可访问的时
间）进行了研究，得到了在带宽或存储约束的
条件下最优的修复目标冗余度。同年，埃米尔·西
特（Emil Sit）与斯里兰·拉曼博汉德兰以及哈
基姆·韦瑟斯庞等人进行合作研究[19]提出，在
稳定环境下当无错误时可以预先修复数据，避
免了对永久错误的判别问题。不难看出，数据
维护是目前的研究热点，有关的研究方法和模
型各不相同，整体研究还处于起步阶段。
安全问题一直是对等网络系统研究关注
的重要内容，目前主要集中在路由层的安全和
拜占庭错误8等方面，包括如何提供匿名路由
功能[20-21]，避免或容忍拜占庭错误[22-23]，以及
避免多重身份攻击[24]等。在数据安全方面，已
有研究[25]对保证数据完整性的问题提出了解决
方案。虽然存储数据的私密性是极为重要的问
题，但在对等网络研究领域仍没有针对此问题
的解决方案，大多数系统仅使用经典的分组加
7 拜占庭协议是基于拜占庭模型的协议，即允许有“叛徒”（这里相当故障或失效）的条件下“忠诚
者”（这里相当完好部件）仍能够在不需要排除甚至检测出“叛徒”的情形下完成使命的协议。
8拜占庭错误（Byzantine failure）是指失效的元部件不仅会有错误的行为，而且其行为会破坏一致性，每次不一定重复。
密算法来保护用户的隐私。
综上所述，不难发现这些研究所针对的环境、使用的分析工具及结论都是不尽相同的，因此在分析方法及与应用相关的结论方面，对等网络存储系统的研究还有很大空间。
面临的挑战
由于对等网络系统的基本原则允许用户自由加入和退出，因而导致对等网络系统具有很高的动态性。这种动态性对共享类和直播类应用没有太大影响，但是却给对等网络存储系统带来可用性、可靠性和安全性方面的三大难题：
（1）可用性方面：在共享系统中，通常依靠副本来提高可用性和下载速度。但是在存储系统中，副本控制非常复杂。存储系统中副本数过多，不仅会带来安全性隐患，也会给一致性维护带来巨大的开销。而且存储系统中副本数也是受限的，同时动态性会导致副本数变化，这些因素对可用性造成的影响远比共享系统大得多。
（2）可靠性方面：存储系统的可靠性是通过维持一定的冗余度来保证的，冗余度的变化取决于系统的故障节点的数目。传统存储系统的错误一般是较为容易检测到的磁盘错误，而对等网络存储系统中，故障是指存放数据的节点永久离线。由于用户的上下线频繁且行为自由，给估计冗余度带来很大困难。
（3）安全性方面：在对等网络存储系统中，理论上，每个用户的机器上都可能存储一些不属于自己的数据，因而文件存在被无意或恶意删除的隐患以及隐私性等问题，给数据的安全维护带来困难。
核心问题
数据可用性研究
数据可用性定义为数据在时间t可以被访问到的概率。由定义可知，数据可用性是与系统的读操作相关的，节点暂时离开可能造成数据暂时不能被访问，会降低数据的可用性。因此，数据的可用性主要受节点的在线率（用在线时间和总观察时间的百分比表
示）和节点每次会话时间长度的影响。由于
对等网络系统中用户上下线频繁，传统的利
用平均故障率计算冗余度的方法以及保障可
用性的策略在动态环境下会导致极大的维护
开销，甚至无法使用。为了解决这些问题，
需要先认识用户变化的规律，再提出相应的
冗余度计算方法，从而保证系统达到所要求
的可用性。这里包含了3个关键问题：（1）
准确预测单个节点的可用性；（2）根据节点
的可用性，建立数据的可用性模型，估算出
合适的数据冗余度；（3）激励用户在线。
对等网络中预测节点可用性的过程非常
复杂。与典型的分布式系统不同，对等网络
中节点的可用性有以下特点：
节点间的差异性：不同节点的平均可用
性不同，有时差异非常大，因此不能像传统
方法那样简单地用所有节点的平均数值来预
测每个节点的可用性。节点间的差异性会影
响到数据的放置策略。传统的存储系统中，
节点的差异性不大，因此数据可以简单地随
机存放。然而，在差异很大的节点集合上放
置数据，所需的冗余度会不同。因此，需要
研究如何依据节点不同的可用性合理地放置
数据，使系统整体的性能最好，即维护带宽
最小。同时，还可以采取规避差异的办法，
把具有类似规律的节点聚类在一起，构成一
个群体。节点间的相互保存和访问数据可以
屏蔽因为时间差异而访问不到数据的问题，
效果上大大提高了用户体验到的可用性。
时间上的差异性：对等网络中的节点
出没体现的是用户的在线行为规律，因此具
有一定的模式，如以天或周为单位的行为模
式。为此，节点的可用性不能只用一个在线
比例值来简单描述，需要我们研究更为精确
的节点可用性模型。这种模型不仅要能够体
现每个节点的平均可用程度，还应体现节点
的在线时间模式。
激励用户在线是对等网络存储与传统存
储相比特有的一个影响可用性的重要问题。
用户频繁上下线将导致系统耗费很大维护代
价来保证可用性，而激励用户在线，降低系
统的动态性，是提高可用性的最直接、经济
Communications of CCF 2008/11
特别报道／Special Report
Communications of CCF 2008/11的方法。激励用户在线不仅需要利用提升用
户在系统中的声誉的机制，还应该用提供更
好的服务质量作为激励。例如提供更大的存
储空间、更快的下载速度以及更大的访问权
限等。
数据可靠性研究
可用性是关注任意时刻数据是否可被
使用，可靠性则更加关注数据是否能长期存
放于系统中。数据可靠性与系统的写操作相
关，体现了数据写入系统后不丢失的概率。
节点的暂时失效并不导致数据丢失，数据仍
然可靠地存储在系统中，只是不能立即获得
访问，只影响可用性而不影响可靠性。这也
是可靠性区别于可用性的最重要的特点。在
传统系统中，暂时性错误比较少，系统性能
可以主要用可靠性来衡量。在对等网络环境
下，可用性就变得非常重要，二者都需要予
以关注。
系统可靠性定义为系统在时间t没有永久
丢失数据的概率。系统可靠性主要受到系统
中存储节点的寿命影响，而节点暂时离开造
成的数据暂时不可访问不应计算在内。传统
的系统故障概率一般符合指数分布，因此也
经常用平均失效时间（Mean Time To Failure，
MTTF）作为可靠性的指标。而这样的定义并
不符合P2P系统的特点。
可靠性是通过冗余来保证的，并且计算
冗余度是以已知副本数为前提，因此检测存
活副本数和修复丢失的副本就构成了可靠性
研究的两个重要内容。
错误检测
本文中的“错误”定义为存放数据的节
点永久离线所导致的数据丢失。错误检测就
是检测节点是否永久离线。当数据剩余冗余
度高于某一阈值时，系统不需要再增加冗余
就能保证数据的可靠性。因此，若系统高估
了数据的剩余冗余度，则会导致数据的冗余
得不到及时增加而造成丢失。反之，低估数
据的冗余度会使系统因增加不必要的冗余而
带来过多的额外开销。
然而，在对等网络系统中准确评估数据
的剩余冗余度是非常困难的。原因是系统无
法准确地区分节点的暂时失效和永久失效。
由于节点的暂时失效不影响数据的剩余冗余
度，因此，把暂时失效误判为永久失效（以
下简称为误判）会低估数据的冗余度，而把
永久失效误判为暂时失效（以下简称为漏
判）则会高估数据的冗余度。因此，我们需
要研究合理的模型以便有效地评估数据的剩
余冗余度。现有的研究表明，不区分失效的
类型会导致系统维护开销过高而使整个系统
无法运行。
确定检测的依据是解决问题的关键，我
们可以设定一个节点离开系统的时间阈值，
用以判断一个节点是否永久离线。事实上，
人工设定准确的阈值是不可能的。与其追求
设计精确判断每个节点状态的判别器，不如
我们换一种思路，追求系统中的漏判和误判
的平衡，即努力让误判数等于漏判数。一方
面系统考虑到判断器误判，会预先修复一些
副本；另一方面，系统会因判断器误判（同
时包括检测延迟和修复延迟导致的误判），
来不及修复一些副本。如果我们能使系统预
先修复产生的冗余与错误发生后不能及时修
复的冗余缺失相抵消，就在修复开销和目标
冗余度之间达到了最好的平衡。
定期心跳（或探测）法是比较直观的错
误监测方案。然而，当数据节点上存储的数
据很多时，该节点就会每个周期发送大量的
心跳数据包，从而导致系统性能极度下降甚
至使系统不可运行。此问题涉及到数据分发
和系统结构的设计。合理地采用分层管理或
者对节点分簇管理可以缓解扁平结构带来的
瓶颈问题。
数据的修复策略研究
由于与对等网络存储系统相关联的问题
多且复杂，因此，在该系统中需要维护多少
数据冗余、何时进行数据修复以及如何修复
等问题仍然是非常困难的研究课题。
数据的修复策略分为预先修复和事后修
复两类。预先修复是在永久失效发生前就开
始修复，可以平滑整个系统的带宽，但会增
加系统的额外开销。而事后修复是在永久失
效发生后才开始修复，虽能够节省系统开销，但会产生系统的突发带宽，影响存储系统的吞吐率。由于每一时刻系统中数据的剩余冗余度不同，因此需要研究以下两个关键问题：（1）如何根据剩余冗余度调度数据修复的次序使系统性能最优；（2）每个数据采取何种修复方式最好，由于每个对象的剩余冗余度和修复次序不同，会导致修复策略不同。
一般的修复过程是首先利用估算器来估算数据的剩余冗余度，然后在修复策略中优先调度冗余度低的数据，同时根据数据冗余度的变化情况动态调整数据修复的次序。另外，还可根据数据冗余度和调度次序设计出更高效的数据自适应修复策略。例如，如果数据的冗余度较高，则可采用事后修复来减少系统维护开销；反之，需要预先防止并发失效带来突发带宽。
目前在该研究领域中，研究者提出的解决方案很多。例如，采用预先的多余副本避免修复，或采用动态地增加多余副本策略，或采用无错误时预先修复方案等。针对不同的解决方案，其分析模型又是多种多样。例如，采用组合概率法计算数据可用性，或采用随机过程法计算状态持久性，还可采用类似半衰期的生命周期模型分析节点离开的影响，或采用节点指数离开假设做随机过程分析。
虽然在诸多的方案和分析方法中并没有统一的结论，但主要方法基本都是在带宽约束下，考察系统可以支持的修复冗余度和修复速度的最优值。在多数研究中，最大的难题是难以判断节点的离线是暂时还是永久，因而使系统无法针对永久错误进行精确修复。因此，对系统节点离线行为的判别算法将可能成为今后研究的核心。
另外，我们看到目前多数关于系统的研究都是针对类似P l a n e t L a b这种稳定系统，而对于高动态系统只有少数有关可行性的讨论。其原因主要在于目前还没有出现很成功的高动态环境中的存储系统，而且在高动态环境中的其它类型的对等网络应用的测量结果也相对较少，使得我们对高动态环境中节点行为的认识还很欠缺，因而缺少进行系统研究的基础。
目前，有关稳定节点环境中对等网络存
储系统冗余数据长期维护问题的研究正进入
深入开展的阶段，而高动态环境的研究还在
起步阶段。
数据一致性研究
数据的一致性与系统的更新操作有关。
更新操作发生时，非在线节点因无法接收到
更新而造成数据副本间的不一致。节点频繁
上下线将使传统一致性协议的开销增大或者
导致丢失更新，为此需要解决以下两个问
题：（1）研究一个在高动态环境下的一致性
协议，能够用更少的开销保证副本最终的一
致状态。（2）研究一个能够依据数据的更新
频率和失效频率来选择预先修复时机和修复
速度的模型，以保证在一致性前提下高效地
修复数据。一种设想是，可以考虑设计一种
动态建立和更新数据目录的协议，当不一致
的节点重新上线时，可通过读取目录获得更
新来达到一致，以适应动态的对等网络存储
环境。
无用数据的删除也会影响一致性。在执
行删除操作时，如果用户不在线，会使本应被
删除的文件仍保留在其节点上，若用户再次上
线，有可能造成和现有文件版本的不一致。因
此，必须考虑以下两个问题：（1）如何在节
点上下线频繁的情况下，保证数据的所有副本
中应删除的数据最终都被完全删除。（2）如
何在少部分不可信节点不遵守系统协议的情况
下，保证数据的所有副本中应删除的数据最终
都被完全删除。这两点都是传统分布式存储系
统没有遇到的问题。
数据安全性研究
开放的对等网络存储的本质特征是数据
存储在其它不可信的节点上。因此，若仅做
传统的分组加密将难以真正保证数据的机密
性，系统会存在以下安全隐患：（1）当密码
算法的弱点被发现或密钥丢失时，敏感数据
就会受到安全威胁；（2）即便用户发现其数
据的机密性受到威胁，也无法销毁所有恶意
节点上存储的密文副本以减小其损失，即在
各种安全威胁面前，数据的拥有者都非常被
Communications of CCF 2008/11
特别报道／Special Report
Communications of CCF 2008/11
动。这些问题严重阻碍了对等网络存储系统的发展。
一些系统的经典做法是：先用分组加密算法（比如高级加密标准（AES 9））为用户的数据加密以保证其机密性，然后将加密的数据再做副本或纠删码冗余以保证数据的高可用性。然而如前文指出的这并不能很好地保护用户的隐私。
对等网络存储系统的加密方案必须支持新型存储结构的特征，同时还需要有较高的算法性能。要想设计出既满足对等网络环境安全性要求又具有高性能的算法，我们认为应该考虑数据碎片、数据分布和数据加密这三个层面的安全性。在分布式存储系统中，通常采用纠删码作为冗余策略。纠删码方法把数据拆分成碎片并分发到不同的节点上，在一定层面上使系统具备了数据安全所需的改变数据原始信息的功能。如果利用纠删码的这个特点，再通过加密算法对文件碎片进行加密，那么在数据分发时，可将这些碎片独立分发到对等网络存储系统中的不同节点。若节电获取的碎片少于阈值个数，则不可能恢复任何原始数据的子部分信息。恶意节点即便得到数据的密钥或发现密码算法的
弱点，也不可能仅从自己本地存储的密文中获取任何敏感信息。如果恶意节点收集到了足够多的密文碎片，只要没有得到密钥，还是不可能解读出原始信息。
结语
近年来，对等网络应用发展迅猛，显示出该网络模式的强大生命力。虽然对等网络存储系统还面临着很多难题，但今后必将成为一种重要的存储组织模式。此外，稳定节点环境下的技术研究成果也极大地推动了对等网络存储系统的发展。相比之下，高动态环境下的持久存储研究仍处于起步阶段，其发展有赖于我们对高动态环境下用户行为的进一步认识。因此，我们需要尽快构造这方面的系统来收集实际动态性数据，以支持此研究。
[1] Kubiatowicz, J., et al., OceanStore: An Architecture for Global-Scale Persistent Storage. Proceedings of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems, 2000: p. 190-201
[2] Druschel, P. and A. Rowstron, PAST: A Large-Scale, Persistent Peer-to-Peer Storage Utility. Proc. HotOS VIII, 2001
[3] Adya, A., et al., Farsite: Federated, Available, and Reliable Storage for An Incompletely Trusted
Environment. ACM SIGOPS Operating Systems Review, 2002. 36: p. 1-14
参考文献
杨 智
北京大学信息科学技术学院博士生。研究方向为P2P计算及分布式存储。
代亚非
C C F 高级会员、存储专委会委员。博士，北京大学信息科学技术学院教授。主要研究方向为P2P计算、网络存储和网络与分布式系统。Email：dyf@https://www.doczj.com/doc/fc12110945.html,
田 敬
C C F会员。博士，就职于北京大学信息科学技术学院。主要研究方向为P 2P 存储。E m a i l：j i n g.t i a n@https://www.doczj.com/doc/fc12110945.html,。
9
Advanced Encryption Standard
（下转58页）
[4] Dabek, F., et al., Wide-Area Cooperative Storage with CFS. 18th ACM Symposium on Operating
Systems Principles (SOSP’01). October, 2001
[5] Rhea, S., et al., Pond: the OceanStore Prototype. Proc. of FAST, 2003. 2003
[6] Stribling, J., OverCite: A Cooperative Digital Research Library. In 4th International Workshop on Peer-
to-Peer Systems, 2005
[7] Bhagwan, R., et al., Total Recall: System Support for Automated Availability Management. In Proc. of
the First ACM/Usenix Symposium on Networked Systems Design and Implementation (NSDI), 2004
[8] Bhagwan, R., S. Savage, and G. Voelker, Replication strategies for highly available peer-to-peer storage
systems. proc. of FuDiCo: Future directions in Distributed Computing, June, 2002.
[9] Lin, W., D. Chiu, and Y. Lee, Erasure code replication revisited. In Proc. of Fourth International
Conference on Peer-to-Peer Computing, 2004: p. 90-97
[10] Rodrigues, R. and B. Liskov, High Availability in DHTs: Erasure Coding vs. Replication. Proc. of the
4th International Workshop on Peer-to-Peer Systems, 2005
[11] Douceur, J. and R. Wattenhofer, Competitive Hill-Climbing Strategies for Replica Placement in a
Distributed File System. Proceedings of 15th DISC, 2001: p. 48-62
[12] Schwarz, T.J.E., Q. Xin, and E.L. Miller, Availability in Global Peer-To-Peer Storage Systems. In Proc.
of 6th Workshop on Distributed Data and Structures (WDAS), 2004.
[13] Ramanathan, M., Increasing object availability in peer-to-peer systems. In Proc. of Parallel and
Distributed Processing Symposium, 2004
[14] Lian, Q., W. Chen, and Z. Zhang, On the Impact of Replica Placement to the Reliability of Distributed
Brick Storage Systems. Distributed Computing Systems, 2005. ICDCS 2005. Proceedings. 25th IEEE
International Conference on, 2005: p. 187-196
[15] Weatherspoon, H., et al., Long-Term Data Maintenance in Wide-Area Storage Systems: A Quantitative
Approach. Computer, 2005
[16] Blake, C. and R. Rodrigues, High Availability, Scalable Storage, Dynamic Peer Networks: Pick Two. In
9th Workshop on Hot Topics in Operating Systems, 2003
[17] Chun, B., et al., Ef?cient replica maintenance for distributed storage systems. Proc. of the 3rd
Symposium on Networked Systems Design and Implementation, 2006
[18] Ramabhadran, S. and J. Pasquale, Analysis of long-running replicated systems. Proc. of the 25th IEEE
Annual Conference on Computer Communications (INFOCOM), 2006
[19] Sit, E., et al., Proactive replication for data durability. 5rd International Workshop on Peer-to-Peer
Systems (IPTPS 2006), 2006
[20] Zhuang, L., et al., Cashmere: Resilient anonymous routing. Proc. of NSDI, 2005
Communications of CCF 2008/11