cockroachdb / cockroachdb/cockroach

raft: introduce log consistency checks

Open
#135,238 0 comments 0 reactions 0 assignees View on GitHub
A-kv-replication C-enhancement O-postmortem O-support P-3 T-kv
Dominant language
Go
Stars
32.5k
Forks
4.1k
PR merge metrics
PR metrics pending

Description

## Background

Consistency of the state machine across replicas is central for CRDB correctness. Making `Range` state machines identical across replicas requires:

1. All replicas to agree on the same sequence of committed commands (provided by raft).
2. Command application to the state machine being deterministic/consistent across replicas (particularly, resilient to mixed-version situations).

In addition, raft gives its guarantee relying on a lower-level guarantee from storage:

3. Writes are ordered and durable (in particular, resilient to process/host crashes and restarts).

There is a line of defence against replica inconsistencies: a periodically running [consistency checker](https://github.com/cockroachdb/cockroach/blob/ea48855e3be78afd0ac85a3c9301da1a547b4418/pkg/kv/kvserver/replica_consistency.go#L63) which fails a node if its state machine diverges from other replicas. In most cases, it helps finding bugs early during the development cycle.

Downsides of the consistency checker:
- It consumes resources (by doing a full scan). As a result, we [throttle](https://github.com/cockroachdb/cockroach/blob/ea48855e3be78afd0ac85a3c9301da1a547b4418/pkg/kv/kvserver/consistency_queue.go#L33-L42) it. As a result, consistency checks are rare. The default is [once in 24h](https://github.com/cockroachdb/cockroach/blob/ea48855e3be78afd0ac85a3c9301da1a547b4418/pkg/kv/kvserver/consistency_queue.go#L24-L31).
- As a result, it can miss transient inconsistencies, or detect them late when there is less observability into the root cause.
- As a result, the blast radius can be large.
- Debugging state machine inconsistencies is costly / time consuming. The underlying cause can be in one of the 3 layers outlined above, which is a large surface spanning teams.

## Proposal

Introduce a cheap consistency check at the raft layer. **Goals**: run it continuously to reduce latency of detection; increase coverage; have a clear way to rule out or zoom into layers 1-3 when debugging.

Today, raft assumes (and ensures) that two `entryID`s match iff the entries are the same. It expands to the "Log Matching" property[^1]: two log prefixes match entirely iff they end with the same entry. This property is taken for belief without comparing the log contents, e.g. [when appending](https://github.com/cockroachdb/cockroach/blob/ea48855e3be78afd0ac85a3c9301da1a547b4418/pkg/raft/log.go#L159-L165) to the log. However, there is evidence that broken durability promises can trick raft into committing different entries under the same `entryID`, and introducing a split view.

We can strengthen this check by including an incremental checksum/hash of the log prefix into the entry. For example:
```
hash(log[:index]) = hash(hash(log[:index-1]) || index || term || data[index])
```

When doing the log match check, in addition to ensuring that `entryID` is the same, we would check that the log hashes also match. If we ever see two log prefixes with the same last `entryID` but mismatching hashes, there is a split view. It rules out state machine from investigation, and the likely cause is either a bug in raft (1), or loss of durability (3). Conversely, if the raft check does not fire, but the replica consistency check does, it means the cause is likely at the state machine level (2).

If the hash is cryptographically strong, it gives the property: once two log hashes diverge at `entryID`, they will never converge back. So the inconsistency will eventually be discovered if both replicas continue participating in a "critical path" / quorum of raft.

A strong hash is expensive, but even a simple/cheap checksum [over a critical subset of entry data, such as [unique proposal ID](https://github.com/cockroachdb/cockroach/blob/6610d705724a21c836f3521f75972e65d9e9e2d4/pkg/kv/kvserver/replica_proposal.go#L136-L137)] would go a long way detecting inconsistencies at this level.

[^1]: https://raft.github.io/raft.pdf

Jira issue: CRDB-44409

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.