Как Git мгновенно сравнивает файлы: Merkle tree

Задумывались, как Git может взглянуть на две директории с сотнями или тысячами файлов и мгновенно понять, совпадают ли они? Если бы мы написали скрипт для этого наивно, то, скорее всего, прошлись бы по каждому файлу и сравнили содержимое побитово. Это операция O(n). Она работает, но с ростом репозитория становится мучительно медленной.

Git делает это за миллисекунды. Давайте разберём, как именно он это делает, не читая каждый файл каждый раз, когда вы вводите команду.

Как Git проверяет содержимое директорий так быстро?

Git использует криптографическую структуру данных, называемую Merkle tree (дерево Меркла). Вместо сканирования сырого содержимого файлов Git присваивает уникальный хеш каждому файлу и каждой директории, сворачивая их в один мастер-хеш.

Представьте, что вы управляете огромной библиотекой книг. Если бы вам нужно было проверить, что два одинаковых здания библиотеки содержат одни и те же книги, чтение каждой страницы заняло бы целые жизни. Вместо этого представьте, что вы генерируете уникальный штрих-код для каждой книги на основе её текста. Затем генерируете штрих-код для полки на основе книг, которые на ней стоят, и, наконец, мастер-штрих-код для всего здания на основе его полок. Если мастер-штрих-коды совпадают, библиотеки идентичны. Git делает именно это, но с вашим исходным кодом.

Как работают вместе blob, tree и commit в Git?

Когда вы создаёте коммит, Git хранит ваши данные в иерархии объектов: blob для содержимого файлов, tree для структуры директорий и commit для метаданных снимка. Каждый уровень генерирует хеш, который полностью зависит от хешей нижележащих уровней.

Допустим, ваша команда разрабатывает стандартное веб-приложение. Когда вы выполняете коммит, Git структурирует данные в три уровня:

Blob

Git берёт сырое содержимое ваших файлов и хеширует его. Создаётся объект blob (binary large object). Blob заботится только о содержимом, полностью игнорируя имя файла.

import hashlib

def create_blob(content):
    # Хешируем содержимое файла (аналогично Git)
    return hashlib.sha1(content.encode()).hexdigest()

# Пример
content = "print('Hello, World!')"
blob_hash = create_blob(content)
print(f"Blob hash: {blob_hash}")  # Вывод: 5a5f... (хеш SHA-1)

Tree

Затем Git создаёт объект tree, представляющий структуру директории. Этот tree содержит имена файлов и ссылки на хеши blob. Git хеширует весь объект tree.

def create_tree(entries):
    # entries: список кортежей (режим, имя, хеш)
    tree_content = ""
    for mode, name, hash_val in entries:
        tree_content += f"{mode} {name}\0{hash_val}"
    return hashlib.sha1(tree_content.encode()).hexdigest()

# Пример: директория с одним файлом
entries = [("100644", "hello.py", blob_hash)]
tree_hash = create_tree(entries)
print(f"Tree hash: {tree_hash}")

Commit

Наконец, объект commit оборачивает корневой tree. Он связывает хеш корневого tree с метаданными: автор, временная метка, хеш родительского коммита. Затем хешируется сам коммит.

def create_commit(tree_hash, parent_hash, author, message):
    commit_content = f"tree {tree_hash}\n"
    if parent_hash:
        commit_content += f"parent {parent_hash}\n"
    commit_content += f"author {author}\n"
    commit_content += f"committer {author}\n"
    commit_content += f"\n{message}\n"
    return hashlib.sha1(commit_content.encode()).hexdigest()

commit_hash = create_commit(tree_hash, None, "Alice ", "Initial commit")
print(f"Commit hash: {commit_hash}")

Почему изменение одного файла меняет хеш коммита?

Потому что структура Merkle tree создаёт строгую цепочку криптографических зависимостей. Изменённый файл порождает новый хеш blob, что заставляет родительский tree сгенерировать новый хеш, вызывая эффект домино вплоть до объекта commit.

В этом истинная сила Merkle tree. Если вы исправите одну опечатку в CSS-файле глубоко в проекте, Git не будет пересканировать остальную кодовую базу. Этот изменённый CSS-файл получает новый хеш blob. Поскольку tree (директория), содержащая этот файл, теперь указывает на новый хеш, хеш tree меняется. Это всплывает вверх до хеша верхнего коммита.

Следовательно, если два хеша коммитов идентичны, у вас есть математическая гарантия, что каждый файл и папка внутри них имеют то же самое содержимое. Если хеши разные, вы мгновенно знаете, что в репозитории что-то изменилось, и Git просто следует по изменённым хешам tree вниз по веткам, чтобы найти, какой именно файл был изменён.

Часто задаваемые вопросы

Какой алгоритм хеширования использует Git?

Исторически Git использует алгоритм SHA-1 для генерации хешей объектов. Хотя SHA-1 имеет известные теоретические уязвимости в строгом контексте безопасности, Git использует его в первую очередь для целостности и согласованности данных. Новые версии Git активно переходят на более безопасный SHA-256.

Хеширует ли Git имя файла или только содержимое?

Git blob хеширует только сырое содержимое файла. Фактическое имя файла и права доступа хранятся и хешируются внутри объекта tree, который указывает на blob. Именно поэтому, если вы переименуете файл без изменения содержимого, Git распознает это как переименование — хеш blob остаётся тем же.

Что происходит со старыми blob при изменении файла?

Git никогда не перезаписывает старые blob. Он создаёт новый объект blob для изменённого содержимого. Старый blob остаётся в локальной базе данных, что позволяет легко переключаться на старые коммиты. Если blob становится полностью недостижимым, он в конечном итоге удаляется фоновой сборкой мусора Git.

Практический вывод

Теперь вы знаете, что Git не сравнивает файлы построчно, а использует Merkle tree для мгновенного сравнения. Попробуйте сами: создайте репозиторий, сделайте несколько коммитов и посмотрите на хеши с помощью git cat-file -p. Убедитесь, что изменение одного файла меняет хеш коммита. Это понимание поможет вам лучше осознать, как Git обеспечивает целостность данных и почему операции с ним такие быстрые.