LazyBarrier: Reconstructing Android IO Stack for Barrier-Enabled Flash Storage

Yuanyi Zhang, Heng Zhang, Wenbin Cao, Xing He, Daejun Park, Jinyoung Choi and 1 other

Apps must write data to storage in a careful order so a phone that crashes mid-write does not corrupt its files, and the classic way to enforce that — a synchronous flush — is so slow that Android disables the storage barrier entirely by default, gambling with your data; a recent alternative issues lightweight barrier commands instead, but it fires one per thread and collapses under many threads; this work rebuilds the Android storage stack to issue those barriers lazily, only when the order truly demands it, for up to 73 percent faster ordered writes.

The argument in one glance

Problem

Preserving write order safely is slow, so Android skips it

Applications must control the order in which writes reach storage so a crash mid-write leaves the file system consistent, not corrupt. The classic way to enforce this is a synchronous flush (fsync), which pushes all pending writes to the device and waits for them to be durable. That is safe but slow, so Android phones disable the storage barrier by default — the No-Barrier mode — to speed fsync up, at the cost of the ordering guarantee it was meant to provide.
What people did

Restore ordering cheaply with barrier write commands

A recent approach, the Barrier-Enabled IO Stack (BEIOS), separates the goal of ordering from the cost of flushing. Instead of a full flush, it issues lightweight barrier write commands to the flash device, which promise to make writes durable in the requested order without the caller waiting for a flush. This restores order-preserving semantics at a fraction of fsync's cost.
Why it fell short

One barrier per thread means it collapses under many threads

The barrier-enabled stack issues a barrier write command for each ordered write, per thread. The paper's evaluation shows that this makes the number of barrier commands grow linearly with the number of threads, so on a multi-core phone running many threads the device is swamped with barrier commands and performance degrades badly. The lightweight per-barrier cost is undone by issuing far too many of them.
This paper's idea

Issue barriers lazily, only when the order truly requires it

LazyBarrier reconstructs the Android IO stack around four pieces: an order-preserving write (OPW) model based on finite automata that defines the legal state transitions of an ordered write; a Lazy Issue algorithm that defers and coalesces barrier commands so their count stops growing with threads; a modified flash-friendly file system (F2FS) that speaks the OPW protocol; and Barrier Scheduling that keeps the order intact across the multi-queue block layer. Together these cut the barrier commands issued, improving ordered-write performance by up to 73 percent over the prior stack.

Why this problem is worth solving

To see why ordering is both essential and expensive, start with what it protects and how it is traditionally bought.

File systems and applications rely on writes reaching persistent storage in a controlled order to survive crashes. The canonical example is that a piece of data must be durable before the metadata or commit record that points to it — otherwise a power failure in between leaves a pointer to garbage, and the file system is corrupt. So the storage stack must be able to say “make sure A is durable before B.” The blunt way to do this is fsync: a synchronous flush that forces all pending writes to the device’s persistent media and blocks the caller until they are safely down. This works, but it is costly, because flash devices keep an internal write-back cache for speed, and a flush drains that cache and stalls the caller while it does — throwing away the very buffering that makes the device fast, and idling the application. On smartphones, where storage performance is felt directly in app responsiveness, this cost is severe enough that Android runs in No-Barrier mode by default: it disables the storage barrier so fsync returns faster, accepting the risk that on a crash, writes may not actually be ordered or durable as promised. In other words, the default trades away the safety guarantee to get acceptable speed — which is exactly the compromise a better ordering mechanism could avoid.

The escape is to notice that ordering and durability are not the same requirement.

Most of the time an application does not need its data to be durable this instant; it needs it to become durable in the right order relative to other writes. Those are different things, and conflating them is what makes fsync so expensive — it forces immediate durability (a flush and a wait) just to get ordering. The Barrier-Enabled IO Stack exploits the difference: modern flash controllers can support a barrier write command, a primitive that tells the device to persist writes in a specified order without the caller having to wait for a flush to complete. This decouples ordering from durability, delivering crash-consistent ordering at a fraction of fsync’s cost, and a whole IO stack — file system, block layer, device — can be built around it. But there is a scaling flaw. The barrier-enabled stack issues one barrier command per ordered write in each thread, so as the number of threads rises, the number of barrier commands issued rises linearly with it. On a modern multi-core phone running many threads, the device is flooded with barrier commands, and the per-command overhead, small individually, adds up until performance collapses. The right primitive is being used, but far too eagerly.

What people did before, and where it broke

fsync (synchronous flush). Force all pending writes durable and wait, which also orders them. Where it broke. Draining the device’s write cache and stalling the caller is slow, so on latency-sensitive phones it is a major cost.
No-Barrier mode (Android default). Disable the storage barrier so fsync returns faster. Where it broke. It gives up the ordering and durability guarantee fsync was meant to enforce, so a crash can corrupt or lose data — trading safety for speed.
Barrier-Enabled IO Stack (BEIOS). Use lightweight barrier write commands to enforce ordering without a full flush, decoupling order from durability. Where it broke. It issues a barrier per ordered write per thread, so barrier commands grow linearly with the thread count and multi-threaded performance degrades badly.
The gap. No stack delivered cheap order-preserving writes that also scaled with many threads: something that keeps the barrier-write idea but stops issuing a barrier for every ordered write in every thread. Deferring and coalescing barriers so their count no longer scales with threads is what LazyBarrier provides.

How LazyBarrier works

From one barrier per thread to barriers issued only when required

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Defer the expensive operation and pay it only when it is truly forced. The barrier-enabled stack pays for a barrier on every ordered write in every thread, but most of those barriers are not yet required; LazyBarrier withholds each one until the ordering model shows the constraint is actually pending, so it issues far fewer. Deferring a costly operation until a runtime condition proves it is actually needed, rather than eagerly paying for it up front and watching the overhead swamp the benefit, is the same discipline the automatic-parallelism work covered elsewhere on this site follows, refusing to spawn parallel work until a signal shows it has been earned, because eager spawning per unit would drown the gains in overhead.

Separate ordering from durability, two things that had been conflated. fsync forces immediate durability just to achieve ordering, but an application usually needs only the order in which writes become durable — so LazyBarrier pulls the two apart and enforces order with a cheap barrier while leaving durability to happen in the background. Untangling two requirements that a single heavy mechanism had bundled together, so each can be handled on its own far cheaper terms, is exactly the move the resize-scheduling work covered elsewhere on this site makes, separating the concerns that were fused into one costly decision so neither has to be paid at the other’s price.

Coalesce many identical per-thread costs into far fewer shared ones. The linear blowup comes from each of many threads independently issuing its own barrier for the same kind of ordering need; LazyBarrier collapses those redundant per-thread barriers, issuing shared ones that serve many threads at once. Recognizing that many instances are independently paying for the same thing and collapsing them into one shared payment, so the cost stops scaling with the number of instances, is the same instinct the circuit-deduplication work covered elsewhere on this site follows, replacing many identical copies with a single shared one to escape a cost that grew with their number.

Following ordered writes from many threads through LazyBarrier

Ordering writes from many threads without flooding the device

Tracing multi-threaded ordered writes shows lazy issuing and scheduling at work.

Step 1 of 5

Many threads each need ordered writes

On a multi-core Android phone, many application threads each require their writes to reach flash storage in order, so that a crash leaves the file system consistent. Each thread has its own stream of ordering constraints.

Ordering, not immediate durability, is what most of these writes actually need.

Why it works

Fewer barriers stops the linear blowup. The barrier-enabled stack issues one barrier per ordered write per thread → so the barrier count grows linearly with threads and floods the device → but issuing barriers lazily and coalescing them keeps the count from scaling with thread count.
Ordering is cheaper than durability. Applications usually need writes ordered, not durable this instant → so waiting for a full flush is unnecessary work → so a lightweight barrier that only enforces order is far cheaper than fsync.
The model pins down when a barrier is required. A finite-automaton model tracks exactly when an ordering constraint is pending → so a barrier can be withheld until the moment it is truly forced → so no barrier is issued that the order does not actually demand.
Scheduling preserves order under parallelism. The multi-queue block layer can reorder requests across its parallel queues → but scheduling the barriers across those queues preserves the intended order → so device parallelism speeds writes without corrupting consistency.
Less overhead keeps the pipeline busy. Fewer barrier commands mean less device-side ordering overhead → so the storage pipeline stalls less and stays busier → so ordered-write performance rises up to 73 percent on phones and 19 percent on servers over the prior stack.

What it costs (trade-offs and scope)

It is a deep stack reconstruction. LazyBarrier changes the Android IO stack across layers — a modified flash-friendly file system, a new write model, a lazy-issue algorithm, and barrier scheduling in the block layer — so it is intrusive, not a drop-in tweak.
It depends on hardware barrier support. The approach relies on the flash device supporting barrier write commands to enforce order without flushing; storage lacking that primitive cannot use it.
Laziness must not violate correctness. Deferring barriers is only safe if the order-preserving-write model captures every real ordering constraint, so the finite-automaton model carries the correctness burden and a missed constraint would risk inconsistency.
The gains are workload-dependent. The reported improvements — 73 percent on a synthetic benchmark, 29 percent in real applications, and 19 percent in a server workload — vary with how ordering-heavy and how multi-threaded the workload is; single-threaded or ordering-light workloads gain less.
It optimizes ordering, not on-demand durability. Like the barrier approach it builds on, LazyBarrier speeds order-preserving writes; a workload that genuinely needs data durable immediately still pays for a real flush.
The internal specifics are in the full paper. The exact finite-automaton states, the Lazy Issue algorithm, and the barrier-scheduling details are described in the paper and are not reproduced here.

The evaluation

Three ways to preserve write order on flash storage

Property	fsync / No-Barrier	Barrier-Enabled IO Stack
How ordering is enforced	A full flush and wait (or nothing)	A barrier command per ordered write
Cost of ordering	High, or unsafe if disabled	Lightweight per barrier
Scaling with thread count	Serializes
Ordered-write speed versus BEIOS	Slow	Baseline

Three ways to preserve write order on flash storage. fsync flushes and waits (or Android disables the barrier for speed, sacrificing safety); the Barrier-Enabled IO Stack orders cheaply with barrier commands but issues one per thread, so its barrier count grows linearly and collapses under many threads. LazyBarrier keeps the barrier idea but issues barriers lazily and coalesced, guided by a finite-automaton order-preserving-write model and scheduled across the multi-queue block layer — improving ordered-write performance by up to 73 percent on the FIO benchmark, 29 percent in real Android applications, and 19 percent in a server dbench workload over the barrier-enabled stack. (This explainer is drawn from the paper's abstract and standard background on storage ordering; the full text, including the model and algorithm details, was not available.)Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

LazyBarrier is a well-motivated storage-systems result. It starts from a real gap: the safe way to order writes (fsync) is so slow that Android disables the barrier by default, and the efficient barrier-command alternative scales badly because it issues one barrier per thread, so its overhead grows linearly. LazyBarrier keeps the barrier-command idea but makes it lazy — deferring and coalescing barriers so their count stops growing with threads — backed by a finite-automaton order-preserving-write model, a modified flash file system, and barrier scheduling for the multi-queue block layer, for reported improvements of 73 percent on a synthetic benchmark, 29 percent in real apps, and 19 percent on servers over the prior stack. Read it with its scope. It is a deep, intrusive change across the IO stack and depends on flash hardware that supports barrier commands. Its laziness is only correct if the ordering model captures every real constraint, so the model bears the correctness burden. The gains depend on the workload being ordering-heavy and multi-threaded, and it optimizes ordering rather than immediate durability. Importantly, this page is written from the paper’s abstract and standard background on write ordering and barriers, because the full text was behind an inaccessible paywall; the roles of the four components and the reported numbers come from the abstract, but the exact finite-automaton model, the Lazy Issue algorithm, and the barrier-scheduling details are in the paper and are not reproduced or invented here. The durable lesson is that when a system pays for a guarantee on every operation, the win often lies not in a cheaper per-operation mechanism but in issuing it far less often — deferring, coalescing, and only paying when correctness truly demands.

Background

Why the storage stack keeps getting rebuilt around what the device can really do

It helps to see LazyBarrier as part of a long effort to reshape the operating system’s storage stack around the true capabilities and costs of the underlying flash. For years the stack inherited assumptions from spinning disks — that ordering means flushing, that durability and order come together — and flash quietly broke them, offering primitives like barrier commands that separate the two, and demanding new software to use them well. The work on managing multi-tenant flash storage covered elsewhere on this site pushes on the same seam from a different direction, rebuilding how virtual flash devices are shared and scheduled to match what the hardware can actually deliver, rather than accepting the legacy abstractions. The broad lesson is that the storage stack is not a fixed edifice but something repeatedly reconstructed as the device beneath it changes: the biggest wins come from noticing where the old abstractions overpay — a full flush where only ordering was needed, a barrier per thread where a few would do — and redesigning the layers so the software asks the hardware for exactly what it needs and no more.

If you remember only three things

1. Applications need their writes to reach storage in a controlled order so a crash mid-write leaves the file system consistent (data durable before the metadata pointing to it). The classic mechanism, fsync, forces a full device-cache flush and waits — safe but slow, so Android runs in No-Barrier mode by default, disabling the barrier for speed and sacrificing the guarantee. The Barrier-Enabled IO Stack (BEIOS) restores cheap ordering by decoupling it from durability: rather than flush, it issues lightweight barrier write commands that make the device persist writes in the requested order without waiting. But BEIOS issues one barrier per ordered write per thread, so the barrier count grows linearly with the thread count and multi-threaded performance collapses.
2. LazyBarrier reconstructs the Android IO stack around four components: an order-preserving write (OPW) model based on finite automata that defines the legal state transitions of an ordered write and pins down exactly when an ordering constraint is pending; a Lazy Issue algorithm that defers and coalesces barrier commands so their number stops growing with the thread count; a modified flash-friendly file system (F2FS) that supports OPW end to end; and Barrier Scheduling that preserves ordering across the multi-queue block layer, whose parallel queues can reorder requests. The core insight is to keep the barrier-command idea but issue barriers far less often — only when correctness truly forces it.
3. On Android smartphones, LazyBarrier improves order-preserving-write performance over BEIOS by 73 percent under the FIO benchmark and 29 percent in real applications, and it outperforms BEIOS by 19 percent in a dbench server workload. Its scope: it is a deep, intrusive stack change that depends on hardware barrier support; its laziness is correct only if the ordering model captures every real constraint; the gains depend on the workload being ordering-heavy and multi-threaded; and it optimizes ordering, not on-demand durability. This explainer is written from the paper's abstract and standard storage-ordering background, because the full text was unavailable — the exact model, algorithm, and scheduling details are in the paper and are not reproduced here.

Check yourself

Check your understanding

1. Why does Android disable the storage barrier by default, and what does that cost?
2. What is the key idea behind barrier write commands, and where did the Barrier-Enabled IO Stack fall short?
3. How does LazyBarrier fix the multi-threaded scaling problem?
4. Which statement best reflects LazyBarrier's results and scope?

Sources

The paper is “LazyBarrier: Reconstructing Android IO Stack for Barrier-Enabled Flash Storage” by Yuanyi Zhang, Heng Zhang, Wenbin Cao, Xing He, Daejun Park, Jinyoung Choi, and colleagues, published at ASPLOS 2024, DOI 10.1145/3620665.3640370.

This explainer is marked as a draft because the full text was not accessible: the paper is gold open access (Creative Commons) on the ACM Digital Library, but that page was protected by an anti-bot challenge that blocked automated retrieval, and no arXiv preprint, author-hosted copy, or open repository version could be found. However, a detailed abstract was available, and the account above draws on it together with standard, well-established background on storage-system ordering — crash consistency and the data-before-metadata ordering requirement, fsync and device-cache flushing, Android’s No-Barrier default, the decoupling of ordering from durability via barrier write commands in the Barrier-Enabled IO Stack, the F2FS flash file system, and the Linux multi-queue block layer. The specific claims attributed to the paper come directly from its abstract: that fsync is costly and Android uses No-Barrier by default to speed it up; that the Barrier-Enabled IO Stack provides efficient order-preserving writes via barrier write commands but degrades in multi-threaded scenarios because barrier commands grow linearly with the number of threads; that LazyBarrier introduces an order-preserving write model based on finite automata, a Lazy Issue algorithm that minimizes barrier commands, a modified F2FS, and Barrier Scheduling for the multi-queue block layer; and that it improves order-preserving-write performance over the Barrier-Enabled IO Stack by 73 percent under the FIO benchmark, 29 percent in real applications, and 19 percent in a dbench server workload. The description of how the four components work is a faithful reading of the abstract and the established mechanics of barrier-based storage stacks, but the exact finite-automaton states, the Lazy Issue algorithm, and the barrier-scheduling details are in the full paper and are not reproduced or invented here.