Add ready to start backend callback

This will be used, for example, to indicate that Riak KV ensemble peers
should wait for the riak_kv service to be up before starting to avoid
some nasty races.
Merge pull request #32 from basho/feature/dont-start-peer-until-backend-ready

Add ready to start backend callback

Reviewed-by: lordnull
Save ensemble/cluster state when cluster enabled

Fixes #34 and hopefully basho/riak_kv#983
See #34 for details

Note that even when `riak_ensemble_manager:maybe_save_state/1` fails during
enable, we still want to call `riak_ensemble_manager:state_changed/1` to
ensure that we don't have inconsistent ets tables and running peers.
However, since this activation is not saved we can still send up with
the issue in basho/riak_kv#983.
Ensure activated cluster state is saved before use

In order to do this we turn `riak_ensemble_manager:activate/0` into a
pure function. We do this by removing calls to `ets:insert/2` and
returning the data to be inserted instead. The caller can then attempt
to save and sync the data. If this succeeds, then finally the call to
`ets:insert/2` is made and the state is updated along with `ok` being
returned to the client.
Step down if local_put fails in leader worker

In riak_ensemble_peer:put_obj/4 when local_put/4 fails, step down by
sending a 'request_failed' message to the leader.
Merge pull request #27 from basho/bugfix/step-down-on-local-failure

Step down if local_put fails in leader worker

Reviewed-by: andrewjstone
Merge pull request #35 from basho/bugfix/sync-save-state-on-enable

Save ensemble/cluster state when cluster enabled

Reviewed-by: engelsanchez
Add test deps, test runner, and drop_write_test

Up to this point, riak_ensemble does not have any included unit tests,
relying instead upon high level riak_test system tests that indirectly
test riak_ensemble via Riak. This commit changes this.

This commit adds support for test-only dependencies and adds riak_test
as one of those dependencies to get access to the intercept logic
included with riak_test.

This commit also adds the 'test/run.sh' runner script which is designed
to run individual eunit tests separately for isolation -- preventing
test environment woes. This is necessary because most interesting
riak_ensemble tests are inherently stateful and correctly cleaning up
after a stateful test has historically proven challenging (one reason
why riak_ensemble has preferred riak_tests up to this point).

This commit also adds the `drop_write_test` which uses an intercept to
lie about storing a peer-write to stable storage. Against the current
design of riak_ensemble, this can result in a notfound being returned
to the user for a value we previously acknowledged as written. This is
a serious bug that will be addressed in a later commit.
Fix riak_ensemble_util:orddict_delta order

It is expected that orddict_delta returns the delta list in sorted
order. However, the current implementation incorrectly mixes a list
generated in reverse with a list generated in normal order, leading
to inconsistent ordering.

This commit fixes that issue, leading to orddict_delta always returning
results in proper order.
Implement new synctree module

The new synctree module implements a self-validating hashtree that is
going to be used as riak_ensemble's new data integrity mechanism (in a
future commit). This tree is designed similar to the hashtree used in
file systems such as ZFS, with parent nodes containing the hash of
their children. Thus, during traversal a tree path can be completely
verified from the root node to the endpoint.

The tree is designed to be replicated on multiple nodes and provides
built-in exchange logic that efficiently determines the differences between
two trees -- thus trees can exchange with peers and heal missing/corrupted
data.

The design is conceptually similar to hashtree.erl from riak_core. For
further details, look at the module level edoc in synctree.

The synctree design allows for pluggable backends. This commit provides
the synctree_orddict and synctree_ets backends.
Implement synctree_leveldb module

The synctree_leveldb module provides a synctree backend built on LevelDB
This is the first persistent synctree backend and will be the backend used
for riak_ensemble peers (in a future commit).
Implement new approach to integrity checking/syncing

This commit completely changes how riak_ensemble deals with backend
data loss situations.

Traditionally, once data was committed to a given backend, riak_ensemble
assumed the data would never go missing. Of course, this is invalid
assumption so the notion of backend trust was previously added to
riak_ensemble along with the notion of backend syncing. Untrusted peers
were required to sync with a majority of peers to become trusted. What
exactly syncing meant was a backend-specific detail.

While this handled certain cases of data loss scenarios, it was far
from perfect.

First, it assumed backend syncing was valid. For the Riak K/V backend,
this was not true. The K/V backend relied upon AAE exchange which is
was never designed to be 100% authoritative.

Second, as an optimization, we only checked a peers trust at peer
statup time (or after a backend specific process crashed). This
does not help if a backend loses data while running in normal
operation.

This commit completely removes the notion of backend trust and syncing
from riak_ensemble. Instead, riak_ensemble now implements an embedded
integrity checking protocol based on self-validating hashtrees (using
the new synctree module).

Writing of keys now inserts appropriate metadata into this hash tree,
which is always validated against the keys when read. The synctree
is considered the authoritative source. If the backend disagrees, the
data is considered corrupted and is repaired from data on other
replicas.

Like before, peers that restart are considered trusted and must do
a synctree exchange with a trusted majority (which can include more
than a simple quorum during byzantine situations). This establishes
the initial trust of the synctree at peer startup. However, since
the synctree is self-validating, every operation that touches the
tree validates the traversed path. Thus, any corrupted to either the
on-disk or in-memory components of the synctree will be detected,
causing the tree to once again become untrust and require a new
round of syncing with a trusted majority.

Thus, as designed, a given peer is always able to validate the
entirety of its backend data against the synctree metadata, as well
as validate the synctree itself and repair it via exchange with
sibling replicas as needed.
Hack around buildbot's hardcoded use of rebar eunit
Update .gitignore
Update tools.mk to v0.5.5
Merge pull request #39 from basho/feature/update-git-ignore

Update .gitignore

Reviewed-by: jrwest
Merge pull request #40 from basho/feature/tools.mk-0.5.5

Update tools.mk to v0.5.5

Reviewed-by: andrewjstone
Fix numerous issues with leader leases

By design, riak_ensemble uses leader leases which enable the leader to
reply to read requests without contacting other peers in the ensemble.

This is similar to the design discussed in "Paxos Made Live" [1].

To safely use leader leases, a consensus protocol must:

1. Use strong leaders. A new leader should never be able to be
   elected while followers are supporting an existing leader.

2. Ensure that no peers (current followers or otherwise) can be
   become a leader before the current leader's lease expires.

The protocol used by riak_ensemble supports strong leaders, thus
satisfying the first condition.

The second condition is challenging, because there are very few
guarantees one can make about system clocks; and even fewer that
one can make between clocks on different machines.

This commit hardens the leader leasing logic in riak_ensemble:

-- Leases are now explicitly tracked (rather than just implicitly
   tracked as part of the leader tick/step_down transition).

-- Worker processes now check that a lease is still valid after
   performing a read (rather than just before). This ensures that
   slow reads that complete after a lease expires are rejected.

-- The new lease tracking logic verifies a lease against both
   Erlang corrected time [2] (using receive timeouts) as well as
   against the OS monotonic clock. This is the strongest guarantee
   we can provide without special clock hardware (eg. GPS clocks).

-- Users can now set 'trust_lease = false' to force riak_ensemble
   to never trust leases and always perform quorum operations.

-- A new quorum operation was added (check_epoch) that solely verifies
   the legitimacy of the current leader. Previously, not trusting the
   lease performed a full quorum read which is unnecessary. There is
   no reason not to trust the leader's local data if the leader is
   legitimate.

[1] http://dl.acm.org/citation.cfm?id=1281103
[2] http://www.erlang.org/doc/apps/erts/time_correction.html
Make ens_test ensure app dependencies are started
Support M:N synctree to LevelDB instance mappings

By default, each peer synctree maps to a unique on-disk LevelDB
database. This commit enables ensemble backends to override this
behavior, supporting M:N mappings where multiple trees are stored
in the same on-disk instance.

This change is predominately aimed at Riak, which will use this
feature to map all peers associated with a single vnode to a common
per-vnode synctree LevelDB instance. Riak AAE already does a similar
thing in its hashtree code. Using fewer instances results in better
usage of file handles, write buffers, and the block/file cache.