Skip to content

The world's first wait-free KV store with generic durable linearizable transactions

License

Notifications You must be signed in to change notification settings

pramalhe/RedoDB

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

8 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

RedoDB, a wait-free KV store for Persistent Memory

RedoOpt PTM is meant to make it easy to implement wait-free data structures in persistent memory (sometimes named non-volatile main memory). It is based on the paper "Persistent Memory and the Rise of Universal Constructions" by Correia, Felber and Ramalhete https://github.com/pramalhe/RedoDB/blob/master/RedoDB-2020.pdf

We used RedoOpt PTM to implement a KV store, RedoDB, that has an API similar to LevelDB/RocksDB.

Characteristics of RedoDB:

  • RedoDB is the world's first wait-free KV store;
  • Supports generic transactions passed on a lambda. These transactions can be over user provided (annotated) data types, or multiple operations in the KV store, or multiple operations over multiple KV store instances;
  • Both write and read-only operations have snapshots to work on. This means queries are non-abortable, similar to Multi-Version Concurrency Control (MVCC);
  • RedoDB does not use MVCC, it has its own novel concurrency control based on multiple replicas;
  • Can consume large amounts of persistent memory, but then again, so can MVCC;
  • This implementation is not production ready. This is research code, meant as a proof of concept that wait-free databases are possible and efficient;
  • Transactions in RedoDB are durable linearizable (serializable isolation);
  • Write transactions don't scale, but read-only transactions scale well, irrespective of how many write transactions exist;
  • The durability mechanism in RedoDB is not undo-log, nor redo-log, nor copy-on-write, it is multi-instance based (closer to Romulus);

Releases

No releases published

Packages

No packages published

Languages