# Merge queue

A runner lands the pulls queued for a branch in batches, each checked
once. Pulls and checks in general are in
[collaboration.md](collaboration.md) and [runner.md](runner.md); commands
and flags are in [../reference/cli.md](../reference/cli.md).

## Why a queue

Merging pulls one at a time has two costs. A pull's checks passed against
the branch as it was when they ran, so once another pull lands, that pass
says nothing about the new branch and the pull must be checked again. And
every merge moves the base of every other open pull, so each is retested
in turn.

The queue stacks the queued pulls onto the branch, checks the result once
at its tip, and lands the whole stack when it passes. Several pulls
landing together cost one run. The batch is what gets checked: a
queued pull's own checks are consulted only for its
[pre-flights](#pre-flights), quick workflows it must pass before it
joins one.

Nothing holds still while a batch is checked. People queue and leave, pull
heads move, and someone may push to the branch. Much of this page is about
how the queue notices each of these.

## The queue is records

knotless keeps a repository as records in its owner's atproto account, on
the owner's PDS (the server that holds an account's records); see
[storage.md](storage.md). Pulls are records in their authors' accounts.
There is no queue object either: only `dev.knotless.queue` records, one per
change, each in the account of whoever wrote it. For a private repository
it goes in the writer's repo inside the repository's space; see
[access.md](access.md).

A record names the repository (`repo`), the pull by its AT-URI
(`subject`), a `state` and `createdAt`. Its key is a TID, a time-ordered
record key, so records sort by when they were written.

| State | Written by | Meaning |
| --- | --- | --- |
| `queued` | the person queueing | put the pull at the back of the queue |
| `left` | the person leaving | take the pull out |
| `ejected` | the landing runner | the runner turned the pull away |

An `ejected` record also carries a `reason`, the `commit` of the head that
was turned away, and, when a batch or a pre-flight failed, the `checks`
that failed, each
with its `workflow`, `status` and the `dev.knotless.check` record holding
its log.

### Who may queue

Anyone can write records into their own account, so readers decide which
count. They honour queue records only from the owner or a collaborator,
the people who may merge, and an `ejected` one from a runner the
repository names too, which may land the queue
([Who lands a queue](#who-lands-a-queue)). A stranger's record counts for
nothing. After a
transfer, the previous owner's records count if they predate the move; see
[identity.md](identity.md).

For each pull, the latest honoured record wins, ordered by record key
across all writers. A branch's queue is every open pull whose latest record
is `queued`, oldest first. A closed or merged pull drops out whatever its
record says. A pull retargeted to another branch moves to that branch's
queue.

Before writing, queueing and leaving check:

- Only the owner and collaborators may queue or leave.
- A repository that names no runners cannot queue, because a runner lands
  the queue. Its pulls are merged by hand.
- The pull, read fresh from its author's account, must be open.
- A pull already queued keeps its place, and nothing is written. Any other
  pull gets a new `queued` record, whose new TID puts it at the back.
- A pull that could only be ejected is not let in. One that does not
  apply on its branch as it is now is refused, naming the files that
  conflict, since no pull ahead of it landing changes that. So is one
  with a check that failed at its head merged with the branch's tip. A
  pull with checks still running, or none yet, is let in. A conflict
  with a pull ahead of it is left to the runner, which finds it before
  checking anything ([Building a batch](#building-a-batch)), since that
  pull may be ejected first.
- Leaving needs the latest state to be `queued`. An ejected pull is
  already out.

Queueing returns at once with the pull's branch and its position there,
counted from 1. Nobody waits for the checks.

## Who lands a queue

A runner lands a repository's queues when it runs with `--queue` and its
own account may push there, as the owner or a collaborator, whether or not
the repository names it. Failing that, the first runner the repository
names lands them, so long as none it names may push: knotless.dev's own
runner lands the queues of every repository that names it and no runner of
its owner's. Naming a runner is what lets pulls be queued and makes
readers show its checks. Any other runner leaves the queues alone.

The owner's runner pushes to the owner's PDS directly. A collaborator's
pushes through the owner's gateway; see [gateway.md](gateway.md). A runner
the repository names that may not push lands through the gateway too: the
one sharing for writing recorded, or else the appview's, as the DID
document at `KNOTLESS_APPVIEW` names it. A runner beside the appview reaches
it at an address of their own, `http://serve:2590` in deploy/, which is no
gateway's DID; the document names its public one. The gateway
writes for the owner only once they have delegated writes to it, and takes
from such a runner a batch of queued pulls and nothing else (see
[gateway.md](gateway.md#runners-landing-a-queue)). Until the owner
delegates, the gateway refuses the landing, and the runner ejects the
batch's pulls rather than check them again, saying `the gateway would not
land its batch`, why, and how to delegate. The pages know sooner: a
server that is that gateway says so in a pull's merge status, and
refuses to queue it from the pages, pointing the owner at their account
settings, where they delegate. Its `merged`, `closed` and
`ejected` records count as the owner's would; nothing else it writes
does.

Like `--pulls`, `--queue` runs code anyone can open a pull with, so it
requires the Docker executor.

## Queue-only branches

A pull's own checks are its pre-flight: they say it builds and passes at
its head merged with the branch, but not what the batch's checks hold it
to on top of the others. A merge past the queue lands what only the
pull's own checks passed. A branch whose rule says `queue` (`knotless
protect <url> <branch> --queue`) takes pulls only through the queue:

- A plain merge (`knotless merge`, MCP `merge`) queues the pull instead
  and says so (`main takes pulls through the merge queue: queued, 1 of
  1`). The owner's `--force` still merges at once.
- `dev.knotless.mergePull`, the pages' merge, refuses it, naming the
  rule, as its answer is a merged commit; `getMergeStatus` says
  `queueOnly`, and the pages show only the queue's button.
- A repository with such a branch and no runners has nothing to land the
  queue, so a merge into it is refused, saying so, until it names one.
- The gateway moves the branch for no collaborator but the runner that
  lands the queue ([Who lands a queue](#who-lands-a-queue)), by push or
  by `createCommit`; see [gateway.md](gateway.md#protected-branches).

What it does not hold: the owner. They write their own records with no
gateway, so a push of their own to their own account moves the branch
whatever the rule says, and `--force` is theirs. A collaborator that is
also the queue's lander passes the gateway as the lander does.

## Building a batch

For each branch it lands, a runner keeps a line of batches in memory. Each
batch in flight knows its base (the branch commit it was built on), its
tip, and its pulls. After a restart the runner rebuilds the queue from
records, and checks it left `queued` or `running` become `error`.

To build a batch, the runner takes up to `--batch` (8 by default) waiting pulls in queue
order, skipping any already in a flight and any whose
[pre-flights](#pre-flights) have not passed. It fetches each pull's head fresh
into its mirror, a local bare copy of the git data. Each pull is merged
onto the commit before it with `git merge-tree --write-tree` and squashed
into a commit of its own, so the branch stays linear, one commit per pull,
whatever its protection rule.

A pull whose head branch is gone is ejected. A pull that does not apply on
what is stacked before it is left out, with the paths it conflicts in, and
the rest of the batch goes on. When the batch is built on the branch
itself, the conflicting pull is ejected at its head, with a reason that
names the files and asks the author to merge or rebase and queue again.
When pulls stacked ahead of it change those files, the reason names
them and their branches instead: merge that branch in, or wait for it
to land and merge the branch.
If every pull is left out, the runner builds from the next ones.

Details:

- A squash commit has the merge's tree and one parent. Its author and
  author date come from the head's last commit; its committer is the
  runner's account (`<did>@knotless.invalid`), at the current time.
- Its message is the pull's title, the body if there is one, and the
  pull's AT-URI, separated by blank lines.

## Pre-flights

A batch that fails costs a halving round for each pull that broke it,
and one that does not even build fails the whole batch. A workflow that
says `queue: first` ([the key](../reference/workflows.md#the-merge-queue))
is a pre-flight: a check, such as fmt and clippy, or the tests, that
each pull must pass on its own before it goes into a batch. Its author
can queue at once, rather than wait for the check and then queue.
knotless's own are `check` and `test`: a pull whose tests fail alone,
the most common way to break a batch, is ejected from its own run, which
the runner host makes anyway, rather than costing a batch's run and a
halving round. A batch still runs them at its tip, for pulls that pass
alone and fail together.

On each pass, before building, the runner reads the workflows at the
branch's tip that run first on a pull into it. For each waiting pull not
in a flight, it resolves the head and reads the pull's checks at that
head from every runner the repository names, and its own, as `knotless
checks --pull` does. For each pre-flight it takes the newest run, but
for another runner's that is only `queued`, which counts as none:

| Newest run at the head | What the runner does |
| --- | --- |
| `success`, on any tip | counts it passed |
| `running`, or its own `queued` | waits |
| `failure` or `error`, on the branch's tip | ejects the pull |
| none, `cancelled`, or failed on another tip | runs it here, and waits |

A run is filed `queued` as soon as its runner takes it up, and may wait
long for a job there: a runner of pulls with two jobs that takes up ten
at once has eight waiting. Were that counted as running, the queue
would wait on that runner while its own sat idle. So it runs the
pre-flight too, and whichever runner starts first runs it: as a run of
a pre-flight gets its job, its runner reads the other runners' checks,
and one already `running` or `success` at the same head and base is
left to run, its own check deleted rather than filed `cancelled`. A
`cancelled` one would be the newest run the queue reads, and have it run
the pre-flight yet again.

A pull whose pre-flights have all passed is ready, and batches are built
from the ready pulls in queue order. One still waiting holds up none
behind it.

A pass on an earlier tip is enough, because the batch checks the pull on
the branch as it is anyway. Requiring the tip would run the pre-flight
again each time the branch moves, the delay a pre-flight exists to cut. A
failure ejects only on the current tip: what failed against an older one
the branch may have fixed since.

A pre-flight may also check less than the batch does, for speed.
knotless's own `test` checks the same: a pull's run tests against the
spaces alpha, and the stock PDS for what only it reaches, and holds the
100% gate, as the batch's does. Testing against the stock PDS first and the alpha only when the
gate fell short was slower: nearly every change that reached a test
binary fell short, and then ran the two one after the other.

An ejected pull never entered a batch. Its reason names the head, the
branch and its tip, and the failed workflows, and `checks` points at
their records. `knotless show` adds the command that reads their logs,
`knotless checks <repo> --pull <uri> --log`.

When nobody has run a pre-flight at the head, the runner runs only those
workflows, on the pull itself, as a pull's run: the head merged with the
branch's tip, without secrets, in the `Other` class. A pull is then never
stuck waiting for a runner that will not run it, such as one that runs
pulls only as their authors push. Its check is the runner's own, keyed
by the pull. Once it has run them at a head on a tip, the runner stops
waiting for them there, even with no check to show: the pull may have
taken the workflow away, and its batch will say what it does. A pull
that conflicts with the branch is not run at all; building the batch
ejects it, naming the files.

A pull's run of a pre-flight carries `queue: first` in its check
record. That is how readers say a queued pull is waiting for one.

## Checking a batch

A batch is checked as a push to its branch that has not happened yet: the
branch, at the stack's tip, with the branch's current generation. The
workflows that run are those at the tip whose `on: pull` trigger takes
pulls into that branch; see
[../reference/workflows.md](../reference/workflows.md).

Batch runs get no secrets, since their code comes from pulls. A batch is
trusted when every pull's author and head repository owner is the owner or
a collaborator. A trusted batch shares the cache the branch's pushes use,
but never promotes into it; only a push to the default branch does. An
untrusted batch running a workflow that asks for secrets gets a cache of
its own, which starts empty.

Each run files a `dev.knotless.check` in the runner's account, with `ref`
the branch, `commit` the tip, `baseCommit` the base, and `batch` listing
each pull with its head and batch commit, in order. Batch checks are keyed
under `queue refs/heads/<branch>`, so one `listRecords` scan of that
prefix finds every batch check of a branch. Batches have different tips,
so their runs never collide and one never cancels another as newer. Every
check is filed before any run starts.

Readers group checks by tip, base and branch, count only the newest run of
each workflow, and give each batch a state:

| State | When |
| --- | --- |
| `checking` | any run is still `queued` or `running` |
| `landing` | every run passed, and still after it lands |
| `cancelled` | some run was cancelled, and none failed or errored |
| `failed` | otherwise |

A batch has landed when each of its pulls is merged at exactly its batch
commit. A workflow file that fails to load is an `error` run. Skipped and
reused workflows are not counted, so a batch with none left passes.

## Landing

When every run of the lowest batch has ended and all passed, the runner
lands it, as long as each pull is still the code that was checked and the
branch is still where the batch was built.

It resolves each pull's head again. If one moved, the batch checked code
that is no longer the pull, so every batch is dropped. It then reopens the
repository and refuses unless the branch is exactly at the batch's base.
The push is not forced, so a push to the branch that slips in after that
test fails it too.

One push moves the branch to the tip and deletes the pulls' spent head
branches. A head branch is spent when it is in this repository and the
owner's account, is neither the target nor the default branch, and no
other open pull brings or targets it. Then one `applyWrites` call in the
runner's account, all or none, gives each pull a `dev.knotless.state` of
`merged` whose `commit` is its own batch commit and whose `batch` is the
batch's tip: the commit whose checks let it land. Readers find from it
which checks a pull landed on, after the batch's own runs are pruned, and
which pulls landed together. On the default branch,
the same call closes the issues the pulls name with a closing keyword
(`fixes`, `closes`, `resolves` and their forms) in their title or body.
Each close is a `closed` state naming the pull, and within a batch an issue
is closed once, by the first pull naming it. The keyword rules are those
of any merge; see [collaboration.md](collaboration.md).

A landing that fails drops every batch, and the queue is built again.

## When a batch fails

A batch fails when any workflow's run ends other than `success`. Its runs,
and those of any batch ahead of it, are cancelled. The failure says some
pull broke something, not which.

A batch of one names its culprit, so that pull is ejected at its head. The
reason names the tip, the branch and its commit, and the failed
workflows, and `checks` points at their records. `knotless show` adds the
command that reads their logs, `knotless checks <repo> --queue <branch>
--log`.

A larger batch's pulls become suspects, and the runner halves: the first
half of the suspects, in queue order and rounded up, runs alone as the
next batch. A half that passes lands, and its pulls stop being suspects. A
half that fails becomes the new suspects. When one suspect is left after a
landing, it is ejected without running: its tree on the moved branch is
the tree that failed, so it would fail the same way. Its reason ends with
`Halving the batch found it`, and its `checks` are the first failing
batch's.

```mermaid
flowchart TD
  run[A batch is checked] --> pass{All passed?}
  pass -- yes --> land[Land it; its pulls leave the suspects]
  land --> left{Suspects left?}
  left -- none --> next[Build the next batch from the queue]
  left -- one --> last[Eject it without running]
  left -- more --> half
  pass -- no --> one{One pull?}
  one -- yes --> eject[Eject the pull]
  one -- no --> sus[Its pulls become the suspects]
  sus --> half[The first half of the suspects is the next batch]
  half --> run
```

Suspects hold only while what failed would fail the same way. If the
branch moves some other way, they are cleared, because what failed there
may not fail now. A suspect leaving the queue clears them too.

The runner remembers each pull it landed or ejected by the key of the
record that queued it, and passes it over until the queue as read stops
listing it under that key. A lagging index cannot make it build a pull
twice. A pull queued again has a new key and is taken again.

## Running ahead

If the next batch waited for the one before, a busy queue would land one
batch per run time. With `--depth 2`, the default, the runner builds the
next batch on the tip of the one being checked and checks it as if that
one will pass. It never runs more than one batch ahead; `--depth 1` checks
one at a time.

The batch ahead lands only when the branch is at the very commit it was
built on, where the batch before it landed. When the batch under it lands,
the runner looks at it in the same pass. If the batch under it fails or is
dropped, it is dropped too. No batch runs ahead while there are suspects,
since the next base depends on whether the half being checked passes.

Building ahead, a pull that conflicts is left out but not ejected. The
conflict may be with a batch that never lands, so the pull waits to be
built on the branch itself, where a conflict is real.

The batch that lands next runs in the runner's highest class, with pushes
to the default branch. A batch ahead runs in a lower class with a lower CPU
weight, so work that may be thrown away yields to the batch about to land.

## Noticing a queued pull

The runner reads the queue on each pass. It takes the appview's entries
(knotless-serve's index of records across accounts) and lays fresh reads
over them: the newest 25 `dev.knotless.queue` and `dev.knotless.state`
records about the repository, read straight from the owner's, each
collaborator's and, when the runner that lands the queue is neither, that
runner's accounts. A fresh record replaces its indexed copy, so a
record the index has not caught up with still counts. A read that fails or
takes more than 5 seconds adds nothing.

A pass starts when something rings the repository's door:

- Jetstream, a public stream of record changes, brings a
  `dev.knotless.queue`, `dev.knotless.pull` or `dev.knotless.state` record
  naming the repository. Its frames are unsigned, so the record is only a
  doorbell, and the pass reads the records again.
- Every `--notice` seconds (30 by default) the runner makes the fresh
  reads and rings if anything changed. A queued pull is taken in within
  `--notice`, whatever Jetstream brings.
- Each batch run's end rings, so the queue goes on without an event.
- A failed pass rings again after `--sweep` seconds or 60, whichever is
  less, and `--sweep` rings every
  door regardless.

Rings during a pass are answered by the next one. In a pass, queues come
last, after reruns, moved refs and pull runs.

## When something moves

Each change underneath a batch drops what it made stale:

| What moved | What the runner does |
| --- | --- |
| The branch, by another push | drops every batch, clears the suspects, builds again |
| The branch, deleted | drops every batch |
| A pull in a batch left, closed, merged or retargeted | drops that batch and every one after it |
| A pull's head | nothing until landing, which then drops every batch |

The runner sees the branch move when the lowest batch's base is no longer
its tip. Dropping a batch cancels its runs, which log `cancelled as the
merge queue dropped its batch`. That stands even for a run that would
otherwise finish when superseded, and no later cancel overwrites it.

When the runner stops, a batch run that has not started is dropped and its
check deleted. A drop at a stop is not a failure, so no pull is ejected.
A batch run already going is waited for. If it passes, it counts, and a
batch whose last run passes so lands before the runner stops: checking it
again on the next start would cost all its runs for a landing of a few
seconds. A run that fails while the runner stops counts for nothing, and
nothing else goes on: no batch is built, and the batch is checked again
on the next start.

## The queue and other runs

A queued pull does not run on its own; its batch is its run, apart from
the pre-flights the lander runs for it. It still runs when someone asks
for it with a rerun.

An open pull outside the queue runs again when its head moves, not when its
base does. Once queued it is checked against the branch anyway, so
retesting it on every base move would spend runs for nothing. While a
runner lands the queue, its pull runs rank below the batches and the
pushes.

Landing a batch pushes the branch to its tip, and that push would run the
same workflows on the same tree again. So the runner keeps a trusted
batch's passes, and the push that lands it on the default branch takes the
batch's result and cache layers instead of running. A pass is not reused
for a workflow with secrets, one that finishes when superseded (a deploy),
a check no longer `success`, or a run asked for by name. A batch can
likewise take a trusted pull's or an earlier batch's pass at the same tree
into the same branch.

## Reading the queue

Readers combine queue records with batch checks to say where a pull
stands: `Queued, 2nd of 5`, `In a batch of 3 being checked`, `Landing`, or
`Ejected:` with the reason and failed workflows. A queued pull in no
batch whose newest run of a pre-flight is still running is `Queued, 2nd
of 5, waiting for its pre-flight: check`, read from its own checks. A pull is in a batch when
one containing it is `checking` or `landing` and started after it was
queued. The CLI, the MCP tools ([../reference/mcp.md](../reference/mcp.md))
and the web show this. A pull's page shows it in its merge box, whose Add
to merge queue and Leave queue buttons write the same records as `merge
--queue` and `queue --leave`, as whoever is logged in, for the owner and
collaborators of a repository that names runners. The web's queue page lists each branch's queued
pulls, its batches, ejected pulls and the last five batches landed, from
the server's index of the named runners' checks; see [serve.md](serve.md).

## Measuring it

`just queue-stats` says how the queue did, by day (UTC), from what it
already writes: the queue records in the owner's PDS, the batch checks and
their logs, and main's log for when each pull landed.

- **queued** and **landed**: queue records written, and pulls landed.
- **queued → landed**: minutes from a pull's first queue record to its
  commit on main, past any ejections, at the median and the 95th
  percentile.
- **ejected**: ejections over queue records, and by kind: a conflict, a
  failed batch, a branch gone, or other.
- **batches passed**: of the batches that ended, those that passed.
- **batch test**: minutes of a batch's `test` run, the longest of its six.
- **cancelled checks**, by why: a runner restart, a batch dropped as the
  branch moved, a pull that moved on.
- **passed on a retry**: the tests the `FLAKY` lines name, by network
  and binary.

Merge queues are commonly judged healthy with queued → landed under 30
minutes at the median and 60 at the 95th percentile, a few percent of
pulls ejected, and over 80% of batches passing; the report says so under
its table.

The runner prunes batch checks it no longer needs, so each run keeps what
it read in `target/queue-stats/`, and later runs count it too. To see what
a change did, run it before and after, and compare the days either side.