Cache Stampede sa mobile development: ano ito at mga paraan ng proteksyon

Ano ang Cache Stampede?

Cache Stampede (kilala rin bilang cache thundering herd) — ay isang sitwasyon kung saan ang malaking bilang ng mga kahilingan ay sabay-sabay na nakakatuklas ng cache miss at napupunta sa pinagmumulan ng data. Ito ay lumilikha ng peak load na maaaring humantong sa pagkasira o kumpletong pagbagsak ng system.

Karaniwang senaryo: ang isang mobile app ay nag-cache ng isang karaniwang listahan ng produkto na may TTL = 5 minuto. Sa 14:00 nag-expire ang cache. 500 aktibong user ang sabay-sabay na nagbubukas ng catalog, bawat isa ay nakakatuklas ng walang laman na cache at lahat ng 500 kahilingan ay lumilipad sa server. Ang database o external na API ay hindi makayanan ang biglaang daloy, ang page ay naglo-load ng 10-15 segundo, ang ilang mga kahilingan ay nagti-timeout.

Ayon sa datos ng Vattani et al. (SOCC, 2015), ang Cache Stampede ay nangyayari sa anumang cache layer na may nag-e-expire na mga entry, kabilang ang CDN, Redis, Memcached, HTTP cache ng browser, at in-memory cache ng app. Kung mas sikat ang entry — mas malaki ang potensyal na pinsala mula sa stampede.

def mutex_get(key, lock_timeout=5):
    cached = cache.get(key)
    if cached is not None:
        return cached
    if lock.acquire(key, lock_timeout):
        data = source.load(key)
        cache.set(key, data)
        lock.release(key)
        return data
    sleep(0.01)
    return mutex_get(key, lock_timeout)

Ang halimbawang ito ay nagpapakita ng proteksyon sa pamamagitan ng mutex: tanging ang unang thread ang nag-a-update ng cache, ang iba ay naghihintay ng handa na resulta. Ang mekanismo ng pag-lock — ang pinakasimple ngunit epektibong paraan upang maiwasan ang stampede para sa katamtamang pagkarga.

Bakit nangyayari ang baha ng mga kahilingan kapag cache miss

Maramihang pag-expire ng TTL — ang pangunahing sanhi ng Cache Stampede. Kapag ang isang sikat na cache entry ay may parehong TTL para sa lahat ng kliyente, lahat sila ay sabay-sabay na natutuklasan ang kawalan nito. Ito ay tipikal para sa karaniwang data: halaga ng palitan, listahan ng mga bansa, pangunahing configuration ng app.

Pagbagsak sa restart ng server — kung ang Redis o Memcached ay na-reset, ang buong cache ay magiging walang laman. Sa unang peak ng trapiko, lahat ng kahilingan ay pupunta sa database. Ayon sa Amazon AWS Architecture Blog (2024), inirerekomenda na painitin ang cache pagkatapos ng restart: unti-unting mag-load ng mga sikat na entry upang maiwasan ang biglaang pagtaas ng pagkarga.

Error sa invalidation logic — kapag nilinis ng developer ang cache para sa lahat ng user sa pagbabago ng isang elemento. Halimbawa, sa isang news app kapag nag-publish ng isang artikulo, ang buong listahan ng balita ay na-invalidate. Daan-daang user ang sabay-sabay na nakakatuklas ng walang laman na cache — at bumabagsak ang server. Point invalidation (tanging ng binagong entry) ay nag-aalis ng problemang ito.

Cold start ng app — sa mga mobile device, ang cache ay umiiral lamang sa memorya ng proseso. Pagkatapos ng restart ng app, walang laman ang cache at lahat ng kahilingan ay pupunta sa server. Solusyon: i-save ang cache sa disk sa pagitan ng mga session (Room, SQLite) at gumamit ng preloading ng mahahalagang data sa pagsisimula.

Pag-lock ng Mutex para sa proteksyon ng cache

Ideya ng pamamaraan — kapag cache miss, ang unang thread ay kumukuha ng lock at magsisimulang mag-load ng data mula sa pinagmulan. Ang iba pang mga thread ay naghihintay para sa pagkumpleto ng lock at binabasa ang na-update na cache. Ang lock ay maaaring ipatupad sa pamamagitan ng Redis SETNX, ZooKeeper, o kahit isang in-memory mutex.

Ang pangunahing parameter — lock_timeout. Kung masyadong maikli, maaaring hindi magawa ng unang thread na i-update ang cache, at susubukan din ng pangalawang thread na mag-load ng data, na lumilikha ng mini-stampede. Kung masyadong mahaba — ang mga kliyente ay naghihintay nang mas matagal kaysa kinakailangan. Inirerekomendang halaga: 2-5 segundo para sa tipikal na database request.

Problema ng isang thread — sa pagkabigo ng unang thread (exception, timeout), ang lock ay nananatiling nakuha at lahat ng iba pang thread ay naghihintay hanggang sa mag-expire ang lock_timeout. Solusyon: tanggalin ang lock sa finally block. Ayon sa Redis Best Practices (2025), inirerekomenda ang paggamit ng Lua script para sa atomikong pag-set at pag-release ng mga lock.

-- Atomic lock acquisition script for Redis
if redis.call("SET", KEYS[1], "locked", "NX", "EX", ARGV[1]) then
    return true
else
    return false
end

Ang Lua script na ito ay atomikong sumusuri at nagse-set ng lock na may TTL. Ang atomicity ay ginagarantiyahan na ang dalawang sabay na kahilingan ay hindi makakakuha ng lock — isa lamang, na ganap na pumipigil sa Cache Stampede.

Probabilistic Early Expiration at algorithm na XFetch

Probabilistic Early Expiration (PEE) — isang eleganteng pamamaraan na walang lock. Ang ideya ay ang bawat kliyente na may tiyak na posibilidad ay muling kinakalkula ang cache bago ang aktwal na pag-expire nito. Kung mas malapit ang entry sa pag-expire — mas mataas ang posibilidad. Ito ay natural na namamahagi ng mga reload sa oras, at ang peak load ay napapakinis.

Algorithm na XFetch — iminungkahi ni Vattani, Chierichetti at Panconesi (2015). Formula ng posibilidad: p = max(0, 1 - (beta * age / ttl)), kung saan beta — parameter ng hindi pagkakapantay-pantay (karaniwang 1.0). Sa age = 0 → p = 1 (garantisadong pag-update sa zero edad, na hindi tama). Kaya naman ginagamit ang modipikasyon: p = max(0, (ttl - age) / (ttl * beta)).

Ayon sa datos ng Etsy Engineering (2024), ang implementasyon ng XFetch sa Memcached ay nagbawas ng bilang ng mga stampede event mula 12 bawat araw hanggang 0, at ang peak load ng database ay bumaba ng 78%. Ang random na pag-update ay hindi nangangailangan ng mga lock at synchronization, na ginagawang perpekto ang XFetch para sa arkitekturang microservice.

Para sa mga mobile client, ang PEE ay maaaring ilapat sa side ng app: ang mga kliyente ay random na nag-iinitiate ng pag-update ng cache bago ang opisyal na pag-expire. Halimbawa, sa age > 80% TTL, ang bawat kahilingan na may 20% posibilidad ay nag-a-update ng data. Ang mga distributed mobile device ay lumilikha ng natural na ingay na dagdag na nagbabawas ng posibilidad ng synchronus impact.

Preventive na pag-update ng cache

Ideya ng approach — i-update ang cache bago ito mag-expire, ganap na inaalis ang cache miss. Isang background process (cron, scheduler sa Kubernetes) ang pana-panahong sumusuri sa mga sikat na key at tinatakpan ang mga ito ng bagong TTL. Ang mga kliyente ay laging nakakakita ng cache na valid — ang stampede ay imposible sa depinisyon.

Time-To-Refresh (TTR) — parameter na tumutukoy kung gaano katagal bago mag-expire magsisimula ang pag-update. Halimbawa, TTL = 300 segundo, TTR = 60 segundo: sa markang 240 segundo, ang background process ay nag-o-overwrite ng data. Ito ay ginagarantiyahan na ang mga kliyente ay hindi kailanman nakakakita ng walang laman na cache.

Kahinaan ng preventive na pag-update — patuloy na pagkarga sa pinagmumulan ng data, kahit na walang humihiling ng entry. Para sa madalang na ginagamit na data, ito ay hindi epektibo. Solusyon: subaybayan ang dalas ng mga kahilingan sa key (access frequency) at i-update lamang ang mga sikat na entry. Adaptive TTR — isang advanced na pamamaraan kung saan ang interval ng pag-update ay dinamikong kinakalkula batay sa kasaysayan ng mga kahilingan.

Aling paraan ng proteksyon ang pipiliin

Pag-lock ng Mutex — angkop para sa mga system na may katamtamang pagkarga (hanggang 10 000 rps bawat key). Simple i-implement at ginagarantiyahan na ang pinagmulan ay tumatanggap lamang ng isang kahilingan para sa pag-update. Kahinaan — ang mga lock ay lumilikha ng pagkaantala para sa mga naghihintay na thread.

Probabilistic Early Expiration / XFetch — pinakamainam para sa mataas na pagkarga at distributed system. Hindi nangangailangan ng mga lock, nag-scale nang pahalang, ang peak load ay natural na napapakinis. Inirerekomenda para sa Redis cluster at Memcached na may libu-libong kliyente.

Preventive na pag-update — perpekto para sa kritikal na data na may predictable access pattern (configuration, direktoryo, pangunahing metadata). Nangangailangan ng karagdagang imprastraktura para sa background process.

Cache sa disk sa kliyente — para sa mga mobile app, ang pinakamahalagang antas ng proteksyon. Kahit na ang server cache ay na-invalidate, ang mobile client ay maaaring magpakita ng data mula sa disk habang ang isang bagong kahilingan ay isinasagawa. Room + Stale-While-Revalidate — ang inirerekomendang pattern ng Google (2025), na ganap na nag-aalis ng Cache Stampede sa side ng kliyente.