Let's Talk About Storage & Recovery Methods

1 . Let’s Talk About Storage & Recovery Methods for Non-Volatile Memory Database Systems Joy Arulraj Andrew Pavlo Subramanya R. Dulloor jarulraj@cs.cmu.edu pavlo@cs.cmu.edu subramanya.r.dulloor@intel.com Carnegie Mellon University Carnegie Mellon University Intel Labs ABSTRACT of power, the DBMS must write that data to a non-volatile device, The advent of non-volatile memory (NVM) will fundamentally such as a SSD or HDD. Such devices only support slow, bulk data change the dichotomy between memory and durable storage in transfers as blocks. Contrast this with volatile DRAM, where a database management systems (DBMSs). These new NVM devices DBMS can quickly read and write a single byte from these devices, are almost as fast as DRAM, but all writes to it are potentially but all data is lost once power is lost. persistent even after power loss. Existing DBMSs are unable to take In addition, there are inherent physical limitations that prevent full advantage of this technology because their internal architectures DRAM from scaling to capacities beyond today’s levels [46]. Using are predicated on the assumption that memory is volatile. With a large amount of DRAM also consumes a lot of energy since it NVM, many of the components of legacy DBMSs are unnecessary requires periodic refreshing to preserve data even if it is not actively and will degrade the performance of data intensive applications. used. Studies have shown that DRAM consumes about 40% of the To better understand these issues, we implemented three engines overall power consumed by a server [42]. in a modular DBMS testbed that are based on different storage Although flash-based SSDs have better storage capacities and use management architectures: (1) in-place updates, (2) copy-on-write less energy than DRAM, they have other issues that make them less updates, and (3) log-structured updates. We then present NVM- than ideal. For example, they are much slower than DRAM and only aware variants of these architectures that leverage the persistence support unwieldy block-based access methods. This means that if a and byte-addressability properties of NVM in their storage and transaction updates a single byte of data stored on an SSD, then the recovery methods. Our experimental evaluation on an NVM hard- DBMS must write the change out as a block (typically 4 KB). This ware emulator shows that these engines achieve up to 5.5× higher is problematic for OLTP applications that make many small changes throughput than their traditional counterparts while reducing the to the database because these devices only support a limited number amount of wear due to write operations by up to 2×. We also demon- of writes per address [66]. Shrinking SSDs to smaller sizes also strate that our NVM-aware recovery protocols allow these engines degrades their reliability and increases interference effects. Stop-gap to recover almost instantaneously after the DBMS restarts. solutions, such as battery-backed DRAM caches, help mitigate the performance difference but do not resolve these other problems [11]. Non-volatile memory (NVM)1 offers an intriguing blend of the 1. INTRODUCTION two storage mediums. NVM is a broad class of technologies, in- Changes in computer trends have given rise to new on-line trans- cluding phase-change memory [55], memristors [60], and STT- action processing (OLTP) applications that support a large number MRAM [26] that provide low latency reads and writes on the same of concurrent users and systems. What makes these modern appli- order of magnitude as DRAM, but with persistent writes and large cations unlike their predecessors is the scale in which they ingest storage capacity like a SSD [13]. Table 1 compares the characteris- information [41]. Database management systems (DBMSs) are the tics of NVM with other storage technologies. critical component of these applications because they are respon- It is unclear at this point, however, how to best leverage these new sible for ensuring transactions’ operations execute in the correct technologies in a DBMS. There are several aspects of NVM that order and that their changes are not lost after a crash. Optimizing make existing DBMS architectures inappropriate for them [14, 23]. the DBMS’s performance is important because it determines how For example, disk-oriented DBMSs (e.g., Oracle RDBMS, IBM quickly an application can take in new information and how quickly DB2, MySQL) are predicated on using block-oriented devices for it can use it to make new decisions. This performance is affected by durable storage that are slow at random access. As such, they main- how fast the system can read and write data from storage. tain an in-memory cache for blocks of tuples and try to maximize DBMSs have always dealt with the trade-off between volatile the amount of sequential reads and writes to storage. In the case and non-volatile storage devices. In order to retain data after a loss of memory-oriented DBMSs (e.g., VoltDB, MemSQL), they con- tain certain components to overcome the volatility of DRAM. Such Permission to make digital or hard copies of all or part of this work for personal or components may be unnecessary in a system with byte-addressable classroom use is granted without fee provided that copies are not made or distributed NVM with fast random access. for profit or commercial advantage and that copies bear this notice and the full cita- In this paper, we evaluate different storage and recovery methods tion on the first page. Copyrights for components of this work owned by others than for OLTP DBMSs from the ground-up, starting with an NVM-only ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or re- storage hierarchy. We implemented three storage engine architec- publish, to post on servers or to redistribute to lists, requires prior specific permission tures in a single DBMS: (1) in-place updates with logging, (2) copy- and/or a fee. Request permissions from permissions@acm.org. SIGMOD’15, May 31–June 4, 2015, Melbourne, Victoria, Australia. on-write updates without logging, and (3) log-structured updates. Copyright © 2015 ACM 978-1-4503-2758-9/15/05. . . $15.00. 1 NVM is also referred to as storage-class memory or persistent memory. http://dx.doi.org/10.1145/2723372.2749441 . 707 

2 . DRAM PCM RRAM MRAM SSD HDD means that they can be used for efficient architectures that are used Read latency 60 ns 50 ns 100 ns 20 ns 25 µs 10 ms in memory-oriented DBMSs [25]. But unlike DRAM, all writes Write latency 60 ns 150 ns 100 ns 20 ns 300 µs 10 ms to the NVM are potentially durable and therefore a DBMS can ac- Addressability Byte Byte Byte Byte Block Block cess the tuples directly in the NVM after a restart or crash without Volatile Yes No No No No No needing to reload the database first. Energy/ bit access 2 pJ 2 pJ 100 pJ 0.02 pJ 10 nJ 0.1 J Although the advantages of NVM are obvious, making full use of Endurance >1016 1010 108 1015 105 >1016 them in an OLTP DBMS is non-trivial. Previous work that compared Table 1: Comparison of emerging NVM technologies with other storage disk-oriented and memory-oriented DBMSs for NVM showed that technologies [15, 27, 54, 49]: phase-change memory (PCM) [55], memristors the two architectures achieve almost the same performance when (RRAM) [60], and STT-MRAM (MRAM) [26]. using NVM because of the overhead of logging [23]. This is because current DBMSs assume that memory is volatile, and thus their We then developed optimized variants for these approaches that architectures are predicated on making redundant copies of changes reduce the computational overhead, storage footprint, and wear-out on durable storage. Thus, we seek to understand the characteristics of NVM devices. For our evaluation, we use a hardware-based emu- of different storage and recovery methods from the ground-up. lator where the system only has NVM and volatile CPU-level caches (i.e., no DRAM). Our analysis shows that the NVM-optimized stor- 2.2 NVM Hardware Emulator age engines improve the DBMS’s throughput by a factor of 5.5× while reducing the number of writes to NVM in half. These re- NVM storage devices are currently prohibitively expensive and sults also suggest that NVM-optimized in-place updates is the ideal only support small capacities. For this reason, we use a NVM method as it has lowest overhead, causes minimal wear on the device, hardware emulator developed by Intel Labs [27] in this paper. The and allows the DBMS to restart almost instantaneously. emulator supports tunable read latencies and read/write bandwidths. Our work differs from previous studies because we evaluate a This enables us to evaluate multiple hardware profiles that are not DBMS using a single-tier storage hierarchy. Others have only em- specific to a particular NVM technology. Unlike NVM simulators, ployed NVM for logging [28, 30, 65] or used a two-level hierarchy like PCM-SIM [44], this emulator enables us to better understand the with DRAM and NVM [53]. We note that it is possible today to impact of cache evictions, prefetching, and speculative execution on replace DRAM with NV-DIMM [6], and run an NVM-only DBMS long-running workloads. The hardware emulator is based on a dual- unmodified on this storage hierarchy. This enables us to achieve per- socket Intel Xeon platform. Each CPU supports four DDR3 channels formance similar to that obtained on a DRAM and NVM storage hi- with two DIMMs per channel. Half of the memory channels on each erarchy, while avoiding the overhead of dealing with the volatility of processor are reserved for the emulated NVM while the rest are DRAM. Further, some NVM technologies, such as STT-RAM [26], used for regular memory. The emulator’s custom BIOS firmware are expected to deliver lower read and write latencies than DRAM. partitions the physical memory address space into separate address NVM-only DBMSs would be a good fit for these technologies. spaces for DRAM and emulated NVM. The remainder of this paper is organized as follows. We begin NVM technologies have higher read and write latency than DRAM. in Section 2 with a discussion of NVM and why it necessitates a We are able to emulate the latency for the NVM partition by using re-evaluation of DBMS storage architectures. Next, in Section 3 we custom CPU microcode. The microcode estimates the additional describe our DBMS testbed and its storage engines that we devel- cycles that the CPU would have to wait if DRAM is replaced by oped for this study. We then present in Section 4 our optimizations slower NVM and then stalls the CPU for those cycles. The accuracy for these engines that leverage NVM’s unique properties. We then of the latency emulation model was validated by comparing the present our experimental evaluation in Section 5. We conclude with performance of several applications on emulated NVM and slower a discussion of related work in Section 6. NUMA memory [27]. Since the CPU uses a write-back cache for NVM, the high latency of writes to NVM is not observed on every write but the sustainable write bandwidth of NVM is lower com- 2. BACKGROUND pared to DRAM [38]. The emulator allows us to control the write We now provide an overview of emerging NVM technologies and bandwidth by limiting the number of DDR operations performed discuss the hardware emulator platform that we use in this paper. per microsecond. It is currently not able to independently vary the read and write bandwidths as this throttling feature affects all DDR 2.1 Motivation operations. This limitation is not an issue for this evaluation as There are essentially two types of DBMS architectures: disk- OLTP workloads are not bandwidth intensive [65]. oriented and memory-oriented systems [23]. The former is exem- The emulator exposes two interfaces to access the NVM storage: plified by the first DBMSs, such as IBM’s System R [7], where Allocator Interface: The emulator uses a NVM-aware memory the system is predicated on the management of blocks of tuples on allocator that provides the POSIX malloc interface. Applications disk using an in-memory cache; the latter by IBM’s IMS/VS Fast obtain and use NVM directly using this interface. Internally, lib- Path [32], where the system performs updates on in-memory data numa library [4] is used to ensure that the application allocates and relies on the disk to ensure durability. The need to ensure that all memory only from emulated NVM and not regular DRAM. When changes are durable has dominated the design of systems with both the DBMS writes to a memory location, the written (dirty) data may types of architectures. This has involved optimizing the layout of reside indefinitely in the volatile CPU caches and not propagate data for each storage layer depending on how fast it can perform ran- immediately to NVM. We use a hardware write barrier primitive dom accesses [31]. Further, updates performed on tuples stored in (SFENCE) to guarantee the durability of writes to NVM when they memory need to be propagated to an on-disk representation for dura- are flushed from CPU caches. bility. Previous studies have shown that the overhead of managing this data movement for OLTP workloads is considerable [35]. Filesystem Interface: The emulator exposes a NVM-backed NVM technologies, like phase-change memory [55] and memris- volume to the OS through a special filesystem that is optimized tors [60], remove these tuple transformation and propagation costs for non-volatile memory [27]. This allows applications to use the through byte-addressable loads and stores with low latency. This POSIX filesystem interface to read/write data to files stored on 708 

3 . 4096 4096 Allocator Allocator Txn Batches DBMS 1024 Filesystem 1024 Filesystem Bandwidth (MB/s) Bandwidth (MB/s) 256 256 Coordinator 64 64 Txn Requests 16 16 4 4 Executor Executor Executor Executor Executor Executor 1 1 … 1 2 4 8 16 32 64 128 256 1 2 4 8 16 32 64 128 256 Chunk Size (B) Chunk Size (B) Storage Storage Storage Storage Storage Storage (a) Sequential Writes (b) Random Writes Engine Engine Engine Engine Engine Engine Figure 1: Comparison of the durable write bandwidth of Intel Lab’s NVM emulator using the allocator and filesystem interfaces. Allocator Filesystem OS Interface Interface (malloc, free) (read, write) NVM. Normally, in a block-oriented filesystem, file I/O requires two copies; one involving the block device and another involving the Memory NVM user buffer. The emulator’s optimized filesystem, however, requires Interface (load, store) only one copy between the file and the user buffers. This improves the file I/O performance by 7–10× compared to block-oriented Figure 2: An overview of the architecture of the DBMS testbed. filesystems like EXT4. The filesystem interface allows existing DBMSs to make use of NVM for durable storage. consistent state. This recovery mechanism is required only after the OS restarts and not after the DBMS restarts, because the allocator Both of the above interfaces use memory from the emulated NVM. handles memory management for all applications. The key difference, however, is that the filesystem interface supports To show that accessing NVM through the allocator interface is a naming mechanism that ensures that file offsets are valid after faster than using the filesystem interface, we compare them using the system restarts. The downside of the filesystem interface is a micro-benchmark. In this experiment, the application performs that it requires the application’s writes to go through the kernel’s durable writes to NVM using the two interfaces with sequential and virtual filesystem (VFS) layer. In contrast, when the application random access patterns. The application performs durable writes uses the allocator interface, it can write to and read from NVM using the filesystem’s fsync system call and the allocator’s sync directly within userspace. However, the allocator interface does primitive. We vary the size of the data chunk that the application not automatically provide a naming mechanism that is valid after writes from 1 to 256 bytes. The results in Fig. 1 show that NVM- a system restart. We use a memory allocator that is designed for aware allocator delivers 10–12× higher write bandwidth than the NVM to overcome this limitation. filesystem. The performance gap is more evident when the applica- tion writes out small data chunks sequentially. We also note that the 2.3 NVM-aware Memory Allocator gap between sequential and random write bandwidth is lower than that observed in other durable storage technologies. An NVM-aware memory allocator for a DBMS needs to satisfy We now describe the DBMS testbed that we built to evaluate two key requirements. The first is that it should provide a durability storage and recovery methods for DBMSs running on NVM. As we mechanism to ensure that modifications to data stored on NVM are discuss in subsequent sections, we use non-volatile pointers to build persisted. This is necessary because the changes made by a transac- non-volatile data structures that are guaranteed to be consistent after tion to a location on NVM may still reside in volatile CPU caches the OS or DBMS restarts. These data structures, along with the when the transaction commits. If a power failure happens before allocator interface, are used to build NVM-aware storage engines. the changes reach NVM, then these changes are lost. The allocator exposes a special API call to provide this durability mechanism. Internally, the allocator first writes back the cache lines contain- 3. DBMS TESTBED ing the data from any level of the cache hierarchy to NVM using We developed a lightweight DBMS to evaluate different stor- CLFLUSH [2] instruction. Then, it issues a SFENCE instruction to age architecture designs for OLTP workloads. We did not use an ensure that the data flushed from the CPU caches becomes durable. existing DBMS as that would require significant changes to incor- Otherwise, this data might still be buffered in the memory controller porate the storage engines into a single system. Although some and lost in case of a power failure. From here on, we refer to the DBMSs support a pluggable storage engine back-end (e.g., MySQL, above mentioned durability mechanism as the sync primitive. MongoDB), modifying them to support NVM would still require The second requirement is that it should provide a naming mech- significant changes. We also did not want to taint our measurements anism for allocations so that pointers to locations in memory are with features that are not relevant to our evaluation. valid even after the system restarts. The allocator ensures that the The architecture of the testbed running on the hardware emulator virtual memory addresses assigned to a memory-mapped region is depicted in Fig. 2. The DBMS’s internal coordinator receives never change. With this mechanism, a pointer to a NVM location is incoming transaction requests from the application and then invokes mapped to the same virtual location after the OS or DBMS restarts. the target stored procedure. As a transaction executes in the sys- We refer to these pointers as non-volatile pointers [51]. tem, it invokes queries to read and write tuples from the database. The NVM allocator that we use in our evaluation is based on the These requests are passed through a query executor that invokes the open-source NVM-related libpmem library [58]. We extended this necessary operations on the DBMS’s active storage engine. allocator to follow a rotating best-fit allocation policy and to support The DBMS uses pthreads to allow multiple transactions to run multi-threaded usage. The allocator directly maps the NVM to its concurrently in separate worker threads. It executes as a single address space. Unlike the filesystem interface, accessing a region of process with the number of worker threads equal to the number of memory obtained from this allocator does not require copying data cores, where each thread is mapped to a different core. Since we to user buffers. After an OS restart, the allocator reclaims memory do not want the DBMS’s concurrency control scheme to interfere that has not been persisted and restores its internal metadata to a with our evaluation, we partition the database and use a lightweight 709 

4 . ?''@A?+@B& 7C'D2E2+DF& ;!!<1;:<"$ =>!?@A@:?B$ =::>?=3>@+ 5A:B)C)3B<+ ))3"%&'0++ =01<.(,;.,9&'#>& 718.9(213.&!"#$%4&5##"& !')-$()*'$!)./&0$ <'43"%&'++ 12*324& 5-& 78,&& 7*9"2&& 7:;"2&& 56& !2<#42&*,3&& 1/2.3/435670'$89:6''$ $%&'%(# )*+,%#-'# !"#)*+,%#./%,'0# '(& '(& '(& =>24&'?*@2A& %&'(#*# +,-(# ./01,# ,23#''0+ 2(&3(0# 111# 232# 11111# -.-& 000& 000& 000& F&G1(0#H(6703# +4-5(#3&1&# ,23#''0+ !"#$%&'##%()*&+,-".& 2:,*4;#<4& ()*'$+)+,'$ ,&--4+5$&6'#+ ;400(<1#./0(6170,#8=:# ./01,#./0(6170,#89:# !"#$%&'(& )#$*+#,& %&'(#!""!# 23321111# -..-& -.-& -./& %&'(#!""$# !"#$"%&'()$*'+,&-./0+1--&+ -../& 000& )# >0&<6?#8!:# >0&<6?##8A:# >0&<6?#8@:# /,01,-".(213.&!"#$%4&5##"& !6+0..4& 7#$6'("8'"9+:-;+ !"#$%&'&'$ B(&C#8$:# B(&C#8D:# B(&C#8E:# !2# !""!# !""$# )45## )&7,%## )*+,%## !"# 8%9:(%#&5'## -6# -6# -6# ;<%(#-=&>%0# 232# 111# 111# 111# (a) In-place Updates (InP) (b) Copy-on-Write Updates (CoW) (c) Log-structured Updates (Log) Figure 3: Architectural layout of the three traditional storage engines supported in the DBMS testbed. The engine components accessed using the allocator interface and those accessed using the filesystem interface are bifurcated by the dashed line. locking scheme where transactions are executed serially at each Recovery: Since the changes made by transactions committed partition based on timestamp ordering [59]. Using a DBMS that after the last checkpoint are not written to “durable" storage, the InP supports a pluggable back-end allows us to compare the performance engine maintains a durable write-ahead log (WAL) in the filesystem characteristics of different storage and recovery methods on a single to assist in recovery from crashes and power failures. WAL records platform. We implemented three storage engines that use different the transactions’ changes before they are applied to DBMS [29]. As approaches for supporting durable updates to a database: (1) in- transactions execute queries that modify the database, the engine place updates engine, (2) copy-on-write updates engine, and (3) appends a new entry to the WAL for those changes. Each entry con- log-structured updates engine. Each engine also supports both tains the transaction identifier, the table modified, the tuple identifier, primary and secondary indexes. and the before/after tuple images depending on the operation. We now describe these engines in detail. For each engine, we The most well-known recovery protocol for in-place updates is first discuss how they apply changes made by transactions to the ARIES [47]. With ARIES, the engine periodically takes checkpoints database and then how they ensure durability after a crash. All of that are stored on the filesystem to bound recovery latency and re- these engines are based on the architectures found in state-of-the-art duce the storage space consumed by the log. In our implementation, DBMSs. That is, they use memory obtained using the allocator we compress (gzip) the checkpoints on the filesystem to reduce their interface as volatile memory and do not exploit NVM’s persistence. storage footprint on NVM. During recovery, the engine first loads Later in Section 4, we present our improved variants of these engines the last checkpoint. It then replays the log to ensure that the changes that are optimized for NVM. made by transactions committed since the checkpoint are present in the database. Changes made by uncommitted transactions at the 3.1 In-Place Updates Engine (InP) time of failure are not propagated to the database. The InP engine uses a variant of ARIES that is adapted for main memory DBMSs The first engine uses the most common storage engine strategy with a byte-addressable storage engine [45]. As we do not store in DBMSs. With in-place updates, there is only a single version physical changes to indexes in this log, all of the tables’ indexes are of each tuple at all times. When a transaction updates a field for rebuilt during recovery because they may have been corrupted [45]. an existing tuple, the system writes the new value directly on top of the original one. This is the most efficient method of applying 3.2 Copy-on-Write Updates Engine (CoW) changes, since the engine does not make a copy of the tuple first before updating it and only the updated fields are modified. The The second storage engine performs copy-on-write updates where design of this engine is based on VoltDB [5], which is a memory- instead of modifying the original tuple, it creates a copy of the tuple oriented DBMS that does not contain legacy disk-oriented DBMS and then modifies that copy. As the CoW engine never overwrites components like a buffer pool. The InP engine uses the STX B+tree committed data, it does not need to record changes in a WAL for library for all of its indexes [10]. recovery. The CoW engine instead uses different look-up direc- tories for accessing the versions of tuples in the database. With Storage: Fig. 3a illustrates the architecture of the InP engine. this approach, known as shadow paging in IBM’s System R [33], The storage area for tables is split into separate pools for fixed-sized the DBMS maintains two look-up directories at all times: (1) the blocks and variable-length blocks. Each block consists of a set of current directory, and (2) the dirty directory. The current directory slots. The InP engine stores the table’s tuples in fixed-size slots. points to the most recent versions of the tuples and only contains the This ensures that the tuples are byte-aligned and the engine can effects of committed transactions. The dirty directory points to the easily compute their offsets. Any field in a table that is larger than versions of tuples being modified by active transactions. To ensure 8 bytes is stored separately in a variable-length slot. The 8-byte that the transactions are isolated from the effects of uncommitted location of that slot is stored in that field’s location in the tuple. transactions, the engine maintains a master record that always points The tables’ tuples are unsorted within these blocks. For each to the current directory. Fig. 3b presents the architecture of the CoW table, the DBMS maintains a list of unoccupied tuple slots. When a engine. After applying the changes on the copy of the tuple, the transaction deletes a tuple, the deleted tuple’s slot is added to this engine updates the dirty directory to point to the new version of pool. When a transaction inserts a tuple into a table, the engine first the tuple. When the transaction commits, the engine updates the checks the table’s pool for an available slot. If the pool is empty, master record atomically to point to the dirty directory. The engine then the engine allocates a new fixed-size block using the allocator maintains an internal page cache to keep the hot pages in memory. interface. The engine also uses the allocator interface to maintain System R implements shadow paging by copying the current the indexes and stores them in memory. directory to create the new dirty directory after every commit op- eration. But, creating the dirty directory in this manner incurs 710 

5 .high I/O overhead. The CoW engine uses LMDB’s copy-on-write efficiently. When the size of the MemTable exceeds a threshold, the B+trees [56, 16, 36] to implement shadow paging efficiently. Fig. 3b engine flushes it to the filesystem as an immutable SSTable stored illustrates an update operation on a CoW B+tree. When the engine in a separate file. The Log engine also constructs a Bloom filter [12] modifies the leaf node 4 in the current directory, it only needs to for each SSTable to quickly determine at runtime whether it contains make a copy of the internal nodes lying along the path from that entries associated with a tuple to avoid unnecessary index look-ups. leaf node up to the root of the current version. The current and The contents of the MemTable are lost after system restart. Hence, dirty directories of the copy-on-write B+tree share the rest of the to ensure durability, the Log engine maintains a WAL in the filesys- tree. This significantly reduces the I/O overhead of creating the tem. The engine first records the changes in the log and then applies dirty directory as only a fraction of the B+tree is copied. To further the changes to the MemTable. The log entry contains the transaction reduce the overhead of shadow paging, the CoW engine uses a identifier, the table modified, the tuple identifier, and the before/after group commit mechanism that batches the changes made by a group images of the tuple depending on the type of operation. To reduce of transactions before committing the dirty directory. the I/O overhead, the engine batches log entries for a group of transactions and flushes them together. Storage: The CoW engine stores the directories on the filesystem. The log-structured update approach performs well for write- The tuples in each table are stored in a HDD/SSD-optimized format intensive workloads as it reduces random writes to durable stor- where all the tuple’s fields are inlined. This avoids expensive random age. The downside of the Log engine is that it incurs high read accesses that are required when some fields are not inlined. Each amplification (i.e., the number of reads required to fetch the data database is stored in a separate file and the master record for the is much higher than that actually needed by the application). To database is located at a fixed offset within the file. It supports retrieve a tuple, the Log engine first needs to look-up the indexes secondary indexes as a mapping of secondary keys to primary keys. of all the runs of the LSM tree that contain entries associated with The downside of the CoW engine is that it creates a new copy of the desired tuple in order to reconstruct the tuple [1]. To reduce this tuple even if a transaction only modifies a subset of the tuple’s fields. read amplification, the Log engine performs a periodic compaction The engine also needs to keep track of references to tuples from process that merges a subset of SSTables. First, the entries associ- different versions of the copy-on-write B+tree so that it can reclaim ated with a tuple in different SSTables are merged into one entry the storage space consumed by old unreferenced tuple versions [9]. in a new SSTable. Tombstone entries are used to identify purged As we show in Section 5.3, this engine has high write amplification tuples. Then, the engine builds indexes for the new SSTable. (i.e., the amount of data written to storage is much higher compared to the amount of data written by the application). This increases Recovery: During recovery, the Log engine rebuilds the MemTable wear on the NVM device thereby reducing its lifetime. using the WAL, as the changes contained in it were not written onto durable storage. It first replays the log to ensure that the changes Recovery: If the DBMS crashes before the master record is made by committed transactions are present. It then removes any updated, then the changes present in the dirty directory are not changes performed by uncommitted transactions, thereby bringing visible after restart. Hence, there is no recovery process for the CoW the MemTable to a consistent state. engine. When the DBMS comes back on-line, the master record points to the current directory that is guaranteed to be consistent. The dirty directory is garbage collected asynchronously, since it only contains the changes of uncommitted transactions. 4. NVM-AWARE ENGINES All of the engines described above are derived from existing 3.3 Log-structured Updates Engine (Log) DBMS architectures that are predicated on a two-tier storage hier- Lastly, the third storage engine uses a log-structured update pol- archy comprised of volatile DRAM and a non-volatile HDD/SSD. icy. This approach originated from log-structured filesystems [57], These storage devices have distinct hardware constraints and per- and then it was adapted to DBMSs as log-structured merge (LSM) formance properties [54]. First, the read and write latency of non- trees [50] for write-intensive workloads. The LSM tree consists of volatile storage is several orders of magnitude higher than DRAM. a collection of runs of data. Each run contains an ordered set of Second, the DBMS accesses data on non-volatile storage at block- entries that record the changes performed on tuples. Runs reside granularity, while with DRAM it accesses data at byte-granularity. either in volatile memory (i.e., MemTable) or on durable storage (i.e., Third, the performance gap between sequential and random accesses SSTables) with their storage layout optimized for the underlying stor- is greater for non-volatile storage compared to DRAM. age device. The LSM tree reduces write amplification by batching The traditional engines were designed to account for and reduce the updates in MemTable and periodically cascading the changes the impact of these differences. For example, they maintain two to durable storage [50]. The design for our Log engine is based layouts of tuples depending on the storage device. Tuples stored on Google’s LevelDB [22], which implements the log-structured in memory can contain non-inlined fields because DRAM is byte- update policy using LSM trees. addressable and handles random accesses efficiently. In contrast, fields in tuples stored on durable storage are inlined to avoid random Storage: Fig. 3c depicts the architecture of the Log engine. The accesses because they are more expensive. To amortize the overhead Log engine uses a leveled LSM tree [40], where each level in the for accessing durable storage, these engines batch writes and flush tree contains the changes for a single run. The data starts from them in a deferred manner. the MemTable stored in the topmost level and propagates down to Many of these techniques, however, are unnecessary in a system SSTables stored in lower parts of the tree over time. The size of with a NVM-only storage hierarchy [23, 27, 49]. As shown in the run stored in a given level is k times larger than that of the run Table 1, the access latencies of NVM are orders of magnitude shorter stored in its parent, where k is the growth factor of the tree. The Log than that of HDDs and SSDs. Further, the performance gap between engine allows us to control the size of the MemTable and the growth sequential and random accesses on NVM is comparable to that of factor of the tree. It first stores the tuple modifications in a memory- DRAM. We therefore adapt the storage and recovery mechanisms optimized format using the allocator interface in the MemTable. of these traditional engines to exploit NVM’s characteristics. We The MemTable contains indexes to handle point and range queries refer to these optimized storage engines as the NVM-aware engines. 711 

6 . B11CDB4CE) !"#$%&'"($)*+,-./)0,,+) 758"56+$&'"($)*+,-./)0,,+) B55C+B4CD* 2&"9:*5"":$8,*4';&)* CAADEC7DF+ <'97"%&'++ 899:;"%&'+<'97"%&'0++ !"#$%"&'(&)*+",-$"#$./01)*234/))* 12"34%5*% 6"3/7"8% 2-3(4-&"5&'+,67#''0+ !"#$"%& 2-3(4-&"5&'+,67#''0+ H/I-$,%J$3",#% 9::9% 9::;% &&&% '&'& ?@,,$8-%*+,$3-",(%<A>% *+,-(%*+,$3-",(%<=>% '& 9,:&;,+5<+$)*=48$$/) %'/0';&)$>0?)*2&"9:@*A""&* *+,-.)1,,.&23)456+$) ()*+,&-.& /*+#0*1& 1,/83B%<9>% 1,/83B%%<D>% 1,/83B%<C>% !"#$"%&'()$*'+,&-./0+1--&+ ,&--9+=$&;'#+ 2332& 5)'6*!"7)*5'-"81* !""!####$ 2334& 555& 6$/E%<;>% 6$/E%<F>% 6$/E%<G>% >8"?$&5@$5%)1,A) <0=)7$>0?)*2&"9:@*A""&* 62& 891&& 8#:)"&& 8;<)"&&67& ("=*%"&#1$&& !"#$%&% '()$% *+,-(% .$/#$,% >#$;'("?'"@+A-B+ %!$ '()$$ ',-./$$ '01./$$%&$ 2/345/$,)6$$ -.& -.& -.& >?"%&-@#A"B& .$/#$,% *+$ *+$ *+$ 78/5$*9,:/;$ 23332& 555& 555& !"""!$ ###$ ###$ 23332& 555& 555& 0%0% !"""!$ ###$ ###$ ###$ 0% (a) In-place Updates (NVM-InP) (b) Copy-on-Write Updates (NVM-CoW) (c) Log-structured Updates (NVM-Log) Figure 4: NVM-Aware Engines – Architectural layout of the NVM-optimized storage engines. As we show in our evaluation in Section 5, these engines deliver ations on non-inlined fields. The engine persists this entry before higher throughput than their traditional counterparts while still en- updating the slot’s state as persisted. If it does not ensure this order- suring durability. They reduce write amplification using NVM’s per- ing, then the engine cannot reclaim the storage space consumed by sistence thereby expanding the lifetime of the NVM device. These uncommitted transactions after the system restarts, thereby causing engines use only the allocator interface described in Section 2.3 non-volatile memory leaks. After all of the transaction’s changes with NVM-optimized data structures [49, 62]. are safely persisted, the engine truncates the log. Table 2 presents an overview of the steps performed by the NVM- The engine supports primary and secondary indexes using non- aware storage engines, while executing the primitive database op- volatile B+trees that it maintains using the allocator interface. We erations. We note that the engine performs these operations within modified the STX B+tree library so that all operations that alter the the context of a transaction. For instance, if the transaction aborts index’s internal structure are atomic [49, 62]. For instance, when while executing an operation, it must undo the effects of any earlier adding an entry to a B+tree node, instead of inserting the key in a operation performed by the transaction. sorted order, it appends the entry to a list of entries in the node. This modification is necessary because if the entry crosses cache line 4.1 In-Place Updates Engine (NVM-InP) boundaries, the cache line write-backs required to persist the entry need not happen atomically. Our changes to the library ensure that One of the main problems with the InP engine described in Sec- the engine can safely access the index immediately after the system tion 3.1 is that it has high rate of data duplication. When a trans- restarts as it is guaranteed to be in a consistent state. action inserts a tuple, the engine records the tuple’s contents in the WAL and then again in the table storage area. The InP engine’s Recovery: The effects of committed transactions are durable logging infrastructure also assumes that the system’s durable storage after the system restarts because the NVM-InP engine immediately device has orders of magnitude higher write latency compared to persists the changes made by a transaction when it commits. The DRAM. It therefore batches multiple log records and flushes them engine therefore does not need to replay the log during recovery. periodically to the WAL using sequential writes. This approach, But the changes of uncommitted transactions may be present in however, increases the mean response latency as transactions need the database because the memory controller can evict cache lines to wait for the group commit operation. containing those changes to NVM at any time [48]. The NVM-InP Given this, we designed the NVM-InP engine to avoid these engine therefore needs to undo those transactions using the WAL. issues. Now when a transaction inserts a tuple, rather than copying To undo an insert operation, the engine releases the tuple’s storage the tuple to the WAL, the NVM-InP engine only records a non- space using the pointer recorded in the WAL entry and then removes volatile pointer to the tuple in the WAL. This is sufficient because entries associated with the tuple in the indexes. In case of an update both the pointer and the tuple referred to by the pointer are stored on operation, the engine restores the tuple’s state using the before NVM. Thus, the engine can use the pointer to access the tuple after image. If the after image contains non-inlined tuple fields, then the system restarts without needing to re-apply changes in the WAL. the engine frees up the memory occupied by those fields. For a It also stores indexes as non-volatile B+trees that can be accessed delete operation, it only needs to update the indexes to point to the immediately when the system restarts without rebuilding. original tuple. To handle transaction rollbacks and DBMS recovery correctly, the NVM-InP engine releases storage space occupied by Storage: The architecture of the NVM-InP engine is shown in tuples or non-inlined fields only after it is certain that they are no Fig. 4a and Table 2 presents an overview of the steps to perform longer required. As this recovery protocol does not include a redo different operations. The engine stores tuples and non-inlined fields process, the NVM-InP engine has a short recovery latency that only using fixed-size and variable-length slots, respectively. To reclaim depends on the number of uncommitted transactions. the storage space of tuples and non-inlined fields inserted by uncom- mitted transactions after the system restarts, the NVM-InP engine maintains durability state in each slot’s header. A slot can be in one 4.2 Copy-on-Write Updates Engine (NVM-CoW) of three states - unallocated, allocated but not persisted, or persisted. The original CoW engine stores tuples in self-containing blocks After the system restarts, slots that are allocated but not persisted without pointers in the copy-on-write B+tree on the filesystem. The transition back to unallocated state. problem with this engine is that the overhead of propagating mod- The NVM-InP engine stores the WAL as a non-volatile linked list. ifications to the dirty directory is high; even if a transaction only It appends new entries to the list using an atomic write. Each entry modifies one tuple, the engine needs to copy the entire block to the contains the transaction identifier, the table modified, the tuple iden- filesystem. When a transaction commits, the CoW engine uses the tifier, and pointers to the operation’s changes. The changes include filesystem interface to flush the dirty blocks and updates the master tuple pointers for insert operation and field pointers for update oper- record (stored at a fixed location in the file) to point to the root of 712 

7 . NVM-InP Engine NVM-CoW Engine NVM-Log Engine INSERT • Sync tuple with NVM. • Sync tuple with NVM. • Sync tuple with NVM. • Record tuple pointer in WAL. • Store tuple pointer in dirty dir. • Record tuple pointer in WAL. • Sync log entry with NVM. • Update tuple state as persisted. • Sync log entry with NVM. • Mark tuple state as persisted. • Add tuple entry in secondary indexes. • Mark tuple state as persisted. • Add tuple entry in indexes. • Add tuple entry in MemTable. UPDATE • Record tuple changes in WAL. • Make a copy of the tuple. • Record tuple changes in WAL. • Sync log entry with NVM. • Apply changes on the copy. • Sync log entry with NVM. • Perform modifications on the tuple. • Sync tuple with NVM. • Perform modifications on the tuple. • Sync tuple changes with NVM. • Store tuple pointer in dirty dir. • Sync tuple changes with NVM. • Update tuple state as persisted. • Add tuple entry in secondary indexes. DELETE • Record tuple pointer in WAL. • Remove tuple pointer from dirty dir. • Record tuple pointer in WAL. • Sync log entry with NVM. • Discard entry from secondary indexes. • Sync log entry with NVM. • Discard entry from table and indexes. • Recover tuple space immediately. • Mark tuple tombstone in MemTable. • Reclaim space at the end of transaction. • Reclaim space during compaction. SELECT • Find tuple pointer using index/table. • Locate tuple pointer in appropriate dir. • Find tuple entries in relevant LSM runs. • Retrieve tuple contents. • Fetch tuple contents from dir. • Rebuild tuple by coalescing entries. Table 2: An overview of the steps performed by the NVM-aware storage engines, while executing primitive database operations. The syncing mechanism is implemented using CLFLUSH and SFENCE instructions on the hardware emulator. We describe the sync primitive in Section 2.3. the dirty directory [16]. These writes are expensive as they need to 4.3 Log-structured Updates Engine (NVM-Log) switch the privilege level and go through the kernel’s VFS path. The Log engine batches all writes in the MemTable to reduce The NVM-CoW engine employs three optimizations to reduce random accesses to durable storage [50, 43]. The benefits of this these overheads. First, it uses a non-volatile copy-on-write B+tree approach, however, are not as evident for a NVM-only storage that it maintains using the allocator interface. Second, the NVM- hierarchy because the performance gap between sequential and CoW engine directly persists the tuple copies and only records random accesses is smaller. The original log-structured engine non-volatile tuple pointers in the dirty directory. Lastly, it uses the that we described in Section 3.3 incurs significant overhead from lightweight durability mechanism of the allocator interface to persist periodically flushing MemTable to the filesystem and compacting changes in the copy-on-write B+tree. SSTables to bound read amplification. Similar to the NVM-InP Storage: Fig. 4b depicts the architecture of the NVM-CoW en- engine, the NVM-Log engine records all the changes performed by gine. The storage area for tuples is spread across separate pools for transactions on a WAL stored on NVM. fixed-sized and variable-length data. The engine maintains the dura- Our NVM-Log engine avoids data duplication in the MemTable bility state of each slot in both pools similar to the NVM-InP engine. and the WAL as it only records non-volatile pointers to tuple mod- The NVM-CoW engine stores the current and dirty directory of the ifications in the WAL. Instead of flushing MemTable out to the non-volatile copy-on-write B+tree using the allocator interface. We filesystem as a SSTable, it only marks the MemTable as immutable modified the B+tree from LMDB [16] to handle modifications at and starts a new MemTable. This immutable MemTable is physi- finer granularity to exploit NVM’s byte addressability. The engine cally stored in the same way on NVM as the mutable MemTable. maintains the master record using the allocator interface to support The only difference is that the engine does not propagate writes efficient updates. When the system restarts, the engine can safely to the immutable MemTables. We also modified the compaction access the current directory using the master record because that process to merge a set of these MemTables to generate a new larger directory is guaranteed to be in a consistent state. This is because MemTable. The NVM-Log engine uses a NVM-aware recovery pro- the data structure is append-only and the data stored in the current tocol that has lower recovery latency than its traditional counterpart. directory is never overwritten. Storage: As shown in Fig. 4c, the NVM-Log engine uses an The execution steps for this engine are shown in Table 2. The LSM tree to store the database. Each level of the tree contains a salient feature of this engine’s design is that it avoids the trans- sorted run of data. Similar to the Log engine, this engine first stores formation and copying costs incurred by the CoW engine. When all the changes performed by transactions in the MemTable which a transaction updates a tuple, the engine first makes a copy and is the topmost level of the LSM tree. The changes include tuple then applies the changes to that copy. It then records only the non- contents for insert operation, updated fields for update operation volatile tuple pointer in the dirty directory. The engine also batches and tombstone markers for delete operation. When the size of the transactions to amortize the cost of persisting the current directory. MemTable exceeds a threshold, the NVM-Log engine marks it as To commit a batch of transactions, it first persists the changes per- immutable and starts a new MemTable. We modify the periodic formed by uncommitted transactions. It then persists the contents compaction process the engine performs for bounding read ampli- of the dirty directory. Finally, it updates the master record using an fication to merge a set of immutable MemTables and create a new atomic durable write to point to that directory. The engine orders all MemTable. The engine constructs a Bloom filter [12] for each of these writes using memory barriers to ensure that only committed immutable MemTable to minimize unnecessary index look-ups. transactions are visible after the system restarts. Similar to the Log engine, the NVM-Log engine maintains a Recovery: As the NVM-CoW engine never overwrites commit- WAL. The purpose of the WAL is not to rebuild the MemTable, ted data, it does not have a recovery process. When the system but rather to undo the effects of uncommitted transactions from the restarts, it first accesses the master record to locate the current di- MemTable. An overview of the operations performed by the NVM- rectory. After that, it can start handling transactions. The storage Log engine is shown in Table 2. Like the NVM-InP engine, this new space consumed by the dirty directory at the time of failure is asyn- engine also stores the WAL as a non-volatile linked list of entries. chronously reclaimed by the NVM-aware allocator. When a transaction inserts a tuple, the engine first flushes the tuple to NVM and records the non-volatile tuple pointer in a WAL entry. It then persists the log entry and marks the tuple as persisted. Finally, 713 

8 .it adds an entry in the MemTable indexes. After the transaction For each workload mixture and skew setting pair, we pre-generate commits, the engine truncates the relevant log entry because the a fixed workload of 8 million transactions that is divided evenly changes recorded in MemTable are durable. Its logging overhead among the DBMS’s partitions. Using a fixed workload that is the is lower than the Log engine as it records less data and maintains same across all the engines allows us to compare their storage the WAL using the allocator interface. The engine uses non-volatile footprints and read/write amplification. B+trees [49, 62], described in Section 4.1, as MemTable indexes. Hence, it does not need to rebuild its indexes upon restarting. TPC-C: This benchmark is the current industry standard for eval- uating the performance of OLTP systems [61]. It simulates an Recovery: When the transaction commits, all the changes per- order-entry environment of a wholesale supplier. The workload con- formed by the transaction are persisted in the in-memory component. sists of five transaction types, which keep track of customer orders, During recovery, the NVM-Log engine only needs to undo the ef- payments, and other aspects of a warehouse. Transactions involving fects of uncommitted transactions on the MemTable. Its recovery database modifications comprise around 88% of the workload. We latency is therefore lower than the Log engine as it no longer needs configure the workload to contain eight warehouses and 100,000 to rebuild the MemTable. items. We map each warehouse to a single partition. The initial storage footprint of the database is approximately 1 GB. 5. EXPERIMENTAL ANALYSIS 5.2 Runtime Performance In this section, we present our analysis of the six different storage We begin with an analysis of the impact of NVM’s latency on engine implementations. Our DBMS testbed allows us to evaluate the performance of the storage engines. To obtain insights that the throughput, the number of reads/writes to the NVM device, the are applicable for various NVM technologies, we run the YCSB storage footprint, and the time that it takes to recover the database and TPC-C benchmarks under three latency configurations on the after restarting. We also use the perf toolkit to measure additional, emulator: (1) default DRAM latency configuration (160 ns), (2) lower-level hardware metrics of the system for each experiment [3]. a low NVM latency configuration that is 2× higher than DRAM The experiments were all performed on Intel Lab’s NVM hard- latency (320 ns), and (3) a high NVM latency configuration that ware emulator [27]. It contains a dual-socket Intel Xeon E5-4620 is 8× higher than DRAM latency (1280 ns). Prior work [27] has processor. Each socket has eight cores running at 2.6 GHz. It ded- shown that the sustained bandwidth of NVM is likely to be lower icates 128 GB of DRAM for the emulated NVM and its L3 cache than that of DRAM. We therefore leverage the bandwidth throttling size is 20 MB. We use the Intel memory latency checker [63] to mechanism in the hardware emulator [27] to throttle the NVM validate the emulator’s latency and bandwidth settings. The engines bandwidth to 9.5 GB/s, which is 8× lower than the available DRAM access NVM storage using the allocator and filesystem interfaces bandwidth on the platform. We execute all workloads three times of the emulator as described in Section 2.2. We set up the DBMS on each engine and report the average throughput. to use eight partitions in all of the experiments. We configure the node size of the STX B+tree and the CoW B+tree implementations YCSB: Figs. 5 to 7 present the throughput observed with the to be 512 B and 4 KB respectively. All transactions execute with YCSB benchmark while varying the workload mixture and skew the same serializable isolation level and durability guarantees. settings under different latency configurations. We first consider the read-only workload results shown in Figs. 5a, 6a and 7a. These 5.1 Benchmarks results provide an upper bound on performance since transactions We first describe the benchmarks we use in our evaluation. The do not modify the database and the engines therefore do not need to tables in each database are partitioned in such way that there are flush changes from CPU caches to NVM during execution. only single-partition transactions [52]. The most notable observation is that the NVM-InP engine is not faster than the InP engine for both skew settings. This is because YCSB: This is a widely-used key-value store workload from both engines perform reads using the allocator interface. The CoW Yahoo! [20]. It is representative of the transactions handled by web- engine’s throughput is lower than the in-place updates engine be- based companies. It contains a single table comprised of tuples with cause for every transaction, it fetches the master record and then a primary key and 10 columns of random string data, each 100 bytes looks-up the tuple in the current directory. As the NVM-CoW en- in size. Each tuple’s size is approximately 1 KB. We use a database gine accesses the master record and the non-volatile copy-on-write with 2 million tuples (∼2 GB). B+tree efficiently using the allocator interface, it is 1.9–2.1× faster The workload consists of two transaction types: (1) a read trans- than the CoW engine. The Log engine is the slowest among all the action that retrieves a single tuple based on its primary key, and engines because it coalesces entries spread across different LSM tree (2) an update transaction that modifies a single tuple based on its components to reconstruct tuples. The NVM-Log engine accesses primary key. We use four types of workload mixtures that allow us the immutable MemTables using the allocator interface and delivers to vary the I/O operations that the DBMS executes. These mixtures 2.8× higher throughput compared to its traditional counterpart. We represent different ratios of read and update transactions: see that increasing the workload skew improves the performance • Read-Only: 100% reads of all the engines due to caching benefits. The benefits are most evident for the InP and NVM-InP engines; they achieve 1.3× higher • Read-Heavy: 90% reads, 10% updates throughput compared to the low skew setting. The performance • Balanced: 50% reads, 50% updates gains due to skew are minimal in case of the Log and NVM-Log • Write-Heavy: 10% reads, 90% updates engines due to tuple coalescing costs. We also observe that the performance gap between the two types We modified the YCSB workload generator to support two dif- of engines decreases in the read-only workload when we increase ferent levels of skew in the tuple access patterns that allows us to the NVM latency. In the high latency configuration, the NVM-CoW create a localized hotspot within each partition: and the NVM-Log engines are 1.4× and 2.5× faster than their • Low Skew: 50% of the transactions access 20% of the tuples. traditional counterparts. This is because the benefits of accessing • High Skew: 90% of the transactions access 10% of the tuples. data structures using the allocator interface are masked by slower 714 

9 . InP CoW Log NVM-InP NVM-CoW NVM-Log 2.6M 2.6M 3.3M 3.3M 2.0M 2.3M 2.3M 2.8M 2000000 2000000 2000000 2000000 Throughput (txn/sec) Throughput (txn/sec) Throughput (txn/sec) Throughput (txn/sec) 1600000 1600000 1600000 1600000 1200000 1200000 1200000 1200000 800000 800000 800000 800000 400000 400000 400000 400000 0 0 0 0 Low Skew High Skew Low Skew High Skew Low Skew High Skew Low Skew High Skew (a) Read-only Workload (b) Read-heavy Workload (c) Balanced Workload (d) Write-heavy Workload Figure 5: YCSB Performance (DRAM Latency) – The throughput of the engines for the YCSB benchmark without any latency slowdown. 2.3M 2.3M 2000000 2000000 2000000 2000000 Throughput (txn/sec) Throughput (txn/sec) Throughput (txn/sec) Throughput (txn/sec) 1600000 1600000 1600000 1600000 1200000 1200000 1200000 1200000 800000 800000 800000 800000 400000 400000 400000 400000 0 0 0 0 Low Skew High Skew Low Skew High Skew Low Skew High Skew Low Skew High Skew (a) Read-only Workload (b) Read-heavy Workload (c) Balanced Workload (d) Write-heavy Workload Figure 6: YCSB Performance (Low Latency) – The throughput of the engines for the YCSB benchmark under the low NVM latency configuration (2×). 2000000 2000000 2000000 2000000 Throughput (txn/sec) Throughput (txn/sec) Throughput (txn/sec) Throughput (txn/sec) 1600000 1600000 1600000 1600000 1200000 1200000 1200000 1200000 800000 800000 800000 800000 400000 400000 400000 400000 0 0 0 0 Low Skew High Skew Low Skew High Skew Low Skew High Skew Low Skew High Skew (a) Read-only Workload (b) Read-heavy Workload (c) Balanced Workload (d) Write-heavy Workload Figure 7: YCSB Performance (High Latency) – The throughput of the engines for the YCSB benchmark under the high NVM latency configuration (8×). 50000 NVM loads. The engines’ throughput decreases sub-linearly with Throughput (txn/sec) 40000 respect to the increased NVM latency. For example, with 8× higher 30000 latency, the throughput of the engines only drop by 2–3.4×. The 20000 NVM-aware engines are more sensitive to the increase in latency as they do not incur tuple transformation and copying costs that dampen 10000 the effect of slower NVM accesses in the traditional engines. 0 DRAM Latency Low NVM Latency High NVM Latency For the read-heavy workload, the results shown in Figs. 5b, 6b Figure 8: TPC-C Throughput – The performance of the engines for TPC- and 7b indicate that the throughput decreases for all the engines C benchmark for all three NVM latency settings. compared to the read-only workload because they must flush trans- actions’ changes to NVM. Unlike before where the two engines had TPC-C: Fig. 8 shows the engines’ throughput while executing the same performance, in this workload we observe that the NVM- TPC-C under different latency configurations. Among all the en- InP engine is 1.3× faster than the InP engine due to lower logging gines, the NVM-InP engine performs the best. The NVM-aware overhead. The performance of the CoW engine drops compared to engines are 1.8–2.1× faster than the traditional engines. The NVM- its performance on the read-only workload because of the overhead CoW engine exhibits the highest speedup of 2.3× over the CoW of persisting the current directory. The drop is less prominent in the engine. We attribute this to the write-intensive nature of the TPC- high skew workload because the updates are now concentrated over C benchmark. Under the high NVM latency configuration, the a few hot tuples and therefore the number of copy-on-write B+tree NVM-aware engines deliver 1.7–1.9× higher throughput than their nodes that are copied when creating the dirty directory is smaller. traditional counterparts. These trends closely follow the results The benefits of our optimizations are more prominent for the for the write-intensive workload mixture in the YCSB benchmark. balanced and write-heavy workloads. For the NVM-InP and the The benefits of our optimizations, however, are not as significant as NVM-Log engines, we attribute this to lower logging overhead. In previously observed with the YCSB benchmark. This is because case of the NVM-CoW engine, this is because it does not have to the TPC-C transactions’ contain more complex program logic and copy and transform tuples from the filesystem whenever it modifies execute more queries per transaction. them. This allows this engine to achieve 4.3–5.5× higher throughput than the CoW engine. The performance gap between the Log and the CoW engines decreases because the former incurs lower tuple 5.3 Reads & Writes coalescing costs in these workloads. The Log engine is therefore We next measure the number of times that the storage engines 1.6–4.1× faster than the CoW engine. It still lags behind the InP access the NVM device while executing the benchmarks. This is engine, however, because batching updates in the MemTable are not important because the number of write cycles per bit is limited in as beneficial in the NVM-only storage hierarchy. With increased different NVM technologies as shown in Table 1. We compute latency, the throughput of all the engines decreases less on these these results using hardware performance counters on the emulator write-intensive workloads compared to the workloads that contain with the perf framework [3]. These counters track the number of more reads. The throughput does not drop linearly with increasing loads (i.e. reads) from and stores (i.e. writes) to the NVM device NVM latency. With an 8× increase in latency, the throughput of the during execution. In each trial, the engines’ access measurements engines only drops by 1.8–2.9×. We attribute this to the effects of are collected after loading the initial database. caching and memory-level parallelism in the emulator. YCSB: The results for NVM reads and writes while executing the YCSB benchmark are shown in Figs. 9 and 10, respectively. In 715 

10 . InP CoW Log NVM-InP NVM-CoW NVM-Log 1.6B 1200 1200 1200 1200 1000 1000 1000 1000 NVM Loads (M) NVM Loads (M) NVM Loads (M) NVM Loads (M) 800 800 800 800 600 600 600 600 400 400 400 400 200 200 200 200 0 0 0 0 Low Skew High Skew Low Skew High Skew Low Skew High Skew Low Skew High Skew (a) Read-only Workload (b) Read-heavy Workload (c) Balanced Workload (d) Write-heavy Workload Figure 9: YCSB Reads – The number of load operations executed by the engines while running the YCSB workload. 500 500 500 500 NVM Stores (M) NVM Stores (M) NVM Stores (M) NVM Stores (M) 400 400 400 400 300 300 300 300 200 200 200 200 100 100 100 100 0 0 0 0 Low Skew High Skew Low Skew High Skew Low Skew High Skew Low Skew High Skew (a) Read-only Workload (b) Read-heavy Workload (c) Balanced Workload (d) Write-heavy Workload Figure 10: YCSB Writes – The number of store operations executed by the engines while running the YCSB workload. 600 Recovery Latency (ms) Recovery Latency (ms) 1200 1000000 1000000 500 NVM Stores (M) 1000 10000 10000 NVM Loads (M) 800 400 100 100 600 300 1 1 400 200 0.01 0.01 1000 10000 100000 1000 10000 100000 200 100 Number of transactions Number of transactions 0 0 (a) YCSB (b) TPC-C (a) Reads (b) Writes Figure 12: Recovery Latency – The amount of time that the engines take Figure 11: TPC-C Reads & Writes – The number of load and store opera- to restore the database to a consistent state after a restart. tions executed by the engines while running the TPC-C benchmark. 5.4 Recovery the read-only workload, we observe that the Log engine performs In this experiment, we evaluate the recovery latency of the stor- the most load operations due to tuple coalescing. The NVM-aware age engines. For each benchmark, we first execute a fixed num- engines perform up to 53% fewer loads due to better cache locality ber of transactions and then force a hard shutdown of the DBMS as they do not perform any tuple deserialization operations. When (SIGKILL). We then measure the amount of time for the system to we increase the workload skew, there is a significant drop in the restore the database to a consistent state. That is, a state where the NVM loads performed by all the engines. We attribute this to effects of all committed transactions are durable, and the effects of caching of hot tuples in the CPU caches. uncommitted transactions are removed. The number of transactions In the write-intensive workloads, we observe that the CoW engine that need to be recovered by the DBMS depends on the frequency now performs the most NVM stores. This is because it needs to of checkpointing for the InP engine and on the frequency of flush- copy several pages while creating the dirty directory. This engine ing the MemTable for the Log engine. The CoW and NVM-CoW also performs the largest number of load operations. The copying engines do not perform any recovery mechanism after the OS or mechanism itself requires reading data off NVM. Further, the I/O DBMS restarts because they never overwrite committed data. They overhead of maintaining this directory reduces the number of hot have to perform garbage collection to clean up the previous dirty di- tuples that can reside in the CPU caches. rectory. This is done asynchronously and does not have a significant On the write-heavy workload, the NVM-aware engines perform impact on the throughput of the DBMS. 17–48% fewer stores compared to their traditional counterparts. We attribute this to their lightweight durability mechanisms and smaller YCSB: The results in Fig. 12a show the recovery measurements storage footprints that enable them to make better use of hardware for the YCSB benchmark. We do not show the CoW and NVM- caches. Even with increased workload skew, the NVM-aware en- CoW engines as they never need to recover. We observe that the gines perform 9–41% fewer NVM writes. We note that the NVM latency of the InP and Log engines grows linearly with the number accesses performed by the storage engines correlate inversely with of transactions that need to be recovered. This is because these en- the throughput delivered by these engines as shown in Section 5.2. gines first redo the effects of committed transactions before undoing the effects of uncommitted transactions. In contrast, the NVM-InP TPC-C: Fig. 11 presents the NVM accesses performed while and NVM-Log engines’ recovery time is independent of the number executing the TPC-C benchmark. NVM-aware engines perform of transactions executed. These engines only need to undo the ef- 31–42% fewer writes compared to the traditional engines. We see fects of transactions that are active at the time of failure and not the that the access patterns are similar to that observed with the write- ones since the last checkpoint or flush. The NVM-aware engines intensive workload mixture in the YCSB benchmark. The Log therefore have a short recovery that is always less than a second. engine performs more writes in this benchmark compared to the YCSB benchmark because it has more indexes. This means that TPC-C: The results for the TPC-C benchmark are shown in updating a tuple requires updating several indexes as well. Fig. 12b. The recovery latency of the NVM-InP and NVM-Log en- gines is slightly higher than that in the YCSB benchmark because the 716 

11 . Storage Recovery Index Other 100 100 100 100 80 80 80 80 Time (%) Time (%) Time (%) Time (%) 60 60 60 60 40 40 40 40 20 20 20 20 0 0 0 0 InP W g NV -InP NV CoW g InP W g NV -InP NV CoW g InP W g NV -InP NV CoW g InP W g NV -InP NV CoW g Lo Lo Lo Lo Lo Lo Lo Lo Co Co Co Co M- M- M- M- M M M M M- M- M- M- NV NV NV NV (a) Read-only Workload (b) Read-heavy Workload (c) Balanced Workload (d) Write-heavy Workload Figure 13: Execution Time Breakdown – The time that the engines spend in their internal components when running the YCSB benchmark. TPC-C transactions perform more operations. However, the latency Table Index Log Checkpoint Other is still independent of the number of transactions executed unlike the traditional engines because the NVM-aware engines ensure that 6.0 6.0 Storage (GB) Storage (GB) the effects of committed transactions are persisted immediately. 4.5 4.5 5.5 Execution Time Breakdown 3.0 3.0 In this experiment, we analyze the time that the engines spend 1.5 1.5 in their internal components during execution. We only examine 0.0 0.0 YCSB with low skew and low NVM latency configuration, which InP W g NV -InP NV -CoW g InP W g NV -InP NV CoW g Lo Lo Lo Lo Co Co M- M- allows us to better understand the benefits and limitations of our M M M- M NV NV implementations. We use event-based sampling with the perf frame- work [3] to track the cycles executed within the engine’s components. (a) YCSB Storage (b) TPC-C Storage We start this profiling after loading the initial database. Figure 14: Storage Footprint – The amount of storage occupied in NVM The engine’s cycles are classified into four categories: (1) storage by the internal components of the engines. management operations with the allocator and filesystem interfaces, (2) recovery mechanisms like logging, (3) index accesses and main- 5.6 Storage Footprint tenance, and (4) other miscellaneous components. This last category Lastly, we compare the engines’ usage of NVM storage at run- is different for each engine; it includes the time spent in synchroniz- time. The storage footprint of an engine is the amount of space that ing the engine’s components and performing engine-specific tasks, it uses for storing tables, logs, indexes, and other internal data struc- such as compaction in case of the Log and NVM-Log engines. As tures. This metric is important because we expect that the first NVM our testbed uses a lightweight concurrency control mechanism, these products will initially have a higher cost than current storage tech- results do not contain any overhead from locking or latching [59]. nologies [39]. For this experiment, we periodically collect statistics The most notable result for this experiment, as shown in Fig. 13, maintained by our allocator and the filesystem meta-data during the is that on the write-heavy workload, the NVM-aware engines only workload execution. This is done after loading the initial database spend 13–18% of their time on recovery-related tasks compared for each benchmark. We then report the peak storage footprint of to the traditional engines that spend as much as 33% of their time each engine. For all of the engines, we allow their background on them. We attribute this to the lower logging overhead in the processes (e.g., group commit, checkpointing, garbage collection, case of the NVM-InP and NVM-Log engines, and the reduced cost compaction) to execute while we collect these measurements. of committing the dirty directory in the NVM-CoW engine. We observe that the proportion of the time that the engines spend on YCSB: We use the balanced workload mixture and low skew recovery mechanisms increases as the workload becomes write- setting for this experiment. The initial size of the database is 2 GB. intensive. This explains why the benefits of our optimizations are The results shown in Fig. 14a indicate that the CoW engine has the more prominent for the balanced and write-heavy workloads. largest storage footprint. Since this workload contains transactions These results highlight the benefits of optimizing the memory that modify the database and tuples are accessed more uniformly, allocator to leverage NVM’s characteristics. This is because the this engine incurs high overhead from continually creating new NVM-aware engines spend most of their time performing storage dirty directories and copying tuples. The InP and Log engines rely management operations since their recovery mechanisms are so on logging to improve their recovery latency at the expense of a efficient. Interestingly, the engines performing copy-on-write up- larger storage footprint. The InP engine checkpoints have a high dates spend a higher proportion of time on recovery-related tasks compression ratio and therefore consume less space. compared to other engines, particularly on the read-heavy work- The NVM-aware engines have smaller storage footprints com- load. This highlights the cost of creating and maintaining the dirty pared to the traditional engines. This is because the NVM-InP and directory for large databases, even using an efficient CoW B+tree. NVM-Log engines only record non-volatile pointers to tuples and Another observation from Fig. 13 is that the Log and NVM-Log non-inlined fields in the WAL. As such, they consume 17–21% engines spend a higher fraction of their time accessing and maintain- less storage space than their traditional counterparts. For the CoW ing indexes. This is because they perform multiple index look-ups engine, its large storage footprint is due to duplicated data in its on the LSM tree to reconstruct tuples. We observe that the NVM- internal cache. In contrast, the NVM-CoW engine accesses the Log engine spends less time performing the compaction process non-volatile copy-on-write B+tree directly using the allocator inter- compared to the Log engine. This is due to the reduced overhead of face, and only records non-volatile tuple pointers in this tree and not maintaining the MemTables using the allocator interface. entire tuples. This allows it to use 25% less storage space. 717 

12 . TPC-C: The graph in Fig. 14b shows the storage footprint of number of write barriers required for ensuring correct ordering [53]. the engines while executing TPC-C. For this benchmark, the initial This work is based on the Shore-MT engine [37], which means that size of the database is 1 GB and it grows to 2.4 GB. Transactions the DBMS records page-level before-images in the undo logs before inserting new tuples increase the size of the internal data structures performing in-place updates. This results in high data duplication. in the CoW and Log engines (i.e., the copy-on-write B+trees and Wang et al. present a passive group commit method for a dis- the SSTables stored in the filesystem). By avoiding unnecessary tributed logging protocol extension to Shore-MT [65]. Instead of data duplication using NVM’s persistence property, the NVM-aware issuing a barrier for every processor at commit time, the DBMS engines have 31–38% smaller storage footprints. The space savings tracks when all of the records required to ensure the durability of a are more significant in this benchmark because the workload is transaction are flushed to NVM. This approach is similar to other write-intensive with longer running transactions. Thus, the logs in work on a log manager that directly writes log records to NVM, and the InP and the Log engines grow more quickly compared to the addresses the problems of detecting partial writes and recoverabil- small undo logs in their NVM-aware counterparts. ity [28]. Both of these projects rely on software-based simulation of a NVM + DRAM system. 5.7 Discussion MARS [17] is an in-place updates engine optimized for NVM Our analysis shows that the NVM access latency has the most that relies on a hardware-assisted primitive that allows multiple impact on the runtime performance of the engines, more so than the writes to arbitrary locations to happen atomically. MARS does away amount of skew or the number of modifications to the database in the with undo log records by keeping the changes isolated using this workload. This difference due to latency is more pronounced with primitive. Similarly, it relies on this primitive to apply the redo log the NVM-aware variants; their absolute throughput is better than the records at the time of commit. In comparison, our NVM-InP engine traditional engines, but longer latencies cause their performance to is based on non-volatile pointers, a software-based primitive. It drop more significantly. This behavior is because they are no longer removes the need to maintain redo information in the WAL, but still bottlenecked by heavyweight durability mechanisms [23]. needs to maintain undo log records until the transaction commits. The NVM-aware engines also perform fewer store operations, SOFORT [51] is a hybrid storage engine designed for a storage which will help extend NVM device lifetimes. We attribute this hierarchy with both NVM and DRAM. The engine is designed to not to the reduction in redundant data that the engines store when a perform any logging and uses MVCC. Similar to SOFORT, we make transaction modifies the database. Using the allocator interface with use of non-volatile pointers [58]. Our usage of persistent pointers non-volatile pointers for internal data structures also allows them is different. Their persistent pointer primitive is a combination of to have a smaller storage footprint. This in turn avoids polluting page ID and offset. We eschew the page abstraction in our engines, the CPU’s caches with unnecessary copying and transformation as NVM is byte-addressable. Hence, we use raw NVM pointers operations. It also improves the recovery times of the engines that to build non-volatile data structures. For example, the engines use a WAL since they no longer record redo information. performing in-place and log-structured updates need to perform Overall, we find that the NVM-InP engine performs the best undo logging, which is where we use non-volatile pointers to reduce across a wide set of workload mixtures and skew settings for all data duplication. NVM latency configurations. The NVM-CoW engine did not per- Beyond DBMSs, others have looked into using NVM in filesys- form as well for write-intensive workloads, but may be a better fit for tems. BPFS is a filesystem designed for persistent memory [19]. It DBMSs that support non-blocking read-only transactions. For the uses a variant of shadow paging that supports atomic updates by NVM-Log engine, many of its design assumptions are not copacetic relying on a special hardware instruction that ensures ordering be- for a single-tier storage hierarchy. The engine is essentially perform- tween writes in different epochs. PMFS is another filesystem from ing in-place updates like the NVM-InP engine but with additional Intel Labs that is designed for byte-addressable NVM [27]. It relies overhead of maintaining its legacy components. on write-ahead logging to preserve meta-data consistency and uses shadow paging only for data. It assumes a simpler hardware barrier 6. RELATED WORK primitive than epochs. Further, it optimizes memory-mapped I/O by directly mapping the persistent memory to the application’s ad- We now discuss previous research on using NVM. SafeRAM [21] dress space. The filesystem interface used by the traditional storage is one of the first projects that explored the use of NVM in software engines in our DBMS testbed is backed by PMFS. applications. Using simulations, they evaluated the improvement in throughput and latency of OLTP workloads when disk is replaced by battery-backed DRAM. Later work demonstrated the utility of 7. CONCLUSION NVM in a client-side cache for distributed filesystems [8]. This paper explored the fundamentals of storage and recovery Recently, several application-level APIs for programming with methods in OLTP DBMSs running on an NVM-only storage hier- persistent memory have been proposed. Mnemosyne [64] and NV- archy. We implemented three storage engines in a modular DBMS heaps [18] use software transactional memory to support transac- testbed with different architectures: (1) in-place updates, (2) copy- tional updates to data stored on NVM. NVMalloc [49] is a memory on-write updates, and (3) log-structured updates. We then developed allocator that considers wear leveling of NVM. The primitives pro- optimized variants of each of these engines that better make use of vided by these systems allow programmers to use NVM in their NVM’s characteristics. Our experimental analysis with two different applications but do not provide the transactional semantics required OLTP workloads showed that our NVM-aware engines outperform by a DBMS. the traditional engines by up to 5.5× while reducing the number of In the context of DBMSs, recent work demonstrated that memory- writes to the storage device by more than half on write-intensive oriented DBMSs perform only marginally better than disk-oriented workloads. We found that the NVM access latency has the most DBMSs when using NVM because both systems still assume that impact on the runtime performance of the engines, more so than the memory is volatile [24]. Others have developed new recovery mech- workload skew or the number of modifications to the database in anisms for DBMSs that are using a NVM + DRAM storage hier- the workload. Our evaluation showed that the NVM-aware in-place archy [53, 30, 17, 65]. Pelley et al. introduce a group commit updates engine achieved the best throughput among all the engines mechanism to persist transactions’ updates in batches to reduce the with the least amount of wear on the NVM device. 718 

13 .8. REFERENCES [21] G. Copeland, T. Keller, R. Krishnamurthy, and M. Smith. The case for safe ram. VLDB, pages 327–335. Morgan Kaufmann Publishers Inc., 1989. [1] Apache Cassandra. [22] J. Dean and S. Ghemawat. LevelDB. http://datastax.com/documentation/cassandra/2.0/. http://leveldb.googlecode.com. [2] Intel Architecture Instruction Set Extensions Programming [23] J. DeBrabant, J. Arulraj, A. Pavlo, M. Stonebraker, S. Zdonik, Reference. https://software.intel.com/sites/ and S. Dulloor. A prolegomenon on OLTP database systems default/files/managed/0d/53/319433-022.pdf. for non-volatile memory. In ADMS@VLDB, 2014. [3] Linux perf framework. [24] J. DeBrabant, A. Pavlo, S. Tu, M. Stonebraker, and S. Zdonik. https://perf.wiki.kernel.org/index.php/Main_Page. Anti-caching: A new approach to database management [4] NUMA policy library. system architecture. Proc. VLDB Endow., 6(14):1942–1953, http://linux.die.net/man/3/numa. Sept. 2013. [5] VoltDB. http://voltdb.com. [25] D. J. DeWitt, R. H. Katz, F. Olken, L. D. Shapiro, M. R. [6] AGIGARAM. DDR3 NVDIMM. Stonebraker, and D. Wood. Implementation techniques for http://www.agigatech.com/ddr3.php. main memory database systems. SIGMOD Rec., 14(2):1–8, [7] M. M. Astrahan, M. W. Blasgen, D. D. Chamberlin, K. P. 1984. Eswaran, J. N. Gray, P. P. Griffiths, W. F. King, R. A. Lorie, [26] A. Driskill-Smith. Latest advances and future prospects of P. R. McJones, J. W. Mehl, G. R. Putzolu, I. L. Traiger, B. W. STT-RAM. In Non-Volatile Memories Workshop, 2010. Wade, and V. Watson. System R: relational approach to [27] S. R. Dulloor, S. K. Kumar, A. Keshavamurthy, P. Lantz, database management. ACM Trans. Database Syst., D. Subbareddy, R. Sankaran, and J. Jackson. System software 1(2):97–137, June 1976. for persistent memory. In EuroSys, 2014. [8] M. Baker, S. Asami, E. Deprit, J. Ousterhout, and M. Seltzer. [28] R. Fang, H.-I. Hsiao, B. He, C. Mohan, and Y. Wang. High Non-volatile memory for fast, reliable file systems. In performance database logging using storage class memory. ASPLOS, pages 10–22, 1992. ICDE, pages 1221–1231, 2011. [9] P. A. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency [29] M. Franklin. Concurrency control and recovery. The Computer Control and Recovery in Database Systems. Addison-Wesley Science and Engineering Handbook, pages 1058–1077, 1997. Longman Publishing Co., Inc., Boston, MA, USA, 1986. [30] S. Gao, J. Xu, B. He, B. Choi, and H. Hu. PCMLogging: [10] T. Bingmann. STX B+ tree C++ template classes. Reducing transaction logging overhead with pcm. CIKM, http://panthema.net/2007/stx-btree/. pages 2401–2404, 2011. [11] M. Bjørling, P. Bonnet, L. Bouganim, and N. Dayan. The [31] H. Garcia-Molina and K. Salem. Main memory database necessary death of the block device interface. In CIDR, 2013. systems: An overview. IEEE Trans. on Knowl. and Data Eng., [12] B. H. Bloom. Space/time trade-offs in hash coding with pages 509–516, 1992. allowable errors. Commun. ACM, 1970. [32] D. Gawlick and D. Kinkade. Varieties of concurrency control [13] G. W. Burr, B. N. Kurdi, J. C. Scott, C. H. Lam, in IMS/VS Fast Path. Technical report, Tandem, 1985. K. Gopalakrishnan, and R. S. Shenoy. Overview of candidate [33] J. Gray, P. McJones, M. Blasgen, B. Lindsay, R. Lorie, device technologies for storage-class memory. IBM J. Res. T. Price, F. Putzolu, and I. Traiger. The recovery manager of Dev., 52(4):449–464, July 2008. the system R database manager. ACM Comput. Surv., [14] J. Chang, P. Ranganathan, T. Mudge, D. Roberts, M. A. Shah, 13(2):223–242, June 1981. and K. T. Lim. A limits study of benefits from [34] R. A. Hankins and J. M. Patel. Effect of node size on the nanostore-based future data-centric system architectures. CF performance of cache-conscious b+-trees. SIGMETRICS ’03, ’12, pages 33–42, 2012. pages 283–294, 2003. [15] F. Chen, M. Mesnier, and S. Hahn. A protected block device [35] S. Harizopoulos, D. J. Abadi, S. Madden, and M. Stonebraker. for persistent memory. In 30th Symposium on Mass Storage OLTP through the looking glass, and what we found there. In Systems and Technologies (MSST), 2014. SIGMOD, pages 981–992, 2008. [16] H. Chu. MDB: A Memory-Mapped Database and Backend for [36] M. Hedenfalk. Copy-on-write B+ Tree. OpenLDAP. Technical report, OpenLDAP, 2011. http://www.bzero.se/ldapd/. [17] J. Coburn, T. Bunker, M. Schwarz, R. Gupta, and S. Swanson. [37] R. Johnson, I. Pandis, N. Hardavellas, A. Ailamaki, and From ARIES to MARS: Transaction support for B. Falsafi. Shore-MT: a scalable storage manager for the next-generation, solid-state drives. In Proceedings of the multicore era. In EDBT, pages 24–35, 2009. Twenty-Fourth ACM Symposium on Operating Systems [38] N. P. Jouppi. Cache write policies and performance. In Principles, SOSP ’13, pages 197–212, 2013. Proceedings of the 20th Annual International Symposium on [18] J. Coburn, A. M. Caulfield, A. Akel, L. M. Grupp, R. K. Computer Architecture, ISCA, 1993. Gupta, R. Jhala, and S. Swanson. Nv-heaps: making persistent [39] H. Kim, S. Seshadri, C. L. Dickey, and L. Chiu. Evaluating objects fast and safe with next-generation, non-volatile phase change memory for enterprise storage systems: A study memories. In ASPLOS, pages 105–118. ACM, 2011. of caching and tiering approaches. In Proceedings of the 12th [19] J. Condit, E. B. Nightingale, C. Frost, E. Ipek, B. Lee, USENIX Conference on File and Storage Technologies (FAST D. Burger, and D. Coetzee. Better I/O through 14), 2014. byte-addressable, persistent memory. In SOSP, pages [40] B. Kuszmaul. A Comparison of Fractal Trees to 133–146, 2009. Log-Structured Merge (LSM) Trees. Technical report, [20] B. F. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and Tokutek, 2014. R. Sears. Benchmarking cloud serving systems with YCSB. In SoCC, pages 143–154, 2010. 719 

14 .[41] D. Laney. 3-D data management: Controlling data volume, [61] The Transaction Processing Council. TPC-C Benchmark velocity and variety. Feb. 2001. (Revision 5.9.0). http://www.tpc.org/tpcc/, June 2007. [42] C. Lefurgy, K. Rajamani, F. Rawson, W. Felter, M. Kistler, [62] S. Venkataraman, N. Tolia, P. Ranganathan, and R. H. and T. W. Keller. Energy management for commercial servers. Campbell. Consistent and durable data structures for Computer, 36(12). non-volatile byte-addressable memory. In FAST, 2011. [43] LevelDB. Implementation details of LevelDB. https: [63] V. Viswanathan, K. Kumar, and T. Willhalm. Intel Memory //leveldb.googlecode.com/svn/trunk/doc/impl.html. Latency Checker. https://software.intel.com/en-us/ [44] P. Macko. A simple PCM block device simulator for Linux. articles/intelr-memory-latency-checker. https://code.google.com/p/pcmsim/people/list. [64] H. Volos, A. J. Tack, and M. M. Swift. Mnemosyne: [45] N. Malviya, A. Weisberg, S. Madden, and M. Stonebraker. lightweight persistent memory. In R. Gupta and T. C. Mowry, Rethinking main memory OLTP recovery. In ICDE, 2014. editors, ASPLOS, pages 91–104. ACM, 2011. [46] J. A. Mandelman, R. H. Dennard, G. B. Bronner, J. K. [65] T. Wang and R. Johnson. Scalable logging through emerging DeBrosse, R. Divakaruni, Y. Li, and C. J. Radens. Challenges non-volatile memory. PVLDB, 7(10):865–876, 2014. and future directions for the scaling of dynamic [66] J. H. Yoon, H. C. Hunter, and G. A. Tressler. Flash & dram si random-access memory (DRAM). IBM J. Res. Dev., 46(2-3). scaling challenges, emerging non-volatile memory technology [47] C. Mohan, D. Haderle, B. Lindsay, H. Pirahesh, and enablement - implications to enterprise storage and server P. Schwarz. ARIES: a transaction recovery method supporting compute systems. Flash Memory Summit, aug 2013. fine-granularity locking and partial rollbacks using write-ahead logging. ACM Trans. Database Syst., 17(1):94–162, 1992. APPENDIX [48] D. Molka, D. Hackenberg, R. Schone, and M. S. Muller. Memory performance and cache coherency effects on an intel A. ANALYTICAL COST MODEL nehalem multiprocessor system. PACT ’09, pages 261–270. In this section, we present a cost model to estimate the amount [49] I. Moraru, D. Andersen, M. Kaminsky, N. Tolia, of data written to NVM per operation, by the traditional and NVM- P. Ranganathan, and N. Binkert. Consistent, durable, and safe optimized storage engines. This model highlights the strengths and memory management for byte-addressable non volatile main weaknesses of these engines. memory. In TRIOS, 2013. We begin the analysis by stating the assumptions we use to sim- [50] P. O’Neil, E. Cheng, D. Gawlick, and E. O’Neil. The plify the model. First, the database operations are presumed to be log-structured merge-tree (lsm-tree). Acta Inf., 33(4):351–385, always successful. The amount of data written to NVM while per- June 1996. forming an aborted operation will depend on the stage at which the operation fails. We therefore restrict our analysis to only successful [51] I. Oukid, D. Booss, W. Lehner, P. Bumbulis, and T. Willhalm. operations. Second, the engines handle fixed-length and variable- SOFORT: A hybrid SCM-DRAM storage engine for fast data length tuple fields differently. The fixed-length fields are stored recovery. DaMoN, pages 8:1–8:7, 2014. in-line, while the variable-length fields are stored separately. To [52] A. Pavlo, C. Curino, and S. Zdonik. Skew-aware automatic illustrate this difference, we assume that the update operation alters database partitioning in shared-nothing, parallel OLTP one fixed-length field and one variable-length field. Note that the tu- systems. In SIGMOD, pages 61–72, 2012. ple itself can contain any number of fixed-length and variable-length [53] S. Pelley, T. F. Wenisch, B. T. Gold, and B. Bridge. Storage fields depending on the database schema. management in the NVRAM era. PVLDB, 7(2):121–132, Let us now describe some notation. We denote the size of the 2013. tuple by T . This depends on the specific table on which the engine [54] T. Perez and C. Rose. Non-volatile memory: Emerging performs the database operation. Let the size of the fixed-length technologies and their impact on memory systems. PURCS field and the variable-length field altered by the update operation Technical Report, 2010. be F and V , respectively. These parameters depend on the table [55] S. Raoux, G. Burr, M. Breitwisch, C. Rettner, Y. Chen, columns that are modified by the engine. The size of a pointer is R. Shelby, M. Salinga, D. Krebs, S.-H. Chen, H.-L. Lung, and represented by p. The NVM-optimized engines use non-volatile C. Lam. Phase-change random access memory: A scalable pointers to tuples and variable-length tuple fields to reduce data technology. IBM Journal of Research and Development, duplication. We use θ to denote the write-amplification factor of the 52(4.5):465–479, 2008. engines performing log-structured updates. θ could be attributed to [56] O. Rodeh. B-trees, shadowing, and clones. Trans. Storage, the periodic compaction mechanism that these engines perform to pages 2:1–2:27, 2008. bound read-amplification and depends on the type of LSM tree. Let [57] M. Rosenblum and J. K. Ousterhout. The design and B represent the size of a node in the CoW B+tree used by the CoW implementation of a log-structured file system. ACM Trans. and NVM-CoW engines. We indicate small fixed-length writes to Comput. Syst., 10(1):26–52, Feb. 1992. NVM, such as those used to maintain the status of tuple slots, by ε. [58] A. Rudoff. Persistent memory library. https://github.com/ Given this notation, we present the cost model in Table 3. The pmem/linux-examples/tree/master/libpmem. data written to NVM is classified into three categories: (1) memory, [59] M. Stonebraker, S. Madden, D. J. Abadi, S. Harizopoulos, (2) log, and (3) table storage. We now describe some notable entries N. Hachem, and P. Helland. The end of an architectural era: in the table. While performing an insert operation, the InP engine (it’s time for a complete rewrite). In VLDB, pages 1150–1160, writes three physical copies of a tuple. In contrast, the NVM-InP en- 2007. gine only records the tuple pointer in the log and table data structures [60] D. B. Strukov, G. S. Snider, D. R. Stewart, and R. S. Williams. on NVM. In the case of the CoW and NVM-CoW engines, there The missing memristor found. Nature, (7191):80–83, 2008. are two possibilities depending on whether a copy of the relevant B+tree node is absent or present in the dirty directory. For the latter, the engines do not need to make a copy of the node before applying 720 

15 . Insert Update Delete Memory :T Memory :F+V Memory :ε InP Log :T Log :2×(F+V) Log :T Table :T Table :F+V Table :ε Memory :B+T T Memory :B+F+V F+V Memory :B+ε ε CoW Log :0 Log :0 Log :0 Table :B T Table :B F+V Table :B ε Memory :T Memory :F+V Memory :ε Log Log :T Log :2*(F+V) Log :T Table :θ ×T Table :θ ×(F+V) Table :ε Memory :T Memory :F+V+p Memory :ε NVM-InP Log :p Log :F+p Log :p Table :p Table :0 Table :ε Memory :T Memory :T+F+V Memory :ε NVM-CoW Log :0 Log :0 Log :0 Table :B+p p Table :B+p p Table :B+ε ε Memory :T Memory :F+V+p Memory :ε NVM-Log Log :p Log :F+p Log :p Table :θ ×T Table :θ ×(F+p) Table :ε Table 3: Analytical cost model for estimating the amount of data written to NVM, while performing insert, update, and delete operations, by each engine. the desired transformation. We distinguish these two cases in the engines. These extensions have been added by Intel in late 2014 relevant table entries using vertical bars. Note that these engines and are not currently commercially available. As we describe in have no logging overhead as they always apply modifications in the Section 2.3, we currently implement the sync primitive using the dirty directory. The performance gap between the traditional and the SFENCE and CLFLUSH instructions. We believe that these new ex- NVM-optimized engines, particularly for write-intensive workloads, tensions, such as the PCOMMIT and CLWB instructions [2], can be directly follows from the cost model presented in the table. used to ensure the correctness and improve the performance of this primitive in future processors because they are more efficient and B. IMPACT OF B+TREE NODE SIZE provide better control for how a DBMS interacts with NVM. We examine the sensitivity of our experimental results to size of The PCOMMIT instruction guarantees the durability of stores to the B+tree nodes in this section. The engines performing in-place persistent memory. When the data is written back from the CPU and log-structured updates use the STX B+tree [10] for maintaining caches, it can still reside in the volatile buffers on the memory indexes, while the engines performing copy-on-write updates use controller. After the PCOMMIT instruction is executed, the store must the append-only B+tree [56, 16, 36] for storing the directories. In become persistent. The CLWB instruction writes back a target cache all our experiments, we use the default node size for both the STX line to NVM similar to the CLFLUSH instruction. It is, however, B+tree (512 B) and copy-on-write B+tree (4 KB) implementations. different in two ways: (1) it is a weakly-ordered instruction and can For this analysis, we vary the B+tree node size and examine the thus perform better than the strongly-ordered CLFLUSH instruction, impact on the engine’s throughput, while executing different YCSB and (2) it can retain a copy of the line in the cache hierarchy in workloads under low NVM latency (2×) and low workload skew exclusive state, thereby reducing the possibility of cache misses settings. We restrict our analysis to the NVM-aware engines as they during subsequent accesses. In contrast, the CLFLUSH instruction are representative of other engines. always invalidates the cacheline, which means that data has to be The graphs, shown in Fig. 15, indicate that the impact of B+tree retrieved again from NVM. node size is more significant for the CoW B+tree than the STX To understand the performance impact of the sync primitive com- B+tree. In case of the CoW B+tree, we observe that increasing prising of PCOMMIT and CLWB instructions, we emulate its latency us- the node size improves the engine’s performance on read-heavy ing RDTSC and PAUSE instructions. We note that our software-based workloads. This can be attributed to smaller tree depth, which in latency emulation does not capture all the complex interactions in turn reduces the amount of indirection in the data structure. It also real processors. However, it still allows us to perform a useful what- reduces the amount of metadata that needs to be flushed to NVM if analysis before these instruction set extensions are available. We to ensure recoverability. However, the engine’s performance on vary the latency of the sync primitive from 10–10000 ns and com- write-heavy workloads drops as the B+tree nodes get larger. This pare it with the currently used sync primitive. Since the traditional is because of the copying overhead when performing updates in engines use PMFS [27], which is loaded in as a kernel module, they the dirty directory of the CoW B+tree. We found that the engines require more changes for this experiment. We therefore restrict our performing copy-on-write updates perform well on both types of analysis to the NVM-aware engines. We execute different YCSB workloads when the node size is 4 KB. With the STX B+tree, our workloads under low NVM latency (2×) and low workload skew experiments suggest that the optimal node size is 512 B. This set- settings. ting provides a nice balance between cache misses, instructions The results in Fig. 16 show that the engines are sensitive to the executed, TLB misses, and space utilization [34]. Hence, in all of performance of the sync primitive. Performance measurements of our experiments in Section 5, we configured the B+trees used by all the engines while using the current sync primitive are shown on the the engines to their optimal performance settings. left side of each graph to serve as a baseline. We observe that the throughput of all the engines drops significantly with the increasing C. NVM INSTRUCTION SET EXTENSIONS sync primitive latency. This is expected as these engines make ex- tensive use of this primitive in their non-volatile data structures. The In this section, we explore the impact of newly proposed NVM- impact is therefore more pronounced on write-intensive workloads. related instruction set extensions [2] on the performance of the 721 

16 . Read-Only Read-Heavy Balanced Write-Heavy Throughput (txn/sec) Throughput (txn/sec) Throughput (txn/sec) 2000000 2000000 2000000 1500000 1500000 1500000 1000000 1000000 1000000 500000 500000 500000 0 0 0 64 128 256 512 1024 2048 512 1024 2048 4096 8192 16384 64 128 256 512 1024 2048 B+tree node size (bytes) B+tree node size (bytes) B+tree node size (bytes) (a) NVM-InP engine (STX B+tree) (b) NVM-CoW engine (CoW B+tree) (c) NVM-Log engine (STX B+tree) Figure 15: B+Tree Node Size – The impact of B+tree node size on the performance of the NVM-aware engines. The engines run the YCSB workloads under low NVM latency (2×) and low skew settings. Throughput (txn/sec) Throughput (txn/sec) Throughput (txn/sec) 1600000 1600000 1600000 1200000 1200000 1200000 800000 800000 800000 400000 400000 400000 0 0 0 Current 10 100 1000 10000 Current 10 100 1000 10000 Current 10 100 1000 10000 Sync primitive latency (ns) Sync primitive latency (ns) Sync primitive latency (ns) (a) NVM-InP engine (b) NVM-CoW engine (c) NVM-Log engine Figure 16: NVM Instruction Set Extensions – The impact of sync primitive latency on the performance of the NVM-aware engines. The engines run the YCSB workloads under low NVM latency (2×) and low skew settings. Performance obtained using the current primitive, built using the SFENCE and CLFLUSH instructions, is shown on the left side of each graph to serve as a baseline. We note that the NVM-CoW engine is slightly less sensitive to to run on that storage hierarchy. There are several other aspects latency of the sync primitive than the NVM-InP and NVM-Log of DBMS architectures for NVM that we would like study further. engines. We attribute this to the fact that this engine primarily uses We plan to investigate concurrency control algorithms that are more data duplication to ensure recoverability and only uses the sync sophisticated than the scheme that we used in our testbed to see primitive to ensure the consistency of the CoW B+tree. In case of whether they can be made to scale on a NVM-based system. In the NVM-Log engine, its performance while executing the write- particular, we are interested in exploring methods for supporting heavy workload is interesting. Its throughput becomes less than the hybrid workloads (i.e., OLTP + OLAP) on NVM. throughput on the balanced workload only when the latency of the We will evaluate state-of-the-art index data structures to under- sync primitive is above 1000 ns. This is because the engine needs stand whether their trade-offs are appropriate for NVM (e.g., wear- to reconstruct tuples from entries spread across different LSM tree leveling) and adapt them to exploit its persistence properties. We components. also anticipate the need for techniques to protect the contents of We conclude that the trade-offs that we identified in these NVM- the database from errant code running and prevent the DBMS from aware engines in the main body of the paper still hold at higher corrupting the database by modifying a location in NVM that it sync primitive latencies. Overall, we believe that these new in- should not. structions will be required to ensure recoverability and improve the performance of future NVM-aware DBMSs. E. ACKNOWLEDGEMENTS This work was supported (in part) by the Intel Science and Tech- D. FUTURE WORK nology Center for Big Data and the U.S. National Science Foun- A hybrid DRAM and NVM storage hierarchy is a viable alter- dation (CCF-1438955). All of you need to recognize how Jignesh native, particularly in case of high NVM latency technologies and Patel be tearing through bits with QuickStep like he’s slinging rocks analytical workloads. We plan to expand our NVM-aware engines at less than retail. Respect in the 608. Word is bond. 722