Описание проблемы
Представим среднестатистический высоконагруженный сайт. Обычно на таких сайтах между backend'ом и DB ставят прослойку кеша. С увеличением количества посетителей, вероятность того, что несколько пользователей одновременно наткнутся на "протухший" кеш увеличивается. Если такое случается, то нагрузка на backend и DB возрастает, что в свою очередь увеличивает время обработки запроса и увеличивает вероятность возникновения подобной ситуации. Вот такая вот система с положительной обратной связью:
Маленькие красные горбики — это "затупившие" на множественном обновлении кеша запросы. Эта статья будет описывать один из подходов к решению проблемы на примере(patch attached) связки PHP/APC, однако теоретическая база применима к любому языку и системе кеширования. Варианты решения проблемы
Подходов к решению проблемы может быть несколько. Предложенный же ниже способ является именно workaround'ом. Правильный подход, имхо, использование busy lock'ов, которые бы позволяли только одному процессу обновлять кеш, в то время как остальные бы отдавали устаревшие данные. Однако это решение довольно не тривиально и в большинстве случаев (при равномерном распределении запросов) описанного workaround'а должно более чем хватать.
Также, в моём случае, было решено имплементировать RED на уровне самого кеша, однако то же самое можно было бы реализовать в классе/wrapper'е внутри кода приложения. Такой способ был выбран потому, что лезть в PHP код было лень.
RED
RED, он же, random early detection, random early discard или random early drop — алгоритм для управления очередями, встречаемый в маршрутизаторах и шейперах. Физический смысл его примерно таков: вместо того, чтоб дожидаться когда очередь переполнится и придётся дропать всё подряд (taildrop) вводится определённый порог, после которого мы начинаем с некоторой вероятностью дропать пакеты, сама же вероятность прямо пропорциональна свободному месту в буфере. Отсюда и Random Early Drop.В нашем случае мы введём определённый порог времени жизни записи в кеше(
drop_threshold), после которого начнём с некоторой вероятностью p на запросы чтения из кеша выдавать cache miss, что заставит приложение положить в кеш свежую версию данных. Тем самым уменьшим кол-во конкурентных обновлений кеша обратно пропорционально p.Матчасть
Математика тут на уровне класса третьего, так что просто приведу картинку и формулу:
Disclaimer
PHP я не знаю. На Си пишу как быдло.
APC patch
Код написан скорее как PoC нежели для production использования. Значение
75% было взято с потолка. В реальных условиях drop_threshold должно быть вынесено в конфиг.Index: apc_cache.c
===================================================================
--- apc_cache.c (revision 320057)
+++ apc_cache.c (working copy)
@@ -705,6 +705,13 @@
volatile apc_cache_entry_t* value = NULL;
unsigned long h;
+ /* APC-RED PATCH */
+ const int drop_threshold = 75;
+ unsigned int probability = 0;
+ int red_cf = 0;
+ short drop = 0;
+ /* END OF APC-RED PATCH */
+
if(apc_cache_busy(cache))
{
/* cache cleanup in progress */
@@ -720,8 +727,25 @@
while (*slot) {
if ((h == (*slot)->key.h) &&
!memcmp((*slot)->key.data.user.identifier, strkey, keylen)) {
+ /* APC-RED PATCH */
+ if((*slot)->value->data.user.ttl) {
+ red_cf = (t - (*slot)->creation_time) * 100 /
+ (*slot)->value->data.user.ttl;
+ if (red_cf >= 100) {
+ drop = 1;
+ }
+ else if (red_cf <= drop_threshold) {
+ drop = 0;
+ }
+ else {
+ probability = (red_cf - drop_threshold) * 100 / (100 - drop_threshold);
+ drop = (arc4random() % 100) < probability ? 1 : 0;
+ }
+ }
+ /* END OF APC-RED PATCH */
+
/* Check to make sure this entry isn't expired by a hard TTL */
- if((*slot)->value->data.user.ttl && (time_t) ((*slot)->creation_time + (*slot)->value->data.user.ttl) < t) {
+ if(((*slot)->value->data.user.ttl && (time_t) ((*slot)->creation_time + (*slot)->value->data.user.ttl) < t) || drop) {
#if (USE_READ_LOCKS == 0)
/* this is merely a memory-friendly optimization, if we do have a write-lock
* might as well move this to the deleted_list right-away. Otherwise an insert
Учитывая, сколько парсеров прошёл этот патч перед тем, как попасть на хабр, он наверняка не применится, так что лучше оставить тут ссылку на gist: patch-apc_red.patch
Размышления о прекрасном
В код APC также стоило бы добавить поддержку RCU(например через liburcu) ибо в условиях высоких нагрузок упереться в rwlock (кстати, относительно недавно добавленный в APC) не так уж и сложно. Сам же APC уже давно стоило бы встроить в PHP.
Ещё можно подумать, как адаптивно настраивать
drop_threshold ибо для какой-нибудь глобальной структуры типа board_config, в которой phpbb хранит все-превсе глобальные настройки и которая дёргается на каждый запрос всеми пользователями, имеет смысл threshold ставить в 50%, а для пользовательской сессии, наоборот, стоит «фичу» отключать, выставляя threshold в 100%. Если размышлять на эту тему, можно опять посмотреть в сторону сетевых аналогов, например на Adaptive / Active RED (ARED).Также о проблеме протухания кешей и борьбе с ней можно почитать давнишний, но всё ещё актуальный доклад Андрея Смирнова (smira) на Highload 2008: Web, кэширование и memcached
