Cache stampede
En cache-stampede är en typ av kaskadfel som kan uppstå när massivt parallella datorsystem med cachningsmekanismer utsätts för mycket hög belastning. Det här beteendet kallas ibland också för hundpålning .
För att förstå hur cache-stämplingar uppstår, överväg en webbserver som använder memcached för att cachelagra renderade sidor under en viss tidsperiod, för att underlätta systembelastningen. Under särskilt hög belastning på en enda URL förblir systemet responsivt så länge som resursen förblir cachad, med förfrågningar som hanteras genom att komma åt den cachade kopian. Detta minimerar den dyra återgivningsoperationen.
Under låg belastning resulterar cachemissar i en enda omräkning av renderingsoperationen. Systemet kommer att fortsätta som tidigare, med den genomsnittliga belastningen som hålls mycket låg på grund av den höga träffhastigheten för cache.
Men under mycket tung belastning, när den cachade versionen av den sidan löper ut, kan det finnas tillräcklig samtidighet i serverfarmen för att flera exekveringstrådar alla kommer att försöka rendera innehållet på den sidan samtidigt. Systematiskt vet ingen av de samtidiga servrarna att de andra gör samma rendering samtidigt. Om tillräckligt hög belastning är närvarande kan detta i sig vara tillräckligt för att få till överbelastningskollaps av systemet via uttömmande delade resurser. Överbelastningskollaps leder till att sidan inte någonsin renderas om och cachelagras igen, eftersom varje försök att göra det tar timeout. Således minskar cache-stampe cacheträffhastigheten till noll och håller systemet kontinuerligt i trängselkollaps när det försöker återskapa resursen så länge som belastningen förblir mycket tung.
För att ge ett konkret exempel, anta att den aktuella sidan tar 3 sekunder att rendera och att vi har en trafik på 10 förfrågningar per sekund. Sedan, när den cachelagrade sidan går ut, har vi 30 processer som samtidigt beräknar om renderingen av sidan och uppdaterar cachen med den renderade sidan.
Typisk cacheanvändning
Nedan är ett typiskt cacheanvändningsmönster för ett objekt som behöver uppdateras varje ttl -tidsenhet:
function fetch( key , ttl ) { value ← cache_read( key ) if (! value ) { value ← recompute_value() cache_write( key , value , ttl ) } return value }
Om funktionen recompute_value() tar lång tid och nyckeln används ofta, kommer många processer samtidigt att anropa recompute_value() när cachevärdet löper ut.
I typiska webbapplikationer kan funktionen recompute_value() fråga efter en databas, komma åt andra tjänster eller utföra någon komplicerad operation (vilket är anledningen till att just den här beräkningen cachelagras i första hand). När begärandefrekvensen är hög kommer databasen (eller någon annan delad resurs) att drabbas av en överbelastning av förfrågningar/frågor, vilket i sin tur kan orsaka att systemet kollapsar.
Cache-stämpelreducering
Flera tillvägagångssätt har föreslagits för att mildra cache-stämplingar (även känd som dogpile prevention). De kan grovt grupperas i 3 huvudkategorier.
Låsning
För att förhindra flera samtidiga omberäkningar av samma värde, vid en cachemiss kommer en process att försöka skaffa låset för den cachenyckeln och beräkna om den endast om den förvärvar den.
Det finns olika implementeringsalternativ för fallet när låset inte är förvärvat:
- Vänta tills värdet har beräknats om
- Returnera en "not-found" och låt klienten hantera frånvaron av värdet på rätt sätt
- Behåll ett inaktuellt objekt i cachen som ska användas medan det nya värdet beräknas om
Om den implementeras på rätt sätt kan låsning förhindra stampede helt och hållet, men kräver en extra skrivning för låsmekanismen. Förutom att fördubbla antalet skrivningar, är den största nackdelen en korrekt implementering av låsmekanismen som också tar hand om kantfall inklusive misslyckande i processen för att hämta låset, inställning av en livslängd för låset, race-villkor , och så vidare.
Extern omräkning
Denna lösning flyttar omräkningen av cachevärdet från de processer som behöver det till en extern process. Omräkningen av den externa processen kan utlösas på olika sätt:
- När cachevärdet närmar sig utgången
- Periodvis
- När en process som behöver värdet stöter på en cachemiss
Detta tillvägagångssätt kräver ytterligare en rörlig del - den externa processen - som måste underhållas och övervakas. Dessutom kräver den här lösningen onaturlig kodseparation/duplicering och är mest lämpad för statiska cache-nycklar (dvs. inte genererade dynamiskt, som i fallet med nycklar som indexeras av ett id).
Probabilistisk tidig utgång
Med detta tillvägagångssätt kan varje process beräkna cachevärdet på nytt innan det löper ut genom att fatta ett oberoende probabilistiskt beslut, där sannolikheten för att utföra den tidiga omräkningen ökar när vi närmar oss utgången av värdet. Eftersom det probabilistiska beslutet fattas oberoende av varje process, mildras effekten av stampede eftersom färre processer kommer att löpa ut samtidigt.
Följande implementering baserad på en exponentiell fördelning har visat sig vara optimal när det gäller dess effektivitet när det gäller att förhindra stampedes och hur tidiga omräkningar kan ske.
function x-fetch( key , ttl , beta =1) { value , delta , expiry ← cache_read( key ) if (! värde || (tid() - delta * beta * log(rand(0,1))) ≥ expiry ) { start ← time() värde ← recompute_value() delta ← time() – start cache_write( key , ( värde , delta ), ttl ) } returvärde }
Parametern beta kan ställas in på ett värde som är större än 1 för att gynna tidigare omräkningar och ytterligare minska stämplingar, men författarna visar att inställningen beta =1 fungerar bra i praktiken. Variabeln delta representerar tiden för att beräkna om värdet och används för att skala sannolikhetsfördelningen på lämpligt sätt.
Detta tillvägagångssätt är enkelt att implementera och minskar effektivt cache-stämplingar genom att automatiskt gynna tidiga omräkningar när trafikhastigheten ökar. En nackdel är att det tar mer minne i cachen då vi behöver bunta värdet delta med cache-objektet - när cachesystemet inte stöder hämtning av nyckelns utgångstid, måste vi också lagra utgången ( det vill säga tid( ) + ttl ) i bunten.
externa länkar
- Minimera cache-stämplingar , Joshua Thijssen, 2010
- Problem och lösningar för typisk perl-cacheanvändning, Jonathan Swartz, 2008