Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Siberite: A Simple LevelDB-Backed Message Queue in Go

github.com

Post reply on HN
Print view View original

31–37 of 37 posts

Re: Siberite: A Simple LevelDB-Backed Message Queue in Go

#31

Post by hyc_symas »

leif wrote: post #30
hyc_symas wrote: post #28

Earlier quoted context omitted.

A queue is the correct pattern for a queue. A tree, of any form, offers no advantage. The InfluxDB experience is definitely illuminating. Their problems with LMDB were mainly due to misuse of the API. https://disqus.com/home/discussion/influxdb/benchmarking_lev... For batched sequential writes, there is no other DB anywhere near as fast as LMDB http://symas.com/mdb/microbench/ (Section E, Batched Writes) But even so…

> In that case all you've got is an in-memory queue that evaporates on a system crash. https://www.cs.berkeley.edu/~brewer/cs262/Aries.pdf > Remember that merge operations are O(N). Then remember that there are N of them to do. O(N^2) is a horrible algorithmic complexity. No. Mountains of actual math refute this. LSM-tree merges are O(N log N). This is an Actual Fact. Read more, kids.

Ah yes, you're absolutely right. O(N log N) because there are log N chunks to be merged.

O(N log N) is still untenable in the long run, nobody has exponentially growing compute resources.

Re: Siberite: A Simple LevelDB-Backed Message Queue in Go

#32

Post by databass »

hyc_symas wrote: post #31
leif wrote: post #30

Earlier quoted context omitted.

> In that case all you've got is an in-memory queue that evaporates on a system crash. https://www.cs.berkeley.edu/~brewer/cs262/Aries.pdf > Remember that merge operations are O(N). Then remember that there are N of them to do. O(N^2) is a horrible algorithmic complexity. No. Mountains of actual math refute this. LSM-tree merges are O(N log N). This is an Actual Fact. Read more, kids.

Ah yes, you're absolutely right. O(N log N) because there are log N chunks to be merged. O(N log N) is still untenable in the long run, nobody has exponentially growing compute resources.

May I also mention that N log N is the total cost of compaction for a DB of size N. You don't perform a compaction on every single write. Amortised per write the cost is more like N log(N)/N == log(N).

Also, N log(N) is nowhere near exponential. O(2^N) would be exponential, and that's not what you have here.

Re: Siberite: A Simple LevelDB-Backed Message Queue in Go

#33

Post by hyc_symas »

databass wrote: post #32
hyc_symas wrote: post #31

Earlier quoted context omitted.

Ah yes, you're absolutely right. O(N log N) because there are log N chunks to be merged. O(N log N) is still untenable in the long run, nobody has exponentially growing compute resources.

May I also mention that N log N is the total cost of compaction for a DB of size N. You don't perform a compaction on every single write. Amortised per write the cost is more like N log(N)/N == log(N). Also, N log(N) is nowhere near exponential. O(2^N) would be exponential, and that's not what you have here.

"Amortised per write" - now you're getting down into the constant factors, which Big-O disregards. But you can't ignore them in real implementations. First the actual writes have a 2x constant factor, since you're writing to a WAL in addition to the DB itself.

The original LSM paper claims that writes to Level 0 are free because that's all in-memory. But that's not really true; if you have a stream of incoming writes then everything that goes into Level 0 must eventually be pushed out to Level 1. Buffering doesn't make writes free, it only displaces their occurrence in time.

So you have a rolling merge every M writes. As far as Big-O goes, that's N log(N) / M == N log(N) because Big-O disregards constant factors!

In the context of an implementation like LevelDB, theory and reality diverge even further. Since it's chunking data into 2MB files and deleting them during each merge operation, and also writing a bunch of bookkeeping into Manifest files and other stuff, the number of actual I/Os is much higher. A lot of wasted activity in allocating and deallocating space - filesystem metadata overhead that's also not transactionally safe.

In LevelDB a single merge reads 26MB and writes 26MB at a time to push 2MB of data from a level L to level L+1. So now instead of a single merge op costing only N, it actually costs 13*N. Again, if you're only talking about Big-O complexity you sweep this under the rug. But in reality, this is a huge cost.

Re: Siberite: A Simple LevelDB-Backed Message Queue in Go

#34

Post by hyc_symas »

hyc_symas wrote: post #33
databass wrote: post #32

Earlier quoted context omitted.

May I also mention that N log N is the total cost of compaction for a DB of size N. You don't perform a compaction on every single write. Amortised per write the cost is more like N log(N)/N == log(N). Also, N log(N) is nowhere near exponential. O(2^N) would be exponential, and that's not what you have here.

"Amortised per write" - now you're getting down into the constant factors, which Big-O disregards. But you can't ignore them in real implementations. First the actual writes have a 2x constant factor, since you're writing to a WAL in addition to the DB itself. The original LSM paper claims that writes to Level 0 are free because that's all in-memory. But that's not really true; if you have a stream of incoming writes…

For reference - http://leveldb.googlecode.com/svn/trunk/doc/impl.html

Re: Siberite: A Simple LevelDB-Backed Message Queue in Go

#35

Post by hyc_symas »

hyc_symas wrote: post #33
databass wrote: post #32

Earlier quoted context omitted.

May I also mention that N log N is the total cost of compaction for a DB of size N. You don't perform a compaction on every single write. Amortised per write the cost is more like N log(N)/N == log(N). Also, N log(N) is nowhere near exponential. O(2^N) would be exponential, and that's not what you have here.

"Amortised per write" - now you're getting down into the constant factors, which Big-O disregards. But you can't ignore them in real implementations. First the actual writes have a 2x constant factor, since you're writing to a WAL in addition to the DB itself. The original LSM paper claims that writes to Level 0 are free because that's all in-memory. But that's not really true; if you have a stream of incoming writes…

Stated another way - assume you want to sustain a user workload writing 20MB/sec, and you don't do any throttling. Level 0 consists of 4 1MB files - it will fill in 1/5th of a second, and then compaction will reduce it by 1MB. After that it will be compacting continuously every 1/20th of a second. To sustain this workload for the 1st second will thus require 17 compactions to Level 1. Assuming an already populated Level 1 and worst-case key distribution that means in 1 second it will trigger compactions that read 238MB and write 238MB to store the incoming 20MB.

Level 1 is only 10MB, so if it was empty it would fill in the first 1/2 second. For the remaining 1/2 second it would trigger 5 more compactions to Level 2, reading 130MB and writing 130MB. If it started out full then this would be 260MB/260MB respectively.

So for a 20MB/sec input workload you would need a disk subsystem capable of sustaining 498MB/sec of reads concurrent with 498MB/sec of writes. And that's only for a small DB, only Level 0-2 present (smaller than 110MB), and excluding the actual cost of filesystem operations (create/delete/etc).

That's only for the 1st second of load. For every second after that, you're dumping from Level 0 to Level 1 at 280MB read and 280MB write/sec. And dumping from Level 1 to Level 2 at 260/260 as before. 540/540 - so a disk capable of 1080MB/sec I/O is needed to sustain a 20MB/sec workload. And this is supposed to be HDD-optimized? Write-optimized? O(N logN) - what a laugh.

Maybe LSMs in general can be more efficient than this. LevelDB is pretty horrible though.

Re: Siberite: A Simple LevelDB-Backed Message Queue in Go

#36

Post by Bogdanovich »

dave_ops wrote: post #29
Bogdanovich wrote: post #27

Earlier quoted context omitted.

There is no benefit in that except faster startup time. As a downside you'll get a lot head/tail db keys updates.

Fast start times are a valuable thing for a service component. Stick about 10GB of small entries in it (should be enough to create all the levels) and then see what happens. Also, you could reserve the persisted [H|T] for controlled shutdown scenarios. Basically anything that isn't complete system failure if you're properly trapping signals.

I added some more benchmarks including packing with 200M small 64 byte messages (20Gb) and consumption of that queue. There is no slowdown because of mass delete. https://github.com/bogdanovich/siberite/blob/master/docs/ben...

Re: Siberite: A Simple LevelDB-Backed Message Queue in Go

#37

Post by Bogdanovich »

hyc_symas wrote: post #35
hyc_symas wrote: post #33

Earlier quoted context omitted.

"Amortised per write" - now you're getting down into the constant factors, which Big-O disregards. But you can't ignore them in real implementations. First the actual writes have a 2x constant factor, since you're writing to a WAL in addition to the DB itself. The original LSM paper claims that writes to Level 0 are free because that's all in-memory. But that's not really true; if you have a stream of incoming writes…

Stated another way - assume you want to sustain a user workload writing 20MB/sec, and you don't do any throttling. Level 0 consists of 4 1MB files - it will fill in 1/5th of a second, and then compaction will reduce it by 1MB. After that it will be compacting continuously every 1/20th of a second. To sustain this workload for the 1st second will thus require 17 compactions to Level 1. Assuming an already populated Le…

It would only trigger compaction if sst tables have overlapping keys. And if you only write new items, goleveldb implementation would just create 3.7Mb sst tables by default without trying to merge them into bigger chunks (what's the point? they are all sorted and non-overlapping). When you have queue consumption workload it would start merging tombstones with sst tables and since tombstones are also in sorted order it would not pick up multiple sst tables at a time, and just either completely or partially remove stale sst files. I added some more benchmarks including queue packing with 200M messages of 64 byte size, and benchmarks of consumption of 200M messages. The speed is sustainable. https://github.com/bogdanovich/siberite/blob/master/docs/ben...
Post reply on HN