Cache Stampede у мобилном развоју: шта је то и методе заштите

Шта је Cache Stampede?

Cache Stampede (такође познат као cache thundering herd) — то је ситуација у којој велики број захтева истовремено открива промашај кеша и усмерава се ка извору података. Ово ствара вршно оптерећење које може довести до деградације или потпуног отказа система.

Типичан сценарио: мобилна апликација кешира заједничку листу производа са TTL = 5 минута. У 14:00 кеш истиче. 500 активних корисника истовремено отвара каталог, сваки открива празан кеш и свих 500 захтева лети ка серверу. База података или спољни API не могу да се изборе са изненадним током, страница се учитава 10–15 секунди, део захтева одлази у тајмаут.

Према подацима Vattani et al. (SOCC, 2015), Cache Stampede се јавља у сваком слоју кеширања са записима који истичу, укључујући CDN, Redis, Memcached, HTTP-кеш прегледача и кеш апликације у меморији. Што је запис популарнији — већа је потенцијална штета од 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)

Овај пример демонстрира заштиту кроз мјутекс: само прва нит ажурира кеш, остале чекају готов резултат. Механизам блокирања — најједноставнији, али ефикасан начин спречавања stampede-а за умерена оптерећења.

Зашто настаје лавина захтева при промашају кеша

Масовни истек TTL-а — главни узрок Cache Stampede-а. Када популарни запис у кешу има исти TTL за све клијенте, сви они истовремено откривају његово одсуство. Ово је типично за заједничке податке: курс валута, листа земаља, основна конфигурација апликације.

Колапс при поновном покретању сервера — ако се Redis или Memcached ресетује, цео кеш је празан. При првом врху саобраћаја, сви захтеви иду ка бази података. Према Amazon AWS Architecture Blog (2024), препоручује се загревање кеша након поновног покретања: постепено учитавање популарних записа како би се избегао нагли скок оптерећења.

Грешка у логици инвалидације — када програмер чисти кеш за све кориснике при промени једног елемента. На пример, у вести апликацији при објављивању једног чланка, инвалидира се цела листа вести. Стотине корисника истовремено откривају празан кеш — и сервер пада. Тачкаста инвалидација (само измењеног записа) отклања овај проблем.

Хладан старт апликације — на мобилним уређајима кеш постоји само у меморији процеса. Након поновног покретања апликације, кеш је празан и сви захтеви иду на сервер. Решење: чување кеша на диску између сесија (Room, SQLite) и коришћење претходног учитавања кључних података при старту.

Мјутексно блокирање за заштиту кеша

Идеја метода — при промашају кеша, прва нит преузима блокаду (lock) и почиње учитавање података из извора. Остале нити чекају завршетак блокаде и читају ажурирани кеш. Блокада може бити реализована кроз Redis SETNX, ZooKeeper или чак мјутекс у меморији.

Кључни параметар — lock_timeout. Ако је прекратак, прва нит можда неће стићи да ажурира кеш, а друга нит ће такође покушати да учита податке, стварајући мини-stampede. Ако је предуг — клијенти чекају дуже него потребно. Препоручена вредност: 2–5 секунди за типичне упите бази података.

Проблем једне нити — при отказу прве нити (изузетак, тајмаут) блокада остаје заузета, а све остале нити чекају до истека lock_timeout-а. Решење: уклањање блокаде у finally блоку. Према Redis Best Practices (2025), препоручује се коришћење Lua скрипти за атомско постављање и ослобађање блокада.

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

Ова Lua скрипта атомски проверава и поставља блокаду са TTL-ом. Атомичност гарантује да два истовремена захтева не могу добити блокаду — само један, што потпуно спречава Cache Stampede.

Probabilistic Early Expiration и алгоритам XFetch

Probabilistic Early Expiration (PEE) — елегантан метод без блокада. Идеја је да сваки клијент са одређеном вероватноћом поново израчунава кеш пре његовог стварног истека. Што је запис ближи истеку — већа је вероватноћа. Ово природно распоређује поновна учитавања у времену, а вршно оптерећење се изглађује.

Алгоритам XFetch — предложен од Vattani, Chierichetti и Panconesi (2015). Формула вероватноће: p = max(0, 1 - (beta * age / ttl)), где је beta — параметар неравномерности (обично 1.0). При age = 0 → p = 1 (гарантовано ажурирање при нултом узрасту, што је неправилно). Зато се користи модификација: p = max(0, (ttl - age) / (ttl * beta)).

Према подацима Etsy Engineering (2024), имплементација XFetch-а у Memcached-у смањила је број stampede догађаја са 12 дневно на 0, а вршно оптерећење базе података пало је за 78%. Рандомизирано ажурирање не захтева блокаде и синхронизацију, што чини XFetch идеалним за архитектуру микросервиса.

За мобилне клијенте, PEE се може применити на страни апликације: клијенти насумично покрећу ажурирање кеша пре него што он званично истекне. На пример, при age > 80% TTL, сваки захтев са 20% вероватноће ажурира податке. Распоређени мобилни уређаји стварају природни шум који додатно смањује вероватноћу синхроног удара.

Претходно ажурирање кеша

Идеја приступа — ажурирати кеш пре него што истекне, потпуно искључујући промашај. Позадински процес (cron, scheduler у Kubernetes-у) периодично проверава популарне кључеве и преписује их са новим TTL-ом. Клијенти увек проналазе кеш валидним — stampede је по дефиницији немогућ.

Time-To-Refresh (TTR) — параметар који одређује колико пре истека почети ажурирање. На пример, TTL = 300 секунди, TTR = 60 секунди: на ознаци 240 секунди позадински процес преписује податке. Ово гарантује да клијенти никада не виде празан кеш.

Недостатак претходног ажурирања — константно оптерећење извора података, чак и ако нико не захтева запис. За ретко коришћене податке ово је неефикасно. Решење: праћење учесталости захтева ка кључу (access frequency) и ажурирање само популарних записа. Адаптивни TTR — напредна техника где се интервал ажурирања динамички израчунава на основу историје захтева.

Који метод заштите изабрати

Мјутексно блокирање — погодно за системе са умереним оптерећењем (до 10 000 rps по кључу). Једноставно за имплементацију и гарантује да извор прима само један захтев за ажурирање. Недостатак — блокаде стварају кашњење за нити које чекају.

Probabilistic Early Expiration / XFetch — оптималан за висока оптерећења и дистрибуиране системе. Не захтева блокаде, скалира се хоризонтално, вршно оптерећење се природно изглађује. Препоручује се за Redis-кластере и Memcached са хиљадама клијената.

Претходно ажурирање — идеално за критично важне податке са предвидивим обрасцем приступа (конфигурације, речници, основни метаподаци). Захтева додатну инфраструктуру за позадински процес.

Диск кеш на клијенту — за мобилне апликације најважнији ниво заштите. Чак и ако је серверски кеш инвалидиран, мобилни клијент може приказати податке са диска док се нови захтев извршава. Room + Stale-While-Revalidate — препоручени образац од Google-а (2025), који потпуно искључује Cache Stampede на клијенту.