zfec 1.5.3

简介和许可证

此包实现"擦除代码"或"前向纠错" 代码".< /P>"

您可以在GNU通用公共许可证第2版或， 您可以选择任何更高版本。您可以在 过渡宽限期公共许可证，1.0版，或根据您的选择，任何 更高版本。（您可以根据以下任一条款选择使用此软件包 许可证，由您选择。）有关GNU的条款，请参阅copying.gpl文件 通用公共许可证，第2版。有关 过渡宽限期公共许可条款，1.0版。

最广为人知的擦除代码示例是raid-5算法。 这使得在任何一个硬盘驱动器丢失的情况下， 存储的数据可以完全恢复。zfec包中的算法 有类似的效果，但不是从损失中恢复 单个元素，可以预先参数化选择 它能承受损失的元素。

这个包主要基于Luigi Rizzo等人的旧"FEC"库， 这是一个成熟和优化的擦除编码实现。ZFEC package对原来的"fec"包做了一些更改，包括 添加python api，重构c api以支持零拷贝 操作，一些核心代码本身的清理和优化，以及 添加名为"zfec"的命令行工具。

安装

pip安装zfec

要运行自检，请从解包的源代码树或git签出执行 tox 。

运行haskell api的测试： runhaskell haskell/test/fectest.hs

注意，为了运行haskell api测试，必须安装 首先是库，因为解释器无法将fec.hs作为 它引用一个ffi函数。

社区

该源程序当前可通过git在web上使用命令：

git克隆 https://github.com/tahoe lafs/zfec

请将有关zfec的信息发布到tahoe lafs邮件列表并提供修补程序：

<； https://tahoe-lafs.org/cgi-bin/mailman/listinfo/tahoe-dev >；

如果在zfec中发现错误，请在github上打开一个问题：

<； https://github.com/tahoe-lafs/zfec/issues >；

概述

这个包执行两个操作运算、编码和解码。编码接受 一些输入数据，并通过生成额外的"检查块"来扩展其大小。 称为"次级区块"。解码需要一些数据-任何组合 原始数据块（称为"主要块"）和"次要块"， 并生成原始数据。

编码由两个整数参数化，k和m是总数 生成的块数，k是这些块中有多少是必需的 重建原始数据。要求m至少为1且最多为1 256，k必须至少为1且最多为m。

（请注意，当k==m时，进行擦除编码是没有意义的–它 退化为等同于unix"split"实用程序，该实用程序只需将 连续段的输入。类似地，当k==1时，它退化为 相当于unix"cp"实用程序–每个块都是 输入数据。）

注意，每个"主块"都是原始数据的一段，所以它的大小 是原始数据大小的1/K，每个"次要块"是 大小相同，因此所有块使用的总空间是 原始数据（加上一些填充来填充最后一个主块 和其他的一样大）。除了包含在 块本身也有一些元数据是必需的 为了以后的重建。这些碎片是：1。k，2的值。这个 m，3的值。每个区块的股份数，4。的字节数 使用的填充物。"zfec"命令行工具压缩这些片段 数据，并将它们前置到每个共享的开头，因此每个 "zfec"命令行工具生成的共享文件介于1和4之间 比单独共享数据大的字节。

解码步骤要求将由 编码步骤。解码步骤输出 编码步骤的早期输入。

命令行工具

bin/目录包含两个unix风格的命令行工具"zfec"和 "zunfec"。执行 zfec --help 或 zunfec --help 以供使用 说明。

性能

要运行基准测试，请使用 可选–k=和–m=参数。

在我的Athlon 64 2.4 GHz工作站（运行Linux）上，"zfec"命令行 工具在3.9中编码了一个160 MB的文件，m=100，k=94（大约6%的冗余） 秒，其中"par2"工具在 27秒。zfec用m=12，k=6（100%冗余）编码同一文件 4.1秒，其中par2在7分钟内以大约100%的冗余度对其进行编码 56秒。

基准模式下的底层C库是从大约4.9的文件编码的 每秒一百万字节，解码速度约为每秒580万字节。

在Peter的漂亮Intel Mac笔记本电脑（2.16 GHz核心双核）上，它从一个文件中编码 每秒大约620万字节。

在我更喜欢的英特尔Mac笔记本电脑（2.33GHz核心双核）上，它从 每秒大约680万字节的文件。

在我的旧PowerPC G4 867 MHz Mac笔记本电脑上，它从1.3左右的文件中编码 每秒百万字节。

这里有一篇文章分析了各种擦除码的性能 实现，包括zfec:

http://www.usenix.org/events/fast09/tech/full戋u papers/plank/plank.pdf

zfec在不同的机器和不同的值上表现出良好的性能。 它的内存占用也很小。

API

每个块都与"blocknum"相关联。每个主块的blocknum 是它的索引（从零开始），因此第0个块是第一个主块 砌块ICH是文件的前几个字节，第一个块是下一个 主块，即文件的下几个字节，依此类推。最后 主块具有blocknum k-1。每个次块的blocknum是 k到255之间的任意整数。（使用PythonAPI时， 如果在调用encode（）时未指定所需的辅助块， 默认情况下，它将为块提供从k到m-1（包括k到m-1）的ID。

• C API

  fec_encode（）接受一个k指针数组作为输入，其中每个指针 指向包含输入数据的内存缓冲区（即第i个缓冲区 包含第i个主块）。还有第二个参数 是将要被 产生。（该数组中的每个元素都必须是 次块，即要求它是>；=k和<；m.）

  fec_encode（）的输出是请求的一组次要块，其中 写入调用者提供的输出缓冲区。

  注意，这个fec_encode（）是一个"低级"api，因为它需要 输入数据将被提供在一组完全正确的内存缓冲区中 尺寸。如果您使用一个包含所有 然后，请参阅easyfec.py的"类编码器"作为如何 将单个大缓冲区拆分为适当的输入缓冲区集 对于fec_encode（）。如果从磁盘上的文件开始，请参见 py的encode_file_stringy_easyfec（）作为如何读取的示例 文件中的数据并将其传递给"类编码器"。python接口 提供这些高级操作，haskell接口也是如此。如果 您可以用其他语言实现执行这些高级任务的函数， 请将修补程序发送到tahoe dev @tahoe dev tahoe lafs 以便您的api可以 包括在ZFEC的未来版本中。

  fec_decode（）接受一个k指针数组作为输入，其中每个指针 指向包含块的缓冲区。还有一个单独的输入 参数，它是一个blocknums数组，指示每个 正在传入的块的数目。

  fec_decode（）的输出是 输入丢失，必须重建。这些是重建的 块被写入调用方提供的输出缓冲区。

• python api

  encode（）和decode（）将k个缓冲区的序列作为输入，其中 "sequence"是实现python序列协议的任何对象（例如 作为列表或元组）和"缓冲区"是实现python的任何对象 缓冲区协议（如字符串或数组）。内容是 这些缓冲区中所需的内容与C API相同。

  encode（）还获取所需blocknum的列表。与C API不同的是， python api接受主块和次块的blocknum 在它想要的blocknum列表中。encode（）返回缓冲区列表 包含请求的块的对象。对于每个请求的块 是主块，结果列表包含对 从输入列表中应用主块。对于每个请求的块 这是一个辅助块，列表包含一个新创建的字符串对象 包含那个块。

  decode（）还获取一个整数列表，指示 传递的块int.decode（）返回缓冲区对象的列表 包含原始数据的所有主块（按顺序）。为了 输入列表中出现的每个主块，然后 列表只包含对输入中传递的对象的引用 名单。对于输入中不存在的每个主块， 结果列表包含一个新创建的字符串对象，该对象包含 块，

  谨防可变数据组合可能导致的"陷阱" tpython api在 可能的。

  返回对其输入的引用是有效的，因为它避免了 不必要的数据副本，但如果作为输入传递的对象 是可变的，如果在调用zfec返回后对该对象进行了变异， 然后是来自zfec的结果——它只是对同一个对象的引用 –也会发生变异。这个微妙之处是你为了避免 数据复制。如果你不想担心这个你可以 只需使用不可变对象（例如python字符串）来保存 您可以转到zfec。

• Haskell API

  haskell代码是完全haddocked的，要生成文档，请运行 runhaskell setup.lhs haddock

实用程序

py模块有一个实用函数，可以有效地读取文件 一个一个编码。此模块由"zfec"和 bin/目录中的"zunfec"命令行工具。

依赖关系

需要C编译器。要使用python api或命令行工具 还需要python解释器。我们已经用python v2.7测试过了， 3.5版和3.6版。对于Haskell接口，需要ghc>；=6.8.1。

致谢

多亏了最初的fec lib的作者luigi rizzo和那些 贡献者：菲尔·卡恩、罗伯特·莫雷洛斯·萨拉戈萨、哈里·蒂尔穆尔西和 丹·鲁宾斯坦。多亏了mnet的黑客们写了一个早期的python 包装纸，尤其是迈尔斯·卡彭特和豪克·约翰克尼赫特。感谢布莱恩 Warner和Amber O'Whielacronx需要有关API、文档的帮助， 调试、压缩和单元测试。感谢亚当·兰利的进步 c api和贡献haskell api。感谢GCC的创造者 （从Richard M.Stallman开始）和Valgrind（从Julian开始 为一对优秀的工具。感谢我在AllMyData的同事 – http://allmydata.com –法布里斯·格林达、彼得·塞科尔、罗布·金尼蒙特、布赖恩 华纳、赞德·米莱夫斯基、贾斯汀·博雷塔、马克·梅拉斯赞助了这项工作 在自由软件许可下发布。多亏了杰克·劳埃德，塞缪尔 奈维斯和大卫莎拉霍普伍德。

相关工作

注意：像"zfec"这样的unix风格的工具只做一件事-在本例中 擦除编码-并将其他任务留给其他工具。其他Unix样式 与zfec配合良好的工具包括用于归档多个文件的gnu tar 以及目录到一个文件中， lzip 用于压缩，以及 gnu隐私 加密保护或完整性保护。重要的是 按顺序排列：首先存档，然后压缩，然后加密或 完整性检查，然后删除代码。注意，如果使用GNU隐私保护 为了隐私，它还将确保完整性，因此b2sum的使用是 在那种情况下没有必要。还要注意的是，你还需要做到正直 对擦除产生的块进行检查（如使用b2sum） 在 addition 中编码以对文件内容执行此操作！（有两个 不同的细微故障模式–请参阅"多个文件可以匹配 不可变文件cap"在 hack tahoe lafs！ 名人堂。）

项目使用zfec作为完整分布式系统的一部分。 集成加密、完整性、远程分发的文件系统 块、目录结构、更改文件或目录的备份、访问 控件、不可变文件和目录、可检索性证明和修复 of损坏的文件和目录。

fecpp是zfec的替代品。它实现了按位兼容 算法到ZFEC并获得BSD许可。

佐科·威尔科克斯·奥赫恩

2013年5月15日

科罗拉多州博尔德