LRU-C: Parallelizing Database I/Os for Flash SSDs
- Bohyun Lee, Mijin An, and Sangwon Lee, "LRU-C: Parallelizing Database I/Os for Flash SSDs", VLDB'23 (to appear)
The conventional database buffer managers have two inherent sources of I/O serialization: read stall and mutex conflict. The serialized I/O makes storage and CPU under-utilized, limiting transaction throughput and latency. Such harm stands out on flash SSDs with asymmetric read-write speed and abundant I/O parallelism.
To make database I/Os parallel and thus leverage the parallelism in flash SSDs, we propose a novel approach to database buffering, the LRU-C method. It introduces the LRU-C pointer that points to the least-recently-used-clean page in the LRU list. Upon a page miss, LRU-C selects the current LRU-clean page as a victim and adjusts the pointer to the next LRU-clean one in the LRU list. This way, LRU-C can avoid the I/O serialization of read stalls. The LRU-C pointer enables two further optimizations for higher I/O throughput: dynamic-batch-write and parallel LRU-list manipulation. The former allows to flush more dirty pages at a time, while the latter does to mitigate two mutex-induced I/O serializations. Experiment result from running OLTP workloads using MySQL-based LRU-C prototype on flash SSDs shows that it improves transaction throughput over the vanilla MySQL and the state-of-the-art solution by 3x and 2x, respectively, and also cut the tail latency drastically. Though LRU-C might compromise the hit ratio slightly, its increased I/O throughput far offsets the reduced hit ratio.
The pdf file summarizes the main concept of LRU-C. I hope you can better understand our paper with this slide.
- Slide Link: Link
Modified parts in files are marked with For LRU-C with comments in the source code. Modifications are made only in the following files in LRU-C/storage/innobase/buf and LRU-C/storage/innobase/include.
buf0lru.ccbuf0flu.ccbuf0buf.ccbuf0lru.hbuf0buf.h
- Download the LRU-C source code and unzip the file.
$ wget https://github.com/LeeBohyun/LRU-C/archive/refs/heads/main.zip
$ unzip main.zip- Build and initialize MySQL. Conider
LRU-C-mainasmysql-5.6.26from the installation guide link.
- Installation guide link: Installation Guide
- Run TPC-C and check out the result!