PaperlayerView exact revision on arXiv

Source-linked AI summary

Effectively Prefetching Remote Memory with Leap

Hasan Al Maruf, Mosharaf Chowdhury

arXiv:1911.09829v1cs.DCcs.OS

TL;DR

Memory disaggregation can replace disk swapping with remote memory, but existing systems retain slow-disk-oriented data paths and incur excessive remote-access latency. Leap addresses this gap with majority-based online prefetching, eager cache eviction, and a lean per-application remote-memory path. Integrated into Linux, it improves remote-page latency by up to 104.04× at the median and 22.62× in the tail, with application-level gains up to 10.16× over state-of-the-art solutions.

  • Problem

    Existing memory-disaggregation systems use data-path components designed for slow disks, leaving remote-memory latency substantially higher than the underlying RDMA network.

  • Method

    Leap combines per-process majority-based online prefetching with eager cache eviction and a lean data path that isolates application traffic and removes unnecessary kernel components.

  • Results

    Leap improves median and tail remote-page access latencies by up to 104.04× and 22.62×, respectively, over Linux’s default data path, and improves application performance by up to 10.16× over state-of-the-art solutions.

  • Takeaways & Limitations

    Leap provides remote-memory performance improvements without modifying applications or hardware and can also benefit slower storage systems such as HDDs and SSDs.

  • Takeaways & Limitations

    Leap’s trend detection can treat small windows or perfectly interleaved threads with different strides as random patterns, causing speculative prefetching to stop when speculation fails.

Abstract

from arXiv · show

Memory disaggregation over RDMA can improve the performance of memory-constrained applications by replacing disk swapping with remote memory accesses. However, state-of-the-art memory disaggregation solutions still use data path components designed for slow disks. As a result, applications experience remote memory access latency significantly higher than that of the underlying low-latency network, which itself is too high for many applications. In this paper, we propose Leap, a prefetching solution for remote memory accesses due to memory disaggregation. At its core, Leap employs an online, majority-based prefetching algorithm, which increases the page cache hit rate. We complement it with a lightweight and efficient data path in the kernel that isolates each application's data path to the disaggregated memory and mitigates latency bottlenecks arising from legacy throughput-optimizing operations. Integration of Leap in the Linux kernel improves the median and tail remote page access latencies of memory-bound applications by up to 104.04x and 22.62x, respectively, over the default data path. This leads to up to 10.16x performance improvements for applications using disaggregated memory in comparison to the state-of-the-art solutions.

1 INTRODUCTION

Memory disaggregation can use stranded cluster memory to help memory-constrained applications, but remote accesses still traverse latency-heavy disk-oriented kernel paths. Leap combines per-process majority-based prefetching, eager cache eviction, and a leaner remote-memory data path to improve cache behavior and access latency.

  • Motivation: Memory disaggregation exposes otherwise stranded cluster memory as a logical pool for memory-constrained applications.This can improve application performance and cluster resource utilization when complete working sets do not fit in local memory.
  • Motivation: Existing systems can take close to 40 µs for an average 4KB remote page access, although memory-intensive applications tolerate at most single-µs latency.Cold-page accesses follow a slow kernel data path after local memory is exhausted.
  • Leap: Leap uses a Boyer-Moore majority-vote algorithm to identify each process’s remote access pattern while tolerating short-term irregularities.It detects trends from remote page accesses rather than continuously tracing the full virtual-memory footprint.
  • Leap: Leap determines how many pages to prefetch and eagerly frees a cache entry after it is hit, reducing unnecessary cache occupancy and page-allocation wait time.The eager policy complements background LRU-based asynchronous eviction.
  • Data path: Leap’s per-application remote data path removes unnecessary end-host components, including the block layer, to approach underlying RDMA latency on cache misses.The implementation provides a separate Linux data path while preserving unmodified Linux ABIs.

2 BACKGROUND AND MOTIVATION

Remote-memory systems inherit disk-oriented kernel paths whose queuing and batching overheads can dominate RDMA latency. Linux’s strict, shared prefetching and lazy eviction policies also mishandle diverse access patterns, motivating pattern-aware caching and eviction.

  • Remote memory: Unused cluster memory can form a global pool that serves as slower memory for machines with extreme demand, balancing cluster memory usage.This reduces the need for per-machine memory over-provisioning.
  • Remote memory data path: State-of-the-art systems depend on kernel data paths optimized for slow disks rather than remote memory.Their page-request lifecycle includes stages designed around disk access behavior.
  • Prefetching: Linux’s default prefetcher uses the last two page faults, causing optimistic cache pollution for some applications and pessimistic prefetching for non-sequential patterns.Shared swap placement and interleaved thread strides make the two-request rule unreliable.
  • Remote memory data path: RDMA provides 4.3 µs access latency versus 91.5 µs for disk, but remote-memory solutions measure 38.3 µs versus 125.5 µs because data-path preparation adds 34 µs on average.Preparation and batching variation also makes average latency diverge substantially from the median.
  • Prefetching: For sequential accesses, an eight-page prefetch size achieves 80% cache hits, whereas Stride-10 accesses miss the page cache because successive pages are not consecutive.The contrasting patterns expose the limits of sequential-layout assumptions.
  • Prefetching: Majority-based detection identifies 11.3%–29.7% more sequential accesses than strict pattern matching at window size X = 8.It can tolerate transient interruptions that strict all-access matching treats as patternless.
  • Cache eviction: Linux’s prefetched pages can remain in the LRU list after use, increasing eviction scanning time and delaying memory allocation.The lazy policy wastes cache area while pages wait for their turn to be selected.

3 REMOTE MEMORY PREFETCHING

This section defines the properties of an effective remote-memory prefetcher and presents Leap’s adaptive, majority-based approach for detecting trends and generating prefetch candidates. Leap uses expanding detection windows and adjusts prefetch behavior to tolerate irregular access patterns while controlling overhead and cache pollution.

  • 3.1 Properties of an Ideal Prefetcher: An effective prefetcher must balance accuracy, coverage, and timeliness while limiting computational and memory overhead.Aggressive prefetching can improve coverage but waste cache and bandwidth; conservative prefetching reduces contention but may fail to hide memory latency.
  • 3.2 Online Prefetcher: Leap detects approximate access trends and uses trend availability and prior prefetch utilization to determine which pages and how many pages to prefetch.This separates trend detection from prefetch-candidate generation.
  • 3.2.1 Trend Detection: Leap identifies a majority delta in a fixed-size remote-page access window using the Boyer-Moore majority vote algorithm, ignoring short-term irregularities.A delta is major when it appears at least ⌊w/2⌋+1 times in a window of size w.
  • 3.2.1 Trend Detection: FindTrend begins with a small window and doubles it until it finds a majority or reaches the AccessHistory size.The initial window is controlled by Nsplit, and continuous windows avoid repeatedly scanning the same history items.
  • 3.2.2 Prefetch Candidate Generation: Leap adapts its prefetch window using cache-hit feedback, shrinking after low utilization and expanding after successful prefetches.If no majority trend exists, Leap can speculate using the previous trend or stop prefetching when the prefetch window reaches zero.
  • 3.3 Analysis: The FindTrend function has worst-case time complexity O(Hsize), while its extra computational cost is reported to be outweighed by performance gains even for Hsize = 32.Boyer-Moore detects a majority in O(w) time, and continuous windows prevent repeated access to the same item.

4 SYSTEM DESIGN

Leap replaces the traditional remote-memory data path with a kernel-integrated path combining process-isolated access tracking, majority-based prefetching, and eager cache eviction. It preserves existing memory-disaggregation frameworks while bypassing expensive legacy operations and reducing allocation overhead.

  • 4 SYSTEM DESIGN: Leap adds a separate Linux kernel data path with a page access tracker, majority-based prefetcher, and eager cache eviction mechanism.The implementation uses Linux kernel v4.4.125 and requires around 400 lines of code for these components.
  • 4.1 Page Access Tracker: The page access tracker maintains process-specific fixed-size FIFO AccessHistory queues and records remote page-fault history for prefetch decisions.Leap monitors remote accesses rather than continuously scanning hot in-memory pages, reducing tracking overhead.
  • 4.2 Prefetcher: Leap uses process-level rather than thread-level pattern detection because threads in one process share memory.The prefetcher uses temporal and spatial locality in remote page accesses to predict future demand.
  • 4.3 Data Path: When prefetching, Leap bypasses expensive request scheduling and batching operations in the block layer.Prefetched pages are tracked in a dedicated cache list and freed immediately after a hit.
  • 4.4 Cache Eviction: Eager eviction reduces page-allocation wait time by freeing consumed prefetched pages before background eviction scans select candidates.Average page allocation time is reduced by 750 ns, or 36% less than the comparison point stated in the passage.
  • 4.5 Resilience, Scalability, and Load Balancing: Leap can use existing memory-disaggregation frameworks while retaining their scalability and fault-tolerance characteristics.The paper explicitly claims no innovation in those framework mechanisms.

5 EVALUATION

The evaluation integrates Leap into Linux VMM and VFS paths and tests it against local disks, disaggregated VMM, and disaggregated VFS configurations. Across these settings, Leap improves remote-access latency, prefetching behavior, and application performance over existing approaches.

  • 5 EVALUATION: Leap is evaluated over a 56 Gbps InfiniBand RDMA network on CloudLab.The experiments integrate Leap into both Linux VMM and VFS data paths.
  • 5 EVALUATION: 104.04× median and 22.06× tail latency improvements are reported for 4KB remote page accesses in disaggregated VMM, while disaggregated VFS reaches 24.96× median and 17.32× tail improvements.These are the reported maximum latency benefits for the two memory-disaggregation systems.
  • 5 EVALUATION: Leap’s prefetcher improves cache pollution by up to 1.62×, cache miss performance by up to 10.47×, and prefetch coverage by up to 37.51% over Next-K, Stride, and Linux Read-Ahead.These comparisons use the prefetching counterparts named in the evaluation summary.
  • 5 EVALUATION: Unmodified PowerGraph, NumPy, VoltDB, and MemCached achieve up to 9.84× faster completion times and 10.16× higher throughput than existing memory-disaggregation solutions.The result covers four applications using disaggregated memory.
  • 5 EVALUATION: The evaluation compares local HDD and SSD swapping with disaggregated VMM and disaggregated VFS systems.The disaggregated VMM integrates Leap with Infiniswap, while the disaggregated VFS integrates it with Remote Regions.

5.1 Microbenchmark

The microbenchmark evaluates 4KB remote-page latency under sequential and stride access patterns in disaggregated VMM and VFS systems. Leap benefits from both its prefetcher and faster data path, with especially large gains for stride access.

  • Sequential and Stride Access: 80% of sequential requests hit the default Linux prefetch cache, whereas every stride request misses because prefetched pages are unused.This contrasts sequential behavior with Linux prefetching under stride access.
  • Disaggregated VMM: 4.07× median and 5.48× 99th-percentile latency improvements occur for Leap under sequential disaggregated VMM access.The comparison concerns 4KB page access latency.
  • Disaggregated VMM: 104.04× median and 22.06× tail latency improvements occur for Leap under Stride-10 disaggregated VMM access.The passage attributes the result to effective stride detection and Leap’s faster data path.
  • Disaggregated VFS: Leap improves disaggregated VFS latency by 1.99× median and 3.42× at the 99th percentile for sequential access.These results are for 4KB page access latency.
  • Disaggregated VFS: Leap improves disaggregated VFS latency by 24.96× at the median and 17.32× at the 99th percentile for stride access.The paper focuses on disaggregated VMM for the remainder of its evaluation.

5.2 Performance Benefit of the Prefetcher

Leap’s majority-based prefetcher reduces cache pollution and misses while improving remote-page latency and application completion time. Its benefits arise from combining accurate, timely prefetching with eager cache eviction.

  • Prefetcher effectiveness: Single-digit µs latency reaches the 95th percentile, while prefetching provides sub-µs 4KB page access latency through the 85th percentile.For PowerGraph at a 50% memory limit, the prefetcher also improves 99th-percentile latency by 11.4% over Leap’s optimized data path.
  • Prefetcher effectiveness: 22.2% lower tail latency results from Leap’s eager eviction policy reducing page-cache allocation time.
  • Storage-system comparison: 1.25× and 1.61× lower overall runtime result over SSD and HDD, respectively, compared with Linux’s default prefetcher.These results come from applying Leap’s majority-based prefetching algorithm within Linux’s default disk data path.
  • Cache impact: 28.15%–62.13% fewer page caches and 7.19×–10.47× fewer cache misses demonstrate lower cache pollution than competing prefetchers.Compared with Read-Ahead, Leap experiences 1.736× fewer cache-miss events.
  • Application performance: PowerGraph’s completion time is 2.59×, 3.36×, and 1.75× higher with Next-N-Line, Stride, and Read-Ahead than with Leap.
  • Prefetch trade-offs: Leap trades 0.9–10.88% lower accuracy for 3.06–37.51% coverage, while Stride’s poor coverage and completion time limit its overall performance.

5.3 Leap’s Overall Impact on Applications

Across four memory-intensive applications, Leap improves remote-memory performance through better pattern detection, faster cache eviction, and application-isolated data paths. These benefits persist with constrained cache capacity and concurrent workloads.

  • PowerGraph: Leap detects 19.03% more remote-page access patterns than Read-Ahead for PowerGraph, increasing cache hits and reducing cache-space and RDMA-bandwidth waste.
  • NumPy: NumPy’s completion time improves by 1.27× and 1.4× at 50% and 25% memory limits, while 99th-percentile 4KB access time improves by 5.28× and 2.88%.
  • VoltDB: VoltDB’s throughput improves by 2.76× and 10.16× at 50% and 25% memory limits, respectively, while Leap reduces throughput loss relative to local memory.Leap’s adaptive throttling helps avoid RDMA congestion for VoltDB’s irregular random accesses.
  • Memcached: Memcached’s throughput improves by 1.11× and 1.21× at 50% and 25% memory limits, while its 99th-percentile 4KB access time improves by 5.94× and 1.08×.
  • Constrained cache size: 11.87–13.05% performance loss remains under O(1)MB cache size for the applications benefiting from timely prefetching.For NumPy, the 3.2MB cache is only 0.02% of total remote memory usage.
  • Concurrent workloads: 1.1–2.4× overall performance improvement occurs when all four applications concurrently access remote memory.Per-application path isolation lets Leap make application-specific prefetch decisions and reduce network contention.

6 RELATED WORK

Related systems expose remote memory through software, hardware, and kernel mechanisms, while existing prefetchers often target lower-level memory stacks or disk-oriented access patterns. Leap complements these efforts with a kernel-level prefetcher for RDMA-backed remote DRAM.

  • Remote memory solutions: Remote-memory systems support paging, global virtual-machine abstractions, distributed stores, and filesystems, while hardware proposals use PCIe or extended NUMA fabrics.Leap is described as complementary to these remote-memory solutions.
  • Kernel data paths: Kernel data-path research addresses faster storage through batching, queuing, interrupt, context-switching, and buffer-cache optimizations.
  • Prefetching algorithms: Many prefetchers depend on specific access patterns, application behavior, or hardware support and target a lower-level memory stack than Leap’s prefetcher.
  • Linux Read-Ahead: Linux Read-Ahead was designed to hide disk seek time and can reduce cache utilization for remote-memory access because it uses an optimistic look-around approach.
  • Leap’s position: Leap is presented as the first fully software-based kernel-level prefetcher for DRAM backed by remote memory over fast RDMA-capable networks.

7 CONCLUSION

Leap combines majority-based remote-page pattern detection with a lean RDMA data path that requires no application or hardware modifications. Across two memory disaggregation systems, it substantially improves remote-page latency and application performance.

  • Design: Leap uses majority-based rather than strict pattern detection, making it resilient to short-term irregularities in access sequences.
  • Latency results: 104.04× median and 22.62× tail remote-page latency improvements are achieved over Linux’s default data path across Infiniswap and Remote Regions.
  • Application results: 1.27–10.16× application-level performance improvements are achieved over state-of-the-art solutions.Applying Leap to HDD and SSD storage also produces large performance benefits.
Loading 1911.09829v1…