Skip to content

Introduced key encoding for hierarchical sorting#764

Merged
merlimat merged 3 commits intooxia-db:mainfrom
merlimat:encoded-sorting
Oct 20, 2025
Merged

Introduced key encoding for hierarchical sorting#764
merlimat merged 3 commits intooxia-db:mainfrom
merlimat:encoded-sorting

Conversation

@merlimat
Copy link
Copy Markdown
Collaborator

Until now, we've used a custom comparer in Pebble to achieve the hiearchical sorting.

This PR is changing it to use a key-encoding scheme and byte-wise sorting instead. There are a few reasons:

  1. Custom comparer is not working anymore in Pebble 2.1. There are several additional restrictions that makes it possible to continue using the current compare function. We are locked out of upgrading Pebble if we don't change this.
  2. We need to upgrade to Pebble 2 because there is a conflict version with ZStd depedency. Newer Zstd is making Pebble 1.x crashing. There are other dependencies that start requiring new Zstd, such as the hashicorp/raft dep in Raft based metadata provider #757.
  3. All in all, this will make all the internal DB operations faster, since after the keys are encoded in the wrapper layer, than all the comparisons will just by byte-wise comparison (eg: db iterators, compactions, ...)

There is a new marker added by Oxia to the db so we know the key encoding format. Later, we will add more encoding option (eg: natural sorting).

The first time a db is opened, if the marker is not set, it will be converted to new format.

Signed-off-by: Matteo Merli <mmerli@apache.org>
Signed-off-by: Matteo Merli <mmerli@apache.org>
Signed-off-by: Matteo Merli <mmerli@apache.org>
@merlimat merlimat mentioned this pull request Oct 18, 2025
@merlimat merlimat merged commit 7211295 into oxia-db:main Oct 20, 2025
6 checks passed
@merlimat merlimat deleted the encoded-sorting branch October 20, 2025 17:23
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant