Git. Гибридное устройство деревьев
Что не так с деревьями
В предыдущей статье были рассмотрены все 4 типа объектов внутреннего хранилища Git. Их содержимое преимущественно представляет собой текстовый файл, к которому применяется сжатие по алгоритму zlib, как это было показано на примере blob.
Такой подход позволяет без особых сложностей создавать различные утилиты для взаимодействия с внутренним хранилищем репозитория, даже в обход уже существующих сантехнических команд.
Но давайте попробуем повторить эти манипуляции с объектом tree, который был сформирован при создании второго коммита. Его полный ключ:
2e91f5b82b6fdef912a1f2c00eac01cec57452bc
Наблюдаем, что это объект нужного нам типа, и его основное содержимое состоит из 71 байта информации. Но вот попытка получить сами данные не выглядит успешной. При этом "поломанные символы" отображаются, как в случае прямой распаковки, так и при использовании знакомой команды cat-file.
Что же могло пойти не так?
Типы файлов
Еще на уроках информатики из беззаботных школьных времен или первых курсов университета, принято говорить о делении файлов на бинарные и текстовые. С точки же зрения принципов работы вычислительной техники все файлы являются бинарными, а существующее деление лишь сказывается на способе обработки этих нулей и единиц.
При обработке текстовых файлов оперируют строками, отдельными символами и их кодировкой. А кодировка как раз и определяет сколько и каких байт необходимо записать для каждого отдельного символа.
Например, Java с 9 версии хранит строки в виде массива байт и в зависимости от ситуации использует LATIN-1 или UTF-16. Git в качестве многобайтной кодировки оперирует UTF-8, в которой отдельный символ может потребовать от 1 до 4 байт информации.
"Нестабильный" вес объектов типа tree
Полученный ранее вывод в консоль - это не последствие какой-либо ошибки, а всего лишь особенность хранения содержимого. Если команду cat-file использовать с параметром -p, то вывод немного изменится.
Здесь можем наблюдать два заметных отличия:
1. Все символы начинают отображаться корректно и понятно для человека
2. Данных выводится заметно больше, чем ранее
Первые значения в 79 и 71 байт вполне объяснимы: 71(основное содержимое объекта) + 4(tree) + 1 (символ пробела) + 2(само число 71 в метаинформации объекта) + 1 (NUL символ) = 79(полное содержимое объекта до сжатия)
Но вот понятный нам вывод содержит на 52 байта больше информации, что составляет 73%.
Может по какой-то причине хранение данных для объекта типа **tree** реализовано несколькими файлами? Или у вас возникли какие-то иные предположения за счет чего это происходит? Обязательно поделитесь ими в комментариях.
Гибридное устройство объектов типа tree
До этого мы анализировали содержимое объекта только в текстовом представлении. Самое время взглянуть на него в формате более низкого уровня.
Это полезный навык для IT-специалистов, например, для поиска непечатаемых символов. Из недавнего вспоминается ошибка валидации xml, потому что в сообщении kafka присылали BOM перед xml-прологом.
Мы не будем спускаться до уровня нолей и единиц, а воспользуется HEX-редактором, т.е. представлением в шестнадцатеричном виде.
Первый 15 байт нам уже встречались. Это метка, которая обозначает простой файл, далее символ пробела, наименование файла и NUL.
Далее идут 20 непонятных символов, после которых опять метка 100644 и название второго файла. Заканчивается вывод еще 20 странными символами.
Если же сопоставить последовательность каждых 20 символов с их шестнадцатеричными кодами, то можно заметить следующее:
..#..p.`..?..2..4..z => 8b912315c970c8609f953ff98d32aa123415e97a
.......CK.).wZ....S. => e69de29bb2d1d6434b8b29ae775ad8c2e48c5391
То есть значения справа соответствуют ключам от объектов типа blob для файлов LICENSE и main.txt
В предыдущей статье указывалось, что по алгоритму SHA-1 мы получаем сорока символьный хеш. Так вот для сохранения отдельного "текстового" символа используется минимум один байт информации, а для шестнадцатеричной цифры хватит всего 4 бита, т.е. в два раза меньше.
Это дает экономию в 20 байт для ключа каждого дочернего элемента дерева.
С учетом количества файлов и директорий в реальных проектах суммарно формируется значительный объем информации. Но одновременно это же является причиной, что объекты типа tree представляют собой до сжатия некий гибрид представления данных.
Поиск оставшихся 12 байт
При сравнении количества информации между разными способами вывода содержимого у нас была разница в 52 байта. Мы уже раскрыли секрет экономии 40 байт. Осталось найти всего 12, только вот "лишних" данных от первого вывода не осталось. Тут все более банально, просто параметр -p добавляет данные, которые нужны сугубо для удобства восприятия информации пользователем.
Для каждой из двух записей такой набор состоит из:
1. blob - HEX: 62 6c6f 62; 4 байта - тип дочернего объекта, который однозначно определяется по метке прав доступа 100644
2. пробел после типа дочернего объекта - HEX: 20; 1 байт
3. символ горизонтальной табуляции перед наименованием дочернего объекта - HEX: 09; 1 байт
4. символ перевода строки - HEX: 0a; 1 байт
Да, если по вашим математическим подсчетам (4 + 1 + 1 + 1) * 2 = 14, а не 12, то это также легко объяснить. Просто в данном выводе отсутствует NUL символ после наименования дочернего объекта, который также занимают 1 байт.
Постскриптум
Рассмотренный подход к формированию tree объектов является одним из примеров пользы применения бинарных протоколов. Стоит отметить, что это не единственный механизм Git, который оперирует данными в бинарном формате. Например, есть index, который уже чисто бинарный и использует даже битовые флаги, также существуют бинарные pack-файлы.