Hacker News new | past | comments | ask | show | jobs | submit login
Ask HN: Optimised scan which returns keys having common prefix in sorted order
1 point by absolute7 62 days ago | hide | past | favorite | 2 comments
Hi Everybody,

I found it hard to get keys in Redis with common prefix in sorted order.

So, I am working on implementing a modified data structure using which we can get sorted keys with a common prefix very fast. The command takes a start index and count as well. Here's how fast it is - I have put 10 ^ 7 keys in Redis and the new tcp server built on top of the data structure which I have created. Keys are of format "user:(number)" where number goes from 1 to 10 ^ 7. On running the following command in Redis

scan 0 match user:66199* count 10000000 It takes 2.62s. I know we should use scan command with less count value and retry command until we get a 0 cursor back.. This is just for getting all data for a common prefix, I have used a bigger count value. On running the following command in new server built on top of the data structure scankeys 0 user:66199 It takes 738.083µs and returns all keys having this "user:66199" as prefix. Both the commands outputs same number of keys which are 111. My question to this community is that - Do you people think its a valid use case to solve? Do you guys want this kind of data structure which has support of GET, SET, MGET, SCAN .. where SCAN takes a prefix and returns keys having common prefix in sorted order. Have you guys encountered this use case/problem for production systems?




B-Tree


data structures making use of underlying hardware may have better performance than generic b-tree.[0][1][2][3]

[0] LSM (relies on ability to cache reads) vs. b-tree : https://tikv.org/deep-dive/key-value-engine/b-tree-vs-lsm/

[1] alternatives such as c-tree (lower memory usage/query time at cost of flexibility): https://en.wikipedia.org/wiki/C-trie

[2] radix variants : https://en.wikipedia.org/wiki/Radix_tree

[3] striped trie (distributed/parallel searching of shards) : https://www.agdresearch.com/striped-trie




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: