PaperlayerView exact revision on arXiv

Source-linked AI summary

Sherman: A Write-Optimized Distributed B+Tree Index on Disaggregated Memory

Qing Wang, Youyou Lu, Jiwu Shu

arXiv:2112.07320v2cs.DCcs.DBcs.NI

TL;DR

Memory disaggregation separates compute and memory, but its limited RDMA semantics and near-zero memory-side computation challenge database indexing; existing indexes have low write performance or require hardware changes. Sherman is a write-optimized distributed B+Tree that combines RDMA hardware features with RDMA-friendly software techniques. On typical write-intensive workloads, it improves throughput and 99th-percentile latency by one order of magnitude over state-of-the-art designs.

  • Problem

    Existing indexes for disaggregated memory either have low write performance or require hardware modification, despite the architecture’s limited RDMA semantics and near-zero memory-side computation.

    Source: §3.1 · p. 3

  • Method

    Sherman combines RDMA hardware features and RDMA-friendly software techniques in a write-optimized distributed B+Tree for disaggregated memory.

    Source: §1 · p. 2

  • Results

    On typical write-intensive workloads, Sherman improves throughput and 99th-percentile latency by one order of magnitude over state-of-the-art designs.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Sherman demonstrates that RDMA hardware features combined with RDMA-friendly software designs can deliver a high-performance index on disaggregated memory.

    Source: §7 · p. 13

    Sherman does not guarantee atomic range queries during concurrent writes; applications needing snapshot semantics must use other mechanisms to avoid phantom problems.

    Source: §4.4 · p. 8

Abstract

from arXiv · show

Memory disaggregation architecture physically separates CPU and memory into independent components, which are connected via high-speed RDMA networks, greatly improving resource utilization of databases. However, such an architecture poses unique challenges to data indexing in databases due to limited RDMA semantics and near-zero computation power at memory-side. Existing indexes supporting disaggregated memory either suffer from low write performance, or require hardware modification. This paper presents Sherman, a write-optimized distributed B+Tree index on disaggregated memory that delivers high performance with commodity RDMA NICs. Sherman combines RDMA hardware features and RDMA-friendly software techniques to boost index write performance from three angles. First, to reduce round trips, Sherman coalesces dependent RDMA commands by leveraging in-order delivery property of RDMA. Second, to accelerate concurrent accesses, Sherman introduces a hierarchical lock that exploits on-chip memory of RDMA NICs. Finally, to mitigate write amplification, Sherman tailors the data structure layout of B+Tree with a two-level version mechanism. Our evaluation shows that, Sherman is one order of magnitude faster in terms of both throughput and 99th percentile latency on typical write-intensive workloads, compared with state-of-the-art designs.

1 Introduction

Sherman addresses the write-performance limits of tree indexes on disaggregated memory with a write-optimized B+Tree designed for commodity RDMA NICs. It combines RDMA-aware techniques and reports order-of-magnitude gains in throughput and 99th-percentile latency on common skewed workloads.

1 Introduction

  • One-sided indexes face write-performance limits from multiple round trips, slow locks, unnecessary retries, and coarse-grained consistency checks that amplify writes.The paper also notes that RPC-based indexes are ill-suited to memory servers’ near-zero computation power, while hardware-customized approaches carry high total cost of ownership.Source: §1 · pp. 1–2
  • Sherman is a distributed B+Tree that performs index operations through RDMA one-sided verbs, combining hardware features and RDMA-friendly software techniques.It uses lock-free search with versions for read-write conflicts and exclusive locks for write-write conflicts.Source: §1 · p. 2
  • Command combination uses RDMA’s in-order delivery to issue dependent commands together, reducing round trips.For example, dependent write-back and lock-release commands can be issued simultaneously.Source: §1 · p. 2
  • HOCL pairs global lock tables on memory servers with local lock tables on compute servers to coordinate conflicts and reduce remote retries.Global tables use RDMA NIC on-chip memory; local wait queues improve fairness, and handing a lock directly to another thread saves at least one round trip.Source: §1 · p. 2
  • Sherman’s unsorted leaf entries avoid shift operations, while two-level versions support lock-free search and entry-level integrity.Without a split or merge, insertion or deletion writes back only entry-sized data, saving network bandwidth.Source: §1 · p. 2
  • On common skewed workloads, Sherman improves throughput and 99th-percentile latency by one order of magnitude over FG.For read-intensive workloads, it has slightly higher throughput and 25% lower 99th-percentile latency.Source: §1 · p. 2

2 Background

This section introduces memory disaggregation and RDMA, the architecture and network foundation for the paper’s focus on distributed B+Tree indexes.

2 Background

  • The background section covers memory disaggregation and RDMA network fundamentals.Source: §2 · p. 2

2.1 Memory Disaggregation

  • Memory disaggregation separates compute servers with many CPU cores from memory servers with high-volume memory and near-zero computation power; RDMA connects them for direct access.Compute and memory can scale independently, and applications can pack resources more flexibly.Source: §2.1 · p. 2

2.2 RDMA Network

  • RDMA one-sided verbs access remote memory without receiver CPUs; RDMA-based index research motivates the paper’s focus on distributed B+Trees [6, 21, 47, 54, 69, 81].Sherman uses reliable-connected transport, which supports all one-sided verbs and reliable communication.Source: §2.2 · p. 3

3 Motivation

The section examines why existing distributed tree indexes struggle to support writes on disaggregated memory, then identifies excessive round trips, slow synchronization, and write amplification as key bottlenecks.

3 Motivation

  • The section frames high-performance tree indexing on disaggregated memory as a challenge, motivating its review of existing approaches and analysis of one-sided writes.The analysis is organized around the limits of existing approaches and the causes of slow one-sided writes.Source: §3 · p. 3, §3.1 · p. 3

3.1 Existing Approaches

  • Existing indexes can achieve an ideal lookup with one RDMA_READ, but memory servers’ near-zero compute power rules out RPC-based index operations.The section contrasts lookup support with the difficulty of write operations.Source: §3.1 · p. 3

3.1.1 Using One-sided Verbs Purely.

  • Under 50/50 writes, FG reaches 18 Mops and 19µs tail latency uniformly, but skew 0.99 cuts throughput to 0.34 Mops with tail latency near 20ms.The paper reports that FG is the one-sided-verb tree index deployable on disaggregated memory.Source: §3.1.1 · p. 3

3.1.2 Extending RDMA Interfaces.

  • RPC-based Cell and FaRM-Tree cannot run on disaggregated memory, FG has low write performance, and HT-Tree requires hardware modification.The comparison covers distributed tree indexes that use one-sided verbs for reads.Source: §3.1.2 · p. 4, Table 2 · p. 4

3.2 Why One-sided Approach is Slow?

  • One-sided writes are inefficient for three reasons: excessive round trips, slow synchronization primitives, and write amplification.The section establishes these causes through analysis and experiments.Source: §3.2 · p. 4

3.2.1 Excessive Round Trips.

  • A node modification requires four round trips—lock, read, write, unlock—raising latency and making conflicting writes more likely to be blocked.The example excludes node splits and merges.Source: §3.2.1 · p. 4

3.2.2 Slow Synchronization Primitives.

  • Under high contention, RDMA-based locks collapse as in-NIC atomic serialization stretches queues, failed acquisitions trigger remote retries, and unfairness starves requests.The analysis attributes the performance collapse to these three issues.Source: §3.2.2 · p. 4, Figure 2 · p. 4

3.2.3 Write Amplification.

  • RDMA_WRITE throughput exceeds 50 Mops at I/O sizes up to 128 bytes, but sorted-entry shifts and node-granularity checks make small edits write larger data.The cited mechanisms include whole-node checksums and paired versions at each node’s start and end.Source: Figure 3 · p. 5, §3.2.3 · p. 5, Figure 4 · p. 5

4 Design

Sherman combines RDMA hardware features with RDMA-aware software and data layouts to improve tree-index performance. Its design targets remote round trips, lock contention, and write amplification while supporting concurrent reads and writes.

4.1 Design Principles

  • Sherman uses RDMA’s in-order delivery and NIC on-chip memory, plus compute-server-side lock coordination and tailored node layouts, to reduce round trips, accelerate locks, and limit write amplification.Its design also maintains a compute-server-side index cache to reduce remote accesses during tree traversal.Source: §4.1 · p. 5

4.2 Overview

  • The distributed B+Tree places nodes on memory servers and lets compute-server client threads perform lookup, range query, insert, and delete operations through RDMA.Sibling pointers allow clients to reach targeted nodes amid splits or merges; writes use exclusive locks, while reads use lock-free searches with versions to detect inconsistent data.Source: §4.2 · p. 5, §4.2.1 · p. 5, §4.2.2 · p. 6

4.2.3 Cache Mechanism.

  • Each compute server caches selected internal-node copies; fence-key and level checks detect invalid routes and trigger cache invalidation and retry.The cache covers nodes above leaves and the highest two tree levels; the latter are always cached, while the former use a lock-free skiplist with power-of-two-choices eviction.Source: §4.2.3 · p. 6

4.3 Hierarchical On-Chip Lock

  • HOCL combines NIC-resident global lock tables with compute-server local lock tables, using local queues to avoid unnecessary remote retries and provide first-come-first-served fairness.The handover mechanism can pass a released lock to a waiting thread in the same compute server, saving a round trip; handovers are limited to four consecutively to avoid starving other compute servers.Source: §4.3 · p. 7

4.4 Two-Level Version

  • Unsorted leaf entries avoid shifts during insertion and deletion, while entry-level and node-level versions protect fine-grained updates and whole-node changes, respectively.Without a split or merge, only the modified entry is written back; lookups check node versions and then the targeted entry’s versions, retrying on inconsistency or a potentially missed 4-bit-version wraparound.Source: §4.4 · pp. 7–8

4.5 Command Combination

  • Sherman combines dependent RDMA_WRITE commands by relying on RC queue-pair in-order delivery, avoiding waits for acknowledgements between commands.It can combine a node write-back with lock release, or combine writes for a newly allocated sibling and the split node with release of the split node’s lock when both nodes are on the same memory server.Source: §4.5 · p. 8

4.6 Discussion

  • The paper states that HOCL and command combination can also benefit other lock-based indexes, while two-level versions can help indexes that use lock-free search.The discussion identifies bucket hash tables as an example for the first two techniques.Source: §4.6 · pp. 8–9

5 Evaluation

The evaluation uses an emulated disaggregated-memory cluster, compares Sherman with an optimized FG baseline, and tests multiple workload mixes and access patterns. It also examines scalability and internal performance metrics.

5 Evaluation

  • The evaluation examines workload performance, technique contributions, scalability, internal metrics, parameter effects, and HOCL performance.The stated evaluation questions cover different workloads, client-thread counts, round trips, write amplification, key and cache-index sizes, and HOCL.Source: §5 · p. 9

5.1.1 Hardware Platform.

  • Eight commodity servers with ConnectX-5 NICs emulate memory and compute servers, each split into one memory server and one compute server.Each emulated memory server has 64GB DRAM and 2 CPU cores; each compute server has 1GB DRAM and 22 CPU cores.Source: §5.1.1 · p. 9

5.1.2 Compared Systems.

  • FG is implemented from scratch as FG+, with an index cache and RDMA_WRITE lock release added for comparison; the paper reports FG+ performs better than FG’s published result.The stated workload suite uses YCSB read-write mixes, with inserts including updates to existing keys.Source: §5.1.2 · p. 9, §5.1.3 · p. 9

5.1.3 Workloads.

  • Skewed workloads use Zipfian access with skewness 0.99 by default; experiments generally use 8 memory servers, 8 compute servers, 176 client threads, and a tree bulk-loaded with 1 billion entries.Uniform workloads access all keys with equal probability; reported plots average three or more runs.Source: §5.1.3 · p. 9

5.2 Overall Performance

Under skewed write workloads, Sherman substantially outperforms FG+ in throughput and tail latency, while its component techniques contribute differently to the gains. Under uniform workloads, it also improves throughput and latency, with smaller throughput gains.

5.2.1 Skewed Workloads.

  • Against FG+, Sherman achieves 23.6× higher throughput and 1.4×/30.2× lower 50p/99p latency in write-intensive workloads; in write-only workloads, it achieves 24.7× higher throughput and 1.2× lower median latency.Source: §5.2.1 · pp. 9–10
  • Command combination improves throughput by 3.37× and reduces 50p/99p latency by 1.14×/3.18×; NIC on-chip locks improve throughput and 99p latency by 3.06× and 3.48×, respectively.The hierarchical lock structure brings 2.22× higher throughput and 1.12×/2.68× lower 50p/99p latency; two-level versions add only 3% throughput, but reduce 50p latency by 400ns, from 7.3𝜇 to 6.9𝜇.Source: §5.2.1 · p. 10
  • In read-intensive workloads, Sherman has no considerable performance improvement; command combination reduces 99p latency from 15.3𝜇s to 12.9𝜇s, while 50p latency increases by 100ns (2%).The reported explanation for the 50p increase is that unsorted leaves require traversing the entire leaf node even for non-existing keys.Source: §5.2.1 · p. 10

5.2.2 Uniform Workloads.

  • 1.15× higher throughput and 1.19×/1.27× lower 50p/99p latency: Sherman versus FG+ in uniform write-intensive workloads.For uniform write-only workloads, Sherman delivers 1.24× higher throughput and reduces 50p/99p latency by 1.24×/2.01×.Source: §5.2.2 · p. 10

5.3 Range Query Performance

Range-query results depend on range size and whether queries share the workload with writes. Sherman can lag FG+ on small range-only queries, while it leads in mixed range-write throughput.

5.3 Range Query Performance

  • FG+ outperforms Sherman by 2% at range size 100; at range size 1000, both throughputs drop and are almost the same.The paper attributes the small-range result to unnecessary scans from Sherman’s unsorted leaf layout when targeted leaves are partially occupied, and the larger-range result to network bandwidth becoming the bottleneck.Source: §5.3 · p. 10
  • Up to 1.82× higher throughput: Sherman versus FG+ under range-write workloads, with half the client threads issuing inserts and half issuing range queries.The paper attributes this to write operations using fewer network resources, including through lock handover and entry-sized RDMA_WRITE operations.Source: §5.3 · p. 11

5.4 Scalability

Sherman sustains higher throughput than FG+ as client concurrency and skew increase. Its in-depth results show fewer write round trips and smaller writebacks for operations without node splits.

5.4 Scalability

  • At 528 client threads, Sherman reaches 44 Mops, 1.14× FG+ throughput on uniform workloads; under skew, it reaches 21 Mops at 0.9 skewness and 9 Mops at 0.99, outperforming FG+ by 1.44× and 1.4×.Sherman sustains throughput as skewed-workload client threads increase, while FG+ experiences performance collapse.Source: §5.4 · p. 11

5.5.1 Retry Counts.

  • For skewed workloads at 0.99, 99.98% of lookups require no retries; FG+ sometimes retries multiple times, while Sherman’s two-level mechanism avoids the larger RDMA I/O implicated in those retries.The passage attributes most retry avoidance to PCIe transaction ordering, which orders reads after prior writes.Source: §5.5.1 · pp. 11–12

5.5.2 The Number of Round Trips.

  • 93.6% of Sherman writes need 3 round trips, versus 94% of FG+ writes needing 4; Sherman’s 99th-percentile count is 11, versus FG+’s 453.Command combination coalesces write-back and lock release; HOCL handover lets 3.6% of Sherman writes use 2 round trips.Source: §5.5.2 · p. 12

5.5.3 Write Size.

  • For writes without node splits, Sherman writes back 17 bytes using its two-level version mechanism; about 0.4% of operations in the skewed workload trigger splits and writes larger than 1KB.The evaluation uses a skewed workload with access skewness 0.99.Source: §5.5 · p. 11, §5.5.3 · p. 12

5.6 Sensitivity Analysis

Sherman’s advantage over FG+ grows with key size in the reported experiments, while a larger index cache increases performance and cache hit ratio.

5.6.1 Key Size.

  • As key size grows from 16B to 1KB, Sherman’s performance advantage over FG+ rises from 1.17× to 1.47×.The passage attributes the increase to two-level versions saving more bandwidth for larger tree nodes.Source: §5.6.1 · p. 12
  • With 1KB keys under skewed workloads, Sherman still outperforms FG+ by 1.4×.The passage notes that increasing key size does not affect FG+ throughput in high-contention scenarios.Source: §5.6.1 · p. 12

5.6.2 Index Cache Size.

  • For a dataset of 1 billion entries, a 400MB index cache brings the hit rate close to 98%; Sherman’s performance and cache hit ratio both increase as cache capacity grows.The experiment uses uniform, write-intensive workloads.Source: §5.6.2 · p. 12

5.7 HOCL Performance

HOCL’s on-chip global lock tables and compute-server-local lock tables improve lock throughput and latency in the reported skewed-access experiment. Wait queues and lock handover further reduce latency and remote-locking work.

5.7 HOCL Performance

  • With locks on NIC on-chip memory, throughput improves 2.89× and 50th/99th-percentile latency falls 3.01×/2.88×.The passage attributes the gains to eliminating memory-server PCIe transactions for RDMA_CAS commands.Source: §5.7 · p. 12
  • Adding local lock tables yields 3.85× throughput, 5.39× 50th-percentile latency, and 3.65× 99th-percentile latency improvements.A thread issues a remote RDMA_CAS only when no thread on its compute server holds that lock, avoiding failed retries.Source: §5.7 · p. 12
  • Wait queues reduce 99th-percentile latency from 414μs to 372μs by providing first-come-first-served fairness within a compute server.Source: §5.7 · p. 12
  • Lock handover improves throughput by 2.34× and reduces 99th-percentile latency by 3.19× by avoiding remote RDMA_CAS locking during local handover.Source: §5.7 · p. 13

6 Related Work

The related work places Sherman among RDMA-based database and indexing systems, while distinguishing memory disaggregation from logical compute-memory decoupling. It also situates Sherman within broader research and hardware efforts around disaggregated memory.

6 Related Work

  • Sherman is presented as, to the authors’ knowledge, the first tree index on disaggregated memory offering high performance for reads and writes with commodity RDMA NICs.Source: §6 · p. 13

6.1 RDMA-based Databases

  • Prior RDMA database systems span transaction engines such as FaRM, DrTM, and FaSST; the paper says these systems can use Sherman for indexing or HOCL for concurrency.Source: §6.1 · p. 13

6.2 Memory Disaggregation

  • Unlike NAM’s logical decoupling, Sherman’s memory disaggregation physically separates compute and memory, with near-zero memory-side computation and small compute-side local memory.The related-work discussion also covers operating systems, database deployments, and hardware proposals for memory disaggregation.Source: §6.1 · p. 13, §6.2 · p. 13

6.1 RDMA-based Databases

  • FG supports disaggregated memory using one-sided verbs, while RACE is a lock-free extendible-hashing index; Sherman focuses on improving tree-index performance by combining RDMA hardware features and RDMA-friendly software.Source: §6.1 · p. 13

7 Conclusion

Sherman is an evaluated RDMA-based B+Tree index for disaggregated memory. Its techniques boost write performance and outperform existing solutions, showing that hardware features and RDMA-friendly software can enable a high-performance index in this setting.

7 Conclusion

  • Sherman is an evaluated RDMA-based B+Tree index on disaggregated memory.It introduces techniques aimed at boosting write performance.Source: §7 · p. 13
  • Sherman’s techniques boost write performance and outperform existing solutions.Source: §7 · p. 13
  • Combining RDMA hardware features with RDMA-friendly software designs can enable a high-performance index on disaggregated memory.Source: §7 · p. 13
Loading 2112.07320v2…