Skip to content

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.

round trip 0

Before listing, the whole key space is one range. The seed lists the top level's folder names and cuts there.

Ranges over the key space, as wide as the keys they hold
The sorted stream, its parts, and the resume point K
The 64 workers
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
A model, not a measurement: 64 workers, 96 made-up starting ranges, one page per round trip for every worker, and each split cuts what is left at its middle. It makes the kinds of decisions swath makes, in the same order. K is where a resume would start: the last key of the last part whose journal record is on disk.

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.

Pages follow one another; a range can start at any boundAbove, three pages of a listing, each request starting after the last key of the page before. Below, the key space with two start bounds, a and b, named without listing anything. How many keys lie between them is unknown until the range is listed.A listing reads one page after anotherpage 1page 2page 3…each request starts after the last key of the one beforeA range can start after any bound the store acceptsabhow many keys lie between? no request says
Following pages is cheap but takes one round trip at a time. Naming a bound costs nothing, but nothing says how much work lies behind it.

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.

257 starting ranges, and the one that held most of the bucketTwo strips of the same 257 ranges in key order. Above, each as wide as an even share. Below, each as wide as the objects it held: the third range takes 64.5% of the strip, and the other 256 share the rest.An even share each: 0.39%23.9 million objects, 64.5%What each heldthe other 256: 35.5%Median 42,080 objects; none empty
The starting ranges of the home page's run, in key order. The seed cut at folder names, which say where the structure is but not how many objects lie behind it. The third range, (_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.

Three ways to own a boundary keyFive keys split at the key b. If both ranges exclude b, nobody lists it. If both include it, it is listed twice. swath's left range (a, b] includes it and the right range (b, c] starts after it, so b is listed once.bgapboth exclude bb listed by neitheroverlapboth include bb listed twiceswaththe left owns b(a, b](b, c]
The left range lists keys up to and including 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.

The seed cuts at folder namesOne wave of two requests: a delimiter listing of the top level, which returns folder names such as _para3/ and estofs.20210102/, and the first data page, kept only if the bucket fits on it. The folder names become cuts on the key space, which make the starting ranges.One wave of requests, before any range is listeddelimiter listingfolder names of the top levelfirst data pagekept if the bucket fits on it_para3/estofs.20210102/…stofs_2d_glo.20261108/2,169 folders in the NOAA runcuts, evenly spaced256 cuts kept: 257 starting ranges
The seed's first wave. A narrow top level would add waves, one level down each, within the budgets.

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.

A range split by its ownerThe range from lo to hi. The part up to the cursor c is listed. The rest is split at the pivot m into a lower child from c to m and an upper child from m to hi.listedlower childupper childlocmhi(lo, c] ∪ (c, m] ∪ (m, hi]
A split of the range (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: m lies 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.
Three splits along one chain, each reflected from the anchorThree rows, one per split. In each, the range's owner has listed up to its cursor c, and the cut point m lies as far past c as c lies past the anchor a. The lower child goes to an idle worker; the upper child carries the chain on. The piece handed out doubles from one split to the next.acmcmcmeach lower child goes to an idle worker
Reflection along one chain of splits. The upper child carries the anchor 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.

Listing requests in flight over the run, and where they wentFor the first 13 seconds about 63 of the 64 workers list the other starting ranges and one lists the largest. From the first split at 13.2 s, the largest range's share grows until, from about 30 s, every request in flight is on it. The last range ends at 53.1 s; the run ends at 61.0 s.6400 s10 s20 s30 s40 s50 s60 sfirst split, 13.2 slast range 53.1 ssplits of the largest starting range (1,834)
  • requests listing the largest starting range
  • requests listing the other 256
  • after the last range: draining, publication and finalization
The home page's run, from its trace, in quarter-second steps. For 13 seconds one worker listed the range that held 64.5% of the bucket while the others had starting ranges of their own; once those ran out, every split fed an idle worker, and all 64 listed pieces of it.

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).
A chain of splits against a balanced treeTwo ranges over three round trips. On the left each split peels a small piece off the front, so after three round trips there are four pieces and most of the range is still on one worker. On the right each split halves its range, so after three round trips there are eight pieces of equal size.A chainA balanced tree4 pieces; most of it on one worker8 pieces of equal sizeone row per round trip
Splits wait for pages, so the depth of the tree of splits is a floor under the time. A cut point that peels a little off the front makes a chain; one that hands out half or more keeps the tree shallow.

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.

The tree of ranges and the frontierA range has listed its first part and split; its upper child has split again. Walked depth first, left to right, the pieces are in key order. The stream below has every row up to the frontier, inside the lower child still being listed. Rows already listed further right wait, in memory and then on disk.frontierthe stream, in key orderlisted ahead: waits in memory,then on disk
Grey is listed and already in the stream, solid is listed and waiting, outlined is not listed yet. A range that split keeps only what it listed; its children list the rest.

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.

Parts, their journal records, and the resume pointFour parts in key order. Parts 0 to 2 have journal records on disk and are in the dataset. Part 3 is written but its record is not on disk when the run crashes. The resume point K is the last key of part 2: a resume checks parts 0 to 2 and lists again after K.partsjournaldatasetpart 0part 1part 2part 3Kcrasha resume checks parts 0 to 2 against their records,then lists again after K
Commit before emit. A part's record reaches disk before the part joins the dataset, so the records always describe what is published. The resume point 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:

bash
swath list s3://bucket/logs/ -o /data/logs-2026-11-08 --seed-from /data/logs-2026-11-07

The 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).

Tiles admitted in key order, inside a windowSixteen tiles in key order. The first four are written. The next five are admitted and listing, inside the window at the output. The rest wait to be admitted.the window at the outputwrittenadmitted, listingnot admitted yettiles of about 32 pages, cut from the previous inventory's counts
A refresh lists front to back. A new tile is admitted as the output moves on, so the rows waiting for the output stay near the window instead of growing with the bucket.

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).

Complete and partial prefixes in one run of keysOne range's run of contiguous keys starts inside the prefix a/ and ends inside d/. The prefixes b/ and c/ lie wholly inside it, so their totals are final. a/ and d/ are cut by the run's ends and are summed by name across runs.one range's rows: contiguous keysa/b/c/d/complete: the total is finalpartialpartialpartial prefixes are summed by name across runs
A prefix that one run holds whole is complete as soon as the run passes it. Only the prefixes at a run's two ends wait for other ranges.

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.

Released under the Apache-2.0 license · by Varve