Ordered Key-Value Stores(hyper.dev)
hyper.dev
Ordered Key-Value Stores
https://hyper.dev/ordered-key-value-stores.html
11 comments
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.
Awful data locality however. Random seeks while reading ordered data will give you the worst possible performance.
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.
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
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
Those join algs you link too are pretty fun. And that next key command/ Api bit is also super handy in writing performant array algorithms.
Yeah, I think PostgreSQL is a good first go to database when starting projects. I think its powerful software.
Isn’t this just a key value store with a seperate contiguous index?
I did not see TIKV page mention anywhere about being ordered.
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.
Storage engine on a node using ordered keys is not the same thing as a distributed KV store maintaining an ordered index.
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.
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.
FoundationDB is an ultimate KV
Missing a feature in your database? Just write a layer for it! Works for every requirement of the original post.
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.
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.
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.
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.
[0]: https://hyper.dev/81aabee4001a47bf9c8bdf4475201ba7.html
[0]: https://hyper.dev/81aabee4001a47bf9c8bdf4475201ba7.html
How is this upvoted so highly? The web page has very little information, and isn't even complete
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
Redis also has sorted sets
https://redis.io/topics/data-types#sorted-sets
https://redis.io/topics/data-types#sorted-sets
Hey all, I've been seeing confusion in the comments, so I'll link to official FoundationDB docs that do a better job of explaining these concepts.
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
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
As a side note I didn't write the original article
This page looks incomplete.
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.
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.
It’s not the only thing it can do, but it’s still very good at it.