MemC3 — компактний Memcache з підвищеною паралельністю — за рахунок більш тупого кешування і більш розумного хешування

Це переклад огляду статті «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 тут
Чуваки (колишній гугловец, чувак з університету Карнегі Меллон і ще один із Інтел лабс) зробили покращений Memcached-сумісний кеш (за фактом просто допиляли мемкеш), і у них класні результати продуктивності. Мені дуже сподобався огляд цієї статті в блозі "The morning paper" — опис алгоритмів та інше.

Курсивом — мої коментарі як перекладача.
В основі MemC3 інший, ніж у звичайному мемкеше, алгоритм хешування — оптимістичне "кукушечное" хешування (cuckoo), і додатково до цього особливий "CLOCK" алгоритм витіснення. З'єднані разом, вони дають до 30% більш ефективне використання пам'яті і збільшення продуктивності в запитах в секунду до 3 разів у порівнянні з вашим звичайним Memcached (при навантаженнях з переважаючим читанням невеликих об'єктів, що типово для мемкешей у Facebook).
В кінці оригінальної статті є відмінний розбір отриманих результатів з точки зору вкладу застосованих оптимізацій. Це виглядають приблизно так:
image
Повна пропускна здатність (по мережі) в залежності від числа тредів

У цьому розборі ми просто заценим алгоритми, а деталі їх вкрячивания в мемкеш і методики перформанс тестування, будь ласка, читайте в оригінальній статті.

Кукушечное хешування
Спочатку розберемося з звичайним кукушечным хешуванням. Як працює сама звичайна хеш-таблиця? Ви хэшируете ключ і з цього хешу вибираєте клітинку таблиці (bucket або відро:), в яку потрібно вставити або в якій можна знайти відповідне значення ключа. Куку-хешування використовує дві хеш-функції, виходить, дві можливі осередки для вставки або пошуку значення.
Розглянемо наступну таблицю, у якій кожен рядок являє собою комірку, в кожній з яких чотири слота для даних. Слот — це покажчик на самі дані, об'єкт пару ключ-значення.
image
Маючи ключ для пошуку, ми вважаємо для нього два хешу і отримуємо дві можливі осередки. Тобто треба перевірити 2 клітинки × 4 слота = 8 слотів, щоб знайти або не знайти потрібний ключ.
тобто при пошуку в такий хеш-таблиці потрібно багато операцій порівняно з "звичайної" хеш-таблицею.
Кукушечное хешування отримало свою назву із-за того, як обробляється операція вставки. Спершу ми хэшируем ключ X, який збираємося вставляти, використовуючи обидві хеш-функції, і отримаємо дві можливі осередки. Якщо яка-небудь з цих клітинок має порожній слот, то зберігаємо Х туди. Якщо ж всі слоти зайняті, значить, прийшов час якогось ключа посунутися. Випадково вибираємо один слот в одній з цих двох осередків і переміщаємо (або "переселяємо") з нього ключ (назвемо його Y), таким чином звільняючи місце для запису X. Тепер хэшируем вже Y двома хеш-функціями і знаходимо другу комірку, де він міг би перебувати, і намагаємося вставити Y туди. Якщо всі слоти цієї комірки теж заповнені, то переміщуємо якийсь ключ вже з цих слотів, щоб звільнити місце для Y, і продовжуємо робити так, поки порожній слот не знайдено (або поки не досягнемо деякого максимального кількості переміщень, наприклад, 500).
Тут алгоритм поводиться схоже на зозулю — витягує чужий ключ з уже використаного місця і кладе туди свій, звідси і назва.
image
Якщо не виходить знайти вільний слот, то значить, цю хеш-таблицю пора розширювати — збільшувати виділену під неї пам'ять.
Хоча такий алгоритм для вставки, здається, може вимагати виконання цілої послідовності, ланцюжки переміщень, оцінка тимчасової складності операції вставки для куку-хешування — 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% заповнення таблиці).
Цитата з оригінальної роботи
Щоб додати паралелізму у такий алгоритм, потрібно вирішити дві проблеми:
  1. уникнути дід-локов при отриманні лока на клітинки для запису, адже ми не можемо знати наперед, які комірки будуть порушені нашої операцією
  2. уникнути помилкових кеш-миссов, коли в процесі переміщення якийсь ключ вже був прибраний з однієї клітинки, але ще не вставлено нову, а в цей момент сталося зчитування.
Звичайно, строго кажучи, автори не вирішили першу проблему, вони просто забили на неї, так як дозволяють одночасно виконуватися лише однієї операції запису. У реальних умовах в профілі навантаження часто домінує читання, так що це розумний компроміс.
Кеш-миссов (хибно негативних спрацьовувань) можна уникнути, якщо спочатку визначити повну ланцюжок куку-переміщень, але ще нічого не переміщаючи, а потім виконати ці переміщення у зворотному порядку — від останнього порожнього слота до бажаної вихідної вставки. У поєднанні з тим, що операції запису йдуть в один потік, виходить, що кожен окремий обмін гарантовано не викликає яких-небудь додаткових переміщень і може бути виконаний без необхідності наперед блокувати весь ланцюжок.
Найбільш прямолінійна реалізація — брати блокування на кожну з двох комірок, що беруть участь в обміні (обережно з порядком), і розблокувати їх після обміну. Тут потрібно два лока/релізу на кожен обмін.
Ми намагалися оптимізувати продуктивність для найбільш поширеного використання і скористалися перевагою наявності тільки одного треда запису, щоб вибудувати всі 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, і все це при кращому хіт-рейте.
Цитата з оригінальної роботи
Уявіть циклічний буфер бітів і віртуальну годинну стрілку, що вказує на конкретне місце в буфері.
image
Кожен біт являє "вік" (вік) якогось об'єкта пари ключ-значення. Біт дорівнює '1', якщо відповідний ключ використовувався нещодавно, і '0' — в іншому випадку. Будь-яка операція з ключем просто встановлює відповідний біт давності в '1'. При витісненні потрібно перевірити той біт, на який вказує стрілка годинника. Якщо це '0', то можна витіснити відповідний ключ з кеша. Якщо це '1', то записуємо туди '0' і зрушуємо стрілку годинника вперед, на наступний біт. Цей процес повторюється до тих пір, поки не знайдено нульовий біт.
Процес витіснення інтегрований зі схемою оптимістичних блокувань наступним чином:
Коли процес витіснення вибирає ключ-жертву X CLOCK алгоритмом, то він спочатку збільшує лічильник версії ключа X, щоб повідомити іншим тредам, які в даний час читають X, що їм потрібно спробувати ще раз пізніше; потім він видаляє X, роблячи його недоступним для подальшого читання, в тому числі для тих повторних спроб від інших тредів; і, нарешті, збільшує лічильник версії ключа X знову, щоб завершити цикл змін. Зверніть увагу, що всі витіснення і вставки сериализуются з допомогою локов, так що при оновленні лічильників вони не впливають один на одного.
Цитата з оригінальної роботи
На цьому все. Сподіваюся, вам сподобалося так само, як і мені.
Підписуйтесь на хабра-блог okmeter.io!
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.