Skip to content

Select eviction policy for DA compression temporal registry #2231

@Dentosal

Description

@Dentosal

Introduced in #1609.

DA compression uses "temporal registry", a key-value database where each compressed block header lists new writes to the registry. Since the keyspace is limited to 24bits per type, keys have to be removed according to some logic. The scheme is designed so that changing the way the evicted keys are picked can be freely changed without affecting backwards compatibility.

Currently, the code simply removes the lowest key that's not used by the current block. This suboptimal. Ideally, the values are least likely to be reused in the future will be dropped first (and values never written to are always dropped first). Something like LRU might be a good candidate for this. To get best results, we should observe real data from the system to see what the reuse rates are.

// Pick first key not in the set
// TODO: this can be optimized by keeping a counter of the last key used
// TODO: use a proper algo, maybe LRU?
let mut key = RegistryKey::ZERO;
while self.keep_keys[keyspace].contains(&key) {
key = key.next();
assert_ne!(key, RegistryKey::ZERO, "Ran out of keys");
}
self.keep_keys[keyspace].insert(key);
Ok(key)

Metadata

Metadata

Assignees

No one assigned

    Labels

    tech-debtThe issue is to improve the current code and make it more clear/generic/reusable/pretty/avoidable.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions