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