Стратегія кешування для перенаправлень URL: L1 LRU та L2 Redis

Рівень перенаправлення (redirect tier) сервісу скорочення URL — це одна з небагатьох продуктових систем, де стратегія кешування і є архітектурою. На гарячому шляху (hot path) не відбувається жодної іншої значущої роботи — кожен запит розв'язує ключ (короткий слаг), зчитує цільову URL-адресу та видає 301 або 302 відповідь. Все інше — це спостережуваність та облік. Саме кеш визначає, чи триватиме середній запит 800 мікросекунд або 12 мілісекунд.

Цей допис документує стратегію кешування сервісу edge-redirect компанії Elido. Два рівні, політика витіснення, обрана для оптимізації затримки у хвості розподілу (tail latency), а не коефіцієнта влучань (hit rate), стратегія розігріву, яка простіша, ніж здається, і сценарії збоїв, які ми спостерігали за 18 місяців експлуатації. Стаття redirect p95 < 15ms cornerstone охоплює повний бюджет затримок; це ж — глибоке занурення саме в особливості кешування.

Чому два рівні#

Найпростіша архітектура кешу для сервісу перенаправлення — це один рівень: Redis cluster між процесом перенаправлення та основною базою даних. Кожен запит, який не потрапляє в базу даних, потрапляє в Redis; кожен запит, який не потрапляє в Redis, потрапляє в базу даних. Перехід до Redis додає близько 1 мс, якщо Redis знаходиться в тому ж регіоні.

Дворівневі кеші додають внутрішньопроцесний рівень перед Redis. Перший рівень — назвемо його L1 — знаходиться безпосередньо в адресному просторі процесу перенаправлення. Влучання в L1 повертає цільову URL-адресу за кілька сотень наносекунд, не потребуючи мережевого запиту. Промах у L1 переходить до Redis (L2), який обслуговує запит із затримкою менше мілісекунди. Промах у L2 переходить до виклику origin gRPC до канонічної бази даних Postgres.

Вибір між одним та двома рівнями — це, по суті, питання того, наскільки стабільною має бути затримка у хвості розподілу. Redis швидкий, але не безкоштовний. 1 мс p50 для Redis перетворюється на 4-6 мс p99 під навантаженням, а p99.9 може перевищувати 20 мс при будь-яких мережевих заторах. Для SLO, яке цілиться в p95 < 15ms, кожне влучання в Redis споживає значну частину бюджету. Для p99.9 < 50ms хвіст затримок Redis стає домінуючим фактором.

Внутрішньопроцесний LRU поглинає ключі з найвищою частотою — ті, що генерують понад 80% трафіку. При розподілі трафіку Elido перші 1000 коротких посилань за обсягом запитів складають понад 70% усіх запитів на перенаправлення. Ці ключі легко обслуговувати всередині процесу; «довгий хвіст» може переходити до Redis без погіршення p95.

L1: LRU на рівні процесу#

Кеш L1 використовує Ristretto — той самий LRU з політикою допуску (admission-policy), який використовують Caddy та Dgraph. Ми обрали його з трьох причин:

• Конкурентне читання масштабується лінійно з ядрами CPU. Простіший кеш на базі sync.Map зупиняється на позначці близько 4 млн операцій/сек на типовій машині edge POP; Ristretto стабільно видає понад 30 млн у наших бенчмарках.
• Політика допуску TinyLFU запобігає витісненню гарячих ключів одноразовими робочими навантаженнями сканування. Краулер-бот, який один раз звертається до 10 000 унікальних слагів, не витіснить з кешу справді популярні посилання.
• Обмеження за пам'яттю, а не за кількістю ключів. Ми можемо встановити «використовувати до 256 МБ» замість «зберігати до 100 000 записів», що є критичним для планування потужностей.

Конфігурація, яку ми використовуємо:

cache, err := ristretto.NewCache(&ristretto.Config{
    NumCounters: 10_000_000, // 10M counters → tracks ~1M items
    MaxCost:     256 << 20,   // 256MB
    BufferItems: 64,
    Metrics:     true,
})

NumCounters — це розмір таблиці відстеження частоти TinyLFU; емпіричне правило в документації Ristretto рекомендує 10-кратний розмір від очікуваної кількості елементів. При бюджеті 256 МБ і середньому розмірі запису посилання у 200 байт, кеш вміщує близько 1.3 млн записів при повному заповненні.

TTL для записів L1 становить 60 секунд. Це свідомо малий показник. Цільову адресу перенаправлення можна змінити в панелі керування в будь-який час, і кеш L1 є найповільнішим рівнем для інвалідації (Redis можна інвалідувати за допомогою публікації; L1 живе в кожному процесі та потребує скоординованого шляху інвалідації).

60-секундний TTL означає, що в найгіршому випадку застарілість даних триватиме 60 секунд після оновлення цілі. Для більшості сценаріїв це прийнятно; для випадків, де це не так (негайні зміни цілі під час живої кампанії), кнопка інвалідації в панелі керування запускає розсилку (fanout), яка очищує всі кеші L1 у всьому флоті. Розсилка використовує Redis pub/sub на каналі, на який кожен edge-процес підписується при запуску.

L2: Redis cluster з репліками для читання#

L2 — це Redis cluster, розгорнутий у кожному регіоні (Frankfurt, Ashburn, Singapore). Читання йде до локальних реплік; запис — до регіонального primary і реплікується в межах стандартної асинхронної моделі Redis.

Формат даних невеликий. Запис перенаправлення в L2 виглядає так:

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

Три поля: цільова URL-адреса, прапорці (увімкнено фільтрацію ботів, потрібен пароль тощо, упаковані в uint16) та версія. Версія відповідає версії рядка з Postgres; це дозволяє нам виявляти застарілі записи кешу під час читання.

TTL в L2 становить 24 години. Це набагато більше, ніж у L1, тому що L2 має працюючий шлях інвалідації: коли посилання створюється або оновлюється в базі даних origin, API публікує повідомлення Redis pub/sub у регіональний канал інвалідації, процеси перенаправлення видаляють свої записи L1, а запис L2 перезаписується безпосередньо шаром API.

Інвалідація через pub/sub має тонку властивість: вона допускає втрати. Якщо процес перенаправлення перезапускається під час публікації повідомлення про інвалідацію, він не бачить його, і його кеш L1 може видавати застаріле значення до 60 секунд. Ми з цим погоджуємося, оскільки TTL є запобіжником — час застарілості обмежений.

Розмір Redis cluster на кожному POP невеликий. У Frankfurt працюють три основні вузли плюс три репліки; весь набір даних поміщається приблизно в 4 ГБ. При нашому коефіцієнті влучань у кеш (98% L1, 1.8% L2, 0.2% origin при нормальному навантаженні) вимоги до пропускної здатності Redis помірні — зазвичай 5-15 тис. операцій/сек на піку для кожного POP, що цілком вкладається в потужність одного основного вузла, якби нам довелося консолідуватися.

Вибір політики витіснення#

Політика допуску TinyLFU у Ristretto — це вибір, який найбільше впливає на затримку у хвості розподілу.

Наївний LRU витісняє ключ, який використовувався найдавніше, щойно потрібно звільнити місце. Це нормально, коли паттерн доступу рівномірний — ключі, що використовувалися нещодавно, швидше за все будуть використані знову. Але це не працює у двох специфічних випадках:

• Навантаження скануванням (Scan workloads). Краулер-бот, який швидко переглядає 50 000 унікальних слагів, при наївному LRU витіснить кожен «гарячий» ключ і замінить їх ключами краулінгу, до яких більше ніколи не буде звернень. Коефіцієнт влучань падає, в origin відбувається сплеск навантаження, а p95 різко зростає, оскільки більшість запитів тепер ідуть повільним шляхом.
• Вибухові гарячі ключі. Посилання, яке зазвичай неактивне, але раптово отримує 100 тис. запитів за 30 секунд (вірусний пост у соцмережах, запуск ТБ-кампанії), має бути закешовано швидко. При наївному LRU воно витіснить один із існуючих гарячих ключів.

TinyLFU справляється з обома ситуаціями. Політика допуску відстежує частоту ключів і допускає новий ключ у кеш лише тоді, коли він зустрічається частіше, ніж кандидат на витіснення. Одноразовий скан бота не витіснить гарячі ключі, бо ключі сканування мають частоту 1. Вибуховий гарячий ключ потрапляє в кеш, але тільки після того, як його частота перевищить частоту кандидата на витіснення — що стається вже через кілька сотень запитів.

Ціна цього рішення полягає в тому, що перші 100-500 запитів для новопопулярного посилання будуть повільними (проходитимуть до L2 або origin), поки політика допуску не вирішить його закешувати. Для більшості випадків це правильний компроміс; для кампаній, де ми заздалегідь знаємо про майбутній сплеск, у нас є ендпоінт для попереднього розігріву, описаний нижче.

Розігрів кешу#

Кеш L2 проходить «холодний запуск», коли вводиться в експлуатацію новий Redis cluster. Ми не розігріваємо його зі знімка (snapshot); перші 5 хвилин після перезапуску кластера спостерігається підвищений трафік до origin, поки кеш не заповниться природним чином.

Кеш L1 проходить холодний запуск при перезапуску процесу перенаправлення (деплої, OOM kills, масштабування). Перші 30 секунд після перезапуску процесу більшість запитів ідуть до L2; наступні 60 секунд L1 заповнюється гарячими ключами. Загальний внесок холодного запуску в навантаження на origin невеликий (більшість edge-процесів перезапускаються значно рідше, ніж триває TTL кешу).

Виняток: коли менеджер кампанії заздалегідь публікує посилання, яке гарантовано дасть сплеск трафіку — URL для ТБ-реклами, посилання у прес-релізі, анонс запуску — панель керування пропонує перемикач «pre-warm». Його активація створює холостий запит до сервісу edge-redirect на кожному POP, що заздалегідь наповнює L1. Це простий метод, який рідко буває необхідним; автоскейлер адекватно справляється з непередбачуваними сплесками. Попередній розігрів — це відповідь на очікувані сплески, де затримка холодного кешу в перші 60 секунд була б помітною.

Що відбувається при заповненні L1#

Кеш L1 розміром 256 МБ заповнюється менш ніж за хвилину на типовому edge POP. Після заповнення для кожного нового ключа політика допуску TinyLFU має вирішити, чи варто витісняти існуючий ключ.

Цікаве спостереження: при нашому розподілі трафіку коефіцієнт влучань L1 після розігріву виходить на плато близько 98%. 2% промахів — це «довгий хвіст», тобто ті ~30% посилань, на які припадає менше 30% трафіку, і тому вони не проходять поріг частоти TinyLFU. Ці запити дають промах у L1 і влучають у L2, де коефіцієнт влучань становить приблизно 99%. Решта 0.2% усіх запитів ідуть до origin.

Ми вимірювали цей розподіл при трьох типах навантаження — інтенсивний трафік ботів, вірусний сплеск, стабільний стан — і коефіцієнт влучань L1 коливається між 95% та 99%. Коефіцієнт влучань L2 стабільніший і становить 98-99.5%. Таким чином, загальне навантаження на origin від рівня перенаправлення обмежене приблизно 0.5% від обсягу вхідних запитів, що є ключовим показником для планування потужностей origin.

Детально про інвалідацію кешу#

Потік інвалідації — це та частина архітектури, яку найчастіше розуміють неправильно при зовнішньому аудиті. Деталі:

Коли API отримує запит PATCH /v1/links/{id}, який змінює цільову URL-адресу, послідовно відбуваються три речі:

1. Postgres фіксує зміни з новою версією рядка (UPDATE links SET destination = ?, version = version + 1 WHERE id = ?).
2. Запис у Redis виконується безпосередньо з новим значенням у кожному регіональному кластері Redis. Запис розсилається від API до Redis кожного регіону через шар наскрізного запису (write-through layer).
3. Публікується інвалідація pub/sub у кожному регіональному каналі invalidate:redirect. Edge-процеси перенаправлення підписуються на цей канал при запуску та видаляють запис L1 для відповідного ключа.

Порядок має значення. Пріоритет Postgres гарантує, що канонічне сховище має нове значення. Наскрізний запис у Redis перед публікацією гарантує, що будь-який процес, який пропустить публікацію, але звернеться до Redis, побачить нове значення. Публікація — це оптимізація для підтримки синхронізації L1; TTL — це запобіжник на випадок пропуску публікації.

Відома ситуація гонитви (race condition): процес перенаправлення зчитує дані з Redis (через промах у L1) одночасно з публікацією інвалідації. Зчитування може повернути як нове значення (публікація відбулася трохи раніше), так і старе (публікація відбулася трохи пізніше). Якщо повернуто старе значення і закешовано в L1, наступні 60 секунд цей процес може видавати старі дані. Це прийнятно; альтернатива — синхронне блокування навколо гонитви читання-публікації — додасть затримку до кожного запиту, щоб уникнути крайового випадку, який стосується менше 0.01% інвалідацій.

Для випадків, де вікно застарілості неприпустиме (URL-адреса видаляється з юридичних причин або ціль раптово виявилася шкідливою), дія «purge cache» у панелі керування запускає агресивну інвалідацію: вона призупиняє всі читання L1 на 100 мс у всьому флоті, видаляє ключ із кожного L1, а потім відновлює роботу. Це використовується рідко і обмежене лімітом частоти запитів на секунду.

Сценарії збоїв, з якими ми стикалися на практиці#

Три збої за 18-місячну історію експлуатації, які варто задокументувати, бо вони сформували поточну конфігурацію.

Перемикання основного вузла Redis із застарілими репліками. На 4-й місяць експлуатації стався збій основного вузла в кластері Frankfurt. Репліка була підвищена до основної протягом 30 секунд (перемикання під керуванням Sentinel). Репліки відставали від основного вузла приблизно на 200 мс у момент збою, що означало, що перші кілька сотень інвалідацій, опублікованих безпосередньо перед збоєм, не досягли підвищеної репліки. Результат: коротке вікно, коли близько 0.3% перенаправлень видавали застарілі цілі. Рішення: тепер ми запускаємо репліки з параметрами min-replicas-to-write 1 and min-replicas-max-lag 10, що жертвує невеликою доступністю на запис заради суворішої гарантії затримки реплікації.

Thrashing кешу L1 під час синтетичного моніторингу. На 9-й місяць сторонній сервіс моніторингу аптайму був неправильно налаштований на перевірку кожного короткого посилання в робочому просторі клієнта щохвилини. У клієнта було 18 000 посилань. Паттерн перевірки передбачав повне сканування кожні 60 секунд. Ефект: коефіцієнт влучань L1 впав з 98% до 71% на трьох edge POP, оскільки паттерн сканування допускав кожен перевірений ключ у кеш. Рішення: ми додали фільтрацію на основі User-Agent перед шаром допуску до кешу — відомі User-Agent моніторингу обходять кеш і обслуговуються безпосередньо з L2. Це був крайовий випадок TinyLFU: ключі сканування виглядали достатньо частотними, щоб витіснити справді гарячі ключі.

Розрив з'єднання pub/sub під час тривалого деплою. На 13-й місяць деплой, що тривав довше очікуваного (близько 4 хвилин), призвів до того, що кілька edge-процесів залишалися підключеними до старого каналу pub/sub після перемикання основного вузла Redis. Інвалідації, опубліковані на новому основному вузлі, не доходили до цих процесів; їхні кеші L1 видавали застарілі значення протягом усього деплою. Рішення: впровадження heartbeats для з'єднань pub/sub з автоматичним перепідключенням при втраті, а також очищення L1 під час деплою як запобіжний захід.

Що ми розглядали та відхилили#

Кілька альтернатив, які були оцінені, але не обрані:

Єдиний внутрішньопроцесний кеш, без Redis. Протестовано. Частка промахів до origin у будь-якому окремому процесі занадто висока без L2; база даних origin потребувала б у 3-5 разів більше потужностей. Додаткові витрати на Redis невеликі порівняно з економією потужностей origin.

Використання CDN (Cloudflare або Fastly) для кешування перенаправлень. Протестовано у стейджингу. Регіональна затримка CDN у 1-2 мс при влучанні в кеш приблизно така ж, як у Redis, але ситуація з інвалідацією суттєво гірша (очищення CDN має затримку на рівні хвилин та вартість за очищення кожного URL). CDN додав складності, не покращивши ні затримку, ні коефіцієнт влучань.

Більший розмір L1. Бюджет у 256 МБ відповідає ліміту пам'яті на процес; подвоєння обсягу не подвоює коефіцієнт влучань, оскільки гарячий робочий набір уже вміщується. Зниження віддачі починається приблизно зі 128 МБ при нашому розподілі; 256 МБ мають запас для зростання трафіку.

Спостережуваність#

Метрики, які ми відстежуємо для кожного edge-процесу:

• cache_l1_hit_total, cache_l1_miss_total — виведений коефіцієнт влучань на процес.
• cache_l2_hit_total, cache_l2_miss_total — виведений коефіцієнт влучань на регіон.
• cache_origin_request_total — обсяг запитів до origin; ціль SLO < 1% від загальної кількості запитів.
• cache_invalidation_total{source="pubsub|ttl|purge"} — кількість інвалідацій за механізмом.
• cache_l1_memory_bytes — фактична пам'ять, яку використовує кеш L1; сповіщення спрацьовує при досягненні 90% від налаштованого бюджету.

Усі метрики збираються Prometheus та візуалізуються в наборі дашбордів посібника зі спостережуваності. Дашборди Grafana на регіональному рівні показують регіональний коефіцієнт влучань у кеш з часом; дашборди на рівні процесів (використовуються під час інцидентів) показують коефіцієнт влучань L1 та використання пам'яті для окремих процесів.

Коли варто використовувати цю стратегію, а коли ні#

Дворівневий кеш має сенс, коли:

• Навантаження переважно на читання з розподілом ключів типу «довгий хвіст».
• Гарячий робочий набір вміщується в пам'ять процесу (кілька сотень мегабайт).
• Промахи кешу достатньо дорогі, тому другий рівень суттєво економить навантаження на базу даних.
• Бюджет застарілості достатньо жорсткий, тому одного лише TTL у L1 недостатньо.

Це не має сенсу, коли:

• Гарячий робочий набір не вміщується в пам'ять процесу. У такому разі промахи L1 занадто часто переходять до L2, і L1 дає мало користі.
• Записи відбуваються часто порівняно з читанням. Витрати на інвалідацію стають домінуючими.
• Дані унікальні для кожного запиту (ніякої вигоди від кешування).

Для робочого навантаження сервісу скорочення URL виконуються всі чотири умови «так», і наведена вище конфігурація успішно працює протягом 18 місяців зростання продуктиву. Для інших типів навантаження кількість рівнів та політика витіснення потребують перегляду.

Що ще почитати#

• Hitting p95 < 15ms for redirects from FRA, ASH, and SGP — основа для інженерного кластера; цей допис є детальним зануренням саме в кешування.
• Why we use ClickHouse for click analytics (not Postgres) — суміжне інженерне рішення в тій же архітектурі.
• Fire-and-forget click ingestion with Redpanda — конвеєр обробки подій кліків, який працює паралельно з кешем перенаправлень.
• Short links as Terraform — оперативна інструкція з налаштування рівня перенаправлення.
• Архітектура Edge: /docs/architecture/edge-redirect.
• Посібник з експлуатації: /docs/guides/observability — згаданий вище набір дашбордів метрик.
• Продуктові рішення: /solutions/developers та /solutions/analytics.
• Зовнішні ресурси: Дизайн-документ Ristretto та стаття про TinyLFU для розуміння теорії політики допуску.