tahoe-lafs/trac

add streaming manifest/deep-checker/repairer #590

New issue

Closed

opened 2009-01-22 23:43:25 +00:00 by warner · 3 comments

warner commented

2009-01-22 23:43:25 +00:00

Our current deep-traversal webapi operations (manifest, deep-check,
deep-repair, and to a lesser extent deep-stats) run asynchronously. The
"start-operation" POST provides an unguessable "ophandle", the node builds up
a big table of results, and every once in a while the client polls to see if
the operation has completed (by doing a GET to /ophandle/$HANDLE), retrieving
a representation of the big table when it's done.

We changed to this async mode from a synchronous model in which the client
starts with a GET or a POST, the node builds up a big table of results, then
the node returns the representation of that table to the initial GET/POST
request. We made this change because a deep-check (in particular deep-verify
or repair) can take a very long time, days or weeks for very large/deep
directory structures, and HTTP requests felt fragile: browsers get
interrupted, network addresses change, routes flap, etc. The idea of losing a
lot of progress on a deep-traversal operation felt unacceptable to us.

However, the big table that is generated by any traversal operations (except
for the trivial deep-stats) on a large directory structure is a problem all
by itself. For several allmydata.com accounts, we're seeing upwards of 500k
directories, and millions of files. This results in the tahoe node using
something like 700MB of ram to hold this table, which (depending upon the
host) results in swap thrash. In addition, the act of polling for the results
causes large memory usage, both in the server (to translate the table into,
say. JSON), and in the client (to translate it back).

We're currently trying to improve the efficiency and usability of
deep-repair. We'd like to try a more streaming approach: one tool traverses
the directory structure and builds up a list of filecaps/dircaps. A second
tool then walks that list, performing a check on each file, writing the
results to a second list. A third tool reads that check-results list, decides
which files need repair, and performs a repair on those files. A dispatch
tool could run these components on multiple allmydata.com accounts with
whatever degree of parallelism seems appropriate.

All these tools but the first deep-traversal tool could be interrupted and
pick up where they left off, if they kept suitable state about how far they'd
gotten through their (linear) list of work to do. The deep-traversal tool
would not have this luxury (since it's state is basically embedded in the
python stack of the deep-traversal code inside a tahoe node), but hopefully
the chances of interrupting a manifest operation are relatively low.

So, to accomplish this, and to reduce the memory usage of the node and CLI
tool in question, we'd like to have streaming forms of 'build-manifest' and
'deep-check'. These forms will execute in a single HTTP operation (perhaps
GET for manifest, since it has no side-effects, and POST for deep-check,
since with the repair=true option is does have side-effects). Each form
will emit incrementally-parseable units of status as part of their HTTP
response body, one unit per file visited. When the traversal is complete, a
second kind of unit may be emitted to report e.g. the deep-stats summary.

The CLI tools which use these interfaces will be able to read the response
body incrementally, parsing each unit as they arrive, and then writing a
summary to a file for further processing. At no point with either the Tahoe
node or the CLI tool be holding information about more than a single file at
a time. The Tahoe node's stack will, of course, hold state to manage the
deep-traversal operation, but the size of this state is related to the depth
of the directory tree (worst case is the size of all ancestors and
uncle-nodes of the deepest child node), which is roughly log(N) instead of N.

The individual units can be JSON, as long as the stream has some easily
parseable delimiters so the client can know where one unit ends and the next
one begins. If we can guarantee that the JSON does not contain a newline,
then we can use newlines as delimiters. If we can't enforce any such
restrictions on the JSON, then we'd have to use netstrings for each unit, and
parsing them is a bit harder.

If the individual units have a more custom format (like
"\nSI=xxx;CAP=xxx;SIZE=xxx;HEALTHY=true\n"), then we can use tools like
'grep' on the output to e.g. filter out the files that need repair. It may be
easier to use JSON and write our tools in Python.

Our current deep-traversal webapi operations (manifest, deep-check, deep-repair, and to a lesser extent deep-stats) run asynchronously. The "start-operation" POST provides an unguessable "ophandle", the node builds up a big table of results, and every once in a while the client polls to see if the operation has completed (by doing a GET to /ophandle/$HANDLE), retrieving a representation of the big table when it's done. We changed to this async mode from a synchronous model in which the client starts with a GET or a POST, the node builds up a big table of results, then the node returns the representation of that table to the initial GET/POST request. We made this change because a deep-check (in particular deep-verify or repair) can take a very long time, days or weeks for very large/deep directory structures, and HTTP requests felt fragile: browsers get interrupted, network addresses change, routes flap, etc. The idea of losing a lot of progress on a deep-traversal operation felt unacceptable to us. However, the big table that is generated by any traversal operations (except for the trivial deep-stats) on a large directory structure is a problem all by itself. For several allmydata.com accounts, we're seeing upwards of 500k directories, and millions of files. This results in the tahoe node using something like 700MB of ram to hold this table, which (depending upon the host) results in swap thrash. In addition, the act of polling for the results causes large memory usage, both in the server (to translate the table into, say. JSON), and in the client (to translate it back). We're currently trying to improve the efficiency and usability of deep-repair. We'd like to try a more streaming approach: one tool traverses the directory structure and builds up a list of filecaps/dircaps. A second tool then walks that list, performing a check on each file, writing the results to a second list. A third tool reads that check-results list, decides which files need repair, and performs a repair on those files. A dispatch tool could run these components on multiple allmydata.com accounts with whatever degree of parallelism seems appropriate. All these tools but the first deep-traversal tool could be interrupted and pick up where they left off, if they kept suitable state about how far they'd gotten through their (linear) list of work to do. The deep-traversal tool would not have this luxury (since it's state is basically embedded in the python stack of the deep-traversal code inside a tahoe node), but hopefully the chances of interrupting a manifest operation are relatively low. So, to accomplish this, and to reduce the memory usage of the node and CLI tool in question, we'd like to have streaming forms of 'build-manifest' and 'deep-check'. These forms will execute in a single HTTP operation (perhaps GET for manifest, since it has no side-effects, and POST for deep-check, since with the repair=true option is *does* have side-effects). Each form will emit incrementally-parseable units of status as part of their HTTP response body, one unit per file visited. When the traversal is complete, a second kind of unit may be emitted to report e.g. the deep-stats summary. The CLI tools which use these interfaces will be able to read the response body incrementally, parsing each unit as they arrive, and then writing a summary to a file for further processing. At no point with either the Tahoe node or the CLI tool be holding information about more than a single file at a time. The Tahoe node's stack will, of course, hold state to manage the deep-traversal operation, but the size of this state is related to the depth of the directory tree (worst case is the size of all ancestors and uncle-nodes of the deepest child node), which is roughly log(N) instead of N. The individual units can be JSON, as long as the stream has some easily parseable delimiters so the client can know where one unit ends and the next one begins. If we can guarantee that the JSON does not contain a newline, then we can use newlines as delimiters. If we can't enforce any such restrictions on the JSON, then we'd have to use netstrings for each unit, and parsing them is a bit harder. If the individual units have a more custom format (like "\nSI=xxx;CAP=xxx;SIZE=xxx;HEALTHY=true\n"), then we can use tools like 'grep' on the output to e.g. filter out the files that need repair. It may be easier to use JSON and write our tools in Python.

warner added the

c/code-frontend-web

labels 2009-01-22 23:43:25 +00:00

warner added this to the undecided milestone 2009-01-22 23:43:25 +00:00

warner commented

2009-02-17 05:42:41 +00:00

Author

changeset:476a5c8fac9909d5 adds the stream-deep-check webapi command, which includes repair=true. An earlier patch (which made it into 1.3.0, unlike changeset:476a5c8fac9909d5) added stream-manifest.

The units are JSON, with no internal newlines, so there is one line of output per file/directory examined, plus one at the end with the aggregate stats. We can't use grep on the output, but the python tool that uses ```[for line in out.splitlines()]simplejson.loads(line)))) is easy to write.

The only piece left is to modify the tahoe deep-check tool to use this streaming API instead of the old polling one. tahoe manifest has already been updated.

I think this is now complete.

changeset:476a5c8fac9909d5 adds the stream-deep-check webapi command, which includes repair=true. An earlier patch (which made it into 1.3.0, unlike changeset:476a5c8fac9909d5) added stream-manifest. The units are JSON, with no internal newlines, so there is one line of output per file/directory examined, plus one at the end with the aggregate stats. We can't use grep on the output, but the python tool that uses ```[for line in out.splitlines()]simplejson.loads(line)))) is easy to write. The only piece left is to modify the `tahoe deep-check` tool to use this streaming API instead of the old polling one. `tahoe manifest` has already been updated. I think this is now complete.

warner self-assigned this 2009-02-17 05:42:41 +00:00

warner commented

2009-02-17 23:36:32 +00:00

Author

changeset:fde2289e7b1fda8a updates the CLI "tahoe deep-check" command to use the streaming form.

changeset:fde2289e7b1fda8a updates the CLI "tahoe deep-check" command to use the streaming form.

warner added the

label 2009-02-17 23:36:32 +00:00

warner closed this issue

2009-02-17 23:36:32 +00:00

warner commented

2009-02-25 05:48:13 +00:00

Author

And changeset:fd4ceb6a8762924c + changeset:a3c1fe35d9eda0df update the CLI commands to report errors properly.

And changeset:fd4ceb6a8762924c + changeset:a3c1fe35d9eda0df update the CLI commands to report errors properly.

Sign in to join this conversation.

No labels

c/code-dirnodes

c/code-encoding

c/code-frontend

c/code-frontend-cli

c/code-frontend-ftp-sftp

c/code-frontend-magic-folder

c/code-frontend-web

c/code-nodeadmin

c/code-peerselection

c/dev-infrastructure

kw:AttributeError

kw:DataUnavailable

kw:DeadReferenceError

kw:GetLastError

kw:IFinishableConsumer

kw:LeastAuthority

kw:RIStorageServer

kw:UncoordinatedWriteError

kw:access-control

kw:accessibility

kw:accounting-crawler

kw:anti-censorship

kw:api_auth_token

kw:authentication

kw:availability

kw:backward-compatibility

kw:blocks-cloud-deployment

kw:blocks-cloud-merge

kw:blocks-magic-folder-merge

kw:blocks-merge

kw:blocks-release

kw:brians-opinion-needed

kw:build-helpers

kw:cloud-backend

kw:coding-standards

kw:coding-tools

kw:coding_tools

kw:compatibility

kw:confidentiality

kw:configuration

kw:configuration.txt

kw:connectivity

kw:control.furl

kw:coordination

kw:coveralls.io

kw:create-container

kw:cryptography

kw:cryptography-lib

kw:denial-of-service

kw:desert-island

kw:desert-island-build

kw:design-review-needed

kw:dev-infrastructure

kw:directory-page

kw:disk-backend

kw:earth-dragon

kw:erasure-coding

kw:excess-authority

kw:extensibility

kw:file-descriptor

kw:floatingpoint

kw:forward-compatibility

kw:forward-secrecy

kw:garbage-collection

kw:google-cloud-storage

kw:google-drive-backend

kw:grid-manager

kw:illustration

kw:inlineCallbacks

kw:integration-test

kw:interoperability

kw:interstellar-exploration

kw:introduction

kw:key-value-store

kw:magic-folder

kw:manual-test-needed

kw:more-info-needed

kw:mountain-lion

kw:multiuser-gateway

kw:needs-review

kw:notification

kw:notifyOnDisconnect

kw:openitp-packaging

kw:operation-helpers

kw:optimization

kw:organization

kw:otf-magic-folder-objective1

kw:otf-magic-folder-objective2

kw:otf-magic-folder-objective3

kw:otf-magic-folder-objective4

kw:otf-magic-folder-objective5

kw:otf-magic-folder-objective6

kw:peer-selection

kw:pkg_resources

kw:preservation

kw:pycrypto-lib

kw:pyfilesystem

kw:random-access

kw:raspberry-pi

kw:release-blocker

kw:removable-disk

kw:reserved_space

kw:response-needed

kw:response-time

kw:review-needed

kw:self-contained

kw:servers-of-happiness

kw:setup_requires

kw:setuptools_darcs

kw:simultaneous

kw:space-efficiency

kw:static-analysis

kw:stats_gatherer

kw:tahoe-add-alias

kw:tahoe-archive

kw:tahoe-backup

kw:tahoe-create-alias

kw:tahoe-create-introducer

kw:tahoe-deep-check

kw:tahoe-deepcheck

kw:tahoe-lafs-trac-stream

kw:tahoe-list-aliases

kw:tahoe-magic-folder

kw:tahoe-manifest

kw:tahoe-restart

kw:tahoe-unlink

kw:tahoe-webopen

kw:test-and-set

kw:test-from-egg

kw:ticket999-s3-backend

kw:to-be-closed-on-2011-08-01

kw:tor-protocol

kw:transparency

kw:tub.location

kw:twisted-trial

kw:uncoordinated-writes

kw:unfinished-business

kw:unhandled-error

kw:upload-helper

kw:visualization

kw:volunteergrid2

kw:warners-opinion-needed

kw:welcome-page

kw:windows-related

kw:world-domination

kw:write-enabler

kw:zookos-opinion-needed

kw:zope.interface

p/supercritical

r/cannot reproduce

r/somebody else's problem

r/was already fixed

v/1.9.0-s3branch

No milestone

No project

No assignees

1 participant

Notifications

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference: tahoe-lafs/trac#590

No description provided.