tahoe-lafs/trac

new-downloader requests too much data, builds up #1181

New issue

Open

opened 2010-08-18 23:52:09 +00:00 by warner · 3 comments

warner commented

2010-08-18 23:52:09 +00:00

In #1170 comment:43 I describe a problem that
I noticed in the way the new downloader code handles data for long
reads (hundreds of segments). It looks like we ask for data which we
don't end up using. The .received DataSpans structure on
one of the later-to-arrive shares grew by about 350 ranges (and 35kB)
over the course of 762 segments. The one increment I looked at was by
64 bytes.

I have two guesses, the second more likely than the first:

our use of IncompleteHashTree.needed_hashes() with the
include_leaf=True argument is telling us that we should ask
for e.g. the hash of block0, so we ask for that part of the hash
tree. But then we retrieve block0 itself, and can hash it ourselves
and add it to the hash tree, meaning we never use the H(block0)
data from self._received. This would result in a 32-byte hash
value being added (and never removed) from Self._received
once every other segment.
The ciphertext hash tree nodes are requested from all shares,
because we never know which one will arrive first (and which ones
won't arrive at all). But we only consume the data for these hash
nodes out of the first share that provides them: we leave the
others alone. This will result in a variable amount of data being
left over in each share: larger amounts when the ciphertext hash
tree path down to the current segnum leaf flips over higher
branches (half of the time you'll only get one extra node, a
quarter of the time you'll get two extra nodes, etc, maximizing on
the first and numsegs/2 segments in which you have to get a full
ln2(numsegs) nodes).

I'm not so sure it's the first, since I ran the unit tests with those
include_leaf= arguments set to False, and they failed.

But the ciphertext hash tree feels pretty likely.

The simple fix is to just discard the whole self._received
structure after each segment is complete: in the ideal case (correctly
guessed segsize), it should be empty at that point anyways, and even
if the segsize guess was wrong, the bandwidth hit for flushing the
data is probably not more than a single block (and the round-trips hit
is probably zero). Here's a patch to implement the simple fix:

diff --git a/src/allmydata/immutable/downloader/share.py b/src/allmydata/immutable/downloader/share.py
index f7ed4e8..413f907 100644
--- a/src/allmydata/immutable/downloader/share.py
+++ b/src/allmydata/immutable/downloader/share.py
@@ -531,6 +531,9 @@ class Share:
             for o in observers:
                 # goes to SegmentFetcher._block_request_activity
                 o.notify(state=COMPLETE, block=block)
+            # now clear our received data, to dodge the #1170 spans.py
+            # complexity bug
+            self._received = DataSpans()
         except (BadHashError, NotEnoughHashesError), e:
             # rats, we have a corrupt block. Notify our clients that they
             # need to look elsewhere, and advise the server. Unlike

The complex fix is to consult the ciphertext hash tree when these node
hashes arrive, and either add them to the hash tree or discard them
(instead of the current practice of always storing them and then only
remove them if the hash tree still needs them). It might be easier to
do this if DataSpans had a feature to label each byte (in some
efficient way), so you could ask it for the ranges labelled
"ciphertext hash tree nodes", and discard just those. (this might also
help with pipelining segments, so you merge requests but still get the
large blocks of data back in the right order, to minimize your
buffering needs).

In [#1170 comment:43](/tahoe-lafs/trac/issues/1170#issuecomment-380555) I describe a problem that I noticed in the way the new downloader code handles data for long reads (hundreds of segments). It looks like we ask for data which we don't end up using. The `.received` `DataSpans` structure on one of the later-to-arrive shares grew by about 350 ranges (and 35kB) over the course of 762 segments. The one increment I looked at was by 64 bytes. I have two guesses, the second more likely than the first: * our use of `IncompleteHashTree.needed_hashes()` with the `include_leaf=True` argument is telling us that we should ask for e.g. the hash of block0, so we ask for that part of the hash tree. But then we retrieve block0 itself, and can hash it ourselves and add it to the hash tree, meaning we never use the H(block0) data from `self._received`. This would result in a 32-byte hash value being added (and never removed) from `Self._received` once every other segment. * The ciphertext hash tree nodes are requested from all shares, because we never know which one will arrive first (and which ones won't arrive at all). But we only consume the data for these hash nodes out of the first share that provides them: we leave the others alone. This will result in a variable amount of data being left over in each share: larger amounts when the ciphertext hash tree path down to the current segnum leaf flips over higher branches (half of the time you'll only get one extra node, a quarter of the time you'll get two extra nodes, etc, maximizing on the first and numsegs/2 segments in which you have to get a full ln2(numsegs) nodes). I'm not so sure it's the first, since I ran the unit tests with those `include_leaf=` arguments set to `False`, and they failed. But the ciphertext hash tree feels pretty likely. The simple fix is to just discard the whole `self._received` structure after each segment is complete: in the ideal case (correctly guessed segsize), it should be empty at that point anyways, and even if the segsize guess was wrong, the bandwidth hit for flushing the data is probably not more than a single block (and the round-trips hit is probably zero). Here's a patch to implement the simple fix: ``` diff --git a/src/allmydata/immutable/downloader/share.py b/src/allmydata/immutable/downloader/share.py index f7ed4e8..413f907 100644 --- a/src/allmydata/immutable/downloader/share.py +++ b/src/allmydata/immutable/downloader/share.py @@ -531,6 +531,9 @@ class Share: for o in observers: # goes to SegmentFetcher._block_request_activity o.notify(state=COMPLETE, block=block) + # now clear our received data, to dodge the #1170 spans.py + # complexity bug + self._received = DataSpans() except (BadHashError, NotEnoughHashesError), e: # rats, we have a corrupt block. Notify our clients that they # need to look elsewhere, and advise the server. Unlike ``` The complex fix is to consult the ciphertext hash tree when these node hashes arrive, and either add them to the hash tree or discard them (instead of the current practice of always storing them and then only remove them if the hash tree still needs them). It might be easier to do this if `DataSpans` had a feature to label each byte (in some efficient way), so you could ask it for the ranges labelled "ciphertext hash tree nodes", and discard just those. (this might also help with pipelining segments, so you merge requests but still get the large blocks of data back in the right order, to minimize your buffering needs).

warner added the

labels 2010-08-18 23:52:09 +00:00

warner added this to the soon milestone 2010-08-18 23:52:09 +00:00

warner commented

2010-08-19 00:21:36 +00:00

Author

Incidentally, that patch causes a few unit tests to fail, but it's only the two in test_immutable that assert a specific number of read() calls. They can safely be modified to raise the call limit.

Incidentally, that patch causes a few unit tests to fail, but it's only the two in `test_immutable` that assert a specific number of read() calls. They can safely be modified to raise the call limit.

warner commented

2010-08-19 00:57:38 +00:00

Author

Attachment 1181-patch.diff (2172 bytes) added

patch which also fixes unit test failures

**Attachment** 1181-patch.diff (2172 bytes) added patch which also fixes unit test failures

1181-patch.diff

2.1 KiB

zooko commented

2010-09-06 06:33:54 +00:00

We've applied attachment:1181-patch.diff as changeset:c89a464510394089 but I guess that's not the real solution, so I'm leaving this ticket open.

We've applied [attachment:1181-patch.diff](/tahoe-lafs/trac/attachments/000078ac-3c48-40cf-1e3a-309ab4928d74) as changeset:c89a464510394089 but I guess that's not the *real* solution, so I'm leaving this ticket open.

zooko modified the milestone from soon to 1.9.0

2010-09-10 21:28:41 +00:00

daira modified the milestone from 1.9.0 to soon

2011-08-15 04:16:29 +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#1181

No description provided.