# Improving Performance of Key-Value Stores for High-Performance Storage Devices
## 4 Design and Implementation
### Implementation  
We implement the proposed scheme in RocksDB version 5.13. To enable foreground idle threads to participate in background I/O operations, we introduce a global data structure called ReadQueue. Algorithm 2 represents the pseudocode for the process in which multiple threads add or remove information about files that need to be read into the ReadQueue, facilitating concurrent I/O operations. One of the background jobs, the compaction job, adds information about files requiring read I/O operations (lines 1-7). The main procedure of the compaction job is performed in the function ProcessKeyValueCompaction(), which begins by identifying compaction target files that need to be read from storage devices (line 2). Since all files stored on the storage devices are sorted, the target files are read sequentially to merge and re-sort valid data. In other words, while all target files for com  
Figure 3: Overall design of the existing and proposed schemes.  
paction must eventually be read, they are not read all at once. For instance, if six files with file numbers 1 through 6 are selected as compaction targets, the process begins with file number 1. Files 2 and 3, which store overlapping key ranges, should be read first, but the read operations for files 4, 5, and 6 are delayed until the merge and re-sorting operations for the preceding key ranges are completed. The proposed scheme manages information about files that must eventually be read in the global queue, allowing idle threads to perform I/O operations in advance, which must be performed eventually.  
```
1:procedureProcessKeyValueCompaction()
2://find compaction target files
3:if file is target range then
4:AddFileToReadQueue()
5:endif
6://existing works for compaction \(\triangleright\)Do the original jobs
7:endprocedure
8:procedureDelayWrite()
9:PrefetchQueueData()
10:ifwrite_controler_ISStopped()or_NeedsDelay()then
11:Wait()
12:endif
13:endprocedure
14:procedurePrefetchQueueData()
15:ifqueue.IsEmpty()then
16:return\(\triangleright\)nothing to do
17:else
18:SelectFileToPrefetch()\(\triangleright\)protected by a lock
19:AllocateBuffer()
20:Read()
21:RemoveFileFromReadQueue()
22:endif
23:endprocedure
```  
**Algorithm 2** Pseudocode for the proposed scheme.  
As shown in Algorithm 1 (lines 6-7, 14-15), all threads allocated for foreground I/O operations are stalled and wait for the background jobs to complete. In the proposed scheme, before the threads allocated to foreground I/O operations enter a waiting state, they first check the global queue to see if there are any files requiring read I/O for background jobs (lines 9, 14-23). In the PrefetchQueueData() function, we first check whether the global queue is empty. If the queue is empty, it indicates that other threads have already read the target files and there is no remaining work. In this case, since no additional work is needed, the function returns, and the thread checks again to determine whether waiting is still necessary (lines 10-11). If the queue is not empty, a file is selected from the global queue for reading (lines 17-22). At this point, to avoid duplicate read operations by multiple threads, a thread acquires a lock, reads the file information, and updates the status of the file to indicate that the read operation is in progress. After selecting a file, the thread allocates space in the read buffer so that the file can be preloaded, and the data contained in the file are read into memory. Once the read operations are complete, the status is updated, and the file information is removed from the global queue to prevent duplication I/O operations.  
Our implementation is available as open-source software at [[https://github.com/hkim-snu/rocksdb-parallel.git](https://github.com/hkim-snu/rocksdb-parallel.git)]([https://github.com/hkim-snu/rocksdb-parallel.git](https://github.com/hkim-snu/rocksdb-parallel.git)) (accessed on 16 July 2024).