Badger: Support Transactions

[manishrjain]

Reading the Critique of Snapshot Isolation paper by Yabandeh, I realize that adding transactions (via write snapshot isolation) on top of Badger would be pretty simple. We already do all our writes serially. So, all of our RW transactions, if run from the one serial loop, would not require us to do anything on top of what we're already doing. This would fit really nicely, in fact.

Badger's write throughput is already much better than other KV stores, so even if this causes a slight degradation in write performance, this would be a big win for the users. There won't be much degradation in read performance.

More thought is required to see how other components would be impacted. And if we need to have start and commit timestamps to coordinate this. To make a decision on this, we need to put together a design doc.

Why:

• Dgraph itself would need this to support transactions.
• Many use cases need transactions. Some projects wouldn't even consider using Badger unless it does transactions.
• Bleve integration requires transactions as well. Issue: https://github.com/blevesearch/bleve/issues/591

TODO:

• [x] Put together a design doc to see how this would fit into Badger.

[manishrjain]

An initial draft of design doc:
https://discuss.dgraph.io/t/supporting-transactions-in-badger/1766

[manishrjain]

Need to consider if there's a demand for transactions in Badger and/or if Dgraph needs this.

[joeblew99]

Huge +1 !

I use boltdb and also bleve and pilosa.

Bleve does the unstructured data indexing
Pilosa does the structured data indexing.

Having transactions would be huge.
When a write comes in I need to commit to the badger dB and then get bleve and pilosa to also take a data changeset.

At the moment I use an event sourcing pattern to ensure all indexing systems also finish the indexing even if they die half way.
Using Vader for the event sourcing dB across all 3 would actually allow me huge code reduction in complexity.

Thanks for this amazing project !

[bt]

Huge +1 from me too!

The Blevesearch ecosystem is a very major part of my application and transaction support is required to be able to integrate Badger support in.

Unfortunately, working with kvstores is way beyond my knowledge and henceforth, I have just been hoping that it will eventually be supported. :(

[manishrjain]

Work is underway to introduce MVCC and concurrent transactions in Badger. Txns support serializable snapshot isolation, to prevent write skews. This would be a major API change. A major chunk of coding is done, we're going to start testing it next week.

You can see the changes here:
https://github.com/dgraph-io/badger/compare/develop

[joeblew99]

Thank you !!

[manishrjain]

Badger txn support is in master: https://blog.dgraph.io/post/badger-txn/. Also ran some numbers, the write speed is really good.

[deepakjois]

Looks like this can be closed, @manishrjain ?

[manishrjain]

Yes, transactions are out and ready for prime time!

[pkieltyka]

@manishrjain great job on the most recent release, its great to see badger at such quality while also moving so quickly.

for some additional ideas for your roadmap, I asked the cockroachdb guys what they'd require to consider badger as a storage engine option and they listed some items here: https://github.com/cockroachdb/cockroach/issues/17929#issuecomment-335973836

[manishrjain]

Thanks, @pkieltyka for the kind words. Cockroach folks have been pretty clear that they are not interested in switching away from RocksDB. So take my response mostly for completeness, for sake of other DBs who might be considering using Badger.

Backward iteration on iterators: Yes, since the beginning.
Prefix bloom filters: Not required, due to the smaller size of Badger LSM tree. We do have and use bloom filters for keys though.

Custom key comparators: No one asked for this.
Snapshots: Read-only transactions can give a consistent snapshot view of the entire DB.
Range deletion tombstones: Not sure if this is relevant to Badger. One can just iterate over keys (key-only iteration) really fast and mark them all as deleted in a single txn (batch write).

Direct ingestion of SSTables: Not possible in a live running DB. But, I do want to have a way to ingest sorted keys at an insanely fast rate by directly building and writing out SSTables at the bottom most level (L7), for a new Badger instance. This would be useful to rebuild Badger from a backup. That'd be the closest to "ingesting SSTables", because it would avoid compaction costs, which is the limiting factor in terms of write throughput.