Load balance and cache affinity: Friends, foes, or frenemies?
summary
Shows that routing by a precomputed TARS voting table (term × replica weights) plus lightweight online multipliers cuts important cache misses by about 2× and raises search-throughput ~40% in one backend. Method uses offline balanced graph partitioning of term–query co‑occurrence, simulates caches on nine regional traces (train/val/test), iteratively refines weights with a cache simulator, and runs in production with Metis/Kapar-style tooling and active probing for hot keys.
AI-written summary · about
chapters (21)
- 0:00Introduction
- 1:05Cache affinity challenges
- 7:17Cache affinity types and impact
- 13:41Non-monotonic load balancing
- 16:31Classic cache affinity limits
- 21:34Vimeo’s consistent hashing
- 24:47Slicer auto-sharding
- 26:57YouTube active probing
- 29:11LLM KV cache challenges
- 30:35Web search retrieval
- 33:10TARS voting scheme
- 37:59Search engine architecture
- 43:14Query trace characteristics
- 51:42Term clustering and voting
- 1:01:45Graph partitioning for clustering
- 1:08:53Cut cost vs cache misses
- 1:10:43Voting table refinement
- 1:12:36Simulation results
- 1:14:03Production benefits
- 1:15:32Conclusion
- 1:22:04Q&A
related talks
17mFalcon: A Scalable Analytical Cache Model
39mSecure Cache Designs: State of the Art and ...
27mAll-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method
41mUsing Microarchitectural Design to Break KASLR and More
13mMemPool Flavors: Between Versatility and Specialization in a RISC-V Manycore Cluster
01h 04mThe challenge of managing parallelism and data-movement for tensor computations on GPUs
01h 10mOn Algorithmic Game Theory II
49mGraph Based Processing of Big Images