[tahoe-dev] GSoC: MDMF mutable files
Kevan Carstensen
kevan at isnotajoke.com
Thu Apr 22 12:14:41 PDT 2010
Hi tahoe-dev,
I wrote a proposal to implement the MDMF scheme (as introduced in ticket
#393 [1]) as a Google Summer of Code project. As the ticket and my
project proposal discuss, current mutable files suffer a number of
serious performance problems, making them unsuited to general use (i.e.,
use in the same way as immutable files can be used). The MDMF scheme
will address the most severe of these issues, and will make it possible
to use mutable files in a general way.
The text of my project proposal is below. If you have any questions,
comments, or suggestions on what I've proposed, please feel free to let
me know.
Thanks,
=== Begin proposal ===
## Abstract
The current mutable file design in Tahoe-LAFS does not scale well to
files of arbitrary size. Creating, reading, or modifying a mutable file
uses memory proportional to the size of the file, and it is not possible
to read or modify part of a mutable file without reading or modifying
all of the mutable file. These behaviors are not consistent with how
users expect mutable files to behave [2]. To fix this, I will implement
the "Medium sized Distributed Mutable Files" scheme described in ticket
#393 [1]. The MDMF scheme will give Tahoe-LAFS mutable files that can be
created and modified while using a constant (and relatively small)
amount of memory, can (as a result) scale efficiently to large sizes,
and can be read and updated with greater specificity than they can now.
## Background
Roughly, the current mutable file upload process proceeds as follows:
- Read, encrypt, and encode all of the file. For each share, generate
a block hash tree (of one node/hash, since there is only one block
per share, since this process does not segment the file)
- Use the root hashes of the block hash trees generated in the
previous step to generate a share hash tree. Compute, for each
share, the necessary nodes in the share hash tree to validate that
share's root block hash
- Push the shares to the grid, along with the root of the share hash
tree and, for each server, the appropriate block hash tree and share
hash chain, as computed in the previous step.
(the actual code that does this is in [3])
Compare this with the immutable file upload process, which can be
roughly expressed as:
- For each segment of the file,
- Encrypt and encode the segment
- Send shares from the segment (called blocks) to the servers on the
grid responsible for holding them.
- Store hashes of the shares just sent.
- For each share (a collection of blocks, one for each segment),
construct the block hash tree (a merkle tree over all of the blocks
associated with a share), and send it to the server responsible for
holding the share.
- Using the roots of the block hash trees computed above, compute the
share hash tree (a merkle tree over all of the shares, where each
share is represented by the root of its block hash tree). Send the
root of this tree to all servers holding shares for this upload, and
send the components of the share hash tree necessary to validate
each share to the server holding that share.
(the code that does this is in [4])
A key difference between this two processes is the use (or non-use) of
segments.
By processing segments of the source data, the immutable file upload
code is able to keep a near-constant (when we account for lists of block
hashes that grow with the upload) and relatively small memory footprint
throughout the entire upload process. Also, since decoding proceeds
segment-wise, immutable files are fairly responsive -- only a small
amount of data of even a large immutable file needs to be downloaded,
validated, and decoded before an application has plaintext to work with
-- enabling, for example, streaming downloads.
The mutable file code does not use segments, but instead processes all
of the source data at once. This means that the memory footprint of a
mutable file upload is proportional to the size of the source data. This
also means that the entire mutable file must be downloaded, validated,
and decoded before an application has any plaintext data to work with.
The MDMF scheme will address this by adding a meaningful notion of
segments to mutable file processing. If successful, this project will
make mutable files look, in terms of performance, much more like
immutable files than they currently do; the upload process for a mutable
file should, like that for an immutable file, have a near-constant and
relatively small memory footprint, while the process of reading a
mutable file should have similar responsiveness to the process of
reading an immutable file. It should also be possible to make small
changes in the middle of a mutable file without changing the entire
file. Finally, users should have the same strict assurances of
confidentiality and integrity with MDMF as they do with other files in
Tahoe-LAFS.
## Backward and Forward Compatibility
A note on #393 suggests that we will need to use a separate AES key for
each MDMF segment -- derived from the existing AES key by way of a table
of salts (or a table of IVs for AES in counter mode). This table will
need to be stored server-side in the UEB. Further, the current mutable
file retrieval code does not know how to process mutable files with more
than one segment. MDMF, then, would almost certainly break forward
compatibility for older versions of Tahoe-LAFS. Since one of the goals
of Tahoe-LAFS is robust forward-compatibility, a successful MDMF
implementation would need to address this.
One possible solution to this problem would be to define a different cap
for MDMF files, keeping the existing mutable file cap format for SDMF
files. Tahoe-LAFS-from-the-future would retain the ability to read and
write SDMF, which could then be used internally (e.g., for directories)
if there is a compelling reason to do so. Versions of Tahoe-LAFS from
the past would be able to read and write SDMF, and would treat MDMF caps
as caps-from-the-future, something which is handled quite well in
versions after 1.6.0, and suitably well in versions before that.
Another solution would be to bump the mutable file protocol version. The
current mutable file implementation (specifically, [5]) refuses to deal
with mutable files that use a higher protocol version number than it
understands. This is appealing if we no longer wish to use SDMF for
anything (though it would be possible to specify version number 0 for
SDMF files, version number 1 for MDMF files, and still retain the
ability to read and write both types of file), and somewhat simpler to
implement. Past versions of Tahoe-LAFS would, based on protocol version,
refuse to read or modify MDMF files, which addresses the
forward-compatibility concerns without the additional overhead of a new
cap type.
## Proposal
If we want to make a new cap format for MDMF, then the project breaks
down into:
- Discuss, design, and implement MDMF caps. Alter
docs/specifications/mutable.txt, docs/specfications/uri.txt, and any
other documentation to document the MDMF caps. Alter existing cap
handling code to handle MDMF caps. Define how MDMF mutable files
will be stored on storage servers, and document that as well.
- Design and implement a MDMFMutableFileNode class.
- Alter mutable/layout.py, mutable/publish.py, mutable/retrieve.py,
and other files to know about MDMFMutableFileNodes, and to handle
them appropriately. This means that MDMFMutableFileNodes will be
processed in segments, as are immutable files, and will be stored
with a table of per-segment salts so that confidentiality is assured
when they are updated. Depending on how format-agnostic the
server-side code is, this may involve changes there as well.
- Alter other areas of Tahoe-LAFS to use MDMFMutableFileNodes where
appropriate. In particular, the CLI should create MDMF mutable files,
the WUI should create MDMF mutable files, and the webapi should have
functionality for manipulating MDMF mutable files (this part probably
comes first)
If a version bump is okay, then the project breaks down into:
- Define mutable file protocol version 1. Document mutable file protocol
version 1.
- Alter existing retrieval code to understand mutable file protocol 1.
This means understanding per-segment AES keys (readkey + salt),
understanding variable-size block hash trees, and using them to validate
shares, and any other changes that may need to be made. Design these
alterations so that the retrieval code is still capable of understanding
protocol 0, and will do so seamlessly.
- Alter existing publish code to proceed segment-wise when creating or
modifying mutable files.
- Make sure that it is possible (internally) to query or update a range in
a mutable file, and that that happens in a reasonable amount of time.
- Expose the new range functionality in the webapi, and alter user
utilities to use it when appropriate.
## About Me
I'm a student studying for a Master's degree in Computer Science at
California Polytechnic State University, Pomona. I'll be available to
work on Tahoe-LAFS full-time over the summer.
I've worked with Tahoe-LAFS before; I have contributed several small
improvements and bugfixes to the project, have also contributed
documentation and code review, and have been following its development
(through IRC and the tahoe-dev mailing list) for the better part of a
year. I'm familiar with the codebase, and comfortable with the
requirements (thorough testing; clear, efficient, and robust code)
placed upon contributions.
I've worked as a programmer and system administrator throughout
college. I'm comfortable working with Python, Objective-C, C, and PHP.
Academically, I have an interest in security; particularly capabilities
and systems that use them, and cryptography. Outside of school, work,
and computers, I'm interested in cooking, food, and cars.
Contact
Kevan Carstensen
email: kacarstensen at csupomona.edu
IRC: kevan_ on freenode
[1] http://allmydata.org/trac/tahoe-lafs/ticket/393
[2] see, e.g., http://allmydata.org/pipermail/tahoe-dev/2010-January/003464.html
[3] http://allmydata.org/trac/tahoe-lafs/browser/src/allmydata/mutable/publish.py?rev=4164#L120
[4] http://allmydata.org/trac/tahoe-lafs/browser/src/allmydata/immutable/encode.py?rev=4114#L200
[5] http://allmydata.org/trac/tahoe-lafs/browser/src/allmydata/mutable/layout.py?rev=4164#L37
--
Kevan Carstensen | <kevan at isnotajoke.com>
More information about the tahoe-dev
mailing list