basho/riak_ensemble — pull request #37 by jtuple (2014-07-03 09:30:01+00:00)
Title: New integrated integrity checking for previously committed data

(***Note:*** This is a preliminary pull-request to enable code review while I perform minor code cleanup as well as make 2-3 additional changes/commits)

This pull-request completely changes how `riak_ensemble` guarantees the integrity of committed backend data, even in the presence of byzantine faults. Prior to this pull-request, the approach used was to assume byzantine faults could only occur when a peer restarts and to use backend-specific syncing/verification logic to ensure data integrity and vouch for a given peer. This approach is discussed at length in basho/riak_kv#909 (along with the related paranoia setting pull-request and linked gist).

This approach has two main problems. First, it assumes data loss can only occur between peer restarts -- which is fundamentally unsound. Second, it pushes all data integrity guarantees to the backend implementation and assumes the backend correctly guarantees data integrity. This is a risky assumption.

For example, for Riak the`riak_kv_ensemble_backend` relies upon traditional AAE syncing to ensure data integrity. However, this is fundamentally unsound since the AAE trees are best effort and are not designed to be canonical sources of truth. Additionally, the AAE trees impose a significant operational burden on the user. Specifically, Riak K/V ensembles will be completely unavailable (eg. fail user requests) if AAE is disabled or if AAE trees are in the process of being built (which can take hours to days depending on data set size) when a majority of peers restarts. Thus, this approach burdens the user, leads to potentially long periods of unavailability, yet doesn't provide strong integrity guarantees.

In the end, the hash trees used for AAE are the wrong tool for guaranteeing data integrity. For traditional AP/Riak, the backend itself is the canonical source of truth. The AAE trees are simply best-effort projections of this truth, and are rebuilt weekly by scanning over the backend data directly.

For `riak_ensemble`, we need a metadata source with stronger guarantees -- where the metadata is always trusted, and where the backend is considered wrong (corrupted, lying, etc) if it ever differs from this trusted metadata.

This pull-request integrates backend integrity checking directly into `riak_ensemble` itself, removing the notion of backend trust / syncing. Instead, individual `riak_ensemble` peers now maintain an integrated self-validating hash tree (known as `synctree` in the code). The hash for a given node in the tree is stored in the node's parent, allowing all traversals through the tree to verify the integrity of the entire path -- from the root node down to the destination node. This is similar in spirit to the design used in the ZFS filesystem. (See [this](http://research.cs.wisc.edu/adsl/Publications/zfs-corruption-fast10.pdf) research paper for a high level discussion of the ZFS design as well as how it holds up to various evaluated dataloss/corruption scenarios).

The `synctree` is maintained on each peer in an ensemble and is always kept up-to-date. As new data is written, the `synctree` hash is updated on the leader after seeing a quorum accept the write. This hash tree update is then replicated to followers. (Note: this replication is currently asynchronous. We should make synchronous a configurable option for highest level of paranoia/data integrity).

For all K/V operations, data returned from the backend is verified against the metadata stored in the hash tree. If the backend has incorrect data, the peer will detect the issue and attempt to repair the value from sibling peers.

As with the `hashtree` module from `riak_core`, which is used for AAE, the `synctree` module is designed to perform a tree exchange with remotes replicas to detect and repair any missing data -- in this case, object integrity metadata.

At startup, all peers are considered untrusted and are required to perform a tree exchange with a majority of trusted peers (or *all* peers if a trusted majority is unavailable). This requires more than a simple majority of online/reachable nodes. After performing this exchange, a given peer's tree is assumed to remain trusted. We make this assumption because in addition to the on-disk tree itself, we also maintain a copy of the top hash of the tree in memory. The assumption is that any combination of on-disk or in-memory corruption that occurs will not result in corrupted hashes that pass the tree verification check.

All operations on the tree (reads, writes, and exchange-related reads) verify all encountered tree paths. Thus, corruption in the tree itself will be detected. If detected, the tree discards the corrupted data, becomes untrusted, and must once again perform an exchange with a majority of trusted peers. This design therefore ensures the integrity of the object metadata at all times, enabling a peer to always be able to correctly detect an invalid object (or unexpected notfound) from the backend.

The specific data loss / byzantine faults this pull-request is designed to handle include both undetected data loss as well as data unexpectedly traveling back in time.

An example of undetected data loss would be a backend that lies about writing an object + CRC to disk. Thus, in the future the backend could return a notfound without firing any integrity check (since the CRC itself is also is missing). The same situation can occur in cases where a given backend does detect data corruption that is "repaired" by deleting corrupted keys (eg. LevelDB repair does this, as does Postgres's repair logic, and many, many others) without the higher level application (`riak_ensemble` in this case) realizing those keys were deleted.

An example of data going back in time would be a user restoring K/V data (eg. LevelDB or Bitcask data) from a backup without also restoring the `riak_ensemble` data from the same backup. Thus, as far as `riak_ensemble` is concerned the peer is at epoch Y (with the assumption data is also at epoch Y), but in reality the data is at epoch X (where X < Y). Traditionally, there is no way for the consensus system to detect this case. However, the new integrated metadata trees in `riak_ensemble` (which are also at epoch Y) would immediately detect invalid data on access.

This approach does nothing to detect intentionally crafted data corruption (eg. malicious users). If users can already access/modify your Riak data files, you've already lost (at least, with Riak's design today).

In addition to implementing this new integrity logic, this pull-request also removes the notion of backend trust/syncing from `riak_ensemble`. For Riak itself, this means that Riak-level AAE is no longer necessary to use strongly consistent operations, removing the operational burden discussed above. However, this new integrity checking approach focuses solely on syncing metadata between peers -- not data. This metadata is enough to detect corruption and trigger repair as data is accessed (eg. read repair), but does not sync cold data. Enabling Riak-level AAE is still therefore useful to detect/repair corrupted cold data. (***Note***: Technically not just yet -- that's one of the remaining pull-request items that needs to be done, and will require a PR against `riak_kv`. Coming soon!).

For more details, please see the commit messages for each the commits in this pull-request as well as look at the module level edoc for `synctree.erl`.