Support for Distributed Transactions with Anti-Caching in Main-Memory
Distributed Databases

Atreyee Maiti
18-845, Internet Services, Spring 2014

Main-memory databases have emerged as the right choice for Online
Transaction Processing (OLTP) workloads. This is because traditional
disk-based databases introduce too much overhead for datasets that
could simply be memoryresident (which is the common case with OLTP
workloads), owing to their locking and recovery mechanisms. However,
main-memory databases are restricted by the available main memory. The
complete dataset needs to fit in-memory, even though the transactions
may not be using all of the data at the same time. To deal with this
problem, techniques like anti-caching and OS paging have emerged. The
central idea behind these techniques is to identify cold data
in-memory and push it out to a secondary storage device like a
hard-disk or solid state disk, to make space for new data in-memory.
Whenever a transaction attempts to access a tuple that was evicted out
to disk, it is read back and merged with the inmemory table and the
transaction proceeds to completion.  This makes main-memory databases
optimal for both OLTP datasets that fit in-memory as well as those
that do not.

As part of this project, we extend anti-caching support to distributed
transactions. This enables distributed transactions to proceed to
completion even if the data needed for them is not in-memory for a few
partitions involved in the transaction. We evaluate this
implementation in H-Store, a main-memory distributed database. The
results indicate that we are able to complete distributed transactions
successfully.