宽带网络为传输种类繁多的高速多媒体流提供了平台之后,来自各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负荷和网络负荷,来限制各个节点的过度竞争。
2 分布式计算方案
本系统的分布式存储涉及大量数据的编码与解码,因而需要大量的计算。系统利用空闲的节点,通过进程迁移技术把负载转移过去,以平衡负载;计算量特别大时,使用超流水线技术对单一指令流并行执行。
2.1 进程迁移
进程迁移指将一个进程从当前位置移动到指定的处理器上。此系统中是将某台计算机的存取进程执行过程,转移到另一台计算机上继续运行。迁移是透明的,也就是说被迁移进程本身并不知道它已被迁移到其他节点上。进程迁移使得负载从高负载处理器上流到了低负载处理器上,提高了资源利用效率。但目前的进程迁移技术,大都要求在同构的系统(相同或兼容的机器体系结构和指令集以及操作系统)上进行。
进程迁移可以作为操作系统的一部分,或者用户空间、系统环境的一部分,或者应用程序的一部分。根据应用的级别,其可分为3类(如图4所示):
图4 3种迁移方式示意图
进程迁移的主要工作就在于提取进程状态,然后在目的节点根据进程状态再生该进程。在现实中,一个进程拥有很多状态,并且随着操作系统的演化,进程状态也越来越多样。进程的状态一般可以分为以下几类:
2.2 超流水线执行
所谓超流水线执行,就是在保证结果正确性的前提下,通过并行执行串行指令流来提高程序运行速度。
程序结构分为3种:顺序执行、分支判断和循环。前两种都难以进行多流水线执行。因为几乎每一条指令都需要用到前面指令的计算结果,同样其执行结果也会影响后面指令的执行。然而不可忽视的一点就是:程序90%的执行时间恰恰花费在10%的代码中,而这10%的代码一般是循环或者递归调用。因此,对这10%的代码利用多处理器并行执行,能够大幅度提升程序的运行速度。而且由于循环体内的运算内容,一般仅仅与循环变量有关,如果能够分析出循环体、循环变量、循环初始值以及终止值,并且能够确定产生的结果不会对下一次循环产生影响,那么利用多处理器甚至多主机对循环进行加速就成为可能。
超流水线执行需要经过以下几个步骤:
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