redpanda
redpanda copied to clipboard
ct: Add `dl_stm`
This PR adds dl_stm
implementation.
The implementation is pretty basic and can only be used to add new data and not remove it (no truncation, no replacement).
Internally, the STM uses the data structure based on 'patience sort' algorithm. It contains a set of sorted runs. When new overlay is added it's added to the first sorted run that can fit it without breaking monotonicity. If the number of sorted runs exceeds certain threshold the compaction is invoked. The compaction simply uses k-way merge to put all overlay batches into one big sorted run.
There is no compression at the moment. The idea behind this memory arrangement it that it should be simple to go from this to columnar format (no in-place updates are required).
Backports Required
- [x] none - not a bug fix
- [ ] none - this is a backport
- [ ] none - issue does not exist in previous branches
- [ ] none - papercut/not impactful enough to backport
- [ ] v24.2.x
- [ ] v24.1.x
- [ ] v23.3.x
Release Notes
- none