Optimizing Database Algorithms for Random-Access Block Devices

Abstract

The past decade has seen wide availability of solid-state drives (SSDs) in settings ranging from personal computing to enterprise storage. Their success over the hard disks is driven by performance considerations and cost savings. Besides SSDs based on flash memory, there have been ongoing efforts in developing other non-volatile memory technologies such as phase-change memory and MRAM. All these technologies enable what we refer to as random-access block devices. Unlike hard disks, these devices have fast random accesses; on the other hand, their writes are more expensive than their reads. In this work, we study how to optimize database and storage algorithms for the I/O characteristics of random-access block devices. Specifically, we tackle the following three problems.The first one is about permuting data out-of-core. While external merge sort is popular for implementing permutation on hard disks, it carries unnecessary overhead in storing and comparing keys. We propose more efficient algorithms for a useful class of permutations called Address-Digit Permutations on random-access block devices.The second problem is concurrency control for indexes on SSDs. Various indexes have been proposed for these devices, but to make such indexes practical, we must address the issue of concurrency control. We propose a novel indexing and concurrency control scheme which allows concurrent accesses during ongoing index reorganizations, and does so with minimal memory and block-level locking.The third problem concerns log-structured merge, a popular indexing technique well-suited to random-access block devices. We show how an intelligent partial merge policy, combined with a block-preserving merge procedure, can ­significantly lower write traffic while preserving other advantages of log-structured merge.