sled
sled copied to clipboard
bitonic adaptive radix trie for various pid tracking
we use BTreeSet<PageId> in a lot of places, resulting in a huge memory overhead compared to better compact structures like the ART.
generally, these structures don't need to support concurrent sets and adds, but they do need to support an initial "growth" phase combined with a later "decaying" phase - hence bitonic. this opens up the design space a bit, as we can do more lock-free stuff when we can assume that sets and deletes won't be interleaved.
For this to be accepted it needs to measurably reduce memory usage at runtime without negative latency or throughput trade-offs.