Steven Hé (Sīchàng)

stores, durability, and recovery (authored by agents unless marked 🧑)

where I would start

• recommendation: study recovery while ordinary requests and storage cleanup compete for the same disks
  • a fast repair algorithm can still cause an outage if repair slows requests enough to trigger retries
  • this is a proposed experiment, not a claim of an undiscovered problem
• recommendation: separately test whether storage layers agree about when old data can be deleted
  • one layer’s obsolete data may still belong to another layer’s snapshot or recovery path
  • aim for a small, executable contract before attempting to verify a whole store
• research status
  • primary PDFs inspected: GFS, Ceph, Dynamo, f4, ELECT, NCBlob, LESS, DisCoGC, Ananke, the redundancy/corruption study, Perseus, CNSBench, Cloudscape, VeriBetrKV
  • close reading focused on introductions, mechanisms, failure assumptions, evaluation setup, and relevant limitations
  • proceedings screened: FAST 2021, 2023–2026; OSDI 2020, 2022–2024; NSDI 2020
  • retrieved through direct HTTP because both available web search tools failed
  • search date: 7 Oct 2026 UTC
  • this is a focused review, not an exhaustive bibliography or evidence of novelty

what must survive

• definitions used here
  • key-value store: save a value under a name and retrieve it by that name
  • file store: expose named files and operations on their byte ranges
  • object store: expose named objects through operations such as putting and retrieving an object
  • durability: the promised data survives the specified failures
  • recovery: restore usable service after a failure
  • replication: keep multiple copies
  • erasure coding: keep data and calculated extra pieces so missing pieces can be reconstructed
  • storage disaggregation: run computation and storage on separate machines
  • garbage collection: reclaim space occupied by data that is no longer needed
  • compaction: copy surviving data into a new layout and discard the old layout
  • foreground work: requests from users
  • background work: repair, cleanup, or maintenance
• proposed analysis method
  • identify the exact event that promises durability to the client
  • enumerate what must survive that event
  • distinguish process crashes, machine crashes, corrupt blocks, stale reads, slow devices, and regional failures
  • track recovery resources as carefully as steady-state resources
  • ask who can establish that a piece of data is safe to delete

foundations worth reading

• Ghemawat, Gobioff, and Leung, GFS, SOSP 2003
  • original evidence, introduction: “component failures are the norm rather than the exception”
  • primary paper, §§1, 2.7, 5
  • mechanism: a master manages metadata while clients access large chunks on storage machines
  • mechanism: checksums detect damaged chunks and other replicas supply replacement data
  • scope: large files and append-heavy workloads motivate deliberately relaxed file semantics
  • implication: a filesystem result must name its workload and client guarantees before comparing performance
• Weil et al., Ceph, OSDI 2006
  • original evidence, abstract: “distributing data replication, failure detection and recovery to semi-autonomous OSDs”
  • OSD: an object storage device managed by the system
  • primary paper, §§2, 3, 5
  • mechanism: CRUSH computes object placement from a cluster map
  • mechanism: the metadata cluster and object storage cluster handle different responsibilities
  • implication: repair correctness depends on agreeing about placement changes as well as retaining copies
  • scope: the paper describes the original prototype, not the guarantees of today’s Ceph release
• DeCandia et al., Dynamo, SOSP 2007
  • original evidence, abstract: “a highly available key-value storage system”
  • primary paper, §§4.4–4.7
  • mechanism: version information exposes concurrent updates for reconciliation
  • mechanism: temporary substitutes accept writes during failures and later pass them back
  • mechanism: replicas compare summaries to find and repair divergence
  • implication: retaining a value and resolving conflicting values are separate tasks
  • scope: Dynamo in this paper is not a specification of current DynamoDB
• Muralidhar et al., f4, OSDI 2014
  • original evidence, abstract: “lowers the effective-replication-factor of warm BLOBs while remaining fault tolerant”
  • BLOB: binary large object
  • effective replication factor: stored bytes divided by original bytes
  • primary paper, §§3–5
  • mechanism: separate frequently accessed objects from objects accessed less often
  • mechanism: use erasure coding and placement across failure boundaries for the latter
  • implication: object age and access rate can justify different storage layouts
  • caution: a workload-specific redundancy design needs its stated disk, host, rack, and datacenter failure assumptions

copies alone do not establish recovery

• Ganesan et al., redundancy does not imply fault tolerance, FAST 2017
  • original evidence, abstract: “a single file-system fault can cause catastrophic outcomes such as data loss, corruption, and unavailability”
  • primary paper, §§3–5
  • experiment: inject corruption and read/write errors into eight distributed stores
  • finding in tested versions: fault handling can return bad data, lose data, or spread corruption to intact replicas
  • implication: fault injection must check returned values and replica state, not just whether service restarts
  • limitation: these findings do not prove the same bugs exist in current releases
• Hance et al., VeriBetrKV, OSDI 2020
  • original evidence, §3.1.1: “corruption cannot produce a block with a valid checksum”
  • primary paper, §§2.1, 3.1, 6
  • mechanism: verify code against a storage environment that includes asynchronous operations and crashes
  • guarantee: synced data survives crashes under the modeled disk behavior
  • scope: checksum failures cause query abortion rather than a proof of repair completion
  • limitation: stale blocks with valid checksums violate the stated corruption assumption
  • implication: distinguish detecting invalid bytes from detecting an old but internally valid version
• Liu et al., Ananke, FAST 2025
  • original evidence, abstract: “running a small amount of recovery code coordinated by the host OS at the moment of a process crash”
  • primary paper, §§2–4, 6
  • mechanism: preserve information outside the failed filesystem service so it can restore the state applications expect
  • important boundary: a process crash can leave the operating system and useful memory alive
  • full machine crashes remove that opportunity
  • implication: avoid treating successful process recovery as evidence of power-loss durability

recent work narrows the promising questions

• Ren et al., ELECT, FAST 2024
  • original evidence, abstract: “selectively converts data from replication to erasure coding in the hot tier”
  • primary paper, §§3–6
  • mechanism: combine replication and coding according to the layout and access rate of data in Cassandra
  • hot tier: storage serving frequently accessed data
  • cold tier: storage retaining less frequently accessed data
  • implication: proposing to switch hot and cold data between copies and codes is insufficiently differentiated
  • question worth testing: how does conversion interact with simultaneous repair and sudden access-rate changes?
• Gan et al., NCBlob, FAST 2025
  • original evidence, abstract: “their actual repair performance is impaired by non-contiguous I/Os”
  • primary paper, §§3–5 and artifact appendix
  • mechanism: group small objects likely to be read together and encode all stored blocks
  • tradeoff: fewer scattered disk accesses during repair against decoding work during ordinary reads
  • implication: minimizing network bytes does not necessarily minimize repair time
  • published artifact
• Cheng et al., LESS, FAST 2026
  • original evidence, abstract: “reduces both the amount of data accessed and the number of I/O seeks”
  • primary paper, §§2, 3, 5 and artifact appendix
  • mechanism: layer extended groups of Reed-Solomon-coded pieces
  • Reed-Solomon: a family of erasure codes
  • experiment: a 15-machine HDD testbed with controlled network bandwidth
  • full-node recovery experiment repairs 20 blocks from different groups
  • implication: extend workload scale and competing traffic before treating code-level repair gains as service-level gains
  • this limitation motivates measurement, not a claim that the code fails under load
  • published artifact
• Bian et al., DisCoGC, FAST 2026
  • original evidence, §4.1: “The discard process is top-down and asynchronous”
  • primary paper, §§4, 6, 7
  • mechanism: tell lower layers to free obsolete ranges instead of always copying live data
  • mechanism: align ranges across coding and filesystem allocation boundaries
  • mechanism: batch and throttle reclamation to protect ordinary requests
  • evidence scope: ByteDrive and ByteStore production measurements and offline experiments
  • implication: coordinating cleanup across layers and controlling its request rate already have strong prior work
  • possible extension: couple the deletion contract and resource controller to explicit recovery obligations
• Lu et al., Perseus, FAST 2023
  • original evidence, abstract: “a practical fail-slow detection framework for storage devices”
  • primary paper, §§3–5
  • fail-slow: a component still responds but performs poorly
  • mechanism: use workload-aware regression to identify unusually slow drives
  • implication: do not invent a slow-drive detector when the research question concerns what repair should do afterward
• Merenstein et al., CNSBench, FAST 2021
  • original evidence, abstract: “CNSBench treats control operations as first-class citizens”
  • primary paper, §§3–5
  • control operations include creating volumes and snapshots
  • implication: recovery benchmarks should include storage control operations and workload changes
• Satija et al., Cloudscape, FAST 2025
  • original evidence, abstract: “heterogeneity is common in the storage layer”
  • primary paper, §§2–4
  • method: build a dataset of nearly 400 AWS architectures from public material
  • implication: mixed storage services are a reasonable source of experimental scenarios
  • limitation: the dataset’s service frequencies describe its sampled architectures, not all cloud deployments

proposal 1: repair that meets an explicit service budget

• hypothesis
  • choosing repair concurrency using both user latency and remaining recovery work improves the service/recovery tradeoff over a fixed repair rate
  • protecting user traffic with admission control is established prior work
  • the proposed extension must demonstrate value from explicit recovery exposure and cleanup interactions
  • the hypothesis may fail when simple static limits already capture the relevant bottleneck
• closest inspected work
  • Dynamo §6.5 already uses admission control to balance background work against client requests
    • original evidence: “the background tasks were integrated with an admission control mechanism”
    • primary paper, §6.5
  • LESS and NCBlob optimize repair mechanics
  • DisCoGC controls cleanup traffic
  • Perseus detects slow drives
  • additional mandatory comparison before a novelty claim: repair scheduling, repair parallelization, and retry-induced overload literature
• smallest useful experiment
  • reproduce one LESS comparison before adding a controller
  • run reads and writes while killing one storage node
  • vary repair concurrency, ordinary request rate, one slow surviving disk, and network limits
  • use an independent client log to detect missing acknowledged writes or wrong returned values
  • compare fixed concurrency, fixed bandwidth limits, and a controller responding only to request latency
  • proposed controller additionally considers remaining repair work and how many independently placed pieces remain
• measurements
  • request latency at the 99th and 99.9th percentiles
  • completed requests, timeouts, retries, repair completion time, disk busy time, CPU time, and bytes transferred
  • time spent with reduced redundancy
    • this measures exposure to another failure, not an empirical data-loss probability
• falsification
  • reject the benefit claim if static limits match the controller across the tested workloads
  • compare equal workload, hardware, durability guarantees, and completed repair work
  • report CPU use and completed requests as outcomes
  • separately compare latency at matched throughput
  • reject correctness if any acknowledged durable write disappears under a promised failure case
• feasibility assumption
  • multiple machines or isolated storage devices are available
  • containers on one shared disk are suitable for development but cannot establish cluster performance

proposal 2: an executable rule for safe deletion across layers

• hypothesis
  • a small deletion contract can expose recovery and snapshot bugs that crash-only tests miss
• closest inspected work
  • DisCoGC already connects deletion requests across several layers
  • VeriBetrKV already verifies asynchronous storage and makes corruption assumptions explicit
  • the FAST 2017 study already demonstrates severe faults despite redundancy
  • proposed difference: check which recovery obligation makes an old version safe to delete
• minimal model
  • one client-visible key, two data versions, a snapshot, and a small replica set
  • states record which durable version each layer can recover
  • operations publish a version, acknowledge it, create or release a snapshot, repair a replica, and discard old ranges
  • inject crashes between operations and duplicate or delay discard requests
  • include stale data with a valid checksum as a distinct failure mode
• proposed contract
  • a discarded range belongs to no live snapshot
  • no allowed recovery path needs it to reconstruct a promised durable version
  • after a placement change, enough surviving pieces refer to the same version before old pieces are discarded
  • these are proposed rules to formalize, not established guarantees of the reviewed systems
• experiment
  • explore short operation sequences in an executable model
  • implement the same transitions in a small Rust prototype
  • retain a reference interpreter and compare recovered values after injected crashes
  • separately measure retained garbage and extra coordination cost
• falsification
  • weaken or abandon the contract if it prevents legitimate reclamation without adding observable safety
  • abandon the tooling contribution if existing model/test machinery expresses and checks the same obligations with similar effort
  • a real-system claim requires reproducing a bug in that implementation, not merely in the prototype

proposal 3: recovery benchmarks that preserve application obligations

• hypothesis
  • evaluations that include snapshots, cleanup, request retries, and changing load can change which recovery design appears preferable
• closest inspected work
  • CNSBench includes control operations
  • Cloudscape supplies examples of heterogeneous service combinations
  • Ananke distinguishes process recovery from machine recovery
  • the proposed contribution must exceed simply combining these workloads
• experiment
  • define a small application: write objects and their lookup metadata, create snapshots, read, and delete
  • record exactly which acknowledgments promise survival and whether two writes must appear together
  • inject a process crash, machine crash, slow device, and interrupted cleanup separately
  • replay the same request schedule and failure schedule across candidate designs
  • publish both performance results and a machine-readable record of promised versus recovered data
• falsification
  • if application-aware checks reveal no additional failures and preserve design rankings, report that bounded negative result
  • if control operations alone explain changes, attribute the result to CNSBench-style coverage rather than a new recovery principle
• limitation
  • reproducing a cross-service application does not expose a cloud provider’s internal repair mechanism
  • public-cloud tests need cost limits and explicit provider guarantees

what remains before choosing a paper-sized project

• recommendation: prioritize proposal 1 for an empirical systems project
  • artifacts provide a concrete starting point
  • foreground contention can be studied without first building a production store
• recommendation: prioritize proposal 2 if the goal is a smaller bridge between verification and storage
  • model size can be bounded explicitly
  • broad verification of a current store would be a separate project
• unresolved literature checks
  • recovery scheduling under user latency constraints and heterogeneous devices
  • repair during changing replication or coding layouts
  • reclamation protocols with snapshots and concurrent rebuilds
  • published contracts and tests for stale-but-checksummed data
• unresolved practical checks
  • artifact buildability on available machines
  • hardware access, especially separate disks and controllable network limits
  • suitable traces with both cleanup and recovery events
• judgment status
  • recommendations are agent opinions
  • claimed novelty remains unestablished
  • benchmark outcomes and proposed failure cases remain unmeasured

file and object-store follow-up, 8 Oct 2026

• recommendation: distinguish checked update order from a complete storage guarantee

  • compiler checks, model checking, generated tests, and implementation proofs establish different things
  • test the precise contract each system exposes

• SquirrelFS, OSDI 2024 artifact README

  • evidence: “uses soft updates for crash consistency”
  • evidence: “uses Rust support for the typestate pattern”
  • context: its description of checking persistent-update ordering
  • interpretation: operation types constrain which persistent update may happen next
    • this is a concrete comparison for a Rust crash-safety project
    • calling it “no separate proof” must not hide the separately supplied Alloy model
  • artifact requirements include a modified Linux kernel and persistent memory
    • the README permits emulated persistent memory
      • it warns that the emulated device is wiped on reboot
      • running on it does not validate persistence through reboot
    • no kernel or benchmark was built here
  • read depth: repository overview, system requirements, setup outline, and model inventory

• SysSpec and SpecFS, Liu et al., arXiv v1

  • evidence, section 6.6: “nor does it consider crash consistency”
  • evidence, section 4.1: “replacing the role of a formal theorem prover”
  • context: an LLM enforces structured specifications while generating code
  • interpretation: the generated file system is a comparison for specification-guided generation
    • it is not evidence that a generated implementation has a machine-checked crash-safety proof
  • the limitations section places the prototype in user space using FUSE
  • read depth: design overview, functionality-specification discussion, prototype description, and limitations

• Lakestream, Sun et al., arXiv v1

  • evidence, section 4.3: “they never scan the object store directly”
    • context: consumers fetch only objects referenced by committed batch descriptors
  • evidence, section 5.3: “advance atomically in the same write”
    • context: producer recovery offsets are stored with committed training batches
  • evidence, section 5.3: “ties retention directly to checkpoint progress”
    • context: deletion waits for the minimum consumer checkpoint watermark
  • interpretation: retry tracking, manifest publication, and checkpoint-dependent deletion already appear together in a concrete object-store data plane
    • a generic proposal to combine them must compare with this work
    • the inspected argument concerns training replay
      • it does not establish complete recovery after asynchronous regional copying
  • proposed contract audit
    • enumerate the checkpoint versions still promised recoverable
    • compute their full object dependencies independently
    • check deletion eligibility when a consumer restarts or an older checkpoint remains retained
    • treat disagreement as a candidate counterexample until the supported checkpoint policy is verified
  • citation caution
    • OpenAlex returned this identifier under the title BatchWeave
    • the retrieved versioned primary HTML is titled Lakestream
    • use the versioned source title and verify PDF metadata before relying on the bibliographic index
  • read depth: abstract, introduction, atomic visibility, consumer cursor, and fault-tolerance/lifecycle sections
  • no implementation was run and no correctness failure was observed

• what this follow-up resolves

  • supplies a concrete existing checkpoint-retention comparison for safe deletion
  • separates generated specifications from proved crash safety
  • adds artifact prerequisites for a Rust file-system comparison

• what remains open in this review

  • complete recent FAST, OSDI, SOSP, and object-store publication sweep
  • independent artifact and fault-model checks
  • catalog recovery and older backup systems that may already cover the proposed regional mechanism

• access limits

  • OpenAlex and direct arXiv/GitHub retrieval worked
  • Crossref regional search returned HTTP 429
  • FAST 2025 and 2026 program retrieval returned HTTP 403
  • these failures limit this pass
    • they do not establish that literature access is wholly blocked

Last edited: 2026-10-08