More Like this

1. Obladi: Oblivious Serializable Transactions in the Cloud

   Crooks, Natacha; Burke, Matthew Burke; Cecchetti, Ethan; Harel, Sitar; Agarwal, Rachit; Alvisi, Lorenzo (October 2018, Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI ’18))

   This paper presents the design and implementation of Obladi, the first system to provide ACID transactions while also hiding access patterns. Obladi uses as its building block oblivious RAM, but turns the demands of supporting transac- tions into a performance opportunity. By executing transac- tions within epochs and delaying commit decisions until an epoch ends, Obladi reduces the amortized bandwidth costs of oblivious storage and increases overall system through- put. These performance gains, combined with new oblivious mechanisms for concurrency control and recovery, allow Obladi to execute OLTP workloads with reasonable through- put: it comes within 5× to 12× of a non-oblivious baseline on the TPC-C, SmallBank, and FreeHealth applications. Latency overheads, however, are higher (70× on TPC-C). 

   more » « less
2. Handling Highly Contended OLTP Workloads Using Fast Dynamic Partitioning

   https://doi.org/10.1145/3318464.3389764  

   Prasaad, Guna; Cheung, Alvin; Suciu, Dan (May 2020, SIGMOD)

   Research on transaction processing has made significant progress towards improving performance of main memory multicore OLTP systems under low contention. However, these systems struggle on workloads with lots of conflicts. Partitioned databases (and variants) perform well on high contention workloads that are statically partitionable, but time-varying workloads often make them impractical. To- wards addressing this, we propose Strife—a novel transac- tion processing scheme that clusters transactions together dynamically and executes most of them without any con- currency control. Strife executes transactions in batches, where each batch is partitioned into disjoint clusters with- out any cross-cluster conflicts and a small set of residuals. The clusters are then executed in parallel with no concur- rency control, followed by residuals separately executed with concurrency control. Strife uses a fast dynamic clustering al- gorithm that exploits a combination of random sampling and concurrent union-find data structure to partition the batch online, before executing it. Strife outperforms lock-based and optimistic protocols by up to 2× on high contention workloads. While Strife incurs about 50% overhead relative to partitioned systems in the statically partitionable case, it performs 2× better when such static partitioning is not possible and adapts to dynamically varying workloads. 

   more » « less
3. Verifying vMVCC, a high-performance transaction library using multi-version concurrency control

   Chang, Yun-Sheng; Jung, Ralf; Sharma, Upamanyu; Tassarotti, Joseph; Kaashoek, M. Frans; Zeldovich, Nickolai (July 2023, Proceedings of the 17th USENIX Symposium on Operating Systems Design and Implementation (OSDI))

   Multi-version concurrency control (MVCC) is a widely used, sophisticated approach for handling concurrent transactions. vMVCC is the first MVCC-based transaction library that comes with a machine-checked proof of correctness, providing clients with a guarantee that it will correctly handle all transactions despite a complicated design and implementation that might otherwise be error-prone. vMVCC is implemented in Go, stores data in memory, and uses several optimizations, such as RDTSC-based timestamps, to achieve high performance (25–96% the throughput of Silo, a state-of-the-art in-memory database, for YCSB and TPC-C workloads). Formally specifying and verifying vMVCC required adopting advanced proof techniques, such as logical atomicity and prophecy variables, owing to the fact that MVCC transactions can linearize at timestamp generation prior to transaction execution. 

   more » « less
4. MadFS: Per-File Virtualization for Userspace Persistent Memory Filesystems

   Zhong, Shawn; Ye, Chenhao; Hu, Guanzhou; Qu, Suyan; Arpaci-Dusseau, Andrea; Arpaci-Dusseau, Remzi; Swift, Michael (February 2023, Proceedings of 21st USENIX Conference on File and Storage Technologies (FAST ’23))

   Persistent memory (PM) can be accessed directly from userspace without kernel involvement, but most PM filesystems still perform metadata operations in the kernel for secuity and rely on the kernel for cross-process synchronization. We present per-file virtualization, where a virtualization layer implements a complete set of file functionalities, including metadata management, crash consistency, and concurrency control, in userspace. We observe that not all file metadata need to be maintained by the kernel and propose embedding insensitive metadata into the file for userspace management. For crash consistency, copy-on-write (CoW) benefits from the embedding of the block mapping since the mapping can be efficiently updated without kernel involvement. For cross-process synchronization, we introduce lockfree optimistic concurrency control (OCC) at user level, which tolerates process crashes and provides better scalability. Based on per-file virtualization, we implement MadFS, a library PM filesystem that maintains the embedded metadata as a compact log. Experimental results show that on concurrent workloads, MadFS achieves up to 3.6× the throughput of ext4-DAX. For real-world applications, MadFS provides up to 48% speedup for YCSB on LevelDB and 85% for TPC-C on SQLite compared to NOVA. 

   more » « less
5. ScaleDB: A Scalable, Asynchronous In-Memory Database

   Mehdi, Syed Akbar; Hwang, Deukyeon; Peter, Simon; Alvisi, Lorenzo (July 2023, Proceedings of the 17th USENIX Symposium on Operating Systems Design and Implementation)

   ScaleDB is a serializable in-memory transactional database that achieves excellent scalability on multi-core machines by asynchronously updating range indexes. We find that asynchronous range index updates can significantly improve database scalability by applying updates in batches, reducing contention on critical sections. To avoid stale reads, ScaleDB uses small hash indexlets to hold delayed updates. We use in- dexlets to design ACC, an asynchronous concurrency control protocol providing serializability. With ACC, it is possible to delay range index updates without adverse performance effects on transaction execution in the common case. ACC delivers scalable serializable isolation for transactions, with high throughput and low abort rate. Evaluation on a dual- socket server with 36 cores shows that ScaleDB achieves 9.5× better query throughput than Peloton on the YCSB bench- mark and 1.8× better transaction throughput than Cicada on the TPC-C benchmark. 

   more » « less