os: KeyValueDB: allow finer-grained control of transaction operations

This patch introduces the possibility of using single key/value
modification operations into the transaction interface.

Until now, any 'set' or 'rmkeys' operations required a map of keys to be
provided to the function, which made the task of removing or setting a
bunch of keys easier. Doing these same operations for a single key,
however, would entail creating a map with a single key.

Instead, this patch adds two new virtual abstract functions, to be
implemented by derivative classes, which set or remove one single
key/value, and we then implement the map-based, existing functions in
terms of these new functions.

We also update the derivative classes of KeyValueDB in order to reflect
these changes (i.e., LevelDBStore and KeyValueDBMemory).

Signed-off-by: Joao Eduardo Luis <joao.luis@inktank.com>
os: KeyValueDB: Add virtual raw_key() function to return (prefix,key) pair

If we were to use solely the key() function, whenever we had a key with,
say, prefix 'Foo' and key 'Bar', the key() function would return something
similar to 'Foo<separator>Bar'. Therefore, obtaining the prefix and the key
would require one to be aware of the separator used, and, since that is
implementation specific, we can't rely on such prior knowledge.

This new function must then be implemented by any derivative class of
KeyValueDB, and is expected to return a pair (prefix,key) for the
current iterator's position -- the key() function should behave as
previously, returning only the 'key' component of the pair.

Signed-off-by: Joao Eduardo Luis <joao.luis@inktank.com>
os: KeyValueDB: re-implement (prefix) iter in terms of whole-space iter

In-a-nutshell-version: Create a whole-space iterator interface, and
implement the already existing, prefix-based iterator in terms of the
new whole-space iterator;

This patch introduces a significant change on the architecture of
KeyValueDB's iterator, although its interface remains the same.

Before this patch, KeyValueDB simply defined an interface for a
prefix-based interface, to be implemented by derivative classes. Being
constrained by a prefix-based approach to iterate over the store only makes
sense when we know which prefixes we want to iterate over, but for that we
must know about the prefixes beforehand. This approach didn't work when one
wanted to iterate over the whole key space, without any previous awareness
about the keys and their prefixes.

This patch introduces a new interface for a whole-space iterator, to be
implemented by derivative classes, which is prefix-independent. We also
define an abstract function to obtain this iterator, which must also be
implemented by the derivative class. With this interface in place, we are
then able to implement a prefix-dependent iterator in terms of the
whole-space iterator, which will be offered by the KeyValueDB class itself.

Furthermore, we implement these changes on LevelDBStore and KeyValueDBMemory,
the in-memory mock store, which leads to significant changes on both:

  * LevelDBStore
    - Substitute the previously existing LevelDBIteratorImpl, which
      followed a prefix-based iteration, for
      LevelDBWholeSpaceIteratorImpl, which now iterates over the whole
      key space of the store;

  * KeyValueDBMemory:
    - Substitute the previously existing MemIterator, which followed a
      prefix-based iteration, for WholeSpaceMemIterator, which now
      iterates over the whole key space of the in-memory mock store;
    - Change the in-memory mock store data structure. Previously, we
      used a map-of-maps, mapping prefixes to a key/value map; now we
      keep a single map, mapping (prefix,key) pairs to values.

Signed-off-by: Joao Eduardo Luis <joao.luis@inktank.com>
os: KeyValueDB: implement snapshot iterators

Create a set of functions, to be implemented by derivative classes of
KeyValueDB, responsible for returning an iterator with strong
read-consistency guarantees. How this iterator is implemented, or by what
is it backed up, is implementation specific, but it must guarantee that
all reads made using this iterator are as if there were no subsequent
writes to the store since we created the iterator.

For instance, LevelDBStore will back this iterator with a leveldb Snapshot,
while KeyValueDBMemory will perform a copy of its in-memory map.

Signed-off-by: Joao Eduardo Luis <joao.luis@inktank.com>
test: test_keyvaluedb_iterators: Test KeyValueDB implementations iterators

This set of tests focus on testing the expected behavior of LevelDBStore's
and KeyValueDBMemory's iterators.

We will test the following use cases:

  * Removing keys from the underlying store while using the
    WholeSpaceIterator;
  * Removing keys from the underlying store while using the
    WholeSpaceSnapshotIterator;
  * Guarantee that both LevelDBStore's and KeyValueDBMemory's store
    state match after performing the same set of operations on both;

Signed-off-by: Joao Eduardo Luis <joao.luis@inktank.com>
Makefile.am: add test_keyvaluedb_iterators to the build

Signed-off-by: Joao Eduardo Luis <joao.luis@inktank.com>