feature (store v2): Support Reverse Iteration for PebbleDB

[alexanderbez]

Summary

The SS interface requires that all implementations define iteration methods, forward and reverse. See here.

Note, iteration must work on versioned domains, i.e. iterate forward or reverse over the domain [x,y) for version X, s.t. each key/value pair returned is in the domain [x,y) AND the version for that key/value pair is at most X (unless deleted/tombstoned).

Problem Definition

We have 3 SS backends -- RocksDB, PebbleDB, and SQLite. Iteration is implemented for all of them. Reverse iteration is only currently implemented for RocksDB and SQLite.

PebbleDB is a derivative of RocksDB, however, it does not support all the features of RocksDB. Namely, RocksDB provides us with a versioning mechanism out-of-the box using Column Families and User-Defined-Timestamps. So implementation for iteration for RocksDB is trivial.

PebbleDB has no such Column Family feature, so we're forced to implement versioning ourselves (MVCC keys). Our implementation is based off of the way CockroachDB uses PebbleDB MVCC keys.

Efficient iteration for PebbleDB is possible using the NextPrefix API. See here. However, reverse iteration is not so trivial since there is no PrevPrefix API.

Proposed Feature

Implement reverse iteration for PebbleDB. The basic idea is that we create the iterator just like we do for forward iteration, except we start at the last element. Then, Next() must scan manually continuously until it reaches a key who's prefix is smaller than the current key. (Note, we might be able to use SeekLT API to speed it up?). This is inefficient, but the only way it seems possible.

So it should look something like this:

func (itr *iterator) Next() bool {
  if itr.reverse {
    return itr.nextReverse()
  }

  return itr.next()
}