+++ /dev/null
-
-
-zfec -- efficient, portable erasure coding tool
-===============================================
-
-Generate redundant blocks of information such that if some of the blocks are
-lost then the original data can be recovered from the remaining blocks. This
-package includes command-line tools, C API, Python API, and Haskell API.
-
-
-Intro and Licence
------------------
-
-This package implements an "erasure code", or "forward error correction
-code".
-
-You may use this package under the GNU General Public License, version 2 or,
-at your option, any later version. You may use this package under the
-Transitive Grace Period Public Licence, version 1.0 or, at your option, any
-later version. (You may choose to use this package under the terms of either
-licence, at your option.) See the file COPYING.GPL for the terms of the GNU
-General Public License, version 2. See the file COPYING.TGPPL.rst for the
-terms of the Transitive Grace Period Public Licence, version 1.0.
-
-The most widely known example of an erasure code is the RAID-5 algorithm
-which makes it so that in the event of the loss of any one hard drive, the
-stored data can be completely recovered. The algorithm in the zfec package
-has a similar effect, but instead of recovering from the loss of only a
-single element, it can be parameterized to choose in advance the number of
-elements whose loss it can tolerate.
-
-This package is largely based on the old "fec" library by Luigi Rizzo et al.,
-which is a mature and optimized implementation of erasure coding. The zfec
-package makes several changes from the original "fec" package, including
-addition of the Python API, refactoring of the C API to support zero-copy
-operation, a few clean-ups and optimizations of the core code itself, and the
-addition of a command-line tool named "zfec".
-
-
-Installation
-------------
-
-This package is managed with the "setuptools" package management tool. To
-build and install the package directly into your system, just run ``python
-./setup.py install``. If you prefer to keep the package limited to a
-specific directory so that you can manage it yourself (perhaps by using the
-"GNU stow") tool, then give it these arguments: ``python ./setup.py install
---single-version-externally-managed
---record=${specificdirectory}/zfec-install.log
---prefix=${specificdirectory}``
-
-To run the self-tests, execute ``python ./setup.py test`` (or if you have
-Twisted Python installed, you can run ``trial zfec`` for nicer output and
-test options.) This will run the tests of the C API, the Python API, and the
-command-line tools.
-
-To run the tests of the Haskell API: ``runhaskell haskell/test/FECTest.hs``
-
-Note that in order to run the Haskell API tests you must have installed the
-library first due to the fact that the interpreter cannot process FEC.hs as
-it takes a reference to an FFI function.
-
-
-Community
----------
-
-The source is currently available via darcs on the web with the command:
-
-darcs get https://tahoe-lafs.org/source/zfec/trunk
-
-More information on darcs is available at http://darcs.net
-
-Please post about zfec to the Tahoe-LAFS mailing list and contribute patches:
-
-<https://tahoe-lafs.org/cgi-bin/mailman/listinfo/tahoe-dev>
-
-
-Overview
---------
-
-This package performs two operations, encoding and decoding. Encoding takes
-some input data and expands its size by producing extra "check blocks", also
-called "secondary blocks". Decoding takes some data -- any combination of
-blocks of the original data (called "primary blocks") and "secondary blocks",
-and produces the original data.
-
-The encoding is parameterized by two integers, k and m. m is the total
-number of blocks produced, and k is how many of those blocks are necessary to
-reconstruct the original data. m is required to be at least 1 and at most
-256, and k is required to be at least 1 and at most m.
-
-(Note that when k == m then there is no point in doing erasure coding -- it
-degenerates to the equivalent of the Unix "split" utility which simply splits
-the input into successive segments. Similarly, when k == 1 it degenerates to
-the equivalent of the unix "cp" utility -- each block is a complete copy of
-the input data.)
-
-Note that each "primary block" is a segment of the original data, so its size
-is 1/k'th of the size of original data, and each "secondary block" is of the
-same size, so the total space used by all the blocks is m/k times the size of
-the original data (plus some padding to fill out the last primary block to be
-the same size as all the others). In addition to the data contained in the
-blocks themselves there are also a few pieces of metadata which are necessary
-for later reconstruction. Those pieces are: 1. the value of K, 2. the
-value of M, 3. the sharenum of each block, 4. the number of bytes of
-padding that were used. The "zfec" command-line tool compresses these pieces
-of data and prepends them to the beginning of each share, so each the
-sharefile produced by the "zfec" command-line tool is between one and four
-bytes larger than the share data alone.
-
-The decoding step requires as input k of the blocks which were produced by
-the encoding step. The decoding step produces as output the data that was
-earlier input to the encoding step.
-
-
-Command-Line Tool
------------------
-
-The bin/ directory contains two Unix-style, command-line tools "zfec" and
-"zunfec". Execute ``zfec --help`` or ``zunfec --help`` for usage
-instructions.
-
-
-Performance
------------
-
-To run the benchmarks, execute the included bench/bench_zfec.py script with
-optional --k= and --m= arguments.
-
-On my Athlon 64 2.4 GHz workstation (running Linux), the "zfec" command-line
-tool encoded a 160 MB file with m=100, k=94 (about 6% redundancy) in 3.9
-seconds, where the "par2" tool encoded the file with about 6% redundancy in
-27 seconds. zfec encoded the same file with m=12, k=6 (100% redundancy) in
-4.1 seconds, where par2 encoded it with about 100% redundancy in 7 minutes
-and 56 seconds.
-
-The underlying C library in benchmark mode encoded from a file at about 4.9
-million bytes per second and decoded at about 5.8 million bytes per second.
-
-On Peter's fancy Intel Mac laptop (2.16 GHz Core Duo), it encoded from a file
-at about 6.2 million bytes per second.
-
-On my even fancier Intel Mac laptop (2.33 GHz Core Duo), it encoded from a
-file at about 6.8 million bytes per second.
-
-On my old PowerPC G4 867 MHz Mac laptop, it encoded from a file at about 1.3
-million bytes per second.
-
-Here is a paper analyzing the performance of various erasure codes and their
-implementations, including zfec:
-
-http://www.usenix.org/events/fast09/tech/full_papers/plank/plank.pdf
-
-Zfec shows good performance on different machines and with different values
-of K and M. It also has a nice small memory footprint.
-
-
-API
----
-
-Each block is associated with "blocknum". The blocknum of each primary block
-is its index (starting from zero), so the 0'th block is the first primary
-block, which is the first few bytes of the file, the 1'st block is the next
-primary block, which is the next few bytes of the file, and so on. The last
-primary block has blocknum k-1. The blocknum of each secondary block is an
-arbitrary integer between k and 255 inclusive. (When using the Python API,
-if you don't specify which secondary blocks you want when invoking encode(),
-then it will by default provide the blocks with ids from k to m-1 inclusive.)
-
-- C API
-
- fec_encode() takes as input an array of k pointers, where each pointer
- points to a memory buffer containing the input data (i.e., the i'th buffer
- contains the i'th primary block). There is also a second parameter which
- is an array of the blocknums of the secondary blocks which are to be
- produced. (Each element in that array is required to be the blocknum of a
- secondary block, i.e. it is required to be >= k and < m.)
-
- The output from fec_encode() is the requested set of secondary blocks which
- are written into output buffers provided by the caller.
-
- Note that this fec_encode() is a "low-level" API in that it requires the
- input data to be provided in a set of memory buffers of exactly the right
- sizes. If you are starting instead with a single buffer containing all of
- the data then please see easyfec.py's "class Encoder" as an example of how
- to split a single large buffer into the appropriate set of input buffers
- for fec_encode(). If you are starting with a file on disk, then please see
- filefec.py's encode_file_stringy_easyfec() for an example of how to read
- the data from a file and pass it to "class Encoder". The Python interface
- provides these higher-level operations, as does the Haskell interface. If
- you implement functions to do these higher-level tasks in other languages,
- please send a patch to tahoe-dev@tahoe-lafs.org so that your API can be
- included in future releases of zfec.
-
- fec_decode() takes as input an array of k pointers, where each pointer
- points to a buffer containing a block. There is also a separate input
- parameter which is an array of blocknums, indicating the blocknum of each
- of the blocks which is being passed in.
-
- The output from fec_decode() is the set of primary blocks which were
- missing from the input and had to be reconstructed. These reconstructed
- blocks are written into output buffers provided by the caller.
-
-
-- Python API
-
- encode() and decode() take as input a sequence of k buffers, where a
- "sequence" is any object that implements the Python sequence protocol (such
- as a list or tuple) and a "buffer" is any object that implements the Python
- buffer protocol (such as a string or array). The contents that are
- required to be present in these buffers are the same as for the C API.
-
- encode() also takes a list of desired blocknums. Unlike the C API, the
- Python API accepts blocknums of primary blocks as well as secondary blocks
- in its list of desired blocknums. encode() returns a list of buffer
- objects which contain the blocks requested. For each requested block which
- is a primary block, the resulting list contains a reference to the
- apppropriate primary block from the input list. For each requested block
- which is a secondary block, the list contains a newly created string object
- containing that block.
-
- decode() also takes a list of integers indicating the blocknums of the
- blocks being passed int. decode() returns a list of buffer objects which
- contain all of the primary blocks of the original data (in order). For
- each primary block which was present in the input list, then the result
- list simply contains a reference to the object that was passed in the input
- list. For each primary block which was not present in the input, the
- result list contains a newly created string object containing that primary
- block.
-
- Beware of a "gotcha" that can result from the combination of mutable data
- and the fact that the Python API returns references to inputs when
- possible.
-
- Returning references to its inputs is efficient since it avoids making an
- unnecessary copy of the data, but if the object which was passed as input
- is mutable and if that object is mutated after the call to zfec returns,
- then the result from zfec -- which is just a reference to that same object
- -- will also be mutated. This subtlety is the price you pay for avoiding
- data copying. If you don't want to have to worry about this then you can
- simply use immutable objects (e.g. Python strings) to hold the data that
- you pass to zfec.
-
-- Haskell API
-
- The Haskell code is fully Haddocked, to generate the documentation, run
- ``runhaskell Setup.lhs haddock``.
-
-
-Utilities
----------
-
-The filefec.py module has a utility function for efficiently reading a file
-and encoding it piece by piece. This module is used by the "zfec" and
-"zunfec" command-line tools from the bin/ directory.
-
-
-Dependencies
-------------
-
-A C compiler is required. To use the Python API or the command-line tools a
-Python interpreter is also required. We have tested it with Python v2.4,
-v2.5, v2.6, and v2.7. For the Haskell interface, GHC >= 6.8.1 is required.
-
-
-Acknowledgements
-----------------
-
-Thanks to the author of the original fec lib, Luigi Rizzo, and the folks that
-contributed to it: Phil Karn, Robert Morelos-Zaragoza, Hari Thirumoorthy, and
-Dan Rubenstein. Thanks to the Mnet hackers who wrote an earlier Python
-wrapper, especially Myers Carpenter and Hauke Johannknecht. Thanks to Brian
-Warner and Amber O'Whielacronx for help with the API, documentation,
-debugging, compression, and unit tests. Thanks to Adam Langley for improving
-the C API and contributing the Haskell API. Thanks to the creators of GCC
-(starting with Richard M. Stallman) and Valgrind (starting with Julian
-Seward) for a pair of excellent tools. Thanks to my coworkers at Allmydata
--- http://allmydata.com -- Fabrice Grinda, Peter Secor, Rob Kinninmont, Brian
-Warner, Zandr Milewski, Justin Boreta, Mark Meras for sponsoring this work
-and releasing it under a Free Software licence. Thanks to Jack Lloyd, Samuel
-Neves, and David-Sarah Hopwood.
-
-
-Related Works
--------------
-
-Note: a Unix-style tool like "zfec" does only one thing -- in this case
-erasure coding -- and leaves other tasks to other tools. Other Unix-style
-tools that go well with zfec include `GNU tar`_ for archiving multiple files
-and directories into one file, `lzip`_ for compression, and `GNU Privacy
-Guard`_ for encryption or `b2sum`_ for integrity. It is important to do
-things in order: first archive, then compress, then either encrypt or
-integrity-check, then erasure code. Note that if GNU Privacy Guard is used
-for privacy, then it will also ensure integrity, so the use of b2sum is
-unnecessary in that case. Note also that you also need to do integrity
-checking (such as with b2sum) on the blocks that result from the erasure
-coding in *addition* to doing it on the file contents! (There are two
-different subtle failure modes -- see "more than one file can match an
-immutable file cap" on the `Hack Tahoe-LAFS!`_ Hall of Fame.)
-
-The `Tahoe-LAFS`_ project uses zfec as part of a complete distributed
-filesystem with integrated encryption, integrity, remote distribution of the
-blocks, directory structure, backup of changed files or directories, access
-control, immutable files and directories, proof-of-retrievability, and repair
-of damaged files and directories.
-
-`fecpp`_ is an alternative to zfec. It implements a bitwise-compatible
-algorithm to zfec and is BSD-licensed.
-
-.. _GNU tar: http://directory.fsf.org/project/tar/
-.. _lzip: http://www.nongnu.org/lzip/lzip.html
-.. _GNU Privacy Guard: http://gnupg.org/
-.. _b2sum: https://blake2.net/
-.. _Tahoe-LAFS: https://tahoe-lafs.org
-.. _Hack Tahoe-LAFS!: https://tahoe-lafs.org/hacktahoelafs/
-.. _fecpp: http://www.randombit.net/code/fecpp/
-
-
-Enjoy!
-
-Zooko Wilcox-O'Hearn
-
-2013-05-15
-
-Boulder, Colorado
projects / tahoe-lafs / zfec.git / blobdiff