Устранение дубликатов

Репозитории с поддержкой Xet используют разбиение на блоки по содержимому (CDC) для дедупликации на уровне байтов (~64 КБ данных, также называемых «блоком»). Каждый блок идентифицируется скользящим хэшем, который определяет границы блоков на основе фактического содержимого файла, что делает процесс устойчивым к вставкам или удалению данных в любой части файла. При загрузке файла в репозиторий с поддержкой Xet с помощью клиента, поддерживающего Xet, его содержимое разбивается на блоки переменной длины. После разбиения сохраняются только новые блоки, которых ещё нет в хранилище Xet, всё остальное отбрасывается.

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

Как работает разбиение на блоки по содержимому

Чтобы понять концепцию разбиения на блоки по содержимому, представьте файл как длинный отрывок текста. Система сканирует данные с помощью скользящего хеша — небольшой математической функции, которая перемещается по байтам. Каждый раз, когда хеш совпадает с определённым шаблоном, в этой позиции устанавливается граница блока. Поскольку границы определяются самим содержимым (а не фиксированными позициями), идентичные участки данных всегда образуют одни и те же блоки, даже если окружающее содержимое меняется.

Почему не фиксированный размер блоков?

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

Original file, fixed 6-byte chunks:

  |The qu|ick br|own fo|x jump|s over| the l|azy do|g     |
  chunk1  chunk2 chunk3 chunk4 chunk5 chunk6 chunk7 chunk8

Insert "very " before "lazy":

  |The qu|ick br|own fo|x jump|s over| the v|ery la|zy dog|
  chunk1  chunk2 chunk3 chunk4 chunk5 chunk6 chunk7 chunk8
                                       ~~~~~~ ~~~~~~ ~~~~~~
                                        3 chunks changed!

Хотя было вставлено всего 5 байт, 3 из 8 фрагментов изменились, так как все границы после правки сдвинулись на 5 позиций. В реальных файлах при размере фрагмента 64 КБ даже небольшая правка может сделать недействительными сотни мегабайт фрагментов.

Content-Defined Chunking сохраняет границы стабильными

В CDC границы задаются там, где содержимое совпадает с шаблоном, а не через фиксированные интервалы. Это означает, что вставка влияет только на тот фрагмент, где происходит правка. Фрагменты до и после остаются неизменными:

Original file, content-defined chunks (boundaries marked by "|"):

  |The quick |brown fox |jumps over |the lazy dog|
    chunk 1     chunk 2    chunk 3     chunk 4

Insert "very " before "lazy":

  |The quick |brown fox |jumps over |the very lazy dog|
    chunk 1     chunk 2    chunk 3     chunk 4'
    (same)      (same)     (same)      (changed)

Изменён только 1 из 4 фрагментов — тот, который содержит правку. Остальные три идентичны побайтово и дедуплицируются. Именно поэтому CDC так эффективен для версионируемых данных: при обновлении контрольной точки модели или добавлении строк в набор данных необходимо загрузить и сохранить только изменённые части.

От фрагментов к хранилищу

Полный конвейер дедупликации работает следующим образом:

Когда файл разбивается на фрагменты, хеш каждого фрагмента проверяется с тем, что уже хранится. Это происходит на нескольких уровнях: сначала с фрагментами, уже полученными в текущей сессии загрузки, затем с локальным кэшем метаданных ранее загруженных данных, и, наконец, подмножество фрагментов проверяется со всем хранилищем Xet через глобальный запрос дедупликации. Дублирующиеся фрагменты полностью пропускаются. Новые фрагменты группируются в блоки по 64 МБ и загружаются. Каждый блок хранится один раз в хранилище с адресацией по содержимому (CAS), с ключом, равным его хешу.

Экономия места на практике

Текущая рекомендация Hub — ограничивать размер файлов 200 ГБ. При размере блока 64 КБ файл объёмом 20 ГБ содержит 312 500 блоков, многие из которых остаются неизменными от версии к версии. Git LFS спроектирован так, чтобы фиксировать лишь факт изменения файла и хранить весь его пересмотренный вариант. За счёт дедупликации на уровне блоков бэкенд Xet позволяет сохранять только изменённое содержимое файла (которое может составлять всего несколько КБ или МБ) и безопасно дедуплицировать общие блоки между репозиториями. Для крупных бинарных файлов, встречающихся в репозиториях моделей и наборов данных, это обеспечивает значительное сокращение времени передачи файлов.

For more details, refer to the From Files to Chunks and From Chunks to Blocks blog posts, or the Git is for Data paper by Low et al. that served as the launch point for XetHub prior to being acquired by Hugging Face.