Многопоточная реализация алгоритма кеширования CART

Источник: habrahabr

tridemax

Некоторое время назад передо мной встала задача кеширования запросов в большую базу данных на диске в высоконагруженном многопоточном приложении (С++). Само приложение предназначалось для развертывания в облаке и диск очевидно стал бы самым узким местом. База при этом представляла из себя огромный граф, по которому одновременно ползало множество потоков. Таким образом кеш ко всему еще и должен был быть многопоточным. Идею использования внешних приложений, таких как memcached, я отбросил сразу же - это внесло бы в каждый переход по ребру графа неизбежный дополнительный лаг. Встал вопрос об имплементации внутри приложения.

Документация услужливо подсказала о существовании имплементации LRU кеша в используемой мною библиотеке TBB. К несчастью, данная имплементация на тот момент находилась в preview состоянии (где и находится до сих пор). У меня появился выбор - положится на недостаточно оттестированную имплементацию, где починка любого бага стала бы отличным приключением, либо писать свою. Также, беглое изучение доступных публикаций алгоритмов кеширования привело меня к мысли о том, что, возможно, LRU не самая эффективная схема. Для высоконагруженных приложений даже несколько процентов дополнительной эффективности само по себе хлеб. Перебрав все найденные мной, я остановился на алгоритме CART. Данная схема сочетает в себе несколько полезных достоинств:

Защита от сканирования. Если вы пройдете по всей базе данных один раз - это не повлияет на эффективность кеша. Такая ситуация может возникнуть, например, при работе аналитических инструментов.
Защита от двойного обращения. Часто случается, что один и тот же элемент базы данных запрашивается дважды с коротким промежутком между запросами, а затем к нему не обращаются вовсе. Это может приводить к значительному падению эффективности схем, не имеющих защиты от такого поведения, так как любой запрошенный таким образом элемент получает приоритет в схеме.
Каждый хит в кеш не требует каких-либо значительных операций или поддержания внутренних структур (что является существенным недостатком LRU). Это очень важно для многопоточной имплементации, так как не требует блокировки при каждом обращении.

Давайте взглянем насколько схема эффективна на практике. Так как у меня не было достаточно времени, чтобы имплементировать и отлаживать другие схемы, я буду сравнивать эффективность все с той же имплементацией LRU из библиотеки TBB. Сначала тестируем эффективность обеих схем на случайно сгенерированной последовательности чисел (0…10000) для трех размеров кеша (100, 500 и 1000):

Less is better.
Random numbers, cache size 100
CART result: 0.99, missed 994950 / 1005000
LRU result: 0.990057, missed 995007 / 1005000
Random numbers, cache size 500
CART result: 0.949862, missed 954611 / 1005000
LRU result: 0.95016, missed 954911 / 1005000
Random numbers, cache size 1000
CART result: 0.90002, missed 904520 / 1005000
LRU result: 0.900309, missed 904811 / 1005000

CART незначительно опережает LRU по эффективности, но, честно говоря, совершенно случайный доступ не самый хороший тест. Более того - в реальном приложении с таким типом доступа эффективность любого кеша будет низкой. Поэтому второй тест я сделал больше похожим на практическое применение. Здесь числа берутся из 6-ти корзин, каждая из которых имеет все большее количество элементов, что уменьшает вероятность выбрать какое-то конкретное число. Таким образом числа от 0 до 150 суммарно имеют такую же вероятность быть выбранными, как и числа от 5000 до 10000. Эта тактика похожа на паттерн выборки, например, из базы данных пользователей, где часто заходящие пользователи чаще дергают базу.

Bins draw, cache size 100
CART result: 0.920258, missed 924859 / 1005000
LRU result: 0.965795, missed 970624 / 1005000
Bins draw, cache size 500
CART result: 0.721484, missed 725091 / 1005000
LRU result: 0.84106, missed 845265 / 1005000
Bins draw, cache size 1000
CART result: 0.581132, missed 584038 / 1005000
LRU result: 0.71412, missed 717691 / 1005000

В этом случае CART уже показывает значительно лучшие результаты, нежели LRU. Чего, собственно, мы и хотели достичь. Всем интересующимся предлагаю скачать пример и запустить собственноручно. Найти эту имплементацию можно здесь. Она тестировалась в реальном приложении под нагрузкой, что впрочем не гарантирует 100% отсутствия возможных багов. Используйте, так сказать, на свой страх и риск. Для интеграции в свои проекты вам необходимы только файлы в папке Include. От зависимости на HashMurmur3 можно избавиться, заменив его на любую подходящую вам хеш-функцию. В зависимостях у этой имплементации есть только TBB, но большинство тех, кто пишет многопоточные приложения на С++, и так его используют. В качестве бонуса прилагается неплохая имплементация генератора случайных чисел. Также оригинальная имплементация использует EASTL вместо STL, но я избавился от этой зависимости перед тем, как выложить публичную версию. Исходники примеров собираются под VS2010, но порт под Linux не должен вызвать проблем. Так как у меня сейчас нет под рукой Linux"а, я был бы благодарен сообществу, если бы кто-то потратил на это немного своего времени и сделал этот порт. P.S. Способов применения хорошей схемы кеширования можно придумать массу. У меня, например, данная имплементация также используется в доступе к Memory Mapped Files, где файл маппится не целиком, что может привести к огромному расходу виртуальной памяти на больших файлах, а ограниченным количеством небольших кусков по 16Мб. Кеш при этом управляет тем, какие куски выталкивать из памяти. Также можно парой сотен строк написать себе свой memcached, если вдруг возникнет такое желание.

Многопоточная реализация алгоритма кеширования CART.

Защита от спама и не только: "Лаборатория Касперского" совершенствует защиту корпоративных почтовых серверов.

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

США открывает национальную систему здравоохранения для разработчиков.

Oracle анонсирует решение по управлению мирового класса для пользователей программы Unbreakable Linux.

Главная » Linux