improve random-access download to retrieve/decrypt less data #798
Labels
No Label
0.2.0
0.3.0
0.4.0
0.5.0
0.5.1
0.6.0
0.6.1
0.7.0
0.8.0
0.9.0
1.0.0
1.1.0
1.10.0
1.10.1
1.10.2
1.10a2
1.11.0
1.12.0
1.12.1
1.13.0
1.14.0
1.15.0
1.15.1
1.2.0
1.3.0
1.4.1
1.5.0
1.6.0
1.6.1
1.7.0
1.7.1
1.7β
1.8.0
1.8.1
1.8.2
1.8.3
1.8β
1.9.0
1.9.0-s3branch
1.9.0a1
1.9.0a2
1.9.0b1
1.9.1
1.9.2
1.9.2a1
LeastAuthority.com automation
blocker
cannot reproduce
cloud-branch
code
code-dirnodes
code-encoding
code-frontend
code-frontend-cli
code-frontend-ftp-sftp
code-frontend-magic-folder
code-frontend-web
code-mutable
code-network
code-nodeadmin
code-peerselection
code-storage
contrib
critical
defect
dev-infrastructure
documentation
duplicate
enhancement
fixed
invalid
major
minor
n/a
normal
operational
packaging
somebody else's problem
supercritical
task
trivial
unknown
was already fixed
website
wontfix
worksforme
No Milestone
No Assignees
3 Participants
Notifications
Due Date
No due date set.
Reference: tahoe-lafs/trac-2024-07-25#798
Loading…
Reference in New Issue
No description provided.
Delete Branch "%!s(<nil>)"
Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?
Currently, using a
Range:
header on an HTTP GET (to fetch just a portion of a file, instead of the whole thing) causes the tahoe client to download the entire file into a tmpfile, then serve out just the portion that was requested. To make this faster, we should only fetch the segments that contain the desired range. Two changes need to happen to make this work:The new Downloader should have a couple of layers:
read(offset, length)
request (maybe a even fully-generalreadv
)Similar code will be needed for MDMF mutable files, since those are specified to contain multiple segments, and we'll want random-access for them too.
Brian is writing the new Downloader.
Attachment new-downloader-v1.diff (124193 bytes) added
work-in-progress of new downloader, maybe 80% complete
As discussed in #990, a positive security side-effect of this rewrite will be to avoid caching plaintext in order to satisfy byterange requests.
Attachment new-downloader-v2.diff (130758 bytes) added
latest WIP patch
Attachment new-downloader-v3.diff (145044 bytes) added
latest WIP patch, a few tests pass
Attachment new-downloader-v4.diff (153208 bytes) added
one system test works
in the v4 patch,
SystemTest.test_filesystem
now passes. I had to disable the "download status" checking code.. that part isn't implemented yet.Next steps:
LiteralFileNode
into a new literal.py, let the top-level (non-literal)ImmutableFileNode
live in filenode.py, move most of the rest of download2.py (theShareFinder
andShare
classes) into download.pyImmutableFileNode
classAttachment new-downloader-v5.diff (158411 bytes) added
rest of SystemTest now passes
Attachment new-downloader-v6.diff (169397 bytes) added
v6 patch: most existing tests pass
In the v6 patch, most of the existing tests pass. Remaining old-test work to do:
And all the TODOs from above.
I've been thinking about the download-status data. What I'd like to record is a list of messages, one per share, with (send time, start+offset, response size, response time) for each one (plus information about the initial DYHB query). For now I'd just dump this information as text in the download-status page, but eventually I'd like a scrolling JS/Canvas-based diagram. It would have time along the X axis, and probably (server,share) along the Y axis. Each message send would be a horizontal line that spans from the send to the receipt, maybe with a thickness related to the number of bytes being requested. There will be lots of overlapping requests, so they must be handled cleanly.
There should be vertical lines to indicate when each completed segment is delivered to the caller (running from the top-most active share to the bottom of the chart, with an arrow pointing downwards). There should also be vertical lines to indicate when the caller requests the next segment: when callers are stalling (i.e. streaming music not buffering too much) it should be obvious by looking at the chart.
Another sort of chart that would be interesting would have byte-offset-in-share as the Y axis, showing how we fetch different pieces of the share at different times.
Replying to warner:
You might consider merging these two. When I wrote test_hung_download, I wasn't familiar enough with the existing tests to see that it was partially duplicating some of test_immutable.
If you like this ticket, you might also like the "Brian's New Downloader" bundle of tickets: #605 (two-hour delay to connect to a grid from Win32, if there are many storage servers unreachable), #800 (improve alacrity by downloading only the part of the Merkle Tree that you need), #809 (Measure how segment size affects upload/download speed.), #287 (download: tolerate lost or missing servers), and #448 (download: speak to as few servers as possible).
Brian's New Downloader is now planned for v1.8.0.
Attachment new-downloader-v7.diff (224567 bytes) added
12 uncovered lines left, some tests disabled
I did a lot of code-coverage work, so the v7 patch fixes a number of real bugs in the previous ones. There are still some significant functional things to fix, though, notably the state=OVERDUE heuristic is missing, and ShareFinder isn't sending requests in parallel. Both fronts will benefit from download-status displays. I found an interesting JS library which might be good for generating the display: http://www.simile-widgets.org/timeline/
Attachment new-downloader-v8.diff (288500 bytes) added
more integration, refactoring
The v8 patch has a lot of integration work: the new downloader now mostly
lives in immutable/downloader/ , all the filenodes live in
immutable/filenode.py (except for Literal, which was moved into
immutable/literal.py). Repairer was rewritten to use the new downloader (and
it's waaaay simpler now). Some of the old downloader code was removed (except
that Verifier still uses it). The download-status display is functional, but
shows mostly raw request-response timestamps (the SIMILE Timeline work is not
in this patch, and might not really want to be in the Tahoe node at all,
maybe it should go into a separate tool).
At this point, the new downloader is almost as good as the old downloader, so
I'm starting to think about landing it after 1.7 is released. It doesn't yet
handle servers hanging very well, but the old downloader didn't either. The
biggest problem is that the new downloader will basically pick share-holding
servers at random, rather than preferring the fastest responders. The old
downloader would, I think, stick with the first 'k' servers that responded
positively to the DYHB requests, so even though it couldn't tolerate the loss
of any server, it would use the fastest-responding ones. The new downloader
could easily pick the slowest responders by accident.
The biggest feature I want to write next is the hanging-server handling
(state=OVERDUE). I know that it will take some fiddling with the heuristics
before we find something that feels right. I'd prefer to have the timeline
visualization in place to support this work, but it's looking to be a decent
amount of work, so I may plunge ahead without it, or find some alternative
approach (GD or some python image-drawing library, probably without zooming).
To do state=OVERDUE right will also provoke structural changes to the way we
manage remote servers (specifically I want an object with a lifetime equal to
the TCP connection's, which remembers how long requests took in the past, so
it can help guess if an outstanding request is overdue or merely slow). I
might want to land this patch first, before starting on that work, since I'm
really far out on a branch right now. My patch is updated to current trunk,
but if anyone gets busy and makes some deep changes to the tree, I may have a
challenging merge job ahead. So merging sooner rather than later feels like a
good idea.
Attachment new-downloader-v9.diff (409611 bytes) added
more small improvements
Attachment new-downloader-v10.diff (388251 bytes) added
added OVERDUE for get_buckets calls, reenabled some "hung server" tests
Whoo! Ready for review! And user testing. Try it out!
I needed to fix a few minor issues when converting this to a darcs patch:
the patch to client.py touches a line next to another line changed in the ticket1074 branch (no real conflict)
'
patch
' failed to create the empty filesrc/allmydata/download/*init*.py
pyflakes warning:
src\allmydata\test\test_hung_server.py:12: '_corrupt_share_data' imported but unused
DEFAULT_MAX_SEGMENT_SIZE
missing frominterfaces.py
some uses of
find_shares
(two in test/no_network.py and one in test/test_download.py)needed to be changed to
find_uri_shares
.'
print r_ev
' statement in util/spans.py should be commented out.With these changes it doesn't fail any tests on my machine.
Attachment new-downloader-v10a.dpatch (274169 bytes) added
Brian's New Downloader, for testing in 1.8beta (or alpha)
Applied to trunk in changeset:cbcb728e7ea0031d changeset:88d7ec2d5451a00c changeset:22a07e9bbe682d6e changeset:797828f47fe1aa44 changeset:7b7b0c9709d8ade6 changeset:63b61ce7bd112af7 changeset:20847dd8768a1622 changeset:919938dd95ded529 (corresponding to 1.8.0beta), then changeset:abcd6e0e96298a76 changeset:2a05aa2d9142ceea changeset:fa34e4dd16813923 changeset:2bd87498498d7c44.
The bugs in ticket:1154 were fixed in changeset:8844655705e4fb76 changeset:43c5032105288a58 changeset:f6f9a97627d210a6, and changeset:a0124e95eee4c1fd reenabled some commented-out tests.
Accepting for review.
Reviewing changeset:cbcb728e7ea0031d:
the
(start, length)
form of theSimpleSpans
constructor is not used outside test code (and the test code can be changed to pass a[(start, length)]
array). Removing this would slightly simplify the constructor and avoid a possibly error-prone overloading.in the
Spans
class comment, ", frequently used to represent .newsrc contents" is out-of-context and not needed.in the
_check
method ofSpans
, if assertions are switched on then theself._spans
array is re-sorted in order to check whether it is ordered. This is unnecessary: if you add anassert length > 0, length
in the loop, then the loop will be checking a condition that is stronger than the array being ordered, given that the starts and lengths are numbers. (The sorting actually takes O(n) time rather than O(n log n) on each call to_check
, because Timsort will detect the ordered input, but it's still unnecessary overhead.)the assert statements should include the variables they use in the exception message, e.g.
assert start > prev_end, (start, prev_end)
."
overlap(s_start, s_length, start, length) or adjacent(s_start, s_length, start, length)
" is equivalent to "overlap(s_start, s_length, start-1, length+2)
".in the only other use of
adjacent
(inDataSpans.add
), only thestart0 < start1
case should be able to occur. Inline and simplify.in the loop over
enumerate(self._spans)
, you could exit early whens_start > start+length
. At that point you know where to insert the(start, length)
span without having to re-sort.a
Spans
object behaves somewhat like a set of the elements in all of its spans, but the*contains*
and*iter*
methods are not consistent with that (instead viewing it as a set of(start, length)
pairs). I realize this may allow for more convenient use ofin
and iteration, but it should at least be documented._check
andassert_invariants
do similar things; give them the same name.DataSpans._dump
is poorly named.DataSpans.assert_invariants
should check that none of the data strings are zero-length.is it intentional that
DataSpans.add
callsself.assert_invariants()
butremove
(andpop
, although that's much simpler) don't?if s_start <= start < s_end:
I find this Python construct too clever by half. Anyway, at this points_start <= start
is always true (otherwise we won't get past the firstcontinue
), so I would write this asPerhaps rename
s_*
toold_*
.DataSpans.add
: if I understand correctly, case A also covers:This isn't immediately clear from the comment. Depicting it as
might help. Also, use uppercase consistently for the cases.
suffix_len
in case D has a different meaning tosuffix_len
in case E. Maybe rename it toreplace_len
for case D.Tests:
The
Spans
class is tested byByteSpans
, but it just stores spans of integers, not necessarily byte offsets. I would suggests/ByteSpans/TestSpans/
ands/StringSpans/TestDataSpans/
.I could be wrong, but I don't think the deterministic tests are covering all cases in
add
andremove
. I'd prefer to see those tests have full coverage rather than relying on the randomized tests to make up the gap.good points! I think I'll implement most of them, but after the 1.8.0 release.
This patch broke some docs:
When downloading a file, the current version just asks all known servers for any shares they might have…
When asked to read an arbitrary range of an immutable file, Tahoe-LAFS will download from the beginning of the file up until it has enough of the file to satisfy the requested read…
I think these documentation issues should be fixed before we release Tahoe-LAFS v1.8.0 final.
Let's make a new ticket for the improvements suggested in comment:72911, so we can close this ticket as soon as the docs fixes in comment:72913 are resolved.
Attachment 798-docs.dpatch (4007 bytes) added
docs/performance.txt, architecture.txt: updates taking into account new downloader. refs #798
Replying to warner:
Okay I created #1196 (clean up and optimize spans).
In changeset:f32dddbcedea3c7c: