zfec/README.txt

   1  * Intro and Licence
   2
   3 This package implements an "erasure code", or "forward error correction code".
   4
   5 You may use this package under the GNU General Public License, version 2 or, at
   6 your option, any later version.  You may use this package under the Transitive
   7 Grace Period Public Licence, version 1.0 or, at your option, any later version.
   8 (You may choose to use this package under the terms of either licence, at your
   9 option.)  See the file COPYING.GPL for the terms of the GNU General Public
  10 License, version 2.  See the file COPYING.TGPPL.html for the terms of the
  11 Transitive Grace Period Public Licence, version 1.0.  In addition, Allmydata,
  12 Inc. offers other licensing terms.  If you would like to inquire about a
  13 commercial relationship with Allmydata, Inc., please contact
  14 partnerships@allmydata.com and visit http://allmydata.com .
  15
  16 The most widely known example of an erasure code is the RAID-5 algorithm which
  17 makes it so that in the event of the loss of any one hard drive, the stored data
  18 can be completely recovered.  The algorithm in the zfec package has a similar
  19 effect, but instead of recovering from the loss of only a single element, it can
  20 be parameterized to choose in advance the number of elements whose loss it can
  21 tolerate.
  22
  23 This package is largely based on the old "fec" library by Luigi Rizzo et al.,
  24 which is a mature and optimized implementation of erasure coding.  The zfec
  25 package makes several changes from the original "fec" package, including
  26 addition of the Python API, refactoring of the C API to support zero-copy
  27 operation, a few clean-ups and optimizations of the core code itself, and the
  28 addition of a command-line tool named "zfec".
  29
  30
  31  * Installation
  32
  33 This package is managed with the "setuptools" package management tool.  To build
  34 and install the package directly into your system, just run "python ./setup.py
  35 install".  If you prefer to keep the package limited to a specific directory so
  36 that you can manage it yourself (perhaps by using the "GNU stow") tool, then
  37 give it these arguments: "python ./setup.py install
  38 --single-version-externally-managed
  39 --record=${specificdirectory}/zfec-install.log --prefix=${specificdirectory}"
  40
  41 To run the self-tests, execute "python ./setup.py test" (or if you have Twisted
  42 Python installed, you can run "trial zfec" for nicer output and test options.)
  43 This will run the tests of the C API, the Python API, and the command-line
  44 tools.
  45
  46 To run the tests of the Haskell API:
  47   % runhaskell haskell/test/FECTest.hs
  48
  49 Note that in order to run the Haskell API tests you must have installed the
  50 library first due to the fact that the interpreter cannot process FEC.hs as it
  51 takes a reference to an FFI function.
  52
  53
  54  * Community
  55
  56 The source is currently available via darcs on the web with the command:
  57
  58 darcs get http://allmydata.org/source/zfec/trunk
  59
  60 More information on darcs is available at http://darcs.net
  61
  62 Please join the zfec mailing list and submit patches:
  63
  64 <http://allmydata.org/cgi-bin/mailman/listinfo/zfec-dev>
  65
  66
  67  * Overview
  68
  69 This package performs two operations, encoding and decoding.  Encoding takes
  70 some input data and expands its size by producing extra "check blocks", also
  71 called "secondary blocks".  Decoding takes some data -- any combination of
  72 blocks of the original data (called "primary blocks") and "secondary blocks",
  73 and produces the original data.
  74
  75 The encoding is parameterized by two integers, k and m.  m is the total number
  76 of blocks produced, and k is how many of those blocks are necessary to
  77 reconstruct the original data.  m is required to be at least 1 and at most 256,
  78 and k is required to be at least 1 and at most m.
  79
  80 (Note that when k == m then there is no point in doing erasure coding -- it
  81 degenerates to the equivalent of the Unix "split" utility which simply splits
  82 the input into successive segments.  Similarly, when k == 1 it degenerates to
  83 the equivalent of the unix "cp" utility -- each block is a complete copy of the
  84 input data.)
  85
  86 Note that each "primary block" is a segment of the original data, so its size is
  87 1/k'th of the size of original data, and each "secondary block" is of the same
  88 size, so the total space used by all the blocks is m/k times the size of the
  89 original data (plus some padding to fill out the last primary block to be the
  90 same size as all the others).  In addition to the data contained in the blocks
  91 themselves there are also a few pieces of metadata which are necessary for later
  92 reconstruction.  Those pieces are: 1.  the value of K, 2.  the value of M, 3.
  93 the sharenum of each block, 4.  the number of bytes of padding that were used.
  94 The "zfec" command-line tool compresses these pieces of data and prepends them
  95 to the beginning of each share, so each the sharefile produced by the "zfec"
  96 command-line tool is between one and four bytes larger than the share data
  97 alone.
  98
  99 The decoding step requires as input k of the blocks which were produced by the
 100 encoding step.  The decoding step produces as output the data that was earlier
 101 input to the encoding step.
 102
 103
 104  * Command-Line Tool
 105
 106 The bin/ directory contains two Unix-style, command-line tools "zfec" and
 107 "zunfec".  Execute "zfec --help" or "zunfec --help" for usage instructions.
 108
 109 Note: a Unix-style tool like "zfec" does only one thing -- in this case erasure
 110 coding -- and leaves other tasks to other tools.  Other Unix-style tools that go
 111 well with zfec include "GNU tar" or "7z" a.k.a. "p7zip" for archiving multiple
 112 files and directories into one file, "7z" or "rzip" for compression, and "GNU Privacy
 113 Guard" for encryption or "sha256sum" for integrity.  It is important to do
 114 things in order: first archive, then compress, then either encrypt or sha256sum,
 115 then erasure code.  Note that if GNU Privacy Guard is used for privacy, then it
 116 will also ensure integrity, so the use of sha256sum is unnecessary in that case.
 117 Note that if 7z is used for archiving then it also does compression, so you
 118 don't need a separate compressor in that case.
 119
 120
 121  * Performance
 122
 123 On my Athlon 64 2.4 GHz workstation (running Linux), the "zfec" command-line
 124 tool encoded a 160 MB file with m=100, k=94 (about 6% redundancy) in 3.9
 125 seconds, where the "par2" tool encoded the file with about 6% redundancy in 27
 126 seconds.  zfec encoded the same file with m=12, k=6 (100% redundancy) in 4.1
 127 seconds, where par2 encoded it with about 100% redundancy in 7 minutes and 56
 128 seconds.
 129
 130 The underlying C library in benchmark mode encoded from a file at about 4.9
 131 million bytes per second and decoded at about 5.8 million bytes per second.
 132
 133 On Peter's fancy Intel Mac laptop (2.16 GHz Core Duo), it encoded from a file at
 134 about 6.2 million bytes per second.
 135
 136 On my even fancier Intel Mac laptop (2.33 GHz Core Duo), it encoded from a file
 137 at about 6.8 million bytes per second.
 138
 139 On my old PowerPC G4 867 MHz Mac laptop, it encoded from a file at about 1.3
 140 million bytes per second.
 141
 142 Here is a paper analyzing the performance of various erasure codes and their
 143 implementations, including zfec:
 144
 145 http://www.usenix.org/events/fast09/tech/full_papers/plank/plank.pdf
 146
 147 Zfec shows good performance on different machines and with different values of
 148 K and M. It also has a nice small memory footprint.
 149
 150
 151  * API
 152
 153 Each block is associated with "blocknum".  The blocknum of each primary block is
 154 its index (starting from zero), so the 0'th block is the first primary block,
 155 which is the first few bytes of the file, the 1'st block is the next primary
 156 block, which is the next few bytes of the file, and so on.  The last primary
 157 block has blocknum k-1.  The blocknum of each secondary block is an arbitrary
 158 integer between k and 255 inclusive.  (When using the Python API, if you don't
 159 specify which secondary blocks you want when invoking encode(), then it will by
 160 default provide the blocks with ids from k to m-1 inclusive.)
 161
 162  ** C API
 163
 164 fec_encode() takes as input an array of k pointers, where each pointer points to
 165 a memory buffer containing the input data (i.e., the i'th buffer contains the
 166 i'th primary block).  There is also a second parameter which is an array of the
 167 blocknums of the secondary blocks which are to be produced.  (Each element in
 168 that array is required to be the blocknum of a secondary block, i.e. it is
 169 required to be >= k and < m.)
 170
 171 The output from fec_encode() is the requested set of secondary blocks which are
 172 written into output buffers provided by the caller.
 173
 174 Note that this fec_encode() is a "low-level" API in that it requires the input
 175 data to be provided in a set of memory buffers of exactly the right sizes.  If
 176 you are starting instead with a single buffer containing all of the data then
 177 please see easyfec.py's "class Encoder" as an example of how to split a single
 178 large buffer into the appropriate set of input buffers for fec_encode().  If you
 179 are starting with a file on disk, then please see filefec.py's
 180 encode_file_stringy_easyfec() for an example of how to read the data from a file
 181 and pass it to "class Encoder".  The Python interface provides these
 182 higher-level operations, as does the Haskell interface.  If you implement
 183 functions to do these higher-level tasks in other languages than Python or
 184 Haskell, then please send a patch to zfec-dev@allmydata.org so that your API can
 185 be included in future releases of zfec.
 186
 187
 188 fec_decode() takes as input an array of k pointers, where each pointer points to
 189 a buffer containing a block.  There is also a separate input parameter which is
 190 an array of blocknums, indicating the blocknum of each of the blocks which is
 191 being passed in.
 192
 193 The output from fec_decode() is the set of primary blocks which were missing
 194 from the input and had to be reconstructed.  These reconstructed blocks are
 195 written into output buffers provided by the caller.
 196
 197
 198  ** Python API
 199
 200 encode() and decode() take as input a sequence of k buffers, where a "sequence"
 201 is any object that implements the Python sequence protocol (such as a list or
 202 tuple) and a "buffer" is any object that implements the Python buffer protocol
 203 (such as a string or array).  The contents that are required to be present in
 204 these buffers are the same as for the C API.
 205
 206 encode() also takes a list of desired blocknums.  Unlike the C API, the Python
 207 API accepts blocknums of primary blocks as well as secondary blocks in its list
 208 of desired blocknums.  encode() returns a list of buffer objects which contain
 209 the blocks requested.  For each requested block which is a primary block, the
 210 resulting list contains a reference to the apppropriate primary block from the
 211 input list.  For each requested block which is a secondary block, the list
 212 contains a newly created string object containing that block.
 213
 214 decode() also takes a list of integers indicating the blocknums of the blocks
 215 being passed int.  decode() returns a list of buffer objects which contain all
 216 of the primary blocks of the original data (in order).  For each primary block
 217 which was present in the input list, then the result list simply contains a
 218 reference to the object that was passed in the input list.  For each primary
 219 block which was not present in the input, the result list contains a newly
 220 created string object containing that primary block.
 221
 222 Beware of a "gotcha" that can result from the combination of mutable data and
 223 the fact that the Python API returns references to inputs when possible.
 224
 225 Returning references to its inputs is efficient since it avoids making an
 226 unnecessary copy of the data, but if the object which was passed as input is
 227 mutable and if that object is mutated after the call to zfec returns, then the
 228 result from zfec -- which is just a reference to that same object -- will also
 229 be mutated.  This subtlety is the price you pay for avoiding data copying.  If
 230 you don't want to have to worry about this then you can simply use immutable
 231 objects (e.g. Python strings) to hold the data that you pass to zfec.
 232
 233  ** Haskell API
 234
 235 The Haskell code is fully Haddocked, to generate the documentation, run
 236   % runhaskell Setup.lhs haddock
 237
 238
 239  * Utilities
 240
 241 The filefec.py module has a utility function for efficiently reading a file and
 242 encoding it piece by piece.  This module is used by the "zfec" and "zunfec"
 243 command-line tools from the bin/ directory.
 244
 245
 246  * Dependencies
 247
 248 A C compiler is required.  To use the Python API or the command-line tools a
 249 Python interpreter is also required.  We have tested it with Python v2.4 and
 250 v2.5.  For the Haskell interface, GHC >= 6.8.1 is required.
 251
 252
 253  * Acknowledgements
 254
 255 Thanks to the author of the original fec lib, Luigi Rizzo, and the folks that
 256 contributed to it: Phil Karn, Robert Morelos-Zaragoza, Hari Thirumoorthy, and
 257 Dan Rubenstein.  Thanks to the Mnet hackers who wrote an earlier Python wrapper,
 258 especially Myers Carpenter and Hauke Johannknecht.  Thanks to Brian Warner and
 259 Amber O'Whielacronx for help with the API, documentation, debugging,
 260 compression, and unit tests.  Thanks to Adam Langley for improving the C API and
 261 contributing the Haskell API.  Thanks to the creators of GCC (starting with
 262 Richard M. Stallman) and Valgrind (starting with Julian Seward) for a pair of
 263 excellent tools.  Thanks to my coworkers at Allmydata -- http://allmydata.com --
 264 Fabrice Grinda, Peter Secor, Rob Kinninmont, Brian Warner, Zandr Milewski,
 265 Justin Boreta, Mark Meras for sponsoring this work and releasing it under a Free
 266 Software licence.
 267
 268
 269 Enjoy!
 270
 271 Zooko Wilcox-O'Hearn
 272 2008-01-20
 273 Boulder, Colorado