1 Introduction 2 Overview - USENIX

1 USENIX Association 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13) 385 Scaling Memcache at FacebookRajesh Nishtala, Hans Fugal, Steven Grimm, Marc Kwiatkowski, Herman Lee, Harry C. Li,Ryan McElroy, Mike Paleczny, Daniel Peek, Paul Saab, David Stafford, Tony Tung,Venkateshwaran hcli, rm, mpal, dpeek, ps, dstaff, ttung, :Memcachedis a well known, simple, in-memory caching solution. This paper describes howFacebook leveragesmemcachedas a building block toconstruct and scale a distributed key-value store thatsupports the world s largest social network. Our systemhandles billions of requests per second and holds tril-lions of items to deliver a rich experience for over a bil-lion users around the IntroductionPopular and engaging social networking sites presentsignificant infrastructure challenges.

2 Hundreds of mil-lions of people use these networks every day and im-pose computational, network, and I/O demands that tra-ditional web architectures struggle to satisfy. A socialnetwork s infrastructure needs to (1) allow near real -time communication, (2) aggregate content on-the-flyfrom multiple sources, (3) be able to access and updatevery popular shared content, and (4) scale to processmillions of user requests per describe how we improved the open source ver-sion ofmemcached[14] and used it as a building block toconstruct a distributed key-value store for the largest so-cial network in the world. We discuss our journey scal-ing from a single cluster of servers to multiple geograph-ically distributed clusters. To the best of our knowledge,this system is the largestmemcachedinstallation in theworld, processing over a billion requests per second andstoring trillions of paper is the latest in a series of works that haverecognized the flexibility and utility of distributed key-value stores [1, 2, 5, 6, 12, 14, 34, 36].

3 This paper fo-cuses onmemcached an open-source implementationof an in-memory hash table as it provides low latencyaccess to a shared storage pool at low cost. These quali-ties enable us to build data-intensive features that wouldotherwise be impractical. For example, a feature thatissues hundreds of database queries per page requestwould likely never leave the prototype stage because itwould be too slow and expensive. In our application,however, web pages routinely fetch thousands of key-value pairs of our goals is to present the important themesthat emerge at different scales of our deployment. Whilequalities like performance, efficiency, fault-tolerance,and consistency are important at all scales, our experi-ence indicates that at specific sizes some qualities re-quire more effort to achieve than others. For exam-ple, maintaining data consistency can be easier at smallscales if replication is minimal compared to larger oneswhere replication is often necessary.

4 Additionally, theimportance of finding an optimal communication sched-ule increases as the number of servers increase and net-working becomes the paper includes four main contributions: (1)We describe the evolution of Facebook smemcached-based architecture. (2) We identify enhancements tomemcachedthat improve performance and increasememory efficiency. (3) We highlight mechanisms thatimprove our ability to operate our system at scale. (4)We characterize the production workloads imposed onour OverviewThe following properties greatly influence our , users consume an order of magnitude more con-tent than they create. This behavior results in a workloaddominated by fetching data and suggests that cachingcan have significant advantages. Second, our read op-erations fetch data from a variety of sources such asMySQL databases, HDFS installations, and backendservices.

5 This heterogeneity requires a flexible cachingstrategy able to store data from disparate a simple set of operations (set,get, anddelete) that makes it attractive as an elemen-tal component in a large-scale distributed system. Theopen-source version we started with provides a single-machine in-memory hash table. In this paper, we discusshow we took this basic building block, made it more ef-ficient, and used it to build a distributed key-value storethat can process billions of requests per second. Hence-386 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13) USENIX Associationdatabasewebservermemcache1. get k2. SELECT ..3. set (k,v)databasewebservermemcache2. delete k1. UPDATE ..Figure1 ,weuse memcached torefertothesourcecodeorarunningbinaryan d memcache , , , , , , , ,optimizing,provisioning, ,memcachedprovidesnoserver-to-serverco-o rdination; ,aggregation,androutingservicestoorganiz ememcachedinstancesintoadistributedsyste m.

6 Figure2 , , [8] , (1) (2)Wetreattheprob-abilityofreadingtransi entstaledataasaparametertobetuned, , ,thelatencyofmemcache sresponseisacriticalfactorintheresponset imeofauser Association 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13) , [22]. , [30] , ,includingserializa-tion,compression,req uestrouting,errorhandling, , (DAG) , ,eachthreadinthewebserverisallowedtodire ctlycommunicatewithmemcachedserversdirec tly,bypass-ingmcrouter,withoutestablishi ngandmaintaininga1 The95thpercentileoffetchesforthatpageis1 , of MediansAverage of 95th Percentilesmicroseconds020060010001400 UDP directby mcrouter (TCP)Figure3:GetlatencyforUDP, (usingsequencenumbers) , , , , , (updatesanddeletes) , ,median, ,thestandarddeviationfromtheseaverageswa slessthan1%.Asthedatashow,relyingonUDPca nleadtoa20% 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13) USENIX Association100200300400500010203040 Window Sizemilliseconds95th PercentileMedianFigure4:Averagetimewebre questsspendwaitingtobescheduledclientreq uestsalargenumberofkeys, [11] , scongestioncontrol, ; sLaw[26],L= W,thenumberofrequestsqueuedintheserver(L )isdirectlyproportionaltotheaveragetimea requesttakestoprocess(W),assumingthatthe inputrequestrateisconstant(whichitwasfor ourexperiment).

7 ,theapplicationwillhavetodispatchmoregro upsofmemcacherequestsse-rially, , , , , , [20]. , , ,whenwaitingclientsretrytherequest, ,allofthecachemissesresultedinapeakdatab asequeryrateof17 , , :Withleases,wecanminimizetheappli-cation ,itsvalueistransferredtoadatastruc-USENI X Association 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13) 389 Minimum, mean, and maximumTerabytes20406080 DailyWeeklyLow churnDailyWeeklyHigh churnFigure5:Dailyandweeklyworkingsetofa high-churnfamilyandalow-churnkeyfamilytu rethatholdsrecentlydeleteditems, , ,memoryfootprints, ,wepartitionacluster (namedwildcard) , , ,wecollecttheminimum,average, , , (1)theapplicationroutinelyfetchesmanykey ssimultane-ously,(2)theentiredatasetfits inoneortwomemcachedserversand(3) , , ,ifwereplicateall100keystomul-tipleserve rs,aclient :(1)asmallnumberofhostsareinaccessibledu etoanetworkorserverfailureor(2) , [3].

8 ,namedGutter, , , 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13) USENIX ,asinglekeycanaccountfor20%ofaserver ,eachfailedrequestresultsinahitontheback ingstore, , ,thissys-temreducestherateofclient-visib lefailuresby99%andconverts10% 25% ,hitratesinthegutterpoolgenerallyexceed3 5%inunder4minutesandoftenapproach50%.Thu swhenafewmemcachedserversareunavailabled uetofailureorminornetworkincidents, ,na ,alongwithastorageclusterthatcontainthed atabases, ,tractablenetworkconfiguration, , ,awebserverthatmodifiesdataalsosendsinva lidationstoitsownclustertoprovideread-af ter-Memcache Mcrouter Update Operations Storage MySQL McSqueal Commit Log Storage Server Figure6:Invalidationpipelineshowingkeyst hatneedtobedeletedviathedaemon(mcsqueal) . [7].Wede-ployinvalidationdaemons(namedmc squeal) ,extractsanydeletes.

9 Indeed,only4% :Whilemcsquealcouldcon-tactmemcachedserv ersdirectly, , , ,thiswouldoftenrequirearollingrestartoft heen-tirememcacheinfrastructure,aslowand disruptivepro- USENIX Association 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13) 391A(Cluster)B(Region) ,embeddinginvalida-tionsinSQLstatements, whichdatabasescommitandstoreinreliablelo gs, ,especiallyforlarge, ,ournetworkshave40% ,lowerlatency, , (B)toaregionalpoolwhileleavingtheother(A ) ,however,aretwiceaslargeandaccessedmuchm orefrequently, ,datasetsize, ,anexistingonefails, coldcluster ( )toretrievedatafromthe warmcluster ( ) ,ifaclientinthecoldclus-terdoesadatabase update,andasubsequentrequestfromanotherc lientretrievesthestalevaluefromthewarmcl usterbeforethewarmclusterhasreceivedthei nvalidation, , , , , , , ;werelyonMySQL , 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13) USENIX Associationtipleregions, ,liketherestofthesystem, , , , , ,subsequentrequestscouldresultintherepli ca ,thatserver(1)setsare-motemarkerrkinther egion,(2)performsthewritetothemasterembe ddingkandrktobeinvalidatedintheSQLstatem ent,and(3) ,awebserverwillbeunabletofindthecachedda ta,checkwhetherrkexists, ,weexplicitlytradeadditionallatencywhent hereisacachemiss, ,deletingorevictingkeysisalwaysasafeacti on;itmayinducemoreloadondatabases, , , :Inter-regioncommunica-tionisexpensivesi ncedatahastotraverselargegeo-graphicaldi stances( ).

10 Association 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13) [9,10,28,25]. :(1)allowautomaticexpansionofthehashta-b letoavoidlook-uptimesdriftingtoO(n),(2)m aketheservermulti-threadedusingagloballo cktoprotectmul-tipledatastructures,and(3 ) (X5650) (12coresand12hyperthreads), [4]. ,thesecondsetisourcurrentmemcached, ,whilemissesrequireasinglestaticresponse (END) sustaineditems / secondhitsmisses02M4M6 MFigure7:Multigethitandmissperformanceco mparisonbymemcachedversionGet10 key multigetMax sustaineditems / secondTCPUDP01M2 MFigure8:Gethitperformancecomparisonfors inglegetsand10-keymultigetsoverTCPandUDP formsourTCPimplementationby13%forsingleg etsand8% , ,eachofwhichcontainspre-allocated, smetadata,key, , ,storagefornewitemsisdonebyevictingthele astrecentlyused(LRU) , 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13) USENIX , (LRU) , , (indexedbysec-ondsuntilexpiration) calledtheTransientItemCache.