gitpacking

Общие сведения

Растровые карты достижимости наиболее эффективны, если на диске хранятся растровые карты для одной или нескольких начальных точек обхода. По этой причине Git предпочитает хранить растровые карты для коммитов на вершинах ссылок, поскольку обходы обычно начинаются с этих точек.

Однако при большом количестве ссылок хранить растровую карту для каждой вершины ссылки every нецелесообразно. Это занимает место, а объединение всех этих растровых карт операцией OR обходится дорого.

Один из способов решить эту проблему — создать растровые карты, представляющие groups ссылок. Если при обходе запрашивается вся группа, можно использовать одну такую растровую карту вместо того, чтобы рассматривать каждую ссылку по отдельности. Поскольку эти растровые карты представляют набор объектов, которые были бы достижимы при гипотетическом слиянии всех коммитов, мы называем их растровыми картами псевдослияний.

Обзор

Термин «растровая карта псевдослияния» обозначает пару растровых карт:

Растровые карты псевдослияний могут ускорить обходы растровых карт, если все коммиты для заданного псевдослияния перечислены по обе стороны обхода — напрямую (при явном запросе в составе HAVES или WANTS) либо косвенно (при обнаружении во время обхода для заполнения).

Примеры использования

Предположим, существует растровая карта псевдослияния с большим количеством коммитов, и все они перечислены в разделе WANTS некоторого запроса на обход растровой карты. Если растровые карты псевдослияний включены, механизм растровых карт может быстро определить, что существует псевдослияние, соответствующее некоторому подмножеству требуемых объектов по обе стороны запроса. Затем можно распаковать сжатую EWAH растровую карту и выполнить над ней операцию OR, включив её в результирующую растровую карту. Без растровых карт псевдослияний, напротив, пришлось бы повторять распаковку и шаг OR для потенциально большого числа отдельных растровых карт, что могло бы занять пропорционально больше времени.

Ещё одно преимущество псевдослияний проявляется при сочетании (а) большого количества ссылок, (б) недостаточного покрытия растровыми картами и (в) глубоких вложенных деревьев, из-за чего обход для заполнения обходится относительно дорого. Например, предположим, что имеется столько тегов, что создавать растровую карту для каждого из них по отдельности нецелесообразно. Без растровых карт псевдослияний вычисление результата, например, для git rev-list --use-bitmap-index --count --objects --tags, вероятно, потребовало бы большого объёма обхода для заполнения. Однако если множество таких тегов хранится вместе в растровой карте псевдослияния, механизм растровых карт может воспользоваться тем, что нас интересует только объединение объектов, достижимых из всех этих тегов, и ответить на запрос намного быстрее.

Конфигурация

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

Внутри группы коммиты могут считаться «стабильными» или «нестабильными» в зависимости от их возраста. Эти параметры задаются соответственно значениями конфигурации bitmapPseudoMerge.<name>.stableThreshold и bitmapPseudoMerge.<name>.threshold.

Все стабильные коммиты объединяются в псевдослияния одинакового размера (bitmapPseudoMerge.<name>.stableSize). Если параметр конфигурации stableSize равен, например, 100, то первые 100 коммитов (в порядке даты коммиттера), которые старше значения stableThreshold, образуют одну группу, следующие 100 коммитов — другую и так далее.

Для нестабильных коммитов механизм псевдослияний попытается объединить старые коммиты в большие группы, тогда как более новые коммиты будут входить в небольшие группы. Это основано на эвристике: ссылка с более старым коммитом на вершине с меньшей вероятностью будет изменена так, чтобы указывать на другой коммит, чем ссылка с более новым коммитом на вершине.

Размер групп определяется функцией степенного убывания, а параметр убывания приблизительно соответствует «k» в f(n) = C*n^(-k/100), где f(n) обозначает размер n-й группы псевдослияния. Частота выборки определяет, какой процент подходящих коммитов рассматривается в качестве кандидатов. Пороговый параметр указывает минимальный возраст (чтобы не включать в группу псевдослияния слишком новые коммиты и тем самым снизить вероятность её неактуальности). Параметр «maxMerges» задаёт верхнюю границу количества коммитов псевдослияния в одной группе.

Параметры, относящиеся к стабильности, управляют стабильными группами псевдослияний, состоящими из фиксированного числа коммитов, которые старше настроенного значения «стабильного порога» и могут объединяться в блоки размером «stableSize» в порядке возраста.

Полная конфигурация псевдослияний выглядит следующим образом:

Примеры

Предположим, у вас есть репозиторий с большим количеством ссылок и вам нужна минимальная конфигурация растровых карт псевдослияний, которая улучшит покрытие растровыми картами пространства имён refs/. Для начала можно использовать такую конфигурацию:

[bitmapPseudoMerge "all"]
        pattern = "refs/"
        threshold = now
        stableThreshold = never
        sampleRate = 1
        maxMerges = 64

В результате будут созданы растровые карты псевдослияний для всех ссылок независимо от их возраста, а коммиты будут объединены в 64 коммита псевдослияния.

Если при создании коммитов псевдослияния нужно разделить теги и ветки, следует задать шаблон с группой захвата, например так:

[bitmapPseudoMerge "all"]
        pattern = "refs/(heads/tags)/"

Предположим, вместо этого вы работаете в репозитории сети форков, где каждому форку соответствует числовой идентификатор, а его ссылки находятся в refs/virtual/NNN/ (где NNN — числовой идентификатор соответствующего форка) в сети. В этом случае можно задать, например, следующее:

[bitmapPseudoMerge "all"]
        pattern = "refs/virtual/([0-9]+)/(heads|tags)/"
        threshold = now
        stableThreshold = never
        sampleRate = 1
        maxMerges = 64

В результате будут созданы идентификаторы групп псевдослияний, такие как «1234-heads» и «5678-tags» (соответственно для веток форка «1234» и тегов удалённого репозитория «5678»).