# Converting Concurrent Range Index Structure to Range Index Structure for Disaggregated Memory
## 1 Introduction  
In the memory-driven computing era, the demand for memory is increasing as memory provides high performance to the software. However, the cost of memory is still high, and the memory utilization of servers in the data center is still low. Disaggregated memory is rising as a promising solution to fulfill the increasing demand for memory. Disaggregated memory separates computing and memory in data centers, and it manages the resources as connected computing and memory pools, respectively. The primary virtue of separating computing and memory pools lies in that it enables elastic resource management and reduces the TCO (Total Cost of Ownership) [1]. In-memory storage systems, such as in-memory database systems or an in-memory cache, can be major use cases of disaggregated memory as they require low-latency access to a large amount of physical memory. However, simply exploiting the disaggregated memory cannot fully utilize the architecture's potential. To fully take advantage of disaggregated memory, the index structures, which are the primary data structures of in-memory storage systems, should be changed by considering the characteristics of disaggregated memory. For instance, disaggregated memory requires a high-performance interconnect network to provide low latency to support the memory pool. Most previous research for disaggregated memory [2, 3, 4] depends on RDMA (_Remote Direct Memory Access_) as RDMA provides high-performance and direct access to the memory in the remote server. To directly access the remote memory using RDMA, RDMA one-sided verbs such as RDMA Read/Write/Atomic operations are used because they are memory semantics. RDMA one-sided verbs provide high performance by allowing a memory operation to be executed without the remote host's active involvement. Although RDMA one-sided verbs provide high performance, they still incur high overhead. This is because the latencies of RDMA one-sided verbs are relatively higher than local memory accesses. Previous studies [3, 5] mainly exploit simple hash table-based storage systems because it is challenging to support complicated index operations using RDMA one-sided verbs. There have been a few research efforts for designing range index structures that leverage RDMA one-sided verbs [2, 6]. They explore the design of range index structures on disaggregated memory. The first range index structure to use RDMA one-sided verbs is called FG [6], a distributed Blink-tree that distributes the node among the memory servers in a fine-grained manner. However, it suffers a high overhead from the frequent RDMA one-sided verb calls. Sherman [2] is a state-of-the-art range index structure that uses RDMA one-sided verbs. Sherman leverages the compute server's local DRAM as a local cache. It also exploits the on-chip memory of NIC to reduce the overhead of atomic operations in the RDMA's one-sided verbs. However, these engineering efforts require a deep understanding of RDMA. While recent studies require a steep learning curve for RDMA, we revisited their approaches and observed that they leverage RDMA write operation (i.e., one-sided verb), providing a strong ordering guarantee [2, 7]. This strong ordering guarantee shows similar characteristics to the ordering guarantee of the memory operation in recent concurrent range index structures [8]. In recent concurrent range index structures, the readers can tolerate inconsistent transient states during index update operations by other writers. These inconsistent transient states are called _Transient Inconsistency_. Moreover, other recent studies [9, 10] show that separating the search layer (the internal nodes) and the data layer (the data nodes) in a concurrent range index structure can improve scalability and performance. This structure also can take advantage of disaggregated memory, which is an emerging architecture in a distributed memory system. Hence, in this work, we propose a new approach, called Spread, to convert a concurrent range index structure into a range index structure for disaggregated memory.