Scaling past a million fragments (tiered manifest prototype)

[geruh]

Jack opened Going beyond millions of fragments and followed up with benchmark work on scaling manifests. Version hints in #5997 and #6752 help you find the latest manifest faster. That solves latest-version discovery. It does not change the size of the manifest body itself and every append still rewrites the full fragment list unless the layout changes.

This post is about that second problem.

I want to get the ball rolling on what we do once fragment count gets past a million. I built a prototype on branch tiered-manifest and ran some numbers.

Here are some rough docs

• DESIGN.md
• FORMAT_DECISIONS.md
• Prototype lives here

This post has the bench numbers. Those two files have the design and on-disk format.

The idea prototyped (two levels)

Right now every version is one protobuf file with every fragment inline. Append means writing a new file with the old fragments plus the new one. Cost tracks total fragment count, not the size of the append.

The prototype splits that into a small root plus sealed child files. Think bounded write buffer at the root and immutable chunks on disk. B epsilon tree shaped. Not a full B epsilon tree.

It is opt in only. Flat stays the default. Below 100K fragments nothing seals, so tiered stays in the same single-root layout as flat and, you can set layout back to flat and inline everything in a maintenance commit. This is not a one-way format trap.

At 150K fragments with epsilon 100K, the prototype has one sealed child and a 50K-fragment root buffer.

FLAT today                         TIERED (opt in)

every commit                         every commit
    |                                    |
    v                                    v
+-----------------+                  +-----------------+
| ROOT MANIFEST   |                  | ROOT (buffer cap)|
| all N fragments |                  | refs + buffer    |
| grows with N    |                  +--------+--------+
+-----------------+                           |
                                         sealed children
                                         (never rewritten)

At 150K with epsilon 100K and measured sizes from the bench run.

FLAT                               TIERED at 150K

every commit                       every steady append
    |                                  |
    v                                  v
+-----------------+                +-----------------+
| ROOT MANIFEST   |                | ROOT MANIFEST   |
| all 150K frags  |                | 1 child ref     |
| 9.28 MiB        |                | 50K frag buffer |
+-----------------+                | 3.15 MiB        |
                                   +--------+--------+
                                            |
                                            | ref
                                            v
                                   +-----------------+
                                   | SEALED CHILD    |
                                   | frags 0..99,999 |
                                   | 6.18 MiB        |
                                   | written once    |
                                   +-----------------+

On disk.

{dataset}/
  _versions/{manifest}.manifest       root (schema, refs, buffer)
  _manifest_children/
    v{version}-{min}-{max}-{uuid}.manifest    sealed once
  data/*.lance

Full field-level detail stays in DESIGN.md and FORMAT_DECISIONS.md on the branch.

---

What we measured

NOTE: Benchmark is in prototype branch and is Local NVMe, release build, public API only.

Charts 0 and 1 are measured. Charts 2 and 3 plus table 5 are extrapolated with epsilon 100K and calibrated from the measured 150K root and child sizes.

Latency numbers are local FS. Byte counts and GET counts are the storage facts. I am not claiming S3 latency from this run. However this can be extended to test S3.

The measured cases were 10K real single-row appends and 150K fabricated fragments through the real commit path.

---

Headline numbers

At 150K fragments, steady append rewrites 3.15 MiB of root instead of 9.28 MiB. That is about 3x less root PUT data.

Warm reopen after one more append reads 3.15 MiB instead of 9.29 MiB. Warm reopen at 150K tiered used 3 root GETs and 0 child GETs.

Cold open is the trade. Same total metadata bytes, about 9.3 MiB, but 5 GETs instead of 3 at 150K. More child files means more round trips when nothing is cached.

At 10K fragments, tiered has the same 0.763 MiB root as flat and zero children. This run showed local p50 at 52.15 ms for tiered and 47.98 ms for flat, so I would not call local p50 a tie. The storage path is still a tie at this scale because nothing seals.

---

Scenario A table

10K real single-row appends.

layout	commit p50	commit p99	total	open	root	children
flat	47.98 ms	102.29 ms	495.77 s	6.4 ms	0.763 MiB	0
tiered	52.15 ms	103.60 ms	512.05 s	6.2 ms	0.763 MiB	0

Scenario B table

150K fragments with epsilon 100K.

metric	flat	tiered
migration append	62 ms, root 9.28 MiB, 0 children	34 ms, root 3.15 MiB and one 6.18 MiB child
steady append	51 ms, root PUT 9.28 MiB	38 ms, root PUT 3.15 MiB
cold open	42 ms, 3 GETs, 9.29 MiB	57 ms, 5 GETs, 9.33 MiB
warm reopen	53 ms, 3 GETs, 9.29 MiB	31 ms, 3 GETs, 3.15 MiB

---

Where this helps and where it hurts

Helps when you append a lot, fragment count is well above 100K, and readers mostly follow the tip of the table. Root PUT stops growing with total fragment count.

Ties below 100K fragments. It also ties on total metadata bytes on disk. Tiered splits the same data across files. It does not shrink fragment count.

Hurts on cold open and full enumerate. The model is 3 root GETs plus 2 GETs per sealed child. At 1M fragments that is roughly 21 GETs for tiered versus 3 for flat.

Still hurts on both layouts if compaction never runs. You can still mint fragments until data files are the real problem. Tiered only caps root rewrite size.

---

What v1 actually does

It seals overflow into _manifest_children/ when the root buffer goes over the cap. Root holds refs plus a tail buffer. Open materializes everything into the same fragment list flat would have. Old readers without the feature flag refuse tiered tables.

What it does not do yet

• lazy open
• append without cloning the full fragment list in RAM
• cleanup for orphaned child files after failed commits or re-seals
• anything beyond two levels

Disk layout gets better before CPU and memory do. That matters for root PUT size. It does not fix in-process cost on a 10M fragment table yet.

Delete, compact, and most non-append commits re-seal from scratch in v1. Only pure append keeps old children. Maintenance-heavy tables may not see the same win as append-only ones.

---

Other ways to scale past a million fragments

Two levels is just where I started. I do not think we have to land there forever.

Keep compacting harder

Jack's point in #4000 still stands. Delta gets away with a flat list when compaction keeps fragment count down. Maybe the answer is better default maintenance, not a new layout. Tiered helps when you already have the fragment count and cannot rewrite history overnight.

More than two levels

Child buffers can have their own buffers. Same idea recursively. Root stays tiny. Cold enumerate GET count keeps climbing unless you add caching, merge jobs, or lazy load.

Partition by fragment id

Shard metadata by fragment id range instead of one global buffer. Each shard has its own root and children. Commit touches one shard when appends are local in id space. Enumerate merges shards. This feels natural if fragment ids are monotonic and the partition is by range. It needs design work for cross-shard row routing and commits that span shards.

Manifest delete vectors

Iceberg-style tombstones on sealed files would let delete and update avoid rewriting every child. v1 re-seals everything on non-append ops. Delete vectors may be the path to fixing that.

Lazy materialize

Load refs and buffer on open. Pull a child only when a scan or lookup needs that id range. Ref fields already carry row offsets and byte sizes. Enumerate can stay eager while point lookups stay cheap.

Background merge of adjacent children

optimize_manifest can run off the ingest path. Collapse many children into one when maintenance runs. That keeps enumerate GET count from growing forever on append-only tables.

Byte threshold instead of fragment count

Buffer cap as 100K fragments assumes a roughly stable fragment entry size. Blob-heavy tables may need a byte cap, or both.

---

Questions

1. How do we want to scale past a million fragments? Is two levels enough as a first step, I think going beyond that would need a tree partition key maybe fragment id.

2. For tables that mostly append, is capping root PUT enough to ship something? Or do we need lazy open and child cleanup first?

3. When delete and compact dominate, is tiered even the right lever? Should delete vectors come first?

4. Is 100K fragments the right default buffer, or should config be byte-based?

Happy to walk through the on-disk format, split a read-path-first PR, or throw away this approach if compaction plus version hints is the better bet.

Design doc and bench harness are on branch tiered-manifest. Reproducible with tiered benchmark on branch.

[jackye1995]

Thanks for putting this together @geruh — really great to see a prototype with real numbers, and a lot of the machinery here (root buffering, refs with id ranges, the bench harness) stays useful no matter where we land. Before going deeper on the mechanics though, I want to take a step back on what problem we should be designing for, because I think it changes the conclusion on sealed children.

Fragment count alone is not the real problem

A fragment entry is ~80 bytes, so 1M fragments is only ~80 MiB of manifest — and at 1M rows per fragment, that already holds 1 trillion rows, which is good enough for a very long time. If a workload cannot get anywhere near 1M rows per fragment, that is a separate problem of how data gets written (and compacted), and we should fix it in the write path rather than design the metadata layout around tiny fragments.

What actually gets out of control is the second dimension of the format. Lance tables are 2-dimensional: add column + backfill adds a new data file entry to every fragment it touches. Each round of backfill multiplies the size of the fragment list with zero change in fragment count, and this is core to how Lance is used for ML and feature engineering. So the design target should be: keep metadata cost bounded when the manifest grows in fragments × columns, not just fragments.

Why sealed immutable children break down

This is where I think the current proposal falls short: you cannot really make the child level immutable. The doc already notes that delete/update/compact re-seal from scratch in v1, with delete vectors as the v2 fix — but delete vectors only express removal. A backfill adds a new data file to every fragment, including every fragment inside every sealed child, and there is no tombstone representation for "every fragment gained a data file". So you either rewrite every child on backfill (full write amplification is back), or you let children absorb the new data files and grow (their size multiplies again, past whatever cap they were sealed at). Either way, "sealed once, never rewritten" stops holding exactly on the workload that hurts the most.

Make it a real Bε-tree

This is why I originally suggested a B-epsilon tree rather than a tiered layout. The goal is really about self-balancing the tree node size so it stays optimal all the time — no cliffs, no global re-seal — and the ε (a per-node message buffer) is what gives amortized write amplification: in a plain B-tree, updates are applied to nodes immediately, and today's flat manifest is the degenerate single-node version of that, where we rewrite the whole thing on every commit.

Concretely:

Root node = the manifest we already have. It stays a protobuf file holding the table metadata and the list of fragments to be backwards compatible, plus one new section: fragment_actions, the root's ε buffer. Actions are things like AddFragment, RemoveFragment, AddDataFile, RemoveDataFile, AddDeletionFile. A commit appends its actions to this buffer instead of rewriting fragment state (unless the fragment is in the root manifest). With ~100K fragments (~8 MiB) plus ~2 MiB of buffered actions, the root stays around 10 MiB — and below that scale the tree is just the root, i.e. today's manifest plus a buffer, so nothing changes for small tables.

Flush instead of re-seal. When the root buffer fills, actions are flushed down to the children owning the target fragment id ranges. Each flush rewrites one node and carries a large batch of actions with it — that is where the amortization comes from.

Child nodes are Lance files, not protobuf. @Xuanwo ran an experiment storing 1M fragment entries in Lance format: roughly half the size of protobuf and ~6x faster to decode. Child manifests do not need schema, table config, or any other table-level metadata, so a plain tabular Lance file is ideal: the fragment list is just rows, and the node's own fragment_actions ε buffer lives in a global buffer of the same file. At ~10 MiB of fragment data plus ~2 MiB of actions, each child holds roughly 200K fragments.

Recurse and rebalance. A child whose buffer fills flushes down the same way; a node that outgrows its target size splits, and one that shrinks merges. This is exactly what absorbs the 2D problem: when backfills make fragment entries wider, nodes split to stay near the target size instead of blowing past a cap calibrated in fragment count. With 2–3 levels this comfortably holds billions of fragments.

flowchart TD
    commit["every commit<br/>(append / backfill / delete / compact)"] -->|"appends fragment_actions:<br/>AddFragment / RemoveFragment / AddDataFile /<br/>RemoveDataFile / AddDeletionFile ..."| ROOT

    subgraph ROOT["root node = manifest (protobuf, ~10 MiB)"]
        direction TB
        rmeta["table metadata<br/>(schema, config, indexes, ...)"]
        rfrags["fragment list / child refs<br/>~100K fragments ≈ 8 MiB"]
        rbuf["fragment_actions<br/>(ε buffer, ≈ 2 MiB)"]
    end

    rbuf -. "buffer full → flush actions<br/>routed by fragment id range" .-> C1
    rbuf -.-> C2
    rbuf -.-> cdots["..."]

    subgraph C1["child node = Lance file (~12 MiB)"]
        direction TB
        c1frags["fragment table<br/>~200K fragments ≈ 10 MiB<br/>(tabular, no table-level metadata)"]
        c1buf["fragment_actions<br/>(ε buffer in global buffer, ≈ 2 MiB)"]
    end

    subgraph C2["child node = Lance file"]
        direction TB
        c2frags["fragment table<br/>~200K fragments"]
        c2buf["ε buffer"]
    end

    c1buf -. "same rule recursively:<br/>flush down, split when too big,<br/>merge when too small" .-> G1["Lance file<br/>~200K fragments + ε buffer"]
    c1buf -.-> G2["Lance file<br/>~200K fragments + ε buffer"]
    c1buf -.-> gdots["..."]

Loading

Under this shape, a backfill over 1M fragments becomes a stream of AddDataFile actions riding the buffers: every commit writes only the ~10 MiB root, every buffer overflow rewrites exactly one node, and nothing ever rewrites the world. Readers resolve fragment state by overlaying the buffered actions along the root-to-child path, so point lookups only need the root plus one path down, and lazy open falls out naturally.

This actually fits backfill workflow perfectly, because typically data files are not added all at once. When you generate a new embedding it takes a lot of time and GPU compute, so data files are added continuously through a lot of intermediate commits. So the tree can gradually flush these AddDataFile actions into the child nodes.

On your questions: fragment id is the right tree key IMO, but I would not hardwire "two levels + sealed children" into the format — if we define the node layout (Lance file + ε buffer) and the action set once, depth is just recursion. Node size targets are byte-based by construction (~10 MiB per node), which also answers the byte-vs-count question. And notice how several branches of your "other ways" list — more than two levels, partition by fragment id, manifest delete vectors, background merge — converge to this same shape once children carry buffers instead of an immutability guarantee: delete vectors stop being a special mechanism and become just another action type. A good part of your prototype should carry over directly; the main changes are the child file format and giving every level its own ε buffer.