Not sure if this is correct place for raise this issue for discussion or not, but i saw https://github.com/antirez/rax was not maintained for a while.. so I would like raise the discussion here:

Problem: Currently redis use embedded rax library for providing quick look up in certain places, such as slot_to_keys table, and tracking bcast prefixes, however, missing prefix search API may bring some level of inefficiency when searching by prefixes, for example in https://github.com/redis/redis/blob/unstable/src/tracking.c#L119 and https://github.com/redis/redis/blob/unstable/src/tracking.c#L320 If a prefix searching API can be provided, we can improve the time complexity from O(n) to O(k)(the string length of the key). This would be a good improvement when we have many tracking prefixes registered for redis.

Possible solution: We can extend the raxIterator functionality to provide this API support, we may need to do two changes: 1. extend the raxSeek function to include a symbol to search the last matching prefix node.(by calling raxLowWalk internal function) 2. provide an API called raxPath to pop out the node matching prefixes from iternator stack, this is similar to raxPrev call but simplier since we don't need to go deeper in the parent trees.

@redis/core-team please let me know your thoughts on this issue, thanks!

Comment From: itamarhaber

Hello dear @hwware

I think you're in the right place to propose improvements to rax, and especially so if these benefit Redis. I can't quantify the improvement yet (if you get to do it, before/after performance numbers are always good), but it sounds like a good idea to me :)

Comment From: madolson

Making structural improvements to the RAX library that make maintaining Redis easier sounds great to me as well.

Comment From: yossigo

I second (third really) that.

Comment From: hwware

thank you @itamarhaber @madolson @yossigo.. I will take look this. The main logic of the API should be fairly simple, but since RAX library is in lower layer and there are lots of edge cases need to be considered(like compressed node etc), we need to provide the test cases thoroughly on this to make sure no surprise happens.