{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T10:13:24Z","timestamp":1767262404809},"reference-count":84,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,2]]},"abstract":"<jats:p>Our deployment of cache-aware load balancing in the Google web search backend reduced cache misses by ~0.5x, contributing to a double-digit percentage increase in the throughput of our serving clusters by relieving a bottleneck. This innovation has benefited all production workloads since 2015, serving billions of queries daily.<\/jats:p>\n          <jats:p>A load balancer forwards each query to one of several identical serving replicas. The replica pulls each term's postings list into RAM from flash, either locally or over the network. Flash bandwidth is a critical bottleneck, motivating an application-directed RAM cache on each replica. Sending the same term reliably to the same replica would increase the chance it hits cache, and avoid polluting the other replicas' caches. However, most queries contain multiple terms and we have to send the whole query to one replica, so it is not possible to achieve a perfect partitioning of terms to replicas.<\/jats:p>\n          <jats:p>We solve this via a voting scheme, whereby the load balancer conducts a weighted vote by the terms in each query, and sends the query to the winning replica. We develop a multi-stage scalable algorithm to learn these weights. We first construct a large-scale term-query graph from logs and apply a distributed balanced graph partitioning algorithm to cluster each term to a preferred replica. This yields a good but simplistic initial voting table, which we then iteratively refine via cache simulation to capture feedback effects.<\/jats:p>","DOI":"10.14778\/3311880.3311887","type":"journal-article","created":{"date-parts":[[2019,3,26]],"date-time":"2019-03-26T20:22:15Z","timestamp":1553631735000},"page":"709-723","source":"Crossref","is-referenced-by-count":15,"title":["Cache-aware load balancing of data center applications"],"prefix":"10.14778","volume":"12","author":[{"given":"Aaron","family":"Archer","sequence":"first","affiliation":[{"name":"Google"}]},{"given":"Kevin","family":"Aydin","sequence":"additional","affiliation":[{"name":"Google"}]},{"given":"Mohammad Hossein","family":"Bateni","sequence":"additional","affiliation":[{"name":"Google"}]},{"given":"Vahab","family":"Mirrokni","sequence":"additional","affiliation":[{"name":"Google"}]},{"given":"Aaron","family":"Schild","sequence":"additional","affiliation":[{"name":"UC Berkeley"}]},{"given":"Ray","family":"Yang","sequence":"additional","affiliation":[{"name":"Google"}]},{"given":"Richard","family":"Zhuang","sequence":"additional","affiliation":[{"name":"Google"}]}],"member":"320","published-online":{"date-parts":[[2019,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2740070.2626316"},{"key":"e_1_2_1_2_1","unstructured":"Amazon Web Services (AWS). https:\/\/aws.amazon.com.  Amazon Web Services (AWS). https:\/\/aws.amazon.com."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1350-7"},{"key":"e_1_2_1_4_1","unstructured":"J. Arnold. OpenStack Swift: Using Administering and Developing for Swift Object Storage. O'Reilly Media Inc. 1st edition 2014.   J. Arnold. OpenStack Swift: Using Administering and Developing for Swift Object Storage. O'Reilly Media Inc. 1st edition 2014."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2835776.2835829"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2003.1196112"},{"key":"e_1_2_1_8_1","volume-title":"Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems, NeurIPS '17","author":"Bateni M.","year":"2017"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11558989_20"},{"key":"e_1_2_1_10_1","volume-title":"Osborne\/McGraw-Hill","author":"Bloom R. B.","year":"2002"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-438150-6.50018-2"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45172-3_7"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2516633.2516637"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/4236.769420"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/580760.823759"},{"key":"e_1_2_1_16_1","volume-title":"Manning Publications Co.","author":"Carlson J. L.","year":"2013"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0210-9"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/MIC.2002.1036038"},{"issue":"2","key":"e_1_2_1_19_1","first-page":"321","article-title":"Digital slaves of the render farms?: Virtual actors and intellectual property rights. Journal of Law","volume":"2004","author":"Faier A.","year":"2004","journal-title":"Technology & Policy"},{"key":"e_1_2_1_20_1","unstructured":"https:\/\/github.com\/twitter\/fatcache.  https:\/\/github.com\/twitter\/fatcache."},{"issue":"124","key":"e_1_2_1_21_1","first-page":"5","article-title":"Distributed caching with memcached","volume":"2004","author":"Fitzpatrick B.","journal-title":"Linux Journal"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2740070.2626317"},{"key":"e_1_2_1_23_1","volume-title":"Freeman","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/CloudCom.2017.49"},{"key":"e_1_2_1_25_1","unstructured":"Google Cloud Platform. https:\/\/cloud.google.com.  Google Cloud Platform. https:\/\/cloud.google.com."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2829988.2787507"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2017.137"},{"key":"e_1_2_1_28_1","unstructured":"IBM Bluemix. https:\/\/bluemix.net.  IBM Bluemix. https:\/\/bluemix.net."},{"key":"e_1_2_1_29_1","unstructured":"Internet Live Stats. Google search statistics. http:\/\/www.internetlivestats.com\/google-search-statistics.  Internet Live Stats. Google search statistics. http:\/\/www.internetlivestats.com\/google-search-statistics."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137650"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258660"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(99)00055-9"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007912.1007919"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2670979.2670997"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-016-0394-1"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1773912.1773922"},{"key":"e_1_2_1_38_1","unstructured":"The Launchpad build farm. https:\/\/launchpad.net\/builders.  The Launchpad build farm. https:\/\/launchpad.net\/builders."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.153"},{"key":"e_1_2_1_41_1","unstructured":"https:\/\/www.facebook.com\/notes\/facebook-engineering\/mcdipper-a-keyvalue-cache-for-flash-storage\/10151347090423920.  https:\/\/www.facebook.com\/notes\/facebook-engineering\/mcdipper-a-keyvalue-cache-for-flash-storage\/10151347090423920."},{"key":"e_1_2_1_42_1","unstructured":"memcached: a distributed memory object caching system. https:\/\/memcached.org.  memcached: a distributed memory object caching system. https:\/\/memcached.org."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3098822.3098824"},{"key":"e_1_2_1_44_1","unstructured":"Microsoft Azure. https:\/\/azure.microsoft.com.  Microsoft Azure. https:\/\/azure.microsoft.com."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175309"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.963420"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148170.1148232"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10791-006-9014-4"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/WAINA.2009.96"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/2482626.2482663"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1842733.1842736"},{"key":"e_1_2_1_52_1","unstructured":"Openstack swift: Powering the world's largest storage clouds. https:\/\/www.swiftstack.com\/product\/openstack-swift.  Openstack swift: Powering the world's largest storage clouds. https:\/\/www.swiftstack.com\/product\/openstack-swift."},{"key":"e_1_2_1_53_1","unstructured":"Oracle Cloud Platform. https:\/\/cloud.oracle.com\/paas.  Oracle Cloud Platform. https:\/\/cloud.oracle.com\/paas."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipm.2010.12.007"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1961659.1961663"},{"key":"e_1_2_1_56_1","doi-asserted-by":"crossref","unstructured":"M. T. \u00d6zsu and P. Valduriez. Principles of Distributed Database Systems. Springer Publishing Company Incorporated 3rd edition 2011.   M. T. \u00d6zsu and P. Valduriez. Principles of Distributed Database Systems. Springer Publishing Company Incorporated 3rd edition 2011.","DOI":"10.1007\/978-1-4419-8834-8"},{"key":"e_1_2_1_57_1","doi-asserted-by":"crossref","unstructured":"D. Padua editor. ParaMETIS pages 1458--1458. Springer US Boston MA 2011.  D. Padua editor. ParaMETIS pages 1458--1458. Springer US Boston MA 2011.","DOI":"10.1007\/978-0-387-09766-4_2084"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2534169.2486026"},{"key":"e_1_2_1_59_1","unstructured":"M. Pool. distcc - a free distributed C\/C++ compiler system. https:\/\/distcc.org\/.  M. Pool. distcc - a free distributed C\/C++ compiler system. https:\/\/distcc.org\/."},{"key":"e_1_2_1_60_1","unstructured":"PostgreSQL BuildFarm. https:\/\/buildfarm.postgresql.org.  PostgreSQL BuildFarm. https:\/\/buildfarm.postgresql.org."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/SASO.2013.13"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/1594977.1592603"},{"key":"e_1_2_1_63_1","volume-title":"Redundancy and Availability in Your IT Infrastructure. Independently Published","author":"Ramirez N.","year":"2016"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544813"},{"key":"e_1_2_1_65_1","unstructured":"A. Rodland. Improving load balancing with a new consistent-hashing algorithm. https:\/\/medium.com\/vimeo-engineering-blog\/improving-load-balancing-with-a-new-consistent-hashing-algorithm\\-9f1bd75709ed December 2016.  A. Rodland. Improving load balancing with a new consistent-hashing algorithm. https:\/\/medium.com\/vimeo-engineering-blog\/improving-load-balancing-with-a-new-consistent-hashing-algorithm\\-9f1bd75709ed December 2016."},{"key":"e_1_2_1_66_1","unstructured":"ROS Buildfarm. http:\/\/wiki.ros.org\/buildfarm.  ROS Buildfarm. http:\/\/wiki.ros.org\/buildfarm."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.5555\/646591.697650"},{"key":"e_1_2_1_68_1","first-page":"455","volume-title":"13th USENIX Symposium on Networked Systems Design and Implementation, NSDI '16","author":"Shalita A.","year":"2016"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.5555\/3026852.3026862"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.179115"},{"key":"e_1_2_1_71_1","doi-asserted-by":"crossref","unstructured":"R. Soni. Nginx: From Beginner to Pro. Apress Berkely CA USA 1st edition 2016.   R. Soni. Nginx: From Beginner to Pro. Apress Berkely CA USA 1st edition 2016.","DOI":"10.1007\/978-1-4842-1656-9_1"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634169"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159696"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/964723.383071"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.3156"},{"key":"e_1_2_1_76_1","unstructured":"W. Tarreau. HAProxy: The reliable high performance TCP\/HTTP load balancer. https:\/\/www.haproxy.org\/.  W. Tarreau. HAProxy: The reliable high performance TCP\/HTTP load balancer. https:\/\/www.haproxy.org\/."},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556195.2556213"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433461"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/2829988.2787497"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2007.893881"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/2967360.2967374"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113285"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2007.370231"},{"key":"e_1_2_1_84_1","volume-title":"USA","author":"Zhao B. Y.","year":"2001"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3311880.3311887","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:17:54Z","timestamp":1672219074000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3311880.3311887"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2]]},"references-count":84,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,2]]}},"alternative-id":["10.14778\/3311880.3311887"],"URL":"https:\/\/doi.org\/10.14778\/3311880.3311887","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,2]]}}}