basho/riak_ensemble — pull request #41 by jtuple (2014-07-10 03:31:08+00:00)
Title: Fix numerous issues with leader leases

This pull-request builds on top of #37, so I've made the pull-request against that branch in order to keep things clean for review. After that branch merges and this review is complete, I'll open a dummy pull-request against `develop` for the final Bors checking/merge

---

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] 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