[tahoe-dev] [tahoe-lafs] #670: large file download has bad alacrity

[tahoe-lafs]

#670: large file download has bad alacrity
---------------------------+------------------------------------------------
 Reporter:  zooko          |           Owner:       
     Type:  defect         |          Status:  new  
 Priority:  major          |       Milestone:  1.3.2
Component:  code-encoding  |         Version:  1.3.0
 Keywords:                 |   Launchpad_bug:       
---------------------------+------------------------------------------------

Comment(by warner):

 Zooko and I identified some super-linearities in
 {{{IncompleteHashTree.add_hashes}}}. I haven't yet characterized just how
 bad it is, but I think it's at least {{{O(N**2)}}}. Our current download
 code grabs the entire merkle tree (both the block tree and the ciphertext
 hash tree) and adds the whole thing at once, triggering this superlinear
 behavior.

  * first: change {{{IncompleteHashTree}}} to fix the superlinearity. Add a
 test case which adds a couple thousand hashes, something which takes about
 1.0s on my workstation (so it might take less than 60s on our slowest
 buildslave), but which would take a really really long time in the broken
 version. Some notes on the fix: instead of maintaining a sorted list of
 all pending hash nodes, break the list up into one set per level of the
 tree, and process everything on the lowest level (in arbitrary order)
 before proceding to the level above.

  * second: change download to retrieve the minimal Merkle chain. If we fix
 the first problem, we can probably put this off for a while.

 For reference. Foolscap (serialization+deserialization) takes 84us per
 hash, so 80k hashes would take about 6.7s .

-- 
Ticket URL: <http://allmydata.org/trac/tahoe/ticket/670#comment:1>
tahoe-lafs <http://allmydata.org>
secure decentralized file storage grid