Indexing semantic versions in RocksDB (opens in new tab)

(blog.aawadia.dev)

28 pointsadamretter2y ago17 comments

17 comments

utopcell2y ago

> "The technical primitive data structure here is a hashmap where the keys are sorted."

..somewhere, this person's algorithms teacher is pondering about his life choices.

klysm2y ago

I don’t see why that’s a particularly bad explanation of how RocksDB works

morelisp2y ago

It's not using hashes.

(OK, well, it is maybe using hashes for the per-SST Bloom filter, but that's not what's interesting here. It's maybe also using hashes in the memtable in which case they're using it very inefficiently since the key encoding is not prefix-scan-friendly.)

zokier2y ago

I don't know anything about rocksdb, but this approach on surface level seems like it could be very slow? Wouldn't it be more efficient to encode the semver in a format more suitable to sorting

adamretterOP2y ago

By default RocksDB uses a ByteWiseComparator to sort the keys in the SST. However, RocksDB allows you to provide any comparator you wish. So ultimately it will depend on the performance of the comparator that you implement.

hdhfjkrkrme2y ago

Sure, the old performance/productivity tradeoff.

This quickly solves the problem then you can iterate for performance.

morelisp2y ago

Using RocksDB here seems fairly insane unless you need to keep (at least) several billion constantly-updating versions sorted. Otherwise you can just use SortedMap and regular Java comparators.

curtisblaine2y ago

They might just want cheap disk persistence. I'm not a Java developer, but if SortedMaps are a memory-only data structure, persisting them reliably doesn't look an easy feat.

morelisp2y ago

RocksDB is disk persistence but it sure ain't (for this scale) cheap.

Persisting just about anything in Java is easier than persisting it in Java in RocksDB.

1 more reply

gnulinux2y ago

> The technical primitive data structure here is a hashmap where the keys are sorted.

Why not a tree based map instead?

The_Colonel2y ago

HashMap and sorted keys sounds like a contradiction. I think they just use "HashMap" as a generic term for "Map" and it's actually a tree based map.

morelisp2y ago

It is an LSMT, but I cannot imagine why they would need one here.

samsquire2y ago

I am curious, I recently wrote a naive hashmap for C. I am curious about iterating in insert and sort order.

Is it possible for a hash function to maintain a sort relationship to it's input and output?

blyzz2y ago

Supporting insertion order is straightforward (but has some trade-offs) - you store the values in a backing array or linked list, and the hash table array stores pointers to the values.

You could do something similar with a sorted data structure backing the hashmap to get sorted order (a b-tree or something similar).

You could have the hash function preserve order at the cost of it being a very bad hash function. If you had n buckets, then the first 1/n elements in the keyspace would map to bucket 0, then next 1/n elements map to bucket 1, etc.

hdhfjkrkrme2y ago

If you iterate a python dictionary it will return the keys in insert order.

For sort order you need to sort separately.

j / k navigate · click thread line to collapse

17 comments

utopcell2y ago

> "The technical primitive data structure here is a hashmap where the keys are sorted."

..somewhere, this person's algorithms teacher is pondering about his life choices.

klysm2y ago

I don’t see why that’s a particularly bad explanation of how RocksDB works

morelisp2y ago

It's not using hashes.

zokier2y ago

I don't know anything about rocksdb, but this approach on surface level seems like it could be very slow? Wouldn't it be more efficient to encode the semver in a format more suitable to sorting

adamretterOP2y ago

hdhfjkrkrme2y ago

Sure, the old performance/productivity tradeoff.

This quickly solves the problem then you can iterate for performance.

morelisp2y ago

Using RocksDB here seems fairly insane unless you need to keep (at least) several billion constantly-updating versions sorted. Otherwise you can just use SortedMap and regular Java comparators.

curtisblaine2y ago

They might just want cheap disk persistence. I'm not a Java developer, but if SortedMaps are a memory-only data structure, persisting them reliably doesn't look an easy feat.

morelisp2y ago

RocksDB is disk persistence but it sure ain't (for this scale) cheap.

Persisting just about anything in Java is easier than persisting it in Java in RocksDB.

1 more reply

gnulinux2y ago

> The technical primitive data structure here is a hashmap where the keys are sorted.

Why not a tree based map instead?

The_Colonel2y ago

HashMap and sorted keys sounds like a contradiction. I think they just use "HashMap" as a generic term for "Map" and it's actually a tree based map.

morelisp2y ago

It is an LSMT, but I cannot imagine why they would need one here.

samsquire2y ago

I am curious, I recently wrote a naive hashmap for C. I am curious about iterating in insert and sort order.

Is it possible for a hash function to maintain a sort relationship to it's input and output?

blyzz2y ago

Supporting insertion order is straightforward (but has some trade-offs) - you store the values in a backing array or linked list, and the hash table array stores pointers to the values.

You could do something similar with a sorted data structure backing the hashmap to get sorted order (a b-tree or something similar).

hdhfjkrkrme2y ago

If you iterate a python dictionary it will return the keys in insert order.

For sort order you need to sort separately.

j / k navigate · click thread line to collapse