{"push_id":581185623,"size":224,"distinct_size":2,"ref":"refs/heads/master","head":"b0a3df40d6e4a4a50e5324954ce873b8219cc2e6","before":"c3e9cc5e64bcfd6e342a85932a90428cfdc1ee2d","commits":[{"sha":"4bd7cb9b095dea3960e2cfe243a69682149cbde1","author":{"email":"929efb6bf3ba6086ec34a13bc26d38fa97bea363@gmail.com","name":"evan"},"message":"add optional key transformer to support new key formats","distinct":false,"url":"https://api.github.com/repos/patternmatched/bitcask/commits/4bd7cb9b095dea3960e2cfe243a69682149cbde1"},{"sha":"f61d15cd551cd8b9d6ee133daf92d5067b94d660","author":{"email":"16a9a54ddf4259952e3c118c763138e83693d7fd@basho.com","name":"Joseph Blomstedt"},"message":"Tag meck in rebar.config","distinct":false,"url":"https://api.github.com/repos/patternmatched/bitcask/commits/f61d15cd551cd8b9d6ee133daf92d5067b94d660"},{"sha":"0b0788e367b4b6d0b19cd15e55b11e41e40526f4","author":{"email":"929efb6bf3ba6086ec34a13bc26d38fa97bea363@gmail.com","name":"evan"},"message":"Merge branch 'drop_warn' of https://github.com/lemenkov/bitcask into develop","distinct":false,"url":"https://api.github.com/repos/patternmatched/bitcask/commits/0b0788e367b4b6d0b19cd15e55b11e41e40526f4"},{"sha":"60b5d87ce4c9ba7759ac08cad76b3d7264604419","author":{"email":"929efb6bf3ba6086ec34a13bc26d38fa97bea363@gmail.com","name":"evan"},"message":"Merge branch 'pevm-use-system-malloc' into develop","distinct":false,"url":"https://api.github.com/repos/patternmatched/bitcask/commits/60b5d87ce4c9ba7759ac08cad76b3d7264604419"},{"sha":"dc3900467c326d7cac40cafdda9bf41f6c3f2db5","author":{"email":"929efb6bf3ba6086ec34a13bc26d38fa97bea363@gmail.com","name":"evan"},"message":"Improve bitcask iteration concurrency.\n======================================\n\nThe problem:\n------------\n\nBitcask was designed to have a single iteration in progress at any one\ntime (multiple concurrent iterations are allowed, but must explicitly\nask to use the old snapshot). Effectively this means that to have a\ntrustworthy snapshot, subsequent iterations must wait upon the first\nto complete, whereupon they're awoken and can attemt to iterate.\n\nThe fix:\n--------\n\nThe code change here makes a second form of bitcask keydir entry, the\nentry list.  Entry lists are a deduplicated version of entries.  The\nhead contains the key, the key length, and a pointer to a list of\nsiblings, which contain the keydir values that can vary from instance\nto instance of a key.\n\nWhen a put or delete happens while a fold is under way, the entry is\nconverted to an entry list with the original entry and the update.\nGets (including fold gets) now discriminate between versions via\ntimestamp.\n\nAn arguable implementation decision here was to implement entry lists\nas tagged pointers (LSB set to 1).  This does make reasoning about\ntypes more complicated, but in a space-constrained environment, the\nextra complexity is worth the space overhead incurred by a union type\nwith an internal tag.\n\n_A complication_\n\nKeydir entries are stored in an in-memory hashtable using the khash\nlibrary.  Unfortunately, khash isn't iteration-safe across resizes.\nThus, when we detect that a new put would cause a resize, we fall back\non the old path, where a pending keydir is instantiated and all new\nupdates are noted there until all running iterations complete and the\nkeydirs are folded back in.  While this still means that folds can\nblock for a potentially long time, since khash doubles the size of its\nstorage at each resize, that populated keydirs are much less likely to\nrun into blocking behavior.\n\nTesting:\n--------\n\nBitcask has a reasonable test suite.  It should be run repeatedly in\nboth IO modes.  Note that https://github.com/basho/bitcask/pull/93 is\nstill open and fails occasionally.  That code is not changed here, so\nshould not be counted.\n\nA long PULSE testing run should be done.  I've accumulated ~9 hours or\nso have been done so far, but ideally more should be done.\n\nSome riak tests that involve iteration and listing would be good to\nattempt.  Real-world fold-speed tests like handoff and AAE rebuilds\nwould also be interesting to see.\n\nThe problematic sitation that we're attempting to avoid here is\nsomething like this:\n - on a large keydir, a slow iteration, like a merge, is happening.\n - at the same time, AAE is waiting with a thrown-away tree\n - and someone is trying to do a MR job that requires a keyfold\n   iteration\n\nYou should be able to run riak without this changeand see increased\nlatencies on fold-dependent operations during merges and AAE tree\nrebuilds.  With this change there should be fewer and shorter latency\nspikes while these things are going on.\n\nAlternate approaches:\n---------------------\n\n_Switch to a hash structure with snapshots_\n\nThis likely is a good idea, rather than the current hybrid approach\nbut the existing options are honestly somewhat uninspiring.  Because\nof time limitations, it was decided that there simply wasn't enough\ntime to do this.\n\n_layers of pending keydirs_\n\nWhile this is intuitively appealing, there are two major problems with\nthis approach.  The first is the change of get behavior from O(1) to\nO(N), which could be problematic if N is large.  The second is more\nserious, which is that it's impossible to establish a consistent\nmulti-level iteration snapshot without a lot of memory or time\noverhead.\n\nEg. with levels 1, 2, and 3, and values A, B, and C\n\n```\n1 A:3  B:4\n2      B:del C:7\n3 A:1  B:5   C:nf\n```\n\nYou need to either make a new keydir and merge all the pending keydirs\ninto that temporary keydir for the snapshot, or keep track of seen\nkeys, which is essentially the same approach.  Some thinking about the\nissue suggests that instead of N keydirs, you'd really need N**2\nkeydirs.\n\nOpen work:\n----------\n\n_rw locks_\n\nThis approach requires taking a lock per step of the iterator.  It's\npossible that this could slow down folds considerably due to lock\ncontention.  It may be better to move from the `enif_mutex` to a\n`posix_rw_lock`.  This isn't a trivial change, I don't think, so\ncareful measurement should be done to see if it's a problem before we\ndo the work.\n\nThis change has broader appeal, as it could potentially make concurrent\nreaders (once we've added multiple readers per vnode) faster.\n\n_gc thread_\n\nAt the moment, we only clean up entry-lists when the value is updated,\nso if you had a large run of writes during a fold that were then never\nupdated, the overhead there might never be reclaimed.  It may be worth it\nto add a thread that slowly iterates over the keydir when there are no\nactive folders and cleans up existing entry lists.\n\nFiles changed, w/ brief summary of changes:\n-------------------------------------------\n\n- `c_src/bitcask_nifs.c`\n  the bulk of the changes described above are here\n\n- `src/bitcask.erl`\n  remove keydir git before put\n  instrument folds with time for snapshots\n  update tests, add new tests\n\n- `src/bitcask_nifs.erl`\n  add keydir_get/3, timestamp specific get\n  make itr timestamps consitent with the other bitcask timestamps\n  update tests to work with new behavior\n\n- `c_src/kash.h`\n  add will_resize check\n\n- `src/bitcask_fileops.erl`\n  merges expect hintfiles to always be created, but multiple\n  concurrent folds seem to violate this invariant. sleep for a short\n  time and then abort the merge if the hintfile doesn't get created.\n\n- `test/bitcask_qc.erl`\n  changes to how deletion is accounted for, as the keydir put\n  before delete has been removed to reduce the number of entry\n  list members","distinct":false,"url":"https://api.github.com/repos/patternmatched/bitcask/commits/dc3900467c326d7cac40cafdda9bf41f6c3f2db5"},{"sha":"d5e330cf2ae2bf4e0dbd63a310c6d3f5c8ecbf33","author":{"email":"7a4255afd9c57b6683c0a61b60767f34686dfd0a@ieee.org","name":"Steve Vinoski"},"message":"update meck dependency to basho fork, version 0.8.1","distinct":false,"url":"https://api.github.com/repos/patternmatched/bitcask/commits/d5e330cf2ae2bf4e0dbd63a310c6d3f5c8ecbf33"},{"sha":"bf384b5e98e3d4bd888d5f6ae331d7fb3d30f0c5","author":{"email":"929efb6bf3ba6086ec34a13bc26d38fa97bea363@gmail.com","name":"evan"},"message":"address numerous review comments","distinct":false,"url":"https://api.github.com/repos/patternmatched/bitcask/commits/bf384b5e98e3d4bd888d5f6ae331d7fb3d30f0c5"},{"sha":"c2533a656c7c3454d1c4109aa8fd90a4178e0cac","author":{"email":"929efb6bf3ba6086ec34a13bc26d38fa97bea363@gmail.com","name":"evan"},"message":"- add safety parens to the MAX macros\n- add frees to close memory leaks revealed by valgrind\n  one of which fixes a small leak in master\n- change key count and bytes count to 64bit (previously\n  size_t, then uint32_t)","distinct":false,"url":"https://api.github.com/repos/patternmatched/bitcask/commits/c2533a656c7c3454d1c4109aa8fd90a4178e0cac"},{"sha":"aeb8ae4625e0309161f6879a9cc37b1051afaf59","author":{"email":"99489221180cc5006eb079d087171523439956db@basho.com","name":"Engel A. Sanchez"},"message":"Refactor of Evan's multifold\n\nThis is an attempt to clean up the multifold logic to make it more\nmaintanable.\n\n- New find_result struct holds the results of a find operation. This\n  simplifies the logic of most operations that use a find and later have\n  to figure out exactly where things were found, whether they were a\n  tombstone, etc.\n- Removes the need to malloc temporary entries while manipulating the\n  keydir. For this, a new proxy struct was created to hold the values\n  of a regular or list entry when it's found.\n- Removes the need to malloc temporary entries when looking up stuff\n  from the keydir. A new khash operation was added to allow custom hash\n  and equal functions to be used, so you can look up from something\n  other than a variable length entry.\n- Adds locking to iteration now that it can happen while puts are\n  updating the entries hash. Found during review of original PR","distinct":false,"url":"https://api.github.com/repos/patternmatched/bitcask/commits/aeb8ae4625e0309161f6879a9cc37b1051afaf59"},{"sha":"eed9ad2069cc41d28c326d897cb8affad8a0da7b","author":{"email":"99489221180cc5006eb079d087171523439956db@basho.com","name":"Engel A. Sanchez"},"message":"Fix warnings in debug printing code\n\nAlso, this will only compile now if BITCASK_DEBUG is set.","distinct":false,"url":"https://api.github.com/repos/patternmatched/bitcask/commits/eed9ad2069cc41d28c326d897cb8affad8a0da7b"},{"sha":"8b6adfb294fa2fb99a1570eb1ba2d7765c8ae27b","author":{"email":"99489221180cc5006eb079d087171523439956db@basho.com","name":"Engel A. Sanchez"},"message":"Fix uninitialized variable\n\nFound by Andrew running Valgrind.","distinct":false,"url":"https://api.github.com/repos/patternmatched/bitcask/commits/8b6adfb294fa2fb99a1570eb1ba2d7765c8ae27b"},{"sha":"0d3aeea04e400cce84b047d3c56ec9c3deabf9dc","author":{"email":"99489221180cc5006eb079d087171523439956db@basho.com","name":"Engel A. Sanchez"},"message":"Cleaning up and updating comments","distinct":false,"url":"https://api.github.com/repos/patternmatched/bitcask/commits/0d3aeea04e400cce84b047d3c56ec9c3deabf9dc"},{"sha":"d49759dc88bc56b7638b7767b09cb42db3f207a9","author":{"email":"929efb6bf3ba6086ec34a13bc26d38fa97bea363@gmail.com","name":"evan"},"message":"remove pdict usage","distinct":false,"url":"https://api.github.com/repos/patternmatched/bitcask/commits/d49759dc88bc56b7638b7767b09cb42db3f207a9"},{"sha":"b95bb9aafdc2fa2d1b09ea9f8cc594b07350131c","author":{"email":"929efb6bf3ba6086ec34a13bc26d38fa97bea363@gmail.com","name":"Evan Vigil-McClanahan"},"message":"Merge pull request #103 from basho/pevm-keydir-overhead\n\nadd optional key transformer to support new key formats","distinct":false,"url":"https://api.github.com/repos/patternmatched/bitcask/commits/b95bb9aafdc2fa2d1b09ea9f8cc594b07350131c"},{"sha":"44b9a1b307ae92e503d1aee7dfb3962961e430be","author":{"email":"99489221180cc5006eb079d087171523439956db@basho.com","name":"Engel A. Sanchez"},"message":"Fix fold start time\n\nThe fold code was creating a timestamp *before* the keydir was frozen\nand using that to look at a snapshot of the data. This was hidden by the\nfact that the snapshot code would give in and give you a closest match\nif no entry found for the given timestamp, even if this violated the\nsnapshot logic. When I cleaned up that logic, this surfaced.\n\nAlso, fixing get to return not found in the case an entry for the given\nsnapshot time was not found.","distinct":false,"url":"https://api.github.com/repos/patternmatched/bitcask/commits/44b9a1b307ae92e503d1aee7dfb3962961e430be"},{"sha":"59a2ca9dd8fbec1bb66ba5169cff5c6f9d719414","author":{"email":"929efb6bf3ba6086ec34a13bc26d38fa97bea363@gmail.com","name":"Evan Vigil-McClanahan"},"message":"Merge pull request #106 from basho/eas-multifold-refactor\n\nRefactor of Evan's multifold","distinct":false,"url":"https://api.github.com/repos/patternmatched/bitcask/commits/59a2ca9dd8fbec1bb66ba5169cff5c6f9d719414"},{"sha":"8c3484adc61be30cb860c080d0f2a61aeb066c99","author":{"email":"929efb6bf3ba6086ec34a13bc26d38fa97bea363@gmail.com","name":"evan"},"message":"Merge branch 'develop' into pevm-hybrid-multifold\n\nConflicts:\n\tsrc/bitcask.erl","distinct":false,"url":"https://api.github.com/repos/patternmatched/bitcask/commits/8c3484adc61be30cb860c080d0f2a61aeb066c99"},{"sha":"e8d05019c56bc28533c317e6695744bac651bd51","author":{"email":"929efb6bf3ba6086ec34a13bc26d38fa97bea363@gmail.com","name":"Evan Vigil-McClanahan"},"message":"Merge pull request #104 from basho/pevm-hybrid-multifold\n\nImprove bitcask iteration concurrency.","distinct":false,"url":"https://api.github.com/repos/patternmatched/bitcask/commits/e8d05019c56bc28533c317e6695744bac651bd51"},{"sha":"10dff41456a81b2c470d6cd495281fc88350753f","author":{"email":"929efb6bf3ba6086ec34a13bc26d38fa97bea363@gmail.com","name":"evan"},"message":"remove unused header","distinct":false,"url":"https://api.github.com/repos/patternmatched/bitcask/commits/10dff41456a81b2c470d6cd495281fc88350753f"},{"sha":"963ddcbaffde512d56c2be94af0ddcfbf7467089","author":{"email":"929efb6bf3ba6086ec34a13bc26d38fa97bea363@gmail.com","name":"Evan Vigil-McClanahan"},"message":"Merge pull request #110 from basho/pevm-remove-stdbool\n\nremove unused header","distinct":false,"url":"https://api.github.com/repos/patternmatched/bitcask/commits/963ddcbaffde512d56c2be94af0ddcfbf7467089"}]}