Allow partial merge tombstone deletions

Until now, Bitcask tombstones were not safe to drop during a merge
because old values for the same key located in files not included in the
merge could make the value resurrect if Bitcask was closed and
re-opened. Resurrections have been a problem with Bitcask from the
beginning.

This introduces a new tombstone that includes the id of the file
containing the data it is deleting. Each tombstoned is paired up with
a file, so during a merge that sees both the original file and the
tombstone pointing it, the tombstone can be safely dropped without
risking resurrection of the data. Merges that see a tombstone but do not
include the original file now append that tombstone to that file, so
that it can be dropped by the next merge that includes that file. For
this to work with keys containing values in multiple files, a tombstone
has to be created every time a value is written for that key in a file
other than the file where the previous version was written.  That way
tombstones remain paired up with each file containing values.

Re-opening a file for append has some unfortunate side effects.
Hintfiles have a last record containing the CRC for its data. To append
more data, we need to remove that record and add it again when the merge
is finished. If a merge crashes without finishing, the re-opened files
will be missing the last record with the CRC, similar to a crash of the
writer process.  If Bitcask is configured to not open files without a
CRC, those files would not be available.

When merging old tombstones without file info, transform them into a
tombstone that contains the id of the containing file such that a later
merge can drop it eventually when all files < id have been merged.
Thought leadership on this brought to you by @jonmeredith

Other related fixes:

Added NIF to update stats properly when writing tombstones

Detect when merge includes a range of files starting with the oldest.
It is always safe to drop tombstones in that case. We take advantage
of this to make it possible to remove legacy tombstones.

When merging a consecutive set of files starting from the first file in
the bitcask directory, it is safe to drop all encountered tombstones.
We now detect this kind of "prefix" merge. Notice a merge containing a
"prefix" of the files plus some other later file should be able to drop
tombstones from files in the prefix, but we don't detect that. That is,
if we had files 2, 3, 4, 5, 6 and merged 2, 3 and 6 we could safely drop
tombstones found in files 2 and 3.

Allow merge input files to be specified by creating a merge.txt file in
the cask directory. bitcask:needs_merge() picks the contents of this
file to merge and will delete merge.txt when all files in it have been
deleted or marked for deletion. Leaving empty lines will delimit
batches, such that needs_merge returns one batch of files at a time.
This would prevent long merges including every single data file.

A cap on merge input size can now be passed to needs_merge, so that it
produces merges in batches. This can help with merging large amounts of
files.

Bumped version to 1.7.0. This will be used in the KV side to prepare a
data migration that schedules a merge of all files.
Add option to PULSE test to create merge.txt file on bc_open()

Fix PULSE counterexample by filtering error messages.

    C1 = [[{set,{var,6},
           {call,bitcask_pulse,fork,
                 [[{init,{state,undefined,false,false,[]}},
                   {set,{not_var,7},
                        {not_call,bitcask_pulse,bc_open,
                                  [false,{true,{231,280,114},1}]}},
                   {set,{not_var,10},
                        {not_call,bitcask_pulse,bc_close,[{not_var,7}]}},
                   {set,{not_var,11},
                        {not_call,bitcask_pulse,bc_open,
                                  [false,{true,{170,447,173},1}]}},
                   {set,{not_var,13},
                        {not_call,bitcask_pulse,bc_close,[{not_var,11}]}},
                   {set,{not_var,15},
                        {not_call,bitcask_pulse,bc_open,
                                  [false,{true,{258,18,280},1}]}}]]}},
      {set,{var,7},
           {call,bitcask_pulse,fork,
                 [[{init,{state,undefined,false,false,[]}},
                   {set,{not_var,2},
                        {not_call,bitcask_pulse,bc_open,
                                  [false,{true,{246,472,469},1}]}},
                   {set,{not_var,3},
                        {not_call,bitcask_pulse,bc_close,[{not_var,2}]}},
                   {set,{not_var,6},
                        {not_call,bitcask_pulse,bc_open,
                                  [false,{true,{73,166,183},1}]}},
                   {set,{not_var,7},
                        {not_call,bitcask_pulse,fold,[{not_var,6}]}}]]}},
      {set,{var,8},
           {call,bitcask_pulse,bc_open,[true,{true,{424,237,233},1}]}},
      {set,{var,10},{call,bitcask_pulse,needs_merge,[{var,8}]}},
      {set,{var,11},{call,bitcask_pulse,merge,[{var,8}]}},
      {set,{var,12},{call,bitcask_pulse,delete,[{var,8},1]}},
      {set,{var,13},{call,bitcask_pulse,merge,[{var,8}]}}],
     {62806,53384,84006},
     [{errors,[]}]].
    eqc:check(bitcask_pulse:prop_pulse(), C1).

The error coming from error_logger & failing the property:

    errors: failed
    [{<0.23310.2>,"Invalid merge input file ~s, deleting : ~p",
      ["1399-272921-941361/merge.txt",enoent]}] /= []

This error message is not fatal, so ignore it.

Fix PULSE counterexample when merge's ReadableFiles is the empty list

    C2 = [[{set,{var,2},
           {call,bitcask_pulse,bc_open,[true,{true,{442,453,173},1}]}},
      {set,{var,3},{call,bitcask_pulse,delete,[{var,2},1]}},
      {set,{var,5},{call,bitcask_pulse,bc_close,[{var,2}]}},
      {set,{var,8},
           {call,bitcask_pulse,bc_open,
                 [true,{true,{172,181,201},100}]}},
      {set,{var,9},{call,bitcask_pulse,fork_merge,[{var,8}]}},
      {set,{var,11},{call,bitcask_pulse,fork_merge,[{var,8}]}}],
     {41544,86022,14862},
     [{errors,[]}]].
    eqc:check(bitcask_pulse:prop_pulse(), C2).

The error from PULSE:

    errors: failed
    [{<0.27136.3>,"Failed to merge ~p: ~p\n",
      [{["1399-274027-165496/1.bitcask.data"],[]},
       {function_clause,
           [{lists,min,[[]],[{file,"lists.erl"},{line,300}]},
            {bitcask,merge1,4,[{file,"src/bitcask.erl"},{line,611}]},
            {bitcask_merge_worker,do_merge,1,
                [{file,"src/bitcask_merge_worker.erl"},{line,195}]}]}]}] /= []

Fix for Buildbot EUnit test failure

Buildbot isn't quite right in the head: I've no idea why I can
run this test 3000x without failure, but Buildbot fails

    bitcask_qc: merge2_test...
    =ERROR REPORT==== 5-May-2014::04:56:18 ===
    ** Generic server <0.2324.0> terminating
    ** Last message in was {'DOWN',#Ref<0.0.0.50927>,process,<0.2317.0>,normal}
    ** When Server state == {state,undefined,undefined}
    ** Reason for termination ==
    ** {{badmatch,{error,badarg}},
        [{bitcask_file,handle_info,2,[{file,"src/bitcask_file.erl"},{line,193}]},
         {gen_server,handle_msg,5,[{file,"gen_server.erl"},{line,604}]},
         {proc_lib,init_p_do_apply,3,[{file,"proc_lib.erl"},{line,239}]}]}

Fix: Really, we're stopping, so change the pattern match to '_' so we
don't care.

Fix Dialyzer type typo

Fix Buildbot timeout error

      bitcask: merge_batch_test...*timed out*

Increase timeout to something even a Buildbot can love.
Merge branch 'develop' into feature/partial-merge-tombstone-removal

Conflicts:
	src/bitcask.erl
	src/bitcask_fileops.erl
Fix merge induced failure

check_write changed to take a size, not a binary.
Fix bitcask_qc:prop_merge() test intermittent failures: use unique dir each time
Fixing test failure due to bad merge

bitcask_qc_fsm was failing due to a variable ending up re-assigned when
merging latest develop.
Move from pending delete from setuidbit 8#4000 -> 8#0001
Failing test case for PR 156's 'Cd5' PULSE failing case
Run 'make test' flavors 2x, not 3x
Fix the Cd5 PULSE failing test case

The Cd5 PULSE counterexample can be found at:
https://github.com/basho/bitcask/pull/156#issuecomment-43968268

The bug: when a tombstone T is encountered during a merge, and if
the tombstone is out of date, T was ignored/skipped.  This caused
a incorrect resurrection of T's key later in the test case.

The fix: when a tombstone T is encountered during a merge, and if
T is out of date, perhaps merge it forward anyway.  The code for
merging a tombstone forward was moved into its own function for
reuse, merge_single_tombstone().  That code remains the same as
it was before this commit, except for indenting and comment
formatting.
Remove check_no_tombstones() sanity check in bitcask_pulse.erl (see code comments)
PULSE test: restrict shrinking a bit, add extra fudge time
PULSE test: add missing precondition for 'get' op
Fix race condition in write_and_keydir_put()

Yet another unconditional keydir update that returns to bite later.
In a race with merge, if merge makes a keydir update between the
keydir read of do_put() and the keydir update of
write_and_keydir_put(), we must tell the keydir update that this
update needs the OldFileId prerequisite check.

* Add args to write_and_keydir_put() to pass in prerequisite info
* Use bitcask_nifs:keydir_put/10.
* Export bitcask_nifs:keydir_put/10.

Passes this previously-failing case, with 5,000 iterations:

    Cqq3 = [[{set,{var,3},{call,bitcask_pulse,fork,[[{init,{state,undefined,false,false,[]}},{set,{not_var,1},{not_call,bitcask_pulse,incr_clock,[]}},{set,{not_var,2},{not_call,bitcask_pulse,incr_clock,[]}},{set,{not_var,3},{not_call,bitcask_pulse,incr_clock,[]}},{set,{not_var,4},{not_call,bitcask_pulse,bc_open,[false,{true,{76,128,158},62}]}},{set,{not_var,5},{not_call,bitcask_pulse,fold,[{not_var,4}]}},{set,{not_var,6},{not_call,bitcask_pulse,incr_clock,[]}},{set,{not_var,7},{not_call,bitcask_pulse,fold,[{not_var,4}]}},{set,{not_var,8},{not_call,bitcask_pulse,gets,[{not_var,4},{3,11}]}},{set,{not_var,9},{not_call,bitcask_pulse,gets,[{not_var,4},{7,50}]}},{set,{not_var,11},{not_call,bitcask_pulse,incr_clock,[]}}]]}},{set,{var,4},{call,bitcask_pulse,bc_open,[true,{true,{255,63,413},100}]}},{set,{var,8},{call,bitcask_pulse,puts,[{var,4},{1,30},<<168,239,137>>]}},{set,{var,9},{call,bitcask_pulse,fold,[{var,4}]}},{set,{var,12},{call,bitcask_pulse,delete,[{var,4},7]}},{set,{var,13},{call,bitcask_pulse,puts,[{var,4},{1,13},<<7,103,94,199,217,211,64,106>>]}},{set,{var,14},{call,bitcask_pulse,puts,[{var,4},{18,33},<<141,252,203,157>>]}},{set,{var,15},{call,bitcask_pulse,puts,[{var,4},{42,47},<<209,111,152,239,176,33,14,200>>]}},{set,{var,19},{call,bitcask_pulse,fork_merge,[{var,4}]}},{set,{var,21},{call,bitcask_pulse,puts,[{var,4},{3,20},<<228,240,196,12>>]}},{set,{var,22},{call,bitcask_pulse,puts,[{var,4},{47,48},<<206,42,5,22>>]}},{set,{var,23},{call,bitcask_pulse,delete,[{var,4},7]}},{set,{var,27},{call,bitcask_pulse,sync,[{var,4}]}},{set,{var,28},{call,bitcask_pulse,puts,[{var,4},{31,38},<<71,173,38,2,161,59,41>>]}},{set,{var,29},{call,bitcask_pulse,incr_clock,[]}},{set,{var,30},{call,bitcask_pulse,bc_close,[{var,4}]}},{set,{var,31},{call,bitcask_pulse,incr_clock,[]}},{set,{var,32},{call,bitcask_pulse,bc_open,[true,{true,{218,167,488},84}]}},{set,{var,33},{call,bitcask_pulse,delete,[{var,32},28]}},{set,{var,34},{call,bitcask_pulse,fork_merge,[{var,32}]}},{set,{var,35},{call,bitcask_pulse,delete,[{var,32},7]}},{set,{var,37},{call,bitcask_pulse,delete,[{var,32},23]}},{set,{var,38},{call,bitcask_pulse,put,[{var,32},44,<<227,215,111,250,91,38>>]}},{set,{var,39},{call,bitcask_pulse,delete,[{var,32},29]}},{set,{var,41},{call,bitcask_pulse,sync,[{var,32}]}},{set,{var,9999},{call,bitcask_pulse,get,[{var,32},7]}},{set,{var,42},{call,bitcask_pulse,bc_close,[{var,32}]}},{set,{var,43},{call,bitcask_pulse,incr_clock,[]}}],{22840,31851,8451},[{0,[]},{1,[]},{errors,[]},{events,[]}]].
    [begin Now = now(), io:format("Now ~w ", [Now]), true = eqc:check(bitcask_pulse:prop_pulse(), [lists:nth(1, Cqq3), Now, lists:nth(3, Cqq3)]) end || _ <- lists:seq(1,5000)].
Fix truncated_datafile_test(), close all EUnit test keydirs
Add more EUnit fudge time to generic_qc_fsm:qc_test_()
Another round of trying to eliminate PULSE nondeterminism.

* PULSE side-effect for all bitcask_nifs functions, !@#$!.  The
function-by-function declaration is too specific and thus too brittle.
Every time a new NIF is added or an existing NIF arity is changed,
everyone (myself included) forgets to change rebar.config.script.
Instead, we'll use a blanket wildcard statement, and for the few
non-NIF functions in bitcask_nifs.erl, they'll get instrumented too.

* Move make_merge_file() from bitcask_pulse.erl -> bitcask.erl,
because bitcask_pulse has an explicit `pulse_no_side_effect`
directive for file:'_' calls.
Adjust EUnit timeout for max_merge_size_test()
Add test time fudget to PR156 regression test cases
Fix EUnit nondeterminism by using unique data dir for each test iteration