A New Approach to Database Management System Architecture

1 . Anti-Caching: A New Approach to Database Management System Architecture Justin DeBrabant Andrew Pavlo Stephen Tu Brown University Brown University MIT CSAIL debrabant@cs.brown.edu pavlo@cs.brown.edu stephentu@csail.mit.edu Michael Stonebraker Stan Zdonik MIT CSAIL Brown University stonebraker@csail.mit.edu sbz@cs.brown.edu ABSTRACT DBMSs invariably maintain a buffer pool of blocks in main mem- The traditional wisdom for building disk-based relational database ory for faster access. When an executing query attempts to read a management systems (DBMS) is to organize data in heavily-encoded disk block, the DBMS first checks to see whether the block already blocks stored on disk, with a main memory block cache. In order to exists in this buffer pool. If not, a block is evicted to make room improve performance given high disk latency, these systems use a for the needed one. There is substantial overhead to managing the multi-threaded architecture with dynamic record-level locking that buffer pool, since blocks have to be pinned in main memory and the allows multiple transactions to access the database at the same time. system must maintain an eviction order policy (e.g., least recently Previous research has shown that this results in substantial over- used). As noted in [15], when all data fits in main memory, the head for on-line transaction processing (OLTP) applications [15]. cost of maintaining a buffer pool is nearly one-third of all the CPU The next generation DBMSs seek to overcome these limitations cycles used by the DBMS. with architecture based on main memory resident data. To over- The expense of managing disk-resident data has fostered a class come the restriction that all data fit in main memory, we propose of new DBMSs that put the entire database in main memory and a new technique, called anti-caching, where cold data is moved thus have no buffer pool [11]. TimesTen was an early proponent of to disk in a transactionally-safe manner as the database grows in this approach [31], and more recent examples include H-Store [2, size. Because data initially resides in memory, an anti-caching ar- 18], MemSQL [3], and RAMCloud [25]. H-Store (and its com- chitecture reverses the traditional storage hierarchy of disk-based mercial version VoltDB [4]) performs significantly better than disk- systems. Main memory is now the primary storage device. based DBMSs on standard OLTP benchmarks [29] because of this We implemented a prototype of our anti-caching proposal in a main memory orientation, as well as from avoiding the overhead of high-performance, main memory OLTP DBMS and performed a concurrency control and heavy-weight data logging [22]. series of experiments across a range of database sizes, workload The fundamental problem with main memory DBMSs, however, skews, and read/write mixes. We compared its performance with an is that this improved performance is only achievable when the database open-source, disk-based DBMS optionally fronted by a distributed is smaller than the amount of physical memory available in the sys- main memory cache. Our results show that for higher skewed tem. If the database does not fit in memory, then the operating workloads the anti-caching architecture has a performance advan- system will start to page virtual memory, and main memory ac- tage over either of the other architectures tested of up to 9⇥ for a cesses will cause page faults. Because page faults are transparent data size 8⇥ larger than memory. to the user, in this case the main memory DBMS, the execution of transactions is stalled while the page is fetched from disk. This is a significant problem in a DBMS, like H-Store, that executes transac- 1. INTRODUCTION tions serially without the use of heavyweight locking and latching. Historically, the internal architecture of DBMSs has been pred- Because of this, all main memory DBMSs warn users not to ex- icated on the storage and management of data in heavily-encoded ceed the amount of real memory [5]. If memory is exceeded (or disk blocks. In most systems, there is a header at the beginning of if it might be at some point in the future), then a user must either each disk block to facilitate certain operations in the system. For (1) provision new hardware and migrate their database to a larger example, this header usually contains a “line table” at the front of cluster, or (2) fall back to a traditional disk-based system, with its the block to support indirection to tuples. This allows the DBMS to inherent performance problems. reorganize blocks without needing to change index pointers. When One widely adopted performance enhancer is to use a main mem- a disk block is read into main memory, it must then be translated ory distributed cache, such as Memcached [14], in front of a disk- into main memory format. based DBMS. Under this two-tier architecture, the application first Permission to make digital or hard copies of all or part of this work for looks in the cache for the tuple of interest. If this tuple is not in the personal or classroom use is granted without fee provided that copies are cache, then the application executes a query in the DBMS to fetch not made or distributed for profit or commercial advantage and that copies the desired data. Once the application receives this data from the bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific DBMS, it updates the cache for fast access in the future. Whenever permission and/or a fee. Articles from this volume were invited to present a tuple is modified in the database, the application must invalidate their results at The 39th International Conference on Very Large Data Bases, its cache entry so that the next time it is accessed the application August 26th - 31st 2013, Riva del Garda, Trento, Italy. will retrieve the current version from the DBMS. Many notable web Proceedings of the VLDB Endowment, Vol. 6, No. 14 Copyright 2013 VLDB Endowment 2150-8097/13/14... $ 10.00. 1942 

2 . Application 1 Application Application Check 3 Update Cache Cache Execute Txn Distributed 2Execute Query Execute Txn Cache Buffer Pool Buffer Pool Primary Storage Primary Storage Primary Storage Anti-Cache (a) Disk-oriented DBMS (b) Disk-oriented DBMS with a Distributed Cache (c) Main Memory DBMS with Anti-Caching Figure 1: DBMS Architectures – In (a) and (b), the disk is the primary storage for the database and data is brought into main memory as it is needed. With the anti-caching model shown in (c), memory is the primary storage and cold data is evicted to disk. sites, such as Facebook, use a large cluster of Memcached nodes in Fine-Grained Eviction: A key advantage of anti-caching over front of their sharded MySQL installation. virtual memory in the context of a main memory DBMS is the gran- There are two problems with this two-tier model. First, data ob- ularity at which data can be evicted. In anti-caching, eviction deci- jects may reside both in the cache (in main memory format) and sions are performed at the tuple-level. This means that the coldest in the DBMS buffer pool (in disk format). This double buffering tuples will be written to disk. In virtual memory, OS makes evic- of data is a waste of resources. The second issue is that it requires tion decisions at the page-level. A virtual memory page is likely developers to embed logic in their application to keep the two sys- to be significantly larger than a typical OLTP tuple. Thus, each tems independently synchronized. For example, when an object is page selected for eviction will contain multiple tuples, each with modified, the update is sent to the back-end DBMS. But now the potentially varying levels of coldness. A single hot tuple on a page states of the object in the DBMS and in the cache are different. If will cause the entire page to be hot and kept in memory, even if the the application requires up-to-date values, the application must also other tuples are cold. It is best to make evictions at the same level update the object in the cache. of granularity that the data is accessed, which in a DBMS is at the To overcome these problems, we present a new architecture for tuple level. Anti-caching provides a method for this finer-grained main memory DBMSs that we call anti-caching. In a DBMS with control of evicted data by building pages of cold tuples only. anti-caching, when memory is exhausted, the DBMS gathers the “coldest” tuples and writes them to disk with minimal translation Non-Blocking Fetches: Another difference is how evicted data from their main memory format, thereby freeing up space for more is retrieved when it is needed. In a virtual memory system, the OS recently accessed tuples. As such, the “hotter” data resides in main blocks a process when it incurs a page fault from reading a mem- memory, while the colder data resides on disk in the anti-cache por- ory address that is on disk. For certain DBMSs [29, 34], this means tion of the system. Unlike a traditional DBMS architecture, tuples that no transactions are executed while the virtual memory page is do not reside in both places; each tuple is either in memory or in a being fetched from disk. In an anti-caching DBMS, a transaction disk block, but never in both places at the same time. In this new that accesses evicted data is simply aborted and then restarted at a architecture, main memory, rather than disk, becomes the primary later point once the data that it needs is retrieved from disk. In the storage location. Rather than starting with data on disk and read- meantime, the DBMS continues to execute other transactions with- ing hot data into the cache, data starts in memory and cold data is out blocking. Lastly, since every page fault triggers a disk read, evicted to the anti-cache on disk. queries that access multiple evicted pages will page fault several This approach is similar to virtual memory swapping in operat- times in a sequential fashion. We instead use a pre-pass execution ing systems (OS). With virtual memory, when the amount of data phase that attempts to identify all evicted blocks needed by a trans- exceeds the amount of available memory, cold data is written out to action, which will allow all blocks to be read together [23]. disk in pages, typically in least recently used (LRU) order. When In this paper, we explore the details of our anti-caching proposal. the evicted page is accessed, it is read back in, possibly causing We have implemented a prototype in the H-Store DBMS [2] and other pages to be evicted. This allows the amount of virtual mem- performed a thorough experimental evaluation of the three different ory to exceed the amount of physical memory allocated to a pro- DBMS architectures depicted in Fig. 1: cess. Similarly, anti-caching allows the amount of data to exceed the available memory by evicting cold data to disk in blocks. If data 1. Traditional, disk-based DBMS (MySQL). access is skewed, the working set will remain in main memory. 2. Traditional, disk-based DBMS with a distributed cache front- With anti-caching, it is the responsibility of the DBMS to read end (MySQL + Memcached). and write data as needed. An alternative is to let the virtual mem- 3. Anti-caching in a main memory DBMS (H-Store). ory system do the paging of the data to and from disk. Indeed, this The results of these experiments show that the anti-caching ar- is the approach taken in [28]. However, anti-caching has several chitecture outperforms both the traditional disk-based and hybrid advantages over virtual memory in the context of a main memory architecture on popular OLTP workloads. The difference is even DBMS. In particular, it provides fine-grained control of the data more pronounced at higher skew levels, and demonstrates that main evicted to disk and non-blocking reads of evicted data from disk. memory databases designed around the anti-caching architecture These two main differences are described in detail below: 1943 

3 . Client Procedure Name Input Parameters procedure’s control code. H-Store assumes a workload of transac- Application tions with the following composition: Txn Coordinator Single-Partition Transactions: In this case, there is a database Core Core design that allocates the various partitions of each table to nodes in Execution Engine ... Execution Engine such a way that most transactions are local to a single node [26]. Looking up a banking account balance or a purchase order is an Partition Main Partition example of a single-partition transaction. Data Memory Data A single-partition transaction is examined in the user-space H- Store client library, where parameters are substituted to form a Figure 2: The H-Store Main Memory OLTP system. runnable transaction. The user-level library is aware of H-Store’s partitioning scheme [26], so the transaction can be sent to the cor- can scale to significantly larger than the available main memory rect node where it is executed from beginning to end without any while experiencing minor throughput degradation. blocking. Hence, single-partition transactions are serialized at each Our anti-cache design is based on two key assumptions. Fore- node, and any application that consists entirely of single-partition most is that our current prototype restricts the scope of queries to transactions will obtain maximum parallelism. fit in main memory. We do not consider this a significant hindrance, since such large queries are uncommon in OLTP workloads. The Multi-Partition Transactions: These transactions consist of mul- other design assumption is that all indexes fit in memory. The tiple phases, each of which must be completed before the next trade-offs of using large secondary indexes is a well-studied topic in phase begins. Moreover, one or more of the phases touches multi- database optimization and we do not believe that this requirement ple partitions. is overly restrictive. We propose alternative designs to obviate the Each H-Store transaction is given a unique transaction ID, based need to keep secondary indexes in memory. on the time it arrived in the system. Standard clock-skew algo- rithms are used to keep the various CPU clocks synchronized. If a transaction with a higher transaction ID has already arrived at a 2. H-STORE SYSTEM OVERVIEW node, then the incoming transaction is refused. In this way trans- actions are synchronized in timestamp order at the various nodes, Before discussing the details of our anti-caching model, we first without the need for any deadlock detection. Multi-Partition trans- review H-Store’s architecture and the motivations behind its de- actions use an extension of this protocol, where each local executor sign. In a disk-oriented DBMS, the system retrieves tuples from cannot run other transactions until the multi-partition transaction blocks on disk as they are requested by transactions. These blocks finishes execution. This scheme gives good throughput for work- are stored in an in-memory buffer pool. If a transaction invokes a loads with a preponderance of single-partition transactions. query that accesses data that is not in memory, the DBMS stalls that To ensure that all modifications to the database are durable and transaction until the block with that data is retrieved from disk and persistent, each DBMS node continuously writes asynchronous snap- added to the buffer pool. If the buffer pool is full, then the DBMS shots of the entire database to disk at fixed intervals [21, 29]. In chooses another block to evict to make room for the incoming one. between these snapshots, the DBMS writes out a record to a com- Since the transaction waits until this disk operation completes, such mand log for each transaction that completes successfully [22]. The systems employ a concurrency control scheme to allow other trans- DBMS combines multiple records together and writes them in a actions to execute while the stalled one is waiting for the disk. The group to amortize the cost of writing to disk [16, 34]. Any modifi- overhead of this movement of data and coordination between con- cations that are made by a transaction are not visible to the appli- current transactions has been shown to be significant [15]. cation until this record has been written. This record only contains This DBMS architecture made sense when compute nodes with the original request information sent from the client, which is more enough RAM to store an entire database in memory were either lightweight than record-level logging [22]. non-existent or prohibitively expensive. But modern distributed DBMSs are able to store all but the largest OLTP databases entirely in the collective memory [29]. 3. ANTI-CACHING SYSTEM MODEL Given these observations, H-Store is designed to efficiently ex- We call our architecture anti-caching since it is the opposite ar- ecute OLTP workloads on main memory-only nodes [18, 29]. As chitecture to the traditional DBMS buffer pool approach. The disk shown in Fig. 2, an H-Store node is a single physical computer sys- is used as a place to spill cold tuples when the size of the database tem that manages one or more partitions. A partition is a disjoint exceeds the size of main memory. As stated earlier, unlike normal subset of the data [26]. Each partition is assigned a single-threaded caching, a tuple is never copied. It lives in either main memory or execution engine at its node that is responsible for executing trans- the disk based anti-cache. actions and queries for that partition. At runtime, the DBMS monitors the amount of main memory Although H-Store supports ad hoc queries, it is primarily opti- used by the database. When the size of the database relative to the mized to execute transactions as stored procedures. In this paper, amount of available memory on the node exceeds some administrator- we use the term transaction to refer to an invocation of a stored defined threshold, the DBMS “evicts” cold data to the anti-cache in procedure. Stored procedures are an effective way to optimize order to make space for new data. To do this, the DBMS constructs OLTP applications because they execute entirely at the data node, a fixed-size block that contains the least recently used (LRU) tuples thereby reducing the number of round-trips between the client and from the database and writes that block to the anti-cache. It then the database. A stored procedure contains control code (i.e., ap- updates a memory-resident catalog that keeps track of every tuple plication logic) that invokes pre-defined parameterized SQL com- that was evicted. When a transaction accesses one of these evicted mands. A client application initiates a transaction by sending a re- tuples, the DBMS switches that transaction into a “pre-pass” mode quest to any node in the cluster. Each transaction request contains to learn about all of the tuples that the transaction needs. After the name of a stored procedure and the input parameters for that this pre-pass is complete, the DBMS then aborts that transaction 1944 

4 . Evicted Table Block Table Data Table BlockId TupleId <blockId> Header Tuple Data <creation-timestamp> 999 <offset> 4 6 0110101010101010 <tuple-length> 999 <offset> <tuple-data> newest -- 3 11010101000111111 <string-data> 997 <offset> 2 4 1010001010101000 997 <offset> <tuple-length> 3 1 1010000010101010 <tuple-data> 6 -- 0101101010101010 997 <offset> <string-data> oldest 1 5 0000010101101010 997 <offset> ... ... ... Figure 4: Physical representation of the LRU Chain embedded in the tuple Figure 3: A logical representation of the layout of the in-memory Evicted headers. Each tuple header contains 1 byte for bit flags (left-most box) Table and the disk-resident Block Table. The arrows represent integer off- followed by two 4-byte tuple IDs of the tuples adjacent in the linked list. sets of tuples in a block. ensures that the DBMS is able to identify all of the evicted tuples (rolling back any changes that it may have made) and holds it while that are needed by a transaction. the system retrieves the tuples in the background. Once the data has been merged back into the in-memory tables, the transaction is re- LRU Chain: Lastly, H-Store also maintains an in-memory list of leased and restarted. all the tuples for each table in LRU order. This allows the DBMS to We now describe the underlying storage architecture of our anti- quickly ascertain at runtime the least-recently used tuples to com- cache implementation. We then discuss the process of evicting cold bine into a new block to evict. The LRU Chain is a doubly-linked data from memory and storing it in the non-volatile anti-cache. list where each tuple points to the next and previous most-recently Then, we describe how the DBMS retrieves data from the anti- used tuple for its table. Tuples are added to the tail of the chain cache. All of the DBMS’s operations on the anti-cache are transac- whenever they are accessed, modified, or inserted by a transaction. tional and any changes are both persistent and durable. When a tuple is read or updated, it is first removed from its original location in the chain and inserted at the back. The tuples that were 3.1 Storage Architecture previously adjacent to it in the chain are then linked to each other. The anti-cache storage manager within each partition contains Rather than maintain a separate data structure for the LRU Chain, three components: (1) a disk-resident hash table that stores evicted the DBMS embeds the pointers directly in the tuples’ headers. To blocks of tuples called the Block Table, (2) an in-memory Evicted reduce the memory overhead of this, the pointer for each tuple is Table that maps evicted tuples to block ids, and (3) an in-memory a 4-byte offset of that record in its table’s memory at that partition LRU Chain of tuples for each table. As with all tables and indexes (instead of an 8-byte address location). in H-Store, these data structures do not require any latches since To reduce the CPU overhead of tracking the total ordering of only one transaction is allowed to access them at a time. each table’s LRU Chain, the DBMS selects a fraction of the trans- One of the trade-offs that we need to consider is the storage over- actions to monitor at runtime. The selected transactions are used to head of this bookkeeping, given that the main goal of evicting tu- update data in the LRU Chain. Because hot tuples are, by defini- ples is to free up memory. Obviously the amount of memory used tion, accessed more frequently, they are more likely to be accessed to keep track of evicted tuples should only be a small fraction of the in the transactions sampled and thus are more likely to be updated memory gained from evicting tuples. Our current implementation in the LRU Chain. The rate at which transactions are sampled is also requires that all of the database’s primary key and secondary controlled by parameter ↵, where 0 < ↵  1. We explore the indexes fit in memory. We explore this issue further in Section 5.6. affect of sampling and other trade-offs in Section 5.4. In addition, there are often tables that are accessed frequently Block Table: This is a hash table that maintains the blocks of and should not be allowed to be evicted to disk (e.g., small lookup tuples that have been evicted from the DBMS’s main memory stor- tables). Because these tables would be considered hot, it is unlikely age. Each block is the same fixed-size and is assigned a unique that any portion of such a table would be evicted to disk. Still, there 4-byte key. A block’s header contains the identifier for the single is added overhead of maintaining the LRU chain for such tables. To table that its tuples were evicted from and the timestamp when the remove this, tables can be specifically flagged as evictable during block was created. The body of the block contains the serialized schema creation. Any table not labeled as evictable will not main- evicted tuples from a single table. Every tuple stored in a block tain an LRU chain and will remain entirely in main memory. is prefixed with its size and is serialized in a format that closely resembles its in-memory format (as opposed to a format that is 3.2 Block Eviction specifically designed for disk-based storage). The key portion of the Block Table stays in memory while its values (i.e., the block Ideally, our architecture would be able to maintain a single global data) are stored on disk without OS or file-system caching. ordering of tuples in the system, thus globally tracking hot and cold data. However, the costs of maintaining a single chain across Evicted Table: The Evicted Table keeps track of the tuples that partitions would be prohibitively expensive due to the added costs have been written out to blocks on disk. When a tuple is evicted, of inter-partition communication. Instead, our system maintains a the DBMS removes it from the regular storage space for tables and separate LRU Chain per table that is local to a partition. Thus, in adds it to a dynamically-constructed block that is then stored in order to evict data the DBMS must determine (1) what tables to the Block Table. Each evicted tuple in a block is assigned a 4-byte evict data from and (2) the amount of data that should be evicted identifier that corresponds to its offset in the block it resides in. The from a given table. For our initial implementation, the DBMS an- DBMS updates any indexes containing evicted tuples to reference swers these questions by the relative skew of accesses to tables. the Evicted Table. As discussed in Section 3.4, the Evicted Table The amount of data accessed at each table is monitored, and the 1945 

5 . sequential look-up (i.e., a full table scan). For the latter, the DBMS receive execute evicted NO will need to store the entire table in memory, which may exceed the data transaction transaction accessed? commit physical memory available. We discuss this problem in Section 6.1. For index look-up queries, the system searches the target index YES to find the keys that match the query’s predicate. Each key in the index points to a tuple that is either in the normal table storage or in requeue pre-pass the Evicted Table. If none of the accessed tuples are evicted, then transaction execution the DBMS allows the transaction to continue. If evicted data is needed, the transaction will then enter a special phase to determine exactly which data is needed and where that data exists on disk. merge fetch Pre-pass Phase: A transaction enters the pre-pass phase if evicted blocks blocks data is needed to continue execution. The goal of the pre-pass phase is to determine all of the evicted data that the transaction needs to access so that it can be retrieved together. To do this, the transac- Figure 5: Transaction Execution State Diagram – If the transaction ac- tion executes as normal, except that the DBMS checks the evicted cesses evicted data, then the transaction enters pre-pass execution, fetches flag for each tuple that it accesses to determine whether the tuple and merges the data before the transaction is requeued. has been evicted. If it has, then the DBMS records the evicted tu- amount of data evicted from each table is inversely proportional ple’s block ID and offset from the Block Table (see Fig. 3). When to the amount of data accessed in the table since the last eviction. pre-pass has finished execution, the DBMS rolls back any changes Thus, the hotter a table is, the less data will be evicted. For the that the transaction made at any partition and then re-queues the benchmarks tested, this approach is sufficient, but we expect to transaction along with the list of evicted tuple identifiers that it at- consider more sophisticated schemes in the future. tempted to access during the pre-pass phase. Also, during the pre- After determining how much data to evict from each table, H- pass phase, any in-memory tuples are updated in the LRU Chain to Store executes special single-partition transactions that select tu- reduce the likelihood that these tuples are evicted before the trans- ples for eviction and writes blocks to disk. Since transactions are action is re-queued. This minimizes the possibility of a transaction executed one-at-a-time at each partition, these eviction transactions being restarted multiple times due to evicted data. automatically block all other transactions at their target partition Although it is small, the overhead of aborting and restarting trans- without needing any additional locking mechanisms. actions is not zero. Thus, in the pre-pass phase, the DBMS attempts When the eviction transaction executes, it creates a new block to identify all of the data that a transaction needs by allowing that by popping tuples off the head of the target table’s LRU Chain. For transaction to continue executing after it encounters an evicted tu- each tuple being evicted, H-Store copies its data into the eviction ple [23]. This allows the DBMS to batch fetch requests and min- block buffer. It then adds an entry into the Evicted Table and up- imize the possibility of restarting a transaction multiple times. In dates all indexes to point to this entry instead of the original tuple contrast, in the event of a page fault in virtual memory, execution location. Each tuple in the Evicted Table includes a special evicted halts for each individual evicted page access [28]. flag in its header that enables the DBMS to recognize when a trans- For some transactions, it is not possible for the DBMS to dis- action accesses evicted data. This eviction process continues until cover all of the data that it needs in a single pre-pass. This can occur the block is full, at which point the transaction will create the next if the non-indexed values of an evicted tuple are needed to retrieve block. The process stops once the transaction has evicted the req- additional tuples in the same transaction. In this case, the initial uisite amount of data from each table. Groups of blocks are written pre-pass phase will determine all evicted data that is not dependent out in a single sequential write. For example, if the table is asked to on currently evicted data. Once this data is successfully merged evict a set of n blocks, it will create each of the n blocks indepen- and the transaction is restarted, this unevicted data will be used to dently, and only when all n blocks have been created will it write resolve any data dependencies and determine if any additional data the result to disk in one sequential write. needs to be unevicted. From our experience, however, we believe It is also important to note that the state of the database is con- that such scenarios are rare. The more typical access pattern is that sistent during the eviction process. Although indexes are updated a transaction retrieves the key of a record from a secondary index, and the tuple is removed from the original table before the block is in which case the DBMS will still be able to run the transaction in written to disk, the single-threaded nature of the execution engine the pre-pass phase because the indexes always remain in memory. means that no other transactions access these changes until the spe- We next describe how the DBMS retrieves the evicted tuples cial transaction finishes. Other transactions will not execute until identified during the pre-pass and merges them back into the sys- the entire set of blocks requested for eviction are written to disk. tem’s in-memory storage. Also, at no point during this process is data un-recoverable if the DBMS crashes (see Section 3.6). 3.4 Block Retrieval After aborting a transaction that attempts to access evicted tu- 3.3 Transaction Execution ples, the DBMS schedules the retrieval of the blocks that the trans- Main memory DBMSs, like H-Store, owe their performance ad- action needs from the Block Table in two steps. The system first vantage to processing algorithms that assume that data is in main issues a non-blocking read to retrieve the blocks from disk. This memory. But any system will slow down if a disk read must be pro- operation is performed by a separate thread while regular transac- cessed in the middle of a transaction. This means that we need to tions continue to execute at that partition. The DBMS stages these avoid stalling transaction execution at a partition whenever a trans- retrieved blocks in a separate buffer that is not accessible to queries. action accesses an evicted tuple. We now describe how this is ac- Any transaction that attempts to access an evicted tuple in one of complished with anti-caching. these blocks is aborted as if the data was still on disk. A query can access evicted data through either an index or a Once the requested blocks are retrieved, the aborted transaction 1946 

6 .is then rescheduled. Before it starts, the DBMS performs a “stop- of the blocks that it needs have been retrieved from the nodes in and-copy” operation whereby all transactions are blocked at that the cluster. The system ensures that any in-memory tuples that the partition while the unevicted tuples are merged from the staging transaction also accessed at any partition are not evicted during the buffer back into the regular table storage. It then removes all of time that it takes for each node to retrieve the blocks from disk. the entries for these retrieved tuples in the Evicted Table and then updates the table’s indexes to point to the real tuples. 3.6 Snapshots & Recovery The key issue that we must consider during this step is on how Persistence and durability in disk-based systems is typically achieved much data to merge from a retrieved block back into the in-memory using a combination of on-disk data and logging. In a main mem- storage. For example, the DBMS can choose to merge all of the tu- ory DBMS, however, other techniques such as snapshots and com- ples from the recently retrieved block or just the tuple(s) that the mand logging [22, 29] are used. This does not change for a DBMS previous transaction attempted to access that caused the block to with anti-caching, except that now the system must also snapshot be retrieved in the first place. We now discuss two different solu- the additional data structures discussed Section 3.1. tions for this problem. We compare the efficacy and performance To do this, the DBMS serializes all the contents of the regular of these approaches in Section 5.1. tables and index data, as well as the contents of the Evicted Table, and writes it to disk. At the same time, the DBMS also makes a Block-Merging: The simplest method is for the DBMS to merge copy of the Block Table on disk as it existed when the snapshot be- the entire retrieved block back into the regular table storage. All of gan. No evictions are allowed to occur in the middle of a snapshot. the tuples in the block are inserted back into the in-memory table. To recover after a crash, the DBMS loads in the last snapshot from The requested tuple(s) are placed at the back of the table’s LRU disk. This will set up the tables, indexes, Block Table, and Evicted Chain. Conversely, any tuples not needed by pending transactions Table as it existed before the crash. The DBMS then replays the are added to the front (i.e., cold end) of the LRU Chain, which transactions in the command log that were created after this snap- means that they are more likely to be chosen for eviction in the shot was taken. With this process, all anti-caching data is persistent next round. This ensures that only the tuples that were needed by and the exact state of a system is recoverable in the event of a crash. the transaction that caused the block to be un-evicted become hot, Making a snapshot of the Block Table could be prohibitively ex- whereas the rest of the block is still considered cold. After the pensive for large data sizes. Instead of making copies for each DBMS merges the tuples from the block, it can delete that block checkpoint, the DBMS takes delta snapshots. Because the data from the Evicted Table. within a block in the Block Table is not updated, the DBMS just The overhead of merging all the tuples from the un-evicted block checks to see which blocks were added or removed from the Block can be significant, especially if only a single tuple is needed from Table since the last snapshot. This technique greatly reduces the the block and all of the other tuples are re-evicted shortly thereafter. amount of data copied with each snapshot invocation. In the worst case, there is a continuous un-eviction/re-eviction cy- cle, where unwanted tuples are brought into the system and then immediately re-evicted. 4. ARCHITECTURE COMPARISON To evaluate our anti-caching model, we implemented a prototype Tuple-Merging: To avoid this oscillation, an alternative strat- in H-Store and compared its performance against MySQL, an open- egy is to only merge the tuples that caused the block to be read source, disk-oriented DBMS. We tested MySQL with and without from disk. When a block is retrieved from disk, the DBMS extracts Memcached [14] as a front-end distributed cache. only the tuples that are needed from that block (based on their off- We first describe the two benchmarks and the three DBMS con- sets stored in the Evicted Table) and then only merges those tuples figurations that we used in this analysis. back into the in-memory table. Once the desired tuples are merged, the fetched block is then discarded without updating the block on 4.1 Benchmarks disk. This reduces the time of merging tuples back into their ta- We used the OLTP-Bench [10] framework for the MySQL ex- bles and updating their indexes. It now means that there are now periments and H-Store’s built-in benchmarking framework for the two versions of the tuple, the one in memory and the stale one in anti-caching experiments. the anti-cache on disk. But since the DBMS removes the merged tuples’ from the Evicted Table, all subsequent look-ups of these tu- YCSB: The Yahoo! Cloud Serving Benchmark is a collection of ples will use the in-memory version. If this block is ever fetched workloads that are representative of large-scale services created by again, the stale entries of the already unevicted tuples are ignored. Internet-based companies [9]. For all of the YCSB experiments in Over time, these “holes” in the blocks accumulate. This means this paper, we used a ⇠20GB YCSB database containing a single the amount of valid data that is retrieved in each block is reduced. table with 20 million records. Each YCSB tuple has 10 columns We employ a lazy block compaction algorithm during the merge each with 100 bytes of randomly generated string data. The work- process. This compaction works by tracking the number of holes load consists of two types of transactions; one that reads a single in each of the blocks in the Block Table. When the DBMS retrieves record and one that updates a single record. We use three different a block from disk, it checks whether the number of holes in a block transaction workload mixtures: is above a threshold. If it is, then the DBMS will merge the entire • Read-Heavy: 90% reads / 10% updates block back into the memory, just as with the block-merge strategy. We discuss more sophisticated approaches in Section 6.2. • Write-Heavy: 50% reads / 50% updates • Read-Only: 100% reads 3.5 Distributed Transactions We also vary the amount of skew in workloads to control how Our anti-caching model also supports distributed transactions. often a tuple is accessed by transactions. For these experiments, H-Store will switch a distributed transaction into the “pre-pass” we use YCSB’s Zipfian distribution as it is emblematic of skewed mode just as a single-partition transaction when it attempts to ac- workloads where older items are accessed much less frequently cess evicted tuples at any one of its partitions. The transaction is than newer items. The amount of skew in the Zipfian distribution aborted and not requeued until it receives a notification that all is controlled by the constant s, where s > 0. Higher values of s 1947 

7 . data_size data_size data_size data_size (a) mem_size = 1, read-only (b) mem_size = 2, read-only (c) mem_size = 4, read-only (d) mem_size = 8, read-only data_size data_size data_size data_size (e) mem_size = 1, read-heavy (f) mem_size = 2, read-heavy (g) mem_size = 4, read-heavy (h) mem_size = 8, read-heavy data_size data_size data_size data_size (i) mem_size = 1, write-heavy (j) mem_size = 2, write-heavy (k) mem_size = 4, write-heavy (l) mem_size = 8, write-heavy Figure 6: YCSB experiments. In aLRU, ↵ = 0.01. signify higher skews. In our experiments, we use a Zipfian skew 4.2 System Configurations with values of s between 0.5 and 1.5. All three systems were deployed on a single node with a dual- TPC-C: This benchmark is the current industry standard for socket Intel Xeon E5-2620 CPU (12 cores per socket, 15M Cache, evaluating the performance of OLTP systems [32]. It consists of 2.00 GHz) processor running 64-bit Ubuntu Linux 12.04. The nine tables and five procedures that simulate a warehouse-centric data for each respective DBMS was stored on a single 7200 RPM order processing application. Only two of these procedures modify disk drive. According to hdparm, this disk delivers 7.2 GB/sec for or insert tuples in the database, but they make up 88% of the bench- cached reads and about 297 MB/sec for buffered reads. All trans- mark’s workload. For our experiments, we used a ⇠10GB TPC-C actions were executed with a serializable isolation level. database containing 100 warehouses and 100,000 items. We con- MySQL: We used MySQL (v5.6) with the InnoDB storage en- figured both the H-Store and OLTP-Bench benchmark frameworks gine. We tuned MySQL’s configuration to optimize its execution such that each transaction only accesses data from a single ware- for the type of short-lived transactions in our target benchmarks. In house (i.e., there are no distributed transactions). particular, we also used 512 MB log file cache and 10 MB query We must further decide which tables will be designated as evictable. cache. We configured InnoDB’s buffer pool according to the work- Some of the tables in the TPC-C benchmark are called lookup ta- load size requirement for the different experiments. We did not bles and contain only static data. For example the CUSTOMERS, limit the number of CPU cores that the DBMS is allowed to use. DISTRICT, and WAREHOUSE tables fall into this category. Once ini- tially loaded, no new data is added to these tables. Also, these ta- MySQL + Memcached: In our second configuration, we used bles are used by a majority of the transactions in the workload, and MySQL with Memcached (v1.4) deployed on the same node. We are unlikely to be evicted. Thus, we did not mark them as evictable. modified the transaction code for the different benchmarks to store This allows the system to not maintain a LRU Chain for these ta- cached query results in Memcached as serialized JSON objects. As bles. In most real-world deployments, static lookup tables on the described below, the amount of memory allocated to Memcached order of a few gigabytes will easily fit in memory. Thus, these ta- is based on the working set size of the benchmark. bles will not be evicted and will reside in memory throughout the The primary benefit of using Memcached as a front-end to MySQL duration of the benchmark. is to improve the performance of read queries. Because Mem- On the other hand, some tables are used to record orders, but cached does not use heavyweight locking, simple key-based lookups this data is not read by transactions in the future. These include of cached tuples can be faster than in MySQL. However, writes the HISTORY, ORDERS and ORDER_LINE tables. It is these tables that must be propagated to both the Memcached frontend and MySQL cause a TPC-C database to grow over time. In our benchmark, these backend, thus incurring additional overhead. tables are labeled as evictable. For the benchmark, we set the avail- H-Store with Anti-Caching: Lastly, we deployed the latest ver- able memory to the system to 12GB. This allows all static tables to sion of H-Store [2] that uses our anti-caching prototype. In our cur- fit in memory. As the benchmark progresses and more orders accu- rent implementation, we use BerkeleyDB’s hash table to store the mulate, the data size will continue to grow, eventually exhausting Block Table [24]. BerkeleyDB is configured to use direct I/O with- available memory, at which point the anti-caching architecture will out any caching or locks. We split each benchmark’s database into begin evicting cold data from the evictable tables to disk. 1948 

8 . Figure 7: TPC-C experiments. Figure 8: Merge Strategy Analysis – YCSB read-only, 2⇥ memory, 1MB evict blocks. six partitions using a partitioning scheme that makes all transac- for datasets 8⇥ memory. There are several reasons for this. One is tions single-partitioned [26]. We configured the memory threshold that H-Store’s lightweight concurrency control scheme is more ef- for the system according to the workload size requirement for the ficient than MySQL’s model [15]. Another advantage is that tuples different experiments. We set the system to check its database size are not converted back-and-forth between disk and main memory every 5 seconds and evict data in 1MB blocks. format. Evicted tuples are copied in and out of eviction blocks The benchmark clients in each experiment are deployed on a sep- as contiguous chunks of memory. Also, in an anti-caching archi- arate node in the same cluster. For each experiment, we execute the tecture, eviction blocks are composed dynamically of cold tuples, benchmarks three times and report the average throughput of these rather than evicting fixed blocks which could contain some rela- trials. In each trial, the DBMSs are allowed to “warm-up” for two tively hot data. Hence, anti-caching provides finer-grained control minutes. Empirically, we found that sustained transaction through- of the bytes evicted to disk. put had stabilized within this period. During the warm-up phase, There are several interesting results regarding the MySQL bench- transactions are executed as normal but throughput is not recorded marks. One is that that Memcached improves the throughput of in the final benchmark results. For H-Store, cold data is evicted to MySQL most on the read-only workloads and only for high skew. the anti-cache and hot data is brought into memory. For MySQL, The lower performance in the other workloads is due to the over- hot data is brought into the buffer pool. For the Memcached de- head of synchronizing values in Memcached and in MySQL in the ployment, the client pre-loads relevant objects into Memcached’s event of a write. For low skew workloads, there is a high cost of memory. After the warm-up, each benchmark is run for a duration cache misses in this hybrid architecture. If Memcached is queried of five minutes, during which average throughput is recorded. The and does not contain the requested data, the application must then final throughput is the number of transactions completed in a trial query MySQL, resulting in a cache miss. If Memcached is queried run divided by the total time (excluding the warm-up period). Each and contains the requested data (i.e. a cache hit), the MySQL benchmark is run three times and the throughputs from these runs backend is not queried at all. Because of the lower overhead of are averaged for a final result. Memcached over MySQL, the benefits of a cache hit can be signif- For the anti-caching architecture, we evaluate H-Store’s perfor- icant. However, for the OLTP benchmarks tested, tuples are rela- mance using a LRU Chain sampling rate of ↵ = 0.01 (aLRU) and tively small and queries are relatively simple, so the cost of a cache ↵ = 1.00 (LRU). Thus, for aLRU, only one out of every one hun- miss outweighs the cost of a cache hit. It is only in read inten- dred transactions updates the LRU chain while for LRU every trans- sive, higher skewed workloads (where the likelihood of a cache hit action will update the LRU chain. is higher) that hybrid architecture outperforms standalone MySQL. Also noteworthy is that for workloads with writes, MySQL actu- ally performs worse for skews of 1.5 and 1.25. This results in 4.3 Results & Discussion higher lock contention for hot tuples in a disk-based DBMS that We now discuss the results of executing the two benchmarks uses heavyweight locking and latching. in Section 4.1 on the three DBMS architectures across a range of Another result is that for almost all data sizes and skews tested, workload skew and data size configuration. aLRU performs as well or better than the standard LRU. As dis- YCSB: The results in Fig. 6 are for running the YCSB bench- cussed previously, sampling of transactions is an effective way to mark with all three workload types (read-only, read-heavy, write- capture workload skew and is able to significantly lessen the over- heavy) across a range of data sizes and workload skews. These head of maintaining the LRU chain. Default H-Store provides an results show that as database size increases relative to the amount effective baseline by which to compare the overheads of the anti- of memory in the system, the throughput of all three systems de- caching components. In Figs. 6a, 6e and 6i, we see where the grades, since they perform more disk reads and writes. Similarly, throughput of the aLRU implementation is close to H-Store base- as the skew decreases, their performance also degrades since trans- line, ranging from a 2–7% throughput overhead. Conversely, the actions are more likely to access tuples that are evicted and need to anti-caching with traditional LRU suffers significantly as skew is be retrieved from disk. decreased, meaning the maintenance of the LRU chain is a major We observe, however, that for highly-skewed workloads (i.e., bottleneck at lower skews. workloads with skews of 1.5 and 1.25) the anti-caching architecture TPC-C: The results for TPC-C are shown in Fig. 7. Because the outperforms MySQL by a factor of 9⇥ for read-only, 18⇥ for read- anti-cache architecture is able to efficiently evict cold data from the heavy, and 10⇥ on write-heavy workloads for datasets 8⇥ memory. tables that are growing (i.e., HISTORY, ORDERS and ORDER_LINE) For the same high skews, out anti-caching architecture outperforms the throughput declines little. In TPC-C, the only transaction that the hybrid MySQL + Memcached architecture by a factor of 2⇥ for potentially accesses evicted data is the Order-Status transaction. read-only, 4⇥ for read-heavy, and 9⇥ on write-heavy workloads 1949 

9 . (a) Block Size (b) Tuple Size Figure 9: Block and Tuple Size Analysis – YCSB read-only workload with 2⇥ data size. However, this transaction is only 4% of the workload and reads the Figure 10: Eviction Chain Analysis. most recent order for a given customer. Thus, the data that these transactions need is unlikely to be evicted, meaning the slight de- workloads. The main reason for this is that with a highly skewed crease in throughput for anti-caching is not due to unevicting data. workload, the DBMS needs to retrieve fewer blocks from disk. Be- Instead, it is a result of the increasing memory overhead as the cause each block is unlikely to be retrieved from disk, it is also rela- amount of evicted data grows, since there is an entry in the Evicted tively less common that multiple tuples from a single block will be Table for each evicted tuple. Due to the amount of writes, the hy- requested together. Thus, the system is less likely to benefit from brid architecture performs worse than stand-alone MySQL when the locality of tuples on the same block. data size is larger than memory. Overall, anti-caching provides a 7⇥ improvement in throughput over the other architectures. 5.3 Tuple Size Another important factor in the performance of a DBMS with 5. EXPERIMENTAL ANALYSIS anti-caching is tuple size. The memory overhead of anti-caching’s We also conducted additional experiments to evaluate our design internal data structures is much greater for smaller tuples than for and test its sensitivity to changes in key parameters. These experi- large tuples. Also, when evicting large blocks of smaller tuples, the ments were conducted on the same hardware configuration used for CPU overhead of eviction could be significant, because the DBMS the system comparison study in Section 4. must update indexes and the Evicted Table for each evicted tuple. The cost of eviction from the LRU Chain is constant regardless of 5.1 Merge Strategies tuple size. Thus, to measure the affect of tuple size we will use We first compare the two block retrieval strategies from Sec- the read-heavy YCSB workload with 2⇥ data size and 1MB block tion 3.4: (1) block-merge and (2) tuple-merge. For this experi- sizes. We vary size of tuples in each trial from 128B to 1024B. ment, we use the YCSB read-only workload at 2⇥ memory with an The results in Fig. 9b show that the DBMS achieves higher through- eviction block size of 1MB. The tuple-merge fill-factor (i.e., when puts for the larger tuple sizes. This may seem counterintuitive, the lazy compaction merges the entire block into memory) is set to but the reason is because there is a small but unavoidable mem- 0.50, meaning that each block can contain no more than 50% holes. ory overhead for eviction per tuple. Thus, with smaller tuples anti- The results in Fig. 8 show that across the skews tested the tuple- caching is able to reclaim less memory with each tuple eviction. merge policy outperforms the block-merge policy. There are two This means that to reclaim a fixed amount of memory, more tu- reasons for this. First is that the larger merge costs of the block- ples need to be evicted. However, evicting more tuples increases merge policy, shown in Fig. 11a. Because merging tuples blocks the CPU resources consumed. This additional cost degrades the transactions from executing on the target partition, this can nega- DBMS’s throughput since transaction processing at a partition is tively affect throughput. Second is that in the block-merge policy, blocked while the eviction process executes. unrequested tuples (i.e., tuples that were part of the fetched block but were not requested by a transaction) are merged and placed at 5.4 LRU Chain Overhead the cold end of the LRU Chain. Thus, these tuples were unevicted We next analyze the internal bookkeeping in anti-caching used only to shortly thereafter be evicted once again. This uneviction/re- to keep track of tuple accesses. We compare the DBMS’s perfor- eviction cycle creates unnecessary overhead and is another reason mance using either a doubly-linked or a singly-linked list for the for the lower throughput of the block-merge policy. LRU Chain. As discussed in Section 3.1, there is an inherent trade- off between the amount of memory used to track the LRU ordering 5.2 Evicted Table Block Size of tuples in a table and the cost of maintaining that ordering. To We next investigate the impact on performance of different Evicted show this, we implemented a micro-benchmark in H-Store’s execu- Table block sizes. This parameter controls how many tuples are in tion engine that updates 100,000 tuples and reports the total elapsed each evicted block. Because we have already shown the advan- time needed to update the LRU Chain. As a baseline, we compare tage of the tuple-merge policy over block-merge in Section 5.1, we against the cost when anti-caching is disabled, and thus no eviction only evaluate the tuple-merge policy. In this experiment, we use the chain is maintained. read-only YCSB workload and with a database size of 2⇥ memory. The results are shown in Fig. 10. The baseline is constant across The results in Fig. 9a show that larger block sizes reduce overall all skew levels, as expected. For higher skewed workloads, the throughput, especially for highly skewed workloads. The through- doubly-linked list performs within 5% of the baseline and 20⇥ put degradation is not due to the eviction process, which evicts faster than the singly-linked list. The two strategies slowly con- batches of blocks in a single sequential disk write. Thus, writing verge as skew is decreased. The difference in performance between five 1MB blocks or twenty 256KB blocks is nearly equivalent in the singly-linked list and doubly-linked list is due to the high cost terms of I/O cost. The main difference is due to the added costs of of updating a tuple in the chain. Choosing a tuple for eviction in- fetching larger blocks. volves removing the front tuple of the chain, which can be done Another result from this experiment is that the difference in through- in O(1). Similarly, adding a tuple to the back of the chain can put for larger block sizes is most pronounced at higher skewed also be done in constant time. However, updating a tuple could, 1950 

10 . (a) YCSB (b) TPC-C Figure 12: Eviction overhead measurements for a 60 second interval of the TPC-C and YCSB (read-heavy, 2⇥ memory, 1.0 skew) benchmarks. Each vertical line represent a point in time when block(s) were evicted. (a) Eviction/Uneviction Costs. For each block size, the left bar represents times represent the total time required to update all 1,000 tuples in the block-merge costs and the right bar represents the tuple-merge costs. each of the n indexes, averaged over three runs of the benchmark. The results are seen in Fig. 11b. The performance is shown to scale linearly with the number of indexes and even for a larger number of indexes elapsed time is reasonable. We conclude that the update of secondary indexes is unlikely to be a bottleneck for most OLTP workloads. 5.6 Overhead Measurements Lastly, we measured the affect of evictions on the sustained through- put in the system. For this, we record the throughput of the YCSB and TPC-C benchmarks over time, also recording when evictions occur. The graphs in Fig. 12 show a timeline view of the through- put of our anti-caching implementation while it is evicting and un- (b) Index Update Costs. Elapsed time represents cost of updating the spec- ified number of indexes for a block of 1,000 tuples. evicting data. The vertical lines represent when an eviction oc- curs in the system. Eviction happens less frequently in TPC-C Figure 11: Eviction and Uneviction analysis. because data takes longer to accumulate in memory due to few in the worst case, involve scanning the entire chain to find the tu- unevictions. Also due to the few unevictions in TPC-C, through- ple. This is an O(n) operation, where n is the number of tuples put is less volatile over time compared to YCSB. There are several in the chain. For high skew workloads, it is likely that the hot tu- reasons for throughput volatility. One is group commit of writes, ples that are being updated frequently will be found at the back of which commits transactions in large batches, thereby making the the chain, since the chain is ordered from coldest to hottest. Thus, throughput more volatile over time. Eviction is another factor, and it is better to scan the chain from back-to-front rather than from the throughput can be seen to decrease during an eviction. This de- front-to-back, necessitating a doubly-linked list. We contend that crease is caused by the creation of the eviction block, which must the added memory overhead of a doubly-linked list is a necessary block other transactions. However, once created, writing of the trade-off to optimize for skewed workloads. eviction block to disk is done asynchronously. 5.5 Eviction Overhead Micro-benchmark 6. FUTURE WORK We created another micro-benchmark to compare the relative We now discuss several extensions to our anti-caching model that costs of evicting and unevicting an anti-cache block for a fixed- we plan to investigate in the future. size 1KB tuple. The engine first reads the oldest tuples from one table, copies them into an eviction block, updates an index, and 6.1 Larger-than-Memory Queries then writes the block to disk. Then, the engine reads that block Anti-caching allows main memory DBMSs to manage databases back from disk, copies the data back into the table, and updates that are larger than the amount of collective memory at all nodes. the index. This constitutes a single run of the benchmark. This is Our current implementation works as long as the scope of each repeated three times and the run times averaged for the final result. transaction (i.e., the amount of data that it reads from or writes to The results in Fig. 11a show that the cost of updating indexes the database) fits in memory. But some applications contain queries and copying data to and from disk scales linearly relative to the that need to access more data than can fit in memory, thus we need block size. Although in this experiment the construct and merge to extend our anti-caching model to support them. We first note phases take longer than the disk I/O operations, this experiment that we have never seen an OLTP application in which a transaction was conducted with no other disk traffic. needs to write a large number of tuples all at once. Thus, there is no Additionally, we created a micro-benchmark to analyze the cost need to support writes that exceed the size of main memory. Reads of updating indexes as the number of indexes is increased, since it is are a different matter. While very uncommon in OLTP, it is possible not uncommon for OLTP tables to have more than one secondary for an application to need to perform simple analytical queries (e.g., index. In our analysis, for completeness we test with up to eight aggregates) on entire tables. This is a problem with our current anti- indexes, but acknowledge this is more indexes than would be likely cache design, since all of data needed to complete such a query in practice due to the high costs of maintaining secondary indexes must be in memory first before the query can be processed. We in any DBMS, independent from anti-caching. Each benchmark now discuss three possible solutions. updates 1,000 tuples in a number of indexes varied from one to Obviously, large read queries generate a concurrency control prob- eight. The choice of 1,000 tuples represents the number of tuples lem when mixed with transactions that execute write queries. In a in a single eviction block assuming 1KB tuples and a 1MB block. traditional DBMS, the query will commence after acquiring a table- Both a hash index and a balanced tree index were used. Reported level lock, at which point no writes will be processed in parallel. 1951 

11 .Once the query finishes, the lock is released and all the queued up For example, if one of the queries in the workload often reads data writes can move forward. In this scenario, the total time in the from several tables, then the data is considered semantically re- DBMS is divided into two modes of operations: (1) small write lated. It would be desirable to have all of these tuples reside on the queries are running or (2) large read queries are running. This same block, so that if that data is requested from disk only a single could be implemented in H-Store, but we suspect that it will have block will need to be read. the same performance as traditional DBMS architectures [29]. The second solution is to process large read queries in historical 6.3 Query Optimizations mode [30]. For this approach, each transaction is assigned a times- tamp of when it enters the system and then is only allowed to read There are several potential optimizations that would allow H- tuples with a timestamp that is less than or equal to it. The DBMS Store to process queries on evicted tuples without needing to re- will not overwrite tuples when one of these queries is running, but trieve it from disk. For example, the DBMS does not need to re- instead must keep both the before and after images of the database trieve an evicted tuple if an index “covers” a query (i.e., all of the to ensure that the large read queries are provided with the correct columns that the query needs in its predicate and output are in the version. H-Store already does this type of no-overwrite process- index). Another idea to further reduce the size of the database that ing through its asynchronous checkpoints [22]. Hence, extending it needs to be kept in memory is to evict only a portion of a tuple to to include timestamps is straightforward. Furthermore, time-travel disk. That is, rather than evicting the entire tuple, the system could reads, originally proposed in Postgres, are already supported in sev- only evict those columns that are unlikely to be needed. The sys- eral DBMSs, including Vertica and Oracle. Again, this solution is tem could analyze transactions and identify which columns in each readily implementable and should perform in a comparable fashion table are not accessed often by queries and then choose the opti- to the same solution in a traditional architecture. mal design that minimizes the number of block retrievals but also Finally, the third solution that is often proposed for this prob- maximizes the memory saved. lem is to allow dirty reads (but not dirty writes) [19]. In this case, all read-write conflicts between queries are ignored. The result of a large read query will include the affects of some updates from 7. RELATED WORK parallel transactions, but not necessarily all of them. For this so- There is an extensive history of research on main memory DBMSs. lution, no guarantees can be made about the semantics of the read Notable systems include PRISMA/DB [6], Dalí [17] (later renamed result. In a partitioned system like H-Store, the query is decom- to DataBlitz [7]), and TimesTen [31]. Commercial implementa- posed into individual, single-partitioned operations and then aggre- tions include VoltDB [4], SAP’s HANA [13], MemSQL [3], and gated together after processing the data at each partition separately. EXtremeDB [1]. RAMCloud [25] provides a scalable main mem- Again, this solution should execute with comparable performance ory resident key-value store for use in various cloud computing en- to the same solution in existing systems. vironments, though it does not provide some other common DBMS Although we plan to explore these options in detail in the future, features, such as secondary indexes and multi-object transactions. we do not expect the results to change the benefits of anti-caching. All of these systems are limited to databases that are smaller than the amount of available memory. 6.2 Block Reorganization The HyPer DBMS [19] is a main memory system that is designed As described in Section 3.4, when the DBMS uses the tuple- to execute both OLTP and OLAP queries simultaneously. Similar merge retrieval policy, the anti-cache blocks could contain “holes” to H-Store, OLTP queries are executed serially at partitions without of tuples that were selectively unevicted. Depending on the work- the need for a heavyweight concurrency control scheme. HyPer load, over time these holes reduce the number of tuples that are creates periodic memory snapshots to execute long running OLAP retrieved when a block is retrieved from disk. Thus, we are inves- queries. The DBMS relies on virtual memory paging to support tigating how to reorganize blocks to reduce the number disk opera- databases that are larger than the amount of available memory. tions without affecting the system’s runtime performance. In [28], similar to this work, the authors address the problem of There are several drawbacks to our lazy compaction scheme de- evicting cold data to disk in a main memory database. However, scribed in Section 3.4. First, while the holes accumulate within a their approach is very different, and relies on virtual memory to block but remain below the threshold that triggers the compaction, swap data from memory to disk. Tuple-level access patterns are every time the block is read the garbage data is retrieved. Ideally, analyzed off line, and in-memory data is reorganized according to each block fetched from disk would be full. Another problem is these access patterns. Cold data is moved to a memory location that that under the lazy block compaction scheme, when the number is more likely to be paged to disk by the OS. This approach is sim- of holes rises above the acceptable threshold and the entire block ilar to anti-caching in that it attempts to evict the cold data to disk is merged into memory, the non-hole tuples being merged in are and maintain the hot working set in memory. The major difference cold and likely unwanted. Thus, this has the same drawback as the between the two approaches is that the anti-caching architecture block-merge strategy, though to a lesser degree. It is likely that does not block while an evicted block is being read from disk. This these tuples will be immediately evicted during the next eviction allows other transactions to execute during the disk read. In con- cycle. But if we know these tuples are cold, a better design would trast, during a virtual memory page fault, no further transactions be to never move them back into memory. As future work, we can be executed. plan to explore a background block compaction process that com- The goals of Project Siberia, part of Microsoft’s Hekaton [12] pacts blocks without un-evicting the tuples. This could be done by main memory table extension for SQL Server, are also similar to merging half-full blocks and updating the appropriate Evicted Ta- our anti-caching proposal, but the implementations are different. In ble entries for the evicted tuples compacted. Of course, this would Hekaton, a table either exists entirely in main memory or is consid- have to be done in a transactionally consistent way, ideally without ered disk-based, meaning it is controlled by the standard disk-based affecting the overall performance of the system. execution engine with buffer pool, locks and latches. Anti-caching, Also possible in a block reorganization scheme would be seman- which evicts data at the granularity of individual tuples, offers finer- tic reorganization of blocks consisting of tuples from a set of tables. grained control over which data is evicted. 1952 

12 . In [20] the authors propose a method for identifying hot and cold [8] Q. Chen, M. Hsu, and R. Wu. MemcacheSQL a scale-out sql cache engine. In tuples from a sample of transactions in Hekaton. For our imple- Enabling Real-Time Business Intelligence, volume 126 of Lecture Notes in Business Information Processing, pages 23–37. 2012. mentation in H-Store, we use a LRU-based identification method [9] B. F. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears. that does not require an off-line mechanism. We consider this work Benchmarking cloud serving systems with YCSB. In SoCC, pages 143–154, complementary and plan to investigate more complicated schemes 2010. for identifying cold data. [10] C. A. Curino, D. E. Difallah, A. Pavlo, and P. Cudre-Mauroux. Benchmarking OLTP/Web Databases in the Cloud: The OLTP-Bench Framework. CloudDB, Calvin [33] is a main memory OLTP system that is designed to pages 17–20, October 2012. efficiently handle distributed transactions. It is also able to read [11] D. J. DeWitt, R. H. Katz, F. Olken, L. D. Shapiro, M. R. Stonebraker, and disk-resident data in a transactionally consistent way. To do this, D. Wood. Implementation techniques for main memory database systems. SIGMOD Rec., 14(2):1–8, 1984. Calvin serializes transactions similar to a disk-based system. If a [12] C. Diaconu, C. Freedman, E. Ismert, P.-A. Larson, P. Mittal, R. Stonecipher, small percentage of transactions need disk-resident data (the paper N. Verma, and M. Zwilling. Hekaton: SQL Server’s Memory-Optimized OLTP suggests less than 1%), it is possible to hide disk latency and avoid Engine. In SIGMOD, pages 1–12, 2013. performance degradation. [13] F. Färber, S. K. Cha, J. Primsch, C. Bornhövd, S. Sigg, and W. Lehner. Sap hana database: data management for modern business applications. SIGMOD Rec., The problem of maintaining coherence between an in-memory 40(4):45–51, Jan. 2012. buffer pool and data store on disk is explored in several previ- [14] B. Fitzpatrick. Distributed Caching with Memcached. Linux J., 2004(124):5–, ous works by retrofitting DBMSs to work with distributed caches. Aug. 2004. MemcacheSQL [8] does this by modifying Postgres’s buffer pool to [15] S. Harizopoulos, D. J. Abadi, S. Madden, and M. Stonebraker. OLTP through the looking glass, and what we found there. In SIGMOD, pages 981–992, 2008. use Memcached [14] as an extended distributed memory. All trans- [16] P. Helland, H. Sammer, J. Lyon, R. Carr, P. Garrett, and A. Reuter. Group actions interact only with the Postgres front-end. In [27], the au- commit timers and high volume transaction systems. In Proceedings of the 2nd thors propose TxCache, a transactionally consistent DBMS that au- International Workshop on High Performance Transaction Systems, pages tomatically manages data in a standalone instance of Memcached. 301–329, 1989. [17] H. V. Jagadish, D. F. Lieuwen, R. Rastogi, A. Silberschatz, and S. Sudarshan. The user must still specify how long data will remain in the cache Dalí: A high performance main memory storage manager. In VLDB, pages and the application still must perform a separate query each time to 48–59, 1994. determine whether an object is in the cache. [18] R. Kallman, H. Kimura, J. Natkins, A. Pavlo, A. Rasin, S. Zdonik, E. P. C. Our pre-pass execution phase is similar to run-ahead execution Jones, S. Madden, M. Stonebraker, Y. Zhang, J. Hugg, and D. J. Abadi. H-Store: A High-Performance, Distributed Main Memory Transaction models for processors explored in [23], where that goal is to pre- Processing System. Proc. VLDB Endow., 1(2):1496–1499, 2008. execute instructions to identify page faults and pre-fetch data pages. [19] A. Kemper and T. Neumann. HyPer: A hybrid OLTP&OLAP main memory database system based on virtual memory snapshots. ICDE, pages 195–206, 2011. 8. CONCLUSION [20] J. J. Levandoski, P.-A. Larson, and R. Stoica. Identifying hot and cold data in In this paper, we presented a new architecture for managing datasets main-memory databases. In ICDE, 2013. [21] K. Li and J. F. Naughton. Multiprocessor main memory transaction processing. that are larger than the available memory while executing OLTP DPDS, pages 177–187, 1988. workloads. With anti-caching, memory is the primary storage and [22] N. Malviya, A. Weisberg, S. Madden, and M. Stonebraker. Recovery algorithms cold data is evicted to disk. Cold data is fetched from disk as for in-memory OLTP databases. In Submission, 2013. needed and merged with in-memory data while maintaining trans- [23] O. Mutlu, H. Kim, and Y. N. Patt. Techniques for efficient processing in runahead execution engines. ISCA, pages 370–381, 2005. actional consistency. We also presented an analysis of our anti- [24] M. A. Olson, K. Bostic, and M. Seltzer. Berkeley DB. USENIX ATEC, 1999. caching model on two popular OLTP benchmarks, namely YCSB [25] J. Ousterhout, P. Agrawal, D. Erickson, C. Kozyrakis, J. Leverich, D. Mazières, and TPC-C, across a wide range of data sizes and workload pa- S. Mitra, A. Narayanan, G. Parulkar, M. Rosenblum, S. M. Rumble, rameters. On the workloads and data sizes tested our results are E. Stratmann, and R. Stutsman. The case for ramclouds: scalable high-performance storage entirely in dram. SIGOPS Oper. Syst. Rev., convincing. For skewed workloads with data 8⇥ the size of mem- 43(4):92–105, Jan. 2010. ory, anti-caching has an 8⇥-17⇥ performance advantage over a [26] A. Pavlo, C. Curino, and S. Zdonik. Skew-aware automatic database disk-based DBMS and a 2⇥-9⇥ performance advantage over the partitioning in shared-nothing, parallel OLTP systems. In SIGMOD, pages same disk-based system fronted with a distributed main memory 61–72, 2012. [27] D. R. K. Ports, A. T. Clements, I. Zhang, S. Madden, and B. Liskov. cache. We conclude that for OLTP workloads, in particular those Transactional consistency and automatic management in an application data with skewed data access, the results of this study demonstrate that cache. OSDI’10, pages 1–15, 2010. anti-caching can outperform traditional architectures popular today. [28] R. Stoica and A. Ailamaki. Enabling efficient os paging for main-memory oltp databases. In DaMon, 2013. [29] M. Stonebraker, S. Madden, D. J. Abadi, S. Harizopoulos, N. Hachem, and 9. ACKNOWLEDGEMENTS P. Helland. The end of an architectural era: (it’s time for a complete rewrite). In VLDB, pages 1150–1160, 2007. This work was funded in part by the Intel Big Data ISTC. In ad- [30] M. Stonebraker and L. A. Rowe. The design of POSTGRES. SIGMOD, pages dition, the authors would like to thank Donghui Zhang and VoltDB 340–355, 1986. for their input in the early stages of this project. [31] T. Team. In-memory data management for consumer transactions the timesten approach. SIGMOD ’99, pages 528–529, 1999. [32] The Transaction Processing Council. TPC-C Benchmark (Revision 5.9.0). 10. REFERENCES http://www.tpc.org/tpcc/, June 2007. [1] eXtremeDB. http://www.mcobject.com. [33] A. Thomson, T. Diamond, S.-C. Weng, K. Ren, P. Shao, and D. J. Abadi. [2] H-Store. http://hstore.cs.brown.edu. Calvin: fast distributed transactions for partitioned database systems. In [3] MemSQL. http://www.memsql.com. SIGMOD, pages 1–12, 2012. [4] VoltDB. http://www.voltdb.com. [34] A. Whitney, D. Shasha, and S. Apter. High Volume Transaction Processing Without Concurrency Control, Two Phase Commit, SQL or C++. In HPTS, [5] Oracle TimesTen Products and Technologies. Technical report, February 2007. 1997. [6] P. M. G. Apers, C. A. van den Berg, J. Flokstra, P. W. P. J. Grefen, M. L. Kersten, and A. N. Wilschut. PRISMA/DB: A parallel, main memory relational DBMS. IEEE Trans. on Knowl. and Data Eng., 4(6):541–554, 1992. [7] J. Baulier, P. Bohannon, S. Gogate, S. Joshi, C. Gupta, A. Khivesera, H. F. Korth, P. McIlroy, J. Miller, P. P. S. Narayan, M. Nemeth, R. Rastogi, A. Silberschatz, and S. Sudarshan. Datablitz: A high performance main-memory storage manager. VLDB, pages 701–, 1998. 1953