Как создать дедуплицирующую файловую систему с нуля? Опыт TATLIN.BACKUP

Дедупликация — это технология устранения дубликатов повторяющихся данных в системах хранения. Она позволяет экономить дисковое пространство, а значит и деньги, потраченные на организацию хранения.

Вместо того чтобы сохранять идентичные копии данных, система дедупликации заменяет их ссылками на единственный экземпляр оригинального блока. Это особенно полезно в резервном копировании и архивировании, где одни и те же файлы могут храниться многократно.

Дедупликация бывает двух основных типов:

• Файловая — устраняет копии целых файлов, если они идентичны.
• Блоковая — находит повторы на уровне фрагментов данных. Она бывает:
  • с фиксированными блоками, когда происходит сравнение частей файла одинакового размера,
  • с плавающими блоками — границы блоков определяются специальными алгоритмами.

Блоковые методы, как правило, обеспечивают более высокую эффективность, потому что часто информационные системы вносят относительно небольшие изменения в файлы баз данных или логов. Вычленение этих изменений позволяет не сохранять заново файл целиком. Для этого данные разбиваются на небольшие блоки, для которых вычисляются уникальные подписи. Перед сохранением система сравнивает подпись нового блока с подписями уже сохраненных блоков: если совпадение найдено, сохраняется только ссылка на существующий блок, а не его копия. Дедупликация может происходить в реальном времени перед записью в постоянное хранилище (inline) или после записи (post process). При post process-дедупликации данные считываются с диска, обрабатываются и сохраняются, но уже в дедуплицированном виде.

В системах хранения резервных копий данные часто повторяются. В таких случаях дедупликация позволяет:

• Уменьшить объем требуемого дискового пространства благодаря хранению только уникальных данных в разы или десятки раз в зависимости от типов файлов и сценария использования.
• Экономить сетевой трафик в случае использования алгоритма дедупликации (например, протокола T-BOOST для TATLIN.BACKUP, о котором я расскажу ниже) на машине-источнике — при резервном копировании передаются только уникальные данные, что может ускорить процесс копирования и снижает нагрузку на сеть.

Кратко расскажу, что такое TATLIN.BACKUP и как он работает. Это специализированная система хранения данных, или PBBA (Purpose-Built Backup Appliance), на базе контроллера и дисковых модулей YADRO с проприетарным программным обеспечением. В отличие от систем хранения данных общего назначения, эти устройства разработаны для записи, хранения и чтения резервных копий с учетом всех их особенностей.

До реализации протокола T-BOOST в TATLIN.BACKUP дедупликация производилась только на контроллере. Система разбивает поток поступающих на него данных на блоки и проверяет их на дубликаты среди уже сохраненных. Мы используем алгоритмы построения блоков переменной длины, за счет чего вероятность нахождения дубликатов заметно выше по сравнению с нарезкой файла на блоки одинаковой длины.

Каждый блок данных в системе идентифицируется с помощью криптографического хеша blake3, который вычисляется на основе его содержимого. Этот хеш служит подписью блока и позволяет проверить целостность и уникальность блока.

Криптографическая хеш-функция, которую мы используем, имеет околонулевую вероятность возникновения коллизий: два разных блока данных не должны случайно получить одинаковый хеш.

Файлы в TATLIN.BACKUP хранятся, если говорить упрощенно, в виде упорядоченных списков подписей блоков. Каждая подпись — фактически уникальный ключ, который ссылается на конкретный блок данных. Этот же механизм отвечает за дедупликацию. Более того, можно проверить корректность прочитанного с диска блока, пересчитав его подпись.

Для разделения файлов на блоки в TATLIN.BACKUP мы используем алгоритм FastCDC. Расскажу, какие проблемы он позволяет решить.

FastCDC — это алгоритм разбиения данных на блоки переменной длины (Content Defined Chunking, CDC). В отличие от нарезки с фиксированной длиной блока, FastCDC решает проблему смещения границ (boundary-shift problem), которая возникает при вставке новых данных в файл. Например, если в начало файла добавить байт, то при использовании разбиения с фиксированной длиной все последующие блоки изменятся. Алгоритмы с переменной длиной блока, такие как FastCDC, устраняют эту проблему, поскольку устанавливают границы блоков на основе содержимого данных, используя хеш-функцию для определения неких избранных последовательностей байтов. Впрочем, если байт будет добавлен в середину какого-то блока, то этот блок будет потерян, а граница будет корректно определена уже для следующего от него блока.

FastCDC выделяется среди других алгоритмов высокой скоростью обработки потока байтов. Основная вычислительная нагрузка на систему создается операциями разбиения данных на блоки и их сжатия, поэтому оптимизация алгоритма разбиения напрямую влияет на общую производительность. Это важно для пользователей, так как система должна успеть записать резервную копию, пока открыто технологическое окно — время, в течение которого нужно сделать резервную копию. Часто это связано с необходимым для создания копии простоем информационной системы.

Основная идея FastCDC заключается в следующем: среди всех возможных последовательностей байтов (множество A) выделяется подмножество B. Когда в файле обнаруживается последовательность из множества B, алгоритм устанавливает границу блока (anchor) сразу после этой последовательности.

Так как хранение подмножества B напрямую невозможно из-за огромного количества возможных последовательностей, используется хеш-функция. Она преобразует каждую последовательность байтов в числовое значение, которое определяет класс этой последовательности.

После нахождения опорного байта (anchor) алгоритм проверяет, удовлетворяет ли он дополнительным условиям. Например, FastCDC не создаст новый блок, если точка находится слишком близко к границе предыдущего блока и минимальный размер блока еще не достигнут. Если опорные байты не найдены, система отрежет блок по его максимально допустимому размеру.

У дедупликации на СХД есть пара важных особенностей. Во-первых, алгоритмы разбиения на блоки и сжатия работают на самом контроллере СХД, то есть приходится задействовать его вычислительные мощности. Во-вторых, мы должны отправить на него все данные для резервного копирования, даже если они содержат избыточную информацию. Это создает нагрузку на сеть или увеличивает время резервного копирования при узком канале.

К примеру, у нас есть массив данных объемом 100 ГБ. Мы полностью передаем их на СХД, загружая сеть. Уже на контроллере СХД система проводит сравнение новых данных с хранящимися и удаляет дубликаты. После сравнения оказывается, что уникальных данных в массиве всего 5 ГБ.

В итоге мы загрузили сеть «лишними» данными, а также потратили вычислительные мощности СХД на вычисление границ блоков и сжатие полученных уникальных данных. Чем больше данных мы копируем, тем выше нагрузка на сеть и СХД. Соответственно, может потребоваться докупить ресурсы и улучшить пропускную способность сети.

И тут на помощь приходит протокол T-BOOST. Но, чтобы предметно поговорить о нем, нам придется вернуться в прошлое — на этап создания архитектуры дедуплицирующей файловой системы TBFS для TATLIN.BACKUP .

На этапе проектирования мы делали упор на:

• высокую производительность — мы создаем высоконагруженную систему, поэтому производительность и оптимальное использование ресурсов критичны,
• надежность работы — сохранность и неизменность данных, в том числе в случае неожиданного отключения питания,
• скорость разработки — нам было важно вывести продукт на рынок в сжатые сроки, при этом обеспечить его качественную поддержку, быструю имплементацию нового функционала и высокую скорость работы с данными.

Другими словами, от системы нужны были отказоустойчивость и оптимизация ресурсов, чтобы справляться с записью терабайтов резервных копий и при этом укладываться в установленный клиентом временной интервал. При этом важно было продумать механизмы сохранности и неизменности данных.

Мы решили реализовать виртуальную файловую систему, которая исполняется в Linux в виде сервиса в пользовательском пространстве. Она монтируется в каталоги Linux и получает доступ к файлам через интерфейс FUSE (Filesystem in Userspace). Этот интерфейс позволяет реализовывать файловые системы не в пространстве ядра, а в пользовательском пространстве UNIX-подобных ОС. Благодаря модулю ядра FUSE и соответствующей библиотеке, которая предоставляет API для пользовательских приложений, нам не нужно писать и загружать код непосредственно в ядро. Это существенно упрощает создание и тестирование файловых систем.

Для разработки файловой системы мы выбрали Rust. Это был своего рода эксперимент, который показал, что язык хорошо подходит для крупных проектов с низкой скоростью изменения требований при грамотной организации процесса разработки. В нашем случае у него есть несколько очевидных плюсов:

• Сокращает время, затрачиваемое на код-ревью, что ускоряет процесс разработки и позволяет сконцентрироваться на действительно важном, а не проверке ветвлений на предмет создания мертвой ссылки.
• Позволяет переложить ответственность за обнаружение многих опасных операции на компилятор и статические проверки, особенно относительно работы с памятью: это очень важно, поскольку TBFS — это сложный многопоточный сервис с асинхронной средой выполнения Tokio внутри.

TATLIN.BACKUP имеет сервис-ориентированную архитектуру (SOA). TBFS — один из сервисов системы, который представляет собой единый исполняемый файл. Такой подход позволяет держать все нужное для файловой системы в одном месте и дает несколько преимуществ:

• Все компоненты работают в едином адресном пространстве, поэтому не нужно обеспечивать их взаимодействие и создавать сетевые механизмы коммуникаций.
• Уменьшается количество копирований памяти — это важно когда надо обрабатывать гигабайты данных в секунду. Кроме того повышается локальность данных: кеш процессора используется чаще и дольше. Это важно для ускорения вычислений — процессор не должен простаивать ожидая подгрузки данных из RAM.
• Весь код работает как единое приложение, что позволяет централизованно управлять выделением ресурсов, например распределением CPU и RAM.
• Легко проводить профилирование, поскольку все компоненты работают в едином процессе.

Важно, что в TATLIN.BACKUP на этапе разработки мы «зашили» многие функции. С их помощью мы дополняем функционал решения. T-BOOST — пример такого «расконсервирования», потому что на стадии создания архитектуры мы понимали, что такой протокол в системе нужен.

TBFS содержит две крупные подсистемы: клиент, который предварительно обрабатывает данные, и хранилище. При разработке мы обеспечили их потенциальную отделимость друг от друга. Так они могут взаимодействовать между собой либо локально, либо по сети через проксирование вызовов функций. В TATLIN.BACKUP версии 1.0 проксирование не было реализовано: мы его сделали позднее.

Разберем подробнее эту схему. На контроллере TATLIN.BACKUP работает проприетарная файловая система TBFS с механизмами дедупликации, компрессии и проверки целостности данных, что необходимо для обслуживания протоколов NFS и SMB. Внутри TBFS так же есть сервер T-BOOST, который обслуживает запросы клиентов T-BOOST на проверку уникальности блоков и их сохранение. Клиент TBoost запущен как исполняемый файл в случае с tb_agent или как systemd-сервис в случае TBoost service на машине-источнике данных для резервного копирования. Он разворачивает файловую систему на клиентской машине. Клиент разбивает данные на блоки, опрашивает СХД на предмет уникальности подписей, а также производит сжатие и декомпрессию блоков.

TBoost создает общий ресурс (папку) на машине-источнике и анализирует файлы, которые туда переносятся. Затем он по API запрашивает у TATLIN.BACKUP подтверждение уникальности данных. Контроллер СХД сверяется со своей базой данных и сообщает клиенту, уникален блок или нет. После этого TBoost отсеивает неуникальные данные и передает только ту информацию, которая отсутствует на СХД.

СХД и клиентская файловые системы разграничены набором абстрактных интерфейсов. У клиента TBoost есть проксирующая реализация этих интерфейсов, которая пробрасывает вызов функции по сети.

Наши эксперименты показали, что скорость копирования данных на СХД по протоколу T-BOOST выросла — при обработке файла с избыточной информацией протокол передает только уникальные данные. Сразу оговорюсь, что скорость зависит от набора данных, на котором мы тестируем систему, пропускной способности сети и ресурсов, которые доступны на хосте. Как правило, чем больше в датасете неуникальных данных, тем выше скорость — при условии, что клиент TBoost не будет ограничен недостаточными CPU-ресурсами хоста. К сожалению, общепринятого подхода и набора эталонов для тестирования эффективности дедупликации не существует. Поскольку мы используем интерфейс FUSE в UNIX-подобных ОС, то логично использовать его максимальную пропускную способность как бенчмарк для TATLIN.BACKUP с TBoost. Чем ближе мы к лимиту FUSE, тем лучше реализована наша система.

T-BOOST позволяет снизить нагрузку на сеть и систему TATLIN.BACKUP, но взамен требует от хоста, на котором работает клиент TBoost, мощного процессора и достаточного объема оперативной памяти. Для многих пользователей это — предпочтительный вариант организации резервного копирования.

Скорость восстановления данных из резервной копии также может вырасти за счет кеширования блоков на клиенте и передачи сжатых данных благодаря TBoost.

Есть несколько проблем, которые помогает решить T-BOOST:

• передает только уникальные данные на СХД,
• экономит вычислительные ресурсы и дисковое пространство TATLIN.BACKUP,
• лишен указанных выше недостатков клиентов NFS/SMB-протоколов.

Отмечу, что TATLIN.BACKUP может работать без TBoost: приложение можно не устанавливать, если в нем нет необходимости.

Система TATLIN.BACKUP уже развернута у наших клиентов. Мы активно ее развиваем и семимильными шагами догоняем решения, которые появились на рынке намного раньше.

У нас в планах выпуск SDK, который можно интегрировать в популярные системы резервного копирования данных. Напомню, что TATLIN.BACKUP — это хранилище резервных копий. SDK позволит отказаться от использования интерфейса FUSE, что автоматически снимет ограничение на скорость передачи данных, которое накладывает FUSE.

Мы также планируем выпустить релиз с поддержкой снапшотов, которые дадут возможность реализовать репликацию. Она уже находится в разработке.