Column-Aligned Erasure Coding for Write-Once Collider Event Stores

Particle physics collaborations keep petabytes of collision records for decades, and they mostly protect them by keeping several full copies. Erasure coding stores the same data far more cheaply. It splits each file into $k$ data pieces and computes $m$ extra "parity" pieces such that any $k$ of the $k+m$ pieces rebuild the original. With $k=6$ and $m=3$, the storage overhead is 50% instead of the 200% of triple copies. The catch is speed. On modern flash storage, a careful audit of Ceph found that Reed-Solomon erasure coding cut throughput by 42.5% and raised latency 12.5-fold compared with triple replication (Exploring Fault-Tolerant Erasure Codes for Scalable All-Flash Array Clusters). Physics analysis clusters are moving to flash, so this penalty is the main reason not to use coding there.

This proposal argues that most of that penalty comes from access patterns collider analyses do not have. Collider event data is written once, sealed, and never updated in place. Analyses read it column by column: a search such as BABAR's $B \to K\nu\bar\nu$ pass reads a few dozen kinematic variables out of hundreds stored per event. We propose an erasure-coded layout in which each data piece holds whole, sealed column chunks, and parity is computed only after a file is closed. A read of one variable then touches one data piece on one node, in full, with no parity work. We will test whether this layout recovers replication-level throughput and latency on flash for realistic collider analysis passes while keeping erasure coding's storage savings, and we will find where it fails.

Core Claim

Koh et al. attribute the flash penalty to three things. Small partial writes force read-modify-write of parity, which caused 387% more reads and 151% more writes. Each I/O incurs user-space processing overhead, with 234% more context switches. Objects pay an initialization cost when chunks are first allocated. Our claim is that for sealed, columnar, write-once data, the first and third causes disappear by construction. The second shrinks because a request maps to one large contiguous piece rather than being split across a stripe. The specific, falsifiable prediction is this: in normal operation, a branch-aligned layout with $(k,m)=(6,3)$ comes within 15% of triple-replication throughput and within 2× of its tail latency on a BABAR-style analysis replay. Stock Ceph RS(6,3) on the same hardware and workload should reproduce a gap of roughly the size Koh reports.

What is new here is not erasure coding for science grids. The novelty lies in exploiting the write-once, column-subset structure of collider data to remove the online cost, and in measuring this on physics workloads rather than generic benchmarks.

Relation to Prior Work

Three papers motivate the storage side. Koh et al. measured the flash penalty on 52 SSDs using synthetic and SPEC SFS 2014 enterprise workloads. They suggested mitigations such as dynamic stripe sizing and user-mode I/O, but did not test them on scientific data. We take their measurements as the null hypothesis to beat. An IDA-Based Parallel Storage Scheme in the Scientific Data Grid put information dispersal into the iRODS data-grid middleware with high-energy physics explicitly in mind. It showed better availability than replication at equal redundancy (0.968 vs 0.875) and faster parallel downloads (50 s vs 180 s for a 160 MB file). However, it tested only whole-file sequential downloads of 40–160 MB synthetic files. We study partial, column-selective reads on real event formats, where whole-file dispersal is exactly the wrong unit.

Two papers supply design precedent. HYDRAstor assigned erasure-coding resilience per block rather than per volume. Yiu et al. coded whole objects in an in-memory key-value store instead of slicing them. Our "whole column chunk per data piece" layout is the columnar-analysis analogue of whole-object coding. Unlike either, it is tuned to a read pattern defined by physics variable selection.

On the physics side, Search for the rare decay B -> K nu nu-bar defines the workload we replay. It covers 459 million $B\bar B$ pairs, a tag-side reconstruction, and a 20-tree bagged decision-tree ensemble over up to 38 variables. Together these fix how many columns a realistic pass touches. Aspen Open Jets supplies an openly available, real columnar collider dataset of about 178 million jets for experiments we can release. AI Surrogate Model for Distributed Computing Workloads supplies over two million real ATLAS analysis-data job records. We use their arrival and size statistics to drive concurrent load. That paper models scheduling metadata only and says nothing about storage.

Research Program

We will build a thin placement layer on top of Ceph's object store. Collider files in columnar format, such as ROOT-style trees, are already divided into compressed column chunks. On file close, the layer packs whole chunks into $k$ data objects, balancing their sizes, and never splits a chunk. It then computes $m$ parity objects with a standard systematic Reed-Solomon code, so the original data remains readable directly without decoding. A small index maps each (file, column, event range) to its data object and offset.

Writes during production go to a replicated landing area and are encoded in bulk once sealed. This turns every coding operation into a large sequential write and removes in-place parity updates. Reads in normal operation go straight to the data object. Degraded reads, where a data object is lost, fetch any $k$ surviving objects and rebuild. Under this layout each read moves one chunk of size $c$ in normal mode and about $kc$ in degraded mode. The degraded cost is the same as standard coding, so we do not claim any advantage in degraded mode.

The analysis program has three parts. First, we break down where Koh's overhead goes on our workload: context switches, CPU cycles, and read and write amplification, measured with the same counters they report. Second, we sweep the fraction of columns a pass reads, from one variable up to whole events. This identifies the crossover where whole-event reads make alignment irrelevant and simple striping's parallelism wins, as in Lu et al.'s parallel-download regime. Third, we measure behaviour while one and then two storage nodes fail mid-pass, along with rebuild time.

Baselines

The naive reference point is triple replication on the same flash cluster. It is the default practice and the performance ceiling, and it costs 200% overhead. Every scheme will run the identical replayed analysis, on identical hardware, with the same client concurrency and the same page-cache settings. Each configuration gets the same tuning budget: a fixed grid over object size and client thread count, with the best setting reported.

The strongest existing method is stock Ceph erasure coding with RS(6,3), configured as in Koh et al. For it, the file reports a 42.5% throughput drop and 12.5× latency on synthetic workloads, and a 61% throughput drop with 7.5× latency on SPEC SFS 2014, both relative to triple replication (Koh et al.). We will rerun it on our collider workload rather than borrow those numbers. Beating it means closing at least two-thirds of whichever gap we observe at equal storage overhead.

A tuned version of the same baseline is the fairest competitor. It uses stock RS(6,3) with the stripe unit raised to match typical column-chunk size. This is the "dynamic stripe sizing" mitigation Koh et al. propose, done by configuration alone.

Two ablations isolate our ingredients. The first keeps column alignment but encodes on write without a sealed landing area. The second seals before encoding but stripes byte ranges without respecting chunk boundaries. If either ablation matches the full system, that ingredient alone explains the gain.

Why not just…?

Why not just keep replicating, since disks are cheap? At small scale this is the right answer, and we will report the dataset size below which the extra hardware costs less than the engineering. At the scale of BABAR's preserved sample or LHC analysis tiers, the 200% overhead is the dominant capital cost. Edge-storage work found coded placement cut storage cost by 68.58% on average relative to replication (Cost-Effective Data Placement in Edge Storage Systems With Erasure Code). Lu et al. found coding also gave better availability at equal redundancy. The real question is only whether the speed penalty can be avoided, which is what we measure.

Why not just replicate hot data and erasure-code cold data? This is the most serious threat, because tiering by heat is already common, including in hybrid blockchain storage that replicates recent blocks and codes old ones (Xu et al.). It works if the frequently scanned tier is small. Final analysis tuples are small. Reconstructed event data that working groups re-scan for each new selection is not. We will use the ATLAS job records to estimate what fraction of bytes is touched within a month. We will then compare tiering against our layout at equal total storage. If the hot set is a few percent of bytes, tiering wins on simplicity and we will say so. Our layout matters only if the repeatedly scanned set is large.

Why not just put a flash cache in front of an erasure-coded pool? Caching helps repeated passes over the same skim but not first passes or full reprocessing over data larger than the cache. We will replay cache-hostile passes as well as cache-friendly ones. We will report both, with cache size held to the same hardware budget as the replication difference.

Why not just make the analysis jobs tolerate failures, as in coded computing? Coded Elastic Computing protects linear computations against lost workers. That addresses compute preemption, not losing stored data, and collider event loops are already easy to re-queue per event batch. It is complementary and outside our scope.

Proposed Experiments

The testbed mirrors Koh's scale: four storage nodes with about fifty SSDs. We use two datasets. Aspen Open Jets is the openly releasable real collider dataset. The second is a format-faithful BABAR-like event store, sized to the 38-variable $B\to K\nu\bar\nu$ selection, plus wider event records. If access to preserved BABAR files is obtained, the same replay runs on them directly. Concurrency and request sizes are drawn from the ATLAS analysis-job traces. Metrics are aggregate throughput, median and 99th-percentile latency, context switches, CPU cycles, read and write amplification, rebuild time, and dollars per usable terabyte.

The first decisive check reproduces Koh's gap with stock RS(6,3) on our workload. If the gap is absent even for stock coding, the problem does not exist for collider data, which is itself a publishable negative finding. The second check is whether the full layout reaches the stated targets in normal operation and whether both ablations fall short. The third is the column-fraction sweep, which should show the advantage shrinking to zero as passes approach whole-event reads. The fourth is the equal-storage comparison against heat-based tiering. As a correctness check, the selection outputs must be bit-identical across all schemes, including during injected node failures: event counts in the signal region and decision-tree score histograms.