cockroachdb / cockroachdb/cockroach
raft: maintain the size of the raft log
- Dominant language
- Go
- Stars
- 32.5k
- Forks
- 4.1k
- PR merge metrics
- PR metrics pending
Description
Today, the raft log size is maintained at best effort, and [recomputed](https://github.com/cockroachdb/cockroach/blob/4e677e4e68cd2c13684d16b06ad15318887298cb/pkg/kv/kvserver/replica_raft.go#L3028-L3051) by scanning the log when it becomes imprecise. We can avoid these scans by maintaining prefix sums next to the entries.
- Example log: `e10{size=100} e11{size=200} e12{size=150}`.
- We can store: `e10{sum=1100} e11{sum=1300} e12{sum=1450}`.
- When appending, the `sum` of the next entry is `sum` of the previous entry + size of our entry.
- Then the size of a log range `sum(from, to] = sum[to] - sum[from]`.
- When compacting or overwriting a range `(from, to]` out of the log, deduct the `sum(from, to]` from the in-memory `raftLogSize`.
Caveat: if the range lives for a very long time, the `sum` may wrap around `MaxUint64` (corresponding to 16 exabytes). However, the range `sum[to] - sum[from]` will be correct as long as the real log size if below `MaxUint64`, which in practice is always true. The wrapping will automatically "[unwrap](https://go.dev/play/p/ePu4Zs4jxiA)" itself after the subtraction.
Jira issue: CRDB-44992
Contributor guide
Assessment
This issue has not been assessed yet.