In-Memory Key-Value Store Live Migration with NetMigrate

Zeying Zhu, Yibo Zhao, Zaoxing LiuFAST 2024 · OpenReview

TL;DR

This paper introduces NetMigrate, a novel approach for live migration of in-memory key-value stores that leverages programmable network switches. By offloading migration state tracking to the network, NetMigrate achieves zero downtime and minimal performance impact, significantly improving query throughput and reducing latency compared to existing methods.

What Problem Does This Paper Address?

Modern internet services rely heavily on large-scale, distributed key-value stores for tasks like web caching and real-time analytics. These systems often need to dynamically reconfigure their data distribution (sharding) to adapt to changing workloads, balance load, and improve data locality. However, performing these reconfigurations without interrupting service and degrading performance is a significant challenge. Existing live migration techniques, whether source-based, destination-based, or hybrid, suffer from fundamental limitations: they either incur downtime, introduce performance bottlenecks, or require complex bookkeeping on clients or servers. This paper addresses the need for a more efficient and less intrusive live migration solution for in-memory key-value stores.

Methods

NetMigrate's core innovation lies in its use of programmable Top-of-Rack (ToR) switches as a central "migration index." Instead of relying on clients or servers to track which data shards are being migrated, the ToR switch monitors this process in real-time.

Here's a breakdown of the key techniques:

  • In-Network Migration State Tracking: The ToR switch maintains a "migration state table" using memory-efficient probabilistic data structures like Bloom filters (BF) and counting Bloom filters (CBF). These structures track migration status at a group level (a collection of keys) rather than per-key, which is crucial for managing the vast number of keys in large-scale systems within the limited on-switch memory.
  • Intelligent Query Routing: Based on the migration state tracked in the switch, NetMigrate dynamically routes client queries to either the source or destination server that currently holds the most up-to-date data. This "right-place, right-time" routing minimizes unnecessary data transfers and client-side overhead.
  • Hybrid Approach with Programmable Flexibility: NetMigrate is inherently a hybrid approach, leveraging both source and destination. However, its programmability allows it to dynamically adjust migration policies to mimic other protocols (source-based, destination-based, or other hybrid approaches) or to optimize for specific goals like minimizing migration time or maximizing query throughput.
  • Data Consistency Mechanisms: The system employs strategies to maintain data consistency, including routing write queries to the destination and using double-reads (querying both source and destination) when unsure about data location. It also handles a corner case where late updates to a key might occur just before migration.
  • Efficient Data Transfer: While the switch handles routing, data itself is migrated between servers using data packets. The system also incorporates a mechanism for transferring "late dirty logs" to the destination to ensure consistency for any updates that occur after a data packet has been sent but before the migration is fully complete.

Datasets

The paper does not introduce new datasets. Instead, it uses the standard YCSB (Yahoo! Cloud Serving Benchmark) workload generator to evaluate the performance of key-value stores. The experiments are conducted on Redis instances populated with a large number of key-value pairs (256 million) with specific key and value sizes (4-Byte keys, 64-Byte values).

Key Insights and Ideas

  • The Network as a Smart Coordinator: The most significant insight is that programmable network switches, often overlooked for such tasks, are ideally positioned to act as a central, low-latency coordinator for live migration. Their vantage point allows them to observe all traffic and make informed routing decisions without burdening end hosts.
  • Probabilistic Data Structures for Scalability: The use of Bloom filters and counting Bloom filters is a clever way to manage migration state information within the tight memory constraints of network switches, enabling scalability to billions of keys.
  • Dynamic Policy Adaptation: The ability to dynamically tune migration policies (e.g., prioritize speed vs. performance) by adjusting switch configurations is a powerful feature, allowing NetMigrate to adapt to diverse operational needs.
  • Minimizing Overhead: By offloading complex state tracking to the switch, NetMigrate significantly reduces the overhead on both client applications and server nodes, leading to better overall performance.

Key Results

The experimental results demonstrate NetMigrate's effectiveness:

  • Improved Query Throughput: NetMigrate improves average query throughput by 6.5% to 416% across various YCSB workloads and load-balancing scenarios compared to state-of-the-art approaches.
  • Low Access Latency: The system maintains low access latency during migration, with median latencies reduced by 49% to 65% and 99%-tail latencies improved by 27.0% to 39.5% compared to baselines.
  • Negligible Bandwidth Overhead: NetMigrate incurs very low extra bandwidth overhead, with client-side usage below 0.05% and server-side usage less than 4 × 10⁻⁵%.
  • Zero Downtime: The migration process is designed to be completely transparent to clients, ensuring zero service interruption.
  • Flexible Migration Policies: NetMigrate can achieve comparable migration times to specialized protocols like Rocksteady while offering better performance, and can adapt to different migration speed requirements.

Limitations and Future Work

  • Group-Level Granularity Trade-off: While group-level tracking is memory-efficient, there's a trade-off: smaller groups offer more precise routing but require more memory, while larger groups save memory but can lead to slightly less optimal routing decisions. The paper suggests an optimal group size around 220 keys.
  • Programmable Switch Dependency: The approach relies on the availability of programmable switches (like Intel Tofino), which might not be ubiquitous in all data center environments.
  • Future Work: The authors suggest extending NetMigrate to support larger key/value sizes and multi-key operations. They also mention the potential for integrating NetMigrate with faster networking technologies (like RDMA or DPDK) to further accelerate data transfer and improve migration speed. Additionally, exploring fault tolerance mechanisms for server and switch failures during migration is a promising direction.

Summary updated

BibTeX
@inproceedings{zhu2024memory,
  author = {Zeying Zhu and Yibo Zhao and Zaoxing Liu},
  title = {{In-Memory Key-Value Store Live Migration with NetMigrate}},
  booktitle = {FAST},
  year = {2024},
  url = {https://openreview.net/forum?id=VCw6LRhOgJ},
}
Figure