How swath lists a bucket in parallel
A bucket's listing API hands out keys one page at a time, in order. swath lists a large bucket quickly by dividing its keys into ranges that many workers list at once, and it still writes one sorted inventory. This guide shows how, on one real run: the whole public bucket s3://noaa-gestofs-pds, listed into a sorted Parquet inventory by 64 workers on a 4-vCPU cloud VM.
- Objects: 37,064,981
- Time: 60.9 s. The last range ended at 53.1 s; draining, publication and finalization continued for about 7.8 s.
- Requests: 39,016, none retried or throttled.
- Starting ranges: 257, found with 3 requests.
- Splits: 2,203.
- Largest starting range: 64.5% of the objects, split 1,834 times.
The run report draws every range and split of this run from its trace. The run was measured once, with main at d8fbe439 on 2026-11-15, and the bucket changes over time (how it was measured).
The mechanism in miniature
Before the details, the whole mechanism at a size you can watch. A seed cuts the key space into starting ranges, 64 workers list them, the owner of a heavy range splits it for workers that are idle, and the ordering stage stitches what they list into one sorted stream. The stream is written as parts, and each part is recorded before it joins the dataset. The sections below take these steps one at a time.
Before listing, the whole key space is one range. The seed lists the top level's folder names and cuts there.
- Pages listed
- 0
- Ranges listing or queued
- 1
- Splits
- 0
- Workers busy
- 0 of 64
- Parts published
- 0 of 8
- Manifest
- not yet
- listed, waiting for the stream
- not listed yet
- in the sorted stream
- the heavy starting range and its pieces
- a split's cut point
- a part: written, recorded, published
- an idle worker
The constraint
A listing request returns one page of keys and a token for the next page. The keys come in order: on S3 and GCS in byte order, comparing keys byte by byte as unsigned numbers. A request can also start after a key you name, whether or not that key exists: start-after on S3, startOffset on GCS and startFrom on Azure Blob. The providers differ in the details, and swath adapts their page sizes (up to 1,000 keys on S3 and GCS, up to 5,000 on Azure Blob), their ordering and whether a start bound is inclusive or exclusive. Ranges can start at admissible synthetic bounds, without finding an existing object: any string the store accepts as a start bound will do. So the keys can be cut into pieces, and each piece listed on its own.
What no request tells you is how many keys lie between two cut points. The only way to learn how much work a piece holds is to list it, and that is the work. Dividing a listing is a guess, and the guess is corrected while the listing runs.
The NOAA run shows why it has to be corrected. Its 257 starting ranges came from the bucket's folder names. The median range held 42,080 objects; one held 23.9 million, 64.5% of the bucket.
(_para3/, estofs.20210102/], was split 1,834 times.The range, and the one-key mistake
Every piece of work is a range (lo, hi]: the keys after lo, up to and including hi. Its first request starts after lo, and keys past hi are dropped. The boundary key belongs to the range on its left: of two neighbors (a, b] and (b, c], only the left one lists b. A boundary need not name an object, but when it does, the rule decides who lists it. Incorrect boundary ownership can omit or duplicate an existing boundary key; the order guard, the check every row passes on its way out (below), rejects duplicates.
b; the right one starts after b. Together the ranges of a run cover the keys once, so workers run side by side without removing duplicates afterwards.Keys are compared as bytes, unsigned, the order S3 and GCS list them in. Azure Blob lists in UTF-16 order, and swath's Azure source serves its ranges in byte order over it. Every stage that handles a key checks the order again: the range, the ordering stage, the part writer and the journal. A test splits ranges at random points and checks that every key is listed exactly once (the invariants).
Starting ranges: the seed
A delimiter listing asks for the folder names under a level, the common prefixes up to the next /, instead of every key below them. A folder name is cheap and says where the structure is, though not how many objects are behind it. The seed concurrently requests delimiter listings and the first data page, descends at most four levels below the top, and emits that data page if complete: a bucket that fits on one page is listed in one round trip. Otherwise the page is discarded and swath cuts the bucket at its folders. A level with fewer folders than workers is listed one level deeper, every folder at once, within fixed budgets: at most four levels below the top, 64 requests and 6 round trips. swath keeps at most min(1000, 4 × workers) cuts, evenly spaced.
In the NOAA run the seed listed 2,169 top-level folders with 3 requests, in under half a second. At 64 workers swath kept 256 of them as cuts, which makes 257 ranges.
Splits: the owner hands off
Workers finish their ranges at different times. After each full page, a range's owner checks whether any worker is idle with nothing queued. If one is, and its own range is among the largest left, it splits what it has not listed yet. Its last listed key c becomes the start of a lower child (c, m], and an upper child (m, hi] takes the rest. The owner hands both on and stops, and idle workers take them.
(lo, hi]. Its owner has listed up to c and hands the rest on as two ranges that idle workers take. The three pieces cover the range, and none overlaps another.Only the owner splits its range, at a page boundary, against the cursor it has. No other worker cuts into a range while it is being listed, so a split cannot race the owner's next page, and no request is repeated.
A split is made only where it is worth its requests: each child pays at least one request of its own. swath normally does not split a remainder under two pages, or where either child would be under one page, as estimated from the range's last page.
The cut point m need not be a key that exists. swath places it from what the listing has already shown:
- by reflecting the cursor from the chain's anchor, where the chain of splits began:
mlies about as far past the cursor as the cursor lies past the anchor, so each further split hands out more; - by the density of keys on the last page, when that reaches further: how closely the page's keys are spaced says how far a few pages' worth of keys reach;
- at a folder boundary, found by a delimiter listing from the cursor when a range's splits keep landing in the folder it is already in.
a, so its next split, by whichever worker lists it, hands out about twice as much: a few splits reach across a large remainder instead of peeling a page at a time.Every cut point is valid UTF-8 and leaves out characters a store may refuse in a start bound.
The NOAA run made 2,203 splits, all of them when a worker was idle: 1,579 by reflection, 416 by density, 121 at folder boundaries and 87 at the midpoint between the cursor and the end of the range. The first came at 13 s, when workers began to run out of starting ranges. The largest starting range was split 1,834 times, and all 64 workers listed pieces of it. The range engine has the rules in full.
- requests listing the largest starting range
- requests listing the other 256
- after the last range: draining, publication and finalization
Where parallelism stops helping
- Chains of splits. A split waits for a page, so a chain of splits that each depend on the one before costs one page's round trip per link. A balanced tree of splits keeps those chains short.
- A range that cannot be split. When no usable key lies between a range's cursor and its end, its owner lists the rest alone, one page per round trip.
- The store. swath shares one adaptive request limit across its workers. It reduces concurrency under sustained throttling and recovers as the answers improve (throttling). In the NOAA run requests in flight averaged 52.3 of 64.
- The output. Rows leave through one sorted stream and the part writers, so a run that writes an inventory can wait on its output (next section).
The request count has a floor: one request per page of keys. The NOAA run made 39,016 requests for 37,064,981 objects, about 1.05 per 1,000. On S3, a billion objects require at least a million listing requests (cost). A scheduled inventory (S3 Inventory, GCS Storage Insights, Azure Blob inventory) can cost less, when a daily or weekly report is fresh enough (when swath fits).
One sorted stream
The inventory is written as Parquet parts: files of rows in key order, each starting after the last key of the one before. Ranges finish out of order, yet the inventory is sorted without a sort afterwards. Each range lists its keys in order, and its children sort right after what it listed. The ranges therefore form a tree whose depth-first walk is key order. One drainer walks that tree and hands rows to the output as they arrive at the front of the walk, the frontier.
Rows listed ahead of the frontier wait in memory, up to a budget: --sort-buffer, by default 1/16 of memory and at most 1 GiB. Past it they spill to disk. Each range writes its own file, already in order, coded against the row before and compressed. When the drainer reaches that range it reads the file front to back, with no merge and no index. Once listing has ended, on a machine with cores to spare, the rest of the stream is cut into parts where the writer would cut them, and several parts are written at once.
Every row passes one check on its way out, the order guard: its key must sort after the previous row's. A violation fails the run before any output sees it. With the same build and encoder path (amd64 with AVX2, or every other platform), output is byte-identical across worker counts unless time closes a part (ordering).
In the NOAA run the drainer spent 41.3 s waiting for the frontier while the workers listed further ahead. Spill wrote 795 MB to disk, 4.4 GB of rows before coding and compression, with at most 618 MB on disk at once.
Commit before emit, and resume
Journaled runs keep recovery state locally: in the output directory, or the work directory for remote output (--work-dir, when -o names a bucket). The journal holds a record per part, with its size, its SHA-256 and its last key. An inventory of an object store keeps one; a filesystem run does not. A part joins the dataset only after its journal record is on disk. The manifest, manifest.json, is written last and names every part: a directory without it holds no dataset.
K is the last key of the last recorded part.The resume point is the last key of the last recorded part. swath resume DIR checks every part already published against its record, size and SHA-256, then lists again after that key. It never writes a key twice and never skips one. No worker's cursor and no split is saved, so a resume makes its own splits. Ranges that spilled ahead of the output can be sealed as certified spill files, each holding exactly the rows of one key interval as the run listed them, recorded once its bytes are on disk. A resume replays those instead of listing them again. The tests stop a run at every crash point, including with a real SIGKILL, and resume it. Crash tests compare rows, and compare part bytes when build, encoder path and time-cut conditions permit (stopping and resuming).
A listing is not a point-in-time snapshot. swath publishes the complete result of the live listing it performed: an object written or deleted while it runs may or may not be in it.
Listing a bucket again: the seeded window
A refresh can start from the previous inventory instead of folder names:
swath list s3://bucket/logs/ -o /data/logs-2026-11-08 --seed-from /data/logs-2026-11-07The previous dataset knows how many keys lie where, so swath targets tiles of about 32 listing pages, by expected keys, and skips the delimiter seed and most early splits. Its requests approach one per page.
With those counts the run lists the bucket front to back. Tiles are taken in key order, and the window guides admission toward eight million rows at the output, or fewer when the disk or the sort buffer holds less; it is not a strict storage bound. Rows listed ahead of the output, and the spill they need, stay near that window instead of growing with the bucket. The splits stay adaptive: a region that grew since the previous run is split as on any run (seeding a refresh).
Exact totals without sorting: the swath du view
swath du keeps no rows and needs no order across ranges. Its workers count rows as they arrive: there is no drainer, no spill and no file. Bare swath du on a terminal shows the largest prefixes at any depth, and every figure in it is exact. On the NOAA bucket it took 53.7 s for 37,081,362 objects, with a peak of 119 MiB against the sorted inventory's 1.51 GiB (how it was measured).
It uses the order inside each range. The rows a range lists before it splits, or all of them if it does not, are one run of contiguous keys. A prefix that a run enters after its first row and leaves before its last is complete, so its total is final. The prefixes at a run's two ends are partial; they are summed by name across runs and are complete when the listing ends. Of the complete prefixes and objects, the view keeps the 100 largest at each depth, whatever order the listing completes them in. A dropped one's bytes are already counted in its parent's.
The view then fills the terminal from the largest down, each line under its parent with its size, object count, share, bar and newest date, and the largest prefixes open first. Each parent's other children are folded into one counted (N more) line, so every level adds up. No line goes to an entry under 0.5% of the total (a quarter of one line's share on a short terminal): a long tail of small prefixes stays in its fold, and the view may end shorter than the terminal. On a local tree, ! after the size marks a line whose sums leave out a directory that could not be read (the view).
Read the run
The run report is generated from the NOAA run's trace by tools/explainer. It shows how the starting ranges turned out, the rate of the run over time, the cut points it chose, a map of every range over the keys and time, a replay of the run, and a ledger that rebuilds the ranges from the trace and checks that they cover the bucket once.
If you have a bucket whose keys this engine cannot divide well, open an issue. The shape of its key distribution is enough; names and contents are not needed.