University:
Boston University
Course:
MET CS 201 | Introduction to Programming
Academic year:

2021
Views:

75

Pages:

22
Author:

njihovbdti

RobinHood: Tail Latency-Aware Caching in Large Web Services Microsoft Web Architecture User request Backend queries News Ad-System Recommend Products Request latency Aggregation server Request must wait for last query! Goal: minimize 99-th percentile request latency (P99) 1 What Causes High P99 Request Latency? Based on xbox.com production trace from 3/2018. User request Backend queries B8 B6 B5 B1 Request latency Aggregation server Better load balancing? Auto-scaling for backend systems? already included here 2 What Else Can We Do? User request Cache Backend queries B8 B6 B5 B1 Request latency Aggregation server Aggregation Cache Shared among queries to all backends Can we use this cache to reduce P99 request latency? 3 Can We Use Caching to Reduce the P99? Belief: No Cache 1ms 10% B 100ms P99 [ms] (assuming backend not overloaded) 90% 100 Most hit ratios 1 90 95 100 Hit Ratio [%] “The caching layer does not directly address tail latency” Existing caching systems do not attempt to reduce the P99 Instead focus on: overall miss ratio or fairness properties 4 Can We Use Caching to Reduce the P99? Belief: No (assuming backend not overloaded) Cache 1ms 10% B 90% But: latency is not a constant 100ms P99 [ms] 90% 100 1 90 95 100 Hit Ratio [%] 10% 50ms 100ms Caching can reduce P99 request latency! Effectiveness in Microsoft’s architecture? 5 Can We Use Caching to Reduce the P99? Observations at Microsoft Belief: No (assuming backend not overloaded) 1) Lower hit ratios, more competition for cache space Cache P99 Latency B8 B6 B5 B1 2) Some backends are temporarily overloaded 0 Load 1 Use the Aggregation Cache as a “Load Balancer”! 6 RobinHood: Experimental Validation of our “Caching for Tail Latency Idea” RobinHood Caching System - Microsoft web architecture - Partition aggregation cache by backend system - Minimize request P99 by dynamically adjusting partition sizes Scalable in # backends, #aggregatio n servers eh t f f o n o le Deployab ck a t s e r a w t shelf sof 7 Challenges in Minimizing the Request P99 Use the Aggregation Cache as a “Load Balancer”! How to define “load”? 1) High Load = High Query Rate 8 Challenges in Minimizing the Request P99 Use the Aggregation Cache as a “Load Balancer”! How to define “load”? 2) High Load = High Query P99 User request 100 queries in parallel AC B3 B2 B1 Same P99 on all backends sufficient? 9 Challenges in Minimizing the Request P99 Use the Aggregation Cache as a “Load Balancer”! How to define “load”? 3) High Load = High Query Latency (Different Percentiles) User requests 99.5% 0.5% B3 has high query latency AC B3 B2 B1 Should we prioritize B3? 10 Challenges in Minimizing the Request P99 Use the Aggregation Cache as a “Load Balancer”! How to define “load”? Need a new definition of “load” - Incorporate whether backend “causes” high request P99 - Frequently recalculate load metric 11 Basic RobinHood Algorithm Find the backend “causing” high request P99 Challenges: - Not a single cause - Sample Variance Basic algorithm: 1. Sort all request latencies: P99 P0 2. P100 Determine who “blocked” P99 request (= on critical path) B3 B1 B2 3. B2 blocked Allocate cache space to blocking backend 12 Refined RobinHood Algorithm Find the backend “causing” high request P99 Challenges: - Not a single cause - Sample Variance Refined algorithm: 1. Sort all request latencies: P99 P0 2. X = { requests in P99 neighborhood } 3. Determine who “blocked” requests in X (= on critical path) B3 B1 Consider a “neighborhood” of the P99 P100 B2 4. B2 blocked Allocate in proportion to “request blocking count” (RBC) in X 13 Dynamic Reallocation with RobinHood Record request latencies Calculate RBC (steps 1 - 3) Take 1% cache space from every partition. Reallocate in proportion to RBC (step 4) Per request: - latency - blocking backend Record request latencies ... Δ seconds Δ seconds Time 14 RobinHood Architecture Aggregation Cache (AC) - need support for dynamic resizing - e.g., off-the-shelf memcached 1.5 RH-control Aggregation server AC RobinHood Controller - not on request path - lightweight python Backends B1 ... B5 ... B20 - computes RBC - runs allocation algorithm - controls AC partitioning 15 RobinHood Architecture Production system: 16-64 Ag. servers ⇒ RH-control / AC RH-stats Distributed RobinHood: - Pooled measurements Local measurements Ag. servers RH-control AC RH-control RH-control ... AC ... AC - Increase #tail data points - Stream to/Pull from central buffer (RH-stats) - “Just a buffer” (15s state) Backends B1 ... B5 ... B20 - Local decisions - Based on local partition’s allocation speed - Transient differences Δ = 5 seconds across ag. server 16 Experimental Setup Replay production requests and queries Request generator For 4 hours, at 200k queries/second (max: ~500k queries / second) RH-stats 32 GB cache size 16 threads, 8 Gbit/s network RH-control Ag. servers AC RH-control RH-control ... AC ... AC 20 backends up to 8 servers per backend Emulate query latency spikes Backends B1 MySQL (I/O Bound) ... B5 Matrix Multiply (CPU Bound) ... B20 K-V Store (CPU Bound) 17 Evaluation Results: P99 Request Latency RobinHood [our proposal] MS Production System [OneRF] Minimize overall miss ratio [Cliffhanger, NSDI’16] Fairness between partitions [FairRide, NSDI’16] Balance query latencies [Hyberbolic, ATC’17] (Improved P99-version) 18 Evaluation Results: RBC Balance RBC = request blocking count Intuition: balanced ↔ no single bottleneck 19 Evaluation Results: RBC Balance RBC = request blocking count Intuition: balanced ↔ no single bottleneck 20 Conclusions Is it possible to use caches to improve the request P99? Yes! 5x reduction in peak latency, 10x fewer SLO violations. Caches can be used as load balancers: “RBC load metric”. Feasibility in production systems? Yes! Tested on off-the-shelf software statck. Works orthogonally to existing load balancing and auto scaling techniques. Is this the optimal solution? End of this project? No! There’s a lot to do, e.g., other types of workloads (Google, FB), other types of systems (apply ideas to resource allocation, …). Vision: near-optimal allocation based on performance modeling 21