# Nova-LSM: A Distributed, Component-based LSM-tree Key-value Store

Extended Version

Haoyu Huang  University of Southern CaliforniaLos AngelesUSA<EMAIL_ADDRESS>and  Shahram Ghandeharizadeh  University of Southern CaliforniaLos AngelesUSA
<EMAIL_ADDRESS>
###### Abstract.

The cloud infrastructure motivates disaggregation of monolithic data stores
into components that are assembled together based on an application’s
workload. This study investigates disaggregation of an LSM-tree key-value
store into components that communicate using RDMA. These components separate
storage from processing, enabling processing components to share storage
bandwidth and space. The processing components scatter blocks of a file
(SSTable) across an arbitrary number of storage components and balance load
across them using power-of-d. They construct ranges dynamically at runtime to
parallelize compaction and enhance performance. Each component has
configuration knobs that control its scalability. The resulting component-
based system, Nova-LSM, is elastic. It outperforms its monolithic
counterparts, both LevelDB and RocksDB, by several orders of magnitude with
workloads that exhibit a skewed pattern of access to data.

##  1\. Introduction

Persistent multi-node key-value stores (KVSs) are used widely by diverse
applications. This is due to their simplicity, high performance, and
scalability. Example applications include online analytics (Airbnb, 2016;
Yahoo!, 2015), product search and recommendation (Li et al., 2017), graph
storage (Sharma, 2020; Prabhu, 2014; Matsunobu et al., 2020), hybrid
transactional and analytical processing systems (Yang et al., 2020), and
finance (Dong et al., 2017). For write-intensive workloads, many KVSs
implement principles of the Log-Structured Merge-tree (LSM-tree) (Ghemawat and
Dean, 2020; Dong et al., 2017; Chang et al., 2008; Lakshman and Malik, 2010;
contributors, 2020). They do not perform updates in place and use in-memory
memtables to buffer writes and flush them as Sorted String Tables (SSTables)
using sequential disk I/Os.

To improve resource utilization, cloud-native data stores leverage the cloud
infrastructure with hardware-software co-design to enable elasticity
(Verbitski et al., 2017; Antonopoulos et al., 2019; Depoutovitch et al.,
2020). This motivates disaggregation of monolithic data stores into components
(Ghandeharizadeh et al., 2019b; DeWitt et al., 1990; Haung, 2020). Logically,
components may separate storage from processing. Physically, a component
utilizes the appropriate hardware and scales independent of the others. Fast
networking hardware with high bandwidths, e.g., Remote Direct Memory Access
(RDMA) (Microsoft, 2020), provides connectivity for data exchange between
components that constitute a data store.

We present Nova-LSM, a distributed, component-based LSM-tree data store. Its
components include LSM-tree Component (LTC), Logging Component (LogC), and
Storage Component (StoC). Both LTC and LogC use StoC to store data. LogC uses
StoC to enhance either availability or durability of writes. Nova-LSM enables
each component to scale independent of the others. With an I/O intensive
workload, a deployment may include a few LTCs and LogCs running on compute-
optimized servers with hundreds of StoCs running on storage-optimized servers;
see (Services, 2020; Microsoft, 2020; Shan et al., 2018) for such servers.

An application range partitions data across LTCs. Physically, an LTC may
organize memtables and SSTables of a range in different ways: assign a range
and its SSTables to one StoC, assign SSTables of a range to different StoCs
with one SSTable assigned to one StoC, or assign SSTables of a range to
different StoCs and scatter blocks of each SSTable across multiple StoCs. An
LTC may use either replication, a parity-based technique or a hybrid of the
two to enhance availability of data in the presence of StoC failures.

A LogC may be a standalone component or a library integrated with an LTC. It
may be configured to support availability, durability, or both. Availability
is implemented by replicating log records in memory, providing the fastest
service times. Durability is implemented by persisting log records at StoCs.

A StoC is a simple component that stores, retrieves, and manages variable-
sized blocks. Its speed depends on the choice of storage devices and whether
they are organized in a hierarchy. An example hierarchy may consist of SSD and
disk, using a write-back policy to write data from SSD to disk asynchronously
(Holland et al., 2013; Xu et al., 2016; Srinivasan and Saab, 2020).

Nova-LSM uses RDMA to enable LTCs to share disk bandwidth of StoCs. Figure 1
shows the performance benefits of this architecture when compared with the
classical shared-nothing architecture (Stonebraker, 1986; DeWitt et al.,
1990). It presents throughput of 3 different YCSB (Cooper et al., 2010)
workloads with (1) a uniform access pattern to data and (2) after a sudden
change to a skewed pattern of access to data. These are labeled Uniform and
Zipfian on the x-axis, respectively. We show throughput of two configurations
of Nova-LSM using the same hardware platform consisting of 10 nodes. The one
labeled shared-disk uses RDMA to enable LTCs to share disk bandwidth and space
of all ten StoCs. With the shared-nothing, an LTC stores its SSTables on the
StoC local to its node. The number on each bar is the factor of improvement in
throughput with the shared-disk when compared with the shared-nothing.

With Zipfian, the shared-disk improves performance by a factor of 9 or higher.
The shared-nothing directs most of the requests to the StoC with the most
popular data item, exhausting its disk bandwidth while nine StoCs wait for
work with a disk bandwidth utilization lower than 20%. By requiring LTCs to
share StoCs, Nova-LSM distributes the imposed load more evenly across all 10
disks, improving system throughput dramatically with Zipfian.

Figure 1. Performance comparison between shared-nothing and shared-disk with a
1 TB database range partitioned across 10 servers.

###  1.1. Challenges and Solutions

Challenge 1: A challenge of LSM-tree implementations including LevelDB
(Ghemawat and Dean, 2020), RocksDB (Dong et al., 2017; Matsunobu et al.,
2020), and AsterixDB (Alsubaiee et al., 2014) is write stalls (Luo and Carey,
2019; Sears and Ramakrishnan, 2012; Balmau et al., 2019; Yao et al., 2020). It
refers to moments in time when the system suspends processing of writes
because either all memtables are full or the size of SSTables at Level0
exceeds a threshold. In the first case, writes are resumed once an immutable
memtable is flushed to disk. In the second, writes are resumed once compaction
of SSTables at Level0 into Level1 causes the size of Level0 SSTables to be
lower than its pre-specified threshold.

Solution 1: Nova-LSM addresses this challenge using both its architecture that
separates storage from processing and a divide-and-conquer approach. Consider
each in turn.

With Nova-LSM’s architecture, one may either increase the amount of memory
allocated to an LTC, the number of StoCs to increase the disk bandwidth, or
both. Figure 2 shows the throughput observed by an application for a one-hour
experiment with different Nova-LSM configurations. The base system consists of
one LTC with 32 MB of memory and 1 StoC, see Figure 2.i. As a function of
time, its throughput spikes and drops down to zero due to write stalls,
providing an average throughput of 9,000 writes per second. The log-scale for
the y-axis highlights the significant throughput variation since writes must
wait for memtables to be flushed to disk. Increasing the number of StoCs to 10
does not provide a benefit (see Figure 2.ii) because the number of memtables
is too few. However, increasing the number of memtables to 128 enhances the
peak throughput from ten thousand writes per second to several hundred
thousand writes per second, see Figure 2.iii. It improves the average
throughput 5 folds to 50,000 writes per second and utilizes the disk bandwidth
of 1 StoC fully. Write stalls continue to cause the throughput to drop to
close to zero for a noticeable amount of time, resulting in a sparse chart.
Finally, increasing the number of StoCs of this configuration to 10 diminishes
write stalls significantly, see Figure 2.iv. The throughput of this final
configuration is 27 folds higher than the throughput of the base configuration
of Figure 2.i.

Figure 2. Throughput of different Nova-LSM configurations.

Nova-LSM reduces complexity of software to implement compaction using a divide
and conquer approach by constructing dynamic ranges, Dranges. These Dranges
are independent of the application specified ranges. An LTC creates them with
the objective to balance the load imposed by application writes across them.
This enables parallel compactions to proceed independent of one another,
utilizing resources that would otherwise sit idle. (Section 4.1)

Challenge 2: Increasing the number of memtables (i.e., amount of memory) slows
down scans and gets by requiring them to search a larger number of memtables
and SSTables at Level0.

Solution 2: Nova-LSM implements an index that identifies either the memtable
or the SSTable at Level0 that stores the latest value of a key. If a get
observes a hit in the lookup index, it searches either one memtable or one
SSTable at Level0. Otherwise, it searches SSTables at higher levels that
overlap with the referenced key. This index improves the throughput by a
factor of 1.7 (2.8) with a uniform (skewed) pattern of access to data.
(Section 4.1.1)

Dranges (see Solution 1) partition the keyspace to enable an LTC to process a
scan by searching a subset of memtables and SSTables. This improves the
throughput 26 (18) folds with a uniform (skewed) pattern of access to data.
(Section 4.1.2)

Challenge 3: When LTCs assign SSTables to StoCs randomly, temporary
bottlenecks may form due to random collision of many writes to a few,
potentially one, StoC. This slows down requests due to queuing delays.

Solution 3: Nova-LSM addresses this challenge in two ways. First, it scatters
blocks of a SSTable across multiple StoCs. Second, it uses power-of-d
(Mitzenmacher, 2001) to assign writes to StoCs. Consider each in turn. An LTC
may partition a SSTable into $\rho$ fragments and use RDMA to write these
fragments to $\rho$ StoCs. When the value of $\rho$ equals the total number of
StoCs, $\beta$, the possibility of random collisions is eliminated altogether.
For example with $\beta$=10 StoCs, the throughput doubles when an LTC scatters
a SSTable across $\rho$=10 StoCs instead of one StoC.

Full partitioning is undesirable with large values of $\beta$. It wastes disk
bandwidth by increasing the overall number of disk seeks and rotational
latencies to write a SSTable. Hence, Nova-LSM supports partitioning degrees
lower than the number of StoCs, $\rho<\beta$. (Section 4.4)

With $\rho<\beta$, each LTC implements power-of-d to write a SSTable as
follows. It peeks at the disk queue sizes of $\rho*2$ randomly selected StoCs,
writing to those $\rho$ StoCs with the shortest disk queues. Experimental
results of Figure 1 use $\rho$=3 with $\beta$=10. Note that power-of-d enables
the write-only workload W100 with a uniform access pattern to observe a 60%
improvement. It minimizes the impact of transient bottlenecks attributed to
random independent requests colliding on one StoC.

###  1.2. Contributions and Outline

The primary contributions of this study are as follows.

  * •

An LTC constructs dynamic ranges to enable parallel compactions for SSTables
at Level0, utilizing resources that would otherwise sit idle and minimizing
the duration of write stalls. (Section 4)

  * •

An LTC maintains indexes to provide fast lookups and scans. (Section 4)

  * •

An LTC scatters blocks of one SSTable across a subset of StoCs (e.g., 3 out of
$\beta>3$) while scattering blocks of different SSTables across all $\beta$
StoCs. It uses the power-of-d random choices (Mitzenmacher, 2001) to minimize
queuing delays at StoCs. An LTC implements replication and a parity-based
technique to enhance data availability in the presence of StoC failures.
(Section 3.1 and 4)

  * •

A LogC separates the availability of log records from their durability. LogC
configured with availability using RDMA recovers 4 GB of log records within
one second. (Section 5)

  * •

A StoC implements simple interfaces that allow it to scale horizontally.
(Section 6)

  * •

A highly elastic Nova-LSM. (Section 9)

  * •

A publicly available implementation of Nova-LSM as an extension of
LevelDB111https://github.com/HaoyuHuang/NovaLSM. Nova-LSM shows a 2.3x to 18x
higher throughput than LevelDB and RocksDB with a skewed access pattern and a
2 TB database. Nova-LSM scales vertically as a function of memory sizes. It
also scales horizontally as a function of LTCs and StoCs. (Section 8)

  * •

The main limitation of Nova-LSM is its higher CPU utilization. With 1 LTC and
1 StoC running on 1 server, this is attributed to the overhead of maintaining
the index that addresses Challenge 2. With additional LTCs, this overhead
extends to include pulling of messages by the RDMA threads. Total overhead
results in a 20-30% performance degradation with a CPU intensive workload (50%
scan, 50% write) using a uniform pattern of access to data. With the same
workload and a skewed access pattern, Nova-LSM outperforms LevelDB by a factor
of 5. (Figure 18(b) of Section 8.3.2)

The rest of this paper is organized as follows. Section 2 presents the
background on LevelDB and RDMA. We then present the architecture of Nova-LSM
and its component interfaces in Section 3. Sections 4 to 6 detail the design
of LTC, LogC, and StoC, respectively. Section 7 details the implementation of
Nova-LSM. We present our evaluation results in Section 8. Section 9 presents
the elasticity of Nova-LSM. Section 10 surveys related work. Section 11
concludes and discusses future research directions.

##  2\. Background

###  2.1. LevelDB

LevelDB organizes key-value pairs in two memtables and many immutable Sorted
String Tables (SSTables). While the memtables are main memory resident,
SSTables reside on disk. Keys are sorted inside a memtable and a SSTable based
on the application specified comparison operator. LevelDB organizes SSTables
on multiple levels. Level0 is semi-sorted while the other levels are sorted.
The expected size of each level is limited and is usually increasing by a
factor of 10. This bounds the storage size. When a memtable becomes full, it
is converted to a SSTable at Level0 and written to disk. Other data stores
built using LevelDB support a configurable number of memtables, e.g., RocksDB
(Dong et al., 2017).

With large memory, it is beneficial to have many small memtables instead of a
few large ones. LevelDB implements a memtable using skiplists, providing O(log
n) for both lookups and inserts where n is the number of keys in the memtable.
A larger memtable size increases the number of keys and slows down lookups and
inserts (Balmau et al., 2017b). Typically, an application configures the
memtable size to be a few MB, e.g., 16 MB.

Write: A write request is either a put or a delete. LevelDB maintains a
monotonically increasing sequence number to denote the version of a key. A
write increments the sequence number and appends the key-value pair associated
with the latest value of the sequence number to the active memtable. Thus, the
value of a key is more up-to-date if it has a greater sequence number. When a
write is a delete, the value of the key is a tombstone. When the active
memtable is full, LevelDB marks it as immutable and creates a new active
memtable to process writes. A background compaction thread converts the
immutable memtable to a SSTable at Level0 and flushes it to disk.

Logging: LevelDB associates a memtable with a log file to implement durability
of writes. A write appends a log record to the log file prior to writing to
the active memtable. When a compaction flushes the memtable to disk, it
deletes the log file. In the presence of a failure, during recovery, LevelDB
uses the log files to recover its corresponding memtables.

Get: A get for a key searches memtables first, then SSTables at Level0,
followed by SSTables at higher levels for a value. It terminates once the
value is found. It may search all SSTables at Level0 if each spans the entire
keyspace. This is undesirable especially when we have a large number of
memtables. For SSTables at Level1 and higher, it often searches only one
SSTable since all keys are sorted. Bloom filters may be used to detect when
this search may not be necessary.

Compaction: LevelDB uses leveled compaction (Luo and Carey, 2020b) to reduce
its disk space usage to remove older versions of key-value pairs in the
background. It compacts SSTables at Leveli with the highest ratio of actual
size to expected size. It picks a subset of SSTables at Leveli and computes
their overlapping SSTables at Leveli+1. Then, it reads these SSTables into
memory and compacts them into a new set of SSTables to Leveli+1. This ensures
keys are still sorted at Leveli+1 after compaction. LevelDB deletes the
compacted SSTables to free disk space. With a large number of SSTables at
Level0, the compaction may require a long time to complete. This is the write
stall described in Section 1.1.

###  2.2. RDMA

Similar to the Ethernet-based IP Networks, RDMA consists of a switch and a
network interface card (RNIC) that plugs into a server. It provides bandwidths
in the order of tens and hundreds of Gbps with latencies in the order of a few
microseconds (Huang and Ghandeharizadeh, 2019). The ones used in this study
provide a bandwidth of 56 Gbps, see (Duplyakin et al., 2019) for their
detailed specifications. RDMA is novel because it provides one-sided RDMA
READ/WRITE verbs that read (write) data from (to) a remote server while
bypassing its CPU.

Two servers are connected using a pair of queues (QP): QPi on server $i$ and
QPj on server $j$. Its communication is asynchronous. A QP may be reliable
connected, unreliable connected, or unreliable datagram. We focus on reliable
connected QPs since the other types may drop packets silently. A QP supports
three communication verbs: RDMA SEND, RDMA READ, and RDMA WRITE. RDMA READ and
WRITE bypass the receiver’s CPU. An RDMA READ reads a remote memory region
into its local memory region. An RDMA WRITE writes a local memory region to a
remote memory region directly. QPi may issue a request to QPj using RDMA SEND.
QPj notifies server $j$ once it receives the request. It also generates an
acknowledgment to QPi. QPi may tag a request with a 4-byte immediate data. In
this case, QPj notifies server $j$ of the immediate data when it receives an
RDMA SEND or RDMA WRITE request.

Table 1. Notations and their definitions. Notation | Definition
---|---
$\eta$ | Total number of LTCs.
$\beta$ | Total number of StoCs.
$\omega$ | Number of ranges per LTC.
$\theta$ | Number of Dranges per range.
$\gamma$ | Number of Tranges per Drange.
$\alpha$ | Number of active memtables per range.
$\delta$ | Number of memtables per range.
$\tau$ | Size of memtable/SSTable in MB.
$\rho$ | Number of StoCs to scatter a SSTable.

##  3\. Nova-LSM Components

Figure 3 shows the architecture of Nova-LSM, consisting of LSM-tree components
(LTCs), logging components (LogCs), and storage components (StoCs). This
architecture separates storage from processing similar to systems such as
Aurora (Verbitski et al., 2017), Socrates (Antonopoulos et al., 2019), SolarDB
(Zhu et al., 2019), Tell (Loesing et al., 2015), and RockSet (Pham, 2020).
Table 1 provides the definition of notations used in this paper.

An LTC consists of $\omega$ ranges. The LTC constructs a LSM-tree for each
range. It processes an application’s requests using these trees. A LogC is a
library integrated into an LTC and is responsible for generating log records
to StoCs during normal mode of operation and fetching log records during
recovery mode. A StoC stores, retrieves, and manages variable-sized blocks
using alternative storage mediums, e.g., main memory, disk, SSD, or a storage
hierarchy. These components are interconnected using RDMA.

One may partition a database into an arbitrary number of ranges and assign
these ranges to $\eta$ LTCs. In its simplest form, one may partition a
database across $\omega*\eta$ ranges and assign $\omega$ ranges to each LTC.
The coordinator maintains a configuration that contains the partitioning
information and the assignment of ranges to $\eta$ LTCs. Nova-LSM clients use
this configuration information (Ghandeharizadeh et al., 2019a; Ghandeharizadeh
and Huang, 2018) to direct a request to an LTC with relevant data.

Figure 3. Architecture. Figure 4. Component Interfaces.

Figure 3 shows an IP network for Nova-LSM clients to communicate with LTCs and
the coordinator. This network may be RDMA when the application nodes are in
the same data center as the LTCs and the coordinator (Fent et al., 2020).

Nova-LSM uses mechanisms similar to the Google File System (Ghemawat et al.,
2003) to handle failures. The coordinator of Figure 3 maintains a list of
StoCs, LTCs, and ranges assigned to LTCs. We use leases to minimize management
overhead at the coordinator. A lease has an adjustable initial timeout. The
coordinator grants a lease on a range to an LTC to process requests
referencing key-value pairs contained in that range. Similarly, the
coordinator grants a lease to a StoC to process requests. Both StoC and LTC
may request and receive lease extensions from the coordinator indefinitely.
These extension requests and grants are piggybacked on the heartbeat messages
regularly exchanged between the coordinator and StoCs/LTCs. If the coordinator
loses communication with an LTC, it may safely grant a new lease on the LTC’s
assigned ranges to another LTC after the old lease expires. A StoC/LTC that
fails to renew its lease by communicating with the coordinator stops
processing requests. One may use Zookeeper to realize a highly available
coordinator (Hunt et al., 2010).

While SSTables are immutable, compactions mutate manifest files containing
metadata about levels and their assigned SSTables. Replicas of a manifest file
may become stale if a StoC fails and misses these mutations while it is
unavailable. For each manifest file, Nova-LSM maintains a version number to
distinguish between up-to-date and stale manifest replicas (Ghandeharizadeh et
al., 2019a; Ghandeharizadeh and Huang, 2018). If a StoC is unavailable then
the version numbers of its manifest replicas are not advanced. When the StoC
restarts, it reports its set of manifest replicas and their version numbers to
the coordinator. The coordinator detects the stale manifest replicas and
deletes them.

Figure 5. Thread Model.

###  3.1. Component Interfaces

LTC provides the standard interfaces of an LSM-tree as shown in Figure 4. For
high availability, one may configure LTC to either replicate a SSTable across
StoCs, use a parity-based technique (Patterson et al., 1988), or a combination
of the two. With parity, a SSTable contains a parity block computed using the
$\rho$ data block fragments. Once a StoC fails and an LTC references a data
fragment on this StoC, the LTC reads the parity block and the other $\rho-1$
data block fragments to recover the missing fragment. It may write this
fragment to a different StoC for use by future references.

LogC provides interfaces for append-only log files. It implements these
interfaces using StoCs. For high availability, a LogC client may open a log
file with in-memory storage and 3 replicas.

StoC provides variable-sized block interfaces for append-only files. A StoC
file is identified by a globally unique file id. When a StoC client opens a
file, StoC allocates a buffer in its memory and returns a file handle to the
client. The file handle contains the file id, memory buffer offset, and its
size. A StoC client appends a block by writing to the memory buffer of the
StoC file directly using RDMA WRITE. When a StoC client, say an LTC, reads a
block, it first allocates a buffer in its local memory. Next, it instructs the
StoC to write the block to its buffer using RDMA WRITE. Sections 4 to 6 detail
the design of these interfaces.

###  3.2. Thread Model

Recent studies have shown that RDMA scales poorly with a high number of QPs
(Huang and Ghandeharizadeh, 2019; Kalia et al., 2016). Thus, we configure each
node with a number of dedicated exchange (xchg) threads to minimize the number
of QPs. An xchg thread $k$ at node $i$ maintains a QP that connects to the
xchg thread $k$ at each of the other nodes. Its sole responsibility is to
issue requests from its caller to another node and transmit the received
responses back to its caller. It delegates all actual work to other threads.

LTC has four types of threads, see Figure 5. A client worker thread processes
client requests. A compaction thread flushes immutable memtables to StoCs and
coordinates compaction of SSTables at StoCs. An xchg thread facilitates
issuing requests to other StoCs and receiving their replies. A reorganization
(reorg) thread to balance load across dynamic ranges, Dranges.

Figure 6. LTC constructs $\theta$ Dranges per range.

StoC has three types of threads. A compaction thread compacts SSTables
identified by an LTC and may write them to its local disk. A storage thread
reads and writes blocks from the local disk in response to an LTC request. An
xchg thread facilitates communication between these threads running on one
StoC and those on other LTCs and StoCs. (StoCs communicate to perform
compaction, see Section 4.3.)

The xchg thread continuously pulls on its QP for requests. It backs-off
exponentially when there is no request. This exponential back-off may be
configured to strike a compromise between delays and the amount of utilized
CPU.

##  4\. LSM-tree Component

For each range, an LTC maintains an LSM-tree, multiple active memtables,
immutable memtables, and SSTables at different levels. Nova-LSM further
constructs $\theta$ dynamic ranges (Drange) per range, see Figure 6. Dranges
are transparent to an application.

Each range maintains three invariants. First, key-value pairs in a memtable or
a SSTable are sorted by key. Second, keys are sorted across SSTables at Level1
and higher. Third, key-value pairs are more up-to-date at lower levels, i.e.,
Level0 has more up-to-date value of a key than Leveli where i ¿ 0.

###  4.1. Dynamic Ranges, Dranges

LTC uses a large number of memtables to saturate the bandwidth of StoCs. This
raises several challenges. First, compacting SSTables at Level0 into Level1
becomes prohibitively long due to their large number as these Level0 SSTables
usually span the entire keyspace and must be compacted together. Second, reads
become more expensive since they need to search possibly all memtables and
SSTables at Level0. A skewed access pattern exacerbates these two challenges
with a single key that is updated frequently. Different versions of this key
may be scattered across all SSTables at Level0.

To address these challenges, an LTC constructs Dranges with the objective to
balance the load of writes across them evenly. It assigns the same number of
memtables to each Drange. A write appends its key-value pair to the active
memtable of the Drange that contains its key, preventing different versions of
a single key from spanning all memtables. SSTables at Level0 written by
different Dranges are mutually exclusive. Thus, they may be compacted in
parallel and independently.

An LTC monitors the write load of its $\theta$ Dranges. It performs either a
major or a minor reorganization to distribute its write load evenly across
them. Minor reorganizations are realized by constructing tiny ranges, Tranges,
that are shuffled across Dranges. Major reorganizations construct Dranges and
Tranges based on the overall frequency distribution of writes.

A Drange is duplicated when it is a point and contains a very popular key. For
example, Figure 6 shows [0,0] is duplicated for two Dranges, 0 and 1, because
its percentage of writes is twice the average. This assigns twice as many
memtables to Drange [0,0]. A write for key 0 may append to the active memtable
of either duplicate Drange. This reduces contention for synchronization
primitives that implement thread-safe writes to memtables. Moreover, the
duplicated Dranges minimize the number of writes to StoC once a memtable is
full as detailed in Section 4.2. Below, we formalize Tranges, Dranges, minor
and major reorganization.

###### Definition 4.0.

A tiny dynamic range (Trange) is represented as [$TL_{j}$, $TU_{j}$). A Trange
maintains a counter on the total number of writes that reference a key $K$
where $K<TU_{j}$ and $K\geq TL_{j}$.

###### Definition 4.0.

A dynamic range (Drange) is represented as [$DL_{i}$, $DU_{i}$). A Drange
contains a maximum of $\gamma$ Tranges where $DL_{i}=TL_{i,0}$,
$DU_{i}=TU_{i,\gamma-1}$, and $\forall j\in[1,\gamma),TL_{i,j}=TU_{i,j-1}$. A
Drange contains one active memtable and $\frac{\delta}{\theta}-1$ immutable
memtables. Each Drange processes a similar rate of writes.

###### Definition 4.0.

A minor reorganization assigns Tranges of a hot Drange to its neighbors to
balance load.

###### Definition 4.0.

A major reorganization uses historical sampled data to reconstruct Tranges and
their assigned Dranges.

An LTC triggers a minor reorganization when a Drange receives a higher load
than the average by a pre-specified threshold $\epsilon$, i.e., load ¿
$\frac{1}{\theta}+\epsilon$. With a significant load imbalance where assigning
Tranges to different Dranges does not balance the load, an LTC performs a
major reorganization. It estimates the frequency distribution of the entire
range by sampling writes from all memtables. Next, it constructs new Dranges
and Tranges with the write load divided across them almost evenly.

An LTC may update the boundaries of a Drangei from $[DL_{i},DU_{i})$ to
$[DL^{\prime}_{i},DU^{\prime}_{i})$ in different ways. We consider two
possibilities. With the first, these key-value pairs may be left behind in
memtables of Drangei. This technique requires a get to search all memtables
and overlapping SSTables at all levels since a higher level SSTable may
contain the latest value of a key. To elaborate, an older value of a key may
reside in a memtable of Drangei while its latest value in a memtable of
Drangej is flushed as a SSTable to Level0. Subsequently, this SSTable may be
compacted into higher levels earlier than the flushing of the memtable
containing its older value (and belonging to Drangei).

With the second, Nova-LSM associates a generation id with each memtable. This
generation id is incremented after each reorganization. A reorganization marks
the impacted active memtables as immutable, increments the generation id, and
creates a new active memtable with the new generation id. When writing an
immutable memtable as a SSTable, Nova-LSM ensures the memtables with older
generation ids are flushed first. This allows a get to return immediately when
it finds the value of its referenced key in a level.

One may come up with the best and worst case scenario for each of these
techniques. The worst case scenario for the first technique is when a get
references a key inserted least recently and appears in all levels. In our
experiment, we observed at most 40% improvement with the second technique when
gets are issued one at a time to the system. This improvement became
insignificant with concurrent gets.

####  4.1.1. Get

Each LTC maintains a lookup index to identify the memtable or the SSTable at
Level0 that contains the latest value of a key. If a get finds its referenced
key in the lookup index then it searches the identified memtable/SSTable for
its value and returns it immediately. Otherwise, it searches overlapping
SSTables at higher levels for the latest value and returns it. Each SSTable
contains a bloom filter and LTC caches them in its memory. A get skips a
SSTable if the referenced key does not exist in its bloom filter. In addition,
a get may search SSTables at higher levels in parallel.

Size of the lookup index is a function of the number of unique keys in
memtables and SSTables at Level0, $\ell_{0}$. It is $\ell_{0}$*(the average
key size + 4 bytes for memtable pointer + 8 bytes for Level0 SSTable file
number). 240 MB in experiments of Section 8.

The lookup index prevents a get from searching all memtables and SSTables at
Level0. Its details are as follows. A write that appends to a memtable $m$
updates the lookup index of the referenced key with $m$’s unique id $mid$. An
LTC maintains an indirect mapping MIDToTable from $mid$ to either a pointer to
a memtable or the file number of a SSTable at Level0. When a compaction thread
converts an immutable memtable to a SSTable and flushes it to StoC, it
atomically updates the entry of $mid$ in MIDToTable to store the file number
of the SSTable and marks the pointer to the memtable as invalid.

Once a SSTable at Level0 is compacted into Level1, its keys are enumerated.
For each key, if its entry in MIDToTable identifies the SSTable at Level0
then, the key is removed from the lookup index.

####  4.1.2. Scan

An LTC maintains a range index to process a scan using only those memtables
and Level0 SSTables with a range overlapping the scan. A scan must also search
overlapping SSTables at higher levels since they may contain the latest values
of the referenced keys.

Each element of the range index (a partition) corresponds to an interval,
e.g., [0, 100) in Figure 7. It maintains a list of memtables and SSTables at
Level0 that contain keys within this range. These are in the form of pointers.
Size of required memory is the number of Dranges * (size of start interval key
+ size of end interval key + pointers to memtables and Level0 SSTable file
numbers). 6 KB in experiments of Section 8.

Figure 7. Lookup index and range index. Figure 8. Dranges partition the
keyspace for compaction. Figure 9. LTC scatters a SSTable across multiple
StoCs.

A scan starts with a binary search of the range index to locate the partition
that contains its start key. It then searches all memtables and SSTables at
Level0 in this partition. It also searches SSTables at higher levels. When it
reaches the upper bound of the current range index partition, it seeks to the
first key in the memtables/SSTables of the next range index partition and
continues the search.

The range index is updated in three cases. First, when a new active memtable
for a Drange or a new Level0 SSTable is created, LTC appends it to all
partitions of the index that overlap the range of this memtable/SSTable.
Second, a compaction thread removes flushed immutable memtables and deleted
Level0 SSTables from the range index. Third, a Drange reorganization makes the
range index more fine-grained by splitting its partitions. When a partition
splits into two partitions, the new partitions inherit the memtables/SSTables
from the original partition.

###  4.2. Flushing Immutable Memtables

Once a write exhausts the available space of a memtable, the processing LTC
marks the memtable as immutable and assigns it to a compaction thread. This
thread compacts the memtable by retaining only the latest value of a key and
discarding its older values. If its number of unique keys is larger than a
prespecified threshold, say 100, the compaction thread converts the immutable
memtable into a SSTable and flushes it to StoC. Otherwise, it constructs a new
memtable with the few unique keys, invokes LogC to create a new log file for
the new memtable and a log record for each of its unique keys, and returns the
new memtable as an immutable table to the Drange. When a Drange consists of
multiple immutable memtables whose number of unique keys is lower than the
prespecified threshold, the compaction thread combines them into one new
memtable. Otherwise, it converts each immutable memtable to a SSTable and
writes the SSTable to StoC. With a skewed pattern of writes, this techniques
reduces the amount of data written to StoCs by 65%.

###  4.3. Parallel Compaction of SSTables at Level0

Dranges divide the compaction task at Level0 into $\theta$ smaller tasks that
may proceed concurrently, see Figure 8. This minimizes write stalls when the
total size of SSTables at Level0 exceeds a certain threshold. Without Dranges,
in the worst-case scenario, a Level0 SSTable may consist of keys that
constitute a range overlapping all ranges of SSTables at Levels 0 and 1.
Compacting this SSTable requires reading and writing a large volume of data
from many SSTables. This worst-case scenario is divided $\theta$ folds by
constructing $\theta$ non-overlapping Dranges. This enables $\theta$
concurrent compactions and utilizes resources that would otherwise sit idle.

LTC employs a coordinator thread for compaction. This thread first picks
Leveli with the highest ratio of actual size to expected size. It then
computes a set of compaction jobs. Each compaction job contains a set of
SSTables at Leveli and their overlapping SSTables at Leveli+1. SSTables in two
different compaction jobs are non-overlapping and may proceed concurrently.

Offloading: When StoCs have sufficient processing capability, the coordinator
thread offloads a compaction job to a StoC based on a policy. In this study we
assume round-robin. A short-term research direction is to investigate other
policies that minimize movement of data using RDMA. The StoC pre-fetches all
SSTables in the compaction job into its memory. It then starts merging these
SSTables into a new set of SSTables while respecting the boundaries of Dranges
and the maximum SSTable size, e.g., 16 MB. It may either write the new
SSTables locally or to other StoCs. When the compaction completes, the StoC
returns the list of StoC files containing the new SSTables to the coordinator
thread. The coordinator thread then deletes the original SSTables and updates
MANIFEST file described in Section 4.5.

###  4.4. SSTable Placement

An LTC may be configured to place a SSTable across $\rho$ StoCs with
$\rho\in[1,\beta]$ where $\beta$ is the number of StoCs. With $\rho=1$, a
SSTable is assigned to one StoC. With $\rho>1$, the blocks of a SSTable are
partitioned across $\rho$ StoCs. With large SSTables, partitioning reduces the
time to write a SSTable as it utilizes the disk bandwidth of multiple StoCs.

An LTC may adjust the value of $\rho$ for each SSTable using its size. For
example, Figure 9 shows SSTable 0:900-999 is scattered across 3 StoCs {0, 1,
i} while SSTable L-1:950-999 is scattered across 4 StoC {0, 1, i, $\beta$-1}.
The first SSTable is smaller due to a skewed access pattern that resulted in
fewer unique keys after compaction. Hence, it is partitioned across fewer
StoCs.

When LTC creates a SSTable, it first decides the value of $\rho$ and
identifies the $\rho$ StoCs based on a policy such as random and power-of-d
(Mitzenmacher, 2001). With random, an LTC selects $\rho$ StoCs from $\beta$
randomly. With power-of-d (Mitzenmacher, 2001), LTC selects $\rho$ StoCs with
the shortest disk queue out of $d$ randomly selected StoCs, d = $2\times\rho$.

An LTC partitions a SSTable into $\rho$ fragments and identifies a StoC for
each fragment. It writes all fragments to $\rho$ StoCs in parallel. Finally,
it converts its index block to StoC block handles and writes the metadata
blocks (index and bloom filter blocks) to a StoC.

####  4.4.1. Availability

Scattering a SSTable across multiple StoCs impacts its availability. If a
SSTable is scattered across all $\beta$ StoCs, it becomes unavailable once a
StoC fails. One may scatter a SSTable across fewer StoCs and use either
replication, a parity-based technique, or a hybrid of these technique to
provide data availability.

Nova-LSM implements Hybrid, a technique that combines parity-based and
replication technique as follows. It constructs a parity block for the data
fragments and replicates the metadata block due to its small size (in the
order of a few hundred KBs). This enables a read to fetch the metadata blocks
from any replica using power-of-d.

Fragments, their replicas, and parity blocks are assigned to different StoCs.
Their placements information are registered with the metadata block, see Step
5 of Figure 10.

Hybrid does not incur the overhead of RAID to update a block since SSTables
are immutable. Thus, the parity blocks are not read during normal mode of
operation. In failed mode, the redundant data is read to recover content of a
failed StoC.

We model the availability of data using the analytical models of (Patterson et
al., 1988). Assuming the Mean Time To Failure (MTTF) of a StoC is 4.3 months
and repair time is one 1 hour (Ford et al., 2010), Table 2 shows the MTTF of a
SSTable and the storage layer consisting of 10 StoCs. While MTTF of a SSTable
($MTTF_{SSTable}$) depends on the value of $\rho$, MTTF of the storage layer
($MTTF_{storage}$) is independent as we assume blocks of SSTables are
scattered across all StoCs. With no parity and no replication,
$MTTF_{storage}$ is only 13 days.

By constructing one replica for a SSTable and its fragments, $MTTF_{storage}$
is enhanced to 55.4 years and $MTTF_{SSTable}$ is improved to 554 years.
However, this technique has 100% space overhead.

A parity based technique has a lower space overhead than replication. Its
precise overhead depends on the value of $\rho$, see Table 2. Ideally, StoCs
should be deployed across different racks in a data center. This preserves
availability of data in the presence of rack failures.

Table 2. Impact of $\rho$ on MTTF of a SSTable/Storage layer.  $\rho$ | $MTTF_{SSTable}$ | $MTTF_{storage}$ | Space overhead
---|---|---|---
R=1 | Parity | R=1 | Parity | R=1 | Parity
1 | 4.3 Months | 554 Yrs | 13 Days | 54 Yrs | 0% | 100%
3 | 1.4 Months | 91 Yrs | 13 Days | 30 Yrs | 0% | 33%
5 | 26 Days | 36 Yrs | 13 Days | 18.5 Yrs | 0% | 20%

###  4.5. Crash Recovery

Nova-LSM is built on top of LevelDB and reuses its well-tested crash recovery
mechanism for SSTables and MANIFEST file. A MANIFEST file contains metadata of
an LSM-tree, e.g., SSTable file numbers and their levels. Each application’s
specified range has its own MANIFEST file and is persisted at a StoC. Nova-LSM
simply adds more metadata to the MANIFEST file. It extends the metadata of a
SSTable to include the list of StoC file ids that store its meta and data
blocks. It also appends the Dranges and Tranges to the MANIFEST file.

When an LTC fails, the coordinator assigns its ranges to other LTCs. With
$\eta$ LTCs, it may scatter its ranges across $\eta-1$ LTCs. This enables
recovery of the different ranges in parallel. An LTC rebuilds the LSM-tree of
a failed range using its MANIFEST file. Its LogC queries the StoCs for log
files and uses RDMA READ to fetch their log records. The LTC then rebuilds the
memtables using the log records, populating the lookup index. It rebuilds the
range index using recovered Dranges and the boundaries of the memtables and
Level0 SSTables.

##  5\. Logging Component

LogC constructs a log file for each memtable and generates a log record prior
to writing to the memtable. LogC approximates the size of a log file to be the
same as the memtable size. A log record is self-contained and is in the form
of (log record size, memtable id, key size, key, value size, value, sequence
number).

The log file may be either in memory (availability) or persistent
(durability). It may be configured to be persistent while its most recent log
records are maintained in memory. This reduces mean-time-to-recovery of an
LTC, enhancing availability while implementing durability. An in-memory log
file may be replicated to enhance its availability. If all in-memory replicas
fail, there is data loss. Next section describes our implementation of these
alternatives.

##  6\. Storage Component

A StoC implements in-memory and persistent StoC files for its clients, LTC and
LogC.

###  6.1. In-memory StoC Files

An in-memory StoC file consists of a set of contiguous memory regions. A StoC
client appends blocks to the last memory region using RDMA WRITE. When the
last memory region is full, it becomes immutable and the StoC creates a new
memory region. A StoC client uses RDMA READ to fetch blocks.

When a StoC client opens a file, the StoC first allocates a contiguous memory
region in its local memory and returns the StoC file handle to the client. The
file handle contains the StoC file id and the memory offset of the region. The
client caches the file handle.

A StoC client uses RDMA WRITE to append a block. It writes the block to the
current memory offset at the StoC and advances the offset by the size of the
block. If the block size is larger than the available memory, it requests a
new memory region from the StoC and resumes the append.

We configure the size of a memory region to be the same size as a memtable to
maximize performance. When LogC creates an in-memory StoC file for
availability, only open and delete involve the CPU of the StoC. Appending a
log record requires one RDMA WRITE. Fetching all of its log records requires
one RDMA READ. Both bypass StoC’s CPU.

###  6.2. Persistent StoC Files

A StoC maintains a file buffer shared across all persistent StoC files. When a
StoC client appends a block, it first writes the block to the file buffer
using RDMA WRITE. When a StoC client reads a block, the StoC fetches the block
into the file buffer and writes the block to the StoC client’s memory using
RDMA WRITE.

Figure 10. The workflow between one LTC and multiple StoCs to scatter blocks
of a SSTable.

Figure 10 shows the workflow of an LTC appending a data block fragment to a
StoC file. Its StoC client first sends a request to open a new StoC file 1.
The StoC allocates a memory region in its file buffer. The size of the memory
region is the same as the block size. It also creates a unique id for this
memory region and returns its memory offset to the client along with this
unique id. The client then writes the block to this memory region using RDMA
WRITE. It sets this unique id in the immediate data 2. The StoC is notified
once the RDMA WRITE completes. It then flushes the written block to disk 3 and
sends an acknowledgment to the client 4. Lastly, it writes the metadata blocks
to a StoC following the same procedure 5.

##  7\. Implementation

We implemented Nova-LSM by extending LevelDB with 20,000+ lines of C++ code
that implements components of Sections 3 to 6, an LTC client component, the
networking layer for an LTC to communicate with its clients, and management of
memory used for RDMA’s READ and WRITE verbs. With the latter, requests for
different sized memory allocate and free memory from a fixed preallocated
amount of memory. We use memcached’s slab allocator (memcached contributors,
2020) to manage this memory.

##  8\. Evaluation

This section evaluates the performance of Nova-LSM. We start by quantifying
the performance tradeoffs associated with different configuration settings of
Nova-LSM. Next, we compare Nova-LSM with LevelDB and RocksDB. Main lessons are
as follows:

  * •

When comparing performance of Nova-LSM with and without Dranges, Dranges
enhance throughput from a factor of 3 to 26. (Section 8.2.1)

  * •

With CPU intensive workloads, one may scale LTCs to enhance throughput. With
disk I/O intensive workloads, one may scale StoCs to enhance throughput.
(Sections 8.2.4 and 8.2.5)

  * •

With a skewed workload that requires many requests to reference ranges
assigned to a single LTC, one may re-assign ranges of the bottleneck LTC to
other LTCs to balance load. This enhances performance from 60% to more than 4
folds depending on the workload. (Section 8.2.6)

  * •

Nova-LSM outperforms both LevelDB and RocksDB by more than an order of
magnitude with all workloads that use a skewed pattern of access to data. It
provides comparable performance to LevelDB and RocksDB for most workloads with
a uniform access pattern.

  * •

Nova-LSM is inferior with CPU intensive workloads and a uniform access pattern
due to its higher CPU usage. With a single node, the CPU overhead is due to
maintaining the index. With more than one nodes, the CPU overhead also
includes xchg threads pulling for requests. (Section 8.3)

###  8.1. Experiment Setup

We conduct our evaluation on the CloudLab APT cluster of c6220 nodes
(Duplyakin et al., 2019). Each node has 64 GB of memory, two Xeon E5-2650v2
8-core CPUs, and one 1 TB hard disk. Hyperthreading results in a total of 32
virtual cores. All nodes are connected using Mellanox SX6036G Infiniband
switches. Each server is configured with one Mellanox FDR CX3 Single port mezz
card that provides a maximum bandwidth of 56 Gbps and a 10 Gbps Ethernet NIC.

Our evaluation uses the YCSB benchmark (Cooper et al., 2010) with different
sized databases: 10 GB (10 million records), 100 GB (100 million records), 1
TB (1 billion records), and 2 TB (2 billion records). Each record is 1 KB. We
focus on three workloads shown in Table 3. A get request references a single
key and fetches its 1 KB value. A write request puts a key-value pair of 1 KB.
A scan retrieves 10 records starting from a given key. If a scan spans two
ranges, we process it in a read committed (Berenson et al., 1995) manner with
puts. YCSB uses Zipfian distribution to model a skewed access pattern. We use
the default Zipfian constant 0.99, resulting in 85% of requests to reference
10% of keys. With Uniform distribution, a YCSB client references each key with
almost the same probability.

Table 3. Workloads. Workload | Actions
---|---
RW50 | 50% Read, 50% Write.
SW50 | 50% Scan, 50% Write.
W100 | 100% Write.

A total of 60 YCSB clients running on 12 servers, 5 YCSB clients per server,
generate a heavy system load. Each client uses 512 threads to issue requests.
A thread issues requests to LTCs using the 10 Gbps NIC. We use a high number
of worker/compaction threads to maximize throughput by utilizing resources
that would otherwise sit idle. An LTC has 512 worker threads to process client
requests and 128 threads for compaction. An LTC/StoC has 32 xchg threads for
processing requests from other LTCs and StoCs, 16 are dedicated for performing
compactions (Huang and Ghandeharizadeh, 2019; Kalia et al., 2016). A StoC is
configured with a total of 256 threads, 128 are dedicated for compactions.
Logging is disabled by default. When logging is enabled, LogC replicates a log
record 3 times across 3 different StoCs.

###  8.2. Nova-LSM and Its Configuration Settings

This section quantifies the performance tradeoffs associated with alternative
settings of Nova-LSM. We use a 10 GB database and one range per LTC,
$\omega=1$. Each server hosts either one LTC or one StoC. Section 8.2.1
evaluates Dranges. Section 8.2.3 evaluates the performance impact of logging.
One may scale each component of NOVA-LSM either vertically or horizontally.
Its configuration settings may scale (1) the amount of memory an LTC assigns
to a range, (2) the number of StoCs a SSTable is scattered across, (3) the
number of StoCs used by different SSTables of a range, and (4) the number of
LTCs used to process client requests. Items 1 is vertical scaling. The
remaining three scale either LTCs or StoCs horizontally. We discuss them in
turn in Section 8.2.4 and Section 8.2.5, respectively. Section 8.2.6 describes
migration of ranges across LTCs to balance load. We present results on the
recovery duration in Section 8.2.8.

####  8.2.1. Dynamic Ranges

Nova-LSM constructs Dranges dynamically at runtime based on the pattern of
access to the individual Dranges. Its objective is to balance the write load
across the Dranges. We quantify load imbalance as the standard deviation on
the percentage of puts processed by different Dranges. The ideal load
imbalance is 0. We report this number for both Uniform and Zipfian. The
reported numbers for Uniform serve as the desired value of load imbalance for
Zipfian.

With Uniform and $\theta=64$ Dranges, we observe a very small load imbalance,
2.86E-04$\pm$3.21E-05 (mean$\pm$standard deviation), across 5 runs. Nova-LSM
performs only one major reorganization and no minor reorganizations. With
Zipfian, the load imbalance is 1.65E-03$\pm$4.42E-04. This is less than 6
times worse than Uniform. Nova-LSM performs one major reorganization and
14.2$\pm$14.1 minor reorganizations. There are 11 duplicated Dranges. The
first Drange [0,0] is duplicated three times since key-0 is accessed the most
frequently. Similar results are observed as we vary the number of Dranges from
2 to 64. Duplication of Dranges containing one unique key is essential to
minimize load imbalance with Zipfian.

Dranges facilitate concurrent compactions. We compare Nova-LSM with Nova-LSM-R
and Nova-LSM-S, see Figure 11. Nova-LSM-R randomly selects an active memtable
to process a put request. Nova-LSM-S uses the active memtable of the
corresponding Drange to process a put request. Both do not prune memtables or
merge immutable memtables into a new memtable for Dranges with fewer than 100
unique keys.

With RW50 and W100, Nova-LSM provides 3x to 6x higher throughput when compared
with Nova-LSM-R as it compacts SSTables in parallel. With Nova-LSM-R, a
SSTable at Level0 spans the entire keyspace and overlaps with all other
SSTables at Level0 and Level-1. It must first split these sparse SSTables at
Level0 into dense SSTables and then compact them in parallel. The throughput
of Nova-LSM is comparable to Nova-LSM-S with Uniform. It is higher with
Zipfian because compaction threads write fewer data to StoCs. With Zipfian,
Nova-LSM constructs 11 Dranges that correspond to one unique key and a total
of 26 Dranges that contain less than 100 unique keys. With these Dranges,
Nova-LSM merges their memtables into a new memtable instead of flushing them
to StoCs, providing significant savings by avoiding disk reads and writes.

With SW50, Nova-LSM outperforms Nova-LSM-R by 26x with Uniform and 18x with
Zipfian. This is because keys are scattered across memtables and SSTables at
Level0 with Nova-LSM-R. With Uniform, a scan searches 64 memtables and 75
SSTables at Level0 on average while Nova-LSM searches only 1 memtable and 2
SSTables.

Figure 11. Throughput comparison of Nova-LSM and its variants with $\eta=1$,
$\beta=10$, $\rho=1$, $\alpha=64$, and $\delta=256$.

####  8.2.2. Impact of Skew

Figure 12 shows the throughput of Nova-LSM for different workloads as a
function of skewness. The access pattern becomes more skewed as we increase
the mean of the Zipfian distribution from 0.27 to 0.99. The number at top of
each bar is the factor of improvement relative to Uniform.

The throughput of both RW50 and W100 increases with a higher degree of skew.
It decreases with SW50. Consider each workload in turn. With RW50, Nova-LSM
processes get requests using memory instead of SSTables by maintaining the
most popular keys in the memtables. With W100, Nova-LSM compacts memtables of
Dranges with fewer than 100 unique keys into a new memtable without flushing
them to disk. The number of Dranges with fewer than 100 unique keys increases
with a higher degree of skew. Hence, the percentage of experiment time
attributed to write stalls decreases from 46% with Uniform to 16% with the
most skewed access pattern.

With SW50, the CPU is the limiting resource with all distributions including
Uniform. A higher skew generates more versions of a hot key. A scan must
iterate these versions to find the next unique key that may reside in a
different memtable or SSTable. This increases CPU load with a higher degree of
skew, decreasing the observed throughput.

Figure 12. Impact of Skew with $\eta=1$, $\beta=10$, $\rho=1$, $\alpha=64$,
and $\delta=256$.

####  8.2.3. Logging

When the CPU of LTC is not utilized fully, logging imposes a negligible
overhead on service time and throughput. We measure the service time of a put
request from when a client issues a put request until it receives a request
complete response. Replicating a log record three times using RDMA observes
only a 4% overhead compared to when logging is disabled (0.51 ms versus 0.49
ms). When replicating log records using NIC, the service time increases to
1.07 ms (2.1x higher than RDMA) since it involves the CPU of StoCs.

With replication only, logging uses CPU resources of LTCs and impacts
throughput when CPU of one or more LTCs is fully utilized. As shown in Figure
18, logging has negligible overhead with Uniform since the CPU is not fully
utilized. With Zipfian, it decreases the throughput by at most 33% as the CPU
utilization of the first LTC is higher than 90%. Logging has a negligible
impact on the CPU utilization of StoCs since LogC uses RDMA WRITE to replicate
log records bypassing CPUs of StoCs.

Table 4. Throughput of W100 Uniform as a function of the memory size with $\eta=1$, $\beta=10$, and $\rho=1$. Memory size | $\alpha$ | $\delta$ | Throughput (ops/s)
---|---|---|---
32 MB | 1 | 2 | 8,924
64 MB | 2 | 4 | 10,594
128 MB | 4 | 8 | 36,095
256 MB | 8 | 16 | 34,102
512 MB | 16 | 32 | 53,258
1 GB | 32 | 64 | 204,774
2 GB | 64 | 128 | 245,753
4 GB | 64 | 256 | 246,434

####  8.2.4. Vertical Scalability

One may vertically scale resources assigned to an LTC and/or a StoC either in
hardware or software. The amount of memory assigned to an LTC has a
significant impact on its performance. (Challenge 1 of Section 1 demonstrated
this by showing a 6 fold increase in throughput as we increased memory of an
LTC from 32 MB to 4 GB.) It is controlled using the following parameters:
number of ranges ($\omega$), number of memtables per range ($\delta$), number
of active memtables per range ($\alpha$), and memtable size ($\tau$). Since
$\omega$ ranges may be assigned to different LTCs, we focus on $\omega$=1
range and discuss the impact of $\delta$ and $\alpha$ on throughput of W100.
We set the maximum degree of parallelism for compaction to be $\alpha$.
Experiments of this section use a configuration consisting of 1 LTC with 10
StoCs. Each SSTable is assigned to 1 StoC ($\rho$=1). We use $\beta=10$ to
avoid the disk from becoming the bottleneck. With $\beta=1$, the disk limits
the performance and the LTC does not scale vertically as a function of
additional memory.

Our experiments start with a total of 2 memtables ($\delta$=2), requiring 32
MB of memory, Memory size = $\delta\times 16$ MB. 1 memtable is active
($\alpha$=1), We double memory size by increasing values for both $\alpha$ and
$\delta$ two-folds, see Table 4. With sufficient memory, the throughput scales
super-linearly. For example, increasing memory from 512 MB to 1 GB increases
the throughput almost 4 folds. This is because the duration of write stalls
reduces from 65% to 21% of experiment time. The throughput levels off beyond 2
GB as the bandwidth of StoCs becomes fully utilized.

####  8.2.5. Horizontal Scalability

Horizontal scalability of Nova-LSM is impacted by the number of LTCs, StoCs,
how a SSTable is scattered across StoCs and whether the system uses power-
of-d. Once the CPU of an LTC or disk bandwidth of a StoC becomes fully
utilized, it dictates the overall system performance and its scalability.
Below, we describe these factors in turn.

Scalability of StoCs: Figure 13 shows the throughput and horizontal
scalability of a system consisting of one LTC as we increase the number of
StoCs, $\beta$, from one to 10. LTC stores a SSTable in one StoC ($\rho=1$)
using power-of-2. The throughput scales as long as the CPU of the server
hosting the single LTC does not become a bottleneck. Once the CPU becomes
fully utilized, adding StoCs does not provide a performance benefit. With RW50
and SW50, this limit is reached with 5 StoCs. Hence, additional StoCs do not
provide a benefit. Amongst the different workloads, W100 scales the best. With
Zipfian, the CPU of the single LTC limits its scalability. With Uniform, the
write stalls due to the maximum Level0 size limits the throughput222The
throughput is 319K when the maximum Level0 size is 20 GB. It increases further
to 351K when the maximum Level0 size increases to 30 GB.. The write stall
duration decreases with more StoCs. However, it is not a linear function of
the number of StoCs. The percentage of experiment time spent on write stalls
decreases from 82% with one StoC to 60% with three and 46% with 10 StoCs. This
is because LTC schedules compactions across StoCs in a round-robin manner,
resulting in one or more StoCs to become fully utilized. We will consider
policies other than round-robin as future work.

(a) Throughput.

(b) Scalability.

Figure 13. Throughput and scalability as a function of $\beta$ with $\eta=1$, $\rho=1$, $\alpha=64$, and $\delta=256$.  Table 5. Throughput of W100 Uniform as a function of $\rho$ with $\eta=1$, $\beta=10$, $\alpha=1$, $\delta=2$. $\rho$ | Random |  Power-of-$d$
---|---|---
1 | 27,593 | 42,659
3 | 42,016 | 50,433
10 | 52,590 | 52,477

Power-of-d and degree of partitioning $\rho$: One may configure NOVA-LSM to
write a SSTable to a subset ($\rho$) of StoCs instead of all $\beta$ StoCs.
The value of $\rho$ has a significant impact on the performance of a
deployment. With a limited amount of memory (32 MB), using all 10 disks
($\rho$=10) provides a throughput that is almost twice higher than with one
disk ($\rho$=1), see Table 5 and the column labeled Random. This is because
when both memtables are full, a write must wait until one of the memtables is
flushed to StoC. The time to perform this write is longer when using one disk
compared with 10 disks, allowing $\rho$=10 to provide a significant
performance benefit.

Table 5 shows power-of-2 provides 54% higher throughput than random when
$\rho=1$. It minimizes the queuing delays attributed to writings of SSTables
colliding on the same StoC. When $\rho=3$, power-of-6 provides a comparable
throughput as $\rho=10$. A smaller $\rho$ results in larger sequential writes
that enhances the performance of hard disks. This is not highlighted in Table
5. As an example, with 5 LTCs and W100 using Uniform, when $\rho$=3 is
compared with $\rho$=10, its observed throughput is 17% higher.

Figure 1 in Section 1 presents results for two configurations of Nova-LSM:
shared-nothing and shared-disk. Both use the same hardware platform consisting
of 10 nodes. Each node has its own local disk drives. With the shared-nothing,
an LTC stores its SSTables on its local hard disk drive. With the shared-disk,
an LTC partitions a SSTable across $\rho$=3 StoCs (using power-of-d) out of
$\beta$=10 StoCs. In essence, the shared-nothing does not use the RDMA while
shared-disk uses the RDMA to enable LTCs to share disk bandwidth.

When compared with one another, the shared-disk provides the highest
performance gains with YCSB’s default Zipfian mean setting, 0.99. It utilizes
the bandwidth of all 10 disks while the shared-nothing causes the disk
bandwidth of the node containing the most popular data to become the
bottleneck. The degree of skew impacts the reported factor of improvements
with the shared-disk. For example, with a less skewed access pattern, say
Zipfian mean of 0.73 that directs 53% of requests to 10% of the keys, the
factor of improvement is reduced to 3.8, 3.7, and 5.7 with RW50, W100, and
SW50 workloads, respectively. The reduced load of the bottleneck server in the
shared-nothing architecture minimizes the impact of sharing disk bandwidth and
the factor of improvement.

(a) Throughput.

(b) Scalability.

Figure 14. Throughput and scalability as a function of $\eta$ with $\beta=10$,
$\rho=3$, $\alpha=64$, and $\delta=256$.

Scalability of LTCs: One may increase the number of LTCs in a configuration to
prevent its CPU from becoming the bottleneck. Figure 14 shows system
throughput as we increase the number of LTCs from 1 to 5 with Uniform. The
system is configured with a total of 256 memtables of which 64 are active and
10 StoCs. Each SSTable is partitioned across 3 StoCs, $\rho$=3. All reported
results are obtained using power-of-6.

The SW50 workload scales super-linearly. The database size is 10 GB in this
experiment. With 1 LTC and 4 GB of memtables, the database does not fit in
memory. With 5 LTCs, the database fits in the memtables of the LTCs, reducing
the number of accesses to StoCs for processing scans. It is important to note
that the CPUs of the nodes hosting LTCs remain fully utilized.

The RW50 workload scales sub-linearly because, while the CPU of 1 LTC is fully
utilized, it is not fully utilized with 2 or more LTCs. Moreover, the
percentage of time the experiment spends in write stall increases from 4% with
1 LTC to 13% with 2 LTCs and 39% with 5 LTCs as the disk bandwidth becomes
fully utilized. The same observation holds true with the W100 workload.

With Zipfian, the throughput does not scale. 85% of requests reference keys
assigned to the first LTC. The CPU of this LTC becomes fully utilized to
dictate the overall system performance. Section 8.2.6 describes migration of a
range from one LTC to another to balance load, enhancing performance.

(a) Throughput.

(b) Scalability.

Figure 15. Throughput and scalability as a function of $\beta$ with $\eta=5$,
$\rho=1$, $\alpha=64$, and $\delta=256$.

Scalability of 5 LTCs as a function of StoCs: Figure 15 shows the throughput
and scalability of different workloads with 5 LTCs as we increase the number
of StoCs from 1 to 10. We show the results with Uniform. With Zipfian, one LTC
containing the popular keys becomes the bottleneck to dictate the overall
processing capability. With both RW50 and W100, this LTC bottleneck is
encountered with 3 or more StoCs. With SW50, the bottleneck LTC is present
even with 1 StoCs. (See Section 8.2.6 for re-organization of ranges across
LTCs to address this bottleneck.)

The results with Uniform are very interesting. We discuss each of RW50, SW50,
and W100 in turn. RW50 with Uniform utilizes the disk bandwidth of one StoC
fully. It benefits from additional StoCs, resulting in a higher throughput as
we increase the number of StoCs. The size of the data stored on a StoC
decreases from 20 GB with 1 StoC to 2 GB with 10 StoC. With a single StoC, the
operating system’s page cache is exhausted. With more StoCs, reads are served
using the operating system’s page cache, causing the throughput to scale
super-linearly.

W100 scales up to 3 StoCs and then increases sublinearly with additional
StoCs. Writes stall since size of Level0 is set to 2 GB for all StoC settings.
They constitute 91%, 83%, 79%, 67% of experiment time with 1, 3, 5, 10 StoCs,
respectively. This duration must decrease linearly in order for system
throughput to scale linearly.

SW50 with Uniform utilizes the CPU of all 5 LTCs fully with 3 StoCs. Hence,
increasing the number of StoCs provides no performance benefit, resulting in
no horizontal scale-up.

####  8.2.6. Load balancing across LTCs

Table 6. Throughput (ops/s) with Zipfian and $\eta=5$, $\beta=10$, $\omega=64$, $\alpha=4$, $\delta=8$, $\rho=1$. Workload | Before migration | After migration | Improvement
---|---|---|---
RW50 | 415,798 | 988,420 | 2.38
SW50 | 50,396 | 210,193 | 4.17
W100 | 298,677 | 503,230 | 1.68

The coordinator may monitor the utilization of LTCs and implement a load
balancing technique such as (Serafini et al., 2014; Curino et al., 2011). With
Nova-LSM, it is trivial to migrate ranges across LTCs (detailed in Section 9).
This section focuses on experimental results of Figure 15 with a Zipfian
distribution of access that caused a single LTC to become the bottleneck while
the utilization of other LTCs is approximately 20%. We migrate ranges across
the LTCs to approximate a balanced load across different LTCs. The migration
requires only a few seconds because the bottleneck LTC pushes its ranges to
four different LTCs and each LTC uses one RDMA READ to fetch log records from
the StoC for each the relevant memtable.

Once the migration completes, both the throughput and scalability improve
dramatically, see Table 6. With both W100 and SW50 using Zipfian, the
scalability is similar to that shown with Uniform, see Figure 15(b). Moreover,
the explanation for why their throughput does not scale linearly is also the
same as the discussion with Uniform.

With RW50 using Zipfian, the scalability improves from 3x with 10 StoCs to 6x
after migration. RW50 with Zipfian observes cache hits in memtables, utilizing
the CPU of 5 LTCs fully. Hence, similar to SW50, it does not utilize the disk
bandwidth of all 10 StoCs.

(a) Throughput.

(b) Disk bandwidth of W100.

Figure 16. Impact of SSTable replication $R$ with Uniform and $\eta=1$,
$\beta=10$, $\alpha=64$, $\delta=256$.

####  8.2.7. SSTable Replication

An LTC replicates an SSTable and its fragments to continue operation in the
presence of failures that render a StoC unavailable. Figure 16 shows the
throughput of different workloads as a function of the degree of replication
for a SSTable, $R$. With hybrid, a SSTable contains one parity block for its 3
data block fragments and 3 replicas of its metadata blocks333While a metadata
block is approximately 200 KB in size, a data block fragment is approximately
5.3 MB in size.. Replicating a SSTable consumes disk bandwidth, reducing the
overall system throughput. Its impact is negligible with a workload that
utilizes the CPU fully, e.g., SW50 workload of Figure 16(a). With a disk
intensive workload, say W100, the throughput almost halves when we increase
$R$ from one to two. It drops further from two to three replicas. However, it
is not as dramatic because we use power-of-d. As shown in Figure 16(b), the
overall disk bandwidth utilization with $R=2$ is uneven with StoC 4 showing a
high utilization. With $R=3$, other StoCs start to become fully utilized (due
to power-of-d), resulting in a more even utilization of StoCs. Hence, the drop
in throughput is not as dramatic as $R=2$.

(a) RDMA and CPU processing time with 1 recovery thread.

(b) Recovery duration.

Figure 17. Recovery.

####  8.2.8. Recovery Duration

When an LTC fails, Nova-LSM recovers its memtables by replaying their log
records from in-memory StoC files. The recovery duration is dictated by the
memtable size, the number of memtables, and the number of recovery threads. We
first measure the recovery duration as a function of the number of memtables.
Figure 17(a) shows the recovery duration increases as the number of memtables
increases. We consider different numbers of memtables on the x-axis because
given a system with $\eta$ LTCs, the ranges of a failed LTC may be scattered
across $\eta$-1 LTCs. This enables reconstruction of the different ranges in
parallel, by requiring different LTCs to recover different memtables assigned
to each range.

An LTC fetches all log records from one StoC at the line rate using RDMA READ.
It fetches 4 GB of log records in less than 1 second. We also observe that
reconstructing memtables from log records dominates the recovery duration.

A higher number of threads speeds up recovery time significantly, see Figure
17(b). With 256 memtables, the recovery duration decreases from 13 seconds to
1.5 seconds as we increase the number of recovery threads from 1 to 32. With
32 recovery threads, the recovery duration is dictated by the speed of RDMA
READ.

###  8.3. Comparison with Existing Systems

This section compares Nova-LSM with LevelDB and RocksDB given the same amount
of hardware resources. We present results from both a single node and a ten-
node configuration using different settings:

  * •

LevelDB: One LevelDB instance per server, $\omega$=1, $\alpha$=1, $\delta$=2.

  * •

LevelDB*: 64 LevelDB instances per server, $\omega$=64, $\alpha$=1,
$\delta$=2.

  * •

RocksDB: One RocksDB instance per server, $\omega$=1, $\alpha$=1,
$\delta$=128.

  * •

RocksDB*: 64 RocksDB instances per server, $\omega$=64, $\alpha$=1,
$\delta$=2.

  * •

RocksDB-tuned: One RocksDB instance per server with tuned knobs, $\omega=1$.
We enumerate RocksDB knob values and report the highest throughput. Example
knobs include size ratio, Level1 size, number of Level0 files to trigger
compaction, number of Level0 files to stall writes.

(a) 10 GB database and 1 server.

(b) 100 GB database range partitioned across 10 servers.

(c) 1 TB database range partitioned across 10 servers.

(d) 2 TB database range partitioned across 10 servers.

Figure 18. Comparison of Nova-LSM with LevelDB and RocksDB.

We conducted many experiments with different settings and observe similar
results. Here, we report results with logging disabled to provide an apple-to-
apple comparison. If we enable logging, performance of both LevelDB and
RocksDB would decrease by a factor of 50. For example, in Figure 18(a),
performance of LevelDB* would reduce from 50K to 1K with W100 Uniform. We
compare the different systems using 1 node and 10 nodes in turn.

Nova-LSM uses one range per server with 64 active memtables and 128 memtables
per range, i.e., $\alpha=64$ and $\delta=128$. Its logging is also disabled
unless stated otherwise. With one server, a StoC client at LTC writes SSTables
to its local disk directly. With 10 servers, each LTC scatters a SSTable
across $\rho$=3 StoCs with different SSTables scattered across all 10 StoCs
using power-of-6.

Figure 18 shows the comparison with three different database sizes using 1
node and 10 nodes. We discuss each configuration in turn.

####  8.3.1. One Node

Figure 18(a) shows the throughput of LevelDB, RocksDB, and Nova-LSM with the
aforementioned configurations. The x-axis of this figure identifies different
workloads and access patterns. The numbers on top of each bar denote the
factor of improvement relative to one LevelDB instance. Clearly, Nova-LSM
achieves comparable performance with Uniform and outperforms both LevelDB and
RocksDB with Zipfian.

Table 7. Response time (ms) with Zipfian. | R100 | RW50 | SW50 | W100
---|---|---|---|---
Avg | p95 | p99 | Avg | p95 | p99 | Avg | p95 | p99 | Avg | p95 | p99
LevelDB* | 55 | 304 | 596 | 57 | 324 | 586 | 118 | 615 | 1060 | 5.11 | 0.67 | 0.89
RocksDB* | 56 | 272 | 742 | 60 | 353 | 630 | 128 | 650 | 984 | 3.97 | 0.69 | 1.08
RocksDB-tuned | 71 | 401 | 667 | 75 | 381 | 649 | 139 | 769 | 1232 | 1.93 | 0.70 | 1.02
Nova-LSM | 8 | 43 | 145 | 9 | 61 | 167 | 22 | 98 | 386 | 0.46 | 0.66 | 0.67

With Zipfian, Nova-LSM outperforms both LevelDB and RocksDB for all workloads.
With RW50, Nova-LSM achieves 34x higher throughput than LevelDB with
$\omega=1$ and 7x higher throughput when $\omega=64$. This is because use of
Dranges enables Nova-LSM writes less data to disk, 65% less. Nova-LSM merges
memtables from Dranges with less than 100 unique keys into a new memtable
without flushing them to disk. It uses the otherwise unutilized disk bandwidth
to compact SSTables produced by different Dranges.

With SW50 and Zipfian, the throughput of Nova-LSM is 105x higher than LevelDB
with $\omega=1$ and 8x higher when $\omega=64$. While LevelDB/RocksDB scans
through all versions of a hot key, Nova-LSM seeks to its latest version and
skips all of its older versions. However, maintaining the range index incurs a
15% overhead with Uniform since the CPU is 100% utilized, causing Nova-LSM to
provide a lower throughput than LevelDB with $\omega=64$.

####  8.3.2. Ten Nodes with Large Databases

Figure 18 shows a comparison of Nova-LSM with existing systems using 10 nodes
and two different database sizes: 100 GB and 1 TB. With 1 TB, the LSM-tree has
4 levels for each range. LevelDB* and RocksDB* result in a total of 640
instances. We analyze two different configurations of Nova-LSM with and
without logging.

With Zipfian, Nova-LSM outperforms both LevelDB and RocksDB by more than an
order of magnitude, see Figure 18(b) and Figure 18(c). With a 100 GB database,
Nova-LSM provides 22x higher throughput than LevelDB*. The throughput gain is
9x with the 1 TB database. This is because 85% of requests are referencing the
first server, causing it to become the bottleneck. With LevelDB* and RocksDB*,
the disk bandwidth of the first server is fully utilized and dictates the
overall throughput. With Nova-LSM, while the CPU of the server hosting the LTC
assigned the range with the most popular keys becomes the bottleneck, this LTC
uses the bandwidth of all 10 disks. This also explains why the throughput is
lower when logging is enabled.

With Uniform, the throughput of Nova-LSM is comparable to other systems for
RW50 and SW50. This is because the operating system’s page caches are
exhausted and the cache misses must fetch blocks from disk. These random seeks
limit the throughput of the system. This also explains why the overall
throughput is much lower with the 1 TB database when compared with the 100 GB.
With W100, Nova-LSM provides a higher throughput because the 10 disks are
shared across 10 servers and a server scatters a SSTable across 3 disks with
the shortest queues.

####  8.3.3. Response Times with a 2 TB Database

We analyzed the average, p95 and p99 response time of the different systems
with R100, RW50, SW50, and W100 workloads, see Table 7. These experiments
quantify response time with a low system load: 60 YCSB threads issuing
requests to a 10 node Nova-LSM configuration. With Uniform, all systems
provide comparable response times. With Zipfian, Nova-LSM outperforms the
other systems more than 3x. A fraction of reads reference keys not found in
the index and must search the other levels. This fraction results in a higher
observed response times with p95 and p99. Nova-LSM enhances the average, p95,
and p99 response times by using its index structures and all 10 disks to
process concurrent reads and writes. With RocksDB and LevelDB, clients direct
85% of requests to one disk, degrading response times due to queuing delays.

With W100, a surprising result is the higher average response time when
compared with p95 and p99 for both LevelDB and RocksDB. Write-stalls cause a
few requests to encounter long queuing delays on 1 disk. While the p95 and p99
calculations drop these outliers, calculation of the average includes them to
result in a higher response time.

Figure 19. Comparison of Nova-LSM with LevelDB and RocksDB on tmpfs.

####  8.3.4. Faster Storage

Reported trends hold true with storage devices faster than hard disk. In its
most extreme, the storage may be as fast as memory. We emulated this by using
an in-memory file system, tmpfs (Snyder, 1990), with a 100 GB database
partitioned across 10 servers. In these experiments, the CPU is the bottleneck
resource. Nova-LSM continues to provide a higher throughput than LevelDB* with
Zipfian. This is a factor of 2 to 7 depending on whether Nova-LSM is
configured with logging. While Nova-LSM offloads compactions to StoCs, LevelDB
and RocksDB use a single node to process most of requests and compactions.
With SW50 workload, RocksDB* provides a higher throughput than Nova-LSM by
processing fewer memtables. RocksDB* contains 64 application ranges per server
with 2 memtables per range. A scan searches 2 memtables. With Nova-LSM, a scan
may overlap multiple Dranges with 2 memtables assigned to each Drange. In the
reported experiments, a scan may search a maximum of 26 memtables. With
Uniform, Nova-LSM provides 10% to 30% lower throughput due to the maintenance
of the index structures with writes and RDMA threads pulling for requests.
Both are CPU intensive tasks.

##  9\. Elasticity

Section 8 highlights different components of Nova-LSM must scale elastically
for different workloads. While LTCs must scale elastically with CPU intensive
workloads such as SW50, StoCs must scale elastically with disk I/O intensive
workloads such as RW50.

Elastic scalability has been studied extensively. There exist heuristic-based
techniques (Trushkowsky et al., 2011; Wang et al., 2012; Serafini et al.,
2014; Das et al., 2016) and a mixed integer linear programming (Serafini et
al., 2014; Curino et al., 2011) formulation of the problem. The coordinator of
Figure 3 may adopt one or more of these techniques. We defer this to future
work. Instead, this section describes how the coordinator may add or remove
either an LTC or a StoC from a configuration. Scaling StoCs migrates data
while scaling LTCs migrates metadata and in-memory memtables. Both use RDMA to
perform this migration.

Adding and Removing LTCs: Scaling LTCs migrates one or more ranges from a
source LTC to one or more destination LTCs. It requires the source LTC to
inform the destination LTC of the metadata of the migrating range. This
includes the metadata of LSM-tree, Dranges, Tranges, lookup index, range
index, and locations of log record replicas. It sends the metadata to the
destination LTC using RDMA WRITE. The destination LTC uses this metadata to
reconstruct the range. It also uses multiple background threads to reconstruct
the memtables by replaying their log records in parallel. In experiments
reported below, the total amount of data transferred when migrating a range
was 45 MB. Approximately 1% of this data, 613 KB, was for metadata. The
remaining 99% were log records to reconstruct partially full memtables.

(a) SW50 Uniform, starting config has $\eta=1$, $\beta=13$, $\alpha=4$,
$\delta=8$, $\omega=64$.

(b) RW50 Uniform, starting config has $\eta=3$, $\beta=3$, $\alpha=4$,
$\delta=8$, $\omega=64$.

Figure 20. Elasticity.

The coordinator may redirect clients that reference a migrating range to
contact the destination LTC as soon as it renders the migration decision. The
destination LTC blocks a request that references the migrating range until it
completes reconstructing its metadata and relevant memtables. (It may give a
higher priority to reconstruct those memtables with pending requests.) In our
experiments, the maximum delay incurred to reconstruct metadata of a migrating
range was 570 milliseconds.

Figure 20(a) shows the throughput of SW50 workload with a base configuration
consisting of 1 LTC and 13 StoCs. This workload utilizes the CPU of the LTC
fully, providing a throughput of 100K operations/second. There is sufficient
disk bandwidth to render write stalls insignificant, resulting in an
insignificant throughput variation from 90K to 100K operations per second. We
add 1 new LTC and migrate half the ranges to it. This almost doubles the
throughput. However, write stalls result in a significantly higher throughput
variation ranging from 100K to 200K operations per second. Finally, we add a
3rd LTC. The peak throughput increases to 300K operations per second,
utilizing the CPU of the 3rd LTC fully. Write stalls cause the observed
throughput to vary from 175K to 300K operations per second. While the average
throughput does not scale linearly with additional LTCs due to write stalls,
the peak throughput increases linearly as a function of LTCs.

Adding and Removing StoCs: When a StoC is added to an existing configuration,
LTCs assign new SSTables to the new StoC immediately using power-of-d. Nova-
LSM also considers the possibility of this StoC having replicas of data as
this StoC may have been a part of a previous configuration (and shut down due
to a low system load). A file is useful if it is still referenced by a
SSTable. Otherwise, it is obsolete and is deleted.

Each file name maintains its range id and SSTable file number. A new StoC
starts by enumerating its files to retrieve each file’s range id and SSTable
file number. For each file, it identifies the LTC hosting its range and
queries it to determine if the SSTable is still referenced. If it is not
referenced then the StoC deletes this file. Otherwise, the LTC extends the
SSTable metadata to reference this replica for future use. This may increase
the number of replicas for a data fragment, a metadata block, and a parity
block beyond that specified by an application. If space is at a premium, this
data may be deleted. Given the inexpensive price of disks (2 to 3 pennies per
Gigabyte) and the immutable nature of SSTables, a StoC may maintain these
additional replicas. They are useful because they minimize the amount of data
that must be migrated once this StoC is shutdown during off-peak hours. Once
an LTC repairs metadata of a SSTable, it issues reads to the new StoC using
power-of-d immediately.

When a StoC is shut down gracefully, each LTC analyzes its StoC’s files. It
identifies those SSTables fragments or parity blocks pertaining to SSTables of
its assigned ranges. Next, it identifies a destination StoC for each fragment
while respecting placement constraints, e.g., replicas of a SSTable must be
stored on different StoCs. Lastly, it informs the source StoCs to copy the
identified files to their destinations using RDMA.

Figure 20(b) shows the throughput of the RW50 workload with 3 LTCs and 3
StoCs. Each SSTable is assigned to 1 StoC, $\rho$=1. We increase the number of
StoCs by one every 15 minutes until the number of StoCs reaches 9. With 8
StoCs, the number of write stalls is diminished significantly as there is
sufficient disk bandwidth to keep up with compactions. The number of write
stalls is further reduced with the 9th StoC. Next, we remove the StoCs by 1
every 15 minutes until we are down to 3 StoCs. This reduces the observed
throughput as RW50 is disk I/O intensive.

In Figure 20(b), the average throughput increases from 700K with 3 StoCs to
1.35M with 9 StoCs. This 2 fold increase in throughput is realized by
increasing the number of StoCs 3 folds. The sub-linear increase in throughput
is because the load is unevenly distributed across 9 StoCs even though we use
power-of-d. The average disk bandwidth utilization varies from 76% to 93%. The
base configuration does not have this limitation since it consists of 3 StoCs
and each SSTable is partitioned across all 3 StoCs, $\rho=3$.

##  10\. Related Work

LSM-tree data stores: Today’s monolithic LSM-tree systems (Dong et al., 2017;
Escriva, 2020; Golan-Gueta et al., 2015; Sears and Ramakrishnan, 2012; Dai et
al., 2020; Luo and Carey, 2020a) require a few memtables to saturate the
bandwidth of one disk. Nova-LSM uses a large number of memtables to saturate
the disk bandwidth of multiple StoCs. Its Dranges, lookup index, and range
index complement this design decision.

TriAD (Balmau et al., 2017a) and X-Engine (Huang et al., 2019) separate hot
keys and cold keys to improve performance with data skew. Nova-LSM constructs
Dranges to mitigate the impact of skew. Dranges that contain hot keys maintain
these keys in their memtables without flushing them to StoCs. Dranges also
facilitate compaction of SSTables at Level0.

FloDB (Balmau et al., 2017b) and Accordion (Bortnikov et al., 2018) redesign
LSM-tree for large memory. Both do not address the challenges of compaction
and expensive reads due to a large number of Level0 SSTables. Nova-LSM
maintains lookup index and range index to expedite gets and scans. With FloDB,
a scan may restart many times and block writes. With Nova-LSM, a scan never
restarts and does not block writes.

An adaptive memory management technique for reads and writes referencing
multiple LSM-Trees is described in (Luo and Carey, 2020a). For writes to each
LSM-tree, it maintains one active memtable and a set of immutable memtables
organized into levels. In contrast, Nova-LSM’s LTC maintains multiple active
memtables for a LSM-tree. One for each Drange. This enables different threads
(CPU cores) to write to different Dranges concurrently. An LTC does not flush
immutable memtables with fewer than a pre-specified number of unique values
(100 in our experiments) to disk. With a Drange that consists of 3 or more
immutable memtables, one may use write technique of (Luo and Carey, 2020a).
Quantifying the tradeoffs associated with these alternatives is a short term
research direction. Note that an LTC may use the memory tuner of (Luo and
Carey, 2020a) to manage its buffer cache and write memory.

AC-Key is a caching technique to enhance performance of reads and scans for
LSM-based key-value stores (Wu et al., 2020). Nova-LSM may implement AC-Key or
CAMP (Ghandeharizadeh et al., 2014) as a component.

Both RocksDB subcompactions (Facebook, 2020) and Vinyl (Tarantool, 2020) use
detective techniques while Nova-LSM’s proposed Dranges is a preventive
technique. RocksDB may construct ranges at compaction time and assign a range
to each sub compaction thread. This is redundant with Nova-LSM because it uses
Dranges. Vinyl splits on-disk SSTables into slices. Nova-LSM splits memtables
(of a range) using Dranges. A Level0 SSTable of Vinyl may span the entire
keyspace of a range. Dranges prevent this in Nova-LSM.

The compaction policy is intrinsic to the performance of an LSM-tree. Chen et
al. (Luo and Carey, 2020b) present an extensive survey of alternative LSM-tree
designs. PebblesDB (Raju et al., 2017) uses tiering to reduce write
amplification at the cost of more expensive reads. Dostoevsky (Dayan and
Idreos, 2018) analyzes the space-time trade-offs of alternative policies and
proposes new policies that achieve a better space-time trade-off. Nova-LSM may
use these policies as its future extensions.

Several studies redesign LSM-tree to use fast storage mediums, SSD and NVM (Lu
et al., 2016; Kannan et al., 2018; Kaiyrakhmet et al., 2019; Yao et al.,
2020). NoveLSM reduces write amplification by placing memtables on NVM and
updating the entries in-place (Kannan et al., 2018). MatrixKV uses a multi-
tier DRAM-NVM-SSD to reduce write stalls and mitigate write amplifications
(Yao et al., 2020). Nova-LSM’s StoC may use these storage mediums and
techniques.

Multi-node data stores use LSM-tree to store their data, e.g., BigTable (Chang
et al., 2008), Cassandra (Lakshman and Malik, 2010; Ahmad and Kemme, 2015),
and AsterixDB (Alsubaiee et al., 2014). Nova-LSM is different because it
separates its compute from storage. Its LTC also offloads compaction to StoCs.

Cooperative LSM (Mittal and Nawab, 2021), CooLSM, is designed for wide-area
networks where processing and storage span both edge and cloud nodes. Its
architecture addresses the network latency associated with geographically
distributed applications such as IoT. It consists of Ingestor processes that
receive the write requests and maintain Levels L0 and L1, range partitioned
Compactor processes that maintain the rest of levels, and Reader processes
that maintain a copy of the entire LSM tree for recovery and read
availability. Nova-LSM and its components are different as they are designed
for a data center with fast network connectivity. Hence, data is range
partitioned across LTCs that maintain only memtables. LTCs may off-load
compaction to StoCs making them similar to CooLSM’s compactors. However, Nova-
LSM does not range partition data across StoCs.

Separation of storage from processing: A recent trend in database community is
to separate storage from processing. Example databases are Aurora (Verbitski
et al., 2017), Socrates (Antonopoulos et al., 2019), SolarDB (Zhu et al.,
2019), HBase (contributors, 2020), Taurus (Depoutovitch et al., 2020), and
Tell (Loesing et al., 2015). Nova-LSM is inspired by these studies. Our
proposed separation of LTC from StoC, declustering of a SSTable to share disk
bandwidth, parity-based and replication techniques for data availability, and
power-of-d using RDMA are novel and may be used by the storage component of
these prior studies.

An LSM-tree may run on a distributed file system to utilize the bandwidth of
multiple disks. Orion (Yang et al., 2019) is a distributed file system for
non-volatile memory and RDMA-capable networks. Hailstorm (Bindschaedler et
al., 2020) is designed specifically for LSM-tree data stores. POLARFS (Cao et
al., 2018) provides ultra-low latency by utilizing networking stack and I/O
stack in userspace. Nova-LSM also harnesses the bandwidth of multiple disks.
Its LTC scatters a SSTable across multiple StoCs and uses power-of-d to
minimize delays.

Rockset (Pham, 2020) separates processing from storage by offloading
compaction to Amazon S3. Nova-LSM uses off-the-shelf hardware and software,
controlling the number of physical storage devices ($\rho$) that store a
SSTable.

RDMA-based systems: LegoOS (Shan et al., 2018) disaggregates the physical
resources of a monolithic server into network-attached components. These
components exchange data using RDMA. Nova-LSM may implement its components
using LegoOS. For example, StoC may be implemented using LegoOS’s file system.

Tailwind (Taleb et al., 2018) and Active-Memory (Zamanian et al., 2019) are
replication techniques designed for RDMA. Both replicate data using RDMA
WRITE. LogC also uses RDMA WRITE to replicate log records for high
availability.

Several studies present optimizations on the use of RDMA to enhance
performance and scalability for in-memory key-value stores (Wei et al., 2018;
Dragojević et al., 2014; Huang and Ghandeharizadeh, 2019; Ghandeharizadeh and
Huang, 2019). Nova-LSM is a disk-based data store. Its components use
dedicated threads to minimize the number of QPs.

In-memory key-value stores: In-memory KVSs (FaRM and its extension with
transactions (Dragojević et al., 2014, 2015)) are a different class of systems
than persistent KVSs (Nova-LSM). Their target different applications. In-
memory KVSs outperform persistent KVSs because DRAM is significantly faster
than SSD/HDD. FASTER (Chandramouli et al., 2018) uses an in-memory hash table
to process gets, puts, and RMW expeditiously. It states that its targets
applications are different than KVSs based on LSM-tree and does not support a
sorted order of keys for processing scans.

##  11\. Future Work

We are extending Nova-LSM with new functionalities, application Service Level
Agreements (SLAs), and cost analysis. An example functionality is a write
batch that performs several puts and deletes atomically. We are exploring both
lock-free and lock-based techniques to support this functionality. With the
former, each key impacted by a write batch is extended to identify the other
keys and sequence numbers in the batch. A read that fetches the value of two
or more of these keys detects the metadata and verifies their sequence numbers
to ensure it does not observe values of a concurrent write batch. Otherwise,
it aborts and restarts. A lock-based technique in combination with a two-phase
commit protocol may implement strict serial schedules with write batch, multi-
get, and scan that span multiple LTCs.

SLAs include performance, availability, and consistency requirements of an
application. SLAs motivate an auto-tuner that scales components both
vertically (Das et al., 2016) and horizontally (Serafini et al., 2014). This
must be done intelligently per discussions of Figure 2.

Finally, a cost-analysis quantifies the expense associated with the hardware
platform, power usage, and maintenance. While networking hardware such as RDMA
is expensive, should it reduce the size of a system 10 folds then its savings
in power and space may outweigh its expenses.

##  12\. Acknowledgments

We gratefully acknowledge use of CloudLab network testbed (Duplyakin et al.,
2019) for all experimental results presented in this paper. We thank SIGMOD’s
anonymous reviewers for their valuable comments.

## References

  * (1)
  * Ahmad and Kemme (2015) Muhammad Yousuf Ahmad and Bettina Kemme. 2015.  Compaction Management in Distributed Key-Value Datastores.  _Proc. VLDB Endow._ 8, 8 (April 2015), 850–861.  https://doi.org/10.14778/2757807.2757810
  * Airbnb (2016) Airbnb. 2016.  _Apache HBase at Airbnb_.  https://www.slideshare.net/HBaseCon/apache-hbase-at-airbnb
  * Alsubaiee et al. (2014) Sattam Alsubaiee, Yasser Altowim, Hotham Altwaijry, Alexander Behm, Vinayak Borkar, Yingyi Bu, Michael Carey, Inci Cetindil, Madhusudan Cheelangi, Khurram Faraaz, Eugenia Gabrielova, Raman Grover, Zachary Heilbron, Young-Seok Kim, Chen Li, Guangqiang Li, Ji Mahn Ok, Nicola Onose, Pouria Pirzadeh, Vassilis Tsotras, Rares Vernica, Jian Wen, and Till Westmann. 2014.  AsterixDB: A Scalable, Open Source BDMS.  _Proc. VLDB Endow._ 7, 14 (Oct. 2014), 1905–1916.  https://doi.org/10.14778/2733085.2733096
  * Antonopoulos et al. (2019) Panagiotis Antonopoulos, Alex Budovski, Cristian Diaconu, Alejandro Hernandez Saenz, Jack Hu, Hanuma Kodavalla, Donald Kossmann, Sandeep Lingam, Umar Farooq Minhas, Naveen Prakash, Vijendra Purohit, Hugh Qu, Chaitanya Sreenivas Ravella, Krystyna Reisteter, Sheetal Shrotri, Dixin Tang, and Vikram Wakade. 2019\.  Socrates: The New SQL Server in the Cloud. In _Proceedings of the 2019 International Conference on Management of Data_ (Amsterdam, Netherlands) _(SIGMOD ’19)_. Association for Computing Machinery, New York, NY, USA, 1743–1756.  https://doi.org/10.1145/3299869.3314047
  * Balmau et al. (2017a) Oana Balmau, Diego Didona, Rachid Guerraoui, Willy Zwaenepoel, Huapeng Yuan, Aashray Arora, Karan Gupta, and Pavan Konka. 2017a.  TRIAD: Creating Synergies Between Memory, Disk and Log in Log Structured Key-Value Stores. In _2017 USENIX Annual Technical Conference (USENIX ATC 17)_. USENIX Association, Santa Clara, CA, 363–375.  https://www.usenix.org/conference/atc17/technical-sessions/presentation/balmau
  * Balmau et al. (2019) Oana Balmau, Florin Dinu, Willy Zwaenepoel, Karan Gupta, Ravishankar Chandhiramoorthi, and Diego Didona. 2019.  SILK: Preventing Latency Spikes in Log-Structured Merge Key-Value Stores. In _2019 USENIX Annual Technical Conference (USENIX ATC 19)_. USENIX Association, Renton, WA, 753–766.  https://www.usenix.org/conference/atc19/presentation/balmau
  * Balmau et al. (2017b) Oana Balmau, Rachid Guerraoui, Vasileios Trigonakis, and Igor Zablotchi. 2017b.  FloDB: Unlocking Memory in Persistent Key-Value Stores. In _Proceedings of the Twelfth European Conference on Computer Systems_ (Belgrade, Serbia) _(EuroSys ’17)_. Association for Computing Machinery, New York, NY, USA, 80–94.  https://doi.org/10.1145/3064176.3064193
  * Berenson et al. (1995) Hal Berenson, Phil Bernstein, Jim Gray, Jim Melton, Elizabeth O’Neil, and Patrick O’Neil. 1995\.  A Critique of ANSI SQL Isolation Levels.  _SIGMOD Rec._ 24, 2 (May 1995), 1–10.  https://doi.org/10.1145/568271.223785
  * Bindschaedler et al. (2020) Laurent Bindschaedler, Ashvin Goel, and Willy Zwaenepoel. 2020\.  Hailstorm: Disaggregated Compute and Storage for Distributed LSM-Based Databases. In _Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems_ (Lausanne, Switzerland) _(ASPLOS ’20)_. Association for Computing Machinery, New York, NY, USA, 301–316.  https://doi.org/10.1145/3373376.3378504
  * Bortnikov et al. (2018) Edward Bortnikov, Anastasia Braginsky, Eshcar Hillel, Idit Keidar, and Gali Sheffi. 2018\.  Accordion: Better Memory Organization for LSM Key-Value Stores.  _Proc. VLDB Endow._ 11, 12 (Aug. 2018), 1863–1875.  https://doi.org/10.14778/3229863.3229873
  * Cao et al. (2018) Wei Cao, Zhenjun Liu, Peng Wang, Sen Chen, Caifeng Zhu, Song Zheng, Yuhui Wang, and Guoqing Ma. 2018\.  PolarFS: An Ultra-Low Latency and Failure Resilient Distributed File System for Shared Storage Cloud Database.  _Proc. VLDB Endow._ 11, 12 (Aug. 2018), 1849–1862.  https://doi.org/10.14778/3229863.3229872
  * Chandramouli et al. (2018) Badrish Chandramouli, Guna Prasaad, Donald Kossmann, Justin Levandoski, James Hunter, and Mike Barnett. 2018.  FASTER: A Concurrent Key-Value Store with In-Place Updates. In _Proceedings of the 2018 International Conference on Management of Data_ (Houston, TX, USA) _(SIGMOD ’18)_. Association for Computing Machinery, New York, NY, USA, 275–290.  https://doi.org/10.1145/3183713.3196898
  * Chang et al. (2008) Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber. 2008.  Bigtable: A Distributed Storage System for Structured Data.  _ACM Trans. Comput. Syst._ 26, 2, Article 4 (June 2008), 26 pages.  https://doi.org/10.1145/1365815.1365816
  * contributors (2020) Apache HBase contributors. 2020\.  _Apache HBase_.  The Apache Software Foundation.  https://hbase.apache.org
  * Cooper et al. (2010) Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010\.  Benchmarking Cloud Serving Systems with YCSB. In _Proceedings of the 1st ACM Symposium on Cloud Computing_ (Indianapolis, Indiana, USA) _(SoCC ’10)_. ACM, New York, NY, USA, 143–154.  https://doi.org/10.1145/1807128.1807152
  * Curino et al. (2011) Carlo Curino, Evan P.C. Jones, Samuel Madden, and Hari Balakrishnan. 2011.  Workload-Aware Database Monitoring and Consolidation. In _Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data_ (Athens, Greece) _(SIGMOD ’11)_. Association for Computing Machinery, New York, NY, USA, 313–324.  https://doi.org/10.1145/1989323.1989357
  * Dai et al. (2020) Yifan Dai, Yien Xu, Aishwarya Ganesan, Ramnatthan Alagappan, Brian Kroth, Andrea Arpaci-Dusseau, and Remzi Arpaci-Dusseau. 2020.  From WiscKey to Bourbon: A Learned Index for Log-Structured Merge Trees. In _14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20)_. USENIX Association, 155–171.  https://www.usenix.org/conference/osdi20/presentation/dai
  * Das et al. (2016) Sudipto Das, Feng Li, Vivek R. Narasayya, and Arnd Christian König. 2016.  Automated Demand-Driven Resource Scaling in Relational Database-as-a-Service. In _Proceedings of the 2016 International Conference on Management of Data_ (San Francisco, California, USA) _(SIGMOD ’16)_. Association for Computing Machinery, New York, NY, USA, 1923–1934.  https://doi.org/10.1145/2882903.2903733
  * Dayan and Idreos (2018) Niv Dayan and Stratos Idreos. 2018.  Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging. In _Proceedings of the 2018 International Conference on Management of Data_ (Houston, TX, USA) _(SIGMOD ’18)_. Association for Computing Machinery, New York, NY, USA, 505–520.  https://doi.org/10.1145/3183713.3196927
  * Depoutovitch et al. (2020) Alex Depoutovitch, Chong Chen, Jin Chen, Paul Larson, Shu Lin, Jack Ng, Wenlin Cui, Qiang Liu, Wei Huang, Yong Xiao, and Yongjun He. 2020\.  Taurus Database: How to Be Fast, Available, and Frugal in the Cloud. In _Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data_ (Portland, OR, USA) _(SIGMOD ’20)_. Association for Computing Machinery, New York, NY, USA, 1463–1478.  https://doi.org/10.1145/3318464.3386129
  * DeWitt et al. (1990) David J. DeWitt, Shahram Ghandeharizadeh, Donovan A. Schneider, Allan Bricker, Hui-I Hsiao, and Rick Rasmussen. 1990.  The Gamma Database Machine Project.  _IEEE Trans. Knowl. Data Eng._ 2, 1 (1990), 44–62.  https://doi.org/10.1109/69.50905
  * Dong et al. (2017) Siying Dong, Mark Callaghan, Leonidas Galanis, Dhruba Borthakur, Tony Savor, and Michael Strum. 2017.  Optimizing Space Amplification in RocksDB. In _CIDR 2017, 8th Biennial Conference on Innovative Data Systems Research, Chaminade, CA, USA, January 8-11, 2017, Online Proceedings_ (Chaminade, California, USA). www.cidrdb.org, Chaminade, California, USA.  http://cidrdb.org/cidr2017/papers/p82-dong-cidr17.pdf
  * Dragojević et al. (2014) Aleksandar Dragojević, Dushyanth Narayanan, Miguel Castro, and Orion Hodson. 2014.  FaRM: Fast Remote Memory. In _11th USENIX Symposium on Networked Systems Design and Implementation (NSDI 14)_. USENIX Association, Seattle, WA, 401–414.  https://www.usenix.org/conference/nsdi14/technical-sessions/dragojevi{ć}
  * Dragojević et al. (2015) Aleksandar Dragojević, Dushyanth Narayanan, Edmund B. Nightingale, Matthew Renzelmann, Alex Shamis, Anirudh Badam, and Miguel Castro. 2015.  No Compromises: Distributed Transactions with Consistency, Availability, and Performance. In _Proceedings of the 25th Symposium on Operating Systems Principles_ (Monterey, California) _(SOSP ’15)_. Association for Computing Machinery, New York, NY, USA, 54–70.  https://doi.org/10.1145/2815400.2815425
  * Duplyakin et al. (2019) Dmitry Duplyakin, Robert Ricci, Aleksander Maricq, Gary Wong, Jonathon Duerig, Eric Eide, Leigh Stoller, Mike Hibler, David Johnson, Kirk Webb, Aditya Akella, Kuangching Wang, Glenn Ricart, Larry Landweber, Chip Elliott, Michael Zink, Emmanuel Cecchet, Snigdhaswin Kar, and Prabodh Mishra. 2019.  The Design and Operation of Cloudlab. In _Proceedings of the 2019 USENIX Conference on Usenix Annual Technical Conference_ (Renton, WA, USA) _(USENIX ATC ’19)_. USENIX Association, USA, 1–14.
  * Escriva (2020) Robert Escriva. 2020\.  _HyperLevelDB_.  HyperDex.  https://github.com/rescrv/HyperLevelDB
  * Facebook (2020) Facebook. 2020.  _RocksDB Sub Compaction_.  https://github.com/facebook/rocksdb/wiki/Sub-Compaction
  * Fent et al. (2020) P. Fent, A. v. Renen, A. Kipf, V. Leis, T. Neumann, and A. Kemper. 2020\.  Low-Latency Communication for Fast DBMS Using RDMA and Shared Memory. In _2020 IEEE 36th International Conference on Data Engineering (ICDE)_. 1477–1488.  https://doi.org/10.1109/ICDE48307.2020.00131
  * Ford et al. (2010) Daniel Ford, François Labelle, Florentina I. Popovici, Murray Stokely, Van-Anh Truong, Luiz Barroso, Carrie Grimes, and Sean Quinlan. 2010\.  Availability in Globally Distributed Storage Systems. In _Presented as part of the 9th USENIX Symposium on Operating Systems Design and Implementation_. USENIX, Vancouver, BC.  https://www.usenix.org/conference/osdi10/availability-globally-distributed-storage-systems
  * Ghandeharizadeh et al. (2019a) Shahram Ghandeharizadeh, Marwan Almaymoni, and Haoyu Huang. 2019a.  Rejig: A Scalable Online Algorithm for Cache Server Configuration Changes. In _Transactions on Large-Scale Data- and Knowledge-Centered Systems XLII_. Springer Berlin Heidelberg, Berlin, Heidelberg, 111–134.  https://doi.org/10.1007/978-3-662-60531-8_5
  * Ghandeharizadeh and Huang (2018) Shahram Ghandeharizadeh and Haoyu Huang. 2018.  Gemini: A Distributed Crash Recovery Protocol for Persistent Caches. In _Proceedings of the 19th International Middleware Conference_ (Rennes, France) _(Middleware ’18)_. ACM, New York, NY, USA, 134–145.  https://doi.org/10.1145/3274808.3274819
  * Ghandeharizadeh and Huang (2019) Sharam Ghandeharizadeh and Haoyu Huang. 2019.  Scaling Data Stores with Skewed Data Access: Solutions and Opportunities. In _8th Workshop on Scalable Cloud Data Management, co-located with IEEE BigData ’19_.
  * Ghandeharizadeh et al. (2019b) Shahram Ghandeharizadeh, Haoyu Huang, and Hieu Nguyen. 2019b.  Nova: Diffused Database Processing using Clouds of Components [Vision Paper]. In _15th IEEE International Conference on Beyond Database Architectures and Structures (BDAS)_. Ustron, Poland.
  * Ghandeharizadeh et al. (2014) Shahram Ghandeharizadeh, Sandy Irani, Jenny Lam, and Jason Yap. 2014.  CAMP: A Cost Adaptive Multi-queue Eviction Policy for Key-value Stores. In _Proceedings of the 15th International Middleware Conference, Bordeaux, France, December 8-12, 2014_ , Laurent Réveillère, Lucy Cherkasova, and François Taïani (Eds.). ACM, 289–300.  https://doi.org/10.1145/2663165.2663317
  * Ghemawat and Dean (2020) Sanjay Ghemawat and Jeff Dean. 2020.  _LevelDB_.  Google.  https://github.com/google/leveldb
  * Ghemawat et al. (2003) Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. 2003\.  The Google File System. In _Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles_ (Bolton Landing, NY, USA) _(SOSP ’03)_. ACM, New York, NY, USA, 29–43.  https://doi.org/10.1145/945445.945450
  * Golan-Gueta et al. (2015) Guy Golan-Gueta, Edward Bortnikov, Eshcar Hillel, and Idit Keidar. 2015.  Scaling Concurrent Log-Structured Data Stores. In _Proceedings of the Tenth European Conference on Computer Systems_ (Bordeaux, France) _(EuroSys ’15)_. Association for Computing Machinery, New York, NY, USA, Article 32, 14 pages.  https://doi.org/10.1145/2741948.2741973
  * Haung (2020) Haoyu Haung. 2020\.  _Component-based Distributed Data Stores_.  Ph.D. Dissertation. Los Angeles, CA, USA.  Advisor(s) Shahram Ghandeharizadeh.  http://digitallibrary.usc.edu/cdm/ref/collection/p15799coll89/id/394254/.
  * Holland et al. (2013) David A. Holland, Elaine Angelino, Gideon Wald, and Margo I. Seltzer. 2013.  Flash Caching on the Storage Client. In _2013 USENIX Annual Technical Conference (USENIX ATC 13)_. USENIX Association, San Jose, CA, 127–138.  https://www.usenix.org/conference/atc13/technical-sessions/presentation/holland
  * Huang et al. (2019) Gui Huang, Xuntao Cheng, Jianying Wang, Yujie Wang, Dengcheng He, Tieying Zhang, Feifei Li, Sheng Wang, Wei Cao, and Qiang Li. 2019\.  X-Engine: An Optimized Storage Engine for Large-Scale E-Commerce Transaction Processing. In _Proceedings of the 2019 International Conference on Management of Data_ (Amsterdam, Netherlands) _(SIGMOD ’19)_. Association for Computing Machinery, New York, NY, USA, 651–665.  https://doi.org/10.1145/3299869.3314041
  * Huang and Ghandeharizadeh (2019) Haoyu Huang and Sharam Ghandeharizadeh. 2019.  An Evaluation of RDMA-based Message Passing Protocols. In _6th Workshop on Performance Engineering with Advances in Software and Hardware for Big Data Science, co-located with IEEE BigData ’19_. IEEE, Los Angeles, CA, USA, 3854–3863.
  * Huang and Ghandeharizadeh (2021) Haoyu Huang and Shahram Ghandeharizadeh. 2021.  Nova-LSM: A Distributed, Component-based LSM-tree Key-value Store. In _Proceedings of the 2021 International Conference on Management of Data_ (Virtual event, China) _(SIGMOD ’21)_. Association for Computing Machinery, New York, NY, USA.  https://doi.org/10.1145/3448016.3457297
  * Hunt et al. (2010) Patrick Hunt, Mahadev Konar, Flavio P. Junqueira, and Benjamin Reed. 2010.  ZooKeeper: Wait-free Coordination for Internet-scale Systems. In _Proceedings of the 2010 USENIX Conference on USENIX Annual Technical Conference_ (Boston, MA) _(USENIXATC’10)_. USENIX Association, Berkeley, CA, USA, 11–11.  http://dl.acm.org/citation.cfm?id=1855840.1855851
  * Kaiyrakhmet et al. (2019) Olzhas Kaiyrakhmet, Songyi Lee, Beomseok Nam, Sam H. Noh, and Young ri Choi. 2019.  SLM-DB: Single-Level Key-Value Store with Persistent Memory. In _17th USENIX Conference on File and Storage Technologies (FAST 19)_. USENIX Association, Boston, MA, 191–205.  https://www.usenix.org/conference/fast19/presentation/kaiyrakhmet
  * Kalia et al. (2016) Anuj Kalia, Michael Kaminsky, and David G. Andersen. 2016\.  Design Guidelines for High Performance RDMA Systems. In _2016 USENIX Annual Technical Conference (USENIX ATC 16)_. USENIX Association, Denver, CO, 437–450.  https://www.usenix.org/conference/atc16/technical-sessions/presentation/kalia
  * Kannan et al. (2018) Sudarsun Kannan, Nitish Bhat, Ada Gavrilovska, Andrea Arpaci-Dusseau, and Remzi Arpaci-Dusseau. 2018\.  Redesigning LSMs for Nonvolatile Memory with NoveLSM. In _2018 USENIX Annual Technical Conference (USENIX ATC 18)_. USENIX Association, Boston, MA, 993–1005.  https://www.usenix.org/conference/atc18/presentation/kannan
  * Lakshman and Malik (2010) Avinash Lakshman and Prashant Malik. 2010.  Cassandra: A Decentralized Structured Storage System.  _SIGOPS Oper. Syst. Rev._ 44, 2 (April 2010), 35–40.  https://doi.org/10.1145/1773912.1773922
  * Li et al. (2017) Yu Li, Yu Sun, Anoop Sam John, and Ramkrishna S. Vasudevan. 2017.  _Offheap Read-Path in Production - The Alibaba Story_.  https://blogs.apache.org/hbase/entry/offheap-read-path-in-production
  * Loesing et al. (2015) Simon Loesing, Markus Pilman, Thomas Etter, and Donald Kossmann. 2015.  On the Design and Scalability of Distributed Shared-Data Databases. In _Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data_ (Melbourne, Victoria, Australia) _(SIGMOD ’15)_. Association for Computing Machinery, New York, NY, USA, 663–676.  https://doi.org/10.1145/2723372.2751519
  * Lu et al. (2016) Lanyue Lu, Thanumalayan Sankaranarayana Pillai, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau. 2016.  WiscKey: Separating Keys from Values in SSD-conscious Storage. In _14th USENIX Conference on File and Storage Technologies (FAST 16)_. USENIX Association, Santa Clara, CA, 133–148.  https://www.usenix.org/conference/fast16/technical-sessions/presentation/lu
  * Luo and Carey (2019) Chen Luo and Michael J. Carey. 2019.  On Performance Stability in LSM-Based Storage Systems.  _Proc. VLDB Endow._ 13, 4 (Dec. 2019), 449–462.  https://doi.org/10.14778/3372716.3372719
  * Luo and Carey (2020a) Chen Luo and Michael J. Carey. 2020a.  Breaking down Memory Walls: Adaptive Memory Management in LSM-Based Storage Systems.  _Proc. VLDB Endow._ 14, 3 (Nov. 2020), 241–254.
  * Luo and Carey (2020b) Chen Luo and Michael J. Carey. 2020b.  LSM-based Storage Techniques: A Survey.  _The VLDB Journal_ 29, 1 (2020), 393–418.  https://doi.org/10.1007/s00778-019-00555-y
  * Matsunobu et al. (2020) Yoshinori Matsunobu, Siying Dong, and Herman Lee. 2020\.  MyRocks: LSM-Tree Database Storage Engine Serving Facebook’s Social Graph.  _Proc. VLDB Endow._ 13, 12 (Aug. 2020), 3217–3230.  https://doi.org/10.14778/3415478.3415546
  * memcached contributors (2020) memcached contributors. 2020\.  _memcached_.  https://memcached.org
  * Microsoft (2020) Microsoft. 2020\.  _High performance computing VM sizes_.  https://docs.microsoft.com/en-us/azure/virtual-machines/sizes-hpc
  * Mittal and Nawab (2021) Natasha Mittal and Faisal Nawab. 2021.  CooLSM: Distributed and Cooperative Indexing Across Edge and Cloud Machines. In _2021 IEEE 37th International Conference on Data Engineering (ICDE)_.
  * Mitzenmacher (2001) Michael Mitzenmacher. 2001\.  The Power of Two Choices in Randomized Load Balancing.  _IEEE Trans. Parallel Distrib. Syst._ 12, 10 (Oct. 2001), 1094–1104.  https://doi.org/10.1109/71.963420
  * Patterson et al. (1988) D. Patterson, G. Gibson, and R. Katz. 1988.  A Case for Redundant Arrays of Inexpensive Disks (RAID). In _Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data_ (Chicago, Illinois, USA) _(SIGMOD ’88)_. Association for Computing Machinery, New York, NY, USA, 109–116.
  * Pham (2020) Hieu Pham. 2020\.  _Remote Compactions in RocksDB-Cloud_.  Rockset.  https://rockset.com/blog/remote-compactions-in-rocksdb-cloud/
  * Prabhu (2014) Raghavendra Prabhu. 2014\.  _Zen: Pinterest’s Graph Storage Service_.  http://bit.ly/2ft4YDx
  * Raju et al. (2017) Pandian Raju, Rohan Kadekodi, Vijay Chidambaram, and Ittai Abraham. 2017.  PebblesDB: Building Key-Value Stores Using Fragmented Log-Structured Merge Trees. In _Proceedings of the 26th Symposium on Operating Systems Principles_ (Shanghai, China) _(SOSP ’17)_. Association for Computing Machinery, New York, NY, USA, 497–514.  https://doi.org/10.1145/3132747.3132765
  * Sears and Ramakrishnan (2012) Russell Sears and Raghu Ramakrishnan. 2012.  BLSM: A General Purpose Log Structured Merge Tree. In _Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data_ (Scottsdale, Arizona, USA) _(SIGMOD ’12)_. Association for Computing Machinery, New York, NY, USA, 217–228.  https://doi.org/10.1145/2213836.2213862
  * Serafini et al. (2014) Marco Serafini, Essam Mansour, Ashraf Aboulnaga, Kenneth Salem, Taha Rafiq, and Umar Farooq Minhas. 2014.  Accordion: Elastic Scalability for Database Systems Supporting Distributed Transactions.  _Proc. VLDB Endow._ 7, 12 (Aug. 2014), 1035–1046.  https://doi.org/10.14778/2732977.2732979
  * Services (2020) Amazon Web Services. 2020\.  _Amazon EC2 Instance Types_.  https://aws.amazon.com/ec2/instance-types
  * Shan et al. (2018) Yizhou Shan, Yutong Huang, Yilun Chen, and Yiying Zhang. 2018\.  LegoOS: A Disseminated, Distributed OS for Hardware Resource Disaggregation. In _13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18)_. USENIX Association, Carlsbad, CA, 69–87.  https://www.usenix.org/conference/osdi18/presentation/shan
  * Sharma (2020) Arun Sharma. 2020\.  _Dragon: A Distributed Graph Query Engine_.  Facebook.  https://engineering.fb.com/data-infrastructure/dragon-a-distributed-graph-query-engine/
  * Snyder (1990) Peter Snyder. 1990\.  tmpfs: A Virtual Memory File System. In _Proceedings of the Autumn 1990 European UNIX Users’ Group Conference_ (Nice, France). 241–248.  https://wiki.deimos.fr/images/1/1e/Solaris_tmpfs.pdf
  * Srinivasan and Saab (2020) Mohan Srinivasan and Paul Saab. 2020.  _Flashcache: A General Purpose, Write-back Block Cache for Linux._ Facebook.  https://github.com/facebookarchive/flashcache
  * Stonebraker (1986) Michael Stonebraker. 1986\.  The Case for Shared Nothing.  _IEEE Database Eng. Bull._ 9, 1 (1986), 4–9.  http://sites.computer.org/debull/86MAR-CD.pdf
  * Taleb et al. (2018) Yacine Taleb, Ryan Stutsman, Gabriel Antoniu, and Toni Cortes. 2018.  Tailwind: Fast and Atomic RDMA-based Replication. In _2018 USENIX Annual Technical Conference (USENIX ATC 18)_. USENIX Association, Boston, MA, 851–863.  https://www.usenix.org/conference/atc18/presentation/taleb
  * Tarantool (2020) Tarantool. 2020\.  _Storing Data with Vinyl_.  https://www.tarantool.io/en/doc/2.5/book/box/engines/#garbage-collection-control
  * Trushkowsky et al. (2011) Beth Trushkowsky, Peter Bodík, Armando Fox, Michael J. Franklin, Michael I. Jordan, and David A. Patterson. 2011.  The SCADS Director: Scaling a Distributed Storage System under Stringent Performance Requirements. In _Proceedings of the 9th USENIX Conference on File and Stroage Technologies_ (San Jose, California) _(FAST’11)_. USENIX Association, USA, 12.
  * Verbitski et al. (2017) Alexandre Verbitski, Anurag Gupta, Debanjan Saha, Murali Brahmadesam, Kamal Gupta, Raman Mittal, Sailesh Krishnamurthy, Sandor Maurice, Tengiz Kharatishvili, and Xiaofeng Bao. 2017.  Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases. In _Proceedings of the 2017 ACM International Conference on Management of Data_ (Chicago, Illinois, USA) _(SIGMOD ’17)_. ACM, New York, NY, USA, 1041–1052.  https://doi.org/10.1145/3035918.3056101
  * Wang et al. (2012) Andrew Wang, Shivaram Venkataraman, Sara Alspaugh, Randy Katz, and Ion Stoica. 2012.  Cake: Enabling High-Level SLOs on Shared Storage Systems. In _Proceedings of the Third ACM Symposium on Cloud Computing_ (San Jose, California) _(SoCC ’12)_. Association for Computing Machinery, New York, NY, USA, Article 14, 14 pages.  https://doi.org/10.1145/2391229.2391243
  * Wei et al. (2018) Xingda Wei, Zhiyuan Dong, Rong Chen, and Haibo Chen. 2018\.  Deconstructing RDMA-enabled Distributed Transactions: Hybrid is Better!. In _13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18)_. USENIX Association, Carlsbad, CA, 233–251.  https://www.usenix.org/conference/osdi18/presentation/wei
  * Wu et al. (2020) Fenggang Wu, Ming-Hong Yang, Baoquan Zhang, and David H.C. Du. 2020.  AC-Key: Adaptive Caching for LSM-based Key-Value Stores. In _2020 USENIX Annual Technical Conference (USENIX ATC 20)_. USENIX Association, 603–615.  https://www.usenix.org/conference/atc20/presentation/wu-fenggang
  * Xu et al. (2016) Shuotao Xu, Sungjin Lee, Sang-Woo Jun, Ming Liu, Jamey Hicks, and Arvind. 2016\.  Bluecache: A Scalable Distributed Flash-based Key-value Store.  _Proc. VLDB Endow._ 10, 4 (Nov. 2016), 301–312.  https://doi.org/10.14778/3025111.3025113
  * Yahoo! (2015) Yahoo! 2015.  _HBase Operations in a Flurry_.  http://bit.ly/2yaTfoP
  * Yang et al. (2019) Jian Yang, Joseph Izraelevitz, and Steven Swanson. 2019\.  Orion: A Distributed File System for Non-Volatile Main Memory and RDMA-Capable Networks. In _17th USENIX Conference on File and Storage Technologies (FAST 19)_. USENIX Association, Boston, MA, 221–234.  https://www.usenix.org/conference/fast19/presentation/yang
  * Yang et al. (2020) Jiacheng Yang, Ian Rae, Jun Xu, Jeff Shute, Zhan Yuan, Kelvin Lau, Qiang Zeng, Xi Zhao, Jun Ma, Ziyang Chen, Yuan Gao, Qilin Dong, Junxiong Zhou, Jeremy Wood, Goetz Graefe, Jeff Naughton, and John Cieslewicz. 2020.  F1 Lightning: HTAP as a Service.  _Proc. VLDB Endow._ 13, 12 (Aug. 2020), 3313–3325.  https://doi.org/10.14778/3415478.3415553
  * Yao et al. (2020) Ting Yao, Yiwen Zhang, Jiguang Wan, Qiu Cui, Liu Tang, Hong Jiang, Changsheng Xie, and Xubin He. 2020\.  MatrixKV: Reducing Write Stalls and Write Amplification in LSM-tree Based KV Stores with Matrix Container in NVM. In _2020 USENIX Annual Technical Conference (USENIX ATC 20)_. USENIX Association, 17–31.  https://www.usenix.org/conference/atc20/presentation/yao
  * Zamanian et al. (2019) Erfan Zamanian, Xiangyao Yu, Michael Stonebraker, and Tim Kraska. 2019.  Rethinking Database High Availability with RDMA Networks.  _Proc. VLDB Endow._ 12, 11 (July 2019), 1637–1650.  https://doi.org/10.14778/3342263.3342639
  * Zhu et al. (2019) Tao Zhu, Zhuoyue Zhao, Feifei Li, Weining Qian, Aoying Zhou, Dong Xie, Ryan Stutsman, Haining Li, and Huiqi Hu. 2019.  SolarDB: Toward a Shared-Everything Database on Distributed Log-Structured Storage.  _ACM Trans. Storage_ 15, 2, Article 11 (June 2019), 26 pages.  https://doi.org/10.1145/3318158