Pull to refresh

Борьба с одновременным перестроением кеша с помощью RED

Reading time 6 min
Views 1.9K

Описание проблемы


Представим среднестатистический высоконагруженный сайт. Обычно на таких сайтах между 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
Tags:
Hubs:
+39
Comments 23
Comments Comments 23

Articles