Publishing a tree into many places, exactly once

Some products let an organization define a standard once and roll it out everywhere. A company writes a safety checklist at headquarters and wants every site to use the exact same version. Do it for one site and it is trivial. Do it for a few hundred sites, repeatedly, and it becomes one of those features that looks like a button but hides a small pile of distributed systems problems.

This post is about that button. The interesting parts are tree copying, topological sorting, and a queue design that quietly removes a whole class of bugs.

What we are copying

The core entity here is a structured checklist. Think of a "Daily Inspection" with fields like "check tire pressure", "test the horn", "attach a photo".

The twist is that a checklist can embed other checklists. A "New Machine Setup" might include a "Safety Lockout" checklist as one of its steps, and that one might include another. So a single checklist is really the root of a tree.

Figure 1. One checklist is the root of a tree of nested checklists.

When you publish "New Machine Setup" to a site, every checklist in that tree has to exist at the site too. You cannot copy something that points at a "Safety Lockout" step if "Safety Lockout" was never copied over.

Copy order is the whole problem

A parent references its children by ID. When we copy the parent into a new place, it needs the new IDs of the children that now live there. So children must be created first, then the parent can point at the right copies.

In other words, copy the tree from the leaves up to the root.

This is a dependency ordering problem, and the standard tool is a topological sort. Build a graph where an edge means "this depends on that", then sort it into levels.

Figure 2. The sort produces levels. D is shared by B and C, and still gets copied only once.

Read it left to right. Copy D first. Then B and C, which only depend on D, can be copied. Finally A, which depends on both. Notice D is shared by B and C and still gets copied only once. Shared dependencies fall out of the sort for free.

The implementation is a level by level sort. Count how many things depend on each node, start with the nodes nothing depends on, and peel the graph apart one layer at a time. The same pass detects cycles. If A embeds B and B embeds A, the graph never resolves cleanly, so we reject the publish instead of looping forever.

A small planner holds the sorted levels and hands back one level at a time. After each item copies successfully, it drops out. If one fails, the planner marks that item and everything that depends on it as failed and skips them. A broken child should never leave a half built parent behind.

Now multiply it

The button does not copy one tree to one place. Someone selects several checklists and pushes them to many places at once.

So we are copying many trees, into many destinations, and the trees can share branches. The same "Safety Lockout" might live inside three different checklists that are all going out in the same run. Copying it three times into the same destination would be wasteful, and a good way to create duplicates.

Figure 3. Parents can share a child and also have their own. The planner expands every selected checklist into its full tree, copies each shared branch only once, and skips anything a site already has.

Two planning questions fall out of this:

1. What needs to go where? Expand every selected checklist into its full tree, drop the redundant work (if a parent is already going to a destination, its children ride along), and skip anything a destination already has at the latest version.
2. In what order, within a single destination? That is the topological sort from before.

The first question produces a clean list of work grouped by destination. The second runs inside each unit of work.

Editing the source, then pushing again

Bulk publish is not one and done. The source checklist is a living document. Someone fixes a step, adds a field, reorders a branch, and now every destination that took the old version is out of date. The button has to send those edits out again, to the same crowd of destinations, without turning a small fix into a full recopy of everything everywhere.

Two questions decide how much work a re-push really is. How does the system know which version a destination is sitting on? And how does it avoid touching destinations that are already current?

A version on the source, a bookmark on each destination

Every time the source changes, its edits are bundled into a new version, and that version carries a number that only ever goes up. The latest version is simply the highest number. None of this is inferred from a timestamp or guessed at by comparing contents; the version is a real, recorded thing.

Each destination keeps a bookmark: the exact version of the source it was last brought to. The first publish records the destination at some version. A later edit moves the source to the next version, while the destination's bookmark still points at the old one, so we know it is behind.

That single number is what makes a re-push easy to reason about. To decide whether a destination needs anything, compare two numbers: the source's latest version, and the version the destination is bookmarked at. Equal means current. Behind means there is work to do, and the gap says exactly how much.

Figure 4. The source sits at its latest version. Destinations behind it receive only the changes since their own version, and destinations already at the latest are skipped.

Skip anything already current

If a destination is already at the latest version, the best push is no push. Recopying an unchanged tree would burn work, churn a destination nobody asked to change, and hand the races another opening. So before any copying happens, we drop every destination whose bookmark already matches the source's latest version.

We check this twice, on purpose. The planner does a first pass and leaves the up to date destinations out of the plan entirely, so a worker never even picks them up. Then, right before the copy runs, the worker reads the bookmark one more time. The reason for the second check is timing. Between planning and running, another publish might have already brought that destination current. The plan time check keeps the queue small, and the run time check keeps the result correct even when the plan was a little stale. A stale plan costs a wasted glance, never a missed update or a duplicate.

A re-push is a diff, not a recopy

When a destination is behind, we do not throw its copy away and build a new one. We bring it forward. Because every edit to the source was recorded against a numbered version, the gap between the destination's version and the latest is just an ordered list of changes. A destination several versions behind has a longer list, nothing more. We replay those changes onto the existing copy in order, then move the bookmark up to the latest version.

This keeps the first publish and every later one honestly different in cost. The first time, a destination gets the whole tree. After that it only ever receives the difference. Shared branches follow the same rule: a nested checklist that did not change is left alone, and only the parts that actually moved get pushed.

The part that actually keeps you up at night

Getting the copy right is the easy half. The hard half is doing it for thousands of destinations, in the background, without stepping on yourself.

Picture two publishes hitting the same destination at nearly the same time. Maybe someone clicked twice. Maybe a bulk run and a single update overlapped. Both start copying the same tree. Both check "does this exist yet", both see "no", and both create it. Now the destination has duplicates, or something stuck at the wrong version. These bugs never show up in a demo. They surface later as "why are there two copies of this".

A few deliberate choices remove the problem.

Durable status, not in-memory hope

Every unit of work is a row in a table: one row per (item, destination). Each row moves through a small state machine.

Figure 4. Each unit of work moves through a small, durable state machine.

Because the state lives in storage, a worker crash does not lose the run. We can see exactly what is stuck, retry only the failed pieces, and report honest progress. Each run also stamps a shared ID on its rows, so all the work from one click groups together for tracking and for the progress bar.

The move into "in progress" is a compare and set: a row only flips if it is still "queued". If a stale retry grabs a row that already moved on, the update touches zero rows and we notice. Storage is the referee, not the application code's good intentions.

One lane per destination

The work runs on background workers fed by a queue. We use a first in first out queue, and the important detail is the grouping key.

Every message is tagged with a group key based on the destination. A FIFO queue guarantees that messages in the same group are delivered in order and never processed at the same time. Different groups still run in parallel.

Figure 5. One ordered lane per destination. Different destinations run in parallel.

That single choice removes the race. Two publishes aimed at the same destination are forced into one lane and processed one after the other. The second one sees the finished result of the first, so it correctly decides "already up to date" instead of creating a duplicate. Meanwhile different destinations sit in different lanes and run fully in parallel, so throughput holds up.

We did not fight concurrency by sprinkling locks everywhere. We picked a queue whose ordering guarantee matches the real constraint: one destination's data should only be touched by one writer at a time.

One path instead of many

Systems like this tend to sprawl. Over time you end up with several code paths that can each perform the copy. Every extra path is another chance for two of them to disagree.

The fix that mattered most was boring: route everything through one service. Single copies, bulk copies, and background syncs all call the same function. Before a run starts, we check that none of the selected items already have a queued or in progress job, so a second run can never stack on top of a live one. One path is easier to reason about, easier to test, and leaves far fewer corners for races to hide in.

Watching it happen

Because every piece of work is a tracked row, the person who clicked the button gets a real progress bar instead of a spinner and a prayer. As workers flip rows forward, an aggregated status streams to the UI. All the rows from one run collapse into a single status with a simple priority: if anything failed, show failed; if anything is still running, show in progress; only show complete when every piece is done.

What it adds up to

The lessons that stuck with me:

• Model the thing honestly. A checklist is a tree, so copying it is a graph problem, and a topological sort is the boring correct answer.
• Push state into durable storage. In-memory progress is a lie the moment a worker restarts.
• Let infrastructure enforce your invariants. A FIFO queue with the right group key removed a class of races more cleanly than any application level locking would have.
• Fewer code paths beat clever code paths. The biggest reliability win was deleting duplicates and routing everything through one service.

One click, many copies, in the right order, exactly once. That is the whole job.