Алгоритмы в Git / Git Internals
⭐️ Лектор
Даниил Орешников
Backend-разработчик в SourceCraft (Yandex), преподаватель курса алгоритмов и структур данных в ИТМО. Призер финалов школьных всероссийских олимпиад по математике и по программированию, NCUMC, MathOpen; координатор/проблемсеттер олимпиад по программированию для школьников.
📢 Анонс
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'ом
– знание основ алгоритмов и структур данных (графы, хеш-таблицы)
🕑 Первая лекция пройдёт 12 сентября с 14:00 до 15:30. Курс будет проходить по субботам с 14:00 в Мраморном зале, ПОМИ РАН, наб. реки Фонтанки, 27, Санкт-Петербург. Записаться на курс можно через личный кабинет или в боте:
▶️ Личный кабинет
▶️ Бот