Алгоритмы в Git / Git Internals
Git для большинства — привычный набор команд: commit, merge, push, pull. Но за ними стоит достаточно сложная распределённая система с content-addressable storage, алгоритмами и протоколами обмена данными. Как связаны commit и «патчи» из изменений в коде? Как Git находит общее начало двух веток? Когда изменения можно объединить автоматически, а когда Git честно отказывается угадывать смысл результата? Как клиент и сервер определяют, какие объекты уже известны обеим сторонам, не передавая полную историю?
На курсе мы будем последовательно строить ответы на эти инженерные вопросы, чтобы чёрный ящик под названием Git стал немного прозрачнее. Разберём physical storage: packfiles, .idx, delta compression; посмотрим на используемые алгоритмы и структуры данных: object graph, обход commit DAG и поиск merge base; diff-алгоритмы семейства Myers, а также patience и histogram heuristics; three-way merge и устройство conflict state в index. Увидим, как Git приходит к компромиссам между компактностью и стоимостью чтения, обсудим протокол negotiation между клиентом и сервером через want/have, а также оптимизации и механизмы, которые делают Git применимым к большим репозиториям: commit-graph, Bloom filters, reachability bitmaps, partial clone.
Сквозной проект курса — создание собственного минимального Git-сервера, совместимого с настоящим клиентом Git для clone и fetch. Мы начнём с чтения объектов и refs, затем реализуем базовый протокол, discovery capabilities, negotiation общей истории и генерацию packfile.
Пререквизиты курса:
- хотя бы раз в жизни пользовались Git'ом
- знание основ алгоритмов и структур данных (графы, хеш-таблицы)
Занятия
15 лекций, 8 практикЛекция 1
Версии проекта и устройство Git
Лекция 2
Точное устройство базы объектов
Практика 1
Один OID, два репозитория
Лекция 3
Изменяемое состояние Git
Практика 2
Авторизация внутри транзакции ссылок
Лекция 4
Граф коммитов и выбор истории
Лекция 5
Общие предки и merge base
Лекция 6
Алгоритмы построения diff
Практика 3
bisect на DAG и несовершенный оракул
Лекция 7
Трёхстороннее слияние и конфликты
Лекция 8
От loose objects к packfile
Практика 4
Зелёный CI для уже не того кода
Лекция 9
Дельта-сжатие внутри packfile
Лекция 10
Достижимость и жизненный цикл объектов
Лекция 11
Путь fetch по сети
Практика 5
Планировщик физического хранения
Лекция 12
Согласование общей истории при fetch
Практика 6
Иерархические квоты без блокировки push
Лекция 13
Серверная сторона fetch
Лекция 14
Три дорогих запроса и три индекса
Практика 7
Миграция недоверенного проекта
Лекция 15
Масштабирование больших репозиториев
Практика 8
Merge queue как спекулятивный планировщик

