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

via Shutterstock .

Що таке ybc ?

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

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

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

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

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

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

Дизайн ybc

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

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

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

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

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

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

Що далі?

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

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

Висновок

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

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

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

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

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

Рекомендуємо:

10 вересня, Київ - Ukrainian software development Forum 2.0
30 серпня Одеса - Ukraine Dribbble Meetup 2014 в Одесі
Дайджест цікавих вакансій № 144
Як я працював посудомийником в літньому таборі в Америці
Scala дайджест # 1