os: KeyValueDB: Add virtual raw_key() function to return (prefix,key) pair

In certain cases, such as when we are iterating over the whole key space,
it is useful to obtain the (prefix, key) pair. We could easily obtain the
key as is, but given that each implementation may deal with prefixes and
keys differently (for instance, the LevelDBStore will use '\0' as the
separator for the 'prefix' and 'key' components), we would rather have a
function responsible for returning a pair instead.

Signed-off-by: Joao Eduardo Luis <joao.luis@inktank.com>
os: LevelDBStore: implement the KeyValueDB's raw_key() function

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 'FooBar'. Since the separator used on the LevelDBStore is '\0',
but considering that different implementations of KeyValueDB may use
different separators, anyone using a K/V implementation would have to be
aware of the separator and parse the prefix and the key if they so wanted
to do it during an iteration over the whole store's key space.

As such, implement the raw_key() function which will be responsible for
returning a pair (prefix,key), leaving the parsing and all the
implementation-specific details for the implementation itself.

Signed-off-by: Joao Eduardo Luis <joao.luis@inktank.com>
os: KeyValueDB: Add read-only iterator related interface functions.

Signed-off-by: Joao Eduardo Luis <joao.luis@inktank.com>
os: LevelDBStore: Add a read-only iterator

This read-only iterator relies on leveldb's snapshots, and is intended as
a thread-safe iterator for those occasions when preventing concurrent
modification is not an option.

For instance, we need to iterate over a known, consistent store state
during monitor synchronization, while allowing updates to be performed for
Paxos sake -- and that means both insertion and removal of keys, which
could be, at best, problematic or simply bear unforeseen issues that could
ultimately only be seen during full-fledged concurrent accesses to the
store.

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

os: LevelDBStore: Create a whole-space iterator and read-only iterators

Signed-off-by: Joao Eduardo Luis <joao.luis@inktank.com>
test: cli: mon-store-tool: use raw_key() instead of key() while iterating

raw_key() returns a pair (prefix,key), which is useful when we are
iterating over all the keys in the store.

Signed-off-by: Joao Eduardo Luis <joao.luis@inktank.com>
mon: Paxos: change parameter name on propose_new_value()

We were still keeping the 'oncommit' parameter name, when in fact that
callback is called when we finish the proposal. Therefore, change it from
'oncommit' to 'onfinished' to make it clearer what it is all about.

Signed-off-by: Joao Eduardo Luis <joao.luis@inktank.com>
mon: Paxos: create function to queue a proposal and use it

Instead of creating a proposal and add it to the queue directly on
propose_new_value(), we now use a function that does just that. This will
become useful when we use it on trim_to() to queue a proposal to trim the
Paxos state.

Signed-off-by: Joao Eduardo Luis <joao.luis@inktank.com>
mon: Paxos: do not allow a peon to trim the Paxos versions

We are going ahead and make the trimming a Paxos proposal. We cannot allow
a Peon to be responsible for his own trimming, as it should come from the
Leader in proposal form.

Signed-off-by: Joao Eduardo Luis <joao.luis@inktank.com>
mon: Paxos: assert on finish_proposal() if mon is not the leader

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

Instead of directly modifying the store whenever we want to trim our Paxos
state, we should do it through the Paxos itself, proposing the trim to the
quorum and commit it once accepted.

This enforces three major invariants that we will be able to leverage later
on during the store synchronization:

 1) The Leader will set the pace for trimming across the system. No one
    will trim their state unless they are committing the value proposed by
    the Leader;

 2) Following (1), the whole system (at least all the mons that are part of
    the quorum) will trim at the same time. There will be no divergent
    states due to trimming on different monitors.

 3) Each trim will be kept as a transaction in the Paxos' store, allowing
    us to obtain a consistent state during synchronization, by shipping the
    Paxos versions to the other monitor and applying them. We could have
    incurred in an inconsistent state if the trimming was happening at any
    time and without being logged; but by going through Paxos this concern
    no longer applies.

The trimming itself may be triggered each time a proposal finishes, which
is the time at which we know we have committed a new version on the store.

It shall be triggered iff we are sure we have enough versions on the store
to fill the gap of any monitor that might become alive and still hasn't
drifted enough to require synchronization. Roughly speaking, we will check
if the number of available versions is higher than 'paxos_max_join_drift'.

Furthermore, we added a new option, 'paxos_trim_tolerance', so we are able
to avoid trimming every single time the above condition is met -- which
would happen every time we trimmed a version, and then proposed a new one,
and then we would trim it again, etc. So, just tolerate a couple of commits
before trimming again.

Signed-off-by: Joao Eduardo Luis <joao.luis@inktank.com>
mon: MonitorDBStore: add clear() function to remove all keys from the store

We also provide a finer-grained function that should receive a set of
strings containing exceptions. Basically, any key in the store with the
same prefix as any value in this exceptions set will not be removed.

This is useful to clear the Paxos' and the services' state from the store
without messing the Monitor-specific keys, which if removed would make the
monitor unusable.

Signed-off-by: Joao Eduardo Luis <joao.luis@inktank.com>
msg: Message: Add msg type id for MMonSync

Signed-off-by: Joao Eduardo Luis <joao.luis@inktank.com>
mon: MonitorDBStore: Use LevelDBStore's thread-safe iterator

We need to read the store while still performing updates due to Paxos
proposals. Therefore we need to make sure we always see a consistent state
despite what may be happening. By using a thread-safe iterator from
LevelDBStore, we guarantee that we do not incur in unforeseen problems
regarding keys being added or removed while iterating over the available
keys in the store.

Signed-off-by: Joao Eduardo Luis <joao.luis@inktank.com>
messages: MMonSync: Monitor Synchronization message (WIP)

This commit message will be updated with the full description once this is
no longer WIP. It is mostly done, but there are certainly things that will
end up going away and other things that will be introduced.

Signed-off-by: Joao Eduardo Luis <joao.luis@inktank.com>
mon: Monitor: Add initial support for synchronization (WARNING: WIP)

This is very on-going work, and I've actually stopped working on it for the
time being while addressing other pieces of this puzzle. And I feel I can't
emphasize this enough: this is on-going work.

There is a lot of stuff missing, some other stuff was completely left in
a limbo of half-done/half-undone, and it will certainly NOT WORK.

Also, there are a couple of things that are to be replaced, some other
stuff will be stripped away.

Please, do not waste time reviewing it.

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