Skip to content

[V2] Prefix compression for keys #2

@bravo1goingdark

Description

@bravo1goingdark

Summary

Implement prefix compression to reduce memory usage for keys that share long prefixes (e.g., user:12345:email, user:12345:name).

Motivation

For sorted workloads with keys sharing common prefixes (common in LSM-tree use cases like user:{id}:{field}), storing only the suffix can significantly reduce memory usage.

Implementation Notes (from design doc)

Store only the suffix after a shared prefix:

struct NodeHeaderCompressed {
    shared_prefix_len: u32,  // bytes shared with predecessor's key
    key_suffix_len: u32,
    // ...
}

This requires the predecessor to be stable (it is, since nodes are never moved). Implementation adds complexity to find_less and comparison.

From design doc

See LOCKFREE_SKIPLIST_DESIGN.md lines 391-403

Priority: medium

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions