Designing an Efficient Tree Index on Disaggregated Memory

Approach #1: Using one-sided verbs purely.  FG,²⁵ an RDMA-based $B^{+}\mathrm{Tree}$, completely leverages one-sided verbs to perform index write operations (so it can be deployed on disaggregated memory). For write operations, it adopts a lock-based approach, where tree node modification is protected by RDMA-based spinning locks (RDMA_CAS for acquisition and RDMA_FAA for release). For read operation, FG follows a lock-free search scheme, where threads fetch tree nodes via RDMA_READ without holding locks and then check the consistency using checksum. We conduct an experiment to evaluate FG’s performance. Since FG is not open source, we implement it from scratch; we also cache internal tree nodes to reduce remote accesses. Table 1 shows the result, and we make two observations. First, in read-intensive workload (95% lookup and 5% insert/update), FG can achieve high throughput (> 30Mops) and low 99^th percentile latency (< 16$\mu$s). Second, in write-intensive workload (50% lookup and 50% insert/update), FG delivers 18Mops with 19$\mu$s tail latency under the uniform setting; yet, its performance collapses in case of skew setting, where the key popularity follows a Zipfian popularity with skewness 0.99: Throughput is only 0.34Mops and tail latency is close to 20ms.

Approach #2: Extending RDMA interfaces.  Another approach to designing indexes on disaggregated memory is extending RDMA interfaces. This approach offloads index write operations into memory servers’ NICs via SmartNICs or other customized hardware.^1,16 For example, by exploiting interface extensions (that is, indirect addressing and notification), researchers propose HT-Tree (without implementation),¹ a hybrid index combining the hash table and tree. Yet, compared with commodity RDMA NICs, SmartNICs come at the price of higher TCO and lower performance. More specifically, SmartNICs have much higher market price ($\sim$5$\times$) than that of commodity RDMA NICs at present.¹⁸ As for performance, at 100Gbps network environment, StRoM,¹⁶ the state-of-the-art RDMA extensions using FPGA, has 2$\times$ higher round-trip latency (4$\mu$s) against commodity RDMA NICs ($\sim$2$\mu$s).

B+Tree structure.  Sherman is a $B^{+}\mathrm{Tree}$, where values are stored in leaf nodes. We record a sibling pointer for every leaf node and internal node as in the B-link tree. Client threads can always reach a targeted node by following these sibling pointers in the presence of node split/merging, thus supporting concurrent operations efficiently. Every pointer in Sherman (that is, child/sibling pointers) is 64bit, which includes two parts: 16bit MS unique identifier and 48bit memory address within corresponding MS.

Concurrency control.  Sherman adopts lock-based write operations and lock-free read operations.

Write-write conflicts. Sherman uses node-grained exclusive locks to resolve write-write conflicts: Before modifying a tree node, the client thread must acquire the associated exclusive lock. These exclusive locks are hierarchical: local lock tables at CS-side and global lock tables in on-chip memory of MSs’ NICs (§4.3). Such a hierarchical structure provides high concurrency performance.

Read-write conflicts. Sherman supports lock-free search, which leverages RDMA_READ to fetch data residing in MSs without holding any lock. Moreover, Sherman uses versions to detect inconsistent data caused by concurrent writes. However, different from traditional mechanisms that use node-level versions, Sherman proposes a two-level version mechanism, which combines entry-level and node-level versions, to mitigate write amplification (§4.4).

Cache mechanism.  To reduce remote accesses in the tree traversal, Sherman adopts a cache mechanism. Each CS maintains an index cache, which only makes two types of internal nodes’ copies: nodes above the leaf nodes (level 1 in Figure 3), and the highest two levels of nodes (including root). A client thread firstly searches type cache. On hit, it fetches the targeted leaf node directly from MSs; otherwise, it searches type cache and then traverses to leaf nodes via remote accesses. The index cache never induces data inconsistency issues; detailed reasons are available in our original SIGMOD paper.²⁰

Memory management.  In each MS, we reserve a dedicated memory thread to manage disaggregated memory. The memory thread divides memory residing in corresponding MS into fixed-length chunks (that is, 8MB). Client threads use a two-stage memory allocation scheme to obtain memory from MSs. A client thread first chooses an MS in a round-robin manner, and requests a free chunk from the MS’s memory thread via RPCs. Then, it allocates memory space for tree nodes locally within the chunk.

On-chip lock table.  Current RDMA verbs support device memory programming. Specifically, an RDMA NIC can expose a piece of its on-chip memory (SRAM) to the upper applications, which can be allocated and read/written by RDMA commands. The on-chip memory eliminates PCIe transaction at the receiver side, thus providing extremely high throughput $\sim$110Mops RDMA_CAS). Sherman separates locks from tree nodes and stores locks into on-chip memory at MS side; each tree node is in the same MS as the lock protecting it. These locks in each MS are structured as an array, namely global lock table (GLT). When locking a tree node, the client thread first hashes the address of the tree node into a position number in the associated GLT and then issues an RDMA_CAS command to the lock, which tries to change it from 0 to the 16bit CS identifier atomically. For lock release, the thread clears the lock via an RDMA_WRITE.

An important consideration of GLT is the on-chip memory size. In the NIC we use (ConnectX-5), 256kB on-chip memory is available. To accommodate more locks, we make the granularity of RDMA_CAS finer (16bit rather than 64bit), by applying an infrequently used RDMA verb called masked compare and swap, which allows us to select a portion of 64bit for RDMA_CAS. Thus, an MS can maintain 131,072 locks in its GLT, enabling extremely high concurrency, particularly considering that we only lock at most one tree node at a time for a single write operation. To the best of our knowledge, Sherman is the first RDMA-based system that leverages on-chip memory of RDMA NICs.

Hierarchical structure.  Sherman maintains a local lock table (LLT) in each CS to coordinate conflicting lock requests within the same CSs. The LLT stores a local lock for each lock of all GLTs. When a thread needs to lock a tree node, it first acquires the associated local lock in LLT, and then acquires the associated lock in GLT; thus, conflicting lock requests from the same CSs are queued on the LLT at CS side, avoiding unnecessary remote retries and thus saving RDMA IOPS. Moreover, each local lock in LLT is associated with a wait queue. A thread that cannot acquire a local lock in LLT pushes itself into the corresponding queue; the thread can learn if its turn has arrived by checking whether it is at the head of the queue. The queue provides first-come first-served fairness among threads within the same CSs. For lock release, the thread first releases the lock in GLT and then the local lock in LLT.

Handover mechanism.  The hierarchical structure of HOCL enables a handover mechanism: handing over a lock from one client thread to another. When releasing a lock, if a thread finds out the lock’s wait queue is not empty, it will hand the lock over to the one at the head of the wait queue. To avoid starving threads at other CSs, we limit the maximum number of consecutive handovers to four. The thread that is handed over a lock no longer needs remote accesses for acquiring the lock, thus saving at least one round trip.

Lookup operation.  Two-level version mechanism makes the lookup operation different from the standard one. After reading a leaf node from MSs, a client thread compares the two node-level versions first; mismatched versions indicate the read must be retried. Then, the client thread locates the targeted entry and compares the two associated entry-level versions; if the comparison fails, the client thread needs to re-read the leaf node via RDMA_READ. Wraparounds of these 4bit versions may cause inconsistency to be undetected: two versions match but one wraps around. To handle wraparounds, we measure the time of each RDMA_READ command: If it takes more than 8$\mu$s (that is, $2^4\times 0.5$, where $0.5\mu s\ll$ the time of a single write operation), a retry is needed.

Range query.  For a range query, the client thread issues multiple RDMA_READ in parallel to fetch targeted leaf nodes, and then checks leaf nodes’ consistency in the same way as the lookup operation. Of note, Sherman does not guarantee that a range query is atomic with concurrent write operations. If upper applications (for example, a transaction engine) need snapshot semantics for range queries, they must use other mechanisms to avoid phantom problems.

Discussion.  Our two-level version mechanism assumes that an RDMA_READ is performed in increasing address order. However, a recent work²⁴ shows that this assumption does not always hold true: for 512B data blocks, 0.396% RDMA_READ operations are executed in an out-of-order manner. This means that the two-level version mechanism may induce data inconsistency in some cases of concurrent access. We have fixed the issue in our recent work.¹⁹

Compared systems.  FG²⁵ is a $B^{+}\mathrm{Tree}$ that supports disaggregated memory. Since FG is not open source, we implement it from scratch. For fair comparison, we add necessary optimizations to it: (i) index cache for reducing remote accesses, (ii) using RDMA_WRITE to release lock rather than expensive atomic verb RDMA_FAA. To distinguish our modified version of FG from the original one, we call it FG+ in the evaluation. The performance of FG+ is higher than that reported in FG paper.²⁵

Workloads.  We explore different aspects of the systems by using YCSB workloads.³ We use five types of read-write ratio, as shown in Table 2. Note that insert operations include updating existing keys (about 2/3 of all insert operations). There are two types of key popularity: uniform and skewed. In uniform workloads, all keys have the same probability of being accessed. Skewed workloads follow a Zipfian access distribution (Zipfian parameter, that is., skewness, is 0.99 by default), which is common in production environments.³ Unless otherwise stated, all the experiments are conducted with eight MSs and eight CSs. Each CS owns 500MB index cache, and launches 22 client threads (176 in total in our cluster). For each experiment, we bulkload the tree with one billion entries (8byte key, 8byte value) 80% full, then perform specified workloads. The size of a tree node (that is, internal node and leaf node) is 1KB.