# Converting Concurrent Range Index Structure to Range Index Structure for Disaggregated Memory
## 3 Method
### Case Study: RF-tree
#### 3.3.3 Read Operation  
The Read operation in the range index structure is important as every index operation should traverse the tree and do its own work. The Read operation is composed of a _Non-Blocking Read_ operation in the search layer and an optimistic Read operation in the data layer.  
**Search Layer Cache in the Compute Server.** Since the one-sided verbs have relatively higher latency than local memory access, exploiting the local memory cache in the compute server is essential. In the compute server, a client reads the search layer from the memory servers and reconstructs the search layer in the _Search Layer Cache_ (SLC). The search layer is shared with multiple threads in the same server. RF-tree uses the version-based concurrency control mechanism, similar to the previous studies [4; 9; 10].  
**Non-Blocking Read in the Search Layer.** RF-tree provides a Non-Blocking Read in the search layer to provide high performance. To find the target data node, the client should traverse the search layer. The client reads the search layer from the memory servers using the RDMA Read operation when the compute server's SLC is empty. Since the client copies the search layer without blocking, some internal nodes experience an inconsistent state. To tolerate the inconsistent states of some internal nodes, RF-tree leverages the x86 atomic primitives that can guarantee that 8-byte write is atomic [8; 10; 21; 22]. Moreover, RDMA Write guarantees the order that follows the order of the memory address. RF-tree's Read operation considers the RDMA Write operation's ordering to tolerate the transient inconsistencies, as shown in the following cases.  
* _Case 1: Inconsistent Search Layer._ When the internal nodes are inconsistent, the internal nodes may shift the key-value pairs. For the Write operation, RF-tree shifts the pointer first and then the key. Figure 4 shows an example of an inconsistent search layer. When the client finds a proper key, it first checks whether the pointer value of the key is duplicated. If it is, then it returns the pointer value of the node to the right before the key. If it is not, it returns the pointer of the key, similar to the previous study [8]. The child node may have lower keys and does not have the target key. However, the client tolerates the transient inconsistencies by traversing the child nodes.
* _Case 2: Stale SLC._ Since the search layer is stored in the memory server and cached in the local cache of the compute server, the SLC may be stale. RF-tree can endure the stale SLC by traversing the data layer using the _sibling pointer_ of the data node, as shown in Figure 5. However, traversing the data layer incurs additional expensive _RDMA Read_ operations. Thus, RF-tree updates the SLC when the client traverses more than the threshold. The SLC update is performed using the COW (_Copy-On-Write_). The client reads the SLC from the memory server to another memory space and then updates the pointer of the SLC to the new one.  
**Read in the Data Node.** RF-tree reads the data node from the memory server using an optimistic locking protocol. Since there can be an inconsistent state in the leaf node, RF-tree checks the checksum after reading the data node. When the checksum value is not the same, RF-tree reads the data node from the remote memory server again. Note that the data nodes are not cached in the compute server's SLC. RF-tree always reads the data node from the memory server and stores it in the thread's local buffer. This is because the data node keeps the pointer to the data, so RF-tree needs a consistent and latest version of the data node.  
**Range Query.** In the range query operation, the client traverses the search layer in the SLC and finds the pointers of data nodes, which have the keys to the result of the given range query. Note that the range query of RF-tree has low-level isolation as RF-tree does not keep the locks for the data nodes for the range query.