Entry tags:

git guts

Git Guts (part 1)
Где-то около месяца назад я полностью прочитал man git, и немножко поэкспериментировал с внутренностями git, чтобы понять, как же там все устроено внутри.

Оказалось, внутренне все сделано просто и элегантно.

В отличие от сложно-бинарных репозиториев subversion или недорепозиториев CVS, в git все кристалльно просто, и доступно даже на самом низком уровне.

Репозиторий git - это просто коллекция т.н. объектов, объединенных ссылками друг на друга. Каждый объект - это некий файл специального формата. У каждого объекта есть "имя", которое вычисляется как SHA1 хеш содержимого объекта и записываемся как шестнадцатеричное представление этого хеша. Длина хеша равна 20 байтам, так что шестнадцатеричное представление содержит 40 букв и цифр.

Для тех, кто не знает что такое хеш и зачем он нужен - поясняю буквально на пальцах.

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

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

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

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

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

Кстати, вычислить эту сумму для прозвольного файла в системе может специальаная утилита sha1sum, входящая в coreutils.

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

Расположены все объекты в каталоге .git/objects. Для того чтобы не сваливать все объекты в одну директорию, git отделяет первые два символа имени объекта и создает поддиректорию с таким именем в .git/objects.

Вот например, содержимое базы некоторого git-репозитория

.git/objects/a4/b7fce097055c3cbd6879db9625f9a3890cc409
.git/objects/8c/3c7fbcd903744b20fd7567a1fcefa99133b5bc
.git/objects/e9/65047ad7c57865823c7d992b1d046ea66edf78

То есть в ней хранятся три объекта:

1. a4b7fce097055c3cbd6879db9625f9a3890cc409
2. 8c3c7fbcd903744b20fd7567a1fcefa99133b5bc
3. e965047ad7c57865823c7d992b1d046ea66edf78

Сделано это для ускорения поиска объекта по его имени. Несложно догадаться, что такой нехитрый прием ускоряет поиск в 256 раз.

Добавлю напоследок, что объекты в git бывают четырех типов - blob, tree, commit и tag.



Продолжение следует. Если есть какие-то вопросы или комментарии - милости прошу.