zfec/README.txt

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