Привет, Хабр! Меня зовут Денис Дерюгин. Последние несколько лет я занимаюсь разработкой баз данных ВКонтакте. Аудитория такой крупной соцсети ежедневно генерирует огромные массивы информации.
В этой статье я расскажу про хранилище ВКонтакте: как оно менялось, что мы делаем для оптимизации занятого места и как гарантируем сохранность данных.
Инфраструктура
Мы используем широкий стек решений: от известных ClickHouse, Hadoop и даже MySQL до собственных баз данных для хранения и обработки специфических сущностей (сообщений, лайков, списков друзей и не только).
Свои базы мы умеем реплицировать, шардировать, переключать мастер между репликами в случае отказа оборудования и так далее — всё то, что вы ждёте от NoSQL баз данных. Об этом я как-нибудь расскажу в другой статье.
Особое место занимает медиаконтент: фотографии, музыка, аудиосообщения. Таких сущностей гораздо меньше, чем, например, текстовых сообщений, но зато они занимают гораздо больше места.
Сравним объёмы текстовых сообщений и фотографий:
Сообщения занимают 600 ТБ данных (без учёта репликации) и отдаются со скоростью 1 ГБ/с в суточном пике.
Фотографии занимают 250 ПБ (без учёта репликации) и отдаются со скоростью 100 ГБ/с в суточном пике (без учёта CDN и кешей).
Когда числа растут на порядки, привычная схема с шардированием и репликацией ломается:
Строить хранилище на быстрых SSD-дисках под петабайты данных — дорого.
Решардировать кластер на сотни петабайт не очень-то удобно.
Для хорошего шардирования хочется иметь однородное железо, и с тысячей серверов это сделать заметно сложнее, чем с сотней.
Привычный фактор репликации ×3 становится особенно затруднительным.
Раздача контента через те же эндпойнты проблематична.
Давайте посмотрим, как это работало давным-давно.
storage0
На первых этапах всё работало просто:
Все файлы (фотографии, документы, музыка) хранились в файловой системе на выделенных серверах.
Копии файлов лежали на соседних дисках.
Для раздачи контента использовался nginx.
Само собой, названия storage0 тогда не существовало — это были просто контент-серверы (отсюда cs в доменном имени).
В такой реализации по ссылке было просто понять, где именно лежит нужный файл. Например:
http://cs871.userapi.com/u00001/-7/x_8e0ca14e.jpg
cs871 — server id;
u00001 — user id;
-7 — album id;
x_8e0ca14e.jpg — ресайз + ID файла.
С одной стороны, это удобно в смысле эксплуатации. Если пришли жаловаться, что с картинкой что-то не то, будет просто понять, где она лежит, зайти по ssh на нужный сервер и потрогать руками этот файлик. С другой стороны, у этого подхода много проблем.
Есть привязка к бизнес-логике. Со временем она меняется: например, появляются файлы, не относящиеся к конкретному пользователю, для каких-то сущностей нет ресайзов и так далее. В итоге получается очень много видов ссылок, в которых всё сложнее разбираться.
Рано или поздно диски кончаются. А за старым контентом приходят значительно реже, поэтому нагрузка на серверы становится неравномерной.
Когда один сервер недоступен (например, из-за аварии или при проведении каких-либо работ), файлы, хранящиеся на нём, будут недоступны для пользователя.
Файлы зеркально пишутся на соседний диск, а значит, если зеркальный диск ломается, такая репликация порождает двойную нагрузку на чтение на оставшуюся реплику. Кроме того, нужно записать данные на свежий диск, и это может занимать много времени.
Сложно убедиться, что состояние консистентно. Если пользователь получил ссылку на файл, а он повреждён, не ясно — то ли он был загружен таким, то ли испортился после этого.
storage1
Следующая реализация была попыткой написать собственную базу данных на C с поддержкой наших любимых технологий: TL RPC и бинлогов.
Фактически это был движок, который по HTTP сам раздавал файлы. Он использовал оптимизированный вариант программной репликации — вместо честной копии двух дисков копии файлов псевдослучайно раскладывались по разным дискам. Соответственно, при выходе диска из строя уже не возникало проблем с двукратным увеличением нагрузки, но его замена всё ещё занимала много времени.
Теперь путь к файлам выглядел примерно так:
https://pp.userapi.com/c855436/v855436281/c7322/fNXTJueKmlA.jpg
c855436 — server_id;
v855436281 — volume_id;
c7322 — local_id;
fNXTJueKmlA.jpg — случайный ID файла.
Структура данных представляет собой бинлог с чек-суммами, так что теперь гарантируется иммутабельность файлов (если фотка битая — значит, её такой загрузили). И хранилище теперь ничего не знает про бизнес-логику бэкенда (пользователи, альбомы, ресайзы…). Но данные остаются привязаны к конкретному серверу, который всё так же может выходить из строя.
storage2
Главное, что нам надо было обеспечить — чтобы контент продолжал раздаваться, даже если сервер недоступен. Необходимое условие для этого — сделать так, чтобы адрес файла не содержал информации ни про сервер, ни про физическое расположение файлов на нём.
Самое простое, что можно сделать для этого — присваивать файлам рандомный идентификатор. Альтернатива — сделать content-addressable хранилище, то есть иметь в качестве ключа хеш от содержимого. Так мы получим ещё и дедупликацию контента на уровне метаинформации. В таком случае, если тысяча пользователей сохранит себе одну и ту же картинку, не надо будет хранить тысячу экземпляров — достаточно хранить тысячу разных ссылок на неё. Например, у нас дедуплицируется примерно 25 % всех изображений — и это чувствительно на наших объёмах.
Но после отвязки адреса файла от его физического расположения мы всё ещё должны как-то узнавать, с какого диска нужно его прочитать при раздаче. Значит, появляется дополнительный слой с метаинформацией, который будет понимать, где что лежит.
Средний объём файла у нас ~150 КиБ, метаинформация о файле (где лежит настоящая копия и прочее — например, время загрузки и тип контента) занимает примерно в тысячу раз меньше. А значит, к метаинформации мы уже можем применить привычные подходы для баз данных!
Получаем двухслойную архитектуру: есть слой нормальной базы данных, который хранит линки на второй слой, где уже нет шардирования и данные лежат вперемешку.
Расширение кластера тогда происходит очень просто:
Когда добавляется новый сервер, он сообщает слою с метаданными о готовности к работе и передаёт свои данные (например, data-центр, количество и тип дисков).
После этого слой с метаинформацией начинает посылать на подключённый сервер новые файлы.
Чтобы нагрузка на чтение была равномерной, данные со старых серверов постепенно уносятся на новые, освобождая место для новых загрузок.
При сбое на одном из серверов копии данных также можно распределить между действующими серверами. Так что бутылочного горлышка нет: и чтение, и запись происходят в разных местах.
Отказоустойчивость
Интуитивно понятно, что чем больше копий сохраняется, тем выше отказоустойчивость. Даже если серверов тысяча, бывает, что-то выходит из строя, и проблемы могут накладываться друг на друга.
Если потеря данных вас не беспокоит, можно хранить и по одной копии — усложнять систему ни к чему. И наоборот, можно хранить по 10 копий, если бюджеты бесконечные. Но чем больше пишется копий, тем дороже стоит хранение данных, поэтому надо искать компромисс.
Часто для распределённых систем ставится условие работоспособности при сбое одного из трёх data-центров. Почему именно один из трёх?
1 из 1 — бессмысленно.
1 из 2 — невозможно достичь консенсуса между равными половинками в случае сетевого сплита.
1 из 3 — минимальный показательный случай.
Для разбора дальше тоже возьмём пример с тремя data-центрами.
Самый простой способ распределения копий файлов — по одной копии в каждом data-центре.
Получается, фактор репликации ×3: данные будут доступны при выходе из строя одного data-центра, и при этом в оставшихся двух может сломаться какой-нибудь диск. Одна из копий будет всё ещё жива.
Коды коррекции
Если хочется хранить что-то кроме честных копий, придётся, очевидно, хранить результат каких-либо преобразований данных. Сжатие тут не подойдёт: считаем, что данные и так уже сжаты максимально.
Такой тип преобразования данных называется кодами коррекции. Самый простой пример такой функции — это XOR (логическое исключающее «или»).
Дальше под числами D1, D2, … подразумеваются данные, а под R1, R2, ... — избыточные данные, которые мы получаем при генерации кодов коррекции.
Возьмём два числа и посчитаем XOR:
Теперь, если мы потеряем D2, сможем восстановить его из D1 и R.
То же самое можно проделать с файлами — ведь файлы и есть двоичные числа, пусть иногда и очень длинные:
Получили фактор репликации ×1,5! Теперь попробуем уменьшить фактор репликации ещё сильнее.
Казалось бы, всё круто: фактор репликации × (1 + 1 ÷ n), но…
Во-первых, если сломается больше одного файла, ксоры перестанут работать.
Во-вторых, чтобы восстановить один файл, придётся скачать n других файлов.
Само собой, на практике используются более сложные функции, которые находят баланс между отказоустойчивостью, фактором репликации и сложностью восстановления данных.
В мире RAID используется алгоритм EvenODD, который предназначен для обеспечения избыточности данных и защиты системы от сбоев. EvenOdd5 позволяет пережить отказ двух из пяти дисков.
Но этого всё ещё мало. Простой вариант с тремя копиями — это тоже отказоустойчивость на уровне двух дисков.
В том же мире RAID можно подсмотреть идею с two-dimensional parity check, собрав данные в двухмерную табличку. Берём три блока EvenOdd5 и затем для каждого столбца считаем EvenOdd3.
Теперь наглядно видно, что при отказе целой строки данные всё ещё доступны (по свойствам EvenOdd3).
И даже в более катастрофической ситуации всё будет в порядке. Вот тут, например, при недостающих 13 дисках из 28 можно прочитать любой файл.
Впрочем, если очень не повезёт, можно потерять файлы при отказе 6 дисков:
Хорошая новость в том, что отказы оборудования не совсем случайны, так что можно минимизировать шанс таких аварий.
Раскладка
По этой схеме видно, что она плохо накладывается на три data-центра, о которых шла речь раньше. Ни семь столбцов, ни четыре строки на три не делятся, а значит, отказоустойчивость на уровне data-центра обеспечить не получится.
Чтобы адаптировать схему к трём data-центрам, увеличиваем фактор репликации — и считаем, что один столбец с данными из семи всегда заполнен нулями.
Теперь можно в каждом data-центре разместить по два столбца. По свойствам EvenOdd будем переживать потерю одного из трёх data-центров.
Внутри data-центра можно раскидать блоки с данными по случайным серверам. Для разных блоков столбцы тоже нужно перемешивать, чтобы не было выделенного data-центра, в котором лежат только избыточные данные.
Проблемы
Вроде бы всё хорошо, но с таким подходом возникают новые проблемы.
Сразу формировать блоки не получится
Раньше всё было просто: взял копию — записал на диск. В новой реализации надо связывать данные и ждать, пока в блок наберётся достаточная пачка.
Разные паттерны чтения и записи
В случае с копиями можно решать, откуда качать файл (например, в зависимости от загруженности серверов). Когда копий нет, а оригинал файла лежит отдельно, нужно либо обращаться к исходнику напрямую, либо заниматься восстановлением, что сопряжено с чтением дополнительных данных и их прокачкой по сети.
Нужно организовать перемещение данных
Пока данные свежие и к ним обращаются часто, их лучше хранить в виде копий. И только спустя время (например, через несколько недель) рационально переходить к блокам. Но при переходе из копий в блоки надо что-то делать с двумя из трёх дубликатов, которые становятся просто не нужны.
Амплификация нагрузки
Представим, что из строя вышел один диск и стал недоступен один фрагмент данных.
По свойствам алгоритма его можно восстановить. Для этого потребуется скачать три оставшихся известных фрагмента.
Но на практике поломка одного диска приведёт к перераспределению нагрузки на другие компоненты. В результате возросшая нагрузка может спровоцировать и их выход из строя. Возможно, это будет не отказ диска — например, может кончиться сеть на сервере.
В таком случае, чтобы восстановить изначальный фрагмент, придётся выкачать 8 дополнительных частей. А это восьмикратная нагрузка на сеть и диск. Соответственно, чтобы сохранить возможность восстановления всех данных, желательно закладывать кратный запас по параметрам диска и сети.
Удаления
При работе с копиями файл можно удалить в любой момент. Но после связывания файлов в блок просто так удалить данные не получится, поскольку в этом случае каждый файл становится аргументом для функции (EvenOdd). То есть надо хранить все данные, даже если какой-то из файлов в блоке уже не нужен.
Поэтому мы реализуем своего рода garbage collection — ждём, чтобы накопилось нужное количество удалённых фрагментов, и только после этого полностью разбираем блок. Но в нашем случае прибегать к этому приходится редко, поскольку фотографии и другие медиафайлы из ВКонтакте удаляются нечасто.
Большие файлы
Пока файлы небольшого размера — всё понятно реализуется. Когда речь идёт о файлах на несколько гигабайт, могут возникать проблемы с репликацией, нагрузками на сеть и не только. Ксорить такие длинные числа очень неудобно.
Интуитивное решение — «есть слона по частям», то есть обращаться с такими файлами как с набором файлов поменьше.
Самый простой с точки зрения реализации подход к дроблению — добавить манифест, у которого будет список своих фрагментов (отдельных файлов). Тогда разные кусочки файла попадут в разные шарды слоя с метаинформацией, и не будет возникать бутылочных горлышек.
В такой реализации есть важное преимущество. Так, если у вас есть два больших файла (например, по 10 ГБ), которые отличаются только несколькими байтами данных, а остальные фрагменты идентичны, то автоматически получаем дедупликацию большей части файла.
Но есть и сложность — появляется зависимость от большого количества шардов. И в случае сбоев даже на одном из них это может стать проблемой и не позволит полностью скачать или загрузить нужный файл.
Альтернативный подход — поселить весь манифест в одном шарде. То есть у нас в слое метаинформации каждый фрагмент знает, что файл состоит из определённых объектов, которые лежат на разных дисках. И мы занимаемся репликацией на уровне одного шарда.
Кроме уменьшения бласт-радиуса мы получаем возможность ещё одной оптимизации: при первом подходе фрагменты файла попадут в разные блоки кодов коррекции.
Во втором подходе можно сложить все фрагменты в один блок.
Это значит, что при недоступности какого-то фрагмента придётся качать меньше данных для восстановления: какие-то части будут уже на руках, потому что мы и так качаем файл. Аналогично с удалениями: если файл занимает блок целиком, garbage collection значительно упрощается.
Заключение
Наш опыт показывает, что чем выше требования к вместительности, надёжности и гибкости управления хранилищем, тем больше надо думать над всевозможными оптимизациями и их комбинациями. И направлены такие оптимизации должны быть не только на повышение отказоустойчивости, но и на улучшение утилизации ресурсов, снижение зависимости между блоками данных и упрощение работы с файлами (поиска, загрузки, удаления).
При этом важно, что наш подход — не серебряная пуля. Но он подходит конкретно под наши требования, наш формат данных и их объём, поэтому имеет право на жизнь и может быть полезен в похожих исходных условиях.
А какая архитектура хранилищ выстроена в ваших проектах? Делитесь в комментариях.