cockroachdb / cockroachdb/cockroach

raft: maintain the size of the raft log

Open
#136,358 0 comments 0 reactions 0 assignees View on GitHub
A-kv-replication C-enhancement C-performance T-kv
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

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.