Git designed for AI agents.
Land batching
Status: implemented in phase 3 (standalone mode only), extended in phase 4a
(batch latency: a streaming rebase engine, early completion, adaptive batch
sizes and a batch of one as an ordinary land) and in phase 4b (one range query
per request and the objects of a batch made durable once, as one pack; see
PLAN8.md). This page describes the code in
internal/gitaly/service/operations/land_batch*.go, internal/graft/landlane,
internal/graft/rebase and internal/graft/ancestry. The designs are in
PLAN3.md, section A, and PLAN4.md.
Why
A land is a compare-and-swap (CAS) of a branch from its old tip to a new one.
When many agents land on one branch, most CAS attempts lose to another writer,
the change is rebased again and the attempt is repeated. In the phase 2
benchmark (20 agents, one branch) a change needed about 10 attempts, p99 latency
was 26 s, and changes failed at max_attempts = 20.
Batching moves the contention from the branch to an in-memory queue in the Gitaly process. Several changes are then published with one reference update.
When a land is batched
A UserLand request lands through its lane only if all of these hold:
[graft] standalone = true. Batching is not used with GitLab.[graft.land.batch] disabledis nottrue.- The request is not on an MVCC snapshot (
repositoryreference backend). - The request has no own git object directory and no alternate object directories. Such a request lands alone, because the batch quarantine cannot see the objects that only its directories hold.
- The branch exists. A request that creates a branch lands alone.
Any other request runs the unbatched loop, which retries the CAS up to its own
max_attempts. Unbatched responses report batch_size = 1 and
batch_position = 1.
Lanes
A lane is one (storage, relative path, branch) in one Gitaly process, held by
landlane.Registry:
- Requests enter the lane in FIFO order.
- A lane runs one batch at a time. Lanes of different branches run in parallel.
- A batch is formed when
windowhas passed since the first queued request, or as soon asmax_sizerequests are queued, whichever comes first. A batch that waited already starts at once, so withwindow = "0s"a batch is whatever queued while the previous batch ran. - A request whose context is done before its batch starts is removed from the
queue, and its caller gets
Canceled. - A request cancelled while its batch runs still lands. Its caller gets
Canceledat once, and the outcome is discarded. The lane context carries the values of the first request of the batch, never its cancellation, and per request identity is read from each request's own context.
What a batch does
One batch attempt:
- Opens one quarantine on the repository and reads the branch tip.
- Lands each request in order onto the running tip. For each request:
- The commit ID is resolved. An invalid ID fails that request with
InvalidArgument. - The standalone access policy is evaluated for the request's actor on the
update the request would make (see Policy below). A denied request fails
alone with
PermissionDeniedand an access-check error. - If the commit is already reachable from the running tip, the request
reports
already_landedand changes nothing. - If the running tip is an ancestor of the commit, the commit becomes the new running tip (fast-forward).
- If an earlier land of the commit on the branch put a commit on it that is
still reachable from the running tip, the request reports
already_landedwith that commit and changes nothing (the land identity of PLAN11). - Otherwise the commit is rebased onto the running tip, or merged for
STRATEGY_MERGE.STRATEGY_FF_ONLYfails that request with anot_ancestorerror. - A merge conflict fails only that request with
merge_conflict. When the request setsresolve_conflictsand the resolver is enabled, the conflict is resolved first: by the lane itself for what the rules resolve withininline_timeout(default1s), and otherwise out of the lane, before the request enters it again (see RESOLVE.md, "Out of the lane"). - A request whose outcome is final before the CAS (see Early completion) is answered at once.
- The commit ID is resolved. An invalid ID fails that request with
- Publishes the final running tip with one CAS from the original tip. The
changelog entry of that update has operation
land_batchand one member per landed request (see Changeset log). A batch with exactly one landed member is published as a plainlandinstead (see A batch of one).
A batch that changes nothing publishes nothing. Its requests report their own outcomes.
How a request is decided and rebased
Since phase 4b (PLAN8.md), each request of an attempt costs one short git process, one more when it diverges from the tip, and at most four in all when committer dates are skewed:
- The commit ID is peeled to a commit by an object info process of the
attempt's quarantine (
git cat-file --batch-check), taken from the catfile cache for each peel, so a process that dies fails the request that met it and at most the next one. - One listing of the commits that the change adds to the running tip
(
ancestry.Checker.List,git rev-list --parents commit ^tip) decides the landing (rebase.Plan): an empty list means the change is already landed; the tip being a parent of a listed commit means a fast-forward; both facts hold even when committer dates are skewed. Otherwise the change diverges, or, under skew, may still turn out to be already landed (see below). A skewed history can makegit rev-listlist commits that the tip already has (its walk stops early when the commits it still has to visit are older than those it listed), never fewer. So for a diverging change onegit merge-base --independent tip <bottoms>tells whether the listing is exact: it drops exactly the bottoms of the listing (listed commits none of whose parents is listed) that the tip reaches, and the listing has extra commits exactly when one of them is dropped. Without skew that is the only extra process. With skew (counted bygraft_revrange_skewed_listings_total; the commits removed from listings of the repository rebase todo are counted bygraft_revrange_skew_extra_commits_total)git merge-base --alldecides: the change is already landed when its only merge base is the commit itself; otherwise one listing below the merge bases either is a chain of commits with one parent each down to the only merge base, which is then the exact range, or the range has a merge commit. A land therefore costs at most four git processes, whatever the size of the history. For the rebase strategy, a merge commit in the range refuses the change (InvalidArgument, useSTRATEGY_MERGE), a range that ends at a root commit means unrelated history (InvalidArgument), and otherwise its commits, oldest first, are the commits to replay. - The commits are replayed by the
rebase.Engineof the attempt, which keeps onegit merge-tree --stdinprocess and onegit hash-object --stdin-pathsprocess running for the whole attempt. The replay has the rules, errors and conflict contents of the repository'sRebasewith reapplied cherry-picks. If the commit writer cannot write a commit (ErrCommitWriterUnsupported, for example when signing is configured), that commit is written with the ordinary commit writer of the repository.
With [graft.land] graph_ancestry = true the listing walks the stored graph
index in process instead of running git rev-list; both return the same
commits. The graph checker refuses repositories with shallow commits, grafts or
replace refs, because git walks their history differently; for those it logs a
warning and uses git. A land that is not batched is decided, rebased and
published the same way, by the same code (landingAttempt): it only differs in
its update, which runs with the request's own identity and hooks.
Durability of the objects of a batch
The merge-tree and hash-object processes of an attempt write their objects into
the quarantine of the attempt without fsync. Before the compare-and-swap, the
attempt packs every loose object of its quarantine into one pack with
git pack-objects, which writes and fsyncs the pack and its index, and removes
the loose files and their fan-out directories. The quarantine migration of the
update then moves the pack files into the repository, fsyncing them again,
before the reference changes. So every object that the new tip reaches is on
disk before the branch points to it, with a fixed number of fsyncs per batch
instead of about three per object. A batch that only fast-forwards writes no
object and packs nothing.
If packing fails, the update of the attempt fails: the requests that changed the running tip fail with the error, as for any failed update (see Outcomes of the CAS), and the branch does not move. Each published batch adds one pack to the repository, like a push; housekeeping repacks them as it repacks the packs of pushes.
A land that is not batched writes the few objects of its change with the server's fsync configuration and publishes them as loose objects, without a pack: a pack would cost a process and as many fsyncs for so few objects, and under contention every attempt that loses the compare-and-swap would leave a pack in the repository. In both cases every object file of the quarantine is durable before the quarantine migration moves it.
Hooks and identity of the combined update
The combined update is made as the synthetic user graft-batch (name Graft,
email graft@localhost), with a context that carries no request identity. The
hooks judge the update as that user, and the changeset records the update with
the actor graft-batch. The members carry the real actors.
Policy is therefore checked per request, in process, before the request joins
the running tip. For a combined update that carries members, both the access
check of the pre-receive hook (in standalone mode, the policy) and the policy
check of the reference-transaction hook are skipped, because the members were
checked already. Only an update with operation = land_batch and members is
skipped. Any other update is still checked, and custom server hooks still run
for the combined update.
A [[graft.policy]] rule whose actor matches graft-batch therefore has no
effect on batches with two or more members (a batch of one is judged as its
requester's land): it neither rejects a batch nor makes its requests land
alone. Restrict who may land on a branch with rules for the agents themselves,
which apply to every request of a batch. To keep a branch out of batching
altogether, the only switch is [graft.land.batch] disabled, which applies to
the whole server.
Outcomes of the CAS
When the combined update is not published, the requests that changed the running tip (the members) did not reach the branch. A request after the first member was landed onto a tip that holds members, so its outcome does not hold for the branch either: it may be "already landed" or "unchanged" only because of a member's commits, or it may have conflicted with a member only. Such a request never reports the outcome of that attempt. The requests before the first member landed onto the real tip and keep their outcomes.
- Success. Every request of the batch gets its response.
- Lost to an external writer. The branch moved during the attempt. The batch
is rebuilt on the new tip: every request is landed again, and the attempt is
counted. A batch is rebuilt at most 10 times (11 attempts). The batch
does not use the request's
max_attempts. After the last rebuild, every request from the first member on fails with the samereference_updateerror as an unbatched land that runs out of attempts. The requests before the first member still succeed (already landed or unchanged), with their batch fields set. Rebuilds wait with the backoff of unbatched lands. - Rejected by a hook. A custom server hook, for example a custom pre-receive
hook, rejected the combined update. The policy does not reject it: its access
checks are skipped for the combined update (see above), so a policy rule for
graft-batchcannot cause this outcome. The rejection cannot be attributed to one request from the combined update, so every request is landed alone through the unbatched loop, with its own identity and its ownmax_attempts. Each response then reportsbatch_size = 1. - Other failures. The members fail with the error of the update, which a rebuild does not fix. The requests before the first member keep their outcomes, and their batch fields still describe the batch as submitted (see Responses). The other requests after the first member are landed again in a new attempt on the real tip, without the failed members, and report the outcome of that attempt (its attempt number included). Every such attempt drops at least one member, so this ends.
- Shutdown. A running batch is cancelled when the graceful shutdown period of the server has elapsed, and its requests fail.
Early completion
A request whose outcome is final before the CAS is answered as soon as it is decided, not when the batch is published. An outcome may be answered early only if no other request of the batch can change it. There are two kinds:
Member-independent outcomes, final wherever the request is in the batch:
- a policy denial. It depends only on the actor and the reference;
- an invalid commit ID. It does not depend on the tip.
Tip-dependent outcomes, final only while no earlier request of the batch has changed the running tip, that is, while the running tip is still the tip the batch started from:
- an already landed answer, when the commit is reachable from the starting tip;
- an unresolved merge conflict;
- an
InvalidArgumentthat depends on the tip, for example a range with merge commits or unrelated history.
Once an earlier request has changed the running tip, these requests are not answered early. They stay in the batch and are decided again by the later attempts, rebuilds and the fallback, exactly as before early completion existed.
The stepper hands the result to the lane (landlane.CompleteEarly). The caller
returns with its response, with the batch fields as for every other request of
the batch, while the batch is still running. The executor's later result
for that request is ignored. A request that is completed early is not a member
of the update, and it does not wait for a slow CAS or for hooks.
Requests that land on the running tip still wait for the CAS. If the batch is rebuilt or fails, those requests keep the outcome rules of Outcomes of the CAS; early answers are not revised.
A batch of one
When exactly one request changes the branch in a batch, the update is not a
land_batch. It is made as an ordinary land with the real identity of that
request, so the policy and the pre-receive access check apply to it as they do
for a land that is not batched. The changelog entry has operation land and
carries that single member (original_commit → commit), so the mapping from
the requested commit to the landed commit is kept. The reference-transaction
policy skip applies only to land_batch updates with members, so this land is
policy-checked like any unbatched land. Responses still report the batch fields,
as for every batch: batch_size is the number of requests of the batch, and
batch_position the position of the request in it. Failed and early-answered
requests are counted too, so a batch of one that shares its batch with
conflicting requests reports a batch_size greater than 1, although only one
request landed.
Adaptive sizing
Each lane has an effective maximum batch size, which starts at max_size. After
each batch the lane compares the batch duration with target_latency:
- A batch slower than
target_latencyhalves the effective maximum (never below 1). - A batch faster than half of
target_latencyraises it by a quarter of its value (at least 1), never abovemax_size.
A slow publish (for example a slow hook or a large repository) therefore gets
smaller batches, and a fast lane grows back to max_size. target_latency = "0s" turns the adaptation off, and the lane always uses max_size. The default
target is 500 ms.
A lane is retired as soon as its queue is empty, but its key (storage,
repository and branch) keeps the effective maximum for 5 minutes
(landlane.KeyStateTTL) after that, so the next lane of the key starts from
it. A key without a lane for 5 minutes is forgotten: its next lane starts at
max_size again, and the memory it used is released. The sum of the effective
maxima of the keys that have a lane or were used in the last 5 minutes is
exported as graft_land_lane_effective_max_size. A key that grows back to
max_size keeps counting with max_size until it is forgotten, and the gauge
falls to 0 once no key has been used for 5 minutes.
Responses
Every request gets its own response. Batch fields:
| Field | Meaning |
|---|---|
batch_size |
Number of requests of the batch as submitted. Requests that landed, were already landed, failed or were answered early are all counted. Field 9 of UserLandResponse. |
batch_position |
1-based position of the request in the batch, in submission order, counting every request of the batch (failed ones included). Field 10. |
attempts |
Batch attempts used, the first one included: 1 plus the rebuilds. |
Also set on batched responses: landed_commit_id, old_tip, rewritten,
already_landed, resolved_paths and resolver, as for an unbatched land.
A change that landed alone reports batch_size = 1 and batch_position = 1.
The client libraries expose the batch:
- The SDK sets
LandResult.Batchtosdk.BatchInfo{Size, Position}.BatchInfo.Batched()reportsSize > 1. A server without the batch fields yields the zero value. graft landprintslanded at <commit> (batch 3/17, 1 attempt)when the change shared its batch: the position of the change in the batch, the batch size, and the attempts the land used (2 attemptsafter a rebuild). When the server reports no attempts the note is(batch 3/17). A change that landed alone prints no batch note.LandResultininternal/graft/workspacecarries the same fields asBatchSize,BatchPositionandAttempts.
Changeset log
A combined update writes one changeset with operation land_batch and the
actor graft-batch. A batch of one is an operation land with its real actor
and one member (see A batch of one). Its members list has one entry per
landed request, with the keys of changelog.Member:
| Key | Meaning |
|---|---|
original_commit |
The commit the request asked to land. |
commit |
The commit it landed as inside the batch. Equal to original_commit when it was not rewritten. |
actor |
The agent name of the request, or else its GitLab user ID. |
rewritten |
True if the change was rebased or merged. |
resolved_paths |
Files the resolver resolved for this change. |
The encoded members are limited to 32 KiB, because they travel in the
environment of the git processes of the update. Beyond that the resolved paths
are dropped first. If the list is still too long it is cut to the longest prefix
that fits. The changeset then has members_truncated: true. Changesets of
unbatched lands have no members and operation land. A batch of one has
operation land and its single member.
graft log prints batch of N, then one actor original→landed line per
member. graft log --json writes the members in the same form as the log.
Control characters in member actors and resolved paths are escaped in the text
output (for example \x1b), because they come from clients and from file
names; --json writes them as JSON escapes.
graft-superfan judges every member of a land_batch changeset as a land of
its own: it checks each member's actor against expected_actors, counts each
member toward the burst rule, and fetches the details of each member's
commit for the file rules. graft-batch is not judged as an actor. A batch
whose member list was cut gets a batch-incomplete finding. See
SUPERFAN.md.
Configuration
[graft.land.batch]
disabled = false # true: every request lands alone, as in phase 2
window = "10ms" # collect time after the first queued request; "0s" = no wait
max_size = 50 # largest number of requests in one batch
target_latency = "500ms" # batch duration the lane aims for; "0s" = no adaptation
[graft.land]
graph_ancestry = false # true: ancestry from the stored graph index
The keys are documented in CONFIGURATION.md
and CONFIGURATION.md. window and
target_latency must be non-negative Go durations. max_size must be between
0 and 100; zero means the default. The update of a batch carries the identity
of every member in the environment of its git processes, which bounds it.
Metrics
internal/graft/landlane defines these metrics, the names of which are fixed:
graft_land_lane_queue_depth(gauge): queued requests, summed over lanes.graft_land_batch_size(histogram): requests per executed batch.graft_land_lane_wait_seconds(histogram): time from submission to the start of the execution, per request.graft_land_lane_effective_max_size(gauge): effective maximum batch size, summed over the keys that have a lane or were used in the last 5 minutes (see Adaptive sizing).
The batch executor (internal/gitaly/service/operations) defines:
graft_land_batch_phase_seconds{phase}(histogram): time per phase of a batch attempt. The phases arequarantine(opening the quarantine and the processes of the attempt),tip(reading the branch tip),land_member(one observation per request the stepper lands, in every attempt, denied, conflicting and already-landed requests included),plan,identityandreplay(parts ofland_member: the range listing and decision of a request, the lookup of the earlier land of a diverged request (PLAN11), and the replay of a rebased request),pack(packing the objects of an attempt before its update),update(the CAS and its hooks) andtotal(one observation per execution of the batch, which covers all of its attempts, rebuilds and fallbacks).graft_land_batch_packed_objects_total(counter): objects that attempts packed before their update.graft_land_batch_members_total{outcome}(counter): requests by outcome, with the outcomeslanded,already_landed,conflict,denied,errorandneeds_resolution(the lane handed the request back to be resolved out of the lane, or to wait for its turn on its files; not a failure: a land that loses k rounds counts k of these).graft_land_ticket_wait_seconds(histogram): time a land that lost a round of its conflict resolution waited for its turn on its files (RESOLVE.md, "Out of the lane").graft_land_resolution_rounds(histogram): rounds (resolve, then the lane) a land with conflicts needed.
The hooks (internal/gitaly/hook) define graft_land_intents_seconds
(histogram): the land intents of one prepared reference transaction in the file
changelog, the wait for their lock file, one write and one fsync, under the
references' locks (PLAN11, 4.2), and
graft_land_intents_compaction_failures_total (counter): compactions of the
land intents that failed, which leave the intents as they were.
The server registers the lanes of the process (landlane.Shared) and these
metrics with the Prometheus registry, so they are exported on /metrics. The
phase breakdown of a benchmark run is in BENCH.md.
Policy
The standalone policy (CONFIGURATION.md) decides each request on the update that request would make, with the same actor the pre-receive hook would use for that request alone. A denied request never enters the running tip, so it cannot delay or block the other requests of its batch.
Measured results
Phase 4b
The runs of examples/graft/demo/acceptance-phase4.sh on the phase 4b trees
(three benchmark windows; full tables, phases and the machine in
BENCH.md) meet the phase 4a acceptance,
the stretch goal included: one attempt per landed change, only planned conflicts
fail, and p99 with batching on is below off at every size. The final tree
(9bf4742, window 3):
| p99 landed (ms), run 1 / run 2 | 20 agents | 50 agents | 100 agents |
|---|---|---|---|
| batching on | 819 / 748 | 1880 / 9171 | 4640 / 5390 |
| batching off | 4707 / 4813 | 8267 / 17868 | 14641 / 26692 |
| lands/min, batching on | 1366 / 1476 | 1690 / 620 | 1459 / 1678 |
The stretch goal (p99 on at 100 agents at most half of off) passed by 37% and 60% (in window 1 by 3.7% and 51%). The runs vary a lot, and the benchmark saturates the machine; the 50 agents of window 3, run 2, are an outlier on both sides. A batched request now costs about 8 ms (one range listing and a replay without fsync per object, see How a request is decided and rebased), and most of a batch is its publish: the pack of its objects and the update.
Phase 4a
The phase 4a acceptance run of record (examples/graft/demo/acceptance-phase4.sh,
20, 50 and 100 agents of 5 changes, conflict rate 0.2, seed 1; full tables, the
other runs and the machine in BENCH.md)
does not meet the phase 4a acceptance: attempts and failures pass at every
size, but p99 with batching on is above off at 50 and 100 agents. An earlier run,
before the final fixes, passed narrowly (by 76 ms at 50 agents); two runs of the
final tree failed at 50 and 100 agents.
| metric | off-20 | on-20 | off-50 | on-50 | off-100 | on-100 |
|---|---|---|---|---|---|---|
| attempts/landed | 11.39 | 1.00 | 27.94 | 1.00 | 56.94 | 1.00 |
| landed / failed | 62 / 38 | 78 / 22 | 99 / 151 | 200 / 50 | 115 / 385 | 392 / 108 |
| p50 landed (ms) | 1518 | 1989 | 2097 | 8959 | 4073 | 17292 |
| p99 landed (ms) | 10023 | 2789 | 9939 | 12658 | 13368 | 23253 |
With batching on, every failure is a planned conflict; with batching off, most failures are lands that gave up after 20 attempts, and they are not in the off latencies. In phase 3 the p99 values with batching on were 9868, 15317 and 21808 ms.
The phase breakdown shows where a batch spends its time: landing the members
(land_member, about 80 to 115 ms per member with the rebase engine, one after
another) takes 56 to 72% of it, and the reference update with its hooks
(update) 27 to 42%. The lane is busy for almost the whole run, so with many
agents most of the latency is time spent queued behind earlier batches. Turning
adaptive sizing off does not change that. The profile of phase 4b found where the
per-member time went (fsyncs of loose objects and nine short git processes per
member) and removed it; see PLAN8.md.
Limits
- Batching is per Gitaly process. Two nodes that accept lands for the same branch still race on the reference, as before.
- The lane lives in memory. Requests queued when a Gitaly process stops are not
landed. When the lane registry is closed, queued requests fail with
Unavailable, and callers retry. The SDK does this forLandwithLandOptions.RetryUnavailable: up to 5 retries ofUnavailableonly, with an exponential backoff from 100 ms to 2 s with full jitter, stopped by the context, reported inLandResult.UnavailableRetries. A client that does not use the SDK must do the same: retryUnavailable, and onlyUnavailable, with a bounded backoff. Every strategy is retried by default (UnavailableRetry.SkipRebaseLandsturns it off for rebase lands). The response of a call can be lost after the change landed, and the retry then lands nothing and reportsalready_landed: with a merge or a fast-forward, the change itself is on the branch; with a rebase, with or without conflict resolution, the branch holds a rebased copy, and the server answers from its record of the first land (the land identity of PLAN11), withlanded_commit_idthe copy andlanded_sequenceits changelog sequence. This holds also when a later commit reverted the change in between (for example graft-verify reverting the culprit): the change is not landed again, andreverted_by_commit_idnames the revert. A land with aresolution(the re-land of a conflict package) is always a merge of the tip and the change, soSkipRebaseLandsdoes not apply to it: the retry finds the change on the branch and reportsalready_landed. - A land that arrives alone waits up to
windowbefore its batch runs. Setwindow = "0s"to remove the wait, ordisabled = trueto remove batching. - Requests that do not qualify (see When a land is batched) run unbatched and get the contention behaviour of phase 2.