Hi,
I have recently learned that ref format migrations can take a
significant amount of time in the order of minutes when migrating
millions of refs. This is probably not entirely surprising: the initial
focus for the logic to migrate ref backends was mostly focussed on
getting the basic feature working, and I didn't yet invest any time into
optimizing the code path at all. But I was still mildly surprised that
the migration of a couple million refs was taking minutes to finish.
This patch series thus optimizes how we migrate ref formats. This is
mostly done by expanding upon the "initial transaction" semantics that
we already use for git-clone(1). These semantics allow us to assume that
the ref backend is completely empty and that there are no concurrent
writers, and thus we are free to perform certain optimizations that
wouldn't have otherwise been possible. On the one hand this allows us to
drop needless collision checks. On the other hand, it also allows us to
write regular refs directly into the "packed-refs" file when migrating
from the "reftable" backend to the "files" backend.
This leads to some significant speedups. Migrating 1 million refs from
"files" to "reftable":
Benchmark 1: migrate files:reftable (refcount = 1000000, revision = origin/master)
Time (mean ± σ): 4.580 s ± 0.062 s [User: 1.818 s, System: 2.746 s]
Range (min … max): 4.534 s … 4.743 s 10 runs
Benchmark 2: migrate files:reftable (refcount = 1000000, revision = pks-refs-optimize-migrations)
Time (mean ± σ): 767.7 ms ± 9.5 ms [User: 629.2 ms, System: 126.1 ms]
Range (min … max): 755.8 ms … 786.9 ms 10 runs
Summary
migrate files:reftable (refcount = 1000000, revision = pks-refs-optimize-migrations) ran
5.97 ± 0.11 times faster than migrate files:reftable (refcount = 1000000, revision = origin/master)
And migrating from "reftable" to "files:
Benchmark 1: migrate reftable:files (refcount = 1000000, revision = origin/master)
Time (mean ± σ): 35.409 s ± 0.302 s [User: 5.061 s, System: 29.244 s]
Range (min … max): 35.055 s … 35.898 s 10 runs
Benchmark 2: migrate reftable:files (refcount = 1000000, revision = pks-refs-optimize-migrations)
Time (mean ± σ): 855.9 ms ± 61.5 ms [User: 646.7 ms, System: 187.1 ms]
Range (min … max): 830.0 ms … 1030.3 ms 10 runs
Summary
migrate reftable:files (refcount = 1000000, revision = pks-refs-optimize-migrations) ran
41.37 ± 2.99 times faster than migrate reftable:files (refcount = 1000000, revision = origin/master)
Changes in v2:
- Mention in the first commit message that the introduced flag will be
used in a subsequent patch.
- Link to v1: https://lore.kernel.org/r/20241108-pks-refs-optimize-migrations-v1-0-7fd37fa80e35@xxxxxx
Thanks!
Patrick
---
Patrick Steinhardt (10):
refs: allow passing flags when setting up a transaction
refs/files: move logic to commit initial transaction
refs: introduce "initial" transaction flag
refs/files: support symbolic and root refs in initial transaction
refs: use "initial" transaction semantics to migrate refs
refs: skip collision checks in initial transactions
refs: don't normalize log messages with `REF_SKIP_CREATE_REFLOG`
reftable/writer: optimize allocations by using a scratch buffer
reftable/block: rename `block_writer::buf` variable
reftable/block: optimize allocations by using scratch buffer
branch.c | 2 +-
builtin/clone.c | 4 +-
builtin/fast-import.c | 4 +-
builtin/fetch.c | 4 +-
builtin/receive-pack.c | 4 +-
builtin/replace.c | 2 +-
builtin/tag.c | 2 +-
builtin/update-ref.c | 4 +-
refs.c | 70 ++++++-------
refs.h | 45 +++++----
refs/debug.c | 13 ---
refs/files-backend.c | 244 +++++++++++++++++++++++++---------------------
refs/packed-backend.c | 8 --
refs/refs-internal.h | 2 +-
refs/reftable-backend.c | 14 +--
reftable/block.c | 33 +++----
reftable/block.h | 9 +-
reftable/writer.c | 23 +++--
reftable/writer.h | 1 +
sequencer.c | 6 +-
t/helper/test-ref-store.c | 2 +-
t/t1460-refs-migrate.sh | 2 +-
walker.c | 2 +-
23 files changed, 247 insertions(+), 253 deletions(-)
Range-diff versus v1:
1: 059a17163a ! 1: 167a262a0c refs: allow passing flags when setting up a transaction
@@ Commit message
refs: allow passing flags when setting up a transaction
Allow passing flags when setting up a transaction such that the
- behaviour of the transaction itself can be altered. Adapt callers
- accordingly.
+ behaviour of the transaction itself can be altered. This functionality
+ will be used in a subsequent patch.
+
+ Adapt callers accordingly.
Signed-off-by: Patrick Steinhardt <ps@xxxxxx>
2: 2acf64db6b = 2: 39255cdeff refs/files: move logic to commit initial transaction
3: bac7ca1d80 = 3: 061950cf39 refs: introduce "initial" transaction flag
4: 1101c9da75 = 4: a559563c57 refs/files: support symbolic and root refs in initial transaction
5: 75e769ec3e = 5: 8605fb50bc refs: use "initial" transaction semantics to migrate refs
6: a91fe4e2d5 = 6: eb9cacdaa6 refs: skip collision checks in initial transactions
7: 55901bd45f = 7: 6ac43c46b7 refs: don't normalize log messages with `REF_SKIP_CREATE_REFLOG`
8: d15006b445 = 8: 3b192c1e02 reftable/writer: optimize allocations by using a scratch buffer
9: 4b5603743f = 9: 96cd8b8287 reftable/block: rename `block_writer::buf` variable
10: 4dd22bdbef = 10: a36318ece6 reftable/block: optimize allocations by using scratch buffer
---
base-commit: facbe4f633e4ad31e641f64617bc88074c659959
change-id: 20241108-pks-refs-optimize-migrations-6d0ceee4abb7
