纠删码技术与多副本技术都是分布式存储系统常用数据冗余策略,保证在一定数量的节点或硬盘发生故障后,数据依然可以被读取和修复.多副本技术因其简单高效被广泛用于GFS(Google File System)[4]、HDFS(Hadoop Distributed File System)[5]、Ceph[6]和Farsite[7]等分布式存储系统,优点在于读写性能高,且数据修复占用的网络带宽较少,缺点是存储空间利用率较低.与多副本技术相比,纠删码技术在相同容错的要求下有更高的存储利用率,因此纠删码冗余策略可与多副本技术形成优势互补.目前主流纠删码编解码方案的理论基础是RS编码(Reed-Solomon Code)[8],即一份原始数据经过纠删码编码后生成了k份原始数据分片和m份冗余数据分片,其中任意丢失m份,可以通过其他k份数据解码得到原始数据.纠删码技术同样被广泛用于各存储系统,如Facebook的f4[9]、微软的WAS(Windows Azure Storage)[10-11]、亚马逊的AWS(Amazon Web Services)[12]和OceanStore[13],以及TFS(Taobao File System)[14]、HDFS、Ceph和Openstack Swift[15]等.该技术主要问题在于纠删码数据对随机读写的支持不友好,写惩罚较大,且数据修复读写的比例最高可达k∶1,会占用更多的网络带宽.
纠删码数据的分片数明显增多,使纠删码数据的一致性保障变得复杂.针对数据一致性问题已有较多的研究工作, Brewer[16]提出的CAP(Consistency, Availability, Partition Tolerance)定理为数据一致性研究提供了概念和理论支撑.田俊峰等[17]对数据一致性从学术理论到工程应用的研究工作进行了较为全面系统的论述,在文中指出目前因果一致性的研究重点包括时钟方法优化、协议设计以及操作事务序列优化等方面.分布式共识算法Paxos[18-19]和Raft[20]则解决了当发生宕机或网络异常时,集群内部如何快速达成一致以保证集群节点间的数据一致性的问题.针对纠删码条带化数据的一致性保障和修复,目前大都沿用了多副本数据一致性保障的思路,为每个条带化数据组集中分配一个类似版本号的序列号,并通过日志和两阶段提交达成整个条带化数据组的一致[21],但这类方式没有关注纠删码条带化写入时额外的输入输出(Input/Output,IO)次数,同时在部分更新的场景下,需要未更新数据部分的所在存储节点参与IO.为了更好地支持条带化数据组的部分更新,减少纠删码数据写入的IO次数,本文提出了一种基于自修正数据标签(Self-Correction Data Tag,SCDT)的条带化数据写入方法和一致性检查方法,可以更好地应对条带化数据组的部分更新,同时有效减少纠删码数据写入的IO次数,提高一致性检查效率.
1 自修正数据标签
自修正数据标签是条带化数据组内各数据单元的一致性标识,本节将对自修正数据标签的设计和维护方法进行介绍.
1.1 SCDT设计
为了保证单调递增的特点,SCDT引入存储节点的启动次数以及CPU运行时间,以此判断同一条带化数据组内各数据单元写入的先后顺序,这也是条带化数据一致性检查的基本依据.SCDT由4个部分构成,每个部分为4字节(byte).第1部分包含两个字段,第一个字段为SCDT的版本信息,占用8 bit,用于针对不同版本的SCDT进行兼容处理;第二个字段是当次写入所更新的原始数据单元的序号信息,占用24 bit.原始数据单元在条带化数据组中的序号按照偏移量先后顺序编号,一个条带化数据组中有k份原始数据,则序号为0~k-1,如果当次写入所更新的原始数据单元的序号为0,1,2,则将第二个字段从低位到高位的0,1,2位置的二进制位设置为1,即为0…0 0111.第2部分为存储节点的启动次数;第3~4部分则分别为存储节点CPU运行时间的秒数和纳秒数.
SCDT第1部分中的第二个字段可以获取当次写入所更新的原始数据单元的序号,在基于SCDT进行条带化数据一致性检查时,只需要根据冗余数据单元的SCDT和当次写入所更新的原始数据单元的SCDT来判断该条带化数据组是否一致,不需要读取当次写入未更新的数据单元.第2~4部分共同保证了SCDT的单调递增,由于存储节点的节点启动次数会因为节点宕机、重启及误操作等差错场景导致单调递增难以保证,所以需要对存储节点的启动次数进行持久化记录和检查维护.
1.2 SCDT维护
SCDT中存储节点的启动次数容易受到外部操作的影响,为了降低这种影响,需要设计一套维护方法,包括初始化与持久保存和后续的检查与调整,分别记为InitAndPersistStore和CheckAndAdjust.
当存储节点中执行数据读写或服务启动初始化时,InitAndPersistStore过程对存储节点启动次数进行初始化和持久保存.首先要获取存储节点系统中记录的启动次数,记为绝对启动次数.考虑到系统中记录的启动次数可能被修改,无法保证启动次数的单调递增,因此需要一个持久化文件保存存储节点的启动次数.该持久化文件中记录了两个数值,一个是基准启动次数,初始值为0;另一个是相对启动次数,初始值为绝对启动次数,相对启动次数等于基准启动次数加上绝对启动次数.
如果持久化文件已经存在,则从该文件中读取基准启动次数和相对启动次数.如果相对启动次数不等于基准启动次数加绝对启动次数,则需要对基准启动次数和相对启动次数进行调整,使得等号成立;调整操作要求相对启动次数和基准启动次数都不能减小,用调整后的基准启动次数和相对启动次数更新所述持久化文件,其中相对启动次数作为SCDT的第二部分用于数据标签的生成.
CheckAndAdjust一般发生在条带化数据读写过程中.条带化数据组中每个数据单元都带有写入时生成的SCDT,其中包含当时的相对启动次数(记为preBootTimes)以及当时的CPU运行时间(记为preRunTimes).当发生数据读写时,数据单元带有的数据标签中的preBootTimes和 preRunTimes需要与此时持久化文件中记录的相对启动次数和基准启动次数进行检查、比较和调整.
如果持久化文件中记录的相对启动次数大于preBootTimes或者两者相等,但当前时刻CPU运行时间大于preRunTimes,则不需要调整持久化文件中的相对启动次数和基准启动次数;否则,根据preBootTimes和当前的绝对启动次数,向上调整相对启动次数和基准启动次数,保证相对启动次数等于基准启动次数加上绝对启动次数,同时要求相对启动次数要大于preBootTimes.使用调整后的基准启动次数和相对启动次数更新持久化文件,其中相对启动次数用于生成SCDT.
2 条带化数据一致性检查
为了更好地支持条带化数据组的部分更新,减少写入过程中的IO交互次数,本文在SCDT的基础上设计了带标签的条带化数据写入方法以及相应的条带化数据一致性检查方法,可以通过一个条带化数据的部分数据单元判定该条带化数据组的一致性.本节首先对条带化数据概念进行简要说明,然后从条带化数据写入方法和一致性检查方法两方面进行阐述.
2.1 条带化数据
图1
2.2 基于SCDT的写入方法
数据的写入方式决定了数据一致性检查的方法,因此,首先需要阐明本文设计的带标签条带化数据写入方法(Method of Writing Striped Data with Tag,MWSDT).
纠删码条带化数据存在两种写入方式:整条带写入方式和部分条带写入方式.采用整条带方式执行纠删码数据的写入时,如果写入的数据是整条带对齐,则将写入的数据通过纠删码技术生成k份原始数据单元和m份冗余数据单元,然后生成本次写入的SCDT,将该SCDT分别与k份原始数据单元和m份冗余数据单元拼接后,写入指定存储位置即可.如果写入的数据不是整条带对齐,需要先读取没有更新的原始数据单元和没有首尾对齐的原始数据单元,与本次写入的数据合并,构成整条带对齐的数据,然后编码生成m份冗余数据单元,与生成的SCDT拼接,将m份冗余数据单元和写入数据更新到的原始数据单元写入指定存储位置.
部分条带写入方式可以用于写入的数据不是整条带对齐时来执行纠删码数据的写入.具体的做法为,首先读取本次写入更新到的原始数据单元的旧数据,以及m份冗余数据单元的旧数据,用纠删码编码更新的方式计算m份冗余数据单元的新数据,然后生成SCDT,分别与更新的原始数据单元和m份冗余数据单元拼接后写入指定存储位置.
关于选择整条带方式还是部分条带方式执行纠删码数据写入,存在一个临界值,记为uThreshold.当更新的原始数据单元数大于uThreshold时,选择整条带方式执行纠删码数据的写入,否则选择部分条带方式执行纠删码数据写入.关于该临界值的分析计算将在性能分析对比中进行论述.另外,在执行条带化数据组的写入时,先执行m份冗余数据单元的写入,在确定m份冗余数据单元有写入成功的情况下,再执行更新的原始数据单元的写入,这样m份冗余数据中一定存在最新一次的SCDT,该SCDT将作为一致性检查的基准.
2.3 基于SCDT的一致性检查方法
在MWSDT的基础上,本文进一步设计了基于SCDT的条带化数据一致性检查方法(Consistency Check of Striped Data with Tag,CCSDT).对于一个条带化数据组,首先读取其中m份冗余数据单元,比较m份冗余数据单元的SCDT,如果m个SCDT全部相同,则从该SCDT中确定最近一次写入所更新的原始数据单元并读取.然后,将原始数据单元中的SCDT逐个与冗余数据单元的SCDT比较.如果原始数据单元的SCDT全部与冗余数据的SCDT相同,则该条带化数据组是一致的;否则该条带化数据组的数据单元不一致.
如果条带化数据组不一致,则需要确定待修复的数据单元.首先,选择m份冗余数据的SCDT中存储节点相对启动次数和CPU运行时间最大的作为基准SCDT,记为baseTag;根据baseTag中记录的原始数据单元的序号信息,读取相应的原始数据单元.然后,将读取的原始数据单元和m份冗余数据单元的SCDT与baseTag进行比较.确定与baseTag相同的标签集合,记为sameTagSet;与baseTag不相同的标签集合,记为diffTagSet,其中元素数量较少的集合所对应的数据单元即为需要修复的数据单元.因此,整个过程只需要读取m份冗余数据单元和最近一次写入所更新的原始数据单元,即可确定相应的条带化数据组的一致性.
3 性能测试分析对比
图2
图3
图3
不同纠删码参数下采用CCSDT前后的一致性检查时间对比
Fig.3
Comparison of consistency check time with or without CCSDT at different erasure coding parameters
由MWSDT可知,如果在一个条带化数据组内,更新的原始数据单元数为u(0<u≤k),采用整条带方式执行纠删码数据写入,需要读取写入数据未更新到的原始数据单元,IO次数为k-u+2,写入数据更新的原始数据单元和m份冗余数据单元写入,IO次数为u+m,发生IO次数合计为k+m+2.如果采用部分条带方式执行纠删码数据写入,需要读取本次更新的原始数据单元和m份冗余数据单元,IO次数为u+m,写入本次更新的原始数据单元和m份冗余数据单元, IO次数为u+m,发生IO次数合计为2(u+m).使k+m+2和2(u+m)相等,则可得临界值uThreshold=(k-m)/2+1.
IO交互次数是存储系统性能的重要影响因素,在完成相同的数据传输任务时,IO交互次数越少,则系统性能越高.为了验证MWSDT对IO交互次数的减少效果,设计如下测试.设固定条带单元大小1个chunk size为64 KB,纠删码参数固定为k=8,m=3,写入数据的大小(data size)依次为1~8个chunk size.统计采用MWSDT前后的IO次数,在固定纠删码参数k=8,m=3的情况下,写入数据字节数为1~8个chunk size,测试记录数据,如图2(a)所示,采用本文设计的带标签条带化数据写入方法能够降低写入过程的IO交互次数.在写入数据大小不满8个chunk size的情况下,当写入数据大小为1~4个chunk size时,MWSDT可以明显减少写入时的IO次数.但随着写入数据大小趋于8个chunk size,不采用MWSDT的写入方式带来的额外的IO次数逐渐减少,最终与MWSDT写入方式的IO次数持平,这是因为当写入数据逐渐趋近8个chunk size时,需要读取的旧数据会越来越少.
为了验证MWSDT对纠删码数据写入性能的提升,本文在一款自研分布式存储系统中实现MWSDT算法,对接上海某三甲医院的PACS进行对比测试.将其医疗影像数据以纠删码方式写入存储系统,在不同纠删码参数组合EC(k, m)情况下,统计采用MWSDT前后纠删码写入性能,如图2(b) 所示.在不同纠删码参数下,采用MWSDT后纠删码写入性能提升了1.6~2.4倍,并且提升倍数随k+m的增加而增加,这是因为不采用 MWSDT,纠删码写入的IO次数会随着k+m的变大而增加,而采用MWSDT后纠删码写入的IO次数只随m的变大而增加.
为了验证CCSDT对条带化数据一致性检查的效率提升,在MWSDT写入过程IO交互次数对比实验的基础上进行测试,参数设置等同前文所述.在不同的纠删码参数下,首先使用MWSDT以不同的data size写入纠删码数据,再使用CCSDT对所述条带化数据组进行一致性检查.然后,在不使用MWSDT 的情况下,以不同的data size写入纠删码数据,以现有方法对所述条带化数据组进行一致性检查.统计采用CCSDT前后的一致性检查需要的时间,结果如图3所示.当写入时的数据大小为1~2个chunk size时,CCSDT的一致性检查效率提升1.7~2.6倍.随着写入的data size增加至k个chunk size,CCSDT一致性检查需要读取更多的原始数据单元,因此逐渐与不采用CCSDT的一致性检查时间持平.
4 结语
根据纠删码条带化数据中原始数据单元和冗余数据单元的更新特点,考虑分布式存储系统中节点故障的场景,设计了自修正数据标签SCDT;针对纠删码条带化数据写惩罚大,以及一致性检查需要读取所有条带单元导致一致性检查效率低的问题,基于SCDT实现了条带化数据写入方法MWSDT和条带化数据一致性检查方法CCSDT,并通过实验测试进行效果验证.
研究显示,纠删码参数中取原始数据单元份数为k,在写入数据大小不足k个chunk size时,带标签条带化数据写入方法可以有效减少写入过程中的IO交互次数,提升纠删码数据写入性能,基于SCDT的条带化数据一致性性检查方法可以显著降低条带化数据的一致性检查时间.本文提出的方法为纠删码冗余策略在分布式存储系统中的应用提供了一套可行方案.
参考文献
Introducing PACS to the late majority. A longitudinal study
[J].
DOI:10.1007/s10278-008-9160-x
PMID:18979133
[本文引用: 1]
The purpose of this study was to study whether the benefits from introducing a picture archiving and communication systems (PACS) reported by innovators and early adopters also can be achieved by a hospital belonging to the "late majority" and to see whether such benefits are sustained, using report turnaround time (RTAT) as an indicator. Activity-related data was retrieved from the radiology information system (RIS) over a 2-year period. The median RTAT for preliminary reports was initially reduced from 12 to 2 h then increased to 3 h. For final reports, the median RTAT was initially reduced from 23 to 13 h then gradually reverted back to 22 h. Innovators and early adopters demonstrate not only that positive results can be achieved but also the importance of involving key personnel. We believe that such involvement and the focus on wider organizational concerns are important when introducing PACS to the late majority, both for achieving and sustaining positive results.
PACS: An overview of the technology and related issues
[J].
The Google file system
[J].DOI:10.1145/1165389.945450 URL [本文引用: 1]
The hadoop distributed file system
[C]//
Ceph:A scalable, high-performance distributed file system
[C]//
Farsite: Federated, available, and reliable storage for an incompletely trusted environment
[J].
Polynomial codes over certain finite fields
[J].DOI:10.1137/0108018 URL [本文引用: 1]
Facebook’s warm BLOB storage system
[C]//
Windows Azure Storage: A highly available cloud storage service with strong consistency
[C]//
Erasure coding in windows azure storage
[C]//
Exploring the cloud from passive measurements: The Amazon AWS case
[C]//
OceanStore: An architecture for global-scale persistent storage
[J].
DOI:10.1145/356989.357007
URL
[本文引用: 1]
OceanStore is a utility infrastructure designed to span the globe and provide continuous access to persistent information. Since this infrastructure is comprised of untrusted servers, data is protected through redundancy and cryptographic techniques. To improve performance, data is allowed to be cached anywhere, anytime. Additionally, monitoring of usage patterns allows adaptation to regional outages and denial of service attacks; monitoring also enhances performance through pro-active movement of data. A prototype implementation is currently under development.
Towards robust distributed systems (abstract)
[C]//
数据因果一致性研究综述
[J].
DOI:10.11959/j.issn.1000-436x.2020055
[本文引用: 1]
数据因果一致性是分布式存储中保障数据一致性的重要方案之一，目前的因果一致性方案研究重点包括时钟方法的优化、协议的设计以及操作事务序列的优化等方面。实际上云环境除了时钟漂移、查询放大等情况之外，还存在木马、不可信第三方等不安全因素，以致于破坏因果一致性元数据、用户操作结果的一致性，甚至影响存储环境的可用性。从一致性存储性能提升和安全保障角度出发，结合区块链等共识机制，对比分析了时钟同步方法、数据复制策略、服务端协议的分析设计以及操作事务序列化等研究方向，总结讨论了它们的的原理、优势、局限性以及安全约束方面的不同效用，进而指出未来的发展趋势和后续研究方向，期望对该领域的研究起到参考和帮助作用。
Survey on the causal consistency of data
[J].
DOI:10.11959/j.issn.1000-436x.2020055
[本文引用: 1]
Causal consistency is one of the important projects to ensure data consistency in distributed storage.The current research focuses on causal consistency including optimization of clock method,design of the protocol and the optimization of operation transaction sequence.In the actual cloud environment,in addition to clock skew and query amplification,there are also insecure factors such as Trojans and untrusted third parties,which will destroy the causal consistency metadata stored by users,and the consistency of user’s operating results,even affect the availability of the storage environment.From the perspective of performance improvement and security in distributed storage,the clock synchronization,data replications,analysis and design of server protocol,related research progress of the serialization of operational affairs were introduced combined with consensus mechanisms such as blockchain.At the same time,their principlest,advantages,limitations,and different utilities in terms of security constraints were discussed,and then the future development trends and follow-up research directions were point out at last,which would provide a reference and help for the research in this field.
The part-time parliament
[J].
In search of an understandable consensus algorithm
[C]//
