Batching, Pipelining, Vectorization, and Amortization

Ledgerline’s write service receives 6,000 small ledger entries/s. Each durable append group pays a modeled 240 µs setup cost for framing, coordination, and one flush boundary, plus 35 µs of variable CPU and copy work per entry. Every entry must complete within 10 ms of arrival. A proposal changes the fixed batch size from 8 to 64 because the cost per item falls monotonically.

The arithmetic agrees with the first half of the proposal. The decision does not.

For a batch of (n) homogeneous items, the modeled service interval is

[ S(n) = F + nv, ]

where (F) is fixed time per batch, (v) is variable time per item, and (n) is items per batch. Amortized service demand per item is

[ c(n) = v + \frac{F}{n}. ]

At (F=240\ \mu s) and (v=35\ \mu s), (c(1)=275\ \mu s), (c(8)=65\ \mu s), (c(32)=42.5\ \mu s), and (c(64)=38.75\ \mu s). The marginal gain shrinks because (F/n) approaches zero; batching cannot remove (v).

But the oldest item in a count batch waits for the other (n-1) arrivals before service. At a steady 6,000 items/s, that idealized fill wait is ((n-1)/6{,}000) seconds. With deterministic arrivals and no other queueing, a 32-item batch completes its oldest item in about 6.53 ms. A 64-item batch takes about 12.98 ms. The larger batch offers more modeled capacity and violates the stated deadline before variance, scheduling, or storage tails enter the model.

The decision is: how far should fixed cost be amortized before marginal savings are outweighed by fill wait, service tail, memory, fairness, deadline, and recovery cost?

Five mechanisms move different terms

These techniques are related but not interchangeable.

Batching groups several items so they share a fixed operation such as a syscall, frame, transaction, launch, allocation, or lookup. It adds formation wait and retains items together.

Pipelining overlaps different stages for different items or batches. It can improve steady-state throughput without reducing total work. It adds in-flight state and can expose the slowest stage as the cadence.

Parallelism runs independent work simultaneously on multiple resources. It requires the independence and coordination proof developed in Chapter 18.

Vectorization applies one instruction or operator to multiple data elements, often using regular contiguous representation. It can reduce instruction and branch overhead. It is constrained by layout, masks, alignment, memory bandwidth, and exceptional lanes.

Coalescing merges compatible operations or transfers: adjacent writes, acknowledgements, network frames, wakeups, invalidations, or state updates. It is safe only when the combined operation preserves each item’s semantics.

A system can use all five. A columnar query operator may form row batches, pipeline scan/decode/filter stages, run partitions in parallel, vectorize predicate evaluation within each batch, and coalesce output writes. Analyze each term separately or a speedup will be attributed to the wrong mechanism.

The cost curve is a bound, not a batch-size prescription

The simple cost equation assumes homogeneous items, one fixed cost, linear variable cost, no spill, no cache cliff, and no interactions. Those assumptions often break at the batch sizes a benchmark celebrates.

Add the missing terms conceptually:

[ c(n) = v + \frac{F}{n} + q(n) + m(n) + h(n) + r(n), ]

where (q(n)) is per-item formation and scheduling wait, (m(n)) is memory/cache/spill cost, (h(n)) is head-of-line and fairness cost expressed in the chosen objective, and (r(n)) is retry or recovery amplification. Not every term is naturally time per item; the equation is a decision ledger, not permission to add incomparable quantities. Model latency, memory, and economic harm in their own units, then apply explicit constraints.

The fixture produces this idealized boundary:

Capacity is (n/S(n)). Mean fill wait assumes equally spaced arrivals and averages item positions within a batch. “Oldest completion” adds the oldest fill wait to full batch service, pessimistically assuming every item observes completion after the entire batch. A streaming implementation might release some results earlier; an atomic commit cannot.

Do not plot throughput, median latency, and tail latency on an unlabeled dual axis. Their numerical scales and meanings differ. A table or aligned small multiples make the trade visible: capacity keeps rising while the oldest-item deadline crosses between 32 and 64.

At low arrival rates, count batching can wait far longer. At bursty rates, many batches fill immediately and some linger. At heterogeneous service cost, count does not predict duration. Production policy therefore needs count, bytes, estimated work, oldest age, and earliest deadline.

Flush policy determines who pays the wait

A count trigger flushes when (n) items accumulate. It is simple and useful when item sizes and costs are bounded. It needs an age or deadline trigger so low load does not wait indefinitely.

A time trigger flushes after a maximum linger interval. It bounds formation delay only relative to a clearly defined clock: first item, last flush, or periodic tick. Periodic timers can synchronize across workers. Jitter and first-item timers often avoid a burst of simultaneous flushes.

A byte trigger protects frame, packet, memory, storage, and protocol limits better than count when payload sizes vary. It still misses CPU-heavy small items.

A work trigger uses an estimated cost such as decoded cells, tokens, pixels, compressed bytes, expected storage operations, or predicted execution time. Estimates can be wrong and adversarial, so retain hard count/byte bounds.

A deadline trigger flushes early enough that the earliest item’s remaining budget covers queueing, service, downstream work, and uncertainty. This makes batch policy subordinate to the user objective rather than to a local fullness target.

An adaptive trigger changes the target using arrival rate, observed service, queue age, deadline slack, memory, and downstream credit. It earns its complexity when workload phases are broad enough that one fixed policy wastes material capacity or violates objectives.

Ledgerline selects a maximum 32 ordinary items, 128 KiB serialized bytes, 1.5 ms formation age, and an earliest-deadline guard. The 32 is a ceiling, not a target that must be reached. A partial batch flushes when any bound fires. Under high load it fills by count. Under low load it flushes by age. A large entry flushes by bytes or cost. A near-deadline entry prevents a newer batch from waiting for fullness.

Partial batches are not a failure. They are how latency-bounded batching behaves. Track fill ratio by trigger so the team can see whether the policy is limited by count, bytes, age, deadlines, or downstream credits.

Pipeline overlap changes cadence, not stage work

Consider three deterministic batch stages: Parse 0.4 ms, Transform 0.9 ms, and Commit 1.3 ms. Processing three batches serially takes

[ T_{serial} = 3(0.4 + 0.9 + 1.3) = 7.8\ \text{ms}. ]

With one worker/resource per stage and buffers that permit overlap, ideal makespan is

[ T_{pipe} = \sum_i s_i + (B-1)\max_i(s_i) = 2.6 + 2(1.3) = 5.2\ \text{ms}, ]

where (s_i) is stage service time and (B=3) batches. After filling, the 1.3 ms Commit stage sets cadence. Pipelining does not make Commit faster; it keeps Parse and Transform useful while another batch commits.

The exact timeline is:

non-pipelined
slot:    1  2  3  4  5  6  7  8  9
batch 1: P  T  C
batch 2:          P  T  C
batch 3:                   P  T  C

pipelined
slot:    1  2  3  4  5
parse:   1  2  3
trans:      1  2  3
commit:        1  2  3

Unequal stage durations require buffers between stages. Those buffers need the same count, bytes, age, and credit discipline as Chapter 19. Unlimited in-flight batches can keep fast stages busy while allocating memory faster than Commit releases it. Bound the number of batches per stage and let Commit credits stop upstream formation.

Pipeline latency for one batch may remain the sum of stage times even while throughput improves. Deepening a pipeline can add handoffs, queues, cache disruption, and recovery state. It can also create bubbles when a stage stalls. Measure stage service, interstage wait, utilization, in-flight bytes, blocked-on-credit time, and end-to-end completion.

Ordering complicates parallel stage instances. If batch 3 transforms before batch 2 but commit order is required per account, the reorder buffer becomes another queue. Either preserve affinity, attach versions and reorder within a bound, or permit out-of-order effects where the invariant allows. Do not call a reorder buffer “temporary” without sizing its worst case.

Failure requires knowing which stages are replayable and which effect committed. Assign a batch identity plus item identities. Persist or reconstruct stage progress only where the consequence warrants it. Retrying the entire batch after a partial external effect can duplicate successful items; per-item outcome records or idempotent sink keys may be necessary.

Vectorization depends on representation and exceptions

Vectorized execution is most effective when the same operation applies to adjacent values with regular control flow. A columnar layout places values of one field contiguously, allowing an operator to load multiple values, compare them, and produce a selection mask with fewer branches and less irrelevant data movement. Apache Arrow’s current columnar format is designed to support contiguous buffers and vectorization across implementations; it is a representation contract, not a guarantee that every operator uses a particular instruction set.

Row-oriented batches can still amortize calls and metadata but may load fields the operator does not need. Columnar batches can reduce bytes touched for projections and filters, yet converting rows to columns costs time and memory. Chapter 17’s layout decision and Chapter 22’s serialization decision determine whether vector-friendly data arrives naturally or must be transposed.

Exceptional lanes matter. Nulls, variable-length values, encoding changes, scalar fallbacks, and rare expensive predicates can break regular execution. A single exceptional record should not force an enormous batch to retain memory indefinitely. Separate a bounded slow path, preserve output order only where needed, and measure fallback ratio and cost.

Vectorization is not the same as parallelism. One core can execute vector operations; many cores can each process batches; an accelerator can process an even wider batch with transfer and launch costs. State the boundary. A throughput gain from fewer instructions may become memory-bandwidth-bound, while a larger working set creates cache or translation pressure.

Validate vector claims with representative null density, cardinality, selectivity, value length, encoding, and output materialization. A dense arithmetic microbenchmark does not transfer to a branchy operator whose survivors trigger random gathers.

Group commit shares durability cost without changing the promise

Group commit allows multiple transactions to share a durable log flush. Each transaction retains its own outcome, but one flush can cover their log records. This reduces fixed flush cost when enough transactions become ready close together.

The durability boundary must remain identical in the comparison. Turning synchronous commit into asynchronous acknowledgement can improve latency by changing the loss contract; that is not merely batching. PostgreSQL’s current documentation distinguishes commit_delay, which enlarges a synchronous group-commit window, from asynchronous commit, which permits a crash-loss window. Its details are implementation-specific, but the distinction is durable: amortize the same guarantee or disclose that the guarantee changed.

Group commit policy needs concurrency. At low load, delaying for a group may waste time because no sibling arrives. At high load, natural overlap can form groups without deliberate linger. Measure flush duration, transactions per flush, wait before flush, commit latency distribution, log bytes, failure semantics, and storage saturation.

Write coalescing combines adjacent or compatible writes to reduce calls, metadata, seeks, or device work. It may increase write amplification or delay a small urgent write behind a large one. Network coalescing shares headers and calls across messages but can delay interactive traffic and create a loss/retry unit larger than one item. Preserve message framing, deadline, congestion, and receiver limits.

Acknowledgement coalescing and wakeup coalescing are similar: fewer control operations for more waiting. Verify the saved term is actually constraining. Removing syscalls from a path bound by storage service or network distance may not improve user completion.

Microbatching is a control problem in streaming and inference

Streaming systems use microbatches to turn unbounded input into finite scheduling, checkpoint, shuffle, and sink units. Batch duration or record count affects freshness, state size, recovery granularity, and straggler impact. A one-minute microbatch may offer efficient throughput and be incompatible with a five-second freshness objective.

Inference systems batch requests to amortize scheduling and exploit accelerator parallelism. Items may have different shapes, sequence lengths, deadlines, or model versions. Padding a batch to the longest item can turn one outlier into wasted compute for every lane. Bucket compatible shapes, cap padding ratio, and allow urgent or incompatible work to bypass or form a smaller batch. Account for host-device transfer and preprocessing rather than reporting kernel-only throughput.

In both domains, queue age is a strong controller input because it measures accumulated user-visible waiting. But queue age alone cannot distinguish a large cheap backlog from a small expensive one. Combine age with arrival rate, estimated service, bytes, device memory, downstream credit, and deadline slack.

Large-batch domination is a fairness failure

The ordinary Ledgerline item costs 35 µs of variable work. One tenant submits 32 complex entries at 250 µs each. With the same 240 µs fixed setup, that batch occupies the single Commit worker for 8.24 ms. Several small batches arriving behind it can miss a 10 ms deadline even though aggregate items/s improves.

This is head-of-line blocking: later work cannot reach a resource because an earlier unit monopolizes its service interval. Count-based fairness says both batches contain 32 items. Cost-based fairness sees a 5.9× service difference between the 8.24 ms complex batch and a 1.36 ms ordinary batch.

Mitigations move different costs:

• cap predicted batch service time as well as count and bytes;
• separate service classes with reserved or weighted capacity;
• use deficit or weighted scheduling across tenant queues;
• split a large batch at safe item boundaries;
• preempt only if stage and effect semantics support it;
• age waiting work so a low-weight class cannot starve; and
• charge actual service against tenant budgets and correct estimation error.

Splitting is unsafe when the batch is the atomic transaction. In that case, admission must reserve the full service and memory budget before start, and large atomic work may need a distinct lane. A lane is not isolation if both lanes contend on the same flush, connection, allocator, or downstream lock.

Measure per-tenant and per-class queue age, completion share, deadline misses, service consumed, batch-size and cost distributions, and maximum uninterrupted occupancy. Aggregate goodput can rise while a contractual population degrades.

Adaptive batching needs stable states and hard guards

An adaptive controller should operate inside non-negotiable safety bounds. One useful state machine is:

Use hysteresis so noise around one threshold does not alternate grow/shrink every window. Limit step size. Observe for at least the relevant batch and downstream feedback delay before another change. Keep hard maximum count, bytes, predicted service, memory, earliest deadline, and tenant share independent of the controller.

A latency-target controller can be dangerously self-reinforcing. When latency rises because downstream service has slowed, enlarging batches to seek throughput may increase fill wait and memory, worsening the tail. Rank hypotheses: is fixed overhead still the constraint, or did storage, bandwidth, cache, quota, or a hot partition become dominant?

Roll out adaptive policy with a shadow decision log: record what size and trigger the controller would choose without applying it. Then canary by tenant or partition, compare equal offered load and outcome correctness, and retain an immediate fixed-policy rollback. Configuration changes should carry an epoch so traces and batch records reveal which policy acted.

Operational evidence separates savings from moved cost

Instrument the item and batch levels. Item telemetry includes arrival, batch assignment, flush trigger, start, effect, deadline, tenant, and outcome. Batch telemetry includes count, bytes, predicted/actual service, fill duration, stage waits, memory retained, retries, and partial failures.

The decisive views are:

• fixed operations per successful item: flushes, syscalls, frames, launches, or transactions;
• capacity and goodput versus offered load, not throughput at one point;
• item queue/fill/service/completion distributions by class and tenant;
• batch count/bytes/cost/fill distributions by trigger;
• pipeline stage service, blocked time, bubbles, in-flight batches, and reorder depth;
• vector width, fallback lanes, bytes touched, cache/bandwidth evidence, and output selectivity;
• durability acknowledgements, records per flush, and crash/replay correctness;
• deadline misses, oldest age, starvation intervals, and uninterrupted resource occupancy; and
• recovery time and retry amplification after partial-batch failure.

Benchmark the same correctness and durability boundary. Validate the generator, preserve the arrival process and cost distribution, warm each representation appropriately, run independent trials, retain raw observations, and state the transfer limit. A saturated closed-loop client can hide formation wait by reducing offered load when responses slow.

Choose the mechanism by the cost it can move

Start with the fixed operation. If bounded, reasonably homogeneous items are repeatedly paying it, a count or time batch can share the cost. Low arrival rate and heterogeneous work weaken that choice because fullness stops predicting either wait or service. Fill triggers, fixed operations per success, and item tails show whether the shared work is worth the new formation delay.

When bytes, work, or deadline slack vary materially, count becomes only a backstop. Flush on the first byte, predicted-service, age, or deadline bound to fire. The estimator can improve utilization, but it cannot be the safety boundary: compare predicted with actual service and retain hard limits that survive a wrong or adversarial estimate. If item semantics prohibit splitting, admission must reserve the entire atomic unit instead.

Use a stage pipeline when distinct resources can overlap useful work. Its gain appears in cadence, not in magically shortened stage service. Stage waits, bubbles, credits, in-flight bytes, and reorder depth reveal whether overlap is real or buffers merely moved the queue. Replay, ordering, and partial effects must remain intelligible at every stage boundary.

Choose vectorized or columnar execution when regular operations touch selected contiguous fields. Measure bytes touched, qualifying lanes, fallbacks, conversion, and output materialization. If gathers, exceptions, conversion, or memory bandwidth dominate, a wider operator name does not improve the outcome. Null, exception, and scalar paths must remain equivalent to the original semantics.

Group commit and other coalescing earn their place only when a flush, call, frame, or wakeup is the constraining fixed term under real concurrency. Compare records per operation and user completion while preserving each item’s outcome and the original acknowledgement and durability boundary. Deliberate linger that breaks the latency objective, or earlier acknowledgement that weakens the guarantee, is a different design rather than successful amortization.

An adaptive controller is justified when workload phases repeatedly defeat every safe fixed policy. Shadow decisions should show that the extra control changes the frontier before it is allowed to act. Hard count, byte, work, memory, deadline, and fairness guards remain outside the controller; epochs, hysteresis, and rollback contain delayed or noisy feedback.

The field rule is marginal: batch only until the next reduction in per-item fixed cost is outweighed by queueing, tail, memory, fairness, or recovery cost.

Field checklist

• What fixed operation is being amortized, and does evidence show it constrains goodput or latency?
• What are variable cost and size distributions, not only their means?
• Which count, byte, predicted-work, memory, age, and deadline bounds apply?
• Can a partial batch flush safely, and which trigger caused each flush?
• Does pipelining improve throughput only, or also the user-visible completion path?
• How many batches and bytes can be in flight at every stage, including reorder buffers?
• Does vectorization save instructions or bytes after conversion, masks, gathers, and fallbacks?
• Are group-commit comparisons made at the same acknowledgement and durability boundary?
• Can one tenant, priority, shape, or expensive item dominate a shared batch or worker?
• What happens after partial effect, timeout, retry, crash, replay, and recovery?
• Does an adaptive controller have hysteresis, hard guards, policy epochs, shadow evidence, and rollback?
• Which changed workload, objective, storage, network, or representation invalidates the chosen size?

Applied policy: choose a latency-bounded write batch

For Ledgerline’s modeled ordinary workload, 32 items leaves about 3.47 ms of the 10 ms oldest-item budget for scheduler variance, downstream acknowledgement, and uncertainty; 64 already exceeds the bound. Therefore choose 32 only if measured non-formation tails fit the remaining budget. If storage p99 adds 4 ms beyond the modeled service, reduce the size or the formation-age ceiling.

Set maximum serialized bytes and predicted service so 32 unusually large or complex entries cannot masquerade as an ordinary batch. Flush at the earliest of count 32, 128 KiB, 1.5 ms oldest formation age, predicted 1.5 ms local service, downstream credit reduction, or earliest deadline minus a conservative service-and-uncertainty reserve. Preserve per-entry operation identity and record the group durability boundary.

Validate sizes 8, 16, 24, and 32 under the real arrival distribution, including low-rate intervals and tenant bursts. Compare goodput, item p50/p95/p99, deadline success, memory, records/flush, tenant age, crash recovery, and storage evidence at equal offered load. The chosen 32 is a model-generated candidate, not a permanent configuration.

Principal drill: throughput rose while fairness failed

Ledgerline serves four tenant classes. One supplies 40% of entries and occasionally sends 32-item atomic batches whose item cost is 250 µs. Small tenants send 1–4 ordinary entries with 10 ms deadlines. The commit resource is shared; splitting the atomic batch is forbidden. A deployment raises aggregate goodput 18% and doubles small-tenant deadline misses.

Produce:

1. a fixed/variable and arrival model by tenant and batch class;
2. count, bytes, predicted service, age, earliest-deadline, memory, and atomicity bounds;
3. a scheduling policy that reserves or weights commit opportunity without pretending the shared flush is isolated;
4. a pipeline and in-flight diagram with credits, reorder needs, and failure points;
5. group-commit semantics that preserve the original durability and per-entry outcomes;
6. partial-effect, timeout, retry, replay, and recovery behavior;
7. per-tenant fairness objectives and maximum uninterrupted occupancy;
8. a representative experiment with raw item and batch observations; and
9. adaptive-controller shadow, canary, hysteresis, rollback, and revisit triggers.

One defensible answer admits large atomic batches only after reserving their full predicted service, gives them a weighted lane with a maximum share per scheduling window, and allows small deadline-bound groups to commit between large groups. Another uses physically separate commit capacity if isolation value pays for it. An answer that reports only aggregate records/s has not addressed the failure.

Review questions and durable conclusions

1. With fixed cost 300 µs and variable cost 20 µs/item, calculate amortized service demand for batches of 1, 10, and 50. Which other measurements are required before choosing 50?
2. Why does a count trigger need an independent age or deadline trigger? Describe the low-load failure that otherwise occurs.
3. A three-stage pipeline has stage times 2, 5, and 3 ms. Calculate the ideal makespan for four batches, then name two reasons production makespan may be longer.
4. Explain why vectorized execution can reduce instruction demand yet fail to improve end-to-end goodput. Give one layout cause and one system-level cause.
5. What makes a group-commit comparison invalid when the treatment acknowledges before the same durability boundary as the baseline?
6. Two 32-item batches have service intervals of 1.4 and 9 ms. Why is round-robin by batch count not service fairness? Name a scheduling alternative and its required estimator.
7. An adaptive controller enlarges batches whenever latency rises. Show the positive feedback loop that can result when downstream service has slowed.
8. Which identities and records allow safe replay after 19 of 32 items committed before a worker failed?

The durable conclusions follow the marginal cost. Batching can remove only the fixed term it actually shares; it cannot erase variable work. Formation delay belongs to every item objective even when aggregate capacity improves. Pipelining overlaps stages but makes the slowest steady stage, interstage bounds, and partial progress explicit. Vectorization depends on representation and regularity, not merely a wide instruction name. Group commit is an amortization result only when acknowledgement and durability remain comparable. A batch boundary is also a scheduling, memory, failure, and fairness boundary. Adaptive control is justified only inside hard guards and with feedback delay, hysteresis, policy identity, shadow evidence, and rollback made observable.

Evidence and transfer limits

• Apache Arrow columnar format specifies language-independent contiguous columnar buffers intended to support vectorization. Actual instruction selection and performance depend on the implementation and workload.
• PostgreSQL 18 WAL configuration documents current group-commit behavior and the latency/throughput trade of commit_delay. It is an implementation example, not a universal setting.
• PostgreSQL asynchronous commit distinguishes changing the durability acknowledgement from enlarging a synchronous group-commit window. The exact risk and timing are version- and configuration-specific.
• Apache Kafka 4.2 producer configuration documents batch.size and linger.ms behavior, including the delay/memory trade. Product defaults are not recommendations for Ledgerline.
• Every Ledgerline number is deterministic modeled teaching evidence from examples/performance-engineering-system-design-handbook/part-03/batching-amortization/. The model assumes deterministic arrivals and stage times, homogeneous ordinary items, perfect pipeline overlap, and no additional queueing. It is not a database, network, accelerator, or production benchmark.

Batching is temporary aggregation for a named operation. Caching duplicates or retains state across operations to avoid future work. Confusing them hides authority, freshness, and invalidation obligations; those become the next design boundary.