Ефективне зберігання: як ми з 50 Пб зробили 32 Пб



Зміни курсу рубля два роки тому змусили нас замислитися про способи зниження вартості заліза для Пошти Mail.Ru. Нам знадобилося зменшити кількість закуповуваного заліза і ціну за хостинг. Щоб знайти, де заощадити, давайте подивимося, з чого складається пошта.


Індекси і тіла листів складають 15 % обсягу, файли — 85 %. Місце для оптимізацій треба шукати у файлах (аттачах в листах). На той момент у нас не була реалізована дедупликация файлів; за нашими оцінками, вона може дати економію в 36 % всього обсягу пошти: багатьом користувачам приходять однакові листи (розсилки соціальних мереж з картинками, магазинів з прайсами тощо). У цьому пості я розповім про реалізацію такої системи, зробленої під керівництвом PSIAlt.

Сховище метаінформації
Є потік файлів, і треба швидко розуміти, дублюється файл чи ні. Просте рішення — давати їм імена, які генеруються на основі вмісту файлу. Ми використовуємо sha1. Початкове ім'я файлу зберігається в самому листі, тому про нього піклуватися не треба.

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

Тепер заллємо туди файл. Нам цікаво запитати у сховища, чи є в тебе файл з sha1? Це означає, що треба все sha1 зберігати в пам'яті. Назвемо місце для зберігання fileDB.



Один і той самий файл може бути в різних листах; значить, будемо вести лічильник кількості листів з таким файлом.



При додаванні файлу лічильник збільшується. Близько 40 % файлів віддаляється. Відповідно, при видаленні листа, в якому є файли, залиті в хмару, треба зменшувати лічильник. Якщо він досягає 0 — файл можна видалити.

Тут ми зустрічаємо першу складність: інформація про лист (індекси) знаходиться в одній системі, а про файл — в іншій. Це може призвести до помилки, наприклад:

  1. Приходить запит на видалення листа.
  2. Система піднімає індекси листи.
  3. Бачить, що є файли (sha1).
  4. Посилає запит на видалення файлу.
  5. Відбувається збій, і лист не видаляється.


У цьому випадку лист залишилося в системі, а лічильник зменшився на одиницю. Коли вдруге прийде видалення цього листа — ми ще раз зменшимо лічильник і отримаємо проблему. Файл може бути ще в одному листі, а лічильник у нього нульовий.



Важливо не втратити дані. Не можна допустити ситуацію, коли користувач відкриває лист, а файлу там немає. При цьому зберігати на дисках трохи зайвих файлів не проблема. Достатньо мати механізм, який однозначно покаже, коректно чи ні лічильник звівся до нуля. Для цього ми завели ще одне поле — magic.



Алгоритм простий. У листі разом з sha1 від файлу ми генеруємо і зберігаємо ще одне довільне число. Всі запити на заливку або видалення файлу робимо з цим числом. Якщо прийшов запит на заливку, то до що зберігається magic додаємо це число. Якщо на видалення — віднімаємо.

Таким чином, якщо всі листи коректне кількість разів збільшили і зменшили лічильник, то magic теж дорівнюватиме нулю. Якщо він відмінний від нуля — видаляти файл не можна.

Давайте розглянемо це на прикладі. Є файл sha1. Він залитий один раз, і при заливці лист згенерувало для нього випадкове число (magic), рівне 345.



Тепер приходить ще один лист з таким же файлом. Воно генерує свій magic (123) і заливає файл. Новий magic підсумовується зі старим, а лічильник збільшується на одиницю. В результаті в FileDB magic для sha1 став дорівнює 468, а counter — 2.



Користувач видаляє другий лист. З поточного magic віднімається magic, запам'ятований у другому листі, counter зменшується на одиницю.



Спочатку розглянемо ситуацію, коли все йде добре. Користувач видаляє перший лист. Тоді magic і counter стануть рівними нулю. Отже, дані консистентны, можна видаляти файл.



Тепер припустимо, що щось пішло не так: перший лист відправило дві команди на видалення. Counter (0) говорить про те, що посилань на файл не залишилося, однак magic (222) сигналізує про проблему: файл видаляти не можна, поки дані не наведені до консистентному станом.



Давайте докрутим ситуацію до кінця і припустимо, що і перший лист видалено. У цьому випадку magic (-123) говорить про неконсистентності даних.



Для надійності відразу ж, як тільки лічильник став дорівнює нулю, а magic — немає (в нашому випадку це magic = 222, counter = 0), файлу виставляється прапор «не видаляти». Так що навіть якщо після безлічі додатків і вилучень по дикому збігом обставин magic і counter зрівняються з нулем, ми все одно будемо знати, що проблемний файл або видаляти його не можна.

Повернемося до FileDB. У будь-суті є деякі прапори. Плануєте ви чи ні, але вони знадобляться. Наприклад, вам треба позначити файл як неудаляемый.



У нас є всі властивості файлу, крім головного: де він фізично лежить. Це місце ідентифікує сервер (IP) і диск. Таких серверів з диском повинно бути два.



Але на одному диску лежить багато файлів (у нашому випадку — близько 2 000 000). Отже, у цих записів FileDB в якості місця зберігання будуть одні і ті ж пари дисків. Так що зберігати цю інфу в FileDB марнотратно. Виносимо її в окрему таблицю, а в FileDB залишаємо ID для вказівки на запис в новій таблиці.



Думаю, очевидно, що, крім такого опису пари, потрібно ще поле flags. Забігаючи вперед, скажу: під прапори лежить інформація про те, що диски зараз залочены, наприклад один вилетів і другий копіюється, тому нічого нового на них писати не можна.



Також нам треба знати кількість вільного місця на кожному диску. Додаємо ці поля в таблицю.



Щоб все працювало швидко, FileDB і PairDB повинні бути в оперативній пам'яті. Візьмемо Tarantool 1.5. Відразу скажу, що зараз слід використовувати останню версію. У FileDB п'ять полів (по 20, 4, 4, 4 і 4 байти), разом 36 байт даних. Ще на кожен запис зберігається header розміром 16 байт плюс по 1 байту на довжину кожного поля. Разом виходить 57 байт на одну запис.


Tarantool дозволяє задати в конфіги мінімальний розмір для алокації, так що можна звести практично до нуля розмір накладних витрат по пам'яті. Ми будемо аллоцировать рівно стільки, скільки треба під одну запис. У нас 12 000 000 000 файлів.

(57 * 12 * 10^9) / (1024^3) = 637 Gb

Але це не все, нам потрібен індекс поля sha1. А це ще 12 байт на запис.

(12 * 12 * 10^9) / (1024^3) = 179 Gb

Разом виходить близько 800 Gb оперативної пам'яті. Але не забуваємо про репліки, а це значить × 2.


Якщо беремо машини з 256 Gb оперативної пам'яті, то нам потрібно вісім машин.

Ми можемо оцінити розмір PairDB. Але середній розмір файлу у нас 1 Мб і диски розміром 1 Tb. Це дозволяє зберігати близько 1 000 000 файлів на диску. Значить, нам треба близько 28 000 дисків. Одна запис в PairDB описує два диска, отже, в PairDB 14 000 записів. Це дуже мало в порівнянні з FileDB.

Заливка файлів
Зі структурою баз даних розібралися, тепер перейдемо до АПІ для роботи з системою. Начебто потрібні методи upload і delete. Але згадаймо про дедуплікаціі: не виключено, що файл, який ми намагаємося залити, вже є в сховищі. Немає сенсу заливати його другий раз. Отже, потрібні такі методи:

  • inc(sha1, magic) — збільшити лічильник. Якщо файлу немає — повернути помилку. Згадуємо, що ще нам потрібен magic. Це дозволить захиститися від невірних вилучень файлів.
  • upload(sha1, magic) — його слід викликати, якщо inc повернув помилку. Значить, такого файлу немає і треба його залити.
  • dec(sha1, magic) — викликається, якщо користувач видаляє лист. Спочатку ми зменшуємо лічильник.
  • GET /sha1 — завантажуємо файл просто по http.

Розберемо, що відбувається під час upload. Для демона, який реалізує цей інтерфейс, ми вибрали протокол iproto. Демони повинні масштабуватися на будь-яку кількість машин, тому не зберігають стан. До нас приходить з сокету запит:



По імені команди ми знаємо довжину заголовка і зчитуємо спочатку його. Зараз нам важлива довжина файлу origin-len. Треба підібрати пару серверів для його заливки. Просто викачуємо весь PairDB, там всього кілька тисяч записів. Далі застосовуємо стандартний алгоритм вибору потрібної пари. Складаємо відрізок, довжина якого дорівнює сумі місць всіх пар, і випадково вибираємо точку на відрізку. В яку пару потрапила точка на відрізку — та і вибрана.



Однак вибирати пару таким простим способом небезпечно. Уявіть, що всі диски заповнені на 90 % і ви додали порожній диск. З величезною ймовірністю всі нові файли будуть литися на нього. Щоб уникнути цієї проблеми, потрібно брати для побудови загального відрізка не вільне місце пари, а корінь N-го ступеня від вільного місця.

Пару вибрали, але наш демон потоковий, і якщо ми почали стримить файл на сторедж, то зворотної дороги немає. Тому, перш ніж заливати реальний файл, спочатку відправляємо невеликий тестовий. Якщо заливка тестового файлу пройшла, тоді віднімаємо з сокета filecontent і стримим його на сторедж. Якщо ні — вибираємо іншу пару. Sha1 можна вважати на льоту, тому його ми теж перевіряємо відразу при заливці.

Розглянемо тепер заливку файлу від loader до обраної парі дисків. На машинах з дисками ми підняли nginx і використовуємо протокол webdav. Прийшов лист. У FileDB цього файлу ще немає, а значить, його треба через loader залити на кілька дисків.



Але нічого не заважає ще одному користувачу отримати такий же лист: припустимо, у два листи адресата. У FileDB цього файлу поки немає; значить, ще один loader буде заливати точно такий же файл і може вибрати цю пару.



Швидше за все, nginx вирішить проблему коректно, але нам треба все контролювати, тому зберігаємо файл зі складним ім'ям.



Червоним виділена частина імені, в якій кожен loader пише випадкове число. Таким чином, два PUT не перетинаються і заливають різні файли. Коли nginx відповів 201, loader робить атомарну операцію MOVE, вказуючи кінцеве ім'я файлу.



Коли другий loader дольет свій файл і теж зробить MOVE, файл перезапишется, але це один і той же файл — проблем не буде. Коли він виявиться на дисках, треба додати запис у FileDB. Тарантул у нас розбитий на два спейсу. Поки ми використовуємо тільки нульовий.



Однак замість простого додавання запису про новому файлі ми використовуємо збережену процедуру, яка або збільшує лічильник файлу, або додає запис про файл. Чому так? За час, коли loader перевірив, що файлу немає в FileDB, залив його і пішов запис, що хтось інший вже міг залити цей файл і додати запис. Вище ми розглядали як раз таку ситуацію. У одного листа два одержувача, і два loader'а почали його заливати. Коли другий закінчить, він теж піде в FileDB.



У цьому випадку другий loader просто инкрементирует лічильник.

Тепер перейдемо до процедури dec. Для нашої системи пріоритетні два завдання — гарантовано записати файл на диск і швидко віддати його клієнту з диска. Фізичне видалення файлу генерує навантаження на диск і заважає першим двом завданням. Тому його ми переносимо в офлайн. Сама процедура dec зменшує лічильник. Якщо останній став дорівнює нулю, як і magic, то файл більше нікому не потрібен. Ми переносимо запис про нього з space0 в space1 в тарантуле.

decrement (sha1, magic){
counter--
current_magic –= magic

if (counter == 0 && current_magic == 0){
move(sha1, space1)
}
}

Valkyrie
На кожному сторедже у нас є демон Valkirie, який слідкує за цілісністю і консистентностью даних, як раз він і працює з space1. Один диск — один інстанси демона. Демон перебирає файли на диску один за іншим і перевіряє, якщо запис про файл space1, іншими словами — чи потрібно його видалити.



Але між перенесенням файлу в space1 при виконанні операції dec() і виявленням файлу валькирией проходить час. Отже, між цими двома подіями файл може бути залитий ще раз і знову опинитися в space0.



Тому Valkyrie відразу перевіряє, чи не з'явився файл в space0. Якщо це сталося і pair_id запису вказує на пару дисків, з якою працює поточна валькірія, то видаляємо запис з space1.



Якщо записи не виявилося, то файл — кандидат на видалення. Все ж між запитом до space0 і фізичним видаленням є часовий проміжок. Стало бути, в цьому зазорі знову ж таки є ймовірність появи запису про файл space0. Тому ми поміщаємо файл на карантин.



Замість видалення файлу перейменовуємо його, додаючи в ім'я deleted і timestamp. Тобто фізично ми видалимо файл timestamp + якийсь час, вказане в конфіги. Якщо стався збій і файл вирішили видалити помилково, то користувач прийде за ним. Ми відновимо файл і виправимо помилку, не втративши дані.

Тепер згадуємо, що дисків два, на кожному працює своя Valkyrie. Валькірії ніяк не синхронізовані один з одним. Виникає питання: коли видаляти запис з space1?



Робимо дві речі. Для початку призначаємо для конкретного файлу одну з Valkyrie майстром. Робиться це дуже просто: по першому біту з назви файла. Якщо він 0, то майстер — disk0, якщо 1, то майстер — disk1.



Тепер рознесемо їх за часом. Згадаймо: коли запис про файл знаходиться в space0, там є поле magic для перевірки консистентности. Коли ми переносимо запис у space1, magic не потрібен, тому запишемо в нього timestamp часу переносу в space1. Тепер Valkyrie master буде обробляти записи в space1 відразу, а slave буде додавати до timestamp затримку і обробляти записи пізніше + видаляти їх з space1.



За рахунок цього ми отримуємо ще один плюс. Якщо на майстрі файл пішов в карантин помилково, то при запиті на майстер ми це побачимо в логах і розберемося. Клієнт, який запитував файл, тим часом сфолбечится на slave, і користувач отримає файл.

Ми розглянули випадок, коли Valkyrie знаходить на диску файл з ім'ям sha1 і у цього файлу (як кандидата на видалення) є запис у space1. Давайте розглянемо, які варіанти можливі.

Приклад. Файл є на диску, але про нього немає запису в FileDB. Якщо в розглянутому вище випадку Valkyrie master з якихось причин певний час не працював, slave встиг помістити файл на карантин і видалити запис з space1. У цьому випадку ми теж ставимо файл на карантин через sha1.deleted.ts.

Ще приклад. Запис є, але вказує на іншу пару. Це може статися при заливці файлу, якщо один лист прийшов двом адресатам. Давайте згадаємо схему.



Що трапиться, якщо другий loader лив файл не на ту ж пару дисків, що і перший? Він инкрементирует лічильник в space0, але на парі дисків, куди він лив, залишаться сміттєві файли. Ми йдемо на цю пару і перевіряємо, що файли читаються і збігається sha1. Якщо все ОК — то такі файли можна відразу видаляти.

Ще Valkyrie може зустріти файл на карантин. Якщо термін карантину закінчився, то файл видаляється.

Тепер Valkyrie натикається на хороший файл. Його треба прочитати з диска і перевірити цілісність, порівняти з sha1. Потім сходити на інший диск з пари і з'ясувати, чи є файл. Для цього достатньо HEAD-запиту. Цілісність файлу перевірить демон, запущений на тій машині. Якщо на поточному машині цілісність файлу порушена, то він тут же завантажується з іншого диска. Якщо на диску файл відсутній, то заливаємо його з поточного диска на другий.

Нам залишилося розглянути останній кейс: проблеми з диском. Після моніторингу адміни розуміють, що це сталося. Ставлять диск в режим service (readonly) і на другому диску запускають процедуру размува. Всі файли з другого диска розкидаються по іншим парам.

Результат
Повернемося до початку. Наша пошта виглядала так:


Після переїзду на нову схему ми заощадили 18 Pb:


Пошта стала займати 32 Pb (25 % — індекси, 75 % — файли). Вивільнені 18Pb дозволили нам довгий час не купувати нове залізо.
Джерело: Хабрахабр

0 коментарів

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