- PVSM.RU - https://www.pvsm.ru -
Это перевод обзора статьи «MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing» Fan et al. в Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI’13), pdf тут [1]
Чуваки (бывший гугловец, чувак из университета Карнеги Меллон и еще один из Интел лабс) сделали улучшенный Memcached-совместимый кеш (по факту просто допилили мемкеш), и у них классные результаты производительности. Мне очень понравился обзор этой статьи в блоге "The morning paper" — описание алгоритмов и прочее.
Курсивом — мои комментарии как переводчика.
В основе MemC3 другой, чем в обычном мемкеше, алгоритм хэширования — оптимистичное "кукушечное" хеширование (cuckoo), и дополнительно к этому особый "CLOCK" алгоритм вытеснения. Соединенные вместе, они дают до 30% более эффективное использование памяти и увеличение производительности в запросах в секунду до 3 раз по сравнению с вашим обычным Memcached (при нагрузках с преобладающим чтением небольших объектов, что типично для мемкешей в Facebook).
В конце оригинальной статьи есть отличный разбор полученных результатов с точки зрения вклада примененных оптимизаций. Это выглядят это примерно так:
Полная пропускная способность (по сети) в зависимости от числа тредов
Сначала разберемся с обычным кукушечным хешированием. Как работает самая обычная хэш-таблица? Вы хэшируете ключ и по этому хэшу выбираете ячейку таблицы (bucket или ведро:), в которую нужно вставить или в которой можно найти соответствующее ключу значение. Куку-хэширование использует две хэш-функции, получается, две возможные ячейки для вставки или поиска значения.
Рассмотрим следующую таблицу, в которой каждая строка представляет собой ячейку, в каждой из которых четыре слота для данных. Слот — это указатель на сами данные, объект пару ключ-значение.
Имея ключ для поиска, мы считаем для него два хеша и получаем две возможные ячейки. То есть нужно проверить 2 ячейки × 4 слота = 8 слотов, чтобы найти или не найти нужный ключ.
То есть при поиске в такой хеш-таблице нужно много операций по сравнению с "обычной" хеш-таблицей.
Кукушечное хэширование получило свое название из-за того, как обрабатывается операция вставки. Сперва мы хэшируем ключ X, который собираемся вставлять, используя обе хэш-функции, и получаем две возможные ячейки. Если какая-либо из этих ячеек имеет пустой слот, то сохраняем Х туда. Если же все слоты заняты, значит, пришло время какому-то ключу подвинуться. Случайно выбираем один слот в одной из этих двух ячеек и перемещаем (или "переселяем") из него ключ (назовем его Y), таким образом освобождая место для записи X. Теперь хэшируем уже Y двумя хеш-функциями и находим вторую ячейку, где он мог бы находиться, и пытаемся вставить Y туда. Если все слоты этой ячейки тоже заполнены, то перемещаем какой-то ключ уже из этих слотов, чтобы освободить место для Y, и продолжаем делать так, пока пустой слот не найден (или пока не достигнем некоторого максимального количества перемещений, например, 500).
Тут алгоритм ведет себя похоже на кукушку — вытаскивает чужой ключ из уже использованного места и кладет туда свой, отсюда и название.
Если так и не получается найти свободный слот, то значит, эту хэш-таблицу пора расширять — увеличивать выделенную под нее память.
Хотя такой алгоритм для вставки, кажется, может потребовать выполнения целой последовательности, цепочки перемещений, оценка временной сложности операции вставки для куку-хэширования — O(1).
Цитата из оригинальной работы
Из вышесказанного понятно, что происходит много выборок по ключу и много сравнений, и все это не слишком хорошо с точки зрения локальности данных. (Видимо, автор имеет в виду, что, поскольку ни ключи, ни даже хеши ключей не хранятся непосредственно в слотах ячеек таблицы, а хранятся в отдельно выделенных структурах ключ-значение, то происходит много рандомных обращений по памяти и полных сравнений ключей, что не позволяет хорошо работать процессорным кешам) Первое, что мы сделали для оптимизации куку-хэширования — ввели теги. Тег — это 1-байтовое хэш-значение ключа, и мы будем хранить его прямо в слоте хэш-таблицы рядом с указателем на ключ. Такие теги позволяют очень быстро (всего-то сравнив один байт) понять, может ли сохраненный ключ совпадать с искомым или нет, без необходимости извлекать его по указателю и целиком сравнивать.
Могут происходить лишние извлечения для двух разных ключей, имеющих один и тот же тег, поэтому ключ всё равно надо извлекать и сравнивать полностью, чтобы убедиться, что он совпадает с искомым. С однобайтовыми тегами частота коллизий будет всего 1/2^8 = 0,39%. В случае проверки всех 8 слотов-кадидатов (например, при поиске отсутствующего ключа — miss'е), будет происходить в среднем 8 × 0,39% = 0,03 разыменований указателей. Поскольку каждая ячейка помещается в один блок процессорного кеша процессора (обычно 64 байт), в среднем каждый поиск обернется только в считывание двух блоков для проверки двух ячеек плюс либо 0.03 разыменований указателей в случае поиска отсутствующего ключа — miss'е, либо 1,03 в случае успешного поиска — hit'е.
Цитата из оригинальной работы
При определении двух возможных ячеек для ключа вместо использования двух хеш-функций, мы будем использовать только один хэш, а также дополнительный тег: пусть ячейка_1 = хэш(X), и у нас есть тег(X), то ячейка_2 = ячейка_1 ⊕ тег(X). Эта конструкция имеет следующее полезное свойство — можно определить ячейку_1, зная тег и ячейку_2. То есть при операциях перемещения ключа нам становится неважно, в какой ячейке лежал ключ, мы можем вычислить альтернативную ячейку без обращения к полному ключу.
Наша схема хеширования, насколько нам известно, является первой реализацией с поддержкой параллельного доступа (multi-reader, single writer), обладающей высокой эффективностью использования памяти (даже при > 90% заполненности таблицы).
Цитата из оригинальной работы
Чтобы добавить параллелизма в такой алгоритм, нужно решить две проблемы:
Конечно, строго говоря, авторы не решили первую проблему, они просто забили на нее, так как позволяют одновременно выполняться лишь одной операции записи. В реальных условиях в профиле нагрузки часто доминирует чтение, так что это разумный компромисс.
Кеш-миссов (ложно отрицательных срабатываний) можно избежать, если сначала определить полную цепочку куку-перемещений, но еще ничего не перемещая, а затем выполнить эти перемещения в обратном порядке — от последнего пустого слота до желаемой исходной вставки. В сочетании с тем, что операции записи идут в один поток, получается, что каждый отдельный обмен гарантированно не вызывает каких-либо дополнительных перемещений и может быть выполнен без необходимости наперед блокировать всю цепочку.
Самая прямолинейная реализация — брать блокировку на каждую из двух ячеек, участвующих в обмене (осторожно с порядком), и разблокировать их после обмена. Тут нужно два лока/релиза на каждый обмен.
Мы пытались оптимизировать производительность для наиболее распространенного использования и воспользовались преимуществом наличия только одного треда записи, чтобы выстроить все insert'ы и lookup'ы в один поток последовательных операций с малым оверхедом. Вместо того, чтобы лочить ячейки, мы заводим на каждой ключ-счетчик версии. Увеличиваем счетчик при перемещении ключа при insert'е и следим за изменением версии во время lookup'а для детекта одновременно происходящего перемещения.
Цитата из оригинальной работы
Но где вы храните эти счетчики?? Если добавить их к каждому объекту ключ-значение, то будет использовано много памяти при сотнях миллионов ключей. Также появляется возможность для race-condition, поскольку эти объекты ключ-значение, хранятся за пределами самой хеш-таблицы и, таким образом, не защищены локами.
Решение состоит в том, чтобы использовать массив счетчиков фиксированного размера — значительно меньшего, чем количество ключей. Массив в 8192 счетчиков влезает в 32KB кэш, и каждый счетчик используется для нескольких ключей, за счет использования нашего старого знакомого — хэширования. Такой компромисс, использование таких шареных счетчиков, по-прежнему даёт хорошую степень параллелизации доступа, сохраняя при этом вероятность "лишней повторной попытки" (счетчик версии увеличился на единицу для какого-то другого ключа, который имеет хэш коллизию в таблице счетчиков версий) низкой, примерно — 0,01%.
Эти счетчики вписаны в общий алгоритм следующим образом:
Дополнительная хитрость для оптимизации куку-хеширования заключается в параллельном поиске нескольких возможных путей вставки. Это увеличивает шансы быстрее найти пустой слот. По тестам вышло, что оптимально проверять параллельно два возможных пути.
До сих пор мы говорили о вставках и поисках. И хотя оптимизированное куку-хэширование так же весьма эффективно использует память, все равно можно ожидать, что в какой-то момент наш кэш заполнится до предела (или почти до предела), и тогда нужно будет беспокоиться о вытеснении.
В обычном Memcached используется политика вытеснения наиболее давно использованных ключей— LRU, но она требует по 18 байт на ключ (два указателя и 2-байтный счетчик ссылок), чтобы обеспечить безопасное вытеснение строго в порядке LRU. Это также привносит значительные накладные расходы на синхронизацию.
В противоположность этому, MemC3 использует всего 1 бит на ключ с возможностью параллелизации операций. Это достигается за счет отказа от строгого LRU в пользу приблизительного LRU основанного на CLOCK алгоритме.
Поскольку в нашем целевом случае преобладают мелкие объекты, то использование памяти снижается при использовании приближенного к LRU вытеснения, что позволяет кэшу хранить значительно больше записей, что, в свою очередь, улучшает общий хит-рейт. Как будет показано в разделе 5, такое управление вытеснением дает увеличение пропускной способности от 3 до 10 раз по сравнению с обычным Memcached, и все это при лучшем хит-рейте.
Цитата из оригинальной работы
Представьте циклический буфер битов и виртуальную часовую стрелку, указывающую на конкретное место в буфере.
Каждый бит представляет "возраст" (давность использования) какого-то объекта пары ключ-значение. Бит равен '1', если соответствующий ключ использовался недавно, и '0' — в противном случае. Любая операция с ключом просто устанавливает соответствующий бит давности в '1'. При вытеснении нужно проверить тот бит, на который указывает стрелка часов. Если это '0', то можно вытеснить соответствующий ключ из кеша. Если это '1', то записываем туда '0' и сдвигаем стрелку часов вперед, на следующий бит. Этот процесс повторяется до тех пор, пока не найден нулевой бит.
Процесс вытеснения интегрирован со схемой оптимистических блокировок следующим образом:
Когда процесс вытеснения выбирает ключ-жертву X по CLOCK алгоритму, то он сначала увеличивает счетчик версии ключа X, чтобы сообщить остальным тредам, которые в настоящее время читают X, что им нужно попробовать позже еще раз; затем он удаляет X, делая его недоступным для последующего чтения, в том числе для тех повторных попыток от других тредов; и, наконец, увеличивает счетчик версии ключа X снова, чтобы завершить цикл изменений. Обратите внимание, что все вытеснения и вставки сериализуются с помощью локов, так что при обновлении счетчиков они не влияют друг на друга.
Цитата из оригинальной работы
На этом всё. Надеюсь, вам понравилось так же, как и мне.
Подписывайтесь на хабра-блог okmeter.io!
Автор: okmeter.io
Источник [2]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/optimizatsiya-koda/220924
Ссылки в тексте:
[1] pdf тут: https://www.cs.cmu.edu/~binfan/papers/nsdi13_memc3.pdf
[2] Источник: https://habrahabr.ru/post/316762/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.