У меня *много* исходных файлов для добавления в репозиторий git, как сделать это быстро

Существует несколько жестких ограничений на количество файлов (технически блоб-объекты), которые может хранить база данных Git. Однако есть множество более мягких ограничений.

У меня есть два довольно больших репозитория — FreeBSD и Linux — которые весят 5,7 и 6,7 миллионов объектов. Это гораздо меньше, чем 100 миллионов файлов: репозиторий Linux составляет примерно 1/15 от этого размера, и даже в этом случае не так много файлы, так как многие объекты представляют собой коммиты и деревья.

Обратите внимание, что есть разница между помещением 100 миллионов файлов в один коммит и помещением 100 миллионов файлов в 100 миллионов коммитов, каждый из которых хранит один файл. Первый потребует создания индекса, в котором перечислены 100 миллионов файлов, что составляет несколько гигабайт индексного файла и, вероятно, будет медленным, но при этом будет храниться 100 миллионов больших двоичных объектов, плюс один объект дерева на каталог, а также одна фиксация. Последний будет строить небольшой индекс (из 1 файла), делать одну фиксацию, используя одно дерево, содержащее один блоб, затем повторять 100 миллионов раз: индекс никогда не будет большим, но репозиторий будет хранить 300 миллионов объектов: 100 миллионов фиксаций, каждая с 1 дерево и 1 капля.

Не сразу становится очевидным, куда уходит все время. git add <path> требуется:

• сжатие содержимого файла и создание нового объекта большого двоичного объекта или повторное использование существующего объекта большого двоичного объекта, если сжатый хэш-идентификатор является идентификатором существующего объекта; тогда
• обновление индекса таким образом, чтобы нулевой промежуточный слот соответствующего имени файла отображался в правильной позиции.

Индекс отсортирован, так что это обновление, вероятно, может быть очень быстрым — если новый файл идет в конец индекса, будет достаточно одного добавления любого байта — или невероятно медленным: вставка в начало будет O(n ¹) на количество записей, уже находящихся в индексе, так как все они должны быть перемещены вниз. На практике Git считывает индекс в память, выполняет там операцию и записывает индекс обратно, поэтому, вероятно, он будет очень медленным, как только индекс преодолеет некоторый порог размера (который будет варьироваться в зависимости от ОС и типа/скорости базового носителя данных). ).

Вам также может понадобиться много места на диске между объектами упаковки. Современный Git будет запускаться git gc --auto после каждой фиксации, но между ранним Git и 2.17.0 (когда он был исправлен) git commit случайно не запустился. Учитывая вашу ситуацию, вы, вероятно, все равно захотите отключить автоматический git gc и запускать его с контролируемыми интервалами — или, как в документации, на которую вы ссылаетесь, использовать git fast-import для создания файла пакета без использования обычных каналов Git. Это позволит полностью избежать необходимости в индексе (пока вы не запустите git checkout для извлекать одного из этих коммитов).

²Единственным реальным жестким ограничением является то, что существует только 2¹ возможных хэш-идентификатора. Тем не менее, вы сталкиваетесь с заметно высокой вероятностью хэш-коллизии, порядка 1 из 10¹⁶⁰ — это также указанная многими производителями дисков частота неисправленных битовых ошибок — к тому времени, когда вы достигаете примерно 1,7 квадриллиона объектов.

git fast-import (используемый такими инструментами, как git filter-repo, действительно хороший вариант, а с Git 2.27 (второй квартал 2020 г.) он работает еще быстрее.

Пользовательская хэш-функция, используемая «git fast-import», была заменена функцией из hashmap.c, что дало хороший прирост производительности.

См. зафиксировать d8410a8 (6 апреля 2020 г.) от Джефф Кинг (peff).
^{(Merged by Junio C Hamano -- gitster -- in commit 6ae3c79, 28 Apr 2020)}

fast-import: replace custom hash with hashmap.c

^{Signed-off-by: Jeff King}

We use a custom hash in fast-import to store the set of objects we've imported so far. It has a fixed set of 2^16 buckets and chains any collisions with a linked list.
As the number of objects grows larger than that, the load factor increases and we degrade to O(n) lookups and O(n^2) insertions.

We can scale better by using our hashmap.c implementation, which will resize the bucket count as we grow.
This does incur an extra memory cost of 8 bytes per object, as hashmap stores the integer hash value for each entry in its hashmap_entry struct (which we really don't care about here, because we're just reusing the embedded object hash).
But I think the numbers below justify this (and our per-object memory cost is already much higher).

I also looked at using khash (here, see article), but it seemed to perform slightly worse than hashmap at all sizes, and worse even than the existing code for small sizes.
It's also awkward to use here, because we want to look up a "struct object_entry" from a "struct object_id", and it doesn't handle mismatched keys as well.
Making a mapping of object_id to object_entry would be more natural, but that would require pulling the embedded oid out of the object_entry or incurring an extra 32 bytes per object.

In a synthetic test creating as many cheap, tiny objects as possible

perl -e '
    my $bits = shift;
    my $nr = 2**$bits;

for (my $i = 0; $i < $nr; $i++) {
        print "blob\n";
        print "data 4\n";
        print pack("N", $i);
}
its | git fast-import

I got these results:

nr_objects   master       khash      hashmap
2^20         0m4.317s     0m5.109s   0m3.890s
2^21         0m10.204s    0m9.702s   0m7.933s
2^22         0m27.159s    0m17.911s  0m16.751s
2^23         1m19.038s    0m35.080s  0m31.963s
2^24         4m18.766s    1m10.233s  1m6.793s

which points to hashmap as the winner.

We didn't have any perf tests for fast-export or fast-import, so I added one as a more real-world case.
It uses an export without blobs since that's significantly cheaper than a full one, but still is an interesting case people might use (e.g., for rewriting history).
It will emphasize this change in some ways (as a percentage we spend more time making objects and less shuffling blob bytes around) and less in others (the total object count is lower).

Here are the results for linux.git:

Test                        HEAD^                 HEAD
----------------------------------------------------------------------------
9300.1: export (no-blobs)   67.64(66.96+0.67)     67.81(67.06+0.75) +0.3%
9300.2: import (no-blobs)   284.04(283.34+0.69)   198.09(196.01+0.92) -30.3%

It only has ~5.2M commits and trees, so this is a larger effect than I expected (the 2^23 case above only improved by 50s or so, but here we gained almost 90s).
This is probably due to actually performing more object lookups in a real import with trees and commits, as opposed to just dumping a bunch of blobs into a pack.