Strategia pamięci podręcznej dla przekierowań URL: L1 LRU i L2 Redis

Warstwa przekierowań w skracaczu URL to jeden z niewielu systemów produkcyjnych, w których strategia pamięci podręcznej stanowi samą architekturę. Na ścieżce krytycznej (hot path) nie dzieje się właściwie nic innego — każde żądanie rozwiązuje klucz (krótki slug), odczytuje docelowy URL i wysyła 301 lub 302. Wszystko inne to observability i logika pomocnicza. To cache decyduje o tym, czy mediana żądania wynosi 800 mikrosekund, czy 12 milisekund.

Ten post dokumentuje strategię cache stojącą za usługą edge-redirect w Elido. Dwa poziomy, polityka usuwania wybrana w celu optymalizacji pod kątem tail latency zamiast hit rate, strategia rozgrzewania, która jest prostsza niż mogłoby się wydawać, oraz awarie, których doświadczyliśmy w ciągu 18 miesięcy na produkcji. Wpis p95 przekierowań < 15ms jako kamień milowy opisuje pełny budżet opóźnień; ten tekst to szczegółowa analiza specyfiki cache.

Dlaczego dwa poziomy#

Najprostsza architektura pamięci podręcznej dla usługi przekierowań to pojedynczy poziom: klaster Redis pomiędzy procesem przekierowania a bazą danych origin. Każde żądanie, które nie trafia do bazy, trafia do Redis; każde żądanie, które nie trafia do Redis, trafia do bazy. Przeskok do Redis dodaje około 1ms, gdy Redis znajduje się w tym samym regionie.

Dwuwarstwowe pamięci podręczne dodają warstwę in-process przed Redisem. Pierwszy poziom — nazwijmy go L1 — znajduje się w przestrzeni adresowej procesu przekierowania. Trafienie w L1 zwraca docelowy URL w ciągu kilkuset nanosekund, bez konieczności komunikacji sieciowej. Brak trafienia (miss) w L1 powoduje przejście do Redis (L2), który serwuje dane z sub-milisekundową latencją. Brak trafienia w L2 kończy się wywołaniem gRPC do origin przeciwko kanonicznej bazie Postgres.

Wybór między jedną a dwiema warstwami to w zasadzie pytanie o to, jak stabilne musi być Twoje tail latency. Redis jest szybki, ale nie jest darmowy. 1ms p50 do Redis staje się 4-6ms p99 pod obciążeniem, a p99.9 może przekroczyć 20ms przy jakimkolwiek przeciążeniu sieci. Przy SLO celującym w p95 < 15ms, każde trafienie w Redis pochłania znaczną część budżetu. Dla p99.9 < 50ms, ogon opóźnień Redis jest dominującym czynnikiem.

In-process LRU absorbuje klucze o najwyższej częstotliwości — te, które generują ponad 80% ruchu. Przy rozkładzie ruchu w Elido, 1000 najpopularniejszych krótkich linków odpowiada za ponad 70% żądań przekierowań. Te klucze łatwo obsłużyć in-process; długi ogon może trafiać do Redis bez pogarszania p95.

L1: LRU na poziomie procesu#

Cache L1 wykorzystuje Ristretto, tę samą bibliotekę LRU z polityką admission, której używają Caddy i Dgraph. Wybraliśmy ją z trzech powodów:

Współbieżne odczyty skalują się liniowo z rdzeniami CPU. Prostszy cache oparty na sync.Map osiąga limit przy około 4M operacji na sekundę na typowej maszynie edge POP; Ristretto utrzymuje ponad 30M w naszych benchmarkach.
Polityka admission TinyLFU zapobiega usuwaniu gorących kluczy przez jednorazowe operacje skanowania. Crawl bota, który dotknie 10 000 unikalnych slugów raz każdy, nie wypchnie naprawdę popularnych linków z pamięci podręcznej.
Ograniczona pamięć zamiast ograniczonej liczby kluczy. Możemy ustawić "użyj do 256MB" zamiast "przechowuj do 100 000 wpisów", co jest kluczowe dla planowania pojemności.

Konfiguracja, którą wdrażamy, wygląda następująco:

cache, err := ristretto.NewCache(&ristretto.Config{
    NumCounters: 10_000_000, // 10M liczników → śledzi ~1M elementów
    MaxCost:     256 << 20,   // 256MB
    BufferItems: 64,
    Metrics:     true,
})

NumCounters to rozmiar tabeli śledzenia częstotliwości TinyLFU; zasada kciuka w dokumentacji Ristretto to 10× oczekiwana liczba elementów. Przy budżecie 256MB i średnim rekordzie linku wynoszącym 200 bajtów, pełny cache mieści około 1.3M wpisów.

TTL dla wpisów L1 wynosi 60 sekund. Jest to celowo krótki czas. Cel przekierowania może zostać zmieniony w dashboardzie w dowolnym momencie, a cache L1 jest najtrudniejszą warstwą do inwalidacji (Redis może zostać inwalidowany przez publikację; L1 żyje w każdym procesie i wymaga skoordynowanej ścieżki inwalidacji).

60-sekundowy TTL oznacza, że w najgorszym przypadku nieaktualność danych trwa 60 sekund po aktualizacji celu. Dla większości zastosowań jest to akceptowalne; tam, gdzie nie jest (natychmiastowe zmiany celu podczas kampanii live), przycisk inwalidacji w dashboardzie wysyła fanout, który czyści wszystkie cache L1 w całej flocie. Fanout wykorzystuje Redis pub/sub na kanale, który każdy proces edge subskrybuje przy starcie.

L2: Klaster Redis z replikami do odczytu#

L2 to klaster Redis, wdrożony w każdym regionie (FRA, ASH, SGP). Odczyty trafiają do lokalnych replik; zapisy do regionalnego primary i są replikowane w ramach standardowego modelu asynchronicznego Redis.

Format danych jest niewielki. Rekord przekierowania w L2 wygląda tak:

KEY:   redirect:f.elido.me:abc123
VALUE: {"d":"https://shop.example.com/spring","f":0,"v":12}

Trzy pola: docelowy URL, flagi (włączone filtrowanie botów, wymagane hasło itp., spakowane w uint16) oraz wersja. Wersja to wersja wiersza z Postgres; pozwala nam wykryć nieaktualne wpisy cache podczas odczytu.

TTL w L2 wynosi 24 godziny. Jest to znacznie dłużej niż w L1, ponieważ L2 ma działającą ścieżkę inwalidacji: gdy link jest tworzony lub aktualizowany w bazie origin, API publikuje wiadomość Redis pub/sub do regionalnego kanału inwalidacji, a procesy przekierowań usuwają swoje wpisy L1; wpis L2 jest nadpisywany bezpośrednio przez warstwę API.

Inwalidacja pub/sub ma subtelną właściwość: jest stratna. Jeśli proces przekierowania jest restartowany w momencie publikacji wiadomości o inwalidacji, nie widzi jej, a jego cache L1 może serwować nieaktualną wartość przez maksymalnie 60 sekund. Akceptujemy to, ponieważ TTL stanowi zabezpieczenie — nieaktualność jest ograniczona czasowo.

Rozmiar klastra Redis w każdym POP jest mały. FRA uruchamia trzy węzły primary plus trzy repliki; cały zestaw danych mieści się w około 4GB. Przy naszym hit rate (98% L1, 1,8% L2, 0,2% origin przy normalnym obciążeniu), wymagania dotyczące przepustowości Redis są umiarkowane — zazwyczaj 5-15k operacji na sekundę w szczycie na POP, co mieści się w wydajności pojedynczego węzła primary, gdybyśmy musieli je skonsolidować.

Wybór polityki usuwania#

Polityka admission TinyLFU w Ristretto to wybór, który ma największe znaczenie dla tail latency.

Naiwny LRU usuwa ostatnio najrzadziej używany klucz, gdy potrzebuje zrobić miejsce. To działa dobrze, gdy wzorzec dostępu jest w miarę jednolity — klucze używane ostatnio są najbardziej prawdopodobne do ponownego użycia. System ten zawodzi w dwóch konkretnych przypadkach:

Obciążenia typu skanowanie. Crawl bota, który uderza w 50 000 unikalnych slugów w krótkich odstępach czasu, w naiwnym LRU usunie każdy gorący klucz i zastąpi go kluczami z crawla, do których nikt więcej nie zajrzy. Hit rate spada, origin odnotowuje skok obciążenia, a p95 rośnie, ponieważ większość żądań trafia teraz na wolną ścieżkę.
Nagłe skoki gorących kluczy. Link, który normalnie jest "zimny", ale nagle otrzymuje 100k żądań w 30 sekund (wirale w social media, start kampanii TV), musi zostać szybko zapisany w cache. W naiwnym LRU wyprze on jeden z istniejących gorących kluczy.

TinyLFU radzi sobie z obydwoma przypadkami. Polityka admission śledzi częstotliwość kluczy i dopuszcza nowy klucz do cache tylko wtedy, gdy jest on częściej używany niż kandydat do usunięcia. Jednorazowy crawl bota nie wypiera gorących kluczy, ponieważ klucze bota mają licznik częstotliwości równy 1. Gwałtownie popularny klucz trafia do cache, ale dopiero gdy jego częstotliwość przekroczy częstotliwość kandydata do usunięcia — co dzieje się w ciągu kilkuset żądań.

Koszt jest taki, że pierwsze 100-500 żądań dla nowo popularnego linku jest wolnych (trafia do L2 lub origin), dopóki polityka admission nie zdecyduje o jego zapisaniu. Dla większości zastosowań jest to właściwy kompromis; dla kampanii, o których wiemy z góry, że link odnotuje skok, mamy endpoint do pre-warmu opisany poniżej.

Rozgrzewanie cache#

Cache L2 startuje "na zimno" (cold-start), gdy uruchamiany jest nowy klaster Redis. Nie rozgrzewamy go z migawki (snapshot); pierwsze 5 minut po restarcie klastra to zwiększony ruch do origin, dopóki cache naturalnie się nie zapełni.

Cache L1 startuje na zimno, gdy proces przekierowania jest restartowany (wdrożenia, OOM, skalowanie). Pierwsze 30 sekund po restarcie procesu to żądania trafiające głównie do L2; przez kolejne 60 sekund L1 wypełnia się zestawem roboczym gorących kluczy. Całkowity wpływ cold-startu na obciążenie origin jest niewielki (większość procesów edge restartuje się znacznie rzadziej niż wynosi TTL cache).

Wyjątek: gdy menedżer kampanii publikuje link, o którym wie, że odnotuje nagły wzrost — URL z reklamy TV, informacja prasowa, ogłoszenie premiery — dashboard oferuje przełącznik "pre-warm". Przełączenie go wysyła puste żądanie przekierowania do usługi edge-redirect w każdym POP, co z wyprzedzeniem wypełnia L1. Jest to rozwiązanie mało eleganckie i rzadko konieczne; autoscaler radzi sobie z nieprzewidzianymi skokami wystarczająco dobrze. Pre-warm to odpowiedź na przewidywane skoki, gdzie latencja zimnego cache przez pierwsze 60 sekund byłaby widoczna.

Co się dzieje przy pełnym L1#

Cache L1 o rozmiarze 256MB zapełnia się w mniej niż minutę w typowym edge POP. Po zapełnieniu, każdy nowy klucz wymaga od polityki TinyLFU decyzji, czy powinien wyprzeć istniejący klucz.

Ciekawa obserwacja: przy naszym rozkładzie ruchu, hit rate L1 stabilizuje się na poziomie około 98% po rozgrzaniu. 2% braków trafień to długi ogon — około 30% linków, które generują mniej niż 30% ruchu i dlatego nie przekraczają progu częstotliwości TinyLFU. Te klucze nie trafiają do L1 i są obsługiwane przez L2, gdzie hit rate wynosi około 99%. Pozostałe 0,2% wszystkich żądań trafia do origin.

Mierzyliśmy ten rozkład przy trzech charakterystykach obciążenia — duży ruch botów, wiralowy skok, stan ustalony — i hit rate L1 waha się między 95% a 99%. Hit rate L2 jest bardziej stabilny i wynosi 98-99,5%. Całkowite obciążenie origin z warstwy przekierowań jest zatem ograniczone do około 0,5% przychodzącego ruchu, co jest kluczową liczbą dla planowania wydajności origin.

Szczegóły inwalidacji cache#

Przepływ inwalidacji jest częścią najczęściej źle rozumianą przez osoby analizujące architekturę z zewnątrz. Szczegóły:

Gdy API otrzyma PATCH /v1/links/{id}, który zmienia docelowy URL, dzieją się kolejno trzy rzeczy:

Postgres zatwierdza zmianę z nową wersją wiersza (UPDATE links SET destination = ?, version = version + 1 WHERE id = ?).
Następuje bezpośredni zapis do Redis z nową wartością w każdym regionalnym klastrze Redis. Zapis jest rozsyłany (fanout) z API do każdego regionu Redis przez warstwę write-through.
Publikowana jest inwalidacja pub/sub na każdym regionalnym kanale invalidate:redirect. Procesy edge redirect subskrybują ten kanał przy starcie i usuwają wpis L1 dla danego klucza.

Kolejność ma znaczenie. Postgres jako pierwszy gwarantuje, że kanoniczny magazyn ma nową wartość. Zapis do Redis przed publikacją gwarantuje, że każdy proces, który przegapi publikację, ale odczyta z Redis, zobaczy nową wartość. Publikacja jest optymalizacją utrzymującą L1 w synchronizacji; TTL jest zabezpieczeniem w razie przegapienia publikacji.

Znany race condition: proces przekierowania, który czyta z Redis (z powodu braku w L1) i jednoczesna publikacja inwalidacji. Odczyt może zwrócić nową wartość (publikacja nastąpiła tuż przed odczytem) lub starą (publikacja nastąpiła tuż po). Jeśli zostanie zwrócona stara wartość i zapisana w L1, przez następne 60 sekund ten proces może serwować starą wartość. Jest to akceptowalne; alternatywa — synchroniczna blokada wokół wyścigu odczyt-publikacja — dodawałaby opóźnienie do każdego żądania, aby uniknąć przypadku brzegowego dotyczącego mniej niż 0,01% inwalidacji.

W przypadkach, gdy okno nieaktualności jest nieakceptowalne (docelowy URL jest usuwany z powodów prawnych, cel nagle stał się złośliwy), akcja "purge cache" w dashboardzie uruchamia agresywną inwalidację: wstrzymuje wszystkie odczyty L1 na 100ms w całej flocie, usuwa klucz z każdego L1, a następnie wznawia działanie. Jest to używane rzadko i objęte limitem wywołań na sekundę.

Awarie, których doświadczyliśmy#

Trzy awarie z 18-miesięcznej historii produkcji, które warto udokumentować, ponieważ ukształtowały obecną konfigurację.

Failover primary Redis z nieaktualnymi replikami. W 4. miesiącu produkcji zawiódł węzeł primary w klastrze FRA. Replika została wypromowana w ciągu 30 sekund (failover sterowany przez Sentinel). Repliki spóźniały się o około 200ms względem primary w momencie awarii, co oznaczało, że pierwsze kilkaset inwalidacji opublikowanych tuż przed failoverem nie dotarło do wypromowanej repliki. Wynik: krótkie okno, w którym około 0,3% przekierowań serwowało nieaktualne cele. Rozwiązanie: obecnie uruchamiamy repliki z min-replicas-to-write 1 i min-replicas-max-lag 10, co poświęca nieco dostępności zapisu na rzecz ściślejszej gwarancji opóźnienia replikacji.

Thrashing pamięci podręcznej L1 podczas skanowania przez monitoring syntetyczny. W 9. miesiącu zewnętrzna usługa monitorowania uptime została błędnie skonfigurowana, aby sprawdzać każdy krótki link w workspace klienta raz na minutę. Klient miał 18 000 krótkich linków. Wzorce próbkowania stanowiły kompletne skanowanie co 60 sekund. Efekt: hit rate cache L1 spadł z 98% do 71% w trzech edge POP, ponieważ wzorzec skanowania dopuszczał każdy sprawdzany klucz do cache. Rozwiązanie: dodaliśmy filtrowanie oparte na User-Agent przed warstwą admission cache — znane agenty monitorujące omijają cache i serwują dane bezpośrednio z L2. Był to przypadek brzegowy TinyLFU: klucze skanowania wydawały się wystarczająco częste, by wyprzeć autentycznie gorące klucze.

Rozłączenie pub/sub podczas długotrwałego wdrożenia. W 13. miesiącu wdrożenie, które trwało dłużej niż oczekiwano (około 4 minuty), spowodowało, że kilka procesów edge pozostało połączonych ze starym kanałem pub/sub po failoverze primary Redis. Inwalidacje publikowane do nowego primary nie docierały do tych procesów; ich cache L1 serwowały nieaktualne wartości przez czas trwania wdrożenia. Rozwiązanie: heartbeat połączenia pub/sub z automatycznym ponownym łączeniem przy braku sygnału oraz czyszczenie L1 podczas wdrożenia jako środek ostrożności.

Co rozważaliśmy i odrzuciliśmy#

Kilka alternatyw ocenionych i niewybranych:

Pojedynczy cache in-process, bez Redis. Przetestowane. Współczynnik miss-to-origin w dowolnym pojedynczym procesie jest zbyt wysoki bez L2; baza danych origin wymagałaby 3-5× większej pojemności. Marginalny koszt Redis jest mały w porównaniu do oszczędności pojemności origin.

CDN typu Cloudflare lub Fastly do cachowania przekierowań. Przetestowane w stagingu. Opóźnienie regionalne CDN na poziomie 1-2ms przy trafieniu w cache jest zbliżone do Redis, ale inwalidacja jest znacznie trudniejsza (czyszczenie CDN ma minutowe opóźnienia i koszty za każdy URL). CDN dodał złożoności bez poprawy latencji czy hit rate.

Większe L1. Budżet 256MB jest dopasowany do limitów pamięci procesu; podwojenie go nie podwaja hit rate, ponieważ gorący zestaw roboczy już się w nim mieści. Spadek korzyści krańcowych zaczyna się przy około 128MB przy naszym rozkładzie; 256MB daje zapas na wzrost ruchu.

Observability#

Metryki, które śledzimy na każdy proces edge:

cache_l1_hit_total, cache_l1_miss_total — wyliczony hit rate na proces.
cache_l2_hit_total, cache_l2_miss_total — wyliczony hit rate na region.
cache_origin_request_total — wolumen żądań do origin; cel SLO to < 1% wszystkich żądań.
cache_invalidation_total{source="pubsub|ttl|purge"} — liczba inwalidacji według mechanizmu.
cache_l1_memory_bytes — faktyczna pamięć używana przez cache L1; alarm przy 90% skonfigurowanego budżetu.

Wszystkie metryki są zbierane przez Prometheus i wizualizowane w zestawie dashboardów przewodnika observability. Dashboardy Grafana na poziomie regionalnym pokazują regionalny hit rate cache w czasie; dashboardy per-proces (używane podczas incydentów) pokazują hit rate L1 i zużycie pamięci przez dany proces.

Kiedy stosować tę strategię, a kiedy nie#

Dwuwarstwowy cache ma sens, gdy:

Obciążenie jest zdominowane przez odczyty z długim ogonem rozkładu kluczy.
Gorący zestaw roboczy mieści się w pamięci procesu (kilkaset megabajtów).
Brak trafienia w cache jest na tyle kosztowny, że druga warstwa znacząco odciąża bazę danych.
Budżet nieaktualności danych jest na tyle mały, że sam TTL w L1 nie jest akceptowalny.

Nie ma on sensu, gdy:

Gorący zestaw roboczy nie mieści się w pamięci procesu. W takim przypadku braki w L1 trafiają do L2 na tyle często, że L1 wnosi niewiele.
Zapisy są częste w stosunku do odczytów. Koszt inwalidacji dominuje.
Dane są unikalne dla każdego żądania (brak korzyści z cachowania).

Dla specyfiki pracy skracacza URL wszystkie cztery warunki na "tak" są spełnione, a powyższa konfiguracja sprawdziła się podczas 18 miesięcy wzrostu produkcji. Dla innych obciążeń liczba warstw i polityka usuwania wymagają ponownej oceny.

Dodatkowe materiały#

Osiąganie p95 < 15ms dla przekierowań z FRA, ASH i SGP — kluczowy wpis dla klastra engineering; ten post to pogłębiona analiza specyfiki cache.
Dlaczego używamy ClickHouse do analityki kliknięć (a nie Postgres) — powiązana decyzja inżynierska w tej samej architekturze.
Ingest kliknięć typu fire-and-forget z Redpanda — potok zdarzeń kliknięć działający obok cache przekierowań.
Krótkie linki jako Terraform — operacyjny opis konfiguracji warstwy przekierowań.
Architektura edge: /docs/architecture/edge-redirect.
Przewodnik operacyjny: /docs/guides/observability — opisany wyżej zestaw dashboardów metryk.
Oferta produktowa: /solutions/developers oraz /solutions/analytics.
Materiały zewnętrzne: Artykuł o projektowaniu Ristretto oraz dokumentacja TinyLFU dotycząca teorii polityki admission.