Привет, Хабр! Меня зовут Александр Черепанов, я руковожу группой в команде Data Path TATLIN.BACKUP.
Мы уже писали в блоге про наше хранилище. Сначала про то, как с нуля делали дедуплицирующую файловую систему: чанки, FastCDC, протокол T-BOOST. Потом про то, что такое снапшоты, зачем они нужны и как мы их устроили на уровне архитектуры: экстенты, файл как список их идентификаторов, выбор Mark-and-Sweep вместо подсчета ссылок для сборки мусора. С тех пор снапшоты уже почти год в проде, и, судя по отзывам, работают неплохо.
Эта статья принципиально другая. Мы достанем отвертку и залезем внутрь: разберемся, на чем технически строятся снапшоты, как мы их сделали поверх RocksDB, при чем тут LSM-дерево и Bloom-фильтр размером с системный диск ноутбука.
В прошлых сериях
TATLIN.BACKUP — специализированная система хранения данных (СХД) для резервных копий. В базовой конфигурации это около 690 ТБ, а с учетом глобальной дедупликации и сжатия (суммарно 6:1) эффективная емкость доходит до 4 ПБ и выше.
Внутри СХД есть наша собственная файловая система TBFS (TATLIN.BACKUP File System), которая режет данные на чанки переменной длины алгоритмом FastCDC еще до записи на диск. Уникальность чанка проверяет по его хешу, а по сети — в идеале по нашему протоколу T-BOOST — гоняет только уникальные данные.
К слову, СХД отлично защищена от аппаратных сбоев:
Copy-on-Write чтобы не сломать то, что уже записано;
T-RAID — собственный RAID от YADRO с возможностью гибкой настройки избыточности;
WAL (Write-Ahead Log) для восстановления после сбоев;
журналирование файловой системы.
Метаданные устроены в три уровня: файлы ссылаются на экстенты, экстенты — на последовательности чанков. Экстент неизменяем: любое изменение файла создает новый экстент, старый никто не трогает. Отсюда и весь фокус со снапшотами: чтобы заморозить состояние файловой системы, достаточно скопировать список идентификаторов экстентов и файловую структуру, а не сами данные.
Ральф Меркл в 1979 году, изобретая хеш-деревья, вряд ли думал, что через сорок с лишним лет ими будут спасать резервные копии от шифровальщиков. Но лес из таких деревьев (спасибо Сергею Ли за метафору, он рассказывал об этом на HighLoad++ 2024) — это ровно то, чем стало наше хранилище чанков. Ниже разберемся, что происходит, когда этот лес надо сфотографировать.
Метаданные и LSM-дерево
Метаданные файлов мы храним в RocksDB — встраиваемой key-value-базе, реализующей структуру LSM-дерева (Log-Structured Merge-Tree).
В нашем случае это компромисс: оно плохо приспособлено для быстрого поиска по произвольному ключу (пришлось добавлять кеши и Bloom-фильтры, о них тоже поговорим), зато отлично использует сильные стороны RAM (быстрая произвольная запись) и дисков (быстрая последовательная запись).
Из чего состоит LSM-дерево RocksDB:
Memtable — небольшая таблица в оперативной памяти, которая быстро принимает вставки. Сбрасывается на диск, когда заполнилась.
SST-файлы (Sorted String Tables) — файлы на диске, которые не изменяются после создания, сортируются по ключу, а еще знают диапазон ключей внутри. Индекс всех SST и диапазонов лежит в RAM для быстрого поиска.
WAL (Write-Ahead Log) — журнал еще не сброшенных на диск записей, нужен, чтобы восстановить Memtable после сбоя питания или простой перезагрузки процесса.
Стоит упомянуть Column Family, отдельное LSM-дерево внутри одной базы со своими Memtable и SST, но с общим WAL. Иначе транзакции между Column Family перестали бы быть консистентными. Мы используем их вместо префиксов в ключах — так не приходится тратить байты на то, что и так знает сама структура базы.
Главное для нас свойство — неизменяемость SST-файлов. Если файл на диске никогда не меняется, клонировать базу можно не копированием, а созданием жестких ссылок (хардлинков) на эти файлы. Тяжелее, чем в ZFS, где клонируется просто указатель на карту блоков, зато почти бесплатно.
Дешевые снапшоты через Checkpoint
В прошлой статье мы писали, что снапшот — это копия списка идентификаторов экстентов, на которые ссылаются файлы. Технически эту копию для нас делает не наш код, а RocksDB через механизм Checkpoint.
При вызове API чекпоинта RocksDB создает хардлинки на все текущие SST-файлы и физически копирует небольшие файлы, которые часто меняются: WAL-файлы, MANIFEST, CURRENT. Из этого вытекает несколько удобных свойств:
снапшот создается почти мгновенно — хардлинк на порядок дешевле копирования SST;
SST-файлы переиспользуются между снапшотами: между двумя соседними снапшотами меняется небольшая часть метаданных, поэтому большинство SST остаются общими;
читать из снапшота можно без конфликтов с основной базой, RocksDB спокойно открывает чекпоинт в режиме read-only или secondary;
откат к прошлому состоянию — TBFS просто начинает работать с другой базой, практически подмена указателя.
Тут стоит уточнить одну вещь: чекпоинт клонирует всю базу целиком, со всеми Column Family, а не только те части, что отвечают за метаданные файлов. Экстенты и структура контейнеров с чанками попадают туда же. В теории это «лишнее» копирование, но раз хардлинк ничего не стоит, экономить на этом просто незачем: дешевле продублировать то, что не нужно, чем городить отдельный механизм частичного чекпоинта Column Family, которого в RocksDB пока и нет.
Маленькая путаница, о которую легко споткнуться: у RocksDB тоже есть метод
GetSnapshot(). Но это не про файлы, а про MVCC-срез базы для консистентного чтения прямо во время работы. Получается два смысла: снапшот файловой системы и снапшот итератора RocksDB, который еще будет упомянут.
Мусор, который жалко выбрасывать не глядя
Файл удалили — экстенты тоже нужно удалить. Но экстенты пересекаются между собой, а один и тот же чанк живет в десятках файлов и снапшотов одновременно. Раньше мы уже разбирали, почему подсчет ссылок нам не подошел: счетчик на каждый экстент означает синхронную запись при каждом изменении, а это отнимает много времени.
Так еще и любая рассинхронизация счетчика и метаданных при сбое питания оборачивается либо утечкой места, либо потерей данных. Архитектурный разбор читайте в предыдущей статье, а мы сразу к деталям.
Двухэтапный Garbage Collector
Мы выбрали Mark-and-Sweep, чтобы не хранить счетчики ссылок. Однако их все равно надо считать: нужно запомнить все экстенты во всех файлах всех файловых систем, а также в их снапшотах, чтобы потом удалить остальные экстенты, нигде не упомянутые.
Экстентов миллионы, чанков десятки миллиардов. Такие хешсеты бы в оперативку не влезли, и пришлось бы аллоцировать своп на пару терабайт.
С похожей проблемой столкнулся Бертон Блум. Он придумал свой фильтр для задачи хранения орфографического словаря: это были времена еще до «640 килобайт памяти хватит всем», поэтому точный список слов туда просто не помещался.
Идея Блума была в том, чтобы хранить не сами слова, а битовую маску. Несколько хеш-функций от слова зажигают несколько бит: если хотя бы один из них погашен — слова во множестве точно нет, а если все зажжены — слово, скорее всего, есть, но не наверняка. Полвека спустя тот же трюк выручает нас ровно с той же проблемой, только счет памяти идет не на килобайты, а на десятки гигабайт.
Итак, вооружившись увесистым фильтром Блума, идем собирать мусор.
Этап 1
Собираем все живые экстенты, никого не удаляя. Обходим текущие файловые системы и все их снапшоты, и заносим идентификаторы встреченных экстентов в один общий Bloom-фильтр.
Приятный побочный эффект такого дизайна: размер фильтра зависит от количества уникальных экстентов в системе, а не от количества снапшотов. Хоть 1024 снапшота, хоть один. Если все они ссылаются на одни и те же экстенты (а благодаря дедупликации SST так обычно и есть), фильтр не растет. Множество есть множество, повторное попадание в него ничего не стоит.
Этап 2
Сверяем и чистим экстенты, а затем чанки. Проходим по хранилищу экстентов и удаляем те, которых нет в фильтре. Для всех выживших экстентов собираем уже второй Bloom-фильтр, на этот раз по хешам уровней леса Меркла. Проходим по уровням леса сверху вниз до самых чанков и удаляем отсутствующие в фильтре элементы.
Важное свойство напоследок: ложноположительное срабатывание Bloom-фильтра означает, что мы не удалим мусор, который могли бы. То есть немного не доубираем место за этот проход GC. Ложноотрицательных срабатываний в конструкции фильтра не бывает в принципе, поэтому живой чанк никогда не попадет под нож по ошибке. Со следующим проходом GC оставшийся мусор соберется — классическая для вероятностных структур игра в пользу безопасности, а не скорости уборки.
Еще вопрос, который нам обычно задают: что происходит с чанком, который дописывается прямо во время построения фильтра? Мы строим фильтр в рамках консистентного среза RocksDB — да, того самого GetSnapshot() из врезки выше, не путать с нашими файловыми снапшотами. Поэтому все записи, попавшие в базу уже после начала обхода, для текущего прохода GC попросту не видны и будут учтены на следующем. Еще существует проблема с «воскрешением» чанков, которые ранее были отмечены на удаление, но во время работы GC в CХД записали файл с этим чанком, но об этом в другой раз.
Очень удобно получилось с откатами на снапшот: Mark-and-Sweep на Bloom-фильтрах эту проблему не замечает вовсе. Ему все равно, из какой ветки истории пришел экстент, было бы что посчитать. Сама подмена базы при откате остается дешевой операцией — сложность достается не операции отката, а проходу GC, который и должен, аки Матфей, разбираться в раскинутых веером версиях истории, отделяя зерна живых экстентов от плевел.
Мертвые файлы и POSIX
СХД выглядит для пользователя как обычная файловая система, а значит, обязана соблюдать семантику POSIX. Еще в ранних версиях Unix заложили решение, которое с тех пор никто не отменял: unlink() убирает файл из каталога немедленно, но, если на него есть открытые файловые дескрипторы, они остаются рабочими до close(). Это старый и заслуженный трюк для временных файлов: открыл, сразу удалил, работаешь с дескриптором, а система сама подчистит данные, когда файл закроют или процесс упадет.
У нас это правило встречается с чекпоинтами неотвратимым образом. Пока файл открыт, а на диске уже «удален», его метаданные все еще должны существовать в актуальной (мутабельной) части базы, иначе некому будет ответить на чтение через открытый дескриптор. Настоящая проблема возникает в другой момент: когда мы создаем новый снапшот прямо сейчас, а в актуальной базе все еще висит запись про файл, который с точки зрения каталога давно не существует. Хардлинкнуть эту запись в новый чекпоинт как есть — значит, подложить будущему пользователю снапшота файл-призрак, которого он по всем правилам видеть не должен. Кроме того, призрак будет удерживать данные файла.
Поэтому в момент создания снапшота мы вычищаем из него такие зомби-записи — удаленные файлы с живым дескриптором. Старые, уже зафиксированные снапшоты это не трогает: они как были заморожены, так и остаются. Это единственное официально разрешенное исключение из правила «не пишите в чекпоинты», которое мы сформулируем чуть ниже, — разовая, ограниченная по объему правка сразу после создания снапшота, а не постоянный поток записей в его дальнейшую жизнь.
Этот «лайфхак» мы скоро поменяем на усложнение логики работы GC. Он будет в курсе наличия зомби и будет пропускать их экстенты, заполняя фильтр. А о том, почему писать в снапшоты плохо, узнаем дальше.
Space Amplification и боль от Compaction
Вот тут и начинается настоящая боль LSM-дерева. Любая запись в снапшот, будь то уборка зомби-файлов выше или что угодно еще, заставляет его SST-файлы расходиться с SST основной базы. В какой-то момент срабатывает Compaction: RocksDB берет несколько SST, сливает их вместе, убирает дубликаты и пишет новые файлы.
Compaction обесценивает смысл хардлинков ровно в тот момент, когда до них добирается. База снапшота начинает переписывать файлы, место на дисках расходуется, а хардлинки, которые должны были достаться почти бесплатно, превращаются в полноценные копии.
Мы перебрали несколько вариантов:
Подход | Проблема |
Полностью отключить Compaction | Базы бесконтрольно раздуваются, а мусор из них никто не убирает. |
Запускать Compaction вручную | API ручной компактификации — блокирующий. Безопасно закрыть базу во время нее нельзя, RocksDB прямым текстом предупреждает об этом, а в каком состоянии база проснется после падения — большой вопрос. |
Отключить Compaction только для снапшотов | RocksDB не дает такой гранулярности: можно вырубить всю фоновую работу целиком, но тогда достанется и основной базе. |
Временное решение было до обидного простым: реже создавать новые SST-файлы, чтобы реже провоцировать Compaction. Для этого увеличили Write Buffer Size (Memtable дольше копит данные в RAM перед сбросом на диск) и размер WAL (позволяет откладывать сброс на диск дальше).
Кстати об этих и не только опциях нам подсказал RocksDB Tuning Advisor — специальная полезная утилита, которая из логов RocksDB и заложенного великого трансцендентного знания может выдать неплохой список советов по подкрутке параметров базы данных.
Честно говоря, бесплатных обедов и тут не бывает: чем больше Memtable, тем больше оперативной памяти она постоянно держит под собой. И тем дольше повторяется WAL при восстановлении и включении. Мы сознательно выменяли часть времени на восстановление после перезапуска или отключения на уменьшение Space Amplification в спокойном режиме работы.
Чего нам не хватает в RocksDB
Пока писали статью, накопился список пожеланий разработчикам RocksDB. Оставлю их тут, вдруг кто-то из них заглянет в статью.
Checkpoint Aware Compaction. Было бы славно, даже восхитительно, если бы Compaction знал про существование хардлинков и не разрушал общие SST-файлы почем зря. С умом пережимал только то, что не расшарено с чекпоинтами. Границы ума и эвристики обсуждаемы.
Асинхронная отказоустойчивая ручная Compaction. Сейчас API ручной компактификации блокирующий и небезопасный при закрытии базы, а хотелось бы неблокирующий вариант с понятной семантикой восстановления после сбоя.
Больше возможностей копирования. Например, чекпоинт набора конкретных Column Family под новыми именами, тогда снапшоты могли бы быть в пределах одной базы несколькими CF, а не целыми базами. Заодно не помешало бы копирование значений под новыми ключами без лишнего копирования памяти на сторону вызывающего.
LSM на блочном устройстве. LSM-дерево в итоге все равно упирается в файловую систему как в лишний слой абстракции. Если кто-то знает готовую реализацию LSM прямо на блочном устройстве, буду рад обсудить в комментариях.
Выводы
RocksDB остается просто key-value-базой. Использовать ее «из коробки» для высоконагруженных систем, не разбираясь в Compaction и Space Amplification, — это как строить дом на песке и верить, что море никогда не поднимется.
Ключевые уроки, которые мы вынесли при разработке системы:
Реализация снапшотов файловой системы на LSM требует понимания внутренней механики, одного API недостаточно. Кстати, ИИ хотя бы читает документацию!
Compaction — не фоновая мелочь, а механизм, способный аннулировать всю экономию места от хардлинков.
Не пишите в чекпоинты. А если совсем нужно, как в случае с зомби-файлами, делайте это один раз, сразу после создания, и настраивайте базу с поправкой на последствия. Но лучше не пишите.
Bloom-фильтры — мощный инструмент для Garbage Collector полувековой выдержки, но размер и число хеш-функций нужно считать, а не угадывать. Считать тут.
POSIX-семантика была придумана задолго до дедуплицирующих СХД, но продолжает диктовать условия и полвека спустя.
RocksDB Tuning Advisor — отдельный инструмент, которому можно скормить логи вашей базы и текущие настройки, и он подскажет, что подкрутить под ваш паттерн нагрузки. Штука полезная, хотя далеко не всесильная.
Статьи, которые я упоминал в начале:
Что такое снапшоты в СХД и как мы их реализовали в TATLIN.BACKUP →
Как создать дедуплицирующую файловую систему с нуля? Опыт TATLIN.BACKUP →
Если решите повторить что-то из этого на своей LSM-базе — заходите в комментарии, обменяемся шрамами.
