云存储系统数据高效编码方法转让专利
申请号 : CN201310278650.8
文献号 : CN103309742B
文献日 : 2016-07-06
发明人 : 张广艳 , 舒继武 , 郑纬民
申请人 : 清华大学
摘要 :
权利要求 :
1.一种云存储系统数据高效编码方法,其特征在于,所述云存储系统包括多个数据存储服务器和多个接入客户端,所述方法包括以下步骤:S1:每个接入客户端根据各自不同的启发式算法生成不同的柯西矩阵,并根据所述柯西矩阵和多个调度生成方法生成多个调度策略,其中,所述调度策略为所述柯西矩阵与其对应的执行数据编码所需异或操作顺序的调度的组合,并从所述多个调度策略中根据执行异或操作次数选择操作次数最少的第一调度策略;
S2:所述数据存储服务器对所述多个接入客户端中每个接入客户端的第一调度策略进行比较,以得到执行异或操作次数最少的最优调度策略;
S3:所述多个接入客户端根据所述最优调度策略对用户发送的数据进行编码,其中,所述编码的编码方式为柯西里德-所罗门编码,并将所述数据和编码所得冗余数据存储到所述多个数据存储服务器上。
2.如权利要求1所述的云存储系统数据高效编码方法,其特征在于,所述步骤S1具体包括:S11:所述每个接入客户端根据一个生成柯西矩阵的启发式算法生成一个柯西矩阵,其中,所述生成柯西矩阵的启发式算法可以有多个;
S12:所述每个接入客户端分别根据多种求调度的启发式算法,计算对所述柯西矩阵的求取执行数据编码所需的异或操作顺序的调度,并从所述每个柯西矩阵的多个调度中选择执行异或操作次数最少的第一调度策略。
3.如权利要求1所述的云存储系统数据高效编码方法,其特征在于,所述数据存储服务器根据多个第一调度策略中的异或次数得到最终异或次数最少的最优调度策略。
4.如权利要求1所述的云存储系统数据高效编码方法,其特征在于,所述步骤S3具体包括:S31:接入客户端创建数据缓存区接收原始数据,直至k个数据块完全到达所述数据缓存区;
S32:根据所述最优调度策略对所述k个数据块进行编码,得到m个纠删码块;
S33:将所述k个数据块和所述m个纠删码块存入不同的k+m个数据存储服务器以实现数据冗余保护。
说明书 :
云存储系统数据高效编码方法
技术领域
背景技术
数据在出错时能及时恢复。纠删码编码使得云存储系统的部署成本大大降低。但是利用纠
删码的云存储系统在数据写入时必须对每k个数据块进行编码操作以得到纠删码,如何提
高编码效率是个技术挑战。
了编码的性能,但是当k,m,w较大时,柯西矩阵的个数 是组合问题,在可以接
受的一定时间内无法找到含“1”的个数最小的柯西矩阵;第二,利用执行数据编码所需异或
操作顺序的调度进行数据编码,调度就是柯西矩阵的新的异或操作序列,以期望利用中间
结果加速后续纠删码元素的计算,减少重复计算。但是,目前为止调度算法都是启发式的,
用它们对一个柯西矩阵求取调度时各自所得到的调度无法保证是所有调度方法中最优的,
并且 个柯西矩阵中究竟哪一个会产生比较好的调度,目前为止没有发现好的
规律。
发明内容
高数据写入云存储系统的效率。
骤:S1:每个接入客户端根据各自不同的启发式算法生成不同的柯西矩阵,并根据所述柯西
矩阵和多个调度生成方法生成多个调度策略,并从所述多个调度策略中根据执行异或操作
次数选择操作次数最少的第一调度策略;S2:所述数据存储服务器对所述多个接入客户端
中每个接入客户端的第一调度策略进行分析,以得到执行异或操作次数最少的最优调度策
略;S3:所述多个接入客户端根据所述最优调度策略对用户发送的数据进行编码,并将所述
数据和编码所得冗余数据存储到所述多个数据存储服务器上。
性能;另外,在接入客户端上,采用分布式执行选择框架的方式,可以快速地生成目前技术
水平下最优的编码方案;同时,该方法还可以提高数据写入云存储系统的效率。
以有多个;S12:所述每个接入客户端分别根据多种求调度的启发式算法,计算对所述柯西
矩阵的求取执行数据编码所需的异或操作顺序的调度,并从所述每个柯西矩阵的多个调度
中选择执行异或操作次数最少的第一调度策略。
k个数据块进行编码,得到m个纠删码块;S33:将所述k个数据块和所述m个纠删码块存入不
同的k+m个数据存储服务器以实现数据冗余保护。在本发明的实施例中,所述调度策略为所
述柯西矩阵与其对应执行数据编码所需异或操作顺序的调度的组合。
附图说明
具体实施方式
图描述的实施例是示例性的,仅用于解释本发明,而不能理解为对本发明的限制。
本发明的限制。此外,术语“第一”、“第二”仅用于描述目的,而不能理解为指示或暗示相对重要性。
发明中的具体含义。
或操作次数最少的第一调度策略。其中,第一调度策略即为该接入客户端的多个调度策略
中的执行异或操作次数最少的调度策略。调度策略为柯西矩阵与其对应的执行数据编码所
需异或操作顺序的调度的组合。具体而言,步骤S101包括:首先,每个接入客户端根据一个
生成柯西矩阵的启发式算法生成一个柯西矩阵,其中,生成柯西矩阵的启发式算法可以有
多个。其次,每个接入客户端分别根据多种求调度的启发式算法,计算对其柯西矩阵的求取
执行数据编码所需的异或操作顺序的调度,从而得到多个调度策略,并从每个柯西矩阵的
多个调度中选择执行异或操作次数最少的调度策略,作为第一调度策略。
较多个接入客户端生成的多个第一调度策略的对应的调度中异或次数的多少,并选择调度
中异或次数最少的第一调度策略作为最终的最优调度策略。
务器上。换言之即,接入客户端利用所得最优调度策略对接收的用户数据进行编码得到用
于数据恢复的冗余数据,并将用户数据和编码所得冗余数据存储到数据存储服务器上。具
体而言,首先多个接入客户端创建数据缓存区接收用户数据,直至k个数据块完全接收并存
入该数据缓存区后,接入客户端根据最优调度策略对k个数据块进行编码,并得到m个纠删
码块,最后将该k个数据块和m个纠删码块存入不同的k+m个数据存储服务器以实现数据冗
余保护,从而可节省存储空间。需要说明的是,在该示例中,由于用户发送的数据的重要程
度不同,因此,用户会根据不同类型的数据选择不同的数据保护强度,具体而言,用户根据
具体的数据类型,选择特定的柯西编码配置参数,从而根据多种特定的配置参数为云存储
系统生成当前技术水平下最优的数据编码方案。进一步地,对于采用特定柯西编码配置参
数的数据存储器,可以一次运行选定的最优的编码方案,而其后续的数据编码、解码都直接
利用该选定的最优编码方案,无需执行任何额外的操作,从而可节省数据处理的时间。
出目前技术水平下最优的编码方案。该方法主要包括三个部分:选择框架的建立、选择框架
的分布式执行和选择框架在云存储系统中的应用。
阵,最终生成柯西矩阵集合,例如为:{m0,m1,……,mt-1}。需要说明的是,如果发现有利于生成较好调度的柯西矩阵也可以动态的加到该集合。
等,并得出每个柯西矩阵对应的最好(matrix,schedule)组合(即第一调度策略),并最终得到第一调度策略的集合{(matrix0,schedule0),(matrix1,schedule1),……,(matrix t-1,schedule t-1)}。当然如果以后有新的、好的调度算法出现,也可以动态加入选择框架中。
schedule)组合。具体而言,首先对每个调度策略的异或次数|S|的多少进行比较,选出|S|
最小的组合(matrix,schedule)。如果|S|最小值对应多个组合,那么考虑到更新性能,选择
柯西矩阵m中“1”的个数最小的组合,例如为(:matrixbest,schedulebest),并将其存入文件中以备云存储系统应用。
案,从而可减少数据编码时的异或次数,提高编码性能。
布式执行选择框架,在保证能得到目前技术水平下最优编码方案的同时,加快执行速度。该
方法按柯西矩阵的生成方法向各台机器发送参数,即在每个接入客户端上根据一个生成柯
西矩阵的启发式算法生成一个柯西矩阵,并根据多个生成调度的启发式算法对该柯西矩阵
生成多个调度策略,该分布式执行选择框架具体包括以下步骤:
hm),以尽可能平均的将柯西矩阵集合{m0,m1,……,mt-1}中的多个柯西矩阵分布到多台机器上。其中,k表示数据块的个数,m表示纠删码块的个数,w表示编码字长。
的调度,最后发送该接入客户端上的第一调度策略(matrix,schedule)到数据存储服务器。
比较,选出|S|最小的组合(matrix,schedule)。如果|S|最小值对应多个组合,那么考虑到
更新性能,选择柯西矩阵m中“1”的个数最小的组合,例如为:(matrixbest,schedulebest),并将其存入文件中以备云存储系统应用。
下的最优编码方案。因此,分布式执行在保证得到目前技术水平下的最优编码方案的同时,
还加快了执行速度,从而可实现提前部署云存储系统。
区,此时满足编码条件。
次对k个准备好的数据块进行编码前都需要生成柯西矩阵以及求该柯西矩阵调度的时间,
从而在一定程度上提高了数据写入的效率。
下的最优编码方案。
如下:
ackQueue中等待数据写入成功与否的通知,然后将数据写入datanode,写入成功后通知
ackQueue将数据从ackQueue中移除并将其存入一个数据缓存区中,以为执行纠删码编码做
数据准备,直到k个64M数据块准备好之后,便可利用提前执行框架得到的目前最优调度对
这k个数据块进行编码了。待编码结束后得到m个纠删码块,需要将它们也放入dataQueue
中,再重新申请纠删码元素的block和datanode信息,在申请的过程中注意k个数据块和m个
纠删码块要分别放到不同的数据节点当中,以保证在一个节点失效时,只有k+m个块中的1
个块失效。
(k,m,w)配置下的编码方案,并用该方案进行数据编码。
性能;另外,采用分布式执行选择框架的方式,可以快速地生成目前技术水平下最优的编码
方案;同时,该方法还可以提高数据写入云存储系统的效率。
一定指的是相同的实施例或示例。而且,描述的具体特征、结构、材料或者特点可以在任何
的一个或多个实施例或示例中以合适的方式结合。
发明的范围由权利要求及其等同限定。