# Converting Concurrent Range Index Structure to Range Index Structure for Disaggregated Memory
## 3 Method
### Converting Concurrent Range Index Structure for Disaggregated Memory  
**Log-Structured Search Layer Region. ** In order to make the search layer RDMA-friendly, the search layer should be accessed with minimal RDMA Read operations. To do this, the internal nodes in the search layer are in consecutive memory space. In the memory server, the memory space is divided into two regions: the _search layer region_ and the _data layer region_. The internal nodes are stored in the search layer region. The data node (i.e., leaf node) is stored in the data layer region. Storing the search layer in consecutive memory space is simple and straightforward. Basically, the internal nodes are allocated sequentially in the search layer region, similar to that of log-structured memory management [13; 14]. Figure 2: Tolerating Transient inconsistency in the concurrent range index structures. (**a**) Blink-tree: Example of lookup operation of key 80. When the node split occurs, the reader can tolerate the transient inconsistency by traversing the sibling node. (**b**) SkipList: Example of lookup operation of key 25. The reader can tolerate transient inconsistency by traversing the lower level when the key is added to the upper level. Load Balancing.The disaggregated memory consists of memory servers connected via RDMA one-sided verbs. Hence, if the loads between the memory servers are unbalanced, the memory servers could become the performance bottleneck. As a result, the data should be distributed among the memory servers uniformly. However, as shown in a previous study [6], fine-grained node distribution can incur additional RDMA Read operations, which cancels out the benefit of the balanced load. Fortunately, the log-structure search layer region helps reduce the number of RDMA Read operations even when the nodes are distributed in a fine-grained manner. This is because the log-structured design enables reading the search layer as a large-sized chunk. Thus, in our Spread approach, each node is stored in the memory server randomly. Higher Consistency Guarantee.Since the disaggregated memory is the remote memory, there can be a high possibility of transient inconsistencies between servers and clients. Previous studies [7; 15] exploit a characteristic of _RDMA Writes_, which transfer data in the order of memory address. However, a recent study [16] shows that the _RDMA Read_ operation can still suffer from transient inconsistencies due to the concurrent multiple cache line retrievals. Hence, an additional consistency-guarantee mechanism is still required. There are several existing approaches, such as checksum [3; 4; 17; 18] and versioning for each cache line [6; 19]. These consistency-guarantee mechanisms improve consistency but incur additional overheads, such as computation and memory accesses. In our Spread approach, we add a CRC (Cyclic Redundancy Check) value as a checksum for each node to guarantee the consistency of the node. Efficient Usage of Local Cache.As RDMA-based disaggregated memory still suffers from the high performance overhead from RDMA's relatively high latency, it is important to reduce the number of RDMA operations. In that sense, leveraging the compute server's local memory cache is a fundamental solution. Previous works [2; 6] already have exploited the local cache. In a compute server, there can be multiple clients based on threads. These threads share the same local cache in the compute server, so the cached range index structure should support concurrent access. Originally, the concurrent range index structures were designed for multi-core scalability in the same machine. Thus, we can leverage the concurrency control of the range index structure. Concurrency Control.The concurrency control protocol exploits atomic instructions to guarantee mutual exclusion in the critical section. The index structure can simply replace the atomic instructions, such as _Compare_And_Swap_ (CAS) and _Fetch_And_Add_ (FAA), with RDMA atomic operations (i.e., RDMA CAS or RDMA FAA) [20].