Welcome back! In part 1 we surveyed the Atmosphere and found lots of projects failing to verify blocks, susceptible to data tampering by low-trust network actors like relays and hubble. A bit bleak, but fixable.

This post digs more into the format, stuff that's harder to fix (but with some impending good news).

Aerodynamics/streaming MST CARs

Spoiler on this one: it's probably about to get resolved:

...where atproto repo serialization v4 will require stream-ordering the CAR's blocks. This is fantastic news, the best outcome. So I'll keep this section short ("short"), but still keep it, because the IETF draft isn't reflecting this yet.

Repository data exports in atproto are CAR files. These full-repo exports are core to backfilling and resyncing. Export sizes follow a really intense power-law distribution: almost all repos are very small, but most of the network's data is in big repos. Most CARs are under 100KiB, but they can be gigabytes.

CAR files do not naturally lend themselves to stream processing, since they are just a series of content-addressed blocks in no particular order. To walk a tree structure like an atproto MST usually means buffering all blocks in memory first. Some implementations, like Bluesky's PDS during repo imports, can consume multiple times more memory than the raw CAR size.

To backfill the 45 million repos in the Atmosphere:

Simple sync implementations like Tap make you pick:

Complicated ones like hubble-sync can go faster with less memory, but to get there looks like:

Stream-ordered CARs (the dream)

Ultimately your atproto CAR processor needs to walk the MST. You follow content-addressed links to step down to nodes (which are blocks in the CAR) and leaves (also blocks in the CAR). What if the blocks in the CAR were pre-ordered in just the way, that the next block need is the next block in the CAR? You could walk and process the tree as you stream the CAR in.

The (current!) IETF repo draft tries to do this,

Preorder traversal enables streaming verification of repositories, allowing parsers to walk the MST structure and output key-to-record mappings while maintaining minimal MST state in memory. This approach supports efficient stream processing of large repositories without requiring complete buffering of the serialized data.

Sadly, it can't work, because

Parsers MUST tolerate other block orderings,

You can watch me try to explain why these conflict (a bit badly) at IETF 126 (slides). (I started making a post explaining it better but probably won't finish that unless someone tells me they would actually read it). But basically: duplicate record blocks are possible (and real) in atproto, and have the same CID by definition, so you cannot avoid buffering all record blocks, because you can't be sure you won't need a block you've already seen again, later. Which defeats the memory-efficiency claim.

Current state of things: Bluesky shipped an optimistic streaming CAR/MST parser which doesn't hold on to blocks in stream-order-looking CARs, and can fail to parse some perfectly valid archives. Repo-stream originally interleaved parsing and walking while still buffering, but abandoned that for full up-front buffering for better performance and less complexity. @atcute/repo optimistically streams to enable earlier UI reactivity, but also buffers records, so it doesn't save memory but is correct.

The fix for this problem is not complicated: you just have to know in advance whether a CAR is stream-ordered or not. Then, parsers working on stream-ordered CARs don't need to tolerate other block orderings, and a missing duplicate block becomes a serialization error.

Hopefully, we'll get IETF consensus on a way to mark a CAR as stream-ordered (or only support stream ordering, which, looks like this is happening!!!!). Tap would be able to support way higher concurrency on small machines and I could delete a whole lot of awful code from hubble-sync!

So this is fixable if we can change the spec. The spec is still just a draft, so there's reason to hope!

Streaming CARs, redux

To quote again from the spec draft,

The block-and-header layout described here is compatible with Content-Addressable archive (CAR) formats such as DASL-CAR.

For stream-ordered CARs, I'm a little nervous about this compatibility claim, which I worry might really just be "happens-to-work", for two reasons:

Garbage trucks in on your blocks

Whew. Onwards. This one is small potatoes. The spec draft already addresses it, I'm just calling it out anyway:

Unrelated blocks not referenced by the repository structure SHOULD be ignored. Excessive quantities of such blocks MAY be treated as a form of resource abuse; see Section 6.

For non-stream-ordered CARs, I don't think you can actually detect "excessive quantities" of garbage blocks, because you can't interpret all blocks until the whole CAR is buffered. A tiny repo could be stuffed with gigabytes of garbage easily.

With stream-ordered CARs, I think garbage blocks should make the archive invalid -- probably worth a spec edit.

Gas guzzling / incompressible CIDs

This is Part 1 again, but for space efficiency instead of a security.

Every CAR block gets prefixed by a 36-byte CID: a 4-byte fixed prefix + 32 byte sha-256 hash of the block's content. Those hash bytes are high-entropy (random-looking) and cannot be compressed. Which is annoying, because they are fully redundant! You can recover them by just hashing the block's content!

Those 32 bytes are part of why STAR-lite files compress to half the size of CARs.

MSTree removal: ...why serialize it?

Hot take: I don't think the Merkle Search Tree structure belongs in repo exports at all.

Repository data is key-value. The MST structure is deterministic from the data. Including the MST doesn't add anything, it's storage-implementation-detail leaking in and wasting terabytes of bandwidth.

If you have repository data in strict key order, the MST is really cheap to reconstruct and verify in a single streaming pass over the data, with the same memory overhead as processing a stream-ordered MST-including CAR.

...if you strip the MST and remove the redundant CIDs, you pretty much end up with STAR-lite, so you can see my bias here.

We could have a world with

But I should probably write that up in a proper STAR-lite post, so I'll just leave it there for now.

Trip report

If we get working stream-ordered CARs in the final IETF spec, the biggest practical problems will be resolved. Fingers crossed. That could even turn me from moderately-anti-CAR to begrudgingly-CAR-accepting. A format that works, isn't a new invention, and only has some limited defects isn't the worst place to land.

It's still going to be work to move the ecosystem toward verifying CIDs, and work to keep new projects from regressing there, but that's just work to do.

The inefficiencies and risks won't go away though, so I don't think the desire for a better repo export format will go away either. STAR-lite already has wide enough use from clients using Hubble alone that it would be disruptive to drop. Ecosystem fracturing with more and more formats is also bad, but I think it's the path toward eventual adoption of a better format into the protocol. One day?

Appendix: CARs in atproto spaces, again

Just writing down in advance that I hope the updated proposal for space ships CARs is roughly:

I'm not convinced about the value a separate "index" at the start of the archive, it feels like it's just trying to shoehorn in some content addressing. (not sure if the plan is to keep it or not!)

This, again, is basically just spaces STAR-lite, but less efficient 💅. But I'm looking forward to the update regardless!

*no-roots bonus: would be a compatibility break with some IPLD CAR libraries, which I'd take as a win, since they almost never verify CIDs as we saw in part 1. (no roots is explicitly allowed in DASL-CAR, so it wouldn't be a compatibility break where it matters)