TFA left me clueless as to whether there's anything about an "ordered key-value store" that adding a sequence field to an unordered (more easily parallelised) store doesn't provide.
It's all about efficient range reads and seek operations.
You can compute set operations pretty efficiently using sorted indices that support a "find next or greater" operation.
For intersection, take the first value from the first set as the smallest candidate of the output set, then call call candidate := next(candidate) on each set, updating the candidate with the next smallest possible value, and adding it to the output set when a candidate was returned by all sets.
The algorithm is worst case optimal up to a log factor, and can even be extended to perform generic constraint programming and multiway joins as a subset of that.
Fascinatingly it's related to the DPLL algorithm for sat solving.
See https://tikv.org/deep-dive/key-value-engine/introduction/. You can specify the storage engine, although all the available engines in that page order the keys: rocksdb allows prefix search, and both B and LSM trees naturally order keys.
I'm not entirely sure about what you mean, and I'm not terribly familiar with TiKV.
In general, a single node partition will use ordered storage. At a higher level (partitions/shards), you use either key ranges or hashing to route keys to partitions: https://tikv.org/deep-dive/scalability/data-sharding/
It seems TiKV uses range partitioning, so that's giving you the order across nodes.
It's late and I must be missing something (or maybe a lot).
ordered by key? ordered by value? ordered by insertion/update time?
Ordered for enumeration? or ordered where I can provide my own search? binary search is great, but I can think cases with better performance lookups with a bias in one direction.
I guess there are two main things.
1. what does ordered mean? I can think of lots of cases where having access to order would be super helpful. How do I tag the thing(s) I care about for lookup>
2. I'm not a super fan of go, but randomizing enumeration of maps was a really good move for avoiding inadvertent dependence on order.
I checked again, and I still don't see what order "means" (safari on OS X. maybe it's not rendering right?)
_edit_
after digging a little deeper, I guess I want to add 3
How are ties broken? Fastest result? Highest memory address?
Ordered KV would be super handy. But the devil is in the details, and I can't find any details.
Should be noted that when talking about e.g. Python dictionaries (and some other in-memory associative arrays), "ordered" refers to insertion order, where as "sorted" refers to key order.
I guess ordered KV stores usually requires total order on they, and that if two keys are identical they refer to the same data.
Randomizing the hash value is great for unordered maps, but for ordered maps you sometimes want to extract a range which can be done faster if you have them ordered for example in a b-tree.
A suggestion for the author: If you start a web page with 'Please bookmark the following address: https://okvs.dev' then you should probably put an explanation of why I should do that pretty soon after, don't just leave it at that!
There's almost no content in the linked article, but I'm confused at the sentence "there is none that meets all those requirements" taking into account the "software" link[0] at the end with plenty of examples. FoundationDB, TiKV, or any variation of RocksDB / LevelDB tend to include these features.
I have a suspicion that certain low-quality posts get employees with accounts to upvote and comment. I believe that this is one of them and two other big-offenders are Cloudflare and CockroachDB
Tangent: I'm very interested in implementations details for ordered key-value stores. B trees and their variants like B+ trees are pretty straightforward conceptually but there seems to be scarce resources on the nitty gritty details past find/insert/delete.
For example I'm interested in redistribution algorithms, duplicate key semantics, and merging. The relative naivety of their implementation can have a large impact on performance/storage depending on how the store is used.
25 comments
[ 2.3 ms ] story [ 59.9 ms ] threadIt’s not the only thing it can do, but it’s still very good at it.
For intersection, take the first value from the first set as the smallest candidate of the output set, then call call candidate := next(candidate) on each set, updating the candidate with the next smallest possible value, and adding it to the output set when a candidate was returned by all sets.
The algorithm is worst case optimal up to a log factor, and can even be extended to perform generic constraint programming and multiway joins as a subset of that.
Fascinatingly it's related to the DPLL algorithm for sat solving.
http://erikdemaine.org/papers/SODA2000/
https://arxiv.org/abs/1404.0703
https://arxiv.org/abs/1310.3314
https://arxiv.org/abs/1203.1952
https://arxiv.org/abs/1803.09930
In general, a single node partition will use ordered storage. At a higher level (partitions/shards), you use either key ranges or hashing to route keys to partitions: https://tikv.org/deep-dive/scalability/data-sharding/
It seems TiKV uses range partitioning, so that's giving you the order across nodes.
I guess there are two main things. 1. what does ordered mean? I can think of lots of cases where having access to order would be super helpful. How do I tag the thing(s) I care about for lookup> 2. I'm not a super fan of go, but randomizing enumeration of maps was a really good move for avoiding inadvertent dependence on order.
I checked again, and I still don't see what order "means" (safari on OS X. maybe it's not rendering right?)
_edit_
after digging a little deeper, I guess I want to add 3 How are ties broken? Fastest result? Highest memory address?
Ordered KV would be super handy. But the devil is in the details, and I can't find any details.
Should be noted that when talking about e.g. Python dictionaries (and some other in-memory associative arrays), "ordered" refers to insertion order, where as "sorted" refers to key order.
Randomizing the hash value is great for unordered maps, but for ordered maps you sometimes want to extract a range which can be done faster if you have them ordered for example in a b-tree.
[0]: https://hyper.dev/81aabee4001a47bf9c8bdf4475201ba7.html
https://redis.io/topics/data-types#sorted-sets
To get a high level overview and see what you can do: https://apple.github.io/foundationdb/features.html https://apple.github.io/foundationdb/design-recipes.html
Then to dive in a bit: https://apple.github.io/foundationdb/data-modeling.html https://apple.github.io/foundationdb/developer-guide.html (Subspaces, Directories, and Transactions)
Also, the section on Anti-Features is interesting: https://apple.github.io/foundationdb/anti-features.html
Tangent: I'm very interested in implementations details for ordered key-value stores. B trees and their variants like B+ trees are pretty straightforward conceptually but there seems to be scarce resources on the nitty gritty details past find/insert/delete.
For example I'm interested in redistribution algorithms, duplicate key semantics, and merging. The relative naivety of their implementation can have a large impact on performance/storage depending on how the store is used.