Foundure 1.0：高效修复和更新功能的擦除代码库（2021）

≥软件X 13（2021）100662原始软件出版物Foundure 1.0：具有高效修复和更新功能的擦除代码库Şuayb Ş. ArslanMEF University，Maslak，Istanbul，Turkeyar t i cl e i nf o文章历史记录：收到2020年2021年1月11日收到修订版2021年1月13日接受保留字：分布式存储擦除编码喷泉编码单指令多数据（SIMD）OpenMP可靠性a b st ra ctFoundure是一个开源软件库，它完全基于快速异或（XOR）逻辑实现了基于多维图的时代编码。它的实现利用编译器优化和多线程来为给定的具有向量处理能力的多核CPU架构生成正确的汇编代码。Foundure拥有重要的功能，这些功能将在现代数据存储，通信和网络计算机系统中找到各种应用，其中数据需要保护以防止设备，硬件和节点故障。作为数据规模达到了前所未有的水平，这些系统已经变得对网络带宽、计算资源和平均消耗功率非常饥渴。为了解决这个问题，所提出的库提供了一个三维设计空间，它权衡了计算复杂性，编码开销，和数据/节点修复带宽来满足现代分布式数据存储和处理系统的不同需求。Foundure库支持高效的编码、解码、修复/重建和更新，同时所有所需的数据存储和计算都分布在网络节点上。©2021作者由爱思唯尔公司出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）中找到。代码元数据当前代码版本1.0用于此代码版本的代码/存储库的永久链接https://github.com/ElsevierSoftwareX/SOFTX-D-20-00043法律代码许可证LGPLv 3使用git的代码版本控制系统使用C、Python、OpenMP等的软件代码语言、工具和服务编译要求、操作环境依赖性Linux Linux环境和C编译器（四、8 .第八条。4）. Python 2.3或以上 如果可用，链接到开发人员文档/手册https://github.com/suaybarslan/founsure/blob/master/tests/Founsure_1_0_User_Manual.pdf问题支持电子邮件arslans@mef.edu.tr1. 动机和意义擦除编码是一种容错机制，在分布式数据存储和处理系统中提供数据保护和高可用性[1]。RS码是基于开销最优设计的纠删码的传统构造方法。换句话说，他们尽可能有效地使用存储空间-理论上是可能的[2]。随着现代数据存储系统的发展，具有不同的需求，对纠删码设计的约束集发生了巨大变化。例如，先前关于纠删编码（诸如RS）的研究工作集中于优化电子邮件地址：arslans@mef.edu.tr。https://doi.org/10.1016/j.softx.2021.100662编码开销即，最小化给定目标数据可靠性的存储空间[2，3]。此外，一些最流行的设计考虑了纯异或（XOR）操作，以提供持久性和有效的计算[4]。最近，局部可修复码由于其有效利用网络资源并最终以次优编码开销为代价实现更好的整体可靠性而引起了人们的关注[5]。除了先进的时代确定的编码算法的专有实现之外，许多具有不同数学构造的开源实现可以在线获得[6，7]。以前的作品提供了开销最优和快速/有效的纠删编码库函数。然而，他们没有考虑到2352-7110/©2021作者。由爱思唯尔公司出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表SoftwareX期刊主页：www.elsevier.com/locate/softxŞuayb Ş. Arslan软件X 13（2021）1006622考虑到被利用的网络、稀缺的计算资源以及分布式设置中的数据/节点再生的在这项研究中，我们提出了利用三维二分图上的二元操作来构造多功能擦除码的Foundure库。设计空间包括计算复杂度、编码开销和修复带宽作为优化的不同维度.如果人们更喜欢具有合理复杂度性能的开销优化设计，那么使用众所周知的Jerasure 2.0 [7]擦除编码库可能是明智的，该库现在完全由RedHat Ceph社区[8]支持。不幸的是，该库等（例如，zfec [9]）没有提供足够的代码结构来解决分布式存储系统的现代问题，诸如降级读取、数据修复/再生带宽、数据安全性等。另一方面，开发Foundure库的主要因此，可以证明，Foundure使用智能/引导配置步骤展示了独特存储应用程序的巨大潜力例如，在归档场景中，Foundure被配置为基线去重引擎[10]。Founsure的编码过程首先定义了一个两个-一维常规二分图，导致非系统的低密度生成矩阵（LDGM）码。具有适当输入分布的这类代码的版本通常被称为喷泉码[11，12]。Founture的LDGM代码的度分布是专门选择的，以满足在计算复杂性、编码开销和修复带宽之间的良好折衷操作点。当前版本（1.0）支持鲁棒孤子分布（RSD）[12]（如果喜欢良好的编码开销设计），以及所有可能的有限最大度分布（如果喜欢不同的操作点），包括默认情况下的[13然而，我们注意到，所提到的分布仅针对最小编码开销标准进行了优化。方信的建筑支柱之一是真正的象征检查关系。校验符号是低密度奇偶校验（LDPC）编码领域中常用的术语。校验符号的作用是提供数据符号子集之间的数学关系，以检查某个条件，通常是简单的二进制和或等效的伽罗瓦域运算。检查的想法也非常有利于本地数据修复/重建[14]。因此，在Foundure的二维二分图之上，编码引擎生成用于“仅数据”（以下称为校验#1）、“数据编码”（称为校验#2）和“仅编码”（称为校验#3）块/符号的校验节点可以想象，这些校验节点（数学关系）可以添加到二维二分图中，以赋予其三维外观。这种新的数据表示法应用于提供库的高级解码、修复和更新功能。在整个文档中，节点通常包含多个块，块通常包含多个符号。Foundure使用置信传播（BP）[15]（也称为消息传递）算法来解析或解码用户数据，以重新配对编码数据或更新编码数据。粘BP作为设计准则的目的是确保低复杂度的解码过程并允许快速/有效的操作。库还支持寄存器级并行通过编译器优化，以及多线程使用开放标准openMP原语与其编码，解码，修复和更新功能。多线程特性，一旦正确配置和使用，允许并行处理，并确保加速共享内存架构。通过缩短处理时间，确保快速响应任何通用分布式存储系统的常见读/写请求。在当前版本中，原始用户数据不会出现在输出文件中。相反，由于所谓的非系统性编码，所有输出文件都是用户数据的一个非线性函数。换句话说，在没有任何进一步解码的情况下，不能从编码器输出读取数据。因此，使用Foundure，可以认为用户数据在编码操作后自动加密请注意，我们使用伪随机数生成器（基于线性同余生成器）和种子（长类型的整数）来构建底层二分图的边。因此，如果没有种子数（我们可以将它们视为加密上下文中的密钥），就无法恢复原始用户数据，因为底层图的生成取决于种子的可用性。因此，Foundure软件包还提供了用户可配置的轻量级内置加密功能。与数据在编码器输出端显式显示的系统代码不同，Foundure具有前面提到的非系统格式。然而，除了数据保护之外，这还提供了数据安全性。只要使用我们在这项研究中讨论的各种新技术进行快速解码，非系统代码就不应该成为系统其余部分的整体性能瓶颈本文将简要描述软件体系结构的细节，库提供的一组功能以及一些相关的高级功能。源代码，全面的用户指南，一些测试结果和 所 有 相 关 文 档 也 可 以 从 github 和 Web 链 接http://www.suaybarslan.com/founsure.html获得。2. 软件描述和体系结构2.1. 软件功能Foundure有以下三个可执行的主要组件，它们实现了四个重要功能。fonsureEnc：编码器引擎，在本地编码目录下生成s个数据块（将存储在s个不同的故障域中）和一个元数据文件，该元数据文件包括有关文件的信息、编码参数和种子信息。fonsureDec：解码器引擎，需要本地编码目录，其中包含足够数量的文件、有效文件名和关联的元数据文件，以运行多个置信度验证（BP）通道，从而对用户数据进行解码。fonsureRep：修复引擎，也需要一个编码目录与足够数量的文件和– 修复/修复一个或多个数据块，如果它们已被擦除，损坏或标记为不可用。– 如果已经请求了代码更新，则生成额外的编码块。系统更新被触发 如果数据可靠性随时间推移而降低/降级或由于设备更换而增加。这些函数用于执行编码、解码、重新配对和更新操作.还有一些Foundure的实用功能，用于帮助系统管理员在度分布，所需的可靠性，所需的复杂性和存储空间效率方面做出正确的设计选择。我们还使用实用程序函数来触发更新功能，这将在后面演示实用函数的一个显著特点是它们不直接处理用户数据，而是帮助我们为主函数配置正确的参数，以正确地修改和处理用户数据当前版本支持下面列出的两个实用程序···Şuayb Ş. Arslan软件X 13（2021）1006623××||∑=−⃝⃝≤--=---+simDisk：此函数可用于为给定的编码参数集排除所有可能的磁盘故障组合。换句话说，该函数检查所提供的编码参数是否足以实现用户定义的可靠性目标。因此，运行此函数可以帮助我们通过配置度分布来设计目标策略擦除码，以实现除可靠性之外的各种系统级genChecks：该实用程序功能对于两个不同的重要功能至关重要：（1）快速/有效的数据修复/重建和（2）无缝实时更新。对于修复过程，它生成两种类型的检查：检查#2和检查#3 ， 并 使 用 本 文 档 中 描 述 的 格 式 将 它 们 注 册 到testfile>_check.data文件中。在更新的情况下，它修改元数据 和 testfile>_check.data 文 件 ， 以 便 可 以 通 过 运 行fonsureRep函数来更新编码块。接下来，我们将详细介绍Foundure的编码、解码、修复和更新操作，特别是fonsureEnc、fonsureDec和fonsureRep函数的实现细节。有关基础理论和计算复杂性的更多细节，我们请读者参考适当的文档，如[16]。2.2. 编码/解码操作在图论术语中，节点（有时称为方程）由图顶点表示，节点关系由图的边表示。在三维二部图中有三种类型的节点：数据节点、编码节点和校验节点。编码节点表示通过诸如XOR逻辑运算的预定数学函数生成的数据节点的线性组合的集合。校验节点表示满足特定数学关系（诸如偶或奇奇偶校验）的所有本地数据集和编码节点。Foundure使用的一个简单的数学函数是区域XOR运算，它对相同大小的多个数据块进行运算，并生成单个信息块。我们使用f标志表示文件名，k表示总数其中B是原始用户数据节点/符号，N表示编码节点/符号的总数，T表示每个节点/符号要存储的字节数在fonsureEnc函数中，具有文件大小字节的数据文件被划分为多个字节，每个分区被独立编码，如图所示。1.一、当前版本不支持不同分区之间的分区耦合分割彼此独立地处理这种技术目前正在研究中，并且可能对我们的设计/实现具有类似于空间耦合LDPC码的有趣的性能改进[17]。然而，耦合对于部分磁盘故障可能具有不同的影响，并且可能最终导致跨分区的非均匀解码性能。如果文件大小不是b t字节的倍数，那么我们使用零填充来使文件大小成为倍数。另一方面，foun- sureEnc还检查s是否整除n（sn）。如果不是，则自动选择最小最大n以满足s n。这种要求使我们能够在不同的故障域中存储完全相同数量的信息字节。这与平衡的系统设计特别相关，在平衡的系统设计中，底层存储设备具有相同的类型、质量并且对各种类型的故障具有同等的弹性高效阵列LDPC编码[18，19]。选择阵列LDPC作为预编码是为了实现高效的编码操作和快速处理。作为此操作的结果，被创建以构成总共k个数据块。预编码过程如图1中的1所示。稍后，基于以下从k个数据块的整个集合生成总共n个编码块：具有配置的“随机分布”度和伪随机选择分布的LDGM基码。该过程如图2所示。1.一、最后，n个编码块在不同的输出文件中均匀分布（条带化），以便分配到s个驱动器上。我们在一个循环中对每个数据分区重复这个过程，并在相应的输出文件的末尾附加编码块对于给定的<文件名>.ext文件，我们使用<文件名>_disk0.. 0i.ext引用第i个输出文件。输出文件名中出现的零的数量由“parameter.h”变量DISK_INDX_STRNG_LEN设置。在Foundure实现中，我们对编码、解码和修复操作有不同的对象定义。这些对象具有共同的尾部对象字段中的参数。例如，编码和/或解码函数都接受EncoderObj和/或DecoderObj构造作为 输 入 。 类 似 地 ， 可 以 使 用 标 准 方 式 EncoderObj.sizesb 和EncoderObj.sizek访问b和k变量。每个编码/解码对象与种子值（EncoderObj.seed1）相关联，其他种子值和局部编码/解码对象从该种子值（EncoderObj.seed1）中被编码/解码。数据块的集合是伪随机生成的。EncoderObj和DecoderObj中的每个编码块都有自己的唯一ID。这些ID用于标识已删除的编码块。伪随机发生器使用种子值来创建整数序列。这些整数构成了编码块度数分配和所选数据块的基础 用于编码块计算。这些编号作为对象的一部分存储，并且可以使用相同的初始种子编号后跟常规递归关系重新生成。让我们假设我们有s个输出文件（故障域），那么我们使用默认值EncoderObj.seed+i作为第i个输出文件的种子，其中0是s<。每个校验节点c与度数cd（根据适当的度分布选择）其中，i是选择度i）的概率，并且cd数据节点邻居被选择以参与最终符号计算。度分布f（x）通常被选择为最小化编码开销。例如，对于Raptor码提出了以下度分布[13]：x= 0. 007969 x +0。49357 ×2+ 0。16622x3+0。072646 x4+ 0。082558x5+0。056058 x8+ 0。037229 x9+ 0。05559x19+0。025023 x64+ 0。003135x65其中，1。007969，002 。49357，430。16622，2004年. 072646，105 。082558，0828。056058，1999。037229，2019年. 05559，164。025023，165 。003135.但是，Founsure并不一定能最小化开销。它可以同时优化开销、修复带宽和复杂性。我们建议选择度分布，这将使我们在这三个目标之间有一个很好的权衡点。一个系统的优化程序，以达到所需的工作点是进一步调查的主题。虽然没有针对所有应用的最佳点，但Founsure的设计具有高度可配置性，以适应现代存储生态系统的不同编码如下进行首先，一个内存空间（一个缓冲区）分配值为（kn）t个接下来，检查#1方程由1为see选择的默认值为1389488782，实验观察到该 值 具有良好的 恢复性能。··Şuayb Ş. Arslan软件X 13（2021）1006624+−2k×nFig. 1. 函数fonsureEnc分配（nk）测试缓冲区的字节，生成编码块，并在写入它们之前将它们写入内存上的阴影区域不同的驱动器。磁盘上的文件在循环子进程中被条带化和处理，如图所示。条带数存储在readin变量中，并写入元数据文件。图二. 每一个Founsure符号是t字节，并且应用预编码来找到校验#1等式。我们加上kb额外的符号，以满足所示的检查方程。如图所示，Foundure编码引擎从k个块生成n个编码块算法1置信传播（BP）算法（骨架）一曰： 程序BP（B，E，maxit）<$输入：B∈Fk×n，E<$N：擦除集。2：N ={1，. . . ，n}初始化索引。3：K ={1，. . . ，k}初始化索引。4：C← b：，N\E求生存矩阵。5：F ← K索引：F保存未恢复的索引。6：whileF=andimaxitdo<7：对于g = 1，. . . 、|N\E|做8：cK\F，：← 0解码符号的清零行。9：如果w八（c：，g）= 1，则找到度1编码符号。10：F←F−{f：cf，g=1 forf∈F}11：return F返回未恢复的索引。当我们想要收集输出数据文件的子集并恢复输入数据文件时，我们运行fonsureDec。 解码器基于置信传播算法，算法1中提供了置信传播算法的概述。BP函数允许DecoderObj，擦除的索引E N ={1，2，. . . ，n}的生成矩阵，基码B∈F2和最大迭代次数maxit.在算法1中，我们使用bi，：来引用B的第i行，并且使用b：，i来引用B的第i行。参考B的第i栏。另外，bA，B是指矩阵其行和列由集合A和B索引的B的行和列给出。解码器利用元数据文件中包含的信息来生成（准备）DecoderObj的内容，特别是底层编码图。它以类似于fonsureEnc的方式工作，它读取条带化编码块，加载缓冲器，并且最多运行两次BP算法（一次用于外部图形码，并且如果需要，另外一次用于内部阵列LDPC预编码），并且在每次运行时恢复btŞuayb Ş. Arslan软件X 13（2021）1006625−=⌊⌋==图3.第三章。 Foundure编码器和解码器的软件块摘要。依次最后，通过调用标准内核I/O命令将这些字节写入解码/恢复的数据文件。为了总结Foundure的编码和解码方案的软件体系结构，我们提供了Fig. 图3示出了对用户数据进行编码/解码的软件构建块的顺序。修复操作可以看出，我们对块使用不同的颜色来区分编码和解码过程。其中一些块仅由其中一个函数使用。另一方面，一些块由编码器和解码器过程两者使用使所有计算基于伪随机选择的块并且仅根据简单的XOR逻辑来执行这些计算具有使代码在开销方面非最优的成本（尽管通过选择适当的度分布它可能接近最优）。如果n个编码符号分布在s个驱动器上，并且当其中一个驱动器发生故障时，编码符号的子集丢失。为了找出f-故障组合可以容忍一个给定的程度discovery，我们提供了一个实用程序功能simDisk，用尽所有可能的故障组合，以报告哪些故障情况下是可以容忍的代码，哪些不是。这样的实用程序函数对于确定受Foundure库保护的数据的可靠性非常有用。2.3. 检查方程和数据修复过程给定如图11所示的三维Founture图表示。 4，我们有三种类型的校验节点，如前所述。我们在本小节中提供了这种检查过程的细节。检查#1：这些检查方程由Foundure的预编码定义（对于版本1.0，我们选择了一个Array LPDC代码族[18]，用于算法2中给出的高效处理）。基于良好预编码器的选择、数学和编码参数选择等，自动确定图形连接。Foundure包括基于二进制阵列LDPC码的预编码支持。库的未来版本见图4。F o u n d u r e 图形代码是具有三组校验方程的三维二部图。应包括外部预编码支持，可由用户使用预格式化输入文件提供请参阅预编码小节，了解有关这些校验方程构造的更多信息。检查#2：这些检查方程如算法4中给出的那样生成。这些校验的一个特殊特征是仅从数据节点中选择一个邻居，并且校验节点的其余邻居来自编码节点。此特殊功能可用于部分解码输入数据，而无需运行完整的解码器，并重建输入数据的不必要部分。这一应用可以安全地存储多媒体源，其中感兴趣区域（ROI）可以使用这种类型的检查方程直接重建。检查#3：这些检查方程如算法4中给出的那样生成。这些检查基于编码节点形成局部组。这些检查主要用于在硬件、软件和网络故障的情况下2.4. 预编码过程-生成校验#1方程如图 2，a（b，k，n）Foundure码采用b个数据符号（总共bt个字节），并且最初生成k个b复选基于二进制阵列LDPC编码的#1奇偶校验符号[18]。阵列LDPC码的这种特殊选择实现了高效的编码操作（与块长度成线性关系），并提高了整个Founsure库的复杂度性能。算法2中概述的过程使用通用函数largest_prime_factor（.）它选择了参数中最大的素因子。阵列LDPC的速率被定义为rLDPC b/k。用户可以选择任何k、n和rLDPC，因此我们可以计算适当的bkrLDPC。设plargest_prime_factor（k），我们可能无法得到等于整数的量krLDPC/ p。我们可以使用floor函数来得到j′的估计。然而，阵列LDPC码的性能严重依赖于k′和j′值，并且不存在针对所有（k， r）LDPC对的阵列LDPC码如果（j′，k′）对很小，则观察到代码性能非常差。为此，我们提供了一种算法，合理地选择一个性能良好的阵列LDPC码，并满足（在一定的误差范围内），同时用户提供的参数k， n和rLDPC。可以通过在Foundure主函数的末尾添加“-v”标志来查看所选参数让我们定义以下系统参数。 之后，我们将正式提供为用户提供的参数k、 n和rLDPC确定最接近的性能良好的阵列LDPC码的算法。这些系统参数及其默认值在“parameter.h”文件中定义，可以轻松修改。DIFF_TH：估计值和用户提供的b值之间的允许误差阈值。·Şuayb Ş. Arslan软件X 13（2021）1006626′← ← ←′简体中文←−←++←++←←←×←−，区块1、0、0算法2阵列LDPC校验（校验#1）1：程序检查one（b，k）输入：b，k2：L（1）初始零矩阵3：p←largest_prime_factor（k）4：k′←k/p5：j′←k′−b/p6：对于j=0;jj;j+ +do<7：对于i=0;ip;i++′ 做8：对于m=1;mk−j′+1;m+ +do<（一）i+jp，m−1←k′p−（j′−j+m−1）p−（m（j′−j−1）−i−1+p）（modp）−110：return L（1）L（1）：检查#1组。RRATE_TH：估计的和用户提供的预编码速率之间的允许误差阈值·算法3使用预编码（APP）1：过程app（rLDPC，文件大小，b，t）RED_BYTE_TH：允许在文件末尾附加冗余零字节，以保证参数一致性。RAND_WIN_MAX：随机数搜索窗口最大值。RAND_WIN_MIN：随机数搜索窗口最小值。ARRAY_MIN_JJ：最小阵列LDPCARRAY_MIN_KK：最小阵列LDPC• TRIES_TH：增加前尝试次数的阈值。二比二b ←b，bt←ries0，k←iter1，k′ ←1e9，j′ ←1e9，p←3：while（|Bb|>DIFF_TH|||b/k-rLDPC码|>RRATE_TH||K>p|| j′第四章：||k′ RED_BYTE_TH做5：k比特/rLDPC rand（）mod（RAND_WIN_MAX+RAND_WIN_MIN）-RAND_WIN_MIN6：p←largest_prime_factor（k）7：k′←′k/p，j′←k′−b<$/p以DIFF_TH和RRATE_TH为变量。• DELTA_DIFF_TH：DIFF_TH的步长增量• DELTA_RRATE_TH：RRATE_TH的步长增量接下来，我们提供了一种算法，该算法返回b、k的估计值以及需要附加到输入用户数据的冗余零数（redundantzeros该算法允许四个输入，即rLDPC、文件大小、b和t。系统参数的初始值应通过“parameter.h”文件设置2.5. 生成用于高效维修的为了有效地修复丢失的数据，我们需要从生成的Foundure代码的底层图形内容中提取修复信息。我们观察到检查#3节点是8：如果j_ARRAY_MIN_JJ，则<9：j′←210：b（k′ j′）p11：如果b>0，则12：blocks filesize/tb+113：尝试14：如果tries>TRIES_TH，则15：DIFF_THDIFF_TH + DELTA_DIFF_TH16：RRATE_THRRATE_TH + DELTA_RRATE_TH17：尝试018：iter19：如果iter>1e 7，则20：打印错误并退出。21：blocks filesize/（tb）+122：redundantzeros bt blocks-filesize23：返回b，k，冗余零最适合修复过程的节点类型，因为它建立编码符号之间的直接关系不难看出，这些节点类型（独立创建或依赖地）给出了在通信网络中发生节点故障的不同组合的情况下修复给定节点的替代方式。换句话说，我们发现的这些检查类型越多关于该观察，我们可以使用两种技术来基于校验#1和校验#2等式增加校验#3类型信息的数量：第一种方法如下。我们识别度为1的编码节点（假设我们有M个这些节点）。识别其数据节点邻居。有M个校验#2等式将这些数据节点与编码节点连接。由于对应的M个编码节点携带相同的信息，因此我们可以使用这些校验#2类型的校验方程作为附加的校验#3校验方程。请注意，由于检查由于等式#2和校验等式#3是从相同的基图导出的，所以该技术可能生成已经存在的局部恢复组或可以从编码节点的现有局部组第二种方法如下。请注意，检查#1是用户定义的，但受制于预定义的结构。这定义了数据节点上的本地恢复组以来每个数据节点通过校验#2链接到编码节点的本地恢复组，我们可以使用这种关系来导出校验#3类型的校验方程。例如，假设我们为数据节点D0、D1和D2定义了以下检查#1本地恢复组：（D0，D1，D2）。此外，假设我们有以下检查#2方程：D0=C0D1=C1D2=C0因此，我们可以找到由（C2，C12，C17，C20，C21），通过观察以下等效性，C2<$C12<$C17<$C20<$C21=D0<$D1<$D2（4）请注意，由于此技术使用检查#1等式，因此可能会生成不同的检查#3本地恢复组，并有助于显著提高修复性能。这些附加的检查#3 本地恢复组（例如，等式10的操作）。（4））由“encoder.c”文件中给出的集合联合函数setXOR9：l·····>p··Şuayb Ş. Arslan软件X 13（2021）1006627=⊕−−=−年代−∑−×2.6. 用于联合生成校验#2和校验#3方程的算法为了提高效率，我们提出了一种启发式算法来同时生成检查#2和检查#3方程。该算法利用异或运算（）对生成矩阵B进行稀疏化。如果B是满秩，即，等级（B）那么算法是有保证的才能成功融合。这是由于初等矩阵的行运算将生成n对于满秩B，k个零列 因此该算法将离开主while循环并生成具有列权重k个1和nk个0的修改的B。在最后的数学术语中，我们应该能够找到置换矩阵P，使得BP=[Ik×k|0k×n−k]。还有，L（2，3）L（2，3）P应保存所有本地恢复集，即，检查#2检查前k列中的等式，并检查最后n k列中的#3等式。我们可以将不同类型的检查表示为所有检查#2和检查#3方程的并集，如以下公式所示：（D，{C： ∪ （{C：如果它是1（检查#2），则下一个整数值（下一个sizeof（int）字节）给出了在本地恢复组内涉及的数据符号索引，该本地恢复组的度由以下整数（下一个sizeof（int）字节）给出。该度数还指示下一个要作为编码符号的一个本地恢复组的一部分读取的整数的数量如果它是0（检查#3），则下一个整数值（下一个sizeof（int）字节）给出度数，即，要作为一个本地恢复组的一部分读取的整数的数量，用于对符号进行编码。算法4的优点在于，如果它收敛，则所有数据符号都被一个特定的检查#2本地恢复方程精确覆盖。让我们举一个例子来说明工作原理，并假设我们在<文件名>_check.data中存储了以下整数数组：04 13 56 17 66 1 19 2 11 13 0 2 39 88. . .我I kss，ii≥kss，i如果我们解码这个整数数组，我们将能够说第一个局部集合是类型检查#3，并且这个集合有四个元素。其中，L1（2，3）表示L1（2，3）的第s行和第i列条目。 在算法4中，我们使用伪代码提供了算法的细节。我们使用一个简单的函数zero_columns（.）它查找参数中矩阵的非零列数。由于B通常是稀疏的，因此我们在库实现中使用矩阵的稀疏表示我们还根据本地恢复组的基数对其进行排序，即，具有最小基数的集合首先出现这样的安排有助于我们降低修复/更新的复杂性，因为修复功能按顺序处理本地组。2.7. 管理检查#2和检查#3等式，并生成文件名>_check.data文件，以实现高效的修复/更新过程如前所述，通过二进制阵列LDPC码来方程的用户定义的数量是从一组预编码率的基础上施加的应用程序的可靠性。图连接是确定性的，并且由数组代码的约束给出与校验#1不同，校验#2和校验#3由Foundure基码伪随机地确定。基于代码B的生成器矩阵，运行算法4以确定n个方程。如果算法收敛，那么我们应该有k个用于检查#2类型的方程和n k个用于检查#3类型的方程。该算法产生一组正确的局部方程（组），但不保证这些方程是独立的。在生成这些方程时，我们不使用任何矩阵求逆（这对于大尺寸矩阵来说是相当昂贵的）来找到校验方程，因此我们通过性能来权衡效率。生成检查#2和检查#3局部恢复方程的函数是效用函数genChecks。函数genChecks假设元数据文件已经由编码器foundureEnc的先前运行生成。因此，genChecks生成检查组并修改Meta_data文件（如果“-m”标志参数为True，则在元数据文件的末尾附加检查数据的大小，以sizeof（int）字节表示）。检查信息存储在另一个名为<文件名>_check.data。此文件存储具有特定格式的整数数组。引入一种格式的原因是使用fread和fwriteC库函数的批量读/写功能本研究中提出的格式非常简单，可以改进。我们使用标志位来区分两个不同的校验方程。因此，_check.data中第一个sizeof（int）字节的整数值为0或1。换句话说，第13、第56、第17和第66编码符号形成本地恢复组即，它们的二进制和应该产生全零内容。下一个局部集合属于校验#2，并且相关联的数据符号索引是19。该数据符号与第11和第13编码符号（两个编码符号）一起形成本地恢复组。这样我们就可以解码存储在filename>_check.data中的整个整数如果算法收敛，则整数数组中应该有k个前导1和n k个前导0，注意，数组中包含的整数总数由下式给出：n−1N=Lc+k+2n（ 6）c=0其中Lc是由c索引的校验#2（不包括数据符号）和校验#3中的元素的总数。注意即使算法不收敛，最大可能的存储器占用是Nsizeof（int）字节。因此，它是足够的分配内存的大小由方程。（6）对于文件不遇到分段故障。图 5总结了不同的Foundure函数如何相互交互，生成/使用了哪些其他元数据，以及为确保Foundure库的正确操作，向这些函数中的每一个授予了什么类型的读/写权限。2.8. 读取/格式化filename>_check.data文件当修复过程启动时，内存分配和修复对象（RepairObj）准备开始。主修复引擎应在/Coding目录下查找<文件名>_check.data如果它找到一个并且如果元数据被适当地格式化（在成功的格式检查之后），则它将读入元数据并且格式化检查#2和检查#3等式以用于RepairObj的准备。执行批量读取内核调用，并将所有内容传输到内存中（位于content2read所指向的缓冲区内）。由于Foundure的解码、修复和更新操作完全基于BP算法，因此它在循环中仅在可用的局部集上顺序搜索一个未知数。为了减少计算和带宽，修复/解码过程必须首先使用小尺寸的检查#3方程，以便我们不必运行通过循环的末尾来完成整个修复过程。Foundure实现使用标准的qsort（. ）函数，然后填写RepairObj的相应字段。可以使用“parameter.h”文件中的参数ORDER_DERK_2和ORDER_DERK_3为检查#2和#3公式··Şuayb Ş. Arslan软件X 13（2021）10066282=算法4支票生成算法（CGA）1：程序CGA（B）输入矩阵B∈Fk×n2：L（2，3）<$In×n<$i单位矩阵3：whilezero_columns（B） w（b：，i），则8：如果w（b：，j<$b：，i）_check.data。因此，修复过程使用由编码器/解码器对的先前运行生成的元数据（规则集）。这一系列修改不会对现有的数据/编码块进行任何更改。为了触发/同步数据更改，我们最终需要使用适当的文件名调用fonsureRep函数。由于现有数据只被读取，并且我们使用最小基数，本地恢复组，在更新时，处理工作量最小化。我们最后注意到，由于Founture基于喷泉式代码，因此对可以生成的编码符号的数量没有实际限制。可以看出，Foundure的更新功能是在观察上述所需功能的基础上设计和实现的。····Şuayb Ş. Arslan软件X 13（2021）1006629∈G∈G∈i=0时|| =G3. 高级功能尽管前面的部分已经介绍了Foundure的许多高级特性，但我们还有两个更重要的特定于实现的高级特性，它们使Foundure3.1. 共享内存并行在共享内存的多处理器体系结构中，线程可以用来实现并行性。共享内存标准openMP是一个高级的可移植接口，它使多线程功能的使用更加容易，并获得令人满意的性能改进。许多擦除编码库（例如Jerasure 2.0 [7]）具有包括独立的“for "循环迭代的编码/解码引擎，因此具有多线程处理的巨大潜力。在[20]和[21]中研究了Jerasure 2.0如可见于图 3对于fonsureEnc，软件由循环执行的三个阶段组成。 然而，其 中两个阶段， 即将数据读取 到留在内存中的EncoderObj和DecoderObj中，以及将对象内容写入持久存储设备需要内核I/O调用。由于这些调用，性能将受到底层存储设备I/O带宽的吞吐量性能的抑制因此，我们的重点基本上是第二阶段，即纯编码和解码，其中数据只在CPU缓存和主存之间遍历。Foundure利用共享内存方法标准OpenMP库指令来帮助