How I built swath: listing a billion S3 objects in 4 minutes

A couple of months ago, I was working on a project involving buckets from the AWS Open Data registry. These are public S3 buckets, some of them very large, with billions of objects.

Many of those buckets do not have any form of a public inventory available, so the practical interface I had for listing their contents was the S3 API, ListObjectsV2.

Try to use any naive approach for listing a large bucket using this API, and you will quickly find that it is slow. The API returns up to 1,000 objects at a time. At around 100 ms per request, listing a bucket with a billion objects serially can take more than a day (1 billion objects ÷ 1,000 objects per request × 100 ms ≈ 27.8 hours).

Ten billion objects would take nearly twelve days at the same latency. That might be manageable when you need to do it once. Doing it frequently, across many large buckets, quickly becomes a real pain to manage.

I ended up building a new tool that is able to list large S3 buckets really fast, regardless of their key distribution. My last runs clocked a 1-billion bucket in under 4 minutes, and a 10-billion bucket in under 19 minutes. This is the story of swath.

Existing tools and their limits

Before building swath, I looked at other tools that could parallelize listing in some way. I tried every open-source listing tool that I could find. Some of them worked well on buckets with certain shapes and up to a certain size, but I could not find one that covered everything I needed.

I became curious and started investigating why. I used coding agents to study how each of those tools works: what method it uses for parallelization, how it buffers data, when it does well and where it struggles. This was early work on what ended up being the tools section in the s3-listing-study repo, which I have now open-sourced.

In short, most of the tools I found use one of four broad listing strategies:

1. Serial pagination (e.g. aws-cli, MinIO mc, s5cmd ls) - these tools follow one ListObjectsV2 pagination chain: they make one request, wait till it comes back, and then request the next using the continuation token from the response. This works regardless of the bucket shape but is inherently serial and slow.
2. Prefix or hierarchy discovery (e.g. rclone’s hierarchical walk, s7cmd) - these tools use the bucket’s /-separated prefix structure to create multiple listing jobs; this can work well for buckets that have a reasonably balanced directory-like hierarchy, but much less so when the keyspace is flat or a few prefixes contain many more objects than the others.
3. Speculative range splitting (e.g. s3p) - these tools invent synthetic boundaries in the keyspace to list several ranges in parallel. They work even if the keys don’t have a /-delimited hierarchy, but they still have to guess where useful boundaries might be, and a split that might look balanced lexically can still be very unbalanced in reality.
4. Externally supplied partitions (e.g. s3-fast-list with hints, s5cmd run) - these tools can list multiple ranges in parallel, but only after someone tells them what those ranges are. That information can come from an inventory, a previous listing or just someone’s knowledge of the bucket structure. This can work well once the partitions are known, but they can’t help parallelize the listing of an unfamiliar bucket.

For the workload I had, every tool was missing something. Some could not parallelize certain bucket shapes. Some modes accumulated enough state to OOM at larger sizes. Retry and throttling behavior varied, and I could not find one that let me resume a large unfamiliar listing after a crash.

Building swath

After seeing this, I wondered whether there was a way to combine the useful ideas. Could I build a tool that would list different kinds of buckets quickly without knowing their key distribution in advance? One that would keep discovering opportunities for parallelism while it ran, scale without holding the full result in memory, adapt when the server throttled it, and resume after a crash instead of starting over?

That question became swath.

In a nutshell, swath does not depend on getting the partitioning right before the listing starts. It begins by doing a cheap initial division of the keyspace, and then keeps correcting it based on what it actually finds. If one of the ranges it initially came up with turns out to contain most of the bucket, swath keeps splitting it and lets idle workers help with newly created ranges. The important part is that a bad initial guess does not leave most of the bucket stuck behind one worker for the rest of the run.

It does this with a bounded worklist and streaming output, so its memory use does not grow with the number of objects in the bucket. When writing a managed Parquet dataset, the worklist is persisted in SQLite, allowing an interrupted listing to resume instead of starting over.

It uses virtual threads to support hundreds of workers in one process and AIMD to adapt concurrency when S3 starts pushing back. It can write text or Parquet, and its sorted-Parquet mode produces a globally sorted dataset as part of the run.

Testing swath

During the development of swath, I made thousands of listing runs against hundreds of buckets of different kinds, so I could try out different algorithms, tunable parameters, resource sizing, and crash conditions. Most of the buckets that I tested it on are public.

I quickly found out that testing reliably against public infrastructure is difficult. First, many public buckets are continuously updated and their listings can change over time. Second, you might hit different request latencies and throttling behavior caused by conditions out of your control, which can greatly skew the result of any benchmark, all the more so if you want to test many possible configurations in parallel yourself. And finally, I worried that hitting S3 repeatedly with highly concurrent listings might look like a DDoS attack and get me acquainted with the AWS abuse department.

So instead of testing against the live S3 infrastructure, I built swath-replay.

swath-replay takes a frozen, globally sorted Parquet capture of a bucket that swath itself is capable of producing, and serves the subset of ListObjectsV2 used by swath and the other tools in the study. I conformance-test those request and response shapes against real S3, but it is not a general S3 emulator.

With that, I could run swath-replay as one process and then run swath against it as another process on the very same machine, and expect to get the very same results every time. No risk of objects changing, no networking noise, no load conditions out of our control, and no blocks or abuse emails.

Capture once

  +----------------+   ListObjectsV2   +-------+   writes   +----------------+
  | live S3 bucket | ----------------> | swath | ---------> | sorted Parquet |
  +----------------+                   +-------+            | capture        |
                                                            +--------+-------+
                                                                     |
Replay repeatedly on the same machine                                |
                                                                     |
  +------------------+   ListObjectsV2   +--------------+   reads    |
  | swath under test | ----------------> | swath-replay | <----------+
  |                  | <---------------- |              |
  +------------------+   S3 responses    +--------------+

The difficult part was making sure the replay server itself did not become the bottleneck. For ordinary full-page requests, I managed to make it faster than live S3. Directory-structure probes were harder, however, and the study exposed cases where replay missed its configured latency deadlines under load and disproportionately slowed swath. The globally sorted order proved to be instrumental here, but this is material for a separate post.

Another capability I added was latency injection: replay can hold a response until a fixed deadline derived from live S3 observations for that request shape. I realized later that this is less accurate than it sounds. S3 latency changes with load; replay currently has no tail latency, throttling, or latency rise under load.

Because of those limitations, I treat the comparative replay runs as controlled diagnostics rather than calibrated benchmark measurements.

Benchmarking and optimization

A month ago, swath was already in a functional state, working fast enough against any bucket that I threw at it, including ones with tens of billions of objects. Still, I found myself working on it during many late nights and weekends, simply because I was enjoying it. With swath-replay built, I could test swath against it in a closed loop, and the optimization work almost felt like a game. Especially with the help of coding agents, I could try out wild ideas quickly, even ones that would change thousands of lines and introduce or rip out complex machinery, and have confidence that an improvement is real and that the results are still correct thanks to the testing infrastructure I had put in place.

I got curious and ended up building benchmarking infrastructure to measure just how fast it can go: running it at scale on many kinds of cloud instances with varying amounts of resources, and against many target buckets.

In these live runs, swath 0.3.2 returned 1.07 billion rows in 3 minutes 44 seconds and 10.29 billion rows in 18 minutes 45 seconds, with a steady memory footprint and good CPU utilization.

All five are single runs against live S3 using swath 0.3.2, not averages. They ran on the same kind of 64-vCPU VM, and the clock includes writing the compressed TSV to disk. The rates are just the exact row counts divided by that time. The s3-listing-study results have the full setup and caveats.

I also ended up circling back and trying all the other open-source S3 listing tools again, this time using the benchmarking setup I had built. The full report is in the s3-listing-study repo.

I did my best to find a good configuration for each tool, including non-default modes when I could find them, but I’m sure I missed better setups. swath naturally got a lot more attention than the others, and it was the only tool whose code I changed. Most of these runs were also against swath-replay, not live S3, with all the limitations described above.

What started as a small sidetrack in another project somehow turned into a couple of months of late nights and weekends. This sure wasn’t my plan when I started, but I can definitely say I enjoyed it a lot. Both swath and the study repo are open source; if I got one of the tools wrong, or if you tried swath and it didn’t work so well on your bucket, I’d really like to hear about it.