Алгоритмы в 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'ом
• знание основ алгоритмов и структур данных (графы, хеш-таблицы)