sstable: convert v1 range-del blocks to v2 on-the-fly

[petermattis]

RocksDB generated range-del blocks contain range tombstones that are not fragmented and sorted. Pebble always generates range-del blocks that are fragmented and sorted, making them suitable for serving directly. Pebble distinguishes between RocksDB generated (v1) and Pebble generated (v2) range-del blocks by storing the latter under a different property.

The code still has a TODO to convert v1 to v2 blocks when encountered:

// TODO(peter): if we have a v1 range-del block, convert it on the fly
// and cache the converted version. We just need to create a
// rangedel.Fragmenter and loop over the v1 block and add all of the
// contents. Note that the contents of the v1 block may not be sorted, so
// we'll have to sort them first. We also need to truncate the v1
// tombstones to the sstable boundaries.

I'm not sure if that last sentence regarding tombstone truncation is still accurate given the implicit truncation that happens in mergingIter and the explicit truncation for compactions being done in #67.

[ajkr]

storing the latter under a different property

Do you mind elaborating what you mean by this? I recall in RocksDB we distinguished the old and new formats by giving the range tombstone meta-block a different name. Or maybe we just talked about doing that; let me double-check.

[ajkr]

Or maybe we just talked about doing that; let me double-check.

Seems just talked about it. I think our justification was we can check whether tombstones are already fragmented with a linear scan, which is only done when range tombstone meta-block gets loaded to block cache, and that shouldn't be super frequent.

[petermattis]

Seems just talked about it.

I did this in Pebble. See https://github.com/petermattis/pebble/blob/master/sstable/table.go#L159-L160. Perhaps that isn't necessary, but there it is.

I think our justification was we can check whether tombstones are already fragmented with a linear scan, which is only done when range tombstone meta-block gets loaded to block cache, and that shouldn't be super frequent.

I thought the range tombstones in RocksDB could be unsorted as well, which requires more than a linear scan to fragment.

[ajkr]

I thought the range tombstones in RocksDB could be unsorted as well, which requires more than a linear scan to fragment.

In the newer versions they'll be stored sorted and fragmented. So it first does a linear scan checking if it's already sorted. Only if not it'll sort. It looks like it fragments either way.

[petermattis]

In the newer versions they'll be stored sorted and fragmented. So it first does a linear scan checking if it's already sorted. Only if not it'll sort. It looks like it fragments either way.

Ah, got it. I suppose that is an ok approach too. Regardless, we need to address the TODO in some fashion, either with the RocksDB approach or the plan I had previously envisioned.