This paper presents a scalable page cache called ScaleCache for improving SSD scalability. Specifically, we first propose a concurrent data structure of page cache based on XArray (ccXArray) to enable access and update the page cache concurrently. Second, we introduce a direct page flush (dflush) which directly flushes pages to storage devices in a parallel and opportunistic manner. We implement ScaleCache with two techniques in the Linux kernel and evaluate it on a 64-core machine with eight NVMe SSDs. Our evaluations show that ScaleCache improves the performance of Linux file systems by up to 6.81× and 4.50× compared with the existing scheme and scalable scheme for multiple SSDs, respectively.
Binary Search Tree is the data structure that has fast search speed and easy addition, removal of elements. Due to these advantages, binary search tree (BST) is one of the frequently used data structures of these days. However, most binary search tree schemes use locking technique to support multiple access of multiple threads for synchronization. Unfortunately, this locking techniques significantly reduce the performance of BST. Locking techniques block or spin the threads that has not obtained the lock until the thread that has obtained the lock completes its job. Thus, to improve the performance of BST, efficient concurrent programming technique should be applied, such as lock-free technique. In this paper, we conduct a comparison of existing lock-free/non-blocking BST methods. We analyze operations and evaluate the strengths and weaknesses of each schemes.