Является ли стандартизированный алгоритм двоичного сравнения git (delta storage)?

Git использует дельта-сжатие для хранения объектов, похожих друг на друга.

Этот алгоритм стандартизирован и используется в других инструментах? Есть ли документация, описывающая формат? Совместимо ли это с xdelta/VCDIFF/RFC 3284?

Источник

3 ответа

Решение

Я думаю, что дифференциальный алгоритм, используемый для файлов пакета, был связан с одной из дельта-кодировок: сначала (2005) xdelta, а затем libXDiff.
Но затем, как подробно описано ниже, он перешел к пользовательской реализации.

Во всяком случае, как уже упоминалось здесь:

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

(примечание: создание большого количества упаковочных файлов или получение информации в огромном упаковочном файле является дорогостоящим и объясняет, почему git плохо обрабатывает огромные файлы или огромные репозитории.
Смотрите больше в " git с большими файлами ")

Эта тема также напоминает нам:

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

LibXDiff упоминается в этой теме 2008 года.

Однако с тех пор алгоритм эволюционировал, возможно, в индивидуальном порядке, как показано в этом потоке 2011 года, и как заголовок diff-delta.c указывает на то:

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

/*
 * diff-delta.c: generate a delta between two buffers
 *
 * This code was greatly inspired by parts of LibXDiff from Davide Libenzi
 * http://www.xmailserver.org/xdiff-lib.html
 *
 * Rewritten for GIT by Nicolas Pitre <nico@fluxnic.net>, (C) 2005-2007
 */

Подробнее о пакете файлов Git Book:

формат упакованного файла

Git 2.18 добавляет к дельта-описанию в этом новом разделе документации, который теперь (Q2 2018) гласит:

Типы объектов

Допустимые типы объектов:

  • OBJ_COMMIT (1)
  • OBJ_TREE (2)
  • OBJ_BLOB (3)
  • OBJ_TAG (4)
  • OBJ_OFS_DELTA (6)
  • OBJ_REF_DELTA (7)

Тип 5 зарезервирован для будущего расширения. Тип 0 недействителен.

Представительство

Концептуально существует только четыре типа объектов: коммит, дерево, тег и блоб.
Однако для экономии места объект может быть сохранен как "дельта" другого "базового" объекта.
Этим представлениям назначаются новые типы ss-delta и ref-delta, которые действительны только в файле пакета.

И то и другое ofs-delta а также ref-delta сохранить "дельту", которая будет применена к другому объекту (называемому "базовым объектом") для реконструкции объекта.
Разница между ними в том,

  • ref-delta напрямую кодирует 20-байтовое имя базового объекта.
    • Если базовый объект находится в той же пачке, вместо этого ofs-delta кодирует смещение базового объекта в пачке.

Базовый объект также можно отделить, если он находится в той же упаковке.
Ref-delta также может относиться к объекту вне упаковки (то есть так называемой "тонкой упаковке"). Однако при хранении на диске пакет должен быть автономным, чтобы избежать циклической зависимости.

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

  • один для копирования байтового диапазона из исходного объекта и
  • один для вставки новых данных, встроенных в саму инструкцию.

Каждая инструкция имеет переменную длину. Тип инструкции определяется седьмым битом первого октета. Следующие диаграммы соответствуют соглашению в RFC 1951 (формат сжатых данных Deflate).

Источник

Дельта-кодирование Git основано на копировании / вставке.

Это означает, что производный файл закодирован как последовательность кодов операций, которые могут представлять инструкции копирования (например: копировать из базового файла y байтов, начиная со смещения x в целевой буфер) или вставлять инструкции (например, вставлять следующие x байтов в целевой буфер).

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

  1. Скопировать 5 байтов со смещения 7 (скопировать "кеш" из базового буфера)
  2. Вставьте два пробела
  3. Скопировать 5 байтов со смещения 0 (скопировать "прокси" из базового буфера)

Который переводится в кодировку Git становится:

(байты 1-3 представляют первую инструкцию)

  • 0x91 (10010001), который разделен на
    • 0x80 (10000000)(набор старших битов делает это "копированием из базы в вывод")
    • 0x01 (00000001) (означает "увеличить на один байт и использовать его как базовое смещение)
    • 0x10 (00010000) (передвиньте один байт и используйте его как длину)
  • 0x07 (смещение)
  • 0x05 (длина)

(байты 4-6 представляют вторую инструкцию)

  • 0x02 (поскольку MSB не установлен, это означает "вставить следующие два байта в вывод")
  • 0x20 (пробел)
  • 0x20 (пробел)

(байты 7-8 представляют последнюю инструкцию)

  • 0x90 (10010000), который разделен на
    • 0x80 (10000000)(означает "копия")
    • 0x10 (00010000) (передвиньте один байт и используйте его как длину)
  • 0x05 (длина)

Обратите внимание, что в последней инструкции копирования не указывается смещение, что означает смещение 0. Другие биты в коде операции копирования также могут быть установлены, когда необходимы большие смещения / длины.

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

Недавно я поместил библиотеку node.js в github, которая реализует обе функции diff / patch с использованием дельта-кодирования git. Код должен быть более читабельным и прокомментированным, чем тот, что находится в git source, который сильно оптимизирован.

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

Источник

Этот алгоритм стандартизирован и используется в других инструментах?

Формат пакета является частью общедоступного API: протоколы передачи, используемые для операций push и fetch, используют его для отправки меньшего количества данных по сети.

Они реализованы по крайней мере в двух других основных реализациях Git, кроме ссылки: JGit и libgit2.

Поэтому очень маловероятно, что в формат будут внесены несовместимые изменения в обратном направлении, и его можно считать "стандартизированным" в этом смысле.

Этот удивительный файл из документации описывает эвристику, использованную в алгоритме пакета, как забавный комментарий Линуса по электронной почте: https://github.com/git/git/blob/v2.9.1/Documentation/technical/pack-heuristics.txt

Источник
Другие вопросы по тегам