Load Imbalance and Caching Performance of Sharded Systems
- 17 December 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 28 (1), 112-125
- https://doi.org/10.1109/tnet.2019.2957075
Abstract
Sharding is a method for allocating data items to nodes of a distributed caching or storage system based on the result of a hash function computed on the item's identifier. It is ubiquitously used in key-value stores, CDNs and many other applications. Despite considerable work that has focused on the design and implementation of such systems, there is limited understanding of their performance in realistic operational conditions from a theoretical standpoint. In this paper we fill this gap by providing a thorough modeling of sharded caching systems, focusing particularly on load balancing and caching performance aspects. Our analysis provides important insights that can be applied to optimize the design and configuration of sharded caching systems.Keywords
Funding Information
- H2020 LEIT Information and Communication Technologies (723014)
- Engineering and Physical Sciences Research Council (EP/M003787/1)
This publication has 29 references indexed in Scilit:
- Algorithmic Nuggets in Content DeliveryACM SIGCOMM Computer Communication Review, 2015
- Characterizing the miss sequence of the LRU cacheACM SIGMETRICS Performance Evaluation Review, 2008
- Hierarchical Web caching systems: modeling, design and experimental resultsIEEE Journal on Selected Areas in Communications, 2002
- Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilitiesThe Annals of Applied Probability, 1999
- Using name-based mappings to increase hit ratesIEEE/ACM Transactions on Networking, 1998
- “Balls into Bins” — A Simple and Tight AnalysisLecture Notes in Computer Science, 1998
- Hash routing for collections of shared Web cachesIEEE Network, 1997
- Limits and rates of convergence for the distribution of search cost under the move-to-front ruleTheoretical Computer Science, 1996
- Poisson Arrivals See Time AveragesOperations Research, 1982
- Asymptotic miss ratios over independent referencesJournal of Computer and System Sciences, 1977