News for hackers. Stuff that matters.

krka

Re:Sparkey is a simple constant key/value storage library on Sunday January 14, 2024 @05:35AM (#38989228)
Now when I'm at an actual computer, I see that it was implemented, at least in the Java version. Removing that made for a 30% speed increase: https://github.com/spotify/sparkey-java/pull/65
Re:Sparkey is a simple constant key/value storage library on Saturday January 06, 2024 @04:25AM (#38889904)
True, if the lookup actually implemented this, it would be more divisions. This might partly be why it did not get implemented at all. With a sparse index (25% empty capacity) we should quickly run into empty slots anyway in most cases, and if we mostly expect hits the check would not be useful anyway.

For deletions, neighbour entries would bubble up into their correct slots to preserve that property.

Re:Sparkey is a simple constant key/value storage library on Friday January 05, 2024 @09:44AM (#38879560)
I haven't worked on this code in a long time but I will try to answer based on what I remember. (Also on phone without easy access to the code)

The idea is that all entries have a natural ideal position in the table and the displacement is how far away from it it is placed in practice. If two entries are competing for the same slot, the logic will prefer displacements of 1,2 over 0,3 so if you observe an entry with displacement 5 after already having visited 5 entries you can already conclude you wont find what you are looking for. However, I am not sure this quick exit is actually implemented.

I think the index size is not a power of two, but that was something I considered but it would greatly affect size. At the time of building it, spinning disks were still common and optimizing for space compactness and minimizing page faults/iops were more important. I think it would be at most one division per lookup and the the memory/disk reads would dominate the work anyway.

Deletions are implemented as a special tombstone entry in the log file which then causes a removal from the index slot as well. There is also a naive implementation of a compaction flow (go through log, build index, regenerate new log by looking at the index, then rewrite index)

Re:Sparkey – Key/value storage by Spotify on Wednesday September 04, 2013 @11:32AM (#6328235)
Could be due to a bug related to reading uninitialized data on the stack. That could lead to using the wrong number of bits for the hash, causing an unnecessarily high number of hash collisions, which makes it more expensive due to false positives that needs to be verified. I think it's fixed in the latest master, and the benchmark code now prints the number of collisions per test case, which could be useful debug data.

Also, I think it would be more interesting to see a comparison with lmdb using random writes instead of sequential.

As for the cpu time measurement, the wallclock is very inprecise, so it could be some small quantum larger than cpu time, but it should never be more than the system specific wall clock quantum.

Re:Sparkey – Key/value storage by Spotify on Wednesday September 04, 2013 @10:23AM (#6327746)
Thanks, that's interesting data!

I am not sure why you changed the key format to "key_%09d" - is that an optimization for lmdb, to make sure the insertion order is the same as the internal tree ordering? If so, why is that needed for the benchmark?

I noticed that the wall time and cpu time for the sparkey 100M benchmarks were a bit disjoint, it would seem that your OS was evicting many pages or was stalling on disk writes. The Sparkey files were slightly larger than 4 GB while lmdb was slightly smaller, but I am not sure that really explains it on an 8 GB machine.

I am not sure I agree about the non-linear creation time difference, the benchmarks indicate that both sparkey and lmdb are non-linear. The sparkey creation throughput went from 1206357.25 to 1109604.25 (-8.0%) while lmdb's went from 2137678.50 to 2033329.88 (-4.8%)

Regarding the lookup performance "dropping off a cliff", I think that is related to the large difference in wall time vs cpu time, which indicates a lot of page cache misses.

lmdb seems really interesting for large data sets, but I think it's optimized for different use cases. I'd be curious to see how it behaves with more randomized keys and insertion order. I didn't think of doing that in the benchmark since sparkey isn't really affected by it, but it makes sense for when benchmarking a b-tree implementation.

Sparkey is optimized for our use case where we mlock the entire index file to guarantee cache hits, and possibly also mlock the log file, depending on how large it is.

The way you append stuff to sparkey (first fill up a log, then build a hash table as a finalization) is really useful when you need to use lots of memory while building and can't affort random seek file operations, and in the end when most of the work is done and your memory is free again, finalize the database. Of course, you could do the same thing with lmdb, first writing a log and then converting that into a lmdb file.

Thanks for taking the time to adapt the benchmark code to lmdb, it's been very interesting.

Re:Sparkey – Key/value storage by Spotify on Wednesday September 04, 2013 @07:32AM (#6326769)
Well, some DB's "load" the value in some way before giving it to the user, so that time is implicitly measured for those types of DB's but not for others, so I don't think it's a particularly fair comparison. I think Tokyo Cabinet gives you a pointer to newly allocated memory, at least for compressed data (but I am not completely sure about this). Like LMDB, Sparkey also does no processing of the value for uncompressed data, but for compressed data some decompression needs to take place in the iterator buffer (I guess that's equivalent to your cursor object). Even worse, if this is done lazily upon value retrieval, the cost is completely hidden in the benchmark.

In any case, I think the easiest way to get a fair benchmark is to at least iterate over the value, possibly also compare it. If that time turns out to be significant (perhaps even dominant) compared to the actual lookup time, then further optimization of the actual storage layer is pretty meaningless.

Re:Sparkey – Key/value storage by Spotify on Wednesday September 04, 2013 @02:47AM (#6326013)
Yes, this post was handwaving, and I tried to make that clear ("preliminary", "extremely biased").

On monday I added some slightly more proper benchmark code, you can find it on https://github.com/spotify/sparkey/blob/master/src/bench.c

I didn't add the level-db code to this benchmark however, since I 1) didn't want to manage that dependency 2) didn't know how to write optimized code for usage of it.

I'm using very small records, a couple of bytes of key and value. The insert order is strictly increasing (key_0, key_1, ...), though that doesn't really matter for sparkey since it uses a hash for lookup instead of ordered lists or trees.

As for the symas mdb microbench, I only looked at it briefly but it seems like it's not actually reading the value it's fetching, only doing the lookup of where it actually is, is that correct?

"MDB's zero-memcpy reads mean its read rate is essentially independent of the size of the data items being fetched; it is only affected by the total number of keys in the database."

Doing a lookup and not using the values seems like a very unrealistic usecase.

Here's the part of the benchmark I'm referring to: for (int i = 0; i < reads_; i++) { const int k = rand_.Next() % reads_; key.mv_size = snprintf(ckey, sizeof(ckey), "%016d", k); mdb_cursor_get(cursor, &key, &data, MDB_SET); FinishedSingleOp(); }

Re:Sparkey – Key/value storage by Spotify on Monday September 02, 2013 @03:31PM (#6316700)
I have now created a very simple benchmark suite to give you some rough performance numbers, and updated the README to include some sample numbers for one specific machine.
Re:Sparkey – Key/value storage by Spotify on Monday September 02, 2013 @02:08PM (#6316317)
Bam looks really interesting, definitely a lot simpler than Sparkey, and the basic principle is the same. I have been hesitant to use perfect hashing for Sparkey since I wasn't sure how well it holds up for really large data sets (close to a billion keys). Impressive to write it in less than 300 lines of clean code!
Re:Sparkey – Key/value storage by Spotify on Monday September 02, 2013 @10:48AM (#6315393)
Here are some preliminary performance benchmarks from my regular workstation (Intel(R) Core(TM) i5-2400 CPU @ 3.10GHz, 8 GB RAM): http://pastebin.com/7buZVgdu

The sparkey usage is fairly optimized, but I just randomly put something together for the level-db, so consider the results extremely biased.

Re:Sparkey – Key/value storage by Spotify on Monday September 02, 2013 @10:18AM (#6315251)
There are a bunch of comments related to performance data - the code is available so nothing is stopping anyone from making an unbiased comparison. :)

That said, I intend to publish some sort of performance comparison code / results. The downside with me doing it is that: 1) I know the sparkey code much better than I know level-db or any other solution, so the tuning parameters will probably be suboptimal for the other solutions. 2) I will only focus on our specific usecase (write large bulks, do lots of random reads), which may seem a bit unfair to the most general solutions.

Re:Sparkey – Key/value storage by Spotify on Monday September 02, 2013 @10:14AM (#6315233)
Right, this is actually the first commit - it's just that the history was squashed before publish - we had to remove sensitive Spotify specific things in it, and it seemed easiest to just do a big squash.