Very interesting, though a shame (to me) that it's Go, as I'm actually after a C++ KV store that ideally isn't RocksDB (I want something that's much easier to embed and RocksDB has a bunch of dependencies).
Have you tried benchmarking on baremetal though? I've been shopping around for a KV store and came across this benchmark: http://www.lmdb.tech/bench/ondisk/#sec7
Interestingly, for 768-byte values, LevelDB is the clear winner when it comes to read scaling on a VM yet on bare metal it's drastically outperformed by LMDB.
they say that when you have a hammer, everything looks like a nail. bearing in mind that I definitely have a go-hammer, but depending on the library you're dealing with, turning a go library into a .a or .so via cgo is pretty painless. it usually requires just a very small shim.
anyway, not strictly an answer to the question you asked, but b/c I've spent so much time doing cgo I figured I'd mention it as a possibility.
Badger should outperform LevelDB easily, particularly as the value sizes increase. The design and our benchmarks are both consistent with this.
I haven't had a chance to benchmark on baremetal. We chose to run the benchmarks on Amazon, because that's what most people would use to run the applications/DBs built on top of the KV store. This ensures that the hardware specs used for benchmarking are easily available to everyone.
On bare metal you'll be hard pressed to beat LMDB.
It's really about as simple, and as bare bones as you can make a traditional KV storage while still preserving MVCC, transactions, and maintaining ACID.
Furthermore it's design is prefectly suited to exploit Optane/FRAM non-volatile RAM devices that appear to becoming.
Apparently the way LMDB does I/O is exercising slower (more complex?) code paths in the virtualization implementation code compared to LevelDB, and virtualization overhead is significant in these benchmarks (actually slows down execution several times).
It depends on the hypervisor. XEN/AWS uses and older slower path for memory allocation then the modern KVM/Intel-EPT allows.
Every `malloc` under XEN (that can't be satisfied with unused memory already mapped into that processes userspace) requires a hyper call.
This VMM approach was _largely_ depreciated about 6 years ago when Intel created page table bits that let the bare metal OS give the VM a _range_ of memory it can virtually re-map, but AWS hasn't adopted this.
(The names contain Cabinet but they aren't related to city/national governments.)
I once played around with Kyoto in Lua but can't say anything good or bad about it's performance, scalability, etc. They have documentation and some presentation slides in English on their website and provide quite a lot of language bindings if you are interested.
What do people typically store in KV stores that do not have a database built on top of them? Terabytes of what? Accessed by what kind of application logic?
It's often a storage layer for some more complex thing - e.g. riak had a leveldb "backend". Facebook uses rocksdb similarly, plus there's the myrocks storage engine for using rocksdb with mysql on top.
One use case is maintaining node-level state for stream processing systems. This gives you a scaleable way to do stateful computations (such as aggregations) without the complexity and performance cost of hitting a remote data store. Such support is built into Samza using RocksDB. [1]
I currently use leveldb in my project as a way to handle an intermediate data processing step that chews on much-larger-than-RAM datasets. And I didn't feel like this processing step warranted the overhead of a full-blown database sitting on another box, or even the same box. Works quite nicely thus far.
I considered it, but for what I was doing, a K/V store that also has fast key prefix lookup was perfect. Plus, yeah, what I'm doing is currently super write-heavy.
Link to WiscKey paper, discussion of tradeoffs made - awesome. DB vendors, take a page out of their book please.
RocksDB does go to some lengths to reduce amplification on SSDs, though it seems this design is taking that into consideration from the very beginning.
Go is slow when doing a lot of random lookups. Each lookup into disk is a blocking one, which causes a Goroutine to block the OS thread. A new OS thread then has gets created after a time delay to schedule goroutines. This happens over and over again.
> Each lookup into disk is a blocking one, which causes a Goroutine to block the OS thread.
Can you have multiple OS threads created at the beginning so whenever an OS thread is blocked the OS scheduler simply schedules another OS thread? That's how most databases handle blocking disk IO, right?
Doing blocking disk IO has to be a common task. How do other golang applications/databases handle this issue?
> so whenever an OS thread is blocked the OS scheduler simply schedules another OS thread
Go does that even now. If a thread is blocked, it would create another thread, but it does it with a small delay. I saw a visible increase in IOPS when starting Go with more OS threads (using GoMAXPROCS), because Go doesn't need to wait before having access to these threads, but on a longer running job with enough initiation for OS threads, that benefit would be nullified.
Most LSM based KV stores are designed to avoid random lookups -- and Go DBs tend to use RocksDB -- so it probably hasn't been such a big issue for them.
>Keep it simple, stupid. No support for transactions, versioning or snapshots -- anything that can be done outside of the store should be done outside.
Not sure how I feel about that philosophy. Transaction support is extremely complex and should be left to a storage engine if ever possible.
What is the benefit of this over something like Berkeley DB?
The reason we want to KISS is to ensure a solid, robust, and performant layer of storage, that other projects can use to build their transactional versions, etc.
One can take Badger and build a transactional layer above it, and it would still be below the application layer.
Why would one want to though? (edit) as in why choose this and invest hundreds (thousands?) of development hours doing so. What ROI would support this?
> The reason we want to KISS is to ensure a solid, robust, and performant layer of storage, that other projects can use to build their transactional versions, etc.
Then comparing it to Rocks DB is unfair (infact title of this post is misleading). Stuff like transactions and MVCC is way complicated than it sounds.
Because duplicate counting is not per URL, and and the announcement blog post (which has a link to the github, and the same kind of information as is on there) already was on HN.
34 comments
[ 3.1 ms ] story [ 69.6 ms ] threadHave you tried benchmarking on baremetal though? I've been shopping around for a KV store and came across this benchmark: http://www.lmdb.tech/bench/ondisk/#sec7
Interestingly, for 768-byte values, LevelDB is the clear winner when it comes to read scaling on a VM yet on bare metal it's drastically outperformed by LMDB.
anyway, not strictly an answer to the question you asked, but b/c I've spent so much time doing cgo I figured I'd mention it as a possibility.
I haven't had a chance to benchmark on baremetal. We chose to run the benchmarks on Amazon, because that's what most people would use to run the applications/DBs built on top of the KV store. This ensures that the hardware specs used for benchmarking are easily available to everyone.
It's really about as simple, and as bare bones as you can make a traditional KV storage while still preserving MVCC, transactions, and maintaining ACID.
Furthermore it's design is prefectly suited to exploit Optane/FRAM non-volatile RAM devices that appear to becoming.
LMDB does mmap while LevelDB does plain file I/O.
Every `malloc` under XEN (that can't be satisfied with unused memory already mapped into that processes userspace) requires a hyper call.
This VMM approach was _largely_ depreciated about 6 years ago when Intel created page table bits that let the bare metal OS give the VM a _range_ of memory it can virtually re-map, but AWS hasn't adopted this.
http://fallabs.com/kyotocabinet/
http://fallabs.com/tokyocabinet/
https://en.wikipedia.org/wiki/Tokyo_Cabinet_and_Kyoto_Cabine...
(The names contain Cabinet but they aren't related to city/national governments.)
I once played around with Kyoto in Lua but can't say anything good or bad about it's performance, scalability, etc. They have documentation and some presentation slides in English on their website and provide quite a lot of language bindings if you are interested.
[1] http://samza.apache.org/learn/documentation/latest/container...
[1] https://news.ycombinator.com/item?id=14335931
RocksDB does go to some lengths to reduce amplification on SSDs, though it seems this design is taking that into consideration from the very beginning.
You can follow the discussion here: http://bit.ly/2tb19eX
Can you have multiple OS threads created at the beginning so whenever an OS thread is blocked the OS scheduler simply schedules another OS thread? That's how most databases handle blocking disk IO, right?
Doing blocking disk IO has to be a common task. How do other golang applications/databases handle this issue?
Go does that even now. If a thread is blocked, it would create another thread, but it does it with a small delay. I saw a visible increase in IOPS when starting Go with more OS threads (using GoMAXPROCS), because Go doesn't need to wait before having access to these threads, but on a longer running job with enough initiation for OS threads, that benefit would be nullified.
Most LSM based KV stores are designed to avoid random lookups -- and Go DBs tend to use RocksDB -- so it probably hasn't been such a big issue for them.
Not sure how I feel about that philosophy. Transaction support is extremely complex and should be left to a storage engine if ever possible.
What is the benefit of this over something like Berkeley DB?
One can take Badger and build a transactional layer above it, and it would still be below the application layer.
Transaction support comes with a set of performance compromises, and different companies may want to make different compromises.
Then comparing it to Rocks DB is unfair (infact title of this post is misleading). Stuff like transactions and MVCC is way complicated than it sounds.
TransactionDB* txn_db; Status s = TransactionDB::Open(options, path, &txn_db);
Transaction* txn = txn_db->BeginTransaction(write_options, txn_options); s = txn->Put(“key”, “value”); s = txn->Delete(“key2”); s = txn->Merge(“key3”, “value”); s = txn->Commit(); delete txn;