#800 closed enhancement (fixed)

improve alacrity by downloading only the part of the Merkle Tree that you need

Reported by: zooko Owned by: warner
Priority: major Milestone: 1.8.0
Component: code Version: 1.5.0
Keywords: easy performance download Cc: kevan@…
Launchpad Bug:

Description

The downloader currently reads the entire Merkle Tree over the blocks when it needs to read only a log-N-sized subset of it. Here is the function ReadBucketProxy._get_block_hashes() which is informed by its caller about which hashes are needed, but which then dumbly goes ahead and downloads the entire set: src/allmydata/immutable/layout.py@4048#L415. Here is the caller which figures out exactly which subset of the Merkle Tree that it needs, asks the ReadBucketProxy for it, then stores all the ones it got that it didn't need: src/allmydata/immutable/download.py@4054#L334. (Good thing it stores them, because it usually does need them later, when it proceeds to download the rest of the file.)

This issue was mentioned in this mailing list thread:

http://allmydata.org/pipermail/tahoe-dev/2009-September/002779.html

Ticket #670 mentioned this issue.

Change History (11)

comment:1 Changed at 2009-09-04T02:47:16Z by zooko

  • Keywords easy added

I'm marking this as "easy". :-)

comment:2 Changed at 2009-09-19T10:41:43Z by kevan

  • Cc kevan@… added

In playing around with this, I noticed that if I change the logic in http://allmydata.org/trac/tahoe/browser/src/allmydata/immutable/layout.py?rev=4a4a4f95202ec976#L415 to download only the requested hashes, a number of unit tests that enforce upper limits on the number of reads start to fail. This makes sense -- instead of downloading the entire hash tree at once with one read operation when we need any part of it, we download (with my modifications) each chunk of the hash tree in a separate read operation, so there will of course be more reads.

I probably need to look more deeply into how block hashes are used before coming up with an opinion on this; so I guess this is an FYI note for the moment.

comment:3 Changed at 2009-10-27T04:34:17Z by zooko

I think it is okay for it to use more reads, so the test should be loosened to allow it to pass even if it does. The existence of that test of the number of reads does serve to remind me, however, that multiple small reads of the of the hash tree *would* actually be a performance loss for small files. We should do some more measurements of performance. Perhaps it would be a win to heuristically over-read by fetching a few more than the required number of hashes would be a a win.

comment:4 Changed at 2009-12-04T05:02:09Z by zooko

#442 was a duplicate of this.

comment:5 Changed at 2009-12-12T20:45:29Z by davidsarah

  • Keywords performance added

comment:6 Changed at 2009-12-12T20:46:57Z by davidsarah

  • Keywords download added

comment:7 Changed at 2010-02-10T04:20:45Z by zooko

  • Owner changed from somebody to warner

This may fit into Brian's New Downloader so I'm assigning this ticket to him to get his attention. If it is much later than February 9, and Brian hasn't clicked "accept" on this ticket, then you can safely assume he isn't currently working on it and you can click "accept" on it yourself to indicate that you are working on it.

comment:8 Changed at 2010-02-27T06:41:55Z by zooko

  • Milestone changed from undecided to 1.7.0

comment:9 Changed at 2010-05-08T19:47:36Z by zooko

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), #798 (improve random-access download to retrieve/decrypt less data), #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).

comment:10 Changed at 2010-05-08T22:46:40Z by zooko

  • Milestone changed from 1.7.0 to 1.8.0

Brian's New Downloader is now planned for v1.8.0.

comment:11 Changed at 2010-08-14T18:18:51Z by warner

  • Resolution set to fixed
  • Status changed from new to closed

#798 (which has landed) includes this feature. Specifically, source:src/allmydata/immutable/downloader/share.py@4688#L681 (Share._desire_block_hashes) asks the partially-filled hashtree which nodes it needs, and only sends read requests for those.

The small reads are only coalesced if they are adjacent: except for the first few kB of the share, the downloader does not read extra not-always-needed data for the purpose of reducing the number of remote read() messages. That might be a nice feature to have post-1.8.0; we need to measure the performance tradeoffs: each read() message probably carries about 30-40 bytes of overhead, so I'd expect that coalescing gaps of more than that to be a net loss. Adding a multi-segment readv() message to the remote-read protocol might help, but is more disruptive.

So I'm closing this ticket.

Note: See TracTickets for help on using tickets.