How do you divide 39.7 million S3 objects among 128 listing workers when you cannot see how their keys are distributed?

Two words first, because the rest of the page leans on them. Every S3 object has a key — the byte sequence used as its name — and S3 lists those keys in one global order. This guide calls that ordered set the keyspace. A range is a non-overlapping slice of that order, assigned to one listing worker. If it helps to think of objects as the files stored in the bucket, the keyspace is the single sorted list of all their names.

Before it emits any objects, swath cuts the keyspace into pieces with a bounded delimiter=/ descent. The boundaries reveal structure, not exact object counts: even mass-aware seeding has only bounded samples and keyspace span to work from. The worker-proportional cap is min(1000, 4 × workers) cut points — 512 at 128 workers. This run opened with 513 ranges, which is consistent with that cap, but the retained trace records the range count rather than the seed path that produced it. The upper strip therefore uses a uniform baseline: 0.195% of the objects per range.

Below is that baseline on top, and what the run actually measured underneath. Same 513 initial ranges, same order, same color. Only the widths differ.

The grey profile is mass — where the keys sit in the keyspace. Real buckets are wildly lumpy like this, as Plate 1 just showed, and the engine cannot see the profile; it only ever learns it by listing.

Each colored band is one active range, owned by the worker named inside it. The filled part is what that worker has already listed. A worker moves left to right until it finishes; it never jumps from one live range to another.

When an idle worker steals, it cuts the unscanned remainder of a busy worker's range in two. The busy worker keeps the lower child; the thief immediately takes the upper child. The animation pauses on that exact moment and labels both children. Hollow triangles show the other handoff: an owner shedding an upper child into the dashed pending row for an idle worker to claim. In the recorded run below, owner-side shedding made 92% of all splits. A red tick is a probe that found no useful upper child.

For a general-purpose bucket, S3's ListObjectsV2 gives you one page — up to 1000 keys, in sorted byte order — plus a way to ask for the next one. You can start anywhere by sending start-after=<boundary>, and the boundary need not be a key that exists. So splitting the keyspace is free.

What no request will tell you is how many keys sit between two boundaries. There is no count(prefix) and no "give me keys 50,000–51,000". The only way to find out how much work a range holds is to list it — which is the work. That is the whole problem, and it is why parallel listing is a guessing problem rather than a partitioning one.

That ordered start-after contract is what the range model rests on. S3 directory buckets provide neither the same global order nor StartAfter, which is why swath does not support them.

Everything in the engine is expressed as a half-open range (A, B]. Send start-after = A (S3 returns keys strictly greater), emit each returned key while k ≤ B, and stop at the first key past B without emitting it. B = null means the open frontier — the rightmost range, with no upper bound.

Which side owns the boundary key is the most load-bearing convention in the system. swath's rule: the boundary belongs to the left. Get it wrong in either direction and every single split silently corrupts the output — one key lost, or one key duplicated, per split, across thousands of splits.

Given a range, where do you cut it? swath has two independent answers, and the interesting part is that each one fails exactly where the other works.

The seed, in one paragraph

Before a single worker claims work, SeedStep issues a shallow delimiter=/ pass at the listing prefix. S3 returns the top-level common prefixes p1 < p2 < … < pk, which become cut-points: (⊥, p1], (p1, p2], …, (pk, null]. The cut count is capped at min(1000, 4×workers) and evenly subsampled, so seeding is proportional to the parallelism you actually have. The descent adaptively goes one level deeper only where a sub-level is narrow and complete, and the whole thing is bounded by a probe wallet — a directory explosion can spend the wallet, never blow it. All the seed nodes are inserted in one atomic transaction, so the very first durable state is already a valid tiling of the keyspace.

Source: docs/internals/algorithms.md §8

A worker with no pending range to claim, while others are still busy, becomes a thief. It picks the victim with the largest estimated remaining work — an estimate anchored to what that victim has already listed and how fast it is draining, with the open-frontier worker scoring infinite until it gets a finite bound — and tries to cut it in half.

The pivot is never a bare midpoint. It is placed from what the run has already observed: for a bounded range, an interpolation inside (cursor, hi] using the alphabet actually seen in returned keys; for the open frontier, a forward reflection of the density already drained. Then exactly one probe — a max_keys=1 request — tests whether the upper half has any keys at all. Only when that probe comes back empty does the thief spend more.

There is a fourth trigger worth knowing about, because it inverts the usual direction: owner-side split. On a dense, fast-draining range, even a valid pivot can be overrun before the split commits — the drainer advances a full page per round trip and passes the pivot. So the range's own owner places a pivot far ahead of its cursor and commits the split at page-commit time, gated to fire only while live work has fallen below the worker count. The mechanism is global; the trigger is local and demand-driven — design law L2 in docs/internals/overview.md.

This fourth trigger did most of the work in the recorded run below: 2,204 of 2,399 committed splits were owner-side, while thieves took 195. Both paths are paced to limit unproductive splitting: within a claimed range, its owner carves no more than once per 32 committed non-empty pages, and across the fleet only one thief may own the steal-attempt slot at a time, including any probes that attempt issues. These limits can slow worklist refill; issue #205 tracks their effect and possible demand-aware replacements.

Two rules govern every mechanism above, and both were arrived at by being wrong first. They are not coding conventions or aesthetics — they are findings about where estimation breaks on real data, and any new mechanism has to be argued against them. Plate 1 is the evidence for the first one.

The ordering above is not incidental. A page's checkpoint commits before its rows go downstream. That means the checkpoint can never claim a page that wasn't durably recorded — and it means the reverse window is real: stop the process between the commit and the emit, and you have a page that was committed and never written out.

swath does not paper over that. It tracks two cursors per range. cursor is the last committed key. durable_cursor is the highest key whose pages all live in finalized Parquet parts — parts whose footer has been fsynced. Resume rewinds to durable_cursor, discards the unfinalized tail, and re-lists only that bounded stretch.

Which of those you get depends on where you send the output. swath can stream a table, TSV, or JSONL, and text output may be gzip- or Zstandard-compressed; it can also write TSV/JSONL directory datasets or a managed Parquet dataset. Durable resume is a managed-Parquet feature, and globally sorted Parquet is an opt-in finalization path on top of it. The full decision table lives in docs/usage.md; the short version:

A resumable run stores several related identities. args_hash identifies the listing scope. The filter specification and the output/run identity are persisted separately. swath resume refuses a change to any identity field, because combining different targets, filters, or output contracts would produce an incoherent dataset; operational settings the CLI documents as free or restorable may be restored or re-supplied. --restart discards an unfinished checkpoint instead. The full rules are in docs/usage.md.

For a managed Parquet dataset: no row lost, none duplicated — across splits, steals, crashes, and resumes. An interrupted stdout or text-file run is at-most-once, as the table above describes. A guarantee like that is worth exactly as much as the machinery that would catch its violation. This is that machinery.

Each invariant carries a number (I1–I12) in the repository’s contracts.md, and the contribution rules require that a high-risk unit’s adversarial test — the one trying to break no-gap/no-overlap, or resume-after-crash — is authored or reviewed independently of the code’s author. The test that wants the code to fail is never written only by the person who wants it to pass.

Then the instruments, each answering a different kind of distrust:

• Adversarial keyspaces, in memory. Property suites drive the real engine over generated pathological keyspaces — 0xFF bytes, supplementary-plane characters, boundary shapes built to break pivot math — and assert the listing is complete and duplicate-free under every split/steal interleaving they can provoke.
• kill -9, for real. Integration suites SIGKILL a live listing process mid-run — no shutdown hooks, no goodbye — then resume and require the same complete listing a crash-free run would have produced: nothing missing, nothing doubled. The recovery rule above is exercised as a fact, not an argument.
• A replay of real buckets. A replay server serves captured listings of real buckets back over real HTTP, with measured per-request-shape latency profiles injected — millions-of-objects realism, deterministic and free, without touching S3. The server’s own fidelity is itself tested by diffing its responses against recorded real-S3 traffic, page for page.
• A deterministic simulator. The real split/steal decision code runs against a modeled store in virtual time — same seed, byte-identical run — so a policy pathology found once can be replayed exactly, thousands of times, while it is being fixed.
• An independent reader. Parquet output is verified with DuckDB — a reader that shares no code with the writer.

One structural choice makes all of this bite harder: --checkpoint none is not a separate fast path — it is the same durable machinery pointed at an in-memory database. There is one code path, so the invariants are exercised by every run and every test, not only the checkpointed ones.

Source: docs/ops/dev/TESTING.md · docs/swath-replay.md

A flat prefix is harder to divide, but it is not inherently serial. Current swath recognizes a truncated, dense flat region during seeding and pre-cuts it into leading-byte radix bands. During the run, a thief can also synthesize a density-based pivot without that boundary being an existing key. Those guesses work especially well for hex, UUID, timestamp, and similar printable-ASCII names.

Parallelism stops helping when those bounded guesses cannot find a useful populated child, or when no safe boundary remains strictly between a range's cursor and end. The owner must then finish that residual range. Ordinary pagination within one range is sequential — one round trip per page of up to 1,000 keys — so a large residual tail can still set the run's finish time. The red band in Plate 2 illustrates that outcome; it does not claim that every flat prefix reaches it.

A second potential floor is inside the client: all listing workers feed one bounded channel drained by one output-stage consumer, so output backpressure can serialize a large fleet before batches reach the background writers. A swath 0.3.1 compressed-TSV run on a 1.07-billion-object bucket exposed this bottleneck; see the performance guide for diagnosis and issue #206 for the dated evidence.

The measured example on this page is the capture identified as noaa-gestofs-pds-field-guide-trace — a label assigned to this artifact, not one recorded at capture time. It ran against the public NOAA archive s3://noaa-gestofs-pds/. The trace shows 128 distinct listing workers, consistent with the published concurrency ceiling of 128. The swath version, commit, capture date, exact command, output mode, target and client regions, machine type, and whether seeding used prior information are unknown in the retained evidence; they are marked unknown here rather than inferred.

This is not the recording embedded in the repository README. That is a separate capture of the same bucket, made with swath v0.2.1, which returned 39,585,029 objects — a live bucket changes between runs, so the two are identified separately. The interactive trace linked at the end of this section is this capture, not that one.

Plate 1 was drawn from this run. The single heaviest seed was split 2,155 times over the course of it — mostly by its own worker shedding work ahead of its cursor, since only 195 of the run's 2,399 splits were taken by thieves. Owner-side splitting is what refilled the worklist; idle workers claiming those shed ranges is what emptied it again.

Across the 69-second trace event span, dividing the 5,030 recorded busy worker-seconds evenly across 128 workers gives a 39-second idealized lower bound for this run's own work accounting. The roughly 30-second gap is the run's 3,750 recorded idle worker-seconds divided across the fleet — worker time not spent listing. Startup, stretches with less splittable work than workers, and residual work that could not be usefully split all contribute; the figure does not separate them. At 128 workers, a large share of the fleet was waiting rather than listing. That is a diagnostic of this run — a lead being tracked — not a portable efficiency score or a benchmark result.

Everything above is the argument. Everything below is the implementation behind it — collapsed, because you do not need any of it to understand what swath does or to decide whether it is useful to you. Open what you want to audit.

One clarification before you do. In this guide, worker means a listing worker issuing ordered S3 page requests. Output writers and sorted-finalization encoders are separate bounded pools and do not scale one-for-one with --concurrency: a run at --concurrency 128 does not have 128 Parquet writers or 128 sort encoders.