2R2L кеширование

    Кеширование – широко освещенная и известная тема. Но и в ней могут появляться новые решения. В частности – в области высокоуровневых продуктов (например, в веб-разработке). Столкнувшись с недостатками классического подхода, я попробовал вывести идеальную схему кеширования для случая, когда актуальность данных не является критической. Потом я попробовал найти описание подобной схемы, а лучше – готовые решения. Не нашел. Поэтому назвал ее сам – 2R2L (2 Range 2 Location) – двух-диапазонное двух-«пространственное» кеширование. Хотя наверняка оно уже где-то применяется.

    Началось все с простой задачи – отобразить пользователю новинки неких товаров с учетом его индивидуальных предпочтений. И если с получением новинок проблем не было, то соотнесение новинок с предпочтениями (анализ статистики) уже создавал ощутимую нагрузку (для примера определим ее в 4 секунды). Особенность задачи состояла в том, что в качестве пользователей у нас могут выступать целые организации. И нередки случаи, когда одномоментно (в течение 2-3 секунд) на сервер прилетает 200-300 запросов, относящихся к одному пользователю. Т.е. генерируется один и тот же блок сразу для многих пользователей.

    Очевидное решение – надо кешировать в RAM (не будем подвергать СУБД насилию, заставляя отрабатывать большой поток обращений). Классическая схема:

    1. Пришел запрос
    2. Проверяем кеш. Если данные в нем есть, и они не устарели – просто отдаем их.
    3. Данных нет => генерируем выдачу
    4. Отправляем пользователю
    5. Дополнительно складываем в кеш, указывая TTL

    Недостаток такого решения: если данных в кеше нет, генерировать их будут все запросы, пришедшие за время первой генерации, затрачивая на это ресурсы сервера (пики нагрузки). Ну и конечно, все пользователи при «первом обращении» будут ждать.

    Также отметим, что при индивидуальных кеш-значениях количество записей может вырасти на столько, что доступной ОЗУ сервера просто не хватит. Тогда логичным выглядит использование локального HDD сервера в качестве хранилища кешей. Но мы сразу теряем в скорости.

    Как же быть?

    Первое, что приходит в голову: было бы здорово хранить записи в 2 местах — в RAM (часто запрашиваемые) и HDD (все или только редко запрашиваемые). Концепция «горячих и холодных данных» в чистом виде. Реализаций такого подхода – множество, поэтому останавливаться на нем не будем. Просто обозначим эту составляющую как 2L. В моем случае она успешно реализуется на базе СУБД Scylla.

    Но как избавиться от «просадок» в моменты, когда кеш устарел? А здесь мы и подключаем концепцию 2R, смысл которой заключается в простой вещи: для кеш-записи надо указывать не 1 значение TTL, а 2. TTL1 – метка времени, которая означает «данные устарели, надо бы перегенерировать, но использовать еще можно»; TTL2 – «все устарело настолько, что использовать уже нельзя».

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

    1. Пришел запрос
    2. Ищем данные в кеше. Если данные есть и не устарели (t<TTL1) – отдаем пользователю, как обычно и больше ничего не делаем.
    3. Данные есть, устарели, но можно использовать (TTL1 < t < TTL2) – отдаем пользователю И инициализируем процедуру обновления кеш-записи
    4. Данных нет совсем (убиты по истечении TTL2) – генерируем «как обычно» и записываем в кеш.
    5. После отдачи контента пользователю или в параллельном потоке выполняем процедуры обновления кеш-записей.

    В результате мы имеем:

    • если кеш-записи используются достаточно часто, пользователь никогда не попадет в ситуацию «ожидаем актуализации кеша» — он всегда будет получать уже готовый результат.
    • если правильно организовать очередь «актуализаций», то можно добиться того, что в случае нескольких одновременных обращений к записи с TTL1 < t < TTL2, в очереди будет находиться только 1 задача на обновление, а не несколько одинаковых.

    В качестве примера: для ленты новинок можно указать TTL1 = 1 час (все же не сильно интенсивно новый контент появляется), а TTL2 – 1 неделя.

    В простейшем случае код на PHP для реализации 2R может быть таким:

    $tmp = cache_get($key);
    If (!$tmp){
    	$items = generate_items();
    	cache_set($items, 60*60, 60*60*24*7);
    }else{
    	$items = $tmp[‘items’];
    	If (time()-$tmp[‘tm’] > 60*60){
    		$need_rebuild[] = [‘to’=>$key, ‘method’=>’generate_items’];
    }
    }
    …
    // отдаем данные пользователю
    echo json_encode($items);
    …
    // поскольку данные пользователю уже отправлены, можно и повычислять
    If (isset($need_rebuild) && count($need_rebuild)>0){
    	foreach($need_rebuild as $k=>$v){
    		$tmp = ['tm'=>time(), 'items'=>$$v[‘method’]];
    		cache_set($tmp, 60*60, 60*60*24*7);
    }
    }
    

    На практике, конечно, реализация, скорее всего, будет посложнее. Например, генератор кеш-записей – отдельный скрипт, запущенный в качестве сервиса; очередь – через Rabbit, признак «такой ключ уже есть в очереди на перегенерацию» — через Redis или Scylla.

    Итого, если объединить «двух-диапазонный» подход и концепцию «горячие/холодные» данные, как раз и получим – 2R2L.

    Спасибо!

    Комментарии 21

      0
      Решал похожую задачу.

      У меня был один TTL, только логика немного другая: TTL не влияет на выдачу (на запрос всегда отдаётся кэшированное даже устаревшее значение).
      Однако, есть фоновая команда, которая периодически проверяет устаревшие значения и обновляет их. Так что фактический максимальный TTL = указанный TTL + интервал обновления + скорость обработки.
      Ленивость и экономия памяти обеспечивалась логином: если за некоторый период юзер не логинился, то его кэш очищается.
      (Может, для этой логики тоже есть термин?)

      В итоге: нет проблемы «первого запроса» для активных пользователей, нагрузка фоновая, нагрузка равномерна (размазана по времени и не создаёт резких пиков), при нехватки памяти нагрузка не увеличится (просто реальный TTL будет меньше того что в конфиге).
        0
        Согласен, тоже хорошее решение. Я пробовал фоновый поток, обходящий кеши. Но очень быстро вышло, что слишком много надо было пересчитывать. Когда пришлось ввести 2 фоновых потока, постоянно без пауз что-то считающих, я пошел «в другую сторону».
          0
          Не совсем понял, получается вы в фоне проверяли актуальность всех кешей?
          В этом случае есть плюсы, т.к. всегда есть актуальный кеш.
          Но с другой стороны, может быть такой кейс:
          каталог товаров из 1 млн. (вместе с торговыми предложениями) позиций, вы постоянно актуализируете кеш этих товаров, например какие-то характеристики, но по сути, из всего каталога, у вас 99% запросов приходится только на 30% каталога, остальные — тухляк.
          Получается, что в вы актуализируете постоянно кеш данных, к которым идут запросы очень редко.
            0
            Совершенно верно. И придя к тем же выводам, я убрал «фоновую актуализацию» и внедрил «2-х диапазонные кеши», которые обновляются только в том случае, если востребованы.
              0
              > Получается, что в вы актуализируете постоянно кеш данных, к которым идут запросы очень редко.

              Нет. Цитирую:«Ленивость и экономия памяти обеспечивалась логином: если за некоторый период юзер не логинился, то его кэш очищается.».

              Это не серебряная пуля, я топлю за анализ поведения системы перед тем как его менять (-:
              В моём случае я знаю что юзеров (которые логинились хотя бы раз за последние два дня) в среднем около 30% и держать данные для них в кэше выгодно по этому кртерию. Возможно, в другой системе при других условиях я бы выбирал другой критерий.
            0
            случае нескольких одновременных обращений к записи с TTL1 < t < TTL2, в очереди будет находиться только 1 задача на обновление, а не несколько одинаковых.


            Здесь не понял как и кто за этим следит. Все параллельные процессы инициализируют обновление кэша, так-как для каждого из них выполняется условие TTL1 < t < TTL2. И каждый процесс запустит эвент «кэш мне запили». Очередь, конечно, можно разобрать с условием, что есть только один подписчик, который обновляет кэш, и второе аналогичное задание он пропустит так-как t станет < TTL1 и < TTL2 но что если подписчиков больше одного? В общем, сама по себе концепция не дает возможности предотвратить двойное обновление кэша.

            Плюс я не совсем уверен, что нужен второй TTL как таковой. Если есть доступ к значению времени истечения актуальности кэша, ставим сразу значение второго TTL, как основное, и при запросе пользователем данных, отдаем кэш, и проверяем сколько прошло времени. Если уже порядочно, то кидаем эвент на обновление кэша.
              0
              Да, концепция не дает. Но указанную проблему мы решили. Дело в том, что задачи на обновление у нас идут через Rabbit. Соответственно, поток, занимающийся пересчетом, получая задачу, просто проверяет наличие в кеше соответствующего значения с t < TTL1. Если так и есть, значит задача — дубль, пропускаем. Если t > TTL1 — работаем. И есть отдельный поток — он занимается принудительным пересчетом (иногда надо обновить срочно и вне общей очереди).
              PS На самом деле немного обманул — дополнительно еще ставится/проверяется/удаляется спец. флаг, означающий «задача есть в очереди». Для этого мы используем Redis.

              По второму замечанию — тут сложнее определять, что значит «порядочно» в каждом конкретном случае. Фиксация в секундах или процентах наверняка где-то будет препядствием. Да и в плане разработки — посложнее. При появлении нового набора данных для кеширования, надо внести правки и в общую процедуру «дай кеш-значение».
                0
                Флаг в редисе это потенциальный дедлок. Сообщение может пропасть, консюмер может упасть и некому будет удалить флаг.

                Если у вас мемкеш, посмотрите в сторону cas.
                  0
                  О, с редисом все нормально — ставим довольно короткий TTL для записи самого флага, так что дедлоков не случается. Да и новый консюмер поднимается в течение 10 секунд максимум, если что.
                  А вот на счет мемкеш — спасибо, учтем.
              0

              Похоже на адский велосипед, в котором ещё и очередь сообщений задействована. Если вам нужно сгенерировать запись в кеш, а остальные читатели должны подождать — rw lock вам в руки.

                0
                Идея как раз в том, чтобы по-возможности вообще никогда не заставлять ждать (самое первое генерирование не в счет). А большая «навороченность» обусловлена далеко не столько идеей 2-диапазонного кеширования, сколько размером системы — у много-серверных продуктов свои особенности и требования.
                  0

                  Так тоже можно, вам нужен распределённый лок, вещь очень частая в распределённых системах.


                  1. Вам нужен Redis и операция compare and set. Делается в виде lua скрипта.
                  2. Запрос читает данные из редиса и решает нужно ли их обновлять. Например данные истекли или их нет.
                  3. Если нужно обновить и compareAndSet(key, busy, null) == null то загрузить и обновить. В зависимости от TTL либо в фоне либо заблокировать процесс пока загрузка не кончится.

                  Предусмотреть логику для перезапуска процесса обновления если он завис или не завершился. В идеале с помощью механизма устаревания ключей редиса. Ключ key умирает и следующий compareAndSet загрузит данные.


                  Вместо Redis можно БД использовать как хранилище распределённых локов.

                0
                en.wikipedia.org/wiki/Cache_stampede

                Ну и дальше гуглить решения и алгоритмы этого вопроса.
                Будут те самые готовые решения вашего вопроса.
                symfony.com/blog/new-in-symfony-4-2-cache-stampede-protection
                  0
                  Не совсем. Подобную технологию я использовал ранее. Ее цель — убрать случаи пиковой нагрузки.
                  Например, если на странице нужны 10 кеш-значений, с TTL=100, то по истечении этих 100 секунд все 10 блоков будут перегенерироваться в рамках одного запроса. Чтобы этого избежать, у меня автоматом добавлялась вариативность времен в пределах +-20%. Что гарантировало «постепенное» обновление всего набора.
                  Получается, что идеи хоть и очень схожи, но все-таки разные. Моя основная цель — «ленивое» обновление, что как часть включает в себя и «защиту сервера».
                    0

                    Я так понял, вашем случае защиты сервера нет. Когда одновременно прилетает 100500 запросов на одно кеш-значение, да, вы быстро отдадите пользователю ответ, но при этом 100499 раз избыточно перегенерируете кеш.

                      0
                      Отчего ж? Аж двойная.
                      1. Спец. флаг в Redis (защищает при первом генерировании в основном)
                      2. Контрольная проверка наличия кеш-значения с t < TTL1 в начале процедуры перегенерации. Это если очередь долго разгребалась.
                        0
                        1. Я все-таки в уме держу некоторую абстракцию, где кеш может быть не только в redis, где такого флага может не быть
                        2. И вот как раз в ситуации большого количества запросов TTL1 < t < TTL2, когда запрос на перегенерацию уже отправлен, но еще не выполнен, есть вероятность получить много таких холостых перегенераций
                  0

                  Похоже, вы изобрели stale-while-revalidate (например, как здесь https://tools.ietf.org/html/rfc5861#section-3 )


                  Для Node.js мы иcпользовали https://github.com/thomheymann/stale-lru-cache

                    0
                    Да, видимо оно самое. Было бы странно, если бы такую, в общем-то несложную, вещь я бы придумал первым. Но тем не менее, информации на русском — найти не удалось, на английском — очень сложно (и то только благодаря комментариям к этой статье).
                    0

                    Добрый день!
                    Спасибо за статью!


                    Подскажите, а на сколько надёжен ваш описанный кейс по поводу актуализации кеша через реббит + проверка на существование таски через редис?
                    Практики с очень высокими нагрузками не было. Хотел бы взять на вооружение.

                      0
                      Пока проблем не было. Посещаемость у нас — ~10 млн обращений к скриптам динамики в месяц. Половина из обращений так или иначе работает с кеш-записями.

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое