# Improving Performance of Key-Value Stores for High-Performance Storage Devices
## 3 Background and Motivation
### Existing I/O Path Analysis of RocksDB  
As RocksDB is a widely used KV store, it is important to fully understand its I/O path and examine how the KV stores are implemented to support high performance and data robustness.  
Figure 1 illustrates the existing architecture of RocksDB. Incoming insert operations store key-value pairs in the in-memory write buffer, known as the memtable. When the memtable becomes immutable due to accumulating sufficient key-value pairs, background job--specifically, the flush operation--stores the immutable memtable as a level 0 file in persistent storage. RocksDB organizes these files, which store key-value pairs, into multiple levels based on data access recency. Since duplicate keys are not allowed within a certain level and key-value pairs are stored in order within each level, the compaction job continuously performs read and write operations to manage the number of files at each level. This process ensures that the number of files remains constant at each level, thereby maintaining the desired characteristics of the KV store across all levels.  
Algorithm 1 presents a pseudocode representation of the existing I/O path in RocksDB during an insert operation.  
```
1:procedureDoWrite()
2:ifwrite_thread_isLeaderthen
3:mutex_Lock
4:PreprocessWrite()
5:ifwrite_controller_ISStopped()or_NeedsDelay()then
6:DelayWrite()
7:Wait()
8:endif
9:mutex_Unlock
10:WriteWAL()
11:SyncWAL()
12:Signal()
13:else
14:DelayWrite()
15:Wait()
16:endif
17:LaunchParallelMemTableWriters()
18:endprocedure
```  
**Algorithm 1** Existing I/O path pseudocode  
As shown, RocksDB initiates the insert operation with the DoWrite() function. In this function, the first thread to arrive is selected as the leader thread (lines 2-12). The leader thread acquires a lock and performs preprocessing operations (PreprocessWrite()) to handle the write operation (lines 3-9). It then checks the write controller to determine  
Figure 1: RocksDB architecture [7; 29].  
whether the write operation can proceed, taking into account the status of background operations (line 5). For example, if the flush operation is too slow and there is not enough mentable for inserting new key-value pairs, the leader thread waits for the flush job to complete, allowing the memtable to become available. Another background job, the compaction job, also causes stalls in foreground operations. As new key-value pairs continue to arrive, the compaction job is executed to keep the number of files in level 0 below a certain threshold, which may cause the leader thread to wait until space becomes available in level 0. In other words, if the system is in a state where new key-value pairs cannot be inserted due to ongoing background I/O operations, the operations of the leader thread are stalled (lines 5-8). In summary, the overall progress of the foreground insert operation is heavily dependent on the performance of background jobs. If progress is possible, the leader thread proceeds with foreground I/O operations, such as writing to the write-ahead log and flushing the key-value pairs in the memtable to the non-volatile storage device (lines 10-12).  
In contrast, threads that are not selected as the leader thread are stalled, waiting for the leader thread's operations to complete. This means that, despite the availability of a large number of threads --a trend that is increasing with the growth of CPU cores --only a single thread is responsible for executing the actual I/O operations. This limitation not only reduces the efficiency of I/O operations but also hampers the overall progress of insert operations within the KV store. The insert operation is delayed until sufficient space is available to temporarily store the key-value pairs. This clearly indicates that the current implementation of RocksDB is not optimized for multi-core CPUs and high-performance storage devices.