How do you divide 39.7 million files among 128 workers when S3 will not tell you where they are?

Before it lists anything, swath has to cut the keyspace into pieces. It has no distribution to cut against, so it does what any blind partitioner does: one delimiter=/ probe for the top-level directories, then ranges cut along the boundaries it returns — capped at four per worker and evenly subsampled — each implicitly assumed to hold about as much as the next. For this bucket that came to 513 ranges and an expectation of 0.195% of the files in each.

Below is that assumption on top, and what the run actually measured underneath. Same 513 seeds, same order, same colour. 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 range owned by one worker. The filled part is what that worker has already listed. Watch for the ochre marks: those are splits — the moment an idle worker carves a busy one in half and takes the upper piece.

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=<token>, and the token 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 tokens. 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.

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.

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. That distinction is one of the project's two stated design laws.

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.

Resuming is gated on args_hash — a hash of the run's scope (scheme, endpoint, bucket, prefix, recursion, versioning). Output format and filters are deliberately excluded, because they don't change what gets listed. Resume against a mismatched scope is refused; --restart discards the old run.

Inside one flat directory — a single prefix with no sub-structure — the only tool S3 offers is start-after pagination: one round trip per 1000 keys, strictly sequential. A directory with 110,000 keys is ~110 sequential round trips, and adding workers does not help, because handing a worker a valid starting point deep inside that directory requires already knowing a key that far in — which costs exactly the listing you were trying to parallelize.

You can sometimes split such a directory by guessing name-prefix bands (hex 0–f, say) when the names are uniform. When they aren't, the sequential floor is real. It bounds only that one directory's tail — a bucket with many dense directories still parallelizes across them; only the last, densest one serializes at the very end. That is the red band you saw in Plate 2.

This is the run Plate 1 was drawn from: s3://noaa-gestofs-pds, a public NOAA forecast archive, listed cold with no inventory and no prior knowledge of its shape. The single heaviest seed was split 2,155 times over the course of the run — 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.

The last number is the honest one, and it went the wrong way. Perfect speedup here would have been 39 seconds — 5,030 busy worker-seconds spread evenly across 128 workers. It took 69. The missing 30 seconds are 3,750 worker-seconds spent idle — worker time not spent listing. Some of it is the partition still being corrected; startup, request latency, more workers than there is splittable work, and the unsplittable tail all contribute too, and this figure does not separate them. What it does say plainly is that at 128 workers a large share of the fleet was waiting rather than listing. That gap is a known lead, not a mystery, and it is being tracked.

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.