← All posts

A restack is a state machine, not a script - publishing a rebased stack without losing a branch

Rezee rebases a stack of pull requests behind private refs and publishes it in one leased transaction. The five durable phases, the crash window each one closes, and why a stale-ref error is sometimes a receipt.

Sep 22, 2026 · 15 min read · Kash Gohil · LinkedIn · X

A stacked pull request is the shape you get when you stop waiting: branch B off branch A, open both, review both, land both. The cost is that the stack has to be rebased every time its base moves, and a rebase rewrites every branch above the one that moved.

The naive implementation is a shell script. Check out each branch, git rebase, force-push, repeat. It works until it is interrupted, and then it has left half a stack force-pushed to commits the other half no longer descends from. Nobody can tell you which half, because the only record of what the script intended was the script's own stack frame, and that is gone.

Rezee's restack is a row in Postgres with eleven states and five durable phases. This post is what each phase writes down, which crash it survives, and the two places where the obvious implementation is silently wrong.

What the job freezes

Queueing a restack writes one row and takes one lock. The row is pr_stack_jobs:

CREATE TABLE pr_stack_jobs (
  id              uuid PRIMARY KEY DEFAULT gen_random_uuid(),
  stack_id        uuid NOT NULL REFERENCES pr_stacks(id) ON DELETE CASCADE,
  kind            pr_stack_job_kind NOT NULL,      -- 'restack' | 'merge'
  state           pr_stack_job_state NOT NULL DEFAULT 'queued',
  requested_by    uuid NOT NULL REFERENCES users(id) ON DELETE RESTRICT,
  branches        text[] NOT NULL,
  attempt         integer NOT NULL DEFAULT 0,
  next_attempt_at timestamptz,
  expected_refs   jsonb,
  temporary_refs  jsonb,
  rewritten_refs  jsonb,
  reconciled_at   timestamptz,
  failure_code    text,
  failure_detail  jsonb,
  ...
);

CREATE UNIQUE INDEX pr_stack_jobs_one_unresolved_idx ON pr_stack_jobs (stack_id)
  WHERE state NOT IN ('completed', 'cancelled');

ALTER TABLE pr_stack_jobs
  ADD CONSTRAINT pr_stack_jobs_branches_ck
  CHECK (cardinality(branches) BETWEEN 2 AND 51);

Three things in that DDL are doing real work.

branches is frozen at queue time. It is the trunk followed by each layer's head branch, in order, resolved once. Everything afterwards is a statement about that array rather than a fresh look at the stack, so a pull request opened against the middle of the stack while a restack is running cannot change what the running job is rebasing.

The partial unique index is the ownership. One unresolved job per stack, enforced by the database rather than by a worker's good intentions. A second POST does not queue a second job; it gets job_active back with the existing job's id, which is the answer a retrying client wanted anyway. The index survives a process restart, which a mutex would not.

The cardinality check is a bound on blast radius. A trunk plus fifty layers. Not because fifty is a good number of pull requests to have open, but because every phase below is O(layers) in Git calls and an unbounded stack is an unbounded operation holding a lock.

The lock beside it is a Postgres advisory transaction lock, taken in sorted order so two jobs touching overlapping pull requests cannot deadlock against each other:

export async function withRestackLocks<T>(ids: string[], work: () => Promise<T>) {
  return db.transaction(async (tx) => {
    for (const id of [...new Set(ids)].sort()) {
      const [lock] = await tx.execute<{ acquired: boolean }>(
        sql`select pg_try_advisory_xact_lock(hashtextextended(${id}, 0)) as acquired`,
      );
      if (!lock.acquired) return null;
    }
    return work();
  });
}

pg_try_advisory_xact_lock rather than the blocking form, and null rather than an exception, so a caller that could not get in is told to come back rather than queued behind work it knows nothing about. The transaction scope is the release: if the process dies holding it, Postgres drops it when the connection goes.

The five phases, and the line they do not cross

The five restack phases, and where private refs become public public refs/heads/* private refs/rezee/stacks/<job>/* validating rewriting publishing waiting_for _checks completed snapshot every tip rebase the chain one leased transaction versions, CI, review carry-forward
Nothing anybody has cloned moves until the third phase, and when it moves it moves all at once. The first two phases are cheap to abandon because they have no reader.

The rule the whole design hangs off: a rebase is prepared entirely in a namespace nobody fetches, and published in one transaction. Denji, our Git server, serves that namespace at refs/rezee/stacks/<job>/. A person with the stack checked out sees nothing at all until publishing succeeds.

That buys the property that matters. The first two phases can fail, be retried, be abandoned or be interrupted by a deploy, and the observable state of the repository is identical to never having started. There is no partially force-pushed stack because there is no force-push until every commit already exists.

Phase 1: validating, and why it is re-enterable

prepareRestackJob asks Denji to pin the current tip of every branch in the frozen array under the job's namespace, then writes both the pins and the SHAs into the row.

Two writes in two systems, which is the shape that always has a crash window. Here the window is: Denji created the refs, and makima died before its UPDATE committed. On restart the job is still validating and the refs exist, so a naive retry would ask Denji to create refs that are already there.

Denji refuses that on purpose. It never reuses an existing namespace, because an existing namespace might belong to an interrupted operation whose SHAs are now meaningless. So the retry reads them back instead:

try {
  temporary = await git.createTemporaryRefs(ws, repo, job.id, job.branches);
} catch (error) {
  if (error instanceof DenjiTemporaryRefConflict && error.code === "temporary_refs_exist")
    temporary = await git.readTemporaryRefs(ws, repo, job.id, job.branches);
  else throw error;
}

temporary_refs_exist is not an error in this path. It is the missing receipt from the call that succeeded before the crash. The distinction between that and temporary_refs_stale - the namespace exists but its SHAs no longer match the branches - is the entire difference between resuming and corrupting, which is why Denji returns two codes rather than one.

Phase 2: rewriting, and reading the answer back out of Git

rebaseTemporaryChain replays each layer onto the rebased layer below it, entirely inside the private namespace, and answers with a map of old SHA to new SHA per branch.

Same crash window, harder version: Denji moved every private layer ref and makima missed the reply. Re-running the rebase would rebase the already-rebased chain, which produces a valid-looking result that is wrong.

The recovery reconstructs the answer rather than recomputing it:

export function recoverRebaseResult(
  original: TemporaryRefSet,
  current: TemporaryRefSet,
): RebaseChainResult | null {
  if (
    original.operation !== current.operation ||
    original.refs.length < 2 ||
    original.refs.length !== current.refs.length ||
    original.refs[0]?.sha !== current.refs[0]?.sha
  )
    return null;
  // ... every branch and ref identity must match, position by position
}

The load-bearing check is original.refs[0]?.sha !== current.refs[0]?.sha. Index zero is the private trunk pin, and Denji never moves it. If the trunk pin has moved, this is not an interrupted rewrite of the thing we snapshotted, and the function returns null rather than guessing. Anything structurally different is corruption, not a resumable result.

Phase 3: publishing, and the stale-ref error that is a receipt

This is the only phase that touches a branch anybody has. It builds one transaction from the two checkpoints already in the row - the SHAs captured at queue time as the expected value, the rewritten SHAs as the new value - and hands it to Denji, which runs it through git update-ref --stdin:

var input strings.Builder
input.WriteString("start\n")
for _, update := range updates {
	fmt.Fprintf(&input, "update refs/heads/%s %s %s\n",
		update.Branch, update.NewSHA, update.ExpectedSHA)
}
input.WriteString("prepare\ncommit\n")

Git's ref transaction is all-or-nothing under the three-argument form: every branch moves only if every branch is still at the SHA the caller named. A layer somebody pushed to while the restack was preparing fails the whole publication, and fails it having moved nothing. Denji then re-reads every expectation and answers with the branches that raced, because "something was stale" is not actionable and "feature-b is at abc123, not def456" is.

Now the third and worst crash window: Denji's transaction committed and makima missed the reply. A retry sends the same updates, every branch is already at its new SHA, and Denji correctly reports all of them stale. Treating that as a conflict would strand a stack that is in fact perfectly published.

/**
 * Denji reports only failed leases. After its atomic transaction succeeded,
 * every update that actually changed a SHA must therefore be stale at exactly
 * its requested new SHA. A subset means some branches remain unpublished; an
 * extra or different value is a real concurrent public change.
 */
export function publicationAlreadyApplied(
  updates: RefTransactionUpdate[],
  stale: StaleRef[],
): boolean {
  const changed = updates.filter((update) => update.expectedSha !== update.newSha);
  if (changed.length === 0 || stale.length !== changed.length) return false;
  const byBranch = new Map(stale.map((ref) => [ref.branch, ref]));
  if (byBranch.size !== stale.length) return false;
  return changed.every((update) => {
    const ref = byBranch.get(update.branch);
    return ref?.expectedSha === update.expectedSha && ref.actualSha === update.newSha;
  });
}

The atomicity of the Git transaction is what makes this inference sound. Because the transaction was all-or-nothing, "every changed branch is stale at exactly its target" has one cause, and it is success. One branch short, or one branch at a third value, and it is a real conflict: the job moves to stale_refs and stops, with the offending refs in failure_detail.

This is the piece of the system I would defend hardest in review, and it is twenty lines. It is also the piece that is only correct because of a property of a different service, which is why the comment above it names that property rather than describing what the code does.

Phases 4 and 5: reconcile, then release

Publication moved the refs, which is the dangerous half. The rest is making the product agree with the refs: insert a new version per pull request, carry forward which files each reviewer had marked viewed, pin the new diff so an old review survives garbage collection, queue CI, index the new symbols.

Every one of those boundaries is retryable on purpose. The version pair is unique, Denji's diff pins are append-only, CI runs are keyed by job plus branch. reconciled_at is stamped last, so a crash anywhere in the middle re-runs the whole reconciliation and lands in the same place. Only after reconciliation, after checks pass, and after the private namespace is deleted does the job reach completed and release the partial unique index.

The runner is a bounded loop, not a daemon

export async function runRestackJob(id: string, runner: RestackRunner = defaults) {
  for (let phase = 0; phase < 5; phase++) {
    const job = await runner.read(id);
    if (!job || job.kind !== "restack") return job;
    // ... re-authorize, pick the step for job.state, run it
    const result = await step(id);
    const next = await runner.read(id);
    await runner.progress(next);
    if (!result.ok || (next.state === job.state && ...)) return next;
  }
  return runner.read(id);
}

Five iterations, because there are five phases and a pass that does not advance the state is a pass that is waiting on something outside this process. Every iteration re-reads the row rather than carrying state in local variables, which is the mechanical reason a restart is a resume: the loop has no memory that the row does not have.

It also re-authorizes on every pass, not just at admission:

const gate = await repoWriteGate(owner.ws, owner.repo, { id: job.requestedBy }, "restack pull requests");
if (!gate.ok) return false;
for (const branch of job.branches.slice(1)) {
  const protection = await protectionForBranch(owner.repoId, branch);
  if (!protection.allowForcePushes || protection.requirePullRequest) return false;
}

A restack force-pushes. If the requester lost write access, or somebody turned on branch protection, between queueing and publishing, the job fails with authorization_changed rather than exercising permissions its requester no longer has. The check costs a handful of reads per pass and closes the gap where a long-running operation outlives its own authorization.

Merging the stack is the same row with a different plan

Landing a stack is the second kind on the same table. The difference is what gets frozen: a restack freezes branch order, a merge freezes an immutable prefix.

mergePlan: jsonb("merge_plan").$type<{
  throughPrId: string;
  trunkBranch: string;
  landedCount: number;
  layers: { prId: string; position: number; headBranch: string }[];
}>(),

"Merge through layer 3" is decided once, at admission, and merge_progress counts how far through that plan the job has got. A worker sweeps runnable merge jobs every five seconds and does at most one layer per job per sweep, which keeps a fifty-layer stack from holding the lock for fifty merges.

The ordering inside that sweep is the part worth copying:

const attempt = Math.min(31, row.job.attempt + 1);
const [reserved] = await db
  .update(prStackJobs)
  .set({ attempt, nextAttemptAt: new Date(now.getTime() + mergeRetryDelay(attempt)) })
  .where(and(
    eq(prStackJobs.id, row.job.id),
    eq(prStackJobs.state, row.job.state),
    eq(prStackJobs.attempt, row.job.attempt),
    eq(prStackJobs.mergeProgress, row.job.mergeProgress),
    due(now),
  ))
  .returning();
if (!reserved) return;

The retry deadline is reserved before the work runs, under a compare-and-swap on the exact state the sweep read. A crash mid-merge therefore respects the backoff on restart, where reserving afterwards would let a job that crashes reliably be retried in a tight loop forever. The delay doubles from five seconds and caps at five minutes; landing a layer resets attempt to zero and schedules the next one five seconds out.

The same file has the rule that is easy to get backwards:

} catch (error) {
  // Never turn a transport error into failed/cancelled or clear an intent.
  console.error("merge worker step failed", row.job.id, error);
}

An exception from the step means we do not know what Git did. failed is a claim, and it is a claim that would let somebody edit the pull requests underneath a merge that may have landed. Not knowing is its own state, and the honest response to it is to retry under backoff.

What is not on the job row

A stack member row carries order and nothing else:

CREATE TABLE pr_stack_items (
  stack_id uuid NOT NULL REFERENCES pr_stacks(id) ON DELETE CASCADE,
  pr_id    uuid NOT NULL REFERENCES pull_requests(id) ON DELETE RESTRICT,
  position integer NOT NULL,
  added_at timestamptz NOT NULL DEFAULT now(),
  PRIMARY KEY (stack_id, pr_id)
);

No title, no review state, no CI status, no health. Those live on the pull request and are resolved when the stack is read, because a stack is a view over pull requests rather than a second copy of them. The same instinct as treating an agent as a row in users: the new thing is an arrangement of existing rows, not a parallel world.

Health is computed, and the computation is forty lines with one interesting idea in it:

/** Only a contiguous merged prefix is historical; everything else is live. */
export function remainingStack(trunk: string, pulls: Layer[]) {
  let offset = 0;
  while (pulls[offset]?.state === "merged") offset++;
  // ... from offset up, each layer's base must be the layer below's head
}

Layers 1 and 2 merged is a stack that has partly landed. Layer 2 merged while layer 1 is open is a stack somebody broke, and it reads as needs_restack with the position named. Walking the merged prefix first, rather than filtering merged layers out, is what makes those two cases different answers instead of the same one.

What it cost

The honest list, because a post that only lists wins is a brochure.

  • Five phases is five times the surface. The restack path alone carries 49 integration tests, 22 database tests for the job transitions, and a dedicated test file for the rewrite-recovery function. Most of them exist to assert that a crash at a specific instruction lands somewhere recoverable. That suite is slower than the feature.
  • Every phase boundary is a two-system write. Git and Postgres do not share a transaction and never will. Each boundary needed its own answer to "what if the other one landed and we did not hear", and each answer is different, because what is recoverable differs by phase.
  • Resumability is a property of the schema. expected_refs, temporary_refs and rewritten_refs are three jsonb columns whose only purpose is to make a restart a resume. They are dead weight on a happy path and the entire feature on an unhappy one.
  • The conservative failure is still a failure. A stack that raced a push stops at stale_refs and waits for a person. We prefer that to a robot deciding which of two force-pushes was the one somebody meant, but it is a human interruption that a more aggressive design would not have.

The bet, and we would make it again: a repository is the one thing in a product you cannot restore from a retry. Every phase here exists so that the worst case of an interrupted restack is an operation that has to be re-run, rather than a branch whose commits nobody can find.

FAQ

What is a stacked pull request?

A pull request whose base is another open pull request's branch rather than the trunk. It lets you keep working on top of code that is still in review, and it means each review is one coherent change instead of one enormous one. The cost is that the whole chain has to be rebased when anything below it moves.

Why not just force-push each branch in a loop?

Because the loop has no durable record of its own intent. Interrupt it after three of five force-pushes and nothing in the system knows which two are missing or what they were supposed to point at. Preparing every commit privately and publishing in one leased transaction means the repository is never in a half-rebased state to begin with.

What happens if someone pushes to a branch mid-restack?

The publication fails and moves nothing. Git's ref transaction only commits if every branch still matches the SHA captured when the job was queued, so a racing push is caught at the moment of publication rather than silently overwritten. The job stops at stale_refs with the racing branch and its actual SHA recorded, and re-queueing picks up the new tip.

How do you know a retry is not double-applying a rebase?

Each phase reconstructs its answer from Git rather than recomputing it. The rewrite compares the private namespace against the snapshot it started from and requires the private trunk pin to be unchanged; the publication treats a stale-ref error as success only when every changed branch is stale at exactly the SHA it asked for. Anything short of an exact match is treated as a conflict, not as a resume.

Does this work for an agent running a restack?

Yes, and it is the same code path. An agent restacking through the API is the job's requested_by like anybody else, so it is re-authorized on every pass and is subject to the same branch protections. See scoped tokens for agents for how that authorization is narrowed.