Pragh: Locality-preserving Graph Traversal with Split Live Migration

Xiating Xie, Xingda Wei, Rong Chen, Haibo ChenUSENIX ATC 2019 · OpenReview

TL;DR

This paper introduces Pragh, a novel system for live migration of graph data in distributed graph stores. Pragh's "split live migration" approach physically moves only the values of key-value pairs, keeping keys stationary, to significantly improve data access locality for graph traversal workloads. This technique achieves substantial performance gains, including up to a 19x throughput increase and a 94% reduction in median latency, by minimizing remote data access.

What Problem Does This Paper Address?

Real-world data, such as social networks, transportation systems, and biological networks, are increasingly modeled as graphs. Efficiently querying these large, distributed graphs requires fast traversal operations. A major challenge in distributed graph stores is maintaining data locality, meaning that data frequently accessed together is stored on the same machine. Traditional graph partitioning methods struggle to preserve this locality, especially with dynamic workloads and evolving graphs. Existing live migration techniques, which aim to improve locality by moving data, often face a dilemma: coarse-grained migration incurs high overhead, while fine-grained migration requires complex metadata management. This paper addresses the need for an efficient, fine-grained live migration strategy that preserves locality in distributed graph stores without excessive overhead.

Methods

Pragh introduces a novel "split live migration" model. The core idea is to decouple the migration of keys and values. In Pragh, keys remain at their original locations, while only the values are physically migrated. This allows for fine-grained, vertex-level migration without the need for extensive metadata to track the location of every migrated data item.

Key techniques and design choices include:

  • Split Migration Model: Physically migrates only values, keeping keys stationary. This enables fine-grained migration and avoids complex metadata management.
  • RDMA-Friendly Location Cache: Integrates a cache that stores the addresses of migrated data values. This allows for fully localized access to migrated data, eliminating remote reads for both keys and values.
  • Unilateral Migration Protocol: The target machine initiates and completes the migration of a key-value pair using one-sided RDMA primitives, simplifying the process and allowing concurrent operations.
  • Check-and-Forward Mechanism: Addresses conflicts between data updates (PUT operations) and migration, ensuring consistency in evolving graphs.
  • Lightweight Monitoring: A memory-efficient monitor reuses the location cache's replacement policy to track frequently accessed remote data, generating optimal migration plans without significant overhead.
  • Eager and Deferred Migration: Two optional mechanisms to balance the accuracy and timeliness of migration decisions.

Datasets

The paper evaluates Pragh using a synthetic graph generated by the Graph500 benchmark (RMAT26 dataset). They also mention using the Lehigh University Benchmark (LUBM) for evaluating its application to RDF graph and SPARQL queries. No new benchmarks were introduced; instead, they used existing ones to demonstrate Pragh's effectiveness.

Key Insights and Ideas

  • Decoupling Keys and Values is Key: The fundamental insight is that by keeping keys fixed and only migrating values, Pragh can achieve fine-grained migration with significantly reduced metadata overhead. This is a crucial departure from traditional shard-based migration.
  • RDMA is an Enabler: The availability of RDMA (Remote Direct Memory Access) is critical. It allows for efficient one-sided operations that decouple key and value access, making the split migration approach feasible and performant.
  • Location Cache Complements Split Migration: The location cache, which stores addresses of remote data, perfectly complements split migration. While split migration moves values, the cache ensures that accessing the location of these values also becomes local, leading to fully localized access.
  • Fine-grained Migration Outperforms Coarse-grained: The experiments clearly show that migrating individual vertices (fine-grained) is far more effective for graph traversal workloads than migrating larger shards, even with optimal shard migration plans.
  • Lightweight Monitoring is Sufficient: The paper demonstrates that a simple, cache-based monitoring mechanism is enough to gather the necessary statistics for effective migration, avoiding the high overhead of tracking every access.

Key Results

  • Throughput and Latency Improvements: Pragh achieved up to a 19x increase in throughput and a 94% decrease in median latency on a representative graph traversal benchmark.
  • Reduced Remote Access: The remote access rate dropped from 86.2% to 2.0% with Pragh.
  • Wukong Integration: Integrating split live migration into Wukong (a distributed graph store for RDF data) resulted in up to a 2.53x throughput improvement.
  • Migration Efficiency: Pragh can migrate over a million vertices per second with less than 4KB payloads, and 24 threads can achieve over 10 million migrations per second.
  • Dynamic Workload Recovery: Pragh can recover performance within approximately 5 seconds after a workload change, demonstrating its responsiveness to dynamic environments.

Limitations and Future Work

  • RDMA Dependency: The current implementation heavily relies on RDMA. The authors acknowledge that extending Pragh to commodity networks without RDMA is a future research direction.
  • Coordinator Bottleneck: While the coordinator is designed to be lightweight, it might become a bottleneck in very large clusters.
  • Data Replication Orthogonality: The paper notes that data replication is orthogonal to live migration and suggests integrating split live migration with fine-grained vertex replication as future work.
  • Load Balancing Policies: While Pragh can be used for load balancing, the specific policies and statistics needed for different goals are considered beyond the scope of this paper.
  • Fault Tolerance: Pragh assumes existing mechanisms for durability and availability (checkpointing/replication) and focuses on handling interrupted migrations and crashed machines.

Summary updated

BibTeX
@inproceedings{xie2019pragh,
  author = {Xiating Xie and Xingda Wei and Rong Chen and Haibo Chen},
  title = {{Pragh: Locality-preserving Graph Traversal with Split Live Migration}},
  booktitle = {USENIX ATC},
  year = {2019},
  url = {https://openreview.net/forum?id=d0q6ZaRK9b},
}
Figure