Винахід колеса , або як була розроблена бібліотека кешування Ybc

via Shutterstock .

Що таке ybc ?

Ybc - це легковага низкоуровневая бібліотека на C , що реалізує API для кешування довільних blob'ов. На поточний момент працює тільки під Linux , але може бути легко портована на будь-яку платформу завдяки тому , що весь платформозавісімий код захований за платформонезавісимость інтерфейсом , реалізація якого знаходиться в суворо відведеному місці.

З чого все почалося?

Пару років тому мені потрапила на очі стаття Notes from the Architect , де автор програми Varnish розповідає про те , як треба писати сучасний софт під сучасні платформи (операційні системи + залізо). Після цього я прочитав ще одну статтю того ж автора - You're Doing It Wrong , де він розповідає про те , наскільки важливе розуміння locality of reference при створенні високопродуктивного коду під сучасні платформи. Для тих , кому влом читати оригінали статей , привожу дві основні думки :

Сучасне залізо напхане купою багаторівневих кешей . Тому циклічне звернення до однієї і тієї ж області пам'яті може працювати в 100500 разів швидше , ніж циклічне звернення до випадкових областям пам'яті.
Пам'ять , з якою працюють ваші програми на сучасних операційних системах , має мало спільного з фізичною RAM. Швидкість доступу за різними адресами цієї пам'яті може відрізнятися в мільйони разів. Причому швидкість доступу по одному і тому ж адресою пам'яті в різні інтервали часу може також відрізнятися в мільйони разів.

Ці « таємні знання » можуть сильно допомогти при оптимізації алгоритмів по продуктивності. Для любителів Матана є чудова серія статей - « What every programmer should know about memory » , а також Cache - oblivious algroithm.

Начитавшись вищезгаданої « єресі» , я вирішив випробувати свої сили. Спочатку покопався в исходниках Varnish'а і виявив там наступні « фатальні недоліки» :

Додавання нового запису в переповнений кеш або застарівання вже існуючої запису може призводити до великої кількості операцій введення-виведення по випадкових адресами пам'яті. Як відомо любителям файлів підкачки на HDD , такі операції можуть сильно гальмувати.
Звернення до існуючої записи також може призводити до кількох операцій введення-виведення , якщо всі записи в кеші не поміщаються в RAM.
Реалізація кеша в Varnish була схильна DoS- атаці на хеш- колізії.
При креш Varnish'а все закешовану записи губилися .
Код написаний не мною.

Для « рішення» цих недоліків спочатку були написано кілька патчівдляVarnish, потім була созадана реалізація B - heap і D - heap в одному флаконі під назвою gheap. Потім було вирішено , що краще створити власну реалізацію кеша , позбавлену вищезазначених недоліків. Так зародилася ybc .

Дизайн ybc

Відстеження і видалення записів з кеша в Varnish'а реалізовано за допомогою двох механізмів , присутніх у більшості класичних реалізацій кешу:

LRU - списку , в якому зберігаються покажчики на всі записи , відсортовані за часом останнього звернення до цих записів . При кожному зверненні до запису її покажчик переноситься в початок LRU - списку. При переповненні кеша Varnish проходиться по цьому списку з кінця , видаляючи записи , до яких дуже давно не було звернень.
Heap'а , в якому зберігаються покажчики на всі записи , впорядковані за expiration time . У « голові» heap'а завжди знаходиться запис , яка повинна застаріти раніше всіх . При кожному додаванні нового запису її покажчик заноситься в heap . Періодично Varnish видаляє застарілі записи за допомогою цього heap'а .

Як можна бачити , основний недолік класичної реалізації кешу - підвищеного кількість звернень до пам'яті за довільним адресами , яке виливається в операції введення -виведення при великих обсягах даних.
Головною метою при проектуванні ybc було позбавлення від цього недоліку. Ця мета була досягнута за допомогою радикального способу - повної відмови від LRU з heap'ом на користь «принципово нового» механізму - циклічного буфера на зразок того , який використовується в Log - structured filesystem . Кешувального дані записуються по черзі в циклічний буфер. При переповненні буфера старі дані затираються новими . При цьому структура кеша реалізована таким чином , що відстежувати затирають запису або ініціалізувати циклічний буфер при створенні немає необхідності. При спробі звернення до затертої або пошкодженої записи ybc легко виявить це і поверне результат « запис не знайдено ». Зберігання даних у вигляді циклічного буфера , спроектованого в mmap'ed файл , дало наступні «безкоштовні» фичи :

записи не втрачаються при креш або примусовому рестарт програми, що використовує бібліотеку ybc .
Розмір кеша може перевищувати обсяг фізичної RAM в сотні разів.
закешовану дані ніколи не попадуть в файл підкачки . Це добре з точки зору безпеки і продуктивності - при нехвтке пам'яті операційна система просто « забуде » про cold cacheсторінки пам'яті із за - mmap'ленного файлу замість того , щоб вивантажувати їх у файл підкачки.
Не потрібно городити город з балансуванням закешовану даних між оперативною пам'яттю і файлом - про це подбає механізм віртуальної пам'яті в операційній системі.

Яким же чином ybc знаходить необхідну запис по ключу ? Для цього служить модифікована open addressing хеш -таблиця , адаптована під потреби кеша. Модифікація полягає в тому , що при переповненні хеш- таблиці ybc може спокійно затирати старі записи новими , не турбуючись про memory leak ' ах . Також модифікована хеш -таблиця «безкоштовно » забезпечила захист від DoS- атаки на хеш- колізіївнаслідок обмеженого розміру bucket'ов .

Підрахуємо кількість необхідних звернень до довільних ділянок пам'яті (які, як відомо , на великих обсягах даних перетворюються на дуже повільніоперації вводу-виводу) при читанні читанні і запису для класичної реалізації кеша і для кеша ybc .

Читання
- Для класичного кеша - мінімум дві при кеш- промаху (одна для звернення до хеш- Бакета по ключу , наступні - для перегляду кожного запису в хеш- Бакета ) , мінімум п'ять при кеш- попаданні (плюс дві для перенесення покажчика в початок LRU - списку і одна - для читання закешовану даних).
- Для ybc - одна при кеш- промаху ( для виявлення факту того , що в хеш- таблиці відсутня відповідна запис) , дві при кеш- попаданні - одна для звернення до хеш- таблицю , друга - для читання даних з циклічного буфера.
Запис в переповнений кеш
- Для класичного хеша - багато ( динамічне виділення пам'яті для даних і для хеш -запису , вставка покажчика на дані в хеш- Бакет , довільну кількість звернень до елементів LRU - списку для звільнення необхідної пам'яті під новий запис , довільну кількість звернень до елементів expiration heap'а для видалення застарілих записів , довільну кількість викликів функції звільнення динамічно виділеної пам'яті під видаляються записи та допоміжні елементи в LRU - списку , expiration heap'е та хеш - таблиці ) .
- Для ybc - одна ( для додавання запису в хеш- таблицю). Звернення до пам'яті при додаванні даних в циклічний буфер не враховується , тому що ця область пам'яті з великою часткою ймовірності буде знаходитися в кешах процесора , якщо недавно інший елемент був записаний в кеш.

Корисні і не дуже оптимізації , використовувані в ybc

В ybc також було застосовано безліч дрібних оптимізацій , націлених на мінімізацію working set size . Ось деякі з них :

Дрібні об'єкти , розмір яких не перевищує розміру сторінки пам'яті , можуть переміщатися з певною часткою ймовірності в початок циклічного буфера. Це необхідно для того , щоб « запакувати » дрібні часто запитувані об'єкти в мінімальну область пам'яті. Також це дозволяє продовжити час життя таких об'єктів - адже при переповненні циклічного буфера вони не будуть затерті.
Кеш хеш- таблиці для зберігання часто запитуваних записів . При виявленні запису в цьому кеші вдається уникнути потенційно повільного обігу в основну хеш- таблицю , яка може не вміщатися в RAM.
Мінімізація динамічного виділення пам'яті. Зазвичай алгоритми динамічного виділення пам'яті призводять до довільного кількістю звернень по довільним адресами пам'яті. У ybc динамічне виділення пам'яті використовується тільки в одному дуже специфічному місці - для реалізації dogpile effect handling .
« Упаковка » структур один в одного замість повсюдно використовуваної практики - використання покажчиків на вкладені структури . Це мінімізує кількість разименованія покажчиків (які можуть бути повільними на певних платформах ) при роботі з даними структурами.
Мінімізація копіювання великих обсягів даних з однієї області пам'яті в іншу. Ybc API реалізовано таким чином , щоб користувачі могли уникати більшості операцій копіювання даних. Це може дати істотний виграш у швидкості при роботі з великими blob'амі зразок багатогігабайтними фільмів.
Використання skiplist - ів для прискорення відстеження , які записи в даний момент читаються/пишуться . Дане відстеження необхідно для того , щоб при переповненні цілкліческого буфера не відбулося порушення цілісності читається/Речі в даний момент запису. Skiplist'и виявилися найкращим рішенням , що дозволив уникнути динамічного виділення пам'яті в найбільш часто исполняемом коді.
Мінімізація кількості і тривалості блокувань в часто исполняемом коді. Це необхідно для того , щоб декілька процесорів могли паралельно виконувати корисну роботу , а не чекати , поки інші процесори звільнять блокування. У ybc навіть є спеціальний режим , що відключає всі блокування . Він дозволяє лінійно нарощувати продуктивність ybc для операцій читання шляхом збільшення кількості задіяних CPU в системі. Але за швидкість потрібно платити - в цьому режимі сильно зростає навантаження на CPU для великих blob'ов , тому він підходить тільки для роботи з порівняно маленькими записами .

Що далі?

Після завершення основних робіт над ybc я почав думати , де б його застосувати . Перше, що спало на думку, - реалізація memcached сервера . Програмувати небудь складніше hello world на C мені не дуже хотілося , тому вирішив створити binding'і для ybc на якому-небудь більш доброзичливому для application programming мовою. Вибір припав на Go . У підсумку на Go за допомогою ybc були реалізовані два PoC -додатки :

go - memcached - memcached сервер з « фішками » начебто cache persistence , довільного обсягу Кешована даних ( може перевищувати обсяг RAM) , довільного розміру окремо Кешована записів .
go - cdn - booster - простий кешуючий http - проксі для статичного контенту. На відміну від nginx , зберігає весь закешовану контент в двох , а не в мільйоні файлів. Також не потребує cleaner - процесі , відповідальним за видалення файлів із застарілим контентом.

В планах є бажання використовувати ybc для створення squid killer'а - прозорого кешуючого http - проксіз можливістю кешування range request'оввід основних місць для розміщення відеофайлів на зразок ютуба та іксхамстера . Такий проксі міг би економити вхідний трафік для інтернет -провайдерів , а також віддавати юзерам закешовану контент на швидкості 1Гбіт/с. Поки до нього не дійшли руки.

Висновок

Кілька порад:

Вивчайте деталі реалізації сучасних платформ (залізо , операційна система , програмне оточення ) . Це дозволить вам писати більш ефективний код на будь-якій мові програмування.
Пишіть більше різного коду (бажано застосовного на практиці) на різних мовах програмування , не соромтеся винаходити « велосипеди» . Це дозволить вам робити усвідомлений вибір на користь програмних архітектур і мов програмування , орієнтованих на практичне , а не теоретичне застосування .

Якщо після прочитання цієї статті ви раптом вирішите допомогти в розробці та просуванні ybc , то мені потрібна допомога за такими напрямами:

Портування ybc на інші платформи .
Створення binding'ов для ваших улюблених мов програмування .
Створення високорівневих API , більш зручних для використання в порівнянні з API ybc .
Написання різних додатків , що використовують ybc .

Із задоволенням відповім на будь-які ваші питання до коментарів до цієї статті.

Опубліковано: 14/07/14 @ 06:53
Розділ Різне

SEO Блог