stable: overhaul (again) range tombstone merging
stable: overhaul (again) range tombstone merging

In commit 99ecda3c9657eb882c064e177a537dce05bf5b87, we overhauled the
way we read Cassandra's disjoint range tombstones, and convert them to
the overlapping whole-prefix tombstones which we support.

Unfortunately, while this algorithm worked correctly for a couple of
test cases, it did not for additional test cases. While the previous
algorithm could not generate "wrong" tombstones (it didn't generate things
it didn't see), it could generate redundant overlapping tombstones, and
missed some sanity checks about the correctness of the merge process.

In this patch, a new algorithm makes sure to not generate redundant
tombstones, and includes additional tests to ensure that we do not
mistakenly merge range tombstones which cannot actually be merged.

The following patches will include tests which failed with the previous
algorithm, and succeeds with this one.

I described the new algorithm on the ScyllaDB mailing list this way:

1. Have a stack of open ranges, start & timestamp for each (no end for
   each), and just one "end of last contiguous deletion"
Processing each range tombstone:
2. If the start of a range tombstone is not adjacent to the "end of last
   deletion", assert we have no open range on the stack (because we can
   never close those). In any case, set the "end of of last deletion" to
   the end of this tombstone.
3. If the current tombstone's timestamp is STRICTLY HIGHER than that on the
   top of the stack, push the new tombstone's start+timestamp to the stack.
   Note: If it was STRICTLY LOWER, throw error (it means the open range will
   never be closed).
4. If the current tombstone's end matches (i.e., closes row) of the start on
   the top of the stack, emit this tombstone and pop the stack.
When the row ends:
5. Assert the stack is empty.

Signed-off-by: Nadav Har'El <625169824b719df98706d88646d0aae6f368ae4d@scylladb.com>
Message-Id: <1459778074-10759-1-git-send-email-625169824b719df98706d88646d0aae6f368ae4d@scylladb.com>

scylladb/scylla,raphaelsc/scylla,kjniemi/scylla,scylladb/scylla,raphaelsc/scylla,avikivity/scylla,kjniemi/scylla,avikivity/scylla,duarten/scylla,raphaelsc/scylla,scylladb/scylla,avikivity/scylla,duarten/scylla,scylladb/scylla,kjniemi/scylla,duarten/scylla