search

arthurprs / canopydb

Embedded Key-Value Storage Engine
84 stars 1 forks source link

Consider multi-writer transactions? #5

Open jeromegn opened 3 weeks ago

jeromegn commented 3 weeks ago

Having just implemented it in fjall, it's really not that bad in terms of added complexity.

Of course it depends on each database's snapshotting implementation and garbage collection, but I suspect it wouldn't be too hard to add in Canopy.

Most of the new code is in src/tx/oracle.rs and src/tx/conflict_manager.rs, roughly 300 lines of code.

It could be feature-flagged due to the added conflict error when committing.

arthurprs commented 3 weeks ago

I think it requires less code in an LSM because there's already machinery to merge the transaction memtables(s) with the rest of the snapshot. Adding such functionality to Canopy would be a significantly larger lift.

However, there might be a reasonable path to adding multi-writer transactions (w/o major code changes) by using page-level conflict detection (and/or locking).

arthurprs commented 3 weeks ago

Wait, that first paragraph is not really right...

It should be possible to have each concurrent write txn operate on mutable (COW) versions of the database (thus no merging machinery required). Then at commit time the write txn either replaces the database (if there was nothing commited in between) or replays the mutations if there aren't conflicts (there's already a WriteBatch component capturing those).

The page-level conflict resolution I mentioned is a variation of that. In that case, instead of replaying the mutations, it would just create a new MVCC snapshot with the updated pages. So pros and cons.