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

Load balancing is critical for distributed storage to meet strict\nservice-level objectives (SLOs). It has been shown that a fast cache can\nguarantee load balancing for a clustered storage system. However, when the\nsystem scales out to multiple clusters, the fast cache itself would become the\nbottleneck. Traditional mechanisms like cache partition and cache replication\neither result in load imbalance between cache nodes or have high overhead for\ncache coherence.\n We present DistCache, a new distributed caching mechanism that provides\nprovable load balancing for large-scale storage systems. DistCache co-designs\ncache allocation with cache topology and query routing. The key idea is to\npartition the hot objects with independent hash functions between cache nodes\nin different layers, and to adaptively route queries with the\npower-of-two-choices. We prove that DistCache enables the cache throughput to\nincrease linearly with the number of cache nodes, by unifying techniques from\nexpander graphs, network flows, and queuing theory. DistCache is a general\nsolution that can be applied to many storage systems. We demonstrate the\nbenefits of DistCache by providing the design, implementation, and evaluation\nof the use case for emerging switch-based caching.\n