DiStash: A Disaggregated Multi-Stash Transactional Key-Value Store
Yiming Gao, Hieu Nguyen, Jun Li, Shahram Ghandeharizadeh · 2026
Read DiStash: A Disaggregated Multi-Stash Transactional Key-Value Store by Yiming Gao, Hieu Nguyen, Jun Li, Shahram Ghandeharizadeh (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-27979.txt.
Introduction
Applications often spread data across several storage media. Each medium, called a stash, has different speed and durability. Yiming Gao and three colleagues present DiStash in 2026, a transactional key-value store spanning pools of stash types. Memory, solid-state disks, hard disks, and non-volatile memory are the examples. One transaction can read and write copies across different pools. Applications no longer juggle consistency themselves.
DiStash prevents race conditions that would desynchronise copies across pools. It also guards against failures that lose key-value pairs. A pool can be set as ephemeral or durable storage. Contents can be replicated across pools or tiered exclusively. The implementation extends FoundationDB. Microbenchmarks and eBay's production workload quantify the design trade-offs. The system tolerated failures of stashes in either storage class. The implementation is open source. Cache-augmented databases and hierarchical storage structures are named applications.
Catalog record
| CREATOR | Yiming Gao, Hieu Nguyen, Jun Li, Shahram Ghandeharizadeh |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.27979
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
DiStash: A Disaggregated Multi-Stash Transactional Key-Value Store Yiming Gao, Hieu Nguyen, Jun Li, Shahram Ghandeharizadeh Abstract . A stash is a storage medium such as Dynamic Random Access Memory (DRAM), Solid State Disk (SSD), Hard Disk Drive (HDD), or Non-Volatile Memory (NVM). This paper presents a disaggregated transactional key-value (KV) store, DiStash, that governs KVs across pools of stash types. It enables an application to use a single transaction to read and write different copies of one or more key-value pairs across the different pools of stashes. It simplifies the application logic by (a) preventing undesirable race conditions that may cause copies of data across different stash pools to become inconsistent and/or (b) failures that may result in loss of key-value pairs. A configuration of DiStash may use a pool of stashes as either ephemeral or durable storage. The application dictates whether the content of its participating stashes are inclusive (replicated) or exclusive (tiered). We implement a DiStash by extending FoundationDB. We quantify the tradeoffs with its design decisions using microbenchmarks and eBay’s production workload. We open source our implementation at https://github.com/ebay-USC/DiStash . 1. Introduction Advances in computing, networking, and mass storage devices have introduced disaggregation of storage. Dynamic Random Access Memory (DRAM) ( 24 ; 3 ) , Solid State Disk (SSD) ( 7 ; 4 ) , Hard Disk Drive (HDD) ( 18 ; 12 ; 32 ) , and alternative forms of Non-Volatile Memory (NVM) ( 31 ; 34 ) including NVDIMM ( 22 ; 5 ; 23 ) are a type of stash that offer different speed, storage capacity, failure characteristics, and price points ( 13 ; 14 ) . To provide online access to a large data set, an application may construct pools of stash types. It may either duplicate or migrate data across the different pools with the objective to maximize the number of references to the pool with the fastest stash. This principle is the cornerstone of cache-augmented database management systems ( 15 ; 1 ; 26 ; 28 ; 27 ) , load balancing techniques using a front-end cache ( 9 ; 20 ) , and hierarchical storage structures ( 6 ; 10 ; 36 ) . A challenge of such systems is how to maintain copies of data consistent across different stash pools. The current practice of using different transactional storage managers with different pools may result in undesirable race conditions that cause copies of the data to become inconsistent. This means the value of a data item may reflect different values produced by the execution of different transactions ( 16 ; 33 ) . DiStash 1 1 1 DiStash is a play on the word “destash” which means to declutter or switch locations. is a disaggregated software architecture that builds upon the FoundationDB ( 37 ; 38 ) . It manages data across different stash pools using one transaction. The stash pools may be scattered across different data centers. A configuration of DiStash may specify a different degree of replication for data in a stash pool. This is to tolerate failures of stashes in that pool. An application may maintain a copy of the data on different stash types as illustrated in Figure 1 . Figure 1 . DiStash with three pools of stashes: DRAM, SSD, and HDD. The pool of DRAM stashes is for ephemeral storage of 1-hop sub-query results ( 27 ) . The pool of HDD stashes is for durable storage of graph data. The pool of SSD stashes is ephemeral storage for graph data and durable storage for 1-hop sub-query results. A graph query processor may lookup sub-query results in either DRAM or SSD, and process queries using either SSD or HDD. A stash type may be volatile or non-volatile, see the x-axis of Figure 2 . While a volatile stash such as DRAM loses its data after a power recycle, a non-volatile stash preserves its data. A DiStash deployment supports the designation of a stash type’s operational mode as ephemeral or durable, see the y-axis of Figure 2 . Ephemeral may provide the illusion of an infinite amount of storage space by maintaining a subset of data and evicting others. Examples include a cache manager such as memcached ( 25 ) , Kosar ( 11 ) , or Redis ( 2 ) . Durable maintains data permanently and has a fixed storage capacity. Once it acknowledges storage of a key-value pair, the key-value pair persists. Examples include POSIX-compliant file systems such as EXT2 and database management systems, DBMSs, such as SQLite. Figure 2 . A taxonomy of stash types and their usage. Ephemeral and durable behave differently once their storage capacity is exhausted. Should the application attempt to insert additional data, ephemeral may delete perviously inserted key-value pairs to free space for the new key-value pair. Durable returns an error, e.g., ENOSPC (Error No SPaCe) with EXT2 and SQLITE_FULL with SQLite. Contributions of this paper include: (1) DiStash, a transactional storage manager that supports pools of stashes each with a different number of instances and degree of replication. The stashes may be spread across multiple data centers. Section 3 . (2) A DiStash transaction may read and write data from different pools of stashes. Section 3.2 . (3) An implementation of DiStash using FoundationDB ( 37 ; 38 ) . It may be deployed across multiple data centers. Section 4 . (4) An evaluation of two DiStash deployments across 3 data centers using eBay production workload. Section 5 . (5) We open source our software at https://www.github.com/ebay-USC/DiStash . The rest of this paper is organized as follows. Section 2 motivates DiStash by presenting several use cases of it. Subsequently, we describe each of the above contributions in turn. Section 6 presents related work. Brief conclusions and future research directions are presented in Section 7 . 2. Motivation: Applications of DiStash DiStash has wide applicability described by the following use cases. 2.1. Cache-Augmented Data Stores DiStash may be used to implement cache augmented data stores ( 27 ; 28 ) in support of read dominated workloads such as social networking ( 28 ) or fraud detection ( 26 ) . It may consist of 2 stash pools. SSD for durable storage of data used for query processing. DRAM for ephemeral storage of query results for their fast lookup with repeat queries. Conceptually, the data on the different stashes is inclusive (replicated). However, the physical representation of data is exclusive (tiered) because the result of queries is different than the data used to process those queries. With eBay’s production workload, a cache-augmented graph database lowers 95 th and 99 th percentile of query response times by at least 2x and 1.63x, respectively ( 27 ) . Section 3.1 presents cache-augmented data stores in greater detail. Briefly, an update may be required to modify data on SSD and the impacted query results in DRAM. DiStash enables the application to perform both in one transaction. Section 3.2 highlights the significance of using one transaction. It shows with multiple transactions to manage data across different pools of stashes, undesirable race conditions may cause copies of data across these stash pools to reflect different values produced by different transactions. DiStash frees