[Versioned Storage] Version chain data structure for RocksDB-based storage

To support Concurrency Control and implement effective transactions capability to store multiple values of the same key is needed in existing storage.

Version chain

Key component here is a special data structure called version chain: it is a list of all versions of a particular key, with the most recent version at the beginning (HEAD).

Each entry in the chain contains value, reference to the next entry in the list, begin and end timestamps and id of active transaction that created this version.

There are at least two approaches to implement this structure on top of RocksDB:

• Combine original key and version into a new key which is put into a RocksDB tree. In that case to restore version chain we need to iterate over the tree using original key as a prefix.
• Use original key as-is but make it pointing not to the value directly but to an array containing version and other metainformation (ts, id etc) and keys in some secondary tree.

New API to manage versions

The following new API should be implemented to provide access to version chain:

• Methods to manipulate versions: add new version to the chain, commit uncommited version, abort uncommited version.
• Method to cleanup old versions from the chain.
• Method to scan over keys up to provided timestamp.