YoVDO

DistCache - Provable Load Balancing for Large-Scale Storage Systems with Distributed Caching

Offered By: USENIX via YouTube

Tags

FAST (File and Storage Technologies) Courses Distributed Systems Courses Expander Graphs Courses Queuing Theory Courses Load Balancing Courses Hash Functions Courses

Course Description

Overview

Explore a groundbreaking approach to load balancing in large-scale storage systems through this award-winning conference talk. Delve into DistCache, a novel distributed caching mechanism that offers provable load balancing for expansive storage infrastructures. Learn how this innovative solution co-designs cache allocation with cache topology and query routing, partitioning hot objects using independent hash functions across multiple cache layers. Discover the theoretical foundations behind DistCache, including techniques from expander graphs, network flows, and queuing theory. Examine the design challenges faced and their solutions, such as cache allocation strategies and efficient query routing. Gain insights into the implementation of DistCache, particularly in the context of switch-based caching, and understand its potential applications in various storage systems. Analyze the evaluation setup and key takeaways that demonstrate DistCache's ability to linearly scale cache throughput with the number of cache nodes.

Syllabus

Intro
Storage servers have load imbalance issue
Solutions to mitigate the load imbalance
Second, balance the load between clusters
Natural goals on a distributed caching mechanism
Design Challenges of DistCache
Challenge #1: How to allocate the cached items?
Independent hashes to allocate the cached items
Challenge #2: How to query the cached items?
Theoretical Guarantee behind DistCache
Proof Sketch: Convert to a perfect matching problem
Remarks of the DistCache Analysis
Example Deployment Scenarios of DistCache
Case Study: Switch-based distributed caching
Implementation Overview
P4: Programmable Pratocol-independent Packet Processing
Evaluation Setup
Evaluation Takeaways
Conclusions


Taught by

USENIX

Related Courses

Graph Partitioning and Expanders
Stanford University via NovoEd
Sparse Matrices in Sparse Analysis - Anna Gilbert
Institute for Advanced Study via YouTube
Dinur's PCP- Degree-Reduction, Expanderizing, Mini-PCP - Lecture 27c of CS Theory Toolkit
Ryan O'Donnell via YouTube
Expander Graph Application 2: Derandomization - Lecture 16c of CS Theory Toolkit
Ryan O'Donnell via YouTube
Expanding Across Time to Deliver Bandwidth Efficiency and Low Latency
USENIX via YouTube