分布式存储系统(OceanStore)的复制策略

分布式存储系统（OceanStore）的复制策略姜大光，奚嘉鹏北京化工大学信息科学与技术学院，北京（100029）E-mail：[e-mail]摘要：OceanStore项目是Internet上基于P2P结构的分布存储应用，目标是向用户提供强持久性、高可用性、可扩展性和安全性的服务。它的整个复制策略分为两个大的方面:Erasurecoding和Replication，一份数据同时用Erasurecoding和Replication实现，Erasurecoding主要保证数据的持久性，Replication主要是为了保证用户的访问速度。关键词：OceanStore，分布存储，P2P，复制策略，Tapestry，分布式哈希表中图分类号：TP301文献标识码：AP2P[1](peer-to-peer)技术能够有效实现对网络上数量巨大的资源进行有效管理和充分利用，与传统的Client/Server计算模式不同，它没有服务器和客户机之分，每个结点都是一个对等体(peer)，它们之间直接交换共享的计算、存储、信息等资源和服务。OceanStore[2]是一个广域的P2P网络文件存储系统，P2P存储系统的基本目标是帮助用户把数据分布到广域网的多个结点上，并且保证数据的完整性、一致性、可靠性和可用性。与传统的基于集群或者局域网的分布式存储系统相比，P2P分布式存储系统具有以下优势：（1）存储容量更大。P2P存储系统中的一个存储结点既可以是一般的个人用户的PC机，也可以是基于集群的大型存储设备。（2）可靠性、可用性更高。P2P存储系统在整个Internet中搭建，数据在全球范围内分布，系统可以通过在广域网范围内进行数据冗余管理增强数据的可靠性和可用性。（3）分布式访问效率更高。数据在全球范围分布的另一个好处是当数据有多备份时可以就近访问，对于一些经常处于移动中的用户这一点尤为重要。1.分布存储中复制策略的分析复制策略[3]总体来说是决定一个数据对象(object)同时应该拥有几个副本以及这些副本怎样在Internet上进行分布才能提供高的性能和有效的管理:数据复制作为分布存储系统的一个重要方面，必须解决两个基本问题:首先是性能，其次是管理的有效性。在没计一个复制策略时，必需考虑以下几个问题:（1）复制算法的设计。复制算法是任何一个复制服务的核心，它对数据副本的读取和更新都有及其关键的影响，从根本上决定了一个系统的性能和管理的有效性。（2）一个数据对象需要维护的副本数。较少的副本易于管理，但是不能满足用户的访问速度需求，过多的副本则会给系统的管理带来很大的复杂性，因此，副本的数量必须保持合适，在访问速度和系统可控性方面达到平衡。（3）数据多版本问题。有些数据需要维护一定数量的历史记录，这就要求开发的系统能够支持多版本。（4）数据更新问题。一个数据对象有多个副本，更新时，首先需要考虑采用什么组通信技术，其次需要考虑采用哪种更新信息。（5）数据一致性程度。这包括强一致性和弱一致性。强一致性要求所有副本同步更新，会降低数据的可用性和访问速度；弱一致性则允许非同步更新，会产生一些过期的数据。（6）用户应用需求。网络上的应用侧重点各有不同(如访问速度，数据的多版本支持和读写频率)，开发具体的分布式存储系统时需要综合考虑这些因素，满足不同的用户需求。2.利用Tapestry构建虚拟网络系统中的副本结点是Tapestry[4]定位机制的一部分，主要用于数据的定位，Tapestry是一个可升级的建在TCP/IP上的网络。在Tapestry中，每个主机和资源都是以GUID来命名的。每个加入的主机都被分配到一个GUID，然后在Tapestry上发布它们资源的GUID，其他主机就可以在Tapestry上查询到这些资源。通过Tapestry发送的消息就是用这些GUID来标识的，而不是用IP。然后Tapestry把消息通过路由发送到包含该GUID资源的主机。通过虚拟网络，OceanStore的运行从资源的地域性中脱离出来。而Tapestry中有地域标识，若有多个拥有相同GUID的资源，它会从中选择在物理上相距最近的消息资源来提供给用户。Tapestry的路由规则简单地说就是对每个网络中的节点和与其相邻的节点都设了个匹配原则，根据GUID的匹配关系设立多个匹配链。与某节点的GUID第一位就不同的相邻节点都在该节点的L1链上，依此类推。如图1所示，从起点5230开始，通过查找与目标42AD第一位匹配的节点找到下一个节点400F，然后再查找该节点的L2链找到第二位相同的节点4227，接着匹配4227的L3链就找到42A2，最后通过其L4链就到达目标42AD，完成路由。图1Tapestry路由图整个复制策略分为两个大的方面:erasurecoding[5]系统和复制系统[6]，一份数据同时用erasurecoding系统和复制系统实现，erasurecoding系统主要提供数据的持久性，复制系统主要是为了保证用户的访问速度。ErasureCode实际上是一种数学技巧，它先把一个原始数据块分割成相同大小的m个片断，然后再把这m个片断重新编码成n（m）份，r（＝m/n）就是这个编码率。重新编码的关键就在于原始数据只要有其中任何的m个片断就可以重新构建。在OceanStore中，当对复制进行一次更新操作之后，所有新创建的数据块都用ErasureCode重新编码，然后生成的数据块就被复制通过Tapestry分发存储到各个服务器上。当用户要访问该数据时，系统再通过Tapestry找到足够的片断，再次编码重构数据。在复制系统方面，基本思想是在满足一定的性能要求下,维护尽量少的副本数量以减小系统维护的代价，同时要求各个副本保持负载平衡。3.2系统的可用性使用erasurecodes获取的可用性是利用很大数量的组分统计的稳定性的结果。数据块的可用性能被计算如下P0－一个数据块可用的概率n－所有数据片断的个数m－需要重建一个数据块所需要的片断个数N－系统中所有机器个数M－当前不可用的机器个数∑−=−−•=mninNinMNimCCCP00公式1一个数据块可用的概率等于不可用的片断放在不可用的机器上的方法数乘以可用的片断放在可用的机器上的方法数，然后除以所有的片断放在所有机器上的方法数。例如：有100万台机器，其中10%机器当前不可用：z对于2个复本的复制系统：其中：n=2；m=1；N=1,000,000；M=100,00099.0120210000002100000100000010=•=∑−=−−iiiCCCP公式2z对于r=16/32的erasurecoding系统：其中n=32；m=16；N=1,000,000；M=100,000=•=∑−=−−iiiCCCP公式3在消耗同样存储容量和带宽的前提下，可以断言，可用性随着片断的增加而增加。3.3系统比较使用相同的系统大小B（所有的数据块）和相同的写频率wBlocks/s去比较基于复制的系统和基于erasurecodes的系统。比较复制和rasureencoded系统(用x表示系统)，x系统的总存储量为Sx，x系统的总带宽为BWx，x系统的磁盘寻道次数为Dx，当考虑存储量和带宽的时候，我们不比较读，因为读取一个数据块的数据需求量两个系统是一样的，也就是m个片断在存储量和带宽方面需求等于和一个复制。1、相同的平均无故障时间(MTTF)和修复时期（RepairEpoch）在相同的平均无故障时间(MTTF)和修复时期（RepairEpoch）的前提下比较复制系统和erasureencoded系统。假设我们存储但不删除数据，系统的总容量就是所有相同容量数据块的总和（用B表示）：lifetimeswBlocksNB××=公式4其中N为用户总数，lifetime为系统的生命周期。给定系统大小(由用户的数量定义)，在一个长期系统中存储数据必须的资源是什么，定义丢失一些数据块的期望平均无故障时间(MTTF)作为系统的耐久性远远大于系统的期望的生命周期，就是：lifetimeBMTTFMTTFblocksystem=公式5通过下面的公式我们得到如何去计算系统的存储量、带宽和磁盘寻道次数。Sx为系统中可以存储的所有字节数repairwritexxxBWBWBW+=公式6readrepairwritexxxxDDDD++=公式7Sx是x系统必需的总存储容量，BWx是每一次修复时期支持存储总量写和修复所必须的带宽。Dx是支持修复、写和读的磁盘寻道次数的总数。接着，我们计算复制系统和erasureencoded系统的存储量。××=公式8BrbBnmbSerase××=××=1公式9其中，R为复本个数，r是编码率，b是单个数据块大小。现在我们如下计算存储带宽。nreplicationreplicationreplicatioeSswBlocksNRbBW+×××=公式10earseeraseeraseeSswBlocksNrbBW+×××=1公式11其中，ex是系统的修复时期，我们现在显示由于仅仅原始数据写和修复的带宽被表示作为DataRate：xxeBswBlocksNDR+×=公式12另外，我们计算支持写、修复、读必须的磁盘寻道次数。dbsz是一个磁盘数据块的大小。szdbbeBRswBlocksNRD×+×+××=)1(nreplicationreplicatio公式13szdbmbmeBnswBlocksNnD××+×+××=)(eraseearse公式14上述公式表明,磁盘寻道次数必需依靠复制品的数量(或片段的总数),生产量,系统大小,修复时期,复制品的数量(或片段)必要重建块,并且可能适合盘块复制品(或片段的)的数量。最后，一个复制系统能与一个相似的erasureencoded系统比较通过下面带宽、存储,和磁盘寻道次数比率。rRSSearsenreplicatio×=公式15rRDRrDRRBWBWerasenreplicatioearsenreplicatio×=××=1公式16×≈××+××+×=)()1(公式17我们利用下面适当的参数使抽象的数字具体化：我们测量工作站数据平均写频率35Mr/hr。我们假设一个工作站上有一个用户。我们设置b=8KB的数据块，dbsz=8KB磁盘数据块，N=224用户数，复制系统和erasureencoded系统的修复时期：ereplication=eerase=4months，MTTFsystem1000年。利用前面的参数，我们计算：B=1017总数据块；由此得出，MTTFblock=1020年。我们设置复本个数R=22，编码率r=32/64=1/2。11=earsenreplicatioBWBW公式1811=earsenreplicatioSS公式1911=earsenreplicatioDD公式20这些结果表示,一个复制系统与相同大小erasureencoded系统要求数量级更多带宽、存贮和磁盘寻道次数。2、相同的额外存储量（storageoverhead）和修复时期（RepairEpoch）我们设置复制系统和erasureencoded系统修复时期ereplication=eerase=4个月，副本个数R=2，编码率r＝32/64。我们计算得出一个数据块复制到两个服务