基于网络的分布式海量存储

宽带网络为传输种类繁多的高速多媒体流提供了平台之后，来自各ISP(信源提供商)和众多网络用户的大量信源势必呈海量趋势。然而，当前ISP的服务器“各自为政”，容量有限，难以满足对存储指数增长的需求。为此，本文提出基于网络的分布式海量存储技术方案，利用特征码避免相同资源的冗余存储，加入纠错码进行差错重建，利用进程迁移平衡负载，采用超流水线执行技术加速程序运行速度，以实现网络的资源共享。

　　1 分布式存储方案

　　基于网络的分布式海量存储技术方案的基础在于区域化的扩展S/C(服务器/客户机)模式，或称MP2 (MultiPeer-to-MultiPeer)模式。其存储方式采用MD5编码作为特征码，并采用RS码及交插和交叉技术，以扩展信息重建能力；此外，还提出信息收集源的网络信息缓冲方案，以减轻网络负荷。

　　1.1 区域化的P2P模式

　　本系统需支持Internet范围内的集群，采用了MP2模式，即多点对多点的信息交互模式。传统的S/C模式属服务器与多客户机交互模式。在传统的S/C架构中，资源集中在服务器上，客户机分别与之建立连接交换信息，而客户机之间的信息交换也须经过服务器。MP2模式网络结构图参见图1。

　　MP2模式扩展了传统的S/C模式的概念，图1中的A、B、C机一般是服务器，也可以是客户机。A、B、C机组成一个区域单元服务器群，群内信息交互，并协同与客户机交互。

图1 具有2模式的网络结构图

　　建立区域化的目的在于，根据各个节点所处的位置进行分区管理。同一区域中，节点之间的访问比较迅速，因此采取让负载(包括运算负载和存储负载)尽可能地处于同一个区域，可以提高资源访问的效率以及传输的可靠性。

　　MP2模式系统在本质上仍沿用了S/C的概念，支持TCP/IP协议，而在服务器群中的各节点在层次上是对等关系，并不严格要求其组成是服务器或个人电脑。诚然，由于服务器的处理能力、稳定性、网络条件都远高于个人电脑，在负载均衡算法的透明调节下，服务器自然承担起更多的负荷。

　　1.2 MD5码作为特征码的安全性

　　分散存储于各服务器的文件需利用特征码进行判决，可采用MD5的散列算法。近年来，由Ron Rivest在麻省理工学院提出的MD5报文摘要算法(RFC 1321)是一种Internet上常用的安全散列算法，可将长度任意的报文映射为一个128 bit的报文摘要。

　　本系统的MD5编码的码空间是安全的，证明如下：

　　给定一个散列函数H，如果H有k个随机输入，并可能有n种输出，输出值为H(x)，不难得出k的值，可满足至少存在一个输入y，使得H(y)＝H(x)的概率大于0.5。

　　对于单个值y，H(y)＝H(x)的概率为1/n，H(y)≠H(x)的概率为1－(1/n)。如果产生k个随机值y，那么它们之间两两不匹配的概率等于每个个体不匹配概率的乘积，即[1-(1/n)]k。

　　由二项式定理：

　　得出，对于一个非常小的数a，（1-a)k近似等于1-ka。这样，至少有一个匹配的概率为1-[1-(1/n)]k=k/n。

　　因此，对于长度为m bit的散列码，码空间为2m，要使上述概率大于0.5，那么k的值为2(m－1)。设系统用户数量为3亿户(目前全球计算机数量)，平均每台计算机容量为40 G，则40×10243×3×108≈1.2×1019＜1.84×1019(MD5的码长为128 bit，264＝1.84×1019)。因此可见，即使全球所有用户的硬盘全部塞满，而且文件长度均小到只有1个字节，MD5的空间仍是富裕的，可确保其安全性。 1.3 改进RS码的可靠性若因某存储节点离线，导致部分存储信息无法获取，可借助纠错码进行差错恢复。本系统采用RS码。(m， n)RS码表示码块有m个码元，其中信息码元有n个。通过对m个源编码的输入，计算出m－n个校验码元，整个n个代码可以允许有最多(m－n)/2个代码丢失。如知道丢失位置，通过解联立方程组就可全部恢复丢失的符号。

　　利用这样的编码，能够恢复少量的离散信息丢失。而本系统的结构使信息一旦丢失，就是大片和连续的，所以必须引入交插和交叉技术来增强RS码的恢复能力。所谓交插就是指把大量的码块按照一定的规则打散存放。比如：3个(8，6)RS码块，每一个码块都只能恢复一个符号。经过如图2的处理，就能够恢复任意连续3个符号的丢失，阴影部分的大量信息丢失就分散到每一个码块里面，这样原来不可能恢复的数据得到了恢复。

图2 交插编码示例

　　所谓交叉技术是交插技术的变形，它对码块的横向和纵向都求出RS码(如图3所示)。每1行以及每1列都只能恢复1个符号，但是通过1次恢复后，原本1行/1列的多个符号丢失就会减少，甚至减少到只丢失1个的情况。这样就又能够进行1次恢复。如此这般不停的迭代，即使出现这么多的信息丢失，都可以全部恢复。甚至还可以在三维的空间中进行交叉编码，以应付更复杂的情况。

图3 交叉编码示例

　　综合利用这两种办法，一台主机信息的丢失，对于整个信息来说，只是丢失了很小的一部分，完全可以通过这些重建技术来逐步恢复。

　　1.4 存取效率的提高

　　本系统每次的资源获取都需要和大量的节点建立连接，提取信息。如果每个信息都如此获取，那无疑浪费了相当的网络带宽，因此可引入缓存的理念。常调用信息应进行如下特殊处理：

• 每个节点都具有成为信息收集源的能力。很显然，其收集信息的能力与其连接的节点数目成正比。
  
• 对于每个收集完毕的信息都留有记录，以提供给系统中其他需要相同信息的节点，防止相同的信息重复收集。
  
• 节点与节点之间的连接并不在一次事务之后立即断开，因此相邻的几个事务不需要多次建立连接。
  
• 根据各个节点的CPU负荷和网络负荷，每个节点都可以选择任何节点(包括自身)代为收集需要的信息，因此在现有信息收集源负荷偏高的情况下，能够产生新的信息收集源。
  

　　信息收集源的产生是自动且透明的，无需人工干预。由于每个节点都内置了信息收集源的功能，因此各个节点为了成为具有高信息收集能力的节点而展开竞争；同时，又通过控制CPU负荷和网络负荷，来限制各个节点的过度竞争。

　　2 分布式计算方案　

　　本系统的分布式存储涉及大量数据的编码与解码，因而需要大量的计算。系统利用空闲的节点，通过进程迁移技术把负载转移过去，以平衡负载；计算量特别大时，使用超流水线技术对单一指令流并行执行。

　　2.1 进程迁移

　　进程迁移指将一个进程从当前位置移动到指定的处理器上。此系统中是将某台计算机的存取进程执行过程，转移到另一台计算机上继续运行。迁移是透明的，也就是说被迁移进程本身并不知道它已被迁移到其他节点上。进程迁移使得负载从高负载处理器上流到了低负载处理器上，提高了资源利用效率。但目前的进程迁移技术，大都要求在同构的系统(相同或兼容的机器体系结构和指令集以及操作系统)上进行。
进程迁移可以作为操作系统的一部分，或者用户空间、系统环境的一部分，或者应用程序的一部分。根据应用的级别，其可分为3类(如图4所示)：

图4 3种迁移方式示意图

• 用户级迁移：用户级实现较为简单，软件开发和维护也较为容易，但由于内核空间和用户空间之间存在着壁垒，打破这个边界获得内核提供的服务需要巨大的开销。因此，用户级实现效率远远低于内核级实现。
  
• 应用级迁移：应用级迁移实现较为简单，可移植性好，但是需要了解应用程序语义，并可能需对应用程序进行修改或重编译，透明性较差。
  
• 内核级迁移：基于内核的实现可以充分利用操作系统提供的功能，全面获取进程和操作系统状态，因此实现效率较高，能够为用户提供很好的透明性。但是由于需对操作系统进行修改，实现较为复杂。
  

　　进程迁移的主要工作就在于提取进程状态，然后在目的节点根据进程状态再生该进程。在现实中，一个进程拥有很多状态，并且随着操作系统的演化，进程状态也越来越多样。进程的状态一般可以分为以下几类：

• 进程执行状态：表示当前运行进程的处理器状态，和机器高度相关，包括内核在上下文切换时保存和恢复的信息，例如通用和浮点寄存器值、栈指针以及条件码等。
  
• 进程控制：操作系统用来控制进程的所有信息，一般包括进程优先级、进程标识、父进程标识等。
  
• 进程存储状态和进程地址空间：包括进程的所有虚存信息、进程数据和进程的堆栈信息等，是进程状态的最主要的一部分。
  
• 进程的消息状态：包括进程缓冲的消息和连接的控制信息。进程迁移中通信连接的保持以及迁移后连接的恢复是进程迁移中比较困难的问题。
  
• 文件状态：包括文件描述符和文件缓冲。保持文件的缓存一致性和进程间文件同步访问也是进程迁移机制需要着重考虑的。

　　2.2 超流水线执行

　　所谓超流水线执行，就是在保证结果正确性的前提下，通过并行执行串行指令流来提高程序运行速度。

　　程序结构分为3种：顺序执行、分支判断和循环。前两种都难以进行多流水线执行。因为几乎每一条指令都需要用到前面指令的计算结果，同样其执行结果也会影响后面指令的执行。然而不可忽视的一点就是：程序90%的执行时间恰恰花费在10%的代码中，而这10%的代码一般是循环或者递归调用。因此，对这10%的代码利用多处理器并行执行，能够大幅度提升程序的运行速度。而且由于循环体内的运算内容，一般仅仅与循环变量有关，如果能够分析出循环体、循环变量、循环初始值以及终止值，并且能够确定产生的结果不会对下一次循环产生影响，那么利用多处理器甚至多主机对循环进行加速就成为可能。

　　超流水线执行需要经过以下几个步骤：

• 负荷探测：通过负荷探测来寻找程序负荷最重的地方。很显然，只有加速程序负荷最重的地方的运行速度，才有加速的意义。
  
• 控制流分析：控制流分析能够从机器码角度分析程序中的循环体。只有找到了循环体，才能够继续分析循环体中变量的依赖关系。
  
• 数据流分析：数据流分析判断循环体种各个变量的依赖关系。只要循环体内所有变量间接依赖的值都在循环体外部定义，这样的循环才可以进行并行计算。
  
• 代码片段的分离：找到适合进行并行计算的循环体后，需要分离该循环体所设计的代码片断，以及其所依赖的变量值。分离过程中，仅仅分离与系统API(应用程序接口)调用、输入/输出操作无关的代码，使得分离出来的代码具有操作系统平台无关性。
  

　　3 总结

　　通过本文提出的方案，并借助分布式服务器技术及集群系统的理念，所构建的集群具有以下一些特点：

• 海量的存储空间：通过避免冗余的存储方式，以及强大的数据重建机制，整合广大用户的存储空间，获得了海量的存储能力，同时允许一定比例用户的任意离线而不破坏系统数据的完整性。
  
• 超流水线执行的能力：能够自动寻找程序中可以并行执行的部分，充分利用并行执行机制，使得任何非多线程程序都能得到最大的执行效率，而不需要专门针对并行处理编写专用的程序。
  
• 高度可伸缩的体系：系统基于对等方式运行，任何工作站/服务器的加入、退出都不会影响整个系统的运行，并且具有一定的异构能力。超流水线执行能够忽略工作站的操作系统的差异。
  
• 完全透明的负载均衡：通过抢先式进程迁移(可以透明地在任何时候、任何地方迁移任何进程)，充分利用整个系统的资源和能力，再结合所提出的超流水线运行方式，使得系统能够以更小的粒度分配负载。
  
• 高可靠性：无论是进程迁移还是超流水线执行，在计算节点失效后都允许任务的重新启动，不会引起执行的失败。
  
• 易操作性：对分布式存储以及分布式计算的实现都是透明的，无需特殊编程，任何应用都能立即从中获得好处。
  

　　随着Internet带宽限制被逐步打破，信息高速公路的建立和完善，本系统提供的集群方案，将在集群应用领域开辟新天地。本文只是从技术的角度讨论问题，实际运用中还必须考虑认证权限、合法性、版权问题等一系列的非技术问题。

　　参考文献　

　　1 Dobbertin H. The Status of MD5 After a Recent Attack. CryptoBytes, 1996
　　2 Adams C. RFC 2114 The CAST－128 Encryption Algorithm, 1997
　　3 Brand Per, Haridi Seif, Klintskog Erik, et al. An Architecture for Distributed Programing Platforms. Swedish Institute of Computer Science, 2000. http://ww.sics.se/~seif/distribution.html
　　4 Rawn Shah. Linux Clustering Cornucopia. http://www－900.ibm.com/developerWorks/cn/ linux/cluster/lw－clustering_eng.shtml, May 2000

[摘要] 面对宽带数据的急剧增长，海量存储将成为限制发展的“瓶颈”。文章提出基于网络的分布式海量存储及运算方案。该方案通过网络各服务器间的协同工作，利用特征码避免相同资源的冗余存储，加入纠错码以进行差错重建，利用进程迁移平衡负载，采用超流水线执行技术加速程序运行速度，最终实现网络信息资源及存储资源的共享。

[关键词] 海量存储；进程迁移；分布式存储；并行运算

[Abstract] Alongside the sharp growth of wide band data, successively come "bottleneck" restrictions from mass storage. In view of the situation above, this letter presents a formula for distributed mass storage and computing. All servers work concertedly, exploiting condition code to avoid redundant storage, using error correction code to reconstruct the lost data, balancing load through process migration, and, as well, accelerating execution by super pipeline computing to achieve the share of both information resource and storage resource.

[Keywords] Mass storage; Process migration; Distributed storage; Concurrent computing