basho/bitcask — pull request #148 by engelsanchez (2014-03-14 00:30:02+00:00)
Title: Fix race with concurrent merges and deletes

This fix is a remake of Scott Fritchie's slf-tombstone-managementbranch
in basho/bitcask#128. It builds on heavy cleanup of the get functions that created a
lot of edges cases the branch worked around, as well as the introduction
of epochs by Evan that fixed problems with folds not viewing a stable
snapshot after the multifold support was added, as there were edge cases
around the use of timestamps. The retry code in delete was refactored
into the put method, and the tombstone2 was removed as it could not
solve the merge/delete race by itself while creating incompatible data
files.

* A delete in the writer process may race with a merge writing a value
for the same key on a file with id greater than the current write file.
Re-opening the cask would end up loading the merged value and forgetting
the delete. The delete path will now detect the race and retry the
tombstone write on a file with id greater than the merge file until it
prevails.
* A partial merge could end up removing the tombstone for a key that
still has a value in one of the unmerged files. tombstones just can not
be dropped during a partial merge without knowing that all previous
versions have disappeared too, so we avoid it. This may create more
garbage on disk than previous versions, but it's safer. We should have a
way to force a full merge.
kind of tombstone that contains a pointer to the value it is replacing
has been added.
* Change order of scan & fold: now oldest -> youngest.
* Add un-write last used when writing to a file and then finding a
conflict when updating the keydir. The write is tried at a higher file
and the old write is undone. Used in the merge/delete race fix.
* Avoid getting time in C land, passing it from Erlang instead. Now time
in tests can be completely faked.
* Adjust command frequency weightings for PULSE model to find problems
like this merge/delete race.
* Avoid storing tombstones in the keydir when possible. For this,
hintfile records store a flag in the offset field to indicate value is
a tombstone.
* For testing purposes, fold() and fold_keys() are extended with
another argument to expose the presence of keydir tombstones.
* And add option to make those compiler errors