XFetch: вероятностное раннее истечение без координации

Lock-based митигация добавляет Redis round-trip к каждому cache miss — нормально для ультра-горячих ключей, расточительно для 99% ключей, которые редко сталкиваются. XFetch достигает той же гарантии «только один rebuild на TTL-окно» с нулевой координацией и нулевыми сетевыми затратами.

Правило решения

Каждое чтение кеша вычисляет:

should_refresh = (-beta * delta * ln(rand())) >= time_to_expire

Где:

• delta — типичное время rebuild в секундах (например, 0.4)
• beta — настроечная константа, по умолчанию 1.0
• rand() — равномерное случайное в (0, 1)
• time_to_expire — секунды до срабатывания текущего TTL

По мере приближения time_to_expire к 0 (близко к истечению), порог слева (-beta * delta * ln(rand())) всё вероятнее его превысит. Далеко от истечения вероятность близка к нулю. Вблизи истечения она быстро растёт.

Результат: ключ кеша обновляется до истечения. Первый запрос, поймавший вероятностный порог, запускает rebuild, пока существующее значение ещё отдаётся всем остальным. К моменту, когда TTL мог бы сработать, кеш уже имеет свежее значение.

Точные числа зависят от распределения чтений, но тренд ясен: вероятность концентрируется в последних нескольких секундах до истечения.

Ожидаемые refresh в TTL-окне = 1

Ключевое свойство, доказанное Vattani et al.: интегрирование вероятности по TTL-окну даёт ровно один ожидаемый ранний refresh, независимо от размера флота или ставки чтения. Флот из 100 нод, читающий ключ 1 000 раз в секунду, не производит 100 000 ранних refresh — он всё равно производит примерно 1. Экспоненциальное распределение имеет свойство, что минимум N независимых выборок тоже экспоненциальный со скоростью N × lambda. С ростом флота «первый» читатель поймает порог раньше, но ожидаемый счёт остаётся ~1.

Когда XFetch работает, а когда нет

XFetch требует достаточно частых чтений, чтобы «какой-то читатель» поймал вероятностный порог до TTL. Алгоритм прозрачен, когда чтения происходят, например, каждые 100 мс за 60-секундный TTL — много шансов поймать порог в последних секундах.

Случай провала: холодные или спорадические ключи. Ключ, читаемый раз в 30 с при TTL=60 с, может иметь только одно-два чтения во всём «раннем refresh» окне (последние ~1 с). При малом N вероятность промахнуться по порогу значительна. Ключ истекает нормально и stampede-ит.

Правило большого пальца: используй XFetch на ключах с ≥ 10 чтений за ожидаемое-rebuild-duration-окно до TTL. Для более холодных ключей используй лок или SWR.

Настройка beta

beta управляет тем, насколько рано открывается окно refresh:

• beta < 1.0: более ранние refresh, шире окно, больше потраченных ранних rebuild на холодных ключах. Используй, когда стоимость rebuild очень низка и staleness нужно минимизировать.
• beta = 1.0 (по умолчанию): окно открывается, когда time_to_expire ≈ delta. Баланс.
• beta > 1.0: более поздние refresh, уже окно, выше риск промахнуться по порогу на холодных ключах. Используй только когда rebuild дорог и ранний staleness нужно избежать.