Modern persistent key-value stores, such as RocksDB [48] and LevelDB [27], are typically built using log-structured merge trees (LSMs) [53]. The key idea behind LSMs is buered log structuring.
Writes are rst buered in memory, and then eventually ushed to immutable les on disk. These les are then periodically compacted (i.e., merged) in the background to remove overwritten and deleted records. LSMs are popular because they provide stellar write performance. They ensure that all disk writes are sequential, which exploits the high sequential write bandwidth of traditional disks.
Yet despite these benets, LSMs are not a silver bullet in keyvalue store design. While their design makes writes ecient, it comes at the cost of reads, since records can be present in multiple locations on disk. This is why systems like RocksDB and LevelDB employ block caches, Bloom lters [7,22], and various compaction strategies [9,19,50]-complex and hard-to-tune [47] techniques all aimed at reducing the I/O overhead of reads. For traditional disks (e.g., HDDs and SATA SSDs), this write versus read performance trade-o has been the preferred choice. Random I/O on traditional disks is prohibitively expensive, and so any design that minimizes the amount of random I/O outshines the competition. But is this trade-o still the right one for modern storage devices?
We make the observation that modern NVMe SSDs no longer suer the same signicant random write drawback as traditional disks [29]. With enough request parallelism, NVMe SSDs can achieve their peak sequential write throughput through random writes [29,39,56]. This naturally leads us to a research question: how should a persistent key-value store's design change for NVMe SSDs where random writes are comparable to sequential writes in performance?
Our hypothesis is that an update-in-place design is the answer for larger-than-memory workloads that are (i) read-heavy, or (ii) skewed write-heavy. Update-in-place designs, such as a classical disk-based B+ tree [16,51,52], can oer excellent read performance because each record is stored in a single location on disk-requiring only one I/O to read, if inner nodes are cached in memory. High read performance is desirable because read-heavy workloads such as caching [8,45] or analytics [4,11,40] are common in practice [10].
While disk-based B+ trees do have these read benets, they are also known to suer from their own challenges. First, updating a single record on a page requires reading and writing the entire page, which leads to write amplication. Second, scans can lead to random reads because logically consecutive leaf pages are not necessarily stored sequentially on disk; on NVMe SSDs, we observe that random reads still underperform sequential reads. Third, inserts also cause write amplication because of the need to "make space" in the on-disk structure to hold the new records.
Thus, in order to validate our hypothesis, we need to develop a new design for NVMe SSDs that has the read benets of a classical update-in-place design while also mitigating its traditional write drawbacks. In other words, observing that the fast random I/O of NVMe SSDs would be favorable for an update-in-place design, we propose techniques to make such a design competitive across the board. Our new design leverages three complementary techniques: (A) record caching to reduce read/write amplication in skewed workloads, (B) page grouping to translate scans into sequential reads, and (C) insert forecasting to reduce the I/O needed to "make space" for new records. We implement these techniques in TreeLine, a new update-in-place key-value store designed for NVMe SSDs.
TreeLine buers all writes in its record cache (key idea A), allowing it to (i) keep hot records in memory for as long as possible, and (ii) batch writes that go to the same on-disk page to amortize the I/O costs for updating a page. Caching records instead of pages eciently uses the capacity of the cache even when hot records are not clustered on a few pages. This is true in many real applications: popular items on an e-commerce platform have scattered item IDs, while the activity of users of a social media website is similarly unrelated to their name. In both cases, hot items are updated frequently, illustrating the importance of skewed update-heavy workloads.
Instead of laying out pages randomly on disk, TreeLine groups pages storing adjacent key ranges so that they are stored contiguously on disk (key idea B). Doing so lets TreeLine make long physical reads, which benets scans, while still allowing it to access data at page granularity for point reads. Moreover, TreeLine uses linear models to map records to specic pages within page groups. This helps TreeLine keep its in-memory index small, as it only needs to index the page group boundaries (instead of every page boundary).
Finally, to address the expensiveness of inserts in an update-inplace design, TreeLine exploits the repetitiveness in skewed insert workloads to forecast the location and volume of inserts it expects to receive (key idea C). It uses the forecast to leave appropriate space in its on-disk pages, thereby reducing how frequently it needs to reorganize its on-disk pages to accommodate the new records. TreeLine tracks the inserts observed across dierent parts of the key space and extrapolates these trends forward-a simple but eective technique as we show in our evaluation (see Section 5).
Our proposed techniques provide benets over other recent designs that revisit update-in-place for NVMe SSDs. LeanStore [36] does not optimize for the out-of-memory case, even though it is ecient when the working set ts into memory. KVell [39] indexes every key, leading to a higher memory overhead than TreeLine, which only indexes segment boundaries using page grouping.
We evaluate TreeLine on YCSB [17] using synthetic and realworld datasets. We compare TreeLine against (i) RocksDB [48], a widely-used LSM key-value store, and (ii) LeanStore [36], a stateof-the-art update-in-place key-value store. Across our point YCSB workloads with 1024 byte records, TreeLine outperforms RocksDB and LeanStore by 2.20⇥ and 2.07⇥ respectively on average. Although TreeLine makes some random reads from disk, we nd that it still outperforms RocksDB and LeanStore by 2.50⇥ and 2.80⇥ respectively with 16 threads on uniform scan-heavy workloads.
Contributions. In summary, we make the following contributions:
• We analyze the key performance challenges that arise when employing an update-in-place design on NVMe SSDs and make the case for addressing them with our key ideas. Figure 1: Random write throughput as we increase the number of concurrent writing threads on two distinct NVMe SSDs. The dotted line is each SSD's peak sequential write throughput. The setup for Figure 1a is as described in Section 5.1.
• We propose page grouping: a technique that boosts scan performance by writing logically adjacent pages together onto disk. We have open-sourced TreeLine [60].
TreeLine is a new update-in-place key-value store for NVMe SSDs. Before diving into its design, we rst make the case for why we believe that now is the time to revisit update-in-place designs over LSMs-the current popular design choice.
Random Writes ⇡ Sequential Writes on NVMe SSDs. Recently, NVMe SSDs have become readily available. NVMe SSDs follow a completely dierent storage paradigm compared to traditional hard disk drives. Free from mechanical elements like a spinning disk and a moving head, they instead utilize solid state components and employ an address translation layer to reduce device wear. This shift not only reduces overall access times, but provides two crucial benets: (i) accessing data sequentially is no longer mechanically superior to accessing them randomly, and (ii) highly parallel requests are now feasible [15], which can be used to hide most of the access latency [56]. To empirically conrm these characteristics, we run a series of experiments on an Intel DC P4510 NVMe SSD [31] and the NVMe SSD on AWS c5d.9xlarge instances [3]. As shown in Figure 1, we use o [5] to measure the write throughput while varying the (i) request size, and (ii) number of concurrent writing threads. As we increase the number of concurrent writing threads, both devices' random write throughputs approach their peak sequential write throughputs (1050 MiB/s [31] and 750 MiB/s).
LSMs Leave Read Performance on the Table . As we describe in Section 1, LSMs optimize for writes; but their design also complicates reads. To see how much read performance LSMs "leave on the table", we compare RocksDB (a widely-used LSM key-value store) against our own naïve disk-based B+ tree (an update-in-place system) on an Intel DC P4510 NVMe SSD. We also run TreeLine, Figure 2: TreeLine, a disk-based B+ tree, and RocksDB compared on Zipan read/scan/update workloads. We vary the proportion of updates in the workload from 0% to 100%.
our new system. We compare the systems on a Zipan-distributed (\ = 0.79) workload consisting of reads, updates, and scans on 64 byte records. We vary the proportion of update requests from 0% to 100%. Of the requests that are not updates, 10% are range scans and the rest are point reads. Figure 2 shows each system's throughput in thousands of requests per second. For read-heavy workloads (i.e., less than 40% updates), the limitations of the LSM design lead to RocksDB performing similarly to or worse than our naïve diskbased B+ tree (see Section 5.1 for our experimental setup). TreeLine, using an update-in-place design, takes this performance dierence a step further and outperforms RocksDB all the way up to 80% updates. We outline the key ideas behind TreeLine in Section 3 and we describe why and when it outperforms RocksDB in Section 5.
Summary. The advent of modern NVMe SSDs means that random writes are no longer signicantly more expensive than sequential writes. We believe that this change aords us an opportunity to reconsider how to design persistent key-value stores. Free from needing to ensure sequential writes, we believe that adopting an update-in-place design is a good choice because they excel at readheavy workloads-an important and common class of workloads.
Although writes are more challenging in an update-in-place design, we present techniques in Section 3 that mitigate these challenges.
Workload Skew Does Not Care About Your Layout.
Even in cases where the total size of our data is large enough to warrant using modern storage media instead of a purely in-memory solution, it is usually the case that our working set is much smaller than that, as well as relatively stable in the short term. Given the performance discrepancy between main memory and storage access times, some form of caching would be benecial. The question then becomes, what granularity this cache should be at.
We argue that record caching is the better option for providing good cache utilization when pursuing an update-in-place design. Certainly, this choice increases the metadata:data ratio for the cache memory usage, since the xed metadata overhead for each cache entry is now incurred per record (possibly a few bytes) instead of per page (4 KiB in our design). However, the alternative of page caching has the potential for even worse memory consumption.
Consider a working set that is uncorrelated with the key sort order -one example would be a database of user metadata, where the activity of users is not correlated to the value of their user_id. An LSM design, like RocksDB [48], would consolidate updates from hot users in the write buer and later in level 0 les. Caching the blocks in these les and continuing to employ the write buer would be sucient to keep the working set in memory.
An update-in-place design, on the contrary, cannot perform this consolidation eciently. Having a single "true" copy of the record means that frequent and costly reorganizations would be required to consolidate hot records in "hot pages". A more sustainable option is to organize records in some workload-independent way, such as having each page responsible for a specic key range at any time. Then, page caching could lead to signicant cache underutilization. In the worst case, there could only be a single few-byte hot record in each of several dierent pages. As such, caching at record granularity is preferable in an update-in-place design.
Small Pages, Large Pages: Why Not Both?
From the perspectives of space amplication and I/O reduction, the ideal page is as small as possible (often 4 KiB in practice). Indeed, pages can be seen as simply an unfortunate artifact of current storage technology, with novel media like Optane persistent memory [33] pushing the boundary towards byte addressability.
However, small pages hurt range scans, which benet from reading large amounts of contiguous data from storage. This is because small random reads still do not perform as well as sequential reads on NVMe SSDs; the best way to utilize the full read bandwidth is through large requests [29,56], making large pages attractive.
To bridge this gap, we propose page grouping. The idea is that pages themselves are small but contiguous on the storage device, providing the potential for larger reads when needed. As a thought experiment, one could implement this idea for the entire key space, laying out the data consecutively in pages and keeping the page boundaries in memory. But this design will suer in the face of inserts, requiring us to re-write (on average) half of the entire database whenever we insert a record.
Instead, we implement page grouping locally, by co-locating pages produced during each reorganization-creating data segments. Grouping also lets us reduce the number of entries we have to index in memory to only one entry per segment. We can achieve this by (i) tting a piece-wise linear model over the keys and their positions in the data segment, and then (ii) using the linear components of the model to dene and nd the page boundaries. Each linear model indexes records belonging to one data segment and we place the records into the pages using the model to ensure that there is no indexing error (model-based inserts [1,23]). This approach both (i) allows for long reads when needed, and (ii) leads to a compact in-memory index without sacricing page-level access for point operations. The in-memory index only stores each segment's lower boundary, linear model, and location on disk; this information is enough to compute the correct page for any key.
Page grouping is governed by two parameters, goal and epsilon, which represent (i) the target ll rate of each page, and (ii) the maximum deviation that a model's prediction can have from a record's true position in the dataset. A user would typically set these parameters by rst selecting goal (which impacts TreeLine's space amplication) and then maximizing epsilon, within the constraints of the maximum number of records that can t in a page. Space for at least epsilon records must be left at each of the front and back of the page, to deal with model error near page boundaries.
For example, when using 64 byte records, each page ts up to 54 records after accounting for a 10-byte slot per record and the 89-byte page header (see Section 4.4). In our experiments, we nd that setting goal to 44 and epsilon to 5 provided good performance. We study how these parameters aect the segments in Section 5.4.
Half-Full Pages Are Usually Half-Empty.
Even with page grouping, requiring reorganization for each insert is impractical; data pages must contain empty space to absorb some inserts. This is common in tree data structures, which split a full node into two half-full ones. However, in a disk-based updatein-place design, empty space creates amplication during I/O. Thus, we must leave empty space intelligently, by leveraging patterns in the inserts to generate forecasts about the future insert load. During reorganization, we then leave empty space according to this forecast, decreasing space amplication while still absorbing inserts in a high-performance manner. For this paper, we maintain an in-memory histogram to track the distribution of inserts and use it to forecast inserts for each part of the key space, but TreeLine is also compatible with more elaborate forecasting schemes.
In this section we describe TreeLine, which implements our three key ideas. As shown in Figure 3, TreeLine responds to the performance characteristics of modern storage media by using an update-in-place design, consisting of two main parts: (i) a Tree, an in-memory index to map reads and writes to pages, and (ii) a Line of variable-sized on-disk data segments, all on a single logical level. Section 4.1 describes each supported operation, while Sections 4.2-4.6 then introduce the individual components of TreeLine. Sections 4.7 and 4.8 deal with crash consistency and recovery, as well as thread synchronization, respectively.
Lookups. Lookups rst check the record cache (Section 4.2), which contains the most recent version of a record. If the key is not cached, the in-memory index (Section 4.3) is used to nd the correct data segment, while the associated linear model (if any) locates the data page (Section 4.4). That page is brought into memory and searched. If the key is still not found, the page's overow page (if any) is also brought into memory and searched. If there is no match in the overow page either, TreeLine reports that the key was not found. Data Modications. Inserts, updates, and deletes initially create or update an entry in the record cache. Once the entry is later selected for eviction, TreeLine nds the corresponding data page using the in-memory index and segment linear model (if any), and brings it into memory to perform the operation, together with its overow page (if any). If the base and overow page are both full, reorganization is triggered (Sections 4.5 and 4.6).
Range Scans. Range scans proceed like lookups, but both the record cache and appropriate data page(s) (base and overow) are always checked for keys within the specied range, which are then merged in key order. Records encountered in the record cache override records with the same key that might exist on a data page.
Cache Admittance. Whenever TreeLine admits a record into the record cache, it sets a priority level for the entry, from 0 to ? <0G . The priority is incremented whenever a cache entry is accessed.
We admit records into the record cache on three dierent occasions. First, any data modication request (insert, update, delete) by the user is cached with priority ? <83 = ? <0G /2. If no entry with the same key is already present, TreeLine possibly evicts an entry to make space. Second, any lookup of a non-cached record will cache the record with priority ? <83 after retrieving it from the appropriate data page. Third, we can choose to optimistically also cache additional entries from the same page with priority 1 whenever we cache a record through the lookup path.
Cache Eviction. TreeLine uses the clock algorithm to evict entries from a full cache: it cycles through cache entries until it nds an entry with priority 0, the eviction candidate, decrementing the priority level of each entry it encounters. If the eviction candidate is dirty, we continue advancing the "clock hand" up to 32 entries to nd a clean candidate instead. We do this to prefer evicting entries that do not require I/O. If the nal eviction candidate is dirty, we also write out all dirty cache entries that would go to the same page, but do not evict them. This helps amortize the eviction I/O costs. We have chosen this eviction algorithm because of its minimal synchronization overhead, which is crucial under high parallelism: just a single pointer needs to be atomically updated, compared to e.g., moving an arbitrary element to the back of an LRU queue.
The in-memory index is our map to the on-disk portion of the data. We employ the TLX btree_map [6]: a fast but traditional B+ tree.
Consulting the In-Memory Index. For both evictions of dirty cache entries and lookups/scans of non-cached keys, TreeLine needs to retrieve the correct segment and page for keys. This is achieved through the in-memory index, which maps the lexicographically smallest key of each data segment to the appropriate (physical) segment identier. This is sucient because data segments cover mutually exclusive and collectively exhaustive key ranges. For multi-page segments, a compact linear model is also stored in the in-memory index in order to select the correct data page within the segment without needing additional index nodes.
Updating the In-Memory Index. TreeLine updates the in-memory index during reorganization (see Section 4.5). A read/write latch protects against concurrent in-memory index lookups. Although we have not seen a noticeable impact of this latch, one could use an opportunistic concurrency scheme [38] instead in future work.
Data Pages. TreeLine stores data in data pages. We adapt the physical page design from the implementation of BTreeNode in LeanStore [2,36]. The page size is currently set to 4 KiB to match the page size of the underlying SSD. Each data page uses common prex compression based on the lowest (inclusive) and highest (exclusive) key that it is responsible for, as dened at page creation time. It stores records in insertion order in the back of the page, while a sorted array of slots grows from the front of the page, with each slot pointing to a record; this maintains sorted access while reducing the copying overhead during data modication operations.
Data Segments. As introduced in Section 3.2, TreeLine employs page grouping to co-locate some data pages on disk, creating data segments ("ungrouped" data pages are "single-page data segments"). Data segments consist of pages with the layout described above, together with any possible overow pages (see Section 4.5). The non-overow (base) pages comprising a data segment are laid out logically contiguously on disk. For multi-page data segments, the in-memory index stores a linear model together with the segment identier, letting TreeLine nd the correct page within the segment for a given key. More details are covered in Section 4.5.
Overow Pages. When a data page becomes full, TreeLine allocates an overow page, which is not added to the in-memory index; it is accessed through the base page that overowed. Overow pages are laid out like base pages, and each inherit responsibility for the same key range as their base page. Each of the base and the overow page remains sorted (using slots), but no guarantees are provided for the ordering of keys between these two pages.
Overow pages help us collect more records for a given segment, to amortize the reorganization cost. Once an overow page also lls up, the entire segment involved, called the full segment, will be reorganized. We do not allow for more than one overow page per base page to bound the cost of lookups and data modications.
Page Orderings. For clarity, we distinguish three types of page orderings. Our data pages match the page size of the underlying SSD (4 KiB), so these orderings apply to pages in both the "TreeLine" and the "SSD" sense. The physical order refers to the actual page locations on the SSD. It is not exposed, since the drive itself abstracts it away to balance device wear through out-of-place writes. Instead, the drive exposes a logical order of pages, implemented in the device controller. In TreeLine, each base data page contains keys for a disjoint region of the key space. Based on the lower boundaries of these regions, we also get the key order of pages.
Reorganization. We now move on to the reorganization process, which is divided into four phases. Range detection is followed by one or more iterations of model building and segment write-out, followed by the index update. We provide an example in Figure 4.
Phase I: Range Detection. Only considering records from the full segment can lead to sub-optimal data layouts. Instead, TreeLine also looks "around" the full segment ( for segments with reorganization potential: segments with at least one base page with a (not necessarily full) overow page. It examines neighboring segments in key order, up to a distance of A (currently set to 5) segments from ( in each direction. This process results in a set of up to 2A + 1 segments to be reorganized, which we call pre segments, which are contiguous in key order and include (. In Figure 4a, Phase I nds two neighboring segments with reorganization potential around (.
Phase II: Model Building. This phase operates on the sorted set of all records in the pre segments, called the reorganization set, if it is non-empty. It is visualized as the collection of ovals in Figure 4b.
TreeLine considers records from the reorganization set in key order and tries to place them into as-large-as-possible newly-created segments, which we call post segments. Each page, together with its associated overow page, is brought into memory as needed and kept there until all of its records have been written into new segments. In Figure 4b, Pages 131, 056, 132, 213, 214 and 091 have been brought into memory. We call the smallest key (in key order) of the reorganization set the reference key, which will be the smallest key in the rst page of the new segment being built.
While considering each record, TreeLine builds a linear model (light green line in Figure 4b) using the PGM index's [24] optimal piecewise linear regression algorithm [54]. We chose this algorithm because it produces the optimal (fewest) segments in one pass over the data [24,54]. This model will determine the correct page for a record within the segment, based on the record's key and the segment's reference key. It relates the distance between the record's key and the reference key in key space to their distance within the reorganization set. For example, if the keys in the reorganization set are {"a", "c", "f"}, the reference key is "a" and the distance of "f" from "a" is 5 in key space, but 2 in the set.
A linear model is space-ecient and reasonably accurate at the granularity of the reorganization set, but it will still accumulate error. We continue processing successive records, until we hit a congurable error threshold epsilon, indicated by the dashed dark green line in Figure 4b. Setting epsilon reects a trade-o. A large epsilon will let us process more records, but the resulting model will be less accurate. To compensate, we will need to place fewer records per page, increasing space amplication. On the other hand, a small epsilon will only let us process fewer records at a time, leading to smaller segments and eroding the benets of page grouping.
Once we reach the error threshold, the current iteration of Phase II ends. Any processed records are sent to Phase III as a write-out set and removed from the reorganization set, before repeating Phase II.
An iteration of Phase II is also terminated early in three cases. One is whenever the contents of the reorganization set t on a single page. No model is needed for a single-page segment, so we directly forward all the records to Phase III. The second case is whenever we exceed the memory budget set aside for reorganization; remember that each page with processed records is kept in-memory during model building. In this case, we stop and forward the records and model to Phase III, even if the model error was still below epsilon. The third case is when we have processed enough records (16 * goal) to t a 16 page segment without exceeding epsilon.
Phase III: Segment Write-out. Given a write-out set and a model from Phase II, Phase III materializes the post segment. As shown in Figure 4c, the model is used to place the records in a number of logically contiguous pages on the SSD, either freshly allocated or retrieved from a free list (see Phase IV). The number of pages is determined by dividing the size of the write-out set by the goal parameter. However, to simplify le management, TreeLine only creates xed-size segments containing 1, 2, 4, 8, or 16 pages. So, if the proposed post segment comes out to e.g., 10 pages, TreeLine will only create an 8 page post segment with goal records per page, returning the leftover records to the reorganization set for processing in the following iteration of Phase II. Phase III also generates a unique non-zero production ID associated with this segment and includes it in the rst page of the post segment.
Phase IV: Index Update. TreeLine concludes the reorganization process by updating the in-memory index. The entries for the pre segments are deleted, while entries with the reference key, model (if any) and segment identiers of the post segments are inserted. The pre segments are then invalidated by overwriting their production ID with the value zero, which aids recovery (see Section 4.7). They are then added to a free list, from where they can be retrieved by a future reorganization to be overwritten with its post segments.
Tracking Inserts. We base our insert forecasting on statistics we collect from tracking inserts. We divide the workload into epochs, which represent a certain number of workload inserts (e.g., 100,000). Over the course of an epoch, we build an equi-depth histogram with 1 partitions that captures the distribution of inserts. For each insert, we increment the counter of the histogram bin corresponding to the key (an $ (log 1) operation). To reduce tracking overhead, we could sample inserts, but we nd that the overhead is less than 100 ns per insert, which is negligible for disk-based systems. Once an epoch ends, we "freeze" its histogram and use it for forecasting the distribution of future inserts, discarding any older histograms. This way, there are always two histograms: one being built based on the current epoch and one "frozen" from the last epoch. Besides the epoch size, we need to congure the parameter 1. In the extreme case, each partition would correspond to one data page. However, we nd a more coarse-grained partitioning to be sucient for our workloads. Since we use an equi-depth histogram (as opposed to equi-width), we need to set the partition boundaries. In theory, we could use the full data for this purpose, but this would cause I/O. Instead, we maintain an in-memory reservoir sample [41] of the inserts. At every point in time, that sample represents a uniform random sample of the base data. When creating a new histogram, we sort the in-memory sample and use it to determine approximate partition boundaries. By default, we use a sample size of 10 ⇤ 1.
Generating Forecasts. To forecast inserts for a segment, we use its boundaries to query the "frozen" histogram and sum the counters of intersecting partitions. For partitions that partially overlap the query range, we use linear interpolation. We then forecast inserts for the 5 epochs following the epoch of the "frozen" histogram.
Utilizing Forecasts. During reorganization, we use insert forecasting to determine the empty space in each page, by setting the goal parameter. Using a pessimistic estimate of the number of keys in the current segment, together with the insert forecast, we can determine how many pages will be needed. We then set the goal so as to distribute the current records evenly across these pages.
Interaction with Page Grouping. Both insert forecasting and page grouping aect the physical page layout during reorganizations. The forecasted inserts for a particular segment inuence the goal parameter, which in turn aects the epsilon parameter, as per Section 3.2, since the maximum number of records per page must not be exceeded. Finally, both goal and epsilon impact the linear model construction, by inuencing the transition to Phase III and the post segment size (see Section 4.5).
Crash Consistency. The on-disk information should enable Tree-Line to recover to a consistent state after a crash. Data modication operations only touch a single SSD page, for which the SSD guarantees atomic writes. However, extra care is needed for the two processes that edit multiple pages at a time: overow page allocation and reorganization. When allocating an overow page, we rst write it to disk, before providing the corresponding base page with the overow page identier and writing out the base page as well. We use Check I below to recover from crashes between Table 1: Segment (left) and page (right) lock compatibility.
these two writes. For reorganization, we detect and repair crashes when only some of the post segments have been written out using Check II below. In Phase I, a START REORG record is added to the write-ahead log, including a new globally unique production ID and a list of the pre segments and their current production IDs. The new production ID will also be stored on the post segments resulting from this reorganization. In Phase IV, an END REORG record is appended to the write-ahead log, with the same production ID.
Recovery. We now present a sketch of recovery based on the above scheme. We leave the implementation of this sketch for future work.
Recovery aims to rebuild the in-memory index based on the ondisk data pages. It scans data segments in logical order and inserts the reference key of each into the in-memory index. Any overow pages are deferred to be examined again in the end of the scan, by which point the corresponding base page should be already indexed. We then perform Check I: we use the lower bound of each overow page to nd the correct base page through the in-memory index, and ensure the base page points to the overow page.
Before the data page scan, TreeLine also performs Check II: it checks the write-ahead log for any START REORG records without an END REORG record with the same production ID. Among such in-ight reorganizations, there are two cases. If there is at least one pre segment on disk with a production ID not matching the one logged in the START REORG message, Phase IV must have been reached before crashing. We then treat the reorganization as successful, invalidate any pre segments that still have the production IDs logged in the START REORG message, and treat the post segments as valid when we encounter them during the page scan.
However, all pre segments might still match the production IDs in the START REORG record. In this case, we deem the reorganization failed and treat the pre segments as valid during the page scan, include them in the in-memory index and re-attempt the reorganization after recovery. At the same time, we identify any post segments we encounter during the page scan using the production ID of the START REORG record, and treat them as invalid.
Note that, for each given crash, there could be at most as many concurrent reorganizations as the number of user threads, providing an upper bound on the amount of work needed during recovery.
TreeLine uses two types of locks: segment locks and page locks. Table 1 provides their compatibility matrices. Segment locks can be acquired in Intention Read, Intention Write, reOrganization or reOrganization eXclusive mode. Page locks can be acquired in Shared or eXclusive mode. One page lock protects both a base page and its overow page. We will now explain our locking strategy.
Lookups. TreeLine rst locks the appropriate segment in IR mode. It then locks the appropriate page in S mode and performs the lookup. The page lock is then released before the segment lock. Data Modications. TreeLine rst locks the appropriate segment in IW mode. It then locks the appropriate page in X mode and performs the operation. The page lock is then released before the segment lock. If reorganization is triggered, locks are released and TreeLine follows the reorganization path below.
Range Scans. TreeLine rst locks the appropriate segment in IR mode. It then locks each page in the segment in S mode as the scan proceeds, releasing each page lock as soon as the page has been scanned. If the segment is exhausted and the scan is not nished, TreeLine uses lock coupling to avoid a reorganization from intervening: it rsts acquires an IR lock on the next segment before releasing the IR lock on the previous one.
Reorganization. After Phase I, reorganization locks all the pre segments in key order in O mode. This mode lets reads and scans still use the pre segments while the post segments are being created. At the start of Phase IV, TreeLine upgrades to an OX lock, implicitly also waiting for anyone accessing the pre segments to nish their reads. Once the in-memory index has been updated and at least one pre segment has been invalidated, the OX lock is released.
In this work, we present three techniques that mitigate the traditional drawbacks of update-in-place designs, which we implement in TreeLine. As a result, the goal of our evaluation is to examine the eectiveness of these techniques in comparison to (i) LSM-based systems, and (ii) other update-in-place systems. To that end, we aim to answer the following questions:
• How does TreeLine compare against RocksDB [48] (an LSMbased key-value store) and LeanStore [36] (a state-of-the-art update-in-place key-value store) on throughput and the amount of physical I/O performed? (Section 5.2) • How do the record cache and page grouping contribute to Tree-Line's overall performance? (Section 5.3) • How does the choice of the page grouping parameters (goal and epsilon) aect the grouping "eectiveness"? (Section 5.4) • How eective is insert forecasting? (Section 5.5)
We nd that TreeLine outperforms RocksDB by 2.20⇥ and LeanStore by 2.07⇥ on average across our 1024 byte YCSB point workloads. With 16 request threads, TreeLine outperforms RocksDB and Lean-Store by 2.50⇥ and 2.80⇥ respectively on uniformly distributed scan-heavy workloads (YCSB E), averaged across three datasets.
Hardware and Environment. We use a machine equipped with a 20-core 2.10 GHz Intel Xeon Gold 6230 CPU [32] and 128 GiB of memory, running Linux 5.12.5. We use a 1 TB Intel DC P4510 NVMe SSD [31] and the ext4 le system for all our experiments.
Baselines. We compare TreeLine against RocksDB [48] (an LSM key-value store) and LeanStore [36] (a state-of-the-art update-inplace key-value store). We use RocksDB version 6.14.6 [46] and LeanStore at commit d3d8314 [2]. For a fair comparison, we disable block compression and SSTable checksums in RocksDB, since these features are not present in TreeLine. We congure RocksDB and LeanStore to use 4 KiB blocks to match TreeLine's pages. On RocksDB, we enable both Bloom lters and prex Bloom lters [49] with 10 bits and a prex length of 3 respectively (the recommended defaults). We also disable write-ahead logging on all three systems, to distinguish the performance of TreeLine, RocksDB, and LeanStore on write-heavy workloads from the logging overhead.
Workloads. We use our own C++ implementation of the Yahoo! Cloud Serving Benchmark (YCSB) [17] to perform our evaluation. We provide a description of the YCSB workloads in Table 2.
System Congurations. We use 64 byte records (64 B) (8 byte key, 56 byte value) and 1024 byte records (1024 B) (8 byte key, 1016 byte value). Depending on the dataset, we give each system enough memory to store up to 33% of the dataset in memory. Table 3 describes how this memory is used for the Amazon dataset; it also lists the page grouping parameters used. We give TreeLine, RocksDB, and LeanStore access to 4 background threads.
Datasets. We evaluate against three datasets (one synthetic, two real-world): (i) a synthetic dataset of uniformly distributed keys (20 million keys), (ii) an Amazon reviews dataset (33 million keys), and (iii) an Open Street Maps (OSM) dataset (23 million keys) [18]. We plot their key cumulative distribution functions (CDFs) in Figure 6. Checkpoints. To ensure consistent results, we start each experiment from the same database checkpoint, created for each system as follows. We rst load each database with the dataset being tested. Then, we run a 40 million uniform update workload. The purpose of this update workload is to add levels to RocksDB's LSM tree to more closely resemble an LSM that has "been used". Finally, we persist the databases; their on-disk images become the "checkpoints" we use. We run each experiment against a copy of these checkpoints.
Metrics. We primarily measure throughput during the workload and report it as thousands of requests processed per second (kreq/s).
Using iostat [26], we also measure the amount of physical I/O and the physical I/O throughput observed by the operating system. We report TreeLine's throughput relative to RocksDB and LeanStore using speedups. We compute averages by taking a geometric mean.
5.2.1 Skewed Point Workloads. We rst run the YCSB point workloads with Zipan-distributed requests (\ = 0.99). Figure 5 shows TreeLine's, RocksDB's, and LeanStore's throughputs. Since our conclusions are similar across datasets, we only show and discuss our results for the Amazon dataset as it is the largest (33 million records).
TreeLine outperforms RocksDB (LeanStore) by 1.62⇥ (2.81⇥) and 2.99⇥ (1.53⇥) on average for the 64 B and 1024 B congurations respectively. From these results, we draw three conclusions.
TreeLine outperforms RocksDB and LeanStore on skewed update-heavy workloads because it (i) leverages its record cache to reduce write amplication while also (ii) providing ecient reads. We observe that on workload A (64 B), TreeLine writes 3.09 GiB of physical data while RocksDB and LeanStore write 4.27 GiB and 23.1 GiB respectively. TreeLine uses its record cache to reduce the amount of physical writes it makes to an amount that is less than that of RocksDB, thereby mitigating its potentially high write amplication. LeanStore writes signicantly more than TreeLine and RocksDB because it uses a page cache and (i) the YCSB workloads have key skew (hot records are not necessarily clustered on the same pages), (ii) the records are small relative to the page (64 byte records, 4 KiB pages), and (iii) the pages with hot keys do not all t in memory. On the same workload, TreeLine reads 12 GiB of data while RocksDB reads 27 GiB (2.3⇥ more). RocksDB reads more data than TreeLine because it also runs compaction jobs in the background. LeanStore reads 42.2 GiB of data (3.5⇥ more than TreeLine) because record updates require a page read-modify-write. The reason why TreeLine and RocksDB achieve a higher throughput on update-heavy workloads, compared to read-only workloads, is that caching updates allows reads of recent updates to be served from the cache without I/O. In contrast, for read-only workloads, caching a record for the rst time requires I/O on the critical path.
When TreeLine outperforms RocksDB on read-heavy workloads, it is because it performs fewer physical reads. On workloads B and C (64 B), TreeLine reads 19 GiB, while RocksDB reads 31.55 GiB and 65. 35 GiB respectively (1.6⇥ and 3.5⇥ more). For 1024 B, RocksDB reads 5.4⇥ and 6.8⇥ more data than TreeLine on workloads B and C respectively. There are two reasons for these dierences in physical reads. First, as described above, RocksDB launches compaction jobs in the background to merge obsolete records; this work aects workload B because it contains updates. Second, RocksDB has SSTables present on multiple levels. Hence, a point read may need to query multiple SSTables, even with Bloom lters enabled. In contrast, point reads on TreeLine only ever require up to two page reads (base and overow).
TreeLine surpasses LeanStore on the 64 B read-heavy workloads because of record caching. By design, reads are ecient in both TreeLine and LeanStore because they are update-in-place key-value stores. However, as mentioned previously, the YCSB workloads exhibit key skew. Key skew limits LeanStore's buer pool's eectiveness when records are small relative to the page (e.g., 64 byte records). For example on workload C, LeanStore reads 42.2 GiB of data whereas TreeLine reads 18.8 GiB of data.
Workloads. Next, we examine TreeLine's performance on a scan-heavy workload (YCSB E), where page grouping inuences performance. Since the eectiveness of page grouping depends on the dataset (see Section 5.4), we present results for all three of our datasets. For RocksDB, we also enable prex Bloom lters, which help reduce the number of SSTables read during a scan, making RocksDB a strong baseline. We otherwise use the same experimental setup as our skewed point workload experiments. Figure 7 shows our results for uniform and Zipan-distributed scans. With enough parallelism (i.e., 16 request threads), TreeLine achieves average speedups of 1.74⇥ (2.21⇥) and 1.88⇥ (2.50⇥) over RocksDB for Zipan (uniformly) distributed requests against the 64 B and 1024 B congurations respectively. When compared against LeanStore, TreeLine achieves average speedups of 0.91⇥ (1.58⇥) and 1.86⇥ (2.80⇥) for Zipan (uniformly) distributed requests against the 64 B and 1024 B congurations respectively. LeanStore outperforms TreeLine in certain cases due to caching eects, discussed below. From these results, we draw three key conclusions.
TreeLine's speedup over RocksDB on the scan-heavy workloads comes from reading less data from disk, because of its update-in-place design. Table 4 lists each system's (i) physical reads, (ii) physical read throughput, and (iii) workload request throughput for a uniform scan-heavy workload on the Amazon dataset with 16 request threads. The trends are similar across the other datasets. In both congurations shown in the table, TreeLine reads at least 1.9⇥ less data from disk than RocksDB. This dierence leads to TreeLine's throughput advantage despite it having a lower physical read throughput when scanning 64 byte records.
RocksDB reads more data from disk for two reasons. First, there may exist SSTables on multiple levels that overlap the scan range. RocksDB needs to examine all overlapping SSTables (not excluded by the prex Bloom lters) to return the correct records. Second, RocksDB still runs compaction jobs, because the checkpoints we use contain recent updates (see Section 5.1) and RocksDB always launches a compaction job after starting up.
TreeLine has a lower physical read throughput than RocksDB when scanning 64 B records because of its I/O pattern. Although page grouping enables sequentially reading all the pages in a segment, its eectiveness ultimately depends on the dataset and record size (see Section 5.4). Thus, TreeLine's scans also contain random reads, whereas RocksDB's scans translate to long sequential reads.
TreeLine's scan performance is not signicantly aected by request skew. TreeLine's throughput advantage over RocksDB and LeanStore is higher on uniform scan-heavy workloads because RocksDB's block cache and LeanStore's buer pool become less eective. TreeLine cannot use its record cache to avoid I/O during a scan because it only caches individual records; it must always check the on-disk pages for the records that lie in the scanned ranges. RocksDB caches blocks and LeanStore caches pages, which allows them to avoid I/O when a block or page involved in the scan is already cached in memory. For workloads with long scans that exceed the cache's capacity (e.g., Extract-Transform-Loads [10]), we expect RocksDB's and LeanStore's caches to be less eective.
TreeLine's speedups over LeanStore on the 1024 B congurations are due to page grouping. As shown in Table 4, LeanStore and TreeLine read a comparable amount of physical data from disk. However, on the 1024 B conguration, TreeLine achieves a 7⇥ higher physical read throughput, again due to the I/O request pattern. LeanStore scans require scattered 4 KiB page reads whereas TreeLine can read longer segments from disk due to page grouping.
Workloads. We also run our point workloads with a uniform request distribution. TreeLine achieves an average throughput speedup of 1.45⇥ and 1.32⇥ over RocksDB and LeanStore respectively on our 64 B and 1024 B congurations. On read-heavy uniform point workloads (B, C), TreeLine achieves an average throughput speedup over RocksDB (LeanStore) of 1.36⇥ (1.11⇥); on update-heavy uniform point workloads (A, F), TreeLine has an average speedup over RocksDB (LeanStore) of 1.55⇥ (1.57⇥).
The conclusions we draw about skewed point workloads in Section 5.2.1 hold for uniform point workloads as well, with one exception. The record cache is not as eective at decreasing write amplication in uniform update-heavy workloads. Such workloads, especially when the record size is much smaller than the page size, are fundamentally challenging for larger-than-memory update-inplace systems for two reasons. First, write buering (e.g., with a cache) has a limited impact on reducing the number of page reads and writes in uniform workloads since there is no skew. Second, updates of a single record require reading and writing a entire page from disk-leading to high write amplication. TreeLine does not optimize for uniform update-heavy workloads, since skewed point workloads are more common in real-world scenarios [10].
We study the impact of TreeLine's record cache and page grouping with a factor analysis, using the Amazon dataset and 1024 byte records. We run each of the Zipan YCSB workloads with 16 request threads. Figure 8 shows our results, where we successively disable page grouping and then both page grouping and record caching. We report each conguration's throughput relative to that achieved by the full system. From these results, we draw three key conclusions.
Record caching helps reduce read and write amplication in the read/update workload. TreeLine's record cache reduces the total amount of physical reads (writes) by an average of 3.11 ⇥ (2.60⇥), leading to an average throughput speedup of 8.7⇥. The workloads are highly skewed, so caching hot records reduces the necessary SSD accesses, improving throughput.
Page grouping does not negatively aect the point workloads. Even after enabling page grouping, TreeLine maintains its throughput on the point workloads A-D and F. Recall that Tree-Line's in-memory index only stores the (i) key boundaries, (ii) the physical locations of the beginning of each segment (which can consist of multiple pages), and (iii) linear models that map records to pages within segments. Yet, TreeLine does not need to read in an entire multi-page segment to access a single record for point reads and updates; TreeLine can still operate at page granularity by using the linear model to nd the page for a given record.
Page grouping accelerates scans by enabling longer physically contiguous reads. On the scan-heavy workload E, TreeLine's throughput increases by 1.87⇥ once page grouping is enabled despite there being no signicant change in the amount of physical reads. The reason for this improvement is that TreeLine achieves an increased physical read throughput by 1.87⇥, by making more sequential reads. Without page grouping, scans consist of scattered 4 KiB reads, which leads to lower physical read throughput.
TreeLine uses page grouping (i) to boost scan performance and (ii) to shrink the in-memory index. In this section we (i) study how the dataset, goal, and epsilon aect page grouping; and (ii) analyze page grouping eectiveness in our congurations from Section 5.2. Figure 9: The percentage of pages in multi-page segments as we x "goal" and vary "epsilon" and vice-versa.
We measure segment eciency (the percentage of pages that are in multi-page segments) across our datasets; a higher segment eciency is better. In Figure 9a, we x goal and vary epsilon. In Figure 9b, we x epsilon and vary goal. From these results, we draw three conclusions.
Increasing epsilon improves segment eciency. Epsilon represents the error tolerance when building a page grouping linear model. Having a larger error tolerance translates to being able to t a model through more records. This tolerance translates to a greater likelihood of creating a multi-page segment (for a xed goal value).
Increasing goal decreases segment eciency. Goal is the desired number of records to place on a page. Recall that page grouping uses xed segment sizes (1, 2, 4, 8, and 16 pages). Thus, choosing a small goal decreases the maximum number of records that can be placed onto a segment (for a xed epsilon). This is why Figure 9b shows a decreasing trend as goal increases: tting a model through more records with a xed epsilon becomes more dicult.
The dataset aects segment eciency. Page grouping essentially ts linear models over a dataset's CDF. Intuitively, for a xed epsilon, one needs fewer linear models for a CDF with many "linear regions". The Amazon and OSM datasets enable higher segment eciencies, because their CDFs have many "linear regions" (see Figure 6). Interestingly, our uniform synthetic dataset can produce a lower eciency, because its CDF is locally "bumpier". 5.4.2 Index Entries Reduction. With page grouping, TreeLine only indexes the boundaries of each segment (and the linear model), instead of each page boundary. Reducing the number of index entries has two benets: (i) we save memory for other uses, and (ii) index operations are faster because the index is logically smaller.
On our 1024 B (64 B) workloads, page grouping reduces the number of entries in the index by 3.8⇥ (4.8⇥), 4.5⇥ (1.9⇥), and 1.8⇥ (1.8⇥) for the Amazon, OSM, and synthetic datasets respectively. The reduction depends on the segment distribution; having more pages in larger segments means that fewer index entries are needed.
Finally, we evaluate insert forecasting. Among the YCSB workloads, only D and E perform inserts, and only for 5% of the operations. To make the impact of insert forecasting more visible, we instead run a workload consisting of 50% reads/50% inserts. We compare the performance of TreeLine with insert forecasting enabled with the performance of TreeLine without insert forecasting, as well as with the performance of TreeLine given perfect information about the future stream of inserts, thus avoiding reorganizations. The forecasting epoch length is set to 100,000, we use 1 = 20, 000 histogram partitions and forecast inserts for 5 = 100 future epochs.
For our experiments we use a dataset of taxi pickups in New York City, where we have inlined the pickup coordinates into an 8byte key using the S2 geometry library [28]. This dataset has three interesting properties regarding hot keys: (i) they exist (popular taxi pickup areas), (ii) they are not necessarily co-located in the key space and (iii) they change over time (e.g., due to the time of day).
As shown in Figure 10, insert forecasting is mainly eective in the 64 B case, closing on average more than half of the gap between no forecasting and perfect forecasting and reducing reorganizations by an average of 63% (not plotted). With smaller records, the absolute number of inserts that a 4 KiB page can accommodate is higher. This means that insert forecasting can estimate and leave appropriate free space at a ner granularity, delaying reorganization for longer. On average, insert forecasting improves the throughput of TreeLine by 1.22⇥, reducing reorganizations by an average of 41%.
We also explore the sensitivity of insert forecasting to the epoch length for the 64 B conguration using 1 application thread, scaling 1 to keep it at 20% of the epoch length. As shown in Figure 11, very short epochs cannot justify their overhead, but even an epoch length of 10, 000, 10% of the value in Figure 10a, delivers performance benets. Thus, although the epoch length aects performance, coarse-grained tuning is enough to see improvements.
TreeLine bridges update-in-place and LSM-tree designs. Still, it has some limitations, discussed below alongside possible solutions.
Variable-Sized Records. Our current design assumes xed-sized records. While the data pages support variable-sized records, we train linear models on record positions and divide by the maximum records per page to map records to pages. Instead, we could train the model using record osets. By setting epsilon accordingly, the model would still determine the correct base page for a key.
Non-Integer Keys. To handle string keys, we could follow a similar approach as prior work [58]: recursively build a radix tree of spline models with a node per 8-byte key prex, until the model satises a pre-determined maximum prediction error. A similar approach is taken by the Adaptive Radix Tree (ART) [37], recursing until two keys can be dierentiated, without storing the whole strings.
More Sophisticated Forecasts. To forecast inserts, we project the insert distribution of the previous epoch. This approach works well when distribution shifts happen smoothly, as is the case in the taxi dataset [55]. For more sophisticated insert distributions found in production workloads [10], we could use a timeseries forecasting module like Prophet [59]. We found Prophet ecient enough to perform the forecasting in the background, but its forecasts were comparable to those of our approach for the taxi dataset.
Pure Write Workloads. TreeLine currently cannot compete with RocksDB on pure write workloads. Even with perfect forecasting, inserts in TreeLine still suer from its update-in-place paradigm, while RocksDB can simply write out its memtable without a prior read. To match RocksDB on pure write workloads, we could use a hybrid approach that stages inserts during burst periods in a log-structured le which is gradually merged during idle periods.
LSM Trees. LevelDB [27] pioneered the partitioned leveling merge policy [43], in which each level (except L0) contains multiple rangepartitioned xed-size les to improve concurrency. Building on LevelDB, RocksDB [48] provides more compaction policies and a merge operation to reduce contention with user requests [43]. Wis-cKey [42] extends LevelDB by storing values in a separate values log. This design reduces write amplication by avoiding unnecessarily copying values during the merge. TreeLine, in contrast, only merges a page with its one overow page. It is hence unclear whether introducing key-value separation in TreeLine would yield benets, considering the added cost of garbage collection.
Modern LSM-trees use Bloom lters to reduce disk accesses. Dayan et al. [19] show how to best allocate bits to each lter to improve the space-accuracy trade o. SlimDB [57] and Chucky [21] instead use a multi-level Cuckoo lter, improving pruning power.
Update-in-Place Designs. We are not rst to revisit update-inplace designs for modern hardware. LeanStore [36] bridges the gap between in-memory and disk-based systems through a low overhead buer manager. While ecient when the working set ts into memory, it is not optimized for the out-of-memory case, which we target. FASTER [11,12] is another key-value store with in-place updates. Compared to TreeLine, FASTER is optimized for point accesses and does not support ecient range scans. KVell [39] is a key-value store with a similar design to ours. It uses an in-memory B+ tree to index the unsorted on-disk keys. Its drawbacks are that (i) it needs to index all keys (which can have a high memory overhead), and (ii) scans incur random I/O. In contrast, with page grouping, TreeLine only indexes segment boundaries (i.e., fewer index entries) and reads full segments sequentially when running range scans.
Learned Indexing. Learned indexes [34,35,44] build a model over sorted data to predict the position of a key. Abu-Libdeh et al. [1] integrate learned indexes into Bigtable [13] and show that the index's reduced size improves cache eciency [1]. Like Tree-Line's page grouping, FITing-Tree [25] also ts a piece-wise linear model over its data. However, FITing-Tree (i) is an in-memory data structure, and (ii) uses its error bound to bound lookup time. In contrast, TreeLine is a disk-based system and uses its error bound (epsilon) to control the "ll variation" among pages in a segment. Bourbon [18] extends WiscKey [42] by replacing the block index per SSTable with a faster, more compact learned index. The benets, however, are limited to this single granularity at which learned indexes are employed. The reorganization process in TreeLine instead maximizes the usefulness of each linear model, since it creates the largest possible segment per model, based on the data distribution.
Since both WiscKey and Bourbon are closed source, we cannot perform an apples-to-apples comparison. Bourbon achieves a 1.61⇥ speedup over WiscKey on the Amazon dataset for a 100% read workload [18]. Assuming Bourbon achieves a similar speedup when integrated into RocksDB, TreeLine's 2.4⇥ and 5⇥ speedup (64 B vs. 1024 B records) over RocksDB on that dataset would be competitive.
Instance Optimization. There have been limited proposals for instance-optimized storage systems. Idreos et al. [20,30] aim to instance-optimize (or automatically assemble) an entire storage system based on data and workload characteristics. Cosine [14] is a similar proposal targeted at the cloud. Unlike TreeLine, Cosine does not aim to improve update-in-place designs but rather assembles hybrid solutions from existing designs, including update-in-place.
We present TreeLine: a new update-in-place persistent key-value store for NVMe SSDs. TreeLine captures the read benets of a classical disk-based B+ tree and mitigates its drawbacks to be competitive against LSMs on write-heavy workloads. TreeLine uses three complementary techniques: (A) record caching to reduce read/write amplication in skewed workloads, (B) page grouping to execute scans as sequential reads, and (C) insert forecasting to reduce the I/O cost of "making space" for new records. We evaluate TreeLine on YCSB using synthetic and real world datasets. On YCSB, TreeLine outperforms RocksDB and LeanStore by 2.20⇥ and 2.07⇥ respectively on average across the point workloads, and by up to 10.95⇥ and 7.52⇥ overall. We have open-sourced TreeLine [60].