tahoe-lafs/trac

consider share-at-a-time uploader #1340

New issue

Open

opened 2011-01-27 19:09:11 +00:00 by warner · 1 comment

warner commented

2011-01-27 19:09:11 +00:00

As discussed in this thread:

http://tahoe-lafs.org/pipermail/tahoe-dev/2011-January/005963.html

(in response to discussion about UIs for #467 static-server-selection),
Chris Palmer described Octavia's is-it-uploaded-yet UI. I liked it, and
I'd like to explore how we might achieve something similar in Tahoe.
This ticket is to make sure we don't forget the idea.

The basic goal is to give each upload a sort of "red/yellow/green-light"
status indicator, showing how healthy/robust the file is. When the
upload first starts, it stays in the "red" state until there are enough
shares pushed to recover the file if it were to be deleted from the
original computer, then transitions into the "yellow" state. In that
state, more shares are uploaded until we've achieved the desired
diversity, at which point it goes "green".

The key differences from our current uploader:

we set N higher than usual, maybe 25 or even 50
we don't upload all N shares. Instead, we define some lower threshold
"Nup" (closer to our old N value) which indicates how many shares we
want to upload. The idea is that we could create more shares if we
wanted to, without changing the encoding parameters or the filecaps.
we store the whole file locally for longer, and do multiple passes
over it, instead of the almost-streaming approach we have now
the first pass generates all shares, builds all the hash trees, but
only uploads 'k' shares (discarding the rest)
subsequent passes re-use the cached hash trees, generate all shares
again, but only upload some other subset of the shares, maybe 'k' at
a time, or maybe more.
retain the whole file and the cached hash trees until we've uploaded
Nup shares
if the network is partitioned before Nup is achieved, or the client
is shut down, resume generating and uploading shares when it comes
back
have a realtime status icon which shows the aggregate
red/yellow/green state of all current uploads. This lets users know
when it's safe to close their laptops.

The general notion is to sacrifice some efficiency to reduce the time
needed to get to a mostly-safe upload. The original downloader generates
and uploads all shares in parallel, which eliminates wasted CPU cycles
and almost doesn't need the disk (and #320 plus some new CHK format
could make it fully streaming). But if the process is interrupted before
the very last close() is sent to each share, the whole upload fails and
must be started again from scratch. This new uploader would need more
local disk storage (to handle multiple passes), and waste some amount of
CPU (encoding shares that were then discarded, unless they too were
stored on local disk, and we learned from Tahoe's predecessor that disks
don't do matrix transpositions well), but would get the file to at least
a recoverable state in about the same time a normal non-encoded FTP
upload would have finished, and then gets better after that.

(caching the hashtrees would save some of the hashing time on the second
pass, which may or may not be a win, since hashing is generally pretty
quick too)

Some assumptions that must be tested before this scheme is at all
realistic:

generating extra shares (and then discarding them without pushing) is
cheap
generating N=25 or N=50 shares (and never uploading them, just
keeping the encoding space in reserve for the future) is cheap
building the hash trees on each pass, or caching them, is cheap
we can tolerate the extra disk IO (multiple passes over each file)

At present, zfec doesn't have an API to create fewer than N
shares: you have to make all of them and then throw some away. It might
be possible to enhance zfec to allow this (and of course do it
faster than create-and-discard: ideally, the CPU time would be
proportional to the number of shares we retain), but I haven't looked at
the Reed-Solomon encoding scheme enough to tell. If so, then the second
and subsequent passes could avoid the encoding waste (we'd still
generate each share twice: once on the first pass to build the hash
trees, and a second time on some subsequent pass when we actually push
that share).

Octavia uses pure replication (k=1), which removes the question of
encoding overhead, so it's a bit easier to use this scheme in Octavia
than in Tahoe.

The big big win of this approach is the UI. The k-of-N encoding
parameters don't matter quite so much when you can keep creating more
shares until you're happy with their distribution, so there might be
less need for users to choose k/N instead of sticking with the defaults.
And the "red/yellow/green" status light is a dead-simple UI indicator,
like the way Dropbox tells you when it's done moving data around.

The next step is probably to do some zfec performance tests, to find out
what setting N=25 (and then discarding the extra shares) would do to our
upload speed.

As discussed in this thread: <http://tahoe-lafs.org/pipermail/tahoe-dev/2011-January/005963.html> (in response to discussion about UIs for #467 static-server-selection), Chris Palmer described Octavia's is-it-uploaded-yet UI. I liked it, and I'd like to explore how we might achieve something similar in Tahoe. This ticket is to make sure we don't forget the idea. The basic goal is to give each upload a sort of "red/yellow/green-light" status indicator, showing how healthy/robust the file is. When the upload first starts, it stays in the "red" state until there are enough shares pushed to recover the file if it were to be deleted from the original computer, then transitions into the "yellow" state. In that state, more shares are uploaded until we've achieved the desired diversity, at which point it goes "green". The key differences from our current uploader: * we set N higher than usual, maybe 25 or even 50 * we don't upload all N shares. Instead, we define some lower threshold "Nup" (closer to our old N value) which indicates how many shares we want to upload. The idea is that we could create more shares if we wanted to, without changing the encoding parameters or the filecaps. * we store the whole file locally for longer, and do multiple passes over it, instead of the almost-streaming approach we have now * the first pass generates all shares, builds all the hash trees, but only uploads 'k' shares (discarding the rest) * subsequent passes re-use the cached hash trees, generate all shares again, but only upload some other subset of the shares, maybe 'k' at a time, or maybe more. * retain the whole file and the cached hash trees until we've uploaded Nup shares * if the network is partitioned before Nup is achieved, or the client is shut down, resume generating and uploading shares when it comes back * have a realtime status icon which shows the aggregate red/yellow/green state of all current uploads. This lets users know when it's safe to close their laptops. The general notion is to sacrifice some efficiency to reduce the time needed to get to a mostly-safe upload. The original downloader generates and uploads all shares in parallel, which eliminates wasted CPU cycles and almost doesn't need the disk (and #320 plus some new CHK format could make it fully streaming). But if the process is interrupted before the very last close() is sent to each share, the whole upload fails and must be started again from scratch. This new uploader would need more local disk storage (to handle multiple passes), and waste some amount of CPU (encoding shares that were then discarded, unless they too were stored on local disk, and we learned from Tahoe's predecessor that disks don't do matrix transpositions well), but would get the file to at least a recoverable state in about the same time a normal non-encoded FTP upload would have finished, and then gets better after that. (caching the hashtrees would save some of the hashing time on the second pass, which may or may not be a win, since hashing is generally pretty quick too) Some assumptions that must be tested before this scheme is at all realistic: * generating extra shares (and then discarding them without pushing) is cheap * generating N=25 or N=50 shares (and never uploading them, just keeping the encoding space in reserve for the future) is cheap * building the hash trees on each pass, or caching them, is cheap * we can tolerate the extra disk IO (multiple passes over each file) At present, `zfec` doesn't have an API to create fewer than N shares: you have to make all of them and then throw some away. It might be possible to enhance `zfec` to allow this (and of course do it faster than create-and-discard: ideally, the CPU time would be proportional to the number of shares we retain), but I haven't looked at the Reed-Solomon encoding scheme enough to tell. If so, then the second and subsequent passes could avoid the encoding waste (we'd still generate each share twice: once on the first pass to build the hash trees, and a second time on some subsequent pass when we actually push that share). Octavia uses pure replication (k=1), which removes the question of encoding overhead, so it's a bit easier to use this scheme in Octavia than in Tahoe. The big big win of this approach is the UI. The k-of-N encoding parameters don't matter quite so much when you can keep creating more shares until you're happy with their distribution, so there might be less need for users to choose k/N instead of sticking with the defaults. And the "red/yellow/green" status light is a dead-simple UI indicator, like the way Dropbox tells you when it's done moving data around. The next step is probably to do some zfec performance tests, to find out what setting N=25 (and then discarding the extra shares) would do to our upload speed.

warner added the

c/code-encoding

labels 2011-01-27 19:09:11 +00:00

warner added this to the undecided milestone 2011-01-27 19:09:11 +00:00

zooko commented

2011-01-27 19:57:53 +00:00

I like it! See related tickets #678 (converge same file, same K, different M) and #711 (repair to different levels of M).

I like it! See related tickets #678 (converge same file, same K, different M) and #711 (repair to different levels of M).

daira added

and removed

labels 2012-11-02 01:03:20 +00:00

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

2 participants

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#1340

No description provided.