[GitHub] davisp opened a new pull request #512: Couchdb 3298 optimize writing btree nodes

[gi...@git.apache.org]

davisp opened a new pull request #512: Couchdb 3298 optimize writing btree nodes
URL: https://github.com/apache/couchdb/pull/512
 
 
   ## Overview
   
   As it turns out, the original change in COUCHDB-3298 ends up hurting
   disk usage when a view emits large amounts of data (i.e., more than
   half of the btree chunk size). The cause for this is that instead of
   writing single element nodes it would instead prefer to write kv nodes
   with three elements. While normally we might prefer this in memory, it
   turns out that our append only storage this causes a significantly more
   amount of trash on disk.
   
   We can show this with a few trivial examples. Imagine we write KV's a
   through f. The two following patterns show the nodes as we write each
   new kv.
   
       Before 3298:
   
       []
       [a]
       [a, b]
       [a, b]', [c]
       [a, b]', [c, d]
       [a, b]', [c, d]', [e]
       [a, b]', [c, d]', [e, f]
   
       After 3298:
   
       []
       [a]
       [a, b]
       [a, b, c]
       [a, b]', [c, d]
       [a, b]', [c, d, e]
       [a, b]', [c, d]', [e, f]
   
   The thing to realize here is which of these nodes end up as garbage. In
   the first example we end up with [a], [a, b], [c], [c, d], and [e] nodes
   that have been orphaned. Where as in the second case we end up with
   [a], [a, b], [a, b, c], [c, d], [c, d, e] as nodes that have been
   orphaned. A quick aside, the reason that [a, b] and [c, d] are orphaned
   is due to how a btree update works. For instance, when adding c, we read
   [a, b] into memory, append c, and then during our node write we call
   chunkify which gives us back [a, b], [c] which leads us to writing [a,
   b] a second time.
   
   The main benefit of this patch is to realize when its possible to reuse
   a node that already exists on disk. It achieves this by looking at the
   list of key/values when writing new nodes and comparing it to the old
   list of key/values for the node read from disk. By checking to see if
   the old list exists unchanged in the new list we can just reuse the old
   node. Node reuse is limited to when the old node is larger than 50% of
   the chunk threshold to maintain the B+Tree properties.
   
   The disk usage improvements this gives can also be quite dramatic. In
   the case above when we have ordered keys with large values (> 50% of the
   btree chunk size) we find upwards of 50% less disk usage. Random keys
   also benefit as well though to a lesser extent depending on disk size
   (as they will often be in the middle of an existing node which prevents
   our optimization).
   
   ## Testing recommendations
   
   $ make check
   
   Also, see @nickva's script for testing that he's written. I'll make him add details to this PR once its opened.
   
   ## JIRA issue number
   
   COUCHDB-3298
   
   ## Checklist
   
   - [ ] Code is written and works correctly;
   - [ ] Changes are covered by tests;
   - [ ] Documentation reflects the changes;
   
   Note for documentation, this isn't user visible behavior. Though we will want to call out that we'll use less disk space in our release notes.
 
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on GitHub and use the
URL above to go to the specific comment.
 
For queries about this service, please contact Infrastructure at:
users@infra.apache.org


With regards,
Apache Git Services