Ordered Key-Value Stores

https://hyper.dev/ordered-key-value-stores.html

by timhigins • 6 years ago

40 25 6 years ago

hyper.dev

sfvisser• 6 years ago

PostgreSQL can easily store ordered key/value pairs.

It’s not the only thing it can do, but it’s still very good at it.

082349872349872• 6 years ago

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.

rapsey4• 6 years ago

Awful data locality however. Random seeks while reading ordered data will give you the worst possible performance.

j-pb• 6 years ago

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

wdb• 6 years ago

Yeah, I think PostgreSQL is a good first go to database when starting projects. I think its powerful software.

YankeeKiwi• 6 years ago

Isn’t this just a key value store with a seperate contiguous index?

rapsey4• 6 years ago

I did not see TIKV page mention anywhere about being ordered.

ergl3• 6 years ago

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.

rapsey4• 6 years ago

Storage engine on a node using ordered keys is not the same thing as a distributed KV store maintaining an ordered index.

rossmohax• 6 years ago

FoundationDB is an ultimate KV

louis-paul• 6 years ago

Missing a feature in your database? Just write a layer for it! Works for every requirement of the original post.

jfoutz• 6 years ago

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.

rapsey4• 6 years ago

Ordered by key. If you want to know more read the FoundationDB docs.

beagle3• 6 years ago

Thanks.

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.

erk__• 6 years ago

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.

joosters• 6 years ago

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!

ergl3• 6 years ago

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

jonluca• 6 years ago

How is this upvoted so highly? The web page has very little information, and isn't even complete

mhuffman• 6 years ago

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

shaicoleman• 6 years ago

Redis also has sorted sets

https://redis.io/topics/data-types#sorted-sets

timhigins2• 6 years ago

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

timhigins2• 6 years ago

As a side note I didn't write the original article

qppo• 6 years ago

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.

Ordered Key-Value Stores

Related Stories