🌿 Про "cache stampede" или эффект давки в кэше

В библиотеке Yii Cache наткнулся на алгоритм XFetch, с которым ранее не сталкивался и решил разобраться.

Типичный процесс получения данных из кэша выглядит следующим образом:

1) читаем значение из кэша;
2) если значения нет — рассчитываем его и записываем в кэш;
3) возвращаем значение.

Как правило, данные в кэше хранятся какое-то время, по истечении которого пересчитываются заново.

Если в момент, когда время хранения истекло, выполняется несколько параллельных запросов, то расчёт значения будет выполняться в каждом из этих запросов одновременно, что может повлечь за собой существенную нагрузку на сервер.

Эта проблема называется "cache stampede" (встречаются также названия "thundering herd" и "dog-piling"). Какого-то общепринятого перевода мне найти не удалось, поэтому назовём это эффектом давки.

Один из способов решения данной проблемы — раннее обновления данных. При таком подходе обновление данных в кэше происходит до истечения срока его действия и каждый процесс независимо принимает решение в какой момент производить повторное вычисление.

В 2015 году Andrea Vattani, Flavio Chierichetti и Keegan Lowenstein опубликовали работу Optimal Probabilistic Cache Stampede Prevention, где предложили эффективный алгоритм определения времени раннего обновления данных, основанный на экспоненциальном распределении, который был назван XFetch (eXponential fetch).

Краткий обзор алгоритма можно посмотреть в википедии (EN). Если совсем упростить, то вероятность выполнения раннего вычисления тем выше, чем ближе момент истечения срока хранения данных в кэше.

Таким образом при параллельных процессах обновление кэша происходит с большой вероятностью лишь в одном процессе, а остальные в этот момент используют предыдущее закэшированное значение.

Существуют и другие решения для избегания эффекта давки в кэше (использование блокировок, обновление кэша в отдельном процессе), но они более затратны в реализации и приносят с собой дополнительные проблемы, которые тоже придётся решать.