Nothing Special   »   [go: up one dir, main page]

CN112732203B - 一种再生码构造方法、文件重构方法及节点修复方法 - Google Patents

一种再生码构造方法、文件重构方法及节点修复方法 Download PDF

Info

Publication number
CN112732203B
CN112732203B CN202110348155.4A CN202110348155A CN112732203B CN 112732203 B CN112732203 B CN 112732203B CN 202110348155 A CN202110348155 A CN 202110348155A CN 112732203 B CN112732203 B CN 112732203B
Authority
CN
China
Prior art keywords
block
coding
blocks
code
file
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN202110348155.4A
Other languages
English (en)
Other versions
CN112732203A (zh
Inventor
朱兵
曾志伟
赵旭煜
王伟平
王建新
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Central South University
Original Assignee
Central South University
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Central South University filed Critical Central South University
Priority to CN202110348155.4A priority Critical patent/CN112732203B/zh
Publication of CN112732203A publication Critical patent/CN112732203A/zh
Application granted granted Critical
Publication of CN112732203B publication Critical patent/CN112732203B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0602—Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
    • G06F3/0614—Improving the reliability of storage systems
    • G06F3/0619—Improving the reliability of storage systems in relation to data integrity, e.g. data losses, bit errors
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
    • G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
    • G06F3/0638—Organizing or formatting or addressing of data
    • G06F3/064—Management of blocks
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0668—Interfaces specially adapted for storage systems adopting a particular infrastructure
    • G06F3/067—Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L67/00—Network arrangements or protocols for supporting network services or applications
    • H04L67/01—Protocols
    • H04L67/10—Protocols in which an application is distributed across nodes in the network
    • H04L67/1097—Protocols in which an application is distributed across nodes in the network for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Human Computer Interaction (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Computer Security & Cryptography (AREA)
  • Probability & Statistics with Applications (AREA)
  • Quality & Reliability (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)

Abstract

本发明公开了一种再生码编码方法，包括获取组合设计和存储数据块；对区组排序并编号，统计元素出现的区组及位置，得到文件符号；对原文件进行编码，得到编码块；为每个编码块分配一个不同的文件符号；将每个元素一致的文件符号集合所对应的编码块放置在同一存储节点中，得到再生码。本发明还公开了一种基于所述的再生码构造方法的文件重构方法及节点修复方法。本发明提出的再生码构造方法参数限制宽松且能达到辛格尔顿上界，文件重构和节点修复过程运算简单，同时节点修复效率较高。

Description

一种再生码构造方法、文件重构方法及节点修复方法
技术领域
本发明具体涉及一种再生码构造方法、文件重构方法及节点修复方法。
背景技术
在当今信息爆炸的时代，如何安全可靠地存储海量数据成为了亟需解决的问题。传统的文件存储系统已不能满足可用性和可扩展性等要求，分布式存储系统(DistributedStorage System)应运而生。该系统利用分布式技术，将存储节点通过网络联结起来形成一个能存储海量数据的集群。分布式系统将数据文件分散放置于多个存储节点中，由于网络故障或物理损坏，单个存储节点可能会失效，因此分布式系统必须引入冗余信息来保证可靠性。常见的冗余策略有多副本策略和纠删码策略。多副本策略就是把原文件复制若干倍后再存储，当有节点失效时，替换节点就可以直接从它的副本中复制数据，因此系统中只要存在一个完整的数据副本，源文件就能正常使用；但这种方案存储效率和系统可靠性较低。纠删码策略采用纠删码处理原始文件，常用的纠删码为(n, k)最大距离可分(MaximumDistance Separable, MDS)码，即将原始文件分成大小相等的k份，由这k份文件经线性编码后生成n-k份冗余信息，利用n个节点存储n个线性无关的编码块，终端用户可以通过连接到任意k个节点恢复出原始文件。显然纠删码策略存储效率更高，但是实现也更复杂，应用难度大。
在分布式存储系统中，利用n个节点存储大小为B的原始数据，每个节点存储的数据量为α，终端用户从n个存储节点中的任意k个下载数据即可恢复出原始文件，该过程被称为文件重构过程。当存储系统中有存储节点失效时，为了保证分布式系统的整体功能，需要对该失效节点进行恢复，该过程被称为节点修复过程。
RS（Reed-Solomon）码是一种常见的MDS码，RS码的节点修复过程为：先建立一个新的存储节点，再连接至k个节点下载数据并恢复出原始文件，利用原始文件经线性编码后再向该新节点存储相应的数据。图1为现有技术中RS码修复过程示意图，易见，为恢复一个节点中的存储信息而下载了k个节点的存储数据，修复节点时的数据传输量远大于节点的存储量，即节点的修复过程需要浪费大量的网络带宽。
为了降低修复过程中的修复带宽，文献[A. G. Dimakis, P. B. Godfrey, Y.Wu, M. J. Wainwright, and K. Ramchandran, “Network coding for distributedstorage systems,” IEEE Trans. Inf. Theory, vol. 56, no. 9, pp. 4539–4551,Sep. 2010] 引入了网络编码的概念，即在修复失效节点时，取较多的节点参与修复，且参与修复的节点先将本节点内的数据经过线性组合后再上传，这能极大地降低修复失效节点的带宽消耗，该文使用信息流图对分布式存储系统进行建模，并对其进行最小割分析，如图2所示。图2中S表示信息源，即原始数据。每个存储节点
Figure 8559DEST_PATH_IMAGE001
由输入节点
Figure 881837DEST_PATH_IMAGE002
、输出节点
Figure 58740DEST_PATH_IMAGE003
和有向边
Figure 308456DEST_PATH_IMAGE004
来表示，有向边上的权值为该节点的数据存储量，其值均为α。DC (Data Collector)表示数据收集器，数据收集器DC收集任意k个节点的数据，就能恢复原始数据；从d个节点获取数据，就能修复失效节点。对图2进行最小割分析，将信息源S和数据收集者DC分开的曲线称为该信息流图的割，该曲线切过的所有有向边的权值和称为割的值。根据最大流-最小割定理，当最小割的值不小于信息源S中的原始数据量大小时，DC能够恢复原始数据。基于对信息流图的最小割分析，Dimakis等人给出了单节点修复带宽γ和单节点存储量α之间的折衷曲线，所谓再生码(Regenerating Codes)即α和γ取该折衷曲线上的点时对应的编码。在折衷曲线上存在两类特殊的点，即数据存储量α最小值点和修复带宽γ最小值点，分别对应于：最小存储再生码(Minimum-Storage Regenerating, MSR)，称为MSR编码(MSR Codes)，
Figure 762571DEST_PATH_IMAGE005
最小带宽再生码(Minimum-Bandwidth Regenerating, MSR)，称为MBR编码(MBRCodes)，
Figure 682117DEST_PATH_IMAGE006
再生码的修复过程如下：新建节点从完好的存储节点中任选d个存储节点下载数据，每个节点下载的数据量为β，即再生码的修复带宽
Figure 221682DEST_PATH_IMAGE007
，且修复带宽随着d的增大而减小，这是因为随着参与修复的辅助节点数目d的增加，每个节点修复时传输的数据量β变小，且β变小的速度比d增大的速度更快，从而使总修复带宽减小。可见再生码的修复带宽优于RS码，但再生码的修复过程中的节点访问数d>k。另外，修复节点需要对其存储的数据执行随机线性网络编码操作，为了满足所有编码包是相互独立的，再生码的运算需要在一个较大的有限域内进行。
根据节点中存储的信息是否为校验信息，可以将节点分为：
1）系统节点(Systematic Nodes)：系统节点存储的是未经编码的原始文件信息；
2）校验节点(Parity Nodes)：校验节点存储的是经过编码后的文件信息，也就是冗余信息。
根据修复后的节点数据是否与原失效节点数据相同可以将修复策略分为：
1）功能修复(Functional Repair)：该修复方案修复后的节点数据与原失效节点数据不一定相同，但修复后生成的节点与其他节点组成的分布式存储系统仍具有MDS特性；
2）精确修复(Exact Repair)：该修复方案下修复后的节点数据原失效节点数据相同；
3）混合修复(Hybrid Repair)：该修复方案对系统节点(存储未编码数据)进行精确修复，而对非系统节点(存储冗余数据）不需精确修复只需修复后使新的分布式系统仍满足 MDS 特性即可。
基于Dimakis等人提出的再生码，文献[C. Tian, B. Sasidharan, V. Aggarwal,V. A. Vaishampayan, and P. V. Kumar, “Layered exact-repair regenerating codesvia embedded error correction and block designs,” IEEE Trans. Inf. Theory,vol. 61, no. 4, pp. 1933–1947, Apr. 2015]提出了一种基于组合设计放置策略的精确修复再生码。组合设计是一组满足某些特性的子集的集合（子集被称为区组）。一个给定的区组设计由(X,B)指定，带有参数(r,n)，r≤n，即X是具有n个元素的集合，B是X的r元子集的集合。在该文中主要使用了斯坦纳系(Steiner systems)和重复组合区组设计(DuplicatedCombination Block Design, DCBD)这两种设计，实现了分布式存储系统参数限制为[n,k,d=k=n-1]，[n,k=n-2,d=n-1]和[n,k,d>k]的精确构造。这种构造比MSR码和MBR码之间的空间共享性能更好，并且是实现这种性能的第一类编码。此外，该构造可以在参数限制为[n,k,d=k=n-1]的最优功能修复折衷曲线上达到不平凡的点，并且在高码率下渐近最优。但是该文提出的构造方式对参数限制比较严格，只容许1~2个节点的失效，实用性不高。
发明内容
本发明的目的之一在于提供一种再生码构造方法，该方法的构造过程简单，对参数限制更为宽松。
本发明的目的之二在于还提供一种基于所述的再生码构造方法的文件重构方法。
本发明的目的之三在于还提供一种基于所述的再生码构造方法的节点修复方法。
本发明提供的这种再生码构造方法，包括如下步骤：
S1．获取组合设计和存储数据块；
S2．对区组排序并编号，统计元素出现的区组及位置，得到文件符号；
S3．对数据块进行编码，得到编码块；
S4．为每个编码块分配一个不同的文件符号；
S5．将每个元素一致的文件符号集合所对应的编码块放置在同一存储节点中，得到再生码。
步骤S1，获取的组合设计具体为，选择满足组合条件的t-设计
Figure 9510DEST_PATH_IMAGE008
，λ为t-平衡数，表示任意t元子集均出现在λ个区组中，其中，
记b为区组个数，
Figure 442765DEST_PATH_IMAGE009
；
记r为元素重复度，
Figure 657846DEST_PATH_IMAGE010
；
组合条件为：
Figure 950287DEST_PATH_IMAGE011
；
其中，t为子集的元素数；v为设计的阶，具体为设计中不同元素的总数；m为区组容量，具体为一个区组中的元素个数；
获取的存储数据块具体为，设存储原文件大小为M，将原文件拆分成
Figure 276226DEST_PATH_IMAGE012
个大小相等的数据块。
步骤S2的文件符号设为
Figure 344414DEST_PATH_IMAGE013
，其中1≤i≤b，1≤j≤m，b为区组个数，m为区组容量；同时
Figure 464817DEST_PATH_IMAGE014
表示元素h出现在第i个区组中的第j个位置；将区组编号记为B 1,B 2,…,B b ，对于区组B i ，将其中的元素由小到大顺序排列，位置编号记为{1,2,…,m}。
步骤S3具体为利用双层编码策略对数据块进行编码；外层获得的MDS码构造如下：
利用参数为
Figure 978975DEST_PATH_IMAGE015
MDS码对
Figure 233238DEST_PATH_IMAGE016
个数据块进行编码，获得b(m-t+1)个编码块，其中b为区组个数，m为区组容量，t为子集的元素数，λ为t-平衡数，表示任意t元子集出现在λ个区组；
内层获得的MDS码构造如下：
将上述利用外层编码得到的b(m-t+1)个编码块均分为b组，利用参数为(m,m-t+1)MDS码对每组中的m-t+1个编码块进行二次编码，最终得到bm个编码块。
步骤S4具体包括，为上述获得的每一个编码块分配一个文件符号作为标识，不失一般性地，将
Figure 782031DEST_PATH_IMAGE017
的前
Figure 338915DEST_PATH_IMAGE018
个文件符号
Figure 340369DEST_PATH_IMAGE019
作为外层编码生成的冗余块的标识；将
Figure 883477DEST_PATH_IMAGE020
的文件符号
Figure 286776DEST_PATH_IMAGE021
作为内层编码生成的冗余块的标识，其中，
Figure 14561DEST_PATH_IMAGE022
表示元素h出现在第i个区组中的第j个位置，m为区组容量。
步骤S5具体包括，每当发现一个文件符号
Figure 627945DEST_PATH_IMAGE023
，若其元素h与之前的文件符号
Figure 364957DEST_PATH_IMAGE024
不同，则分配一个新的存储节点并编号为h；对于每一个文件符号
Figure 357183DEST_PATH_IMAGE024
，若其元素h已分配存储节点，则将元素h相同的文化符号
Figure 632700DEST_PATH_IMAGE025
所对应的编码块存放到编码为h的存储节点中，则一个存储节点存储r个编码块，r为元素重复度；得到参数为[n,k=n-t,d=n-t+1]的再生码，n为节点个数，k为下载数据的个数，d为参与修复的节点个数，t为子集的元素数，
Figure 608747DEST_PATH_IMAGE026
表示元素h出现在第i个区组中的第j个位置。
本发明还提供一种包括上述再生码构造方法的文件重构方法，包括如下步骤：
A1．根据步骤S1~S5构造再生码；
A2．连接到存储节点；
A3．在下载当前编码块时，进行重构第一次判断；
A4．在完成一个编码块的下载后，进行重构第二次判断；
A5．利用内层及外层的MDS编码规则恢复原文件。
步骤A3的重构第一次判断具体包括，对于当前具有相同区组编号i 0的文件符号
Figure 883870DEST_PATH_IMAGE027
，是否已经下载了m-t+1个文件符号
Figure 996183DEST_PATH_IMAGE028
所代表的编码块，
Figure 190404DEST_PATH_IMAGE029
表示元素h出现在第i 0个区组中的第j个位置，m为区组容量；若判断为是，则停止下载当前编码块；若判断为否，则下载当前编码块；
步骤A4的重构第二次判断具体包括，判断是否已经下载了
Figure 388167DEST_PATH_IMAGE030
个编码块；若判断为是，则停止下载过程，若判断为否，则继续下载过程，b为区组个数，t为子集的元素数，λ为t-平衡数，表示任意t元子集出现在λ个区组中。
本发明还提供了一种包括上述的再生码构造方法的节点修复方法，包括如下步骤：
B1．根据步骤S1~S5构造再生码；
B2．确定失效节点的序号；
B3．在组合设计中确定失效节点出现过的区组序号；
B4．从n-t+1个节点中下载编码块，共下载r(m-t+1)个编码块，r为元素重复度，n为节点个数，t为子集的元素数，m为区组容量；
B5．将步骤B4下载的r(m-t+1)个编码块分成r组，每组的编码块具有相同的区组编号i；
B6．对每一组编码块利用内层获得的MDS码的编码规则恢复一个编码块；将r组编码块恢复出r个编码块；
B7．将恢复出的r个编码块存储到一个新的存储节点，并将此节点加入原存储系统中完成修复过程。
步骤B2具体为，从剩下的完好节点中对元素编号，记为{h 1,...,h v-1}，将元素编号与
Figure 466981DEST_PATH_IMAGE031
设计中的元素对比，确定失效节点的序号h 0；其中v为设计的阶，m为区组容量，λ为t-平衡数；步骤B3的区组序号记为{i 1,...,i r }；步骤B4的文件符号具体为
Figure 309166DEST_PATH_IMAGE032
，表示h 0出现在第i个区组中的第j个位置，
Figure 815234DEST_PATH_IMAGE033
。
本发明提出的再生码构造方法参数限制宽松且能达到辛格尔顿上界，文件重构和节点修复过程运算简单，同时节点修复效率较高。
附图说明
图1为现有技术中RS码修复过程示意图。
图2为现有技术中分布式存储系统的信息流图。
图3为本发明方法的再生码构造方法的流程示意图。
图4为本发明方法的再生码构造方法的实施例存储编码示意图。
图5为本发明方法的文件重构方法的流程示意图。
图6为本发明方法的文件重构方法的实施例示意图。
图7为本发明方法的节点修复方法的流程示意图。
图8为本发明方法的节点修复方法的实施例示意图。
具体实施方式
如图3为本发明方法的再生码构造方法的流程示意图。本发明提供的这种再生码构造方法，包括如下步骤：
S1．获取组合设计和存储数据块；获取的组合设计具体为，选择满足组合条件的t-设计
Figure 500293DEST_PATH_IMAGE034
，λ为t-平衡数，表示任意t元子集均出现在λ个区组中，其中，
记b为区组个数，
Figure 976274DEST_PATH_IMAGE035
；
记r为元素重复度，
Figure 63179DEST_PATH_IMAGE010
；
组合条件为：
Figure 740148DEST_PATH_IMAGE036
其中，t为子集的元素数；v为设计的阶，具体为设计中元素的种类数；m为区组容量，具体为一个区组中的元素个数；
获取的存储数据块具体为，设存储原文件大小为M，将原文件拆分成相等大小的
Figure 912503DEST_PATH_IMAGE037
个数据块。
S2．对区组排序并编号，统计元素出现的区组及位置，得到文件符号；文件符号设为
Figure 707021DEST_PATH_IMAGE038
，其中1≤i≤b，1≤j≤m，b为区组个数，m为区组容量；同时
Figure 382853DEST_PATH_IMAGE039
表示元素h出现在第i个区组中的第j个位置；将区组编号记为B 1,B 2,…,B b ，对于区组B i ，将其中的元素先后顺序排列，编号记为位置{1,2,…,m}。
S3．利用双层编码策略对数据块进行编码；外层获得的MDS码构造如下：
利用参数为
Figure 230724DEST_PATH_IMAGE040
MDS码对
Figure 15009DEST_PATH_IMAGE041
个数据块进行编码，获得b(m-t+1)个编码块，其中b为区组个数，m为区组容量，t为子集的元素数，λ为t-平衡数，表示任意t元子集出现在λ个区组；
内层获得的MDS码构造如下：
将上述利用外层编码得到的b(m-t+1)个编码块均分为b组，利用参数为(m,m-t+1)MDS码对每组中的m-t+1个编码块进行二次编码，最终得到bm个编码块。
S4．为上述获得的每一个编码块分配一个文件符号作为标识，不失一般性地，将
Figure 973738DEST_PATH_IMAGE017
的前
Figure 35235DEST_PATH_IMAGE042
个文件符号
Figure 788427DEST_PATH_IMAGE043
作为外层编码生成的冗余块的标识；将
Figure 810741DEST_PATH_IMAGE044
的文件符号
Figure 307581DEST_PATH_IMAGE026
作为内层编码生成的冗余块的标识，其中，
Figure 223585DEST_PATH_IMAGE045
表示元素h出现在第i个区组中的第j个位置，m为区组容量。
S5．将每个元素一致的文件符号集合所对应的编码块放置在同一存储节点中，得到再生码。具体包括，每当发现一个文件符号
Figure 537891DEST_PATH_IMAGE046
，若其元素h与之前的文件符号
Figure 906556DEST_PATH_IMAGE047
不同，则分配一个新的存储节点并编号为h；对于每一个文件符号
Figure 207087DEST_PATH_IMAGE048
，若其元素h已分配存储节点，则将元素h相同的文化符号
Figure 243176DEST_PATH_IMAGE049
所对应的编码块存放到编码为h的存储节点中，则一个存储节点存储r个编码块，r为元素重复度；得到参数为[n,k=n-t,d=n-t+1]的再生码，n为节点个数，k为下载数据的个数，d为参与修复的节点个数，t为子集的元素数。
在具体实施方式中，给出一个参数M=39，n=8，d=7，k=6的存储编码实例，如图4为本发明方法的再生码构造方法的实施例存储编码示意图。具体为如下步骤：
步骤（1）、该分布式存储系统取得39个初始数据块（该处的数据块是指将原文件经过步骤S1后获得），利用步骤S3中的双层编码策略进行编码，得到56个编码块。
该参数为[n=8,k=6,d=7] 分布式存储系统，是基于2-(8,4,3)设计来构建的，
2-(8,4,3)进排序后如下：{{0,1,2,3},{0,1,2,4},{0,1,5,6},{0,2,5,7},{0,3,4,5},{0,3,6,7},{0,4,6,7},{1,2,6,7},{1,3,4,6},{1,3,5,7},{1,4,5,7},{2,3,4,7},{2,3,5,6},{2,4,5,6}}。
步骤（2）、统计其内元素出现的区组及位置，结果如下：
Figure 709143DEST_PATH_IMAGE050
Figure 565103DEST_PATH_IMAGE051
,
Figure 669326DEST_PATH_IMAGE052
Figure 684555DEST_PATH_IMAGE053
Figure 216030DEST_PATH_IMAGE054
；
步骤（3）、为56个编码块各分配一个文件符号
Figure 293708DEST_PATH_IMAGE055
，其中
Figure 811408DEST_PATH_IMAGE056
表示元素h出现在第i个区组中的第j个位置。
步骤（4）、双层编码策略具体如下，内层编码利用参数为(4, 3)的MDS码进行编码，不失一般性地令每个区组中的最后一个文件符号所对应的编码块作为校验块，那么可得
Figure 556510DEST_PATH_IMAGE057
…
Figure 258887DEST_PATH_IMAGE058
外层编码利用参数为(42, 39)的MDS进行编码。在本实施例中，不失一般性地令
Figure 89440DEST_PATH_IMAGE059
所对应的编码块作为校验块，那么可得
Figure 394519DEST_PATH_IMAGE060
Figure 994128DEST_PATH_IMAGE061
Figure 867406DEST_PATH_IMAGE062
。
在本实施例中，为了保证校验符号之间相互独立，文件符号前的系数如x，x 2，x 3等为范德蒙矩阵不同行的数据。同时模加法运算均是在有限域内进行，本实施例将有限域设置为GF（43）。
步骤（5）、为不同的元素分配不同的存储节点，该实施例中共由0~7个元素，则需创建8个存储节点；将每个h一致的符号
Figure 559156DEST_PATH_IMAGE063
所对应的编码块放置在同一存储节点中，那么一个存储节点存储7个编码块，最终得到如图4所示的存储编码。
如图5为本发明方法的文件重构方法的流程示意图。基于所述再生码构造方法的文件重构方法包括如下步骤：
A1．根据步骤S1~S5构造再生码；
A2．连接到存储节点；
文件重构方法主要利用步骤S3生成的外层参数为
Figure 808872DEST_PATH_IMAGE064
的MDS码提供的冗余信息；原始数据块数目为
Figure 262987DEST_PATH_IMAGE065
，即增加了
Figure 307166DEST_PATH_IMAGE066
个冗余块，因此，在文件重构过程中需要收集
Figure 971366DEST_PATH_IMAGE067
个不同的编码块。在本实施方式中，最多取n-t个存储节点，用于下载数据。
A3．在下载当前编码块时，进行重构第一次判断；步骤A2的重构第一次判断具体包括，对于当前具有相同区组编号i 0的文件符号
Figure 759193DEST_PATH_IMAGE068
，是否已经下载了m-t+1个文件符号
Figure 333394DEST_PATH_IMAGE069
所代表的编码块，
Figure 423841DEST_PATH_IMAGE070
表示元素h出现在第i 0个区组中的第j个位置，m为区组容量，若判断为是，则停止下载当前编码块，若判断为否，则下载当前编码块；
A4．在完成一个编码块的下载后，进行重构第二次判断；步骤A3的重构第二次判断具体包括，判断是否已经下载了
Figure 716282DEST_PATH_IMAGE071
个编码块，若判断为是，则停止下载过程，若判断为否，则继续下载过程，b为区组个数，t为子集的元素数，λ为t-平衡数，表示任意t元子集均出现在λ个区组中；
A5．利用内层及外层的MDS编码规则恢复原文件；具体为已下载到
Figure 776642DEST_PATH_IMAGE071
个编码块时，若同一区组中编码块数目少于m-t+1个，那么利用外层
Figure 329983DEST_PATH_IMAGE072
MDS编码规则恢复编码块；若同一区组中编码块数目为m-t+1个，那么利用内层(m, m-t+1) MDS编码规则恢复编码块。
并不是每一次重构操作都需n-t个存储节点传输数据，而是只需下载
Figure 981544DEST_PATH_IMAGE073
不同的编码块即可结束文件传输过程，进而开始文件重构操作。
具体实施方式中，给出一个M=39，n=8，d=7，k=6的文件重构实例，如图6为本发明方法的文件重构方法的实施例示意图。具体说明如下：
步骤1)、在本实施例中，连接至Node 0~Node 5这6个节点进行文件重构操作。
步骤2)、Node 0需下载所有数据，Node 1需下载所有数据，Node 2需下载所有数据，Node 3中下载除文件符号
Figure 495702DEST_PATH_IMAGE074
对应的编码块外的所有数据，Node 4中下载除
Figure 625332DEST_PATH_IMAGE075
对应的编码块外的所有数据，Node 5中下载除
Figure 285377DEST_PATH_IMAGE076
对应的编码块外的所有数据，至此共下载39个编码块，数据下载过程结束。
步骤3)、利用外层(42, 39)MDS编码规程进行文件恢复。由于
Figure 842260DEST_PATH_IMAGE077
Figure 843714DEST_PATH_IMAGE078
Figure 901669DEST_PATH_IMAGE079
而从Node 0~Node 5下载的数据缺少
Figure 304969DEST_PATH_IMAGE080
所代表的的的编码块，所以从
Figure 767174DEST_PATH_IMAGE081
中消去其余编码块后结果如下：
Figure 131290DEST_PATH_IMAGE082
Figure 602723DEST_PATH_IMAGE083
Figure 860529DEST_PATH_IMAGE084
步骤4)、编码过程中将有限域设置为GF（43），且
Figure 24794DEST_PATH_IMAGE085
线性无关，那么利用上述三式能将
Figure 125474DEST_PATH_IMAGE086
所代表的编码块恢复出来。那么至此，所有编码块均已得到。
如图7为本发明方法的节点修复方法的流程示意图，基于所述再生码构造方法的节点修复方法，包括如下步骤：
B1．根据步骤S1~S5构造再生码；
B2．确定失效节点的序号；具体为，从剩下的完好节点中对元素编号，记为
Figure 869439DEST_PATH_IMAGE087
，将元素编号与
Figure 247331DEST_PATH_IMAGE088
设计中的元素对比，确定失效节点的序号h 0；节点修复方法根据步骤S3的内层参数为(m,m-t+1)的MDS码提供的冗余信息，由于内层参数为(m,m-t+1)的MDS码只有t-1个数据符号作为冗余信息，因此共需下载r(m-t+1)个编码块。
B3．在组合设计中确定失效节点出现过的区组序号，依次记为
Figure 690819DEST_PATH_IMAGE089
；
B4．从n-t+1个节点中下载编码块，对应文件符号具体为
Figure 154162DEST_PATH_IMAGE090
，
Figure 967397DEST_PATH_IMAGE091
表示h出现在第i个区组中的第j个位置，共下载r(m-t+1)个编码块；
B5．将步骤B4下载的r(m-t+1)个编码块分成r组，每组的编码块具有相同的区组编号i；
B6．对每一组编码块利用内层获得的MDS码的编码规则恢复一个编码块；将r组编码块恢复出r个编码块；
B7．将恢复出的r个编码块存储到一个新的存储节点，并将此节点加入原存储系统中完成修复过程。
对于一个t-设计
Figure 199795DEST_PATH_IMAGE092
，即共有v个不同的元素，每个区组有m个元素，任意t个元素相遇λ次（即出现在同一个区组中）。在编码过程的步骤S3中，内层参数为(m,m-t+1)的MDS码提供t-1份冗余信息，那么对于属于同一个区组的编码块能容忍t-1个编码块的失效。进一步地，整个存储系统能容忍t个节点的失效，共失效tr个编码块，该过程中失效的编码不能只由内层(m,m-t+1) MDS码提供的冗余信息进行恢复，而还必须依赖于外层参数为
Figure 830497DEST_PATH_IMAGE093
的MDS码来进行恢复；其中内层(m,m-t+1)MDS码能为这tr个失效编码块提供
Figure 249977DEST_PATH_IMAGE094
份冗余信息，外层
Figure 866903DEST_PATH_IMAGE095
MDS码能为这些冗余文件提供
Figure 829174DEST_PATH_IMAGE096
份冗余信息，因此利用这
Figure 506143DEST_PATH_IMAGE097
份冗余信息能恢复这失效的tr个编码块。
在具体实施方式中，给出一个M=39，n=8，d=7，k=6的节点修复实例，如图8为本发明方法的节点修复方法的实施例示意图。具体说明如下：在本实施例中，令Node 0失效，那么具体修复过程如下：
步骤一、由于Node 1~Node 7节点完好，那么失效节点的元素编号为0；
步骤二、该分布式存储系统是基于2-(8,4,3)设计的，那么元素0出现过的区组序号有{1,2,3,4,5,6,7}。
步骤三、从7个存储节点中下载
Figure 678498DEST_PATH_IMAGE098
所代表的文件，
Figure 833536DEST_PATH_IMAGE099
Figure 899581DEST_PATH_IMAGE100
，则共下载了21个编码块。
步骤四、将所下载的编码块分为7组，每组中的编码块
Figure 747451DEST_PATH_IMAGE101
具有相同的区组编号i，分组后如下
Figure 407103DEST_PATH_IMAGE102
Figure 736803DEST_PATH_IMAGE103
。
步骤五、对于对每一组均利用内层参数为(4, 3)的MDS码的编码规则恢复出一个编码块，例如在第1组中
Figure 532721DEST_PATH_IMAGE104
，且
Figure 285913DEST_PATH_IMAGE105
已获得，那么经过异或操作后即可恢复
Figure 557494DEST_PATH_IMAGE106
。类似地对每一组均进行上述恢复操作，最终能获得
Figure 319914DEST_PATH_IMAGE107
，而这正是失效节点中的编码块。
步骤六、将上述7个编码块存储至一个新的存储节点，并将此节点加入原分布式存储系统中。至此，节点修复过程完成。
总结本发明提出的码字与Chao Tian提出的码字相关参数，如下表所示：
Figure 235918DEST_PATH_IMAGE108
证明利用上述编码方案生成的[n,k=n-t,d=n-t+1]分布式存储系统能达到辛格尔顿界，即d min= n-k+1，证明过程如下：
Ⅰ．根据编码过程中的步骤S5，将所有具有相同h的
Figure 160011DEST_PATH_IMAGE109
所表示的编码块存储至同一节点中，那么一个节点中存储的文件数
Figure 669621DEST_PATH_IMAGE110
，r为元素重复度；并且为每一个不同的元素h分配一个新的存储节点，那么存储系统的总节点数n=v。
Ⅱ．编码过程的步骤S3，由于存在双层MDS编码，那么该分布式系统中能存储的数据块数目
Figure 970152DEST_PATH_IMAGE111
，其中
Figure 6242DEST_PATH_IMAGE112
。
Ⅲ．根据
Figure 101236DEST_PATH_IMAGE113
。根据节点修复过程，一个节点失效需连接至
Figure 347410DEST_PATH_IMAGE114
个节点进行修复。
Ⅳ．辛格尔顿界的左式：
左式=n-(n-t)+1=t+1
辛格尔顿界的右式：
Figure 451632DEST_PATH_IMAGE115
由于v≥m>0，所以上式
Figure 811069DEST_PATH_IMAGE116
Ⅴ．由于编码过程的步骤S1中，选择的t-设计需要满足的要求是
Figure 716446DEST_PATH_IMAGE117
，因此辛格尔顿界右式=t+1。
Ⅵ．由于左式=右式，因此证毕。

Claims (9)

1.一种再生码构造方法，其特征在于包括如下步骤：
S1．获取组合设计和存储数据块；获取的组合设计具体为，选择满足组合条件的t-设计
Figure 87018DEST_PATH_IMAGE001
，λ为t-平衡数，表示任意t元子集均出现在λ个区组中，其中，
记b为区组个数，
Figure 387549DEST_PATH_IMAGE002
；
记r为元素重复度，
Figure 158059DEST_PATH_IMAGE003
；
组合条件为：
Figure 518633DEST_PATH_IMAGE004
；
其中，t为子集的元素数；v为设计的阶，具体为设计中不同元素的总数；m为区组容量，具体为一个区组中的元素个数；
获取的存储数据块具体为，设存储原文件大小为M，将原文件拆分成
Figure 109014DEST_PATH_IMAGE005
个大小相等的数据块；
S2．对区组排序并编号，统计元素出现的区组及位置，得到文件符号；
S3．对数据块进行编码，得到编码块；
S4．为每个编码块分配一个不同的文件符号；
S5．将每个元素一致的文件符号集合所对应的编码块放置在同一存储节点中，得到再生码。
2.根据权利要求1所述的再生码构造方法，其特征在于步骤S2的文件符号设为
Figure 213237DEST_PATH_IMAGE006
，其中1≤i≤b，1≤j≤m，b为区组个数，m为区组容量；同时
Figure 103832DEST_PATH_IMAGE006
表示元素h出现在第i个区组中的第j个位置；将区组编号记为B 1,B 2,…,B b ，对于区组B i ，将其中的元素由小到大顺序排列，位置编号记为{1,2,…,m}。
3.根据权利要求2所述的再生码构造方法，其特征在于步骤S3具体为利用双层编码策略对数据块进行编码；外层获得的MDS码构造如下：
利用参数为
Figure 884575DEST_PATH_IMAGE007
MDS码对
Figure 962253DEST_PATH_IMAGE008
个数据块进行编码，获得b(m-t+1)个编码块，其中b为区组个数，m为区组容量，t为子集的元素数，λ为t-平衡数，表示任意t元子集出现在λ个区组；
内层获得的MDS码构造如下：
将上述利用外层编码得到的b(m-t+1)个编码块均分为b组，利用参数为(m,m-t+1) MDS码对每组中的m-t+1个编码块进行二次编码，最终得到bm个编码块。
4.根据权利要求3所述的再生码构造方法，其特征在于步骤S4具体包括，为上述获得的每一个编码块分配一个文件符号作为标识，不失一般性地，将
Figure 604587DEST_PATH_IMAGE009
的前
Figure 615268DEST_PATH_IMAGE010
个文件符号
Figure 52065DEST_PATH_IMAGE012
作为外层编码生成的冗余块的标识；将
Figure 882618DEST_PATH_IMAGE013
的文件符号
Figure 328643DEST_PATH_IMAGE014
作为内层编码生成的冗余块的标识，其中，
Figure 177519DEST_PATH_IMAGE016
表示元素h出现在第i个区组中的第j个位置，m为区组容量。
5.根据权利要求4所述的再生码构造方法，其特征在于步骤S5具体包括，每当发现一个文件符号
Figure 316377DEST_PATH_IMAGE006
，若其元素h与之前的文件符号
Figure 368646DEST_PATH_IMAGE017
不同，则分配一个新的存储节点并编号为h；对于每一个文件符号
Figure 352783DEST_PATH_IMAGE017
，若其元素h已分配存储节点，则将元素h相同的文化符号
Figure 72477DEST_PATH_IMAGE018
所对应的编码块存放到编码为h的存储节点中，则一个存储节点存储r个编码块，r为元素重复度；得到参数为[n,k=n-t,d=n-t+1]的再生码，n为节点个数，k为下载数据的个数，d为参与修复的节点个数，t为子集的元素数，
Figure 116656DEST_PATH_IMAGE019
表示元素h出现在第i个区组中的第j个位置。
6.一种基于权利要求1~5之一所述的再生码构造方法的文件重构方法，其特征在于包括如下步骤：
A1．根据步骤S1~S5构造再生码；
A2．连接到存储节点；
A3．在下载当前编码块时，进行重构第一次判断；
A4．在完成一个编码块的下载后，进行重构第二次判断；
A5．利用内层及外层的MDS编码规则恢复原文件。
7.根据权利要求6所述的文件重构方法，其特征在于步骤A3的重构第一次判断具体包括，对于当前具有相同区组编号i 0的文件符号
Figure 656222DEST_PATH_IMAGE020
，是否已经下载了m-t+1个文件符号
Figure 696247DEST_PATH_IMAGE021
所代表的编码块，
Figure 4868DEST_PATH_IMAGE022
表示元素h出现在第i 0个区组中的第j个位置，m为区组容量；若判断为是，则停止下载当前编码块；若判断为否，则下载当前编码块；步骤A4的重构第二次判断具体包括，判断是否已经下载了
Figure 219949DEST_PATH_IMAGE023
个编码块；若判断为是，则停止下载过程，若判断为否，则继续下载过程，b为区组个数，t为子集的元素数，λ为t-平衡数，表示任意t元子集出现在λ个区组中。
8.一种基于权利要求1~5之一所述的再生码构造方法的节点修复方法，其特征在于包括如下步骤：
B1．根据步骤S1~S5构造再生码；
B2．确定失效节点的序号；
B3．在组合设计中确定失效节点出现过的区组序号；
B4．从n-t+1个节点中下载编码块，共下载r(m-t+1)个编码块，r为元素重复度，n为节点个数，t为子集的元素数，m为区组容量；
B5．将步骤B4下载的r(m-t+1)个编码块分成r组，每组的编码块具有相同的区组编号i；
B6．对每一组编码块利用内层获得的MDS码的编码规则恢复一个编码块；将r组编码块恢复出r个编码块；
B7．将恢复出的r个编码块存储到一个新的存储节点，并将此节点加入原存储系统中完成修复过程。
9.根据权利要求8所述的节点修复方法，其特征在于步骤B2具体为，从剩下的完好节点中对元素编号，记为{h 1,...,h v-1}，将元素编号与
Figure 512390DEST_PATH_IMAGE024
设计中的元素对比，确定失效节点的序号h 0；其中v为设计的阶，m为区组容量，λ为t-平衡数；步骤B3的区组序号记为{i 1,...,i r }；步骤B4的文件符号具体为
Figure 572750DEST_PATH_IMAGE025
，表示h 0出现在第i个区组中的第j个位置，
Figure 267037DEST_PATH_IMAGE027
。
CN202110348155.4A 2021-03-31 2021-03-31 一种再生码构造方法、文件重构方法及节点修复方法 Active CN112732203B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202110348155.4A CN112732203B (zh) 2021-03-31 2021-03-31 一种再生码构造方法、文件重构方法及节点修复方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202110348155.4A CN112732203B (zh) 2021-03-31 2021-03-31 一种再生码构造方法、文件重构方法及节点修复方法

Publications (2)

Publication Number Publication Date
CN112732203A CN112732203A (zh) 2021-04-30
CN112732203B true CN112732203B (zh) 2021-06-22

Family

ID=75596222

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202110348155.4A Active CN112732203B (zh) 2021-03-31 2021-03-31 一种再生码构造方法、文件重构方法及节点修复方法

Country Status (1)

Country Link
CN (1) CN112732203B (zh)

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN116880778B (zh) * 2023-09-07 2023-11-21 杭州迅杭科技有限公司 一种基于再生编码及分布式存储的用户隐私保护方法

Citations (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103688514A (zh) * 2013-02-26 2014-03-26 北京大学深圳研究生院 一种最小存储再生码的编码和存储节点修复方法
CN103688515A (zh) * 2013-03-26 2014-03-26 北京大学深圳研究生院 一种最小带宽再生码的编码和存储节点修复方法
US8719667B2 (en) * 2010-07-26 2014-05-06 Thomson Licensing Method for adding redundancy data to a distributed data storage system and corresponding device
CN104838626A (zh) * 2013-01-04 2015-08-12 北京大学深圳研究生院 一种通用射影自修复码的编码、数据重构和修复方法
CN105721611A (zh) * 2016-04-15 2016-06-29 西南交通大学 一种由极大距离可分存储码生成最小存储再生码的一般方法
CN108279995A (zh) * 2018-01-30 2018-07-13 北京交通大学 一种基于安全再生码的分布式存储系统的存储方法
CN109062724A (zh) * 2018-07-21 2018-12-21 湖北大学 一种纠删码转换方法及终端
CN110750382A (zh) * 2019-09-18 2020-02-04 华中科技大学 用于提高数据修复性能的最小存储再生码编码方法及系统
US10608784B2 (en) * 2016-03-15 2020-03-31 ClineHair Commercial Endeavors Distributed storage system data management and security
CN111125014A (zh) * 2019-11-19 2020-05-08 长安大学 一种基于u-型设计的柔性部分重复码的构造方法
WO2020160142A1 (en) * 2019-01-29 2020-08-06 ClineHair Commercial Endeavors Encoding and storage node repairing method for minimum storage regenerating codes for distributed storage systems
CN111796966A (zh) * 2020-05-19 2020-10-20 中大编码有限公司 存储机架感知再生码的构建方法

Patent Citations (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8719667B2 (en) * 2010-07-26 2014-05-06 Thomson Licensing Method for adding redundancy data to a distributed data storage system and corresponding device
CN104838626A (zh) * 2013-01-04 2015-08-12 北京大学深圳研究生院 一种通用射影自修复码的编码、数据重构和修复方法
CN103688514A (zh) * 2013-02-26 2014-03-26 北京大学深圳研究生院 一种最小存储再生码的编码和存储节点修复方法
CN103688515A (zh) * 2013-03-26 2014-03-26 北京大学深圳研究生院 一种最小带宽再生码的编码和存储节点修复方法
US10608784B2 (en) * 2016-03-15 2020-03-31 ClineHair Commercial Endeavors Distributed storage system data management and security
CN105721611A (zh) * 2016-04-15 2016-06-29 西南交通大学 一种由极大距离可分存储码生成最小存储再生码的一般方法
CN108279995A (zh) * 2018-01-30 2018-07-13 北京交通大学 一种基于安全再生码的分布式存储系统的存储方法
CN109062724A (zh) * 2018-07-21 2018-12-21 湖北大学 一种纠删码转换方法及终端
WO2020160142A1 (en) * 2019-01-29 2020-08-06 ClineHair Commercial Endeavors Encoding and storage node repairing method for minimum storage regenerating codes for distributed storage systems
CN110750382A (zh) * 2019-09-18 2020-02-04 华中科技大学 用于提高数据修复性能的最小存储再生码编码方法及系统
CN111125014A (zh) * 2019-11-19 2020-05-08 长安大学 一种基于u-型设计的柔性部分重复码的构造方法
CN111796966A (zh) * 2020-05-19 2020-10-20 中大编码有限公司 存储机架感知再生码的构建方法

Non-Patent Citations (7)

* Cited by examiner, † Cited by third party
Title
Interference Alignment in Regenerating Codes;Nihar B. Shah et al.;《IEEE TRANSACTIONS ON INFORMATION THEORY》;20100510;全文 *
Minimum Storage Regenerating Codes for;HUAYU ZHANG et al.;《IEEE Access》;20170428;全文 *
On the Optimal Minimum Distance of;Bing Zhu et al.;《IEEE Xplore》;20200514;全文 *
Replication-based Distributed Storage Systems with;Bing Zhu et al.;《IEEE Xplore》;20140508;全文 *
二元再生码在分布式存储系统的应用;侯韩旭 等;《计算机研究与发展》;20131126;全文 *
基于柯西矩阵的最小带宽再生码研究伏;宋海龙，王伟平，肖亚龙;《湖南大学学报（自然科学版）》;20170831;全文 *
基于精确再生码的秘密共享方案;宋海龙，王伟平;《中南大学学报（自然科学版）》;20170430;全文 *

Also Published As

Publication number Publication date
CN112732203A (zh) 2021-04-30

Similar Documents

Publication Publication Date Title
US9959169B2 (en) Expansion of dispersed storage network (DSN) memory
CN107656832B (zh) 一种低数据重建开销的纠删码方法
US10241864B2 (en) Expanding information dispersal algorithm width without rebuilding through imposter slices
US7979771B2 (en) Erasure coding technique for scalable and fault tolerant storage system
CN110750382B (zh) 用于提高数据修复性能的最小存储再生码编码方法及系统
CN103746774B (zh) 一种高效数据读取的容错编码方法
US20160328295A1 (en) Site-Based Namespace Allocation
US20140344227A1 (en) Streaming Content Storage
CN107844272A (zh) 一种提高纠错能力的交叉分组编译码方法
US10001923B2 (en) Generation collapse
US20170212683A1 (en) Provisioning ds units on the fly in a dsn memory in response to load
CN112799605B (zh) 平方部分重复码构造方法、节点修复方法及容量计算方法
CN109491835A (zh) 一种基于动态分组码的数据容错方法
CN116501553B (zh) 数据恢复方法、装置、系统、电子设备及存储介质
WO2015180038A1 (zh) 部分复制码的构建方法、装置及其数据修复的方法
CN111831223A (zh) 提高数据去重系统可扩展性的容错编码方法、装置及系统
CN108762978B (zh) 一种局部部分重复循环码的分组构造方法
CN112732203B (zh) 一种再生码构造方法、文件重构方法及节点修复方法
CN107153661A (zh) 一种基于hdfs系统的数据的存储、读取方法及其装置
WO2018011670A1 (en) Manipulating distributed agreement protocol to identify desired set of storage units
Ivanichkina et al. Mathematical methods and models of improving data storage reliability including those based on finite field theory
US20180113626A1 (en) Fail-in-place supported via decentralized or distributed agreement protocol (dap)
Li et al. Relieving both storage and recovery burdens in big data clusters with R-STAIR codes
CN111224747A (zh) 可降低修复带宽和磁盘读取开销的编码方法及其修复方法
CN106911793B (zh) I/o优化的分布式存储数据修复方法

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant