← 输入框|github.com|刷新
Skip to content

[dbsp] Finish a sharded accumulator's flush in the step of the last flush. - #7778

Merged
blp merged 2 commits into
mainfrom
sharded-accumulator-lag-notices
Nov 2, 2026
Merged

blp merged 2 commits into
mainfrom
sharded-accumulator-lag-notices

Conversation

@ryzhyk

@ryzhyk ryzhyk commented Nov 1, 2026

Copy link
Copy Markdown
Contributor

A sharded accumulator receiver that ran before its peers' flushes arrived finished its flush only in the next step, so every exchange on the longest path of a circuit added a step to each commit.

We would like a receiver whose own sender has flushed to wait for other workers to flush in the same step; however a naive way of doing this by introducing a global barrier, e.g., as implemented by wait_for_arrival, would defeat the purpose of the streaming exchange mechanism.

This PR implements a more efficient solution that only requires a worker to wait in the step where it flushes this input.

The new protocol is specified as a set of sequence diagrams in sharded_accumulator.rs.

Linked Issue

Closes #7745

Describe Manual Test Plan

Checklist

  • Unit tests added/updated
  • Integration tests added/updated
  • Documentation updated
  • Changelog updated

Breaking Changes?

Mark if you think the answer is yes for any of these components:

Describe Incompatible Changes

@ryzhyk
ryzhyk requested review from anandbraman and blp November 1, 2026 21:05
@ryzhyk ryzhyk added DBSP core Related to the core DBSP library performance labels Nov 1, 2026
@mythical-fred-oss

Copy link
Copy Markdown
Contributor

LGTM. I found no blocking issues, and all feldera-pr-checks gates pass.

What I ran (debug, -p dbsp):

Command Result
cargo test --lib sharded_accumulator (26 tests, including flush_protocol proptest, uneven_flushes_*, kill_ends_flush_wait_*, join_chain_*) ✅ 5 runs in a row, no flakes
cargo test --lib delivery_panic ✅
cargo test --lib -- multihost exchange accumulat join (147 tests, regression sweep) ✅
cargo check --bench commit_steps, rustfmt --check on the changed files ✅

What I checked by hand:

  • Deadlocks: the dynamic scheduler runs operators as tasks in a JoinSet, so a waiting receiver yields its worker. Each wait depends only on upstream senders, lag notices, or receive tasks that never wait on workers. For two workers to block each other, the circuit graph would need a cycle, and it has none.
  • Message ordering: streaming exchange uses one connection per host pair, with no big/small split. A lag notice therefore can't reorder against the same host's flush, and stale notices are ignored because the receiver checks step >= steps.
  • Possible flakiness: the exact lag-notice count asserted on a single host is deterministic, because the controller finishes every worker's step before starting the next. The multihost assertions are already relaxed to account for timing.

Missing coverage (medium): no test combines uneven flushes with a custom sender that never calls sender_lags, such as PartitionedSender/send_partitioned. That is the path where the receiver alone must send the notice. The unit test lagging_receiver_sends_lag_notice covers it, but no end-to-end test does.

@blp

blp commented Nov 2, 2026

Copy link
Copy Markdown
Member

The protocol is sound as far as I can tell, but it was hard to follow from the comments. The module doc starts with the diagrams. The context that explains them is in the PR body, or spread across the ShardedAccumulator struct doc. Could the module doc give that context before the diagrams, in this order?

  1. The problem: a receiver that runs before a peer's flush arrives outputs one step late, and this adds one step per exchange on the longest path.
  2. Why the receiver cannot simply wait for all flushes: a worker whose sender flushes in a later step cannot get to that step while another receiver waits in this one, so the wait would hang.
  3. A lag notice: "my sender ran in step k without flushing, so do not wait for me in step k."
  4. The receiver rule: after its own sender flushes, a receiver waits until it has all flushes (output the spine) or a lag notice for this step (output nothing, try again next step).
  5. When a worker sends a notice: only if it has not flushed but another worker has. It checks at three points (sender, receiver, late arrival), and each point catches a flush that the earlier points missed.
  6. How the step numbers agree across workers, and why a late notice from an earlier step is ignored.

With that context first, the diagrams read as examples. The struct doc could then point to the module doc, and not repeat it.

For example, the start of the module doc could be something like this, followed by the existing diagrams:

//! A fused shard and accumulate operator over a streaming exchange.
//!
//! In every step, each worker's sender partitions its input among the workers,
//! and each worker's receiver accumulates the parts sent to it into a spine.  A
//! sender's last batch in a transaction is its flush.  A receiver outputs the
//! transaction's spine once it holds the flushes of all senders.
//!
//! # The problem
//!
//! A receiver runs once per step.  If it runs before another worker's flush
//! arrives, it outputs nothing in that step and outputs the spine one step
//! later.  Each exchange on the longest path of a circuit can then add one
//! step to a commit.
//!
//! # Why the receiver cannot simply wait
//!
//! The obvious fix is for a receiver, after its own sender flushes, to wait in
//! the same step for the other flushes.  That hangs when another worker's
//! sender flushes only in a later step:
//!
//! | Step | Worker A                              | Worker B                               |
//! |------|---------------------------------------|----------------------------------------|
//! | k    | sender flushes, receiver waits for B  | upstream not done, sender does not flush |
//! | k+1  | (never starts)                        | can flush only after step k ends       |
//!
//! So A must wait only while B can still flush in step k, and B must tell A
//! when it cannot.
//!
//! # Lag notices
//!
//! A lag notice from worker B for step k means: "my sender ran in step k
//! without flushing, so do not wait for me in step k."
//!
//! A receiver whose own sender has not flushed returns at once, as before.  A
//! receiver whose own sender has flushed waits until one of these happens:
//!
//! - It holds the flushes of all senders.  It outputs the spine.
//! - It gets a lag notice for the current step.  It outputs nothing, and tries
//!   again in the next step.
//!
//! So every step ends: either all flushes arrive, or a lagging worker sends a
//! notice.  When all senders flush in the same step, no worker sends a notice.
//!
//! # When a worker sends lag notices
//!
//! A worker sends lag notices for a step only if its sender has not flushed
//! and it knows that another sender has.  If no sender has flushed, no
//! receiver waits, and a notice would be of no use.  A worker learns of flushes
//! from its own receive queue, which gets every sender's flush.  It looks at
//! three points, and each one catches a flush that the earlier ones missed:
//!
//! | Point                          | Catches                                          |
//! |--------------------------------|--------------------------------------------------|
//! | Its sender runs                | The usual case.  The notice goes out before the sender's data. |
//! | Its receiver runs              | A flush that arrived after the sender looked.    |
//! | A flush arrives after both ran | A late flush, often from another host.  The code that delivers it sends the notice for the lagging worker. |
//!
//! # Step numbers
//!
//! Each flush and each lag notice carries a step number.  Each worker counts
//! its receiver's runs, and every worker runs the same steps, so the numbers
//! agree across workers.  A waiting receiver acts only on a notice for its
//! current step, so a notice from an earlier step that arrives late does not
//! stop it from waiting.
//!
//! # Example
//!
//! Worker B's sender flushes two steps after worker A's:
//!
//! | Step | Worker A                                         | Worker B                                   |
//! |------|--------------------------------------------------|--------------------------------------------|
//! | k    | flushes, waits, gets notice (B, k), outputs nothing | sees A's flush, sends notice (B, k)     |
//! | k+1  | waits, gets notice (B, k+1), outputs nothing     | still lags, sends notice (B, k+1)          |
//! | k+2  | waits, gets B's flush, outputs the spine         | flushes, holds all flushes, outputs the spine |
//!
//! Both workers output the spine in step k+2, the step of the last flush.
//! The diagrams below show these cases, and the case across hosts, in detail.

@blp

blp commented Nov 2, 2026

Copy link
Copy Markdown
Member

About the commit_steps numbers: the bench runs all hosts in one process over 127.0.0.1, so a round trip between hosts takes only tens of microseconds. Within a cloud zone it is more like 100 to 500 µs, and across zones 1 ms or more.

This matters for this PR because it trades one cost for another:

Cost
Saved One full step per exchange on the longest path, in which all operators run again (and the nested circuit too, with --recursive).
Added In each step where a worker lags, the receiver that has flushed waits for a lag notice: one way when the lagging sender sends it, a round trip when a late flush arrival triggers it.

On loopback the added cost is close to zero, so the bench shows the gain but not the cost. Could the PR description show results on main and on this branch for a few latencies, such as 0, 250 and 1000 µs one way, in commit and skewed modes with --hosts 2?

The patch below adds a --latency-us knob to commit_steps. It applies with git apply on top of this branch (3de094b), and I checked that it compiles, passes rustfmt, and has an effect: with --hosts 2 --workers 4 --rows 1000 --commits 10, the median commit takes 3.1 ms at --latency-us 0 and 27.2 ms at --latency-us 1000. On main, which has no commit_steps, the crates/dbsp/src part applies on its own (git apply --include='crates/dbsp/src/*').

It delays data in run_connection_tx and acknowledgements in run_connection_rx. Both are needed: on multihost, each step already waits for its streaming sends to be acknowledged (ShardedAccumulatorRemoteWaiter), on main too. If only the data were delayed, the steps that this PR removes would look too cheap. Messages stay pipelined and in order, because each one waits until its own creation time plus the latency. The model has fixed latency only, with no bandwidth limit and no jitter.

latency.patch
diff --git a/crates/dbsp/benches/commit_steps.rs b/crates/dbsp/benches/commit_steps.rs
index 80ec841bf..6b5f46149 100644
--- a/crates/dbsp/benches/commit_steps.rs
+++ b/crates/dbsp/benches/commit_steps.rs
@@ -25,6 +25,7 @@ use clap::{Parser, ValueEnum};
 use dbsp::{
     DBSPHandle, OrdZSet, RootCircuit, Runtime, Stream, ZSetHandle, ZWeight,
     circuit::{CircuitConfig, Layout},
+    operator::communication::set_simulated_exchange_latency,
     utils::Tup2,
 };
 use rand::{Rng, SeedableRng};
@@ -36,7 +37,7 @@ use std::{
     path::PathBuf,
     sync::mpsc::{Receiver, Sender, channel},
     thread::{self, JoinHandle},
-    time::Instant,
+    time::{Duration, Instant},
 };
 
 /// The number of keys in the dimension table that every join joins with.
@@ -105,6 +106,10 @@ struct Args {
     /// Writes every sample to this file, as JSON.
     #[arg(long)]
     json: Option<PathBuf>,
+
+    /// Simulated one-way latency between hosts, in microseconds.
+    #[arg(long, default_value_t = 0)]
+    latency_us: u64,
 }
 
 /// A command to the thread that drives one host.
@@ -445,6 +450,7 @@ fn facts(first: u64, n: usize, value: impl Fn(u64) -> u64) -> Vec<Tup2<u64, u64>
 
 fn main() -> Result<()> {
     let args = Args::parse();
+    set_simulated_exchange_latency(Duration::from_micros(args.latency_us));
     let hosts = Hosts::start(&args)?;
 
     // Load the dimension table, the facts and, for `--recursive`, a path graph.
diff --git a/crates/dbsp/src/operator/communication.rs b/crates/dbsp/src/operator/communication.rs
index 73ab4ef33..55edf5ce4 100644
--- a/crates/dbsp/src/operator/communication.rs
+++ b/crates/dbsp/src/operator/communication.rs
@@ -8,4 +8,5 @@ pub(crate) use exchange::{
 };
 pub use exchange::{
     ExchangeActivity, ExchangeReceiver, ExchangeSender, Mailbox, new_exchange_operators,
+    set_simulated_exchange_latency,
 };
diff --git a/crates/dbsp/src/operator/communication/exchange.rs b/crates/dbsp/src/operator/communication/exchange.rs
index 3d3fd6c68..dd304cf65 100644
--- a/crates/dbsp/src/operator/communication/exchange.rs
+++ b/crates/dbsp/src/operator/communication/exchange.rs
@@ -58,7 +58,7 @@ use tokio::{
     },
     sync::{Notify, OnceCell, futures::OwnedNotified},
     task::JoinHandle,
-    time::{sleep, timeout},
+    time::{sleep, sleep_until, timeout},
 };
 use tokio_util::sync::{CancellationToken, DropGuard};
 use tracing::{error, info, warn};
@@ -517,7 +517,19 @@ impl ExchangeClient {
         channel: ExchangeChannel,
     ) -> std::io::Result<()> {
         loop {
-            channel.drain(rx.read_u64_le().await?);
+            let next_sequence = rx.read_u64_le().await?;
+            match simulated_latency() {
+                // `drain` is cumulative, so the acknowledgements may drain out
+                // of order.
+                Some(latency) => {
+                    let channel = channel.clone();
+                    tokio::spawn(async move {
+                        sleep(latency).await;
+                        channel.drain(next_sequence);
+                    });
+                }
+                None => channel.drain(next_sequence),
+            }
         }
     }
 
@@ -571,6 +583,12 @@ impl ExchangeClient {
             };
             min_sequence = sequence + 1;
 
+            // Each message waits from its creation, so a burst of messages
+            // waits once in total, and a retransmission does not wait again.
+            if let Some(latency) = simulated_latency() {
+                sleep_until((message.start + latency).into()).await;
+            }
+
             if inject_fault("connection failure") {
                 return Err(std::io::Error::other("simulated connection failure"));
             }
@@ -2640,6 +2658,26 @@ fn ping_interval() -> Duration {
     Duration::from_secs(1)
 }
 
+/// Simulated one-way latency between hosts, in microseconds, or 0 for none
+/// (see [set_simulated_exchange_latency]).
+static SIMULATED_LATENCY_US: AtomicU64 = AtomicU64::new(0);
+
+/// Delays each exchange message, and each acknowledgement, between hosts by
+/// `latency`, to simulate a network in benchmarks.  This applies to every
+/// runtime in the process.
+#[doc(hidden)]
+pub fn set_simulated_exchange_latency(latency: Duration) {
+    SIMULATED_LATENCY_US.store(latency.as_micros().try_into().unwrap(), Ordering::Relaxed);
+}
+
+/// Returns the latency set by [set_simulated_exchange_latency], if any.
+fn simulated_latency() -> Option<Duration> {
+    match SIMULATED_LATENCY_US.load(Ordering::Relaxed) {
+        0 => None,
+        us => Some(Duration::from_micros(us)),
+    }
+}
+
 #[cfg(test)]
 mod tests {
     use feldera_storage::tokio::TOKIO;

@blp blp left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This is getting complicated. Because I know that we're in a rush for this particular review, what I did for this review was:

  • Try to understand the new protocol and behavior at a high level. This was harder than I expected, so I posted some additional documentation comments for the source code that would have helped me.
  • Try to understand what I would expect from performance of the new protocol. This seemed to me like it added a cost for multihost based on round-trip time, which didn't seem to be explained or measured in the benchmark, so I posted an improvement to the benchmark that adds that as a knob to be turned.

I didn't try to understand all the details of the code, so I can't have as much confidence as I normally would that it is correct. I feel OK about that because of the tests, and because I intend to throw Antithesis at the new version to shake out corner cases.

@ryzhyk

ryzhyk commented Nov 2, 2026

Copy link
Copy Markdown
Contributor Author

@blp , thanks for the review. Turns out I can't set timeouts <1ms on a mac, so I ran the benchmarks with 1ms+ timeouts. My reading of this is that, as expected, the protocol only introduces overhead in a skewed workload where one of the workers finishes the transaction ahead of the others.


Commit mode (10 rows per commit):

┌───────────────────┬───────┬──────────────────────┬───────────────────┬───────────────────────┬──────────────────────┐
│ Latency, one way  │ Depth │ Steps, main → branch │ ms, main → branch │ CPU ms, main → branch │ branch/main [95% CI] │
├───────────────────┼───────┼──────────────────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 0                 │ 1     │ 2 → 1                │ 1.00 → 0.745      │ 6.38 → 5.32           │ 0.741 [0.730, 0.754] │
├───────────────────┼───────┼──────────────────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 0                 │ 8     │ 9 → 1                │ 5.84 → 2.10       │ 42.3 → 16.7           │ 0.360 [0.358, 0.362] │
├───────────────────┼───────┼──────────────────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 0                 │ 32    │ 33 → 1               │ 39.4 → 6.67       │ 294 → 56.4            │ 0.169 [0.169, 0.170] │
├───────────────────┼───────┼──────────────────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 250 µs (1.29 ms)  │ 1     │ 2 → 1                │ 11.6 → 7.28       │ 12.5 → 8.45           │ 0.627 [0.612, 0.644] │
├───────────────────┼───────┼──────────────────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 250 µs (1.29 ms)  │ 8     │ 9 → 1                │ 61.1 → 20.5       │ 87.1 → 28.8           │ 0.335 [0.328, 0.346] │
├───────────────────┼───────┼──────────────────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 250 µs (1.29 ms)  │ 32    │ 33 → 1               │ 248 → 65.1        │ 559 → 97.1            │ 0.263 [0.254, 0.272] │
├───────────────────┼───────┼──────────────────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 1000 µs (2.53 ms) │ 1     │ 2 → 1                │ 17.6 → 11.7       │ 14.3 → 9.88           │ 0.664 [0.653, 0.679] │
├───────────────────┼───────┼──────────────────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 1000 µs (2.53 ms) │ 8     │ 9 → 1                │ 84.7 → 31.8       │ 91.7 → 32.8           │ 0.375 [0.371, 0.379] │
├───────────────────┼───────┼──────────────────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 1000 µs (2.53 ms) │ 32    │ 33 → 1               │ 321 → 103         │ 578 → 114             │ 0.319 [0.317, 0.322] │
└───────────────────┴───────┴──────────────────────┴───────────────────┴───────────────────────┴──────────────────────┘

Skewed mode (depth 8):

┌───────────────────┬────────────────┬──────────────────────┬───────────────────┬───────────────────────┬──────────────────────┐
│ Latency, one way  │ Chunk, records │ Steps, main → branch │ ms, main → branch │ CPU ms, main → branch │ branch/main [95% CI] │
├───────────────────┼────────────────┼──────────────────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 0                 │ 10             │ 670 → 665            │ 382 → 392         │ 2,404 → 2,375         │ 1.027 [1.021, 1.030] │
├───────────────────┼────────────────┼──────────────────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 0                 │ 10,000         │ 129 → 121            │ 326 → 321         │ 917 → 877             │ 0.986 [0.983, 0.988] │
├───────────────────┼────────────────┼──────────────────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 250 µs (1.29 ms)  │ 10             │ 671 → 665            │ 4,410 → 5,184     │ 5,574 → 5,980         │ 1.175 [1.164, 1.196] │
├───────────────────┼────────────────┼──────────────────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 250 µs (1.29 ms)  │ 10,000         │ 127 → 121            │ 934 → 1,076       │ 1,141 → 1,192         │ 1.152 [1.117, 1.197] │
├───────────────────┼────────────────┼──────────────────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 1000 µs (2.53 ms) │ 10             │ 671 → 665            │ 6,247 → 7,774     │ 6,119 → 6,516         │ 1.245 [1.200, 1.258] │
├───────────────────┼────────────────┼──────────────────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 1000 µs (2.53 ms) │ 10,000         │ 127 → 121            │ 1,341 → 1,612     │ 1,303 → 1,386         │ 1.203 [1.195, 1.212] │
└───────────────────┴────────────────┴──────────────────────┴───────────────────┴───────────────────────┴──────────────────────┘

…lush

Closes #7745

With more than one worker, a receiver that ran before its peers' flushes
arrived finished its flush only in the next step, so every exchange on the
longest path of a circuit added a step to each commit (#7745).

We would like a receiver whose own worker's sender has flushed to wait for
other workers to flush in the same step; however a naive way of doing this
by introducing a global barrier, e.g., as implemented by wait_for_arrival,
would defeat the purpose of the streaming exchange mechanism. This commit
implements a more efficient solution that only requires a worker to wait
in the step where it flushes this input.

The new protocol is specified as a set of sequence diagrams in
sharded_accumulator.rs.

Performance:

Small commits (10 rows, 8 workers):

┌───────┬───────┬────────┬───────────────────┬───────────────────────┬──────────────────────┐
│ Hosts │ Depth │ Steps  │ ms, main → branch │ CPU ms, main → branch │     branch/main      │
├───────┼───────┼────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 1     │ 1     │ 2 → 1  │ 0.508 → 0.320     │ 3.06 → 2.15           │ 0.629 [0.622, 0.637] │
├───────┼───────┼────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 1     │ 8     │ 9 → 1  │ 3.80 → 1.17       │ 25.9 → 9.81           │ 0.308 [0.305, 0.311] │
├───────┼───────┼────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 1     │ 32    │ 33 → 1 │ 33.6 → 4.02       │ 234 → 35.8            │ 0.120 [0.118, 0.121] │
├───────┼───────┼────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 2     │ 1     │ 2 → 1  │ 0.984 → 0.725     │ 6.20 → 4.74           │ 0.737 [0.729, 0.748] │
├───────┼───────┼────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 2     │ 8     │ 9 → 1  │ 5.84 → 2.07       │ 42.2 → 16.4           │ 0.354 [0.352, 0.357] │
├───────┼───────┼────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 2     │ 32    │ 33 → 1 │ 39.4 → 6.67       │ 290 → 56.4            │ 0.169 [0.168, 0.171] │
└───────┴───────┴────────┴───────────────────┴───────────────────────┴──────────────────────┘

"depth" is the number of operators in the chain. Each operator adds up to an extra step to
each transaction.

Skewed commits (8 workers, depth 8). One worker emits each join's output over many steps, so the workers flush in different steps and lag notices are sent:

┌────────────────┬───────┬───────────┬───────────────────┬───────────────────────┬──────────────────────┐
│     Chunk      │ Hosts │   Steps   │ ms, main → branch │ CPU ms, main → branch │     branch/main      │
├────────────────┼───────┼───────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 10 records     │ 1     │ 669 → 665 │ 246.8 → 240.6     │ 1,479 → 1,463         │ 0.975 [0.969, 0.990] │
├────────────────┼───────┼───────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 10 records     │ 2     │ 671 → 665 │ 373.8 → 379.1     │ 2,331 → 2,249         │ 1.014 [1.011, 1.021] │
├────────────────┼───────┼───────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 10,000 records │ 1     │ 126 → 121 │ 284.9 → 284.4     │ 708 → 707             │ 0.998 [0.994, 1.000] │
├────────────────┼───────┼───────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 10,000 records │ 2     │ 129 → 121 │ 326.2 → 321.7     │ 905 → 876             │ 0.986 [0.984, 0.988] │
└────────────────┴───────┴───────────┴───────────────────┴───────────────────────┴──────────────────────┘

With network latency (2 hosts, 8 workers). The bench runs all hosts in one
process, so for this run a patch delayed every message and acknowledgement
between hosts. The delays use tokio's timer, which rounds them up to whole
milliseconds, so the requested one-way latencies of 250 µs and 1 ms came out
at about 1.3 ms and 2.5 ms.

Small commits (10 rows). Each exchange on the longest path costs main a step,
and the branch a one-way wait for the other host's flushes:

┌─────────┬───────┬────────┬───────────────────┬───────────────────────┬──────────────────────┐
│ Latency │ Depth │ Steps  │ ms, main → branch │ CPU ms, main → branch │     branch/main      │
├─────────┼───────┼────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 0       │ 1     │ 2 → 1  │ 1.01 → 0.745      │ 6.38 → 5.32           │ 0.741 [0.730, 0.754] │
├─────────┼───────┼────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 0       │ 8     │ 9 → 1  │ 5.84 → 2.10       │ 42.3 → 16.7           │ 0.360 [0.358, 0.362] │
├─────────┼───────┼────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 0       │ 32    │ 33 → 1 │ 39.4 → 6.68       │ 294 → 56.4            │ 0.169 [0.169, 0.170] │
├─────────┼───────┼────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 1.3 ms  │ 1     │ 2 → 1  │ 11.6 → 7.28       │ 12.5 → 8.45           │ 0.627 [0.612, 0.644] │
├─────────┼───────┼────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 1.3 ms  │ 8     │ 9 → 1  │ 61.1 → 20.5       │ 87.1 → 28.8           │ 0.335 [0.328, 0.346] │
├─────────┼───────┼────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 1.3 ms  │ 32    │ 33 → 1 │ 248 → 65.1        │ 559 → 97.1            │ 0.263 [0.254, 0.272] │
├─────────┼───────┼────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 2.5 ms  │ 1     │ 2 → 1  │ 17.6 → 11.7       │ 14.3 → 9.88           │ 0.664 [0.653, 0.679] │
├─────────┼───────┼────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 2.5 ms  │ 8     │ 9 → 1  │ 84.7 → 31.8       │ 91.7 → 32.8           │ 0.375 [0.371, 0.379] │
├─────────┼───────┼────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 2.5 ms  │ 32    │ 33 → 1 │ 321 → 103         │ 578 → 114             │ 0.319 [0.317, 0.322] │
└─────────┴───────┴────────┴───────────────────┴───────────────────────┴──────────────────────┘

Skewed commits (depth 8). The branch saves almost no steps, and in each step
the workers that have flushed wait for the lagging worker's lag notice, which
crosses hosts one way. Each step takes about one latency longer: 1.2 ms and
2.4 ms with 10-record chunks:

┌─────────┬────────────────┬───────────┬───────────────────┬───────────────────────┬──────────────────────┐
│ Latency │     Chunk      │   Steps   │ ms, main → branch │ CPU ms, main → branch │     branch/main      │
├─────────┼────────────────┼───────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 0       │ 10 records     │ 670 → 665 │ 381.7 → 391.8     │ 2,404 → 2,375         │ 1.027 [1.021, 1.030] │
├─────────┼────────────────┼───────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 0       │ 10,000 records │ 129 → 121 │ 325.7 → 321.1     │ 917 → 877             │ 0.986 [0.983, 0.988] │
├─────────┼────────────────┼───────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 1.3 ms  │ 10 records     │ 671 → 665 │ 4,410 → 5,184     │ 5,574 → 5,980         │ 1.175 [1.164, 1.196] │
├─────────┼────────────────┼───────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 1.3 ms  │ 10,000 records │ 127 → 121 │ 933.8 → 1,076     │ 1,141 → 1,192         │ 1.152 [1.117, 1.197] │
├─────────┼────────────────┼───────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 2.5 ms  │ 10 records     │ 671 → 665 │ 6,247 → 7,774     │ 6,119 → 6,516         │ 1.245 [1.200, 1.258] │
├─────────┼────────────────┼───────────┼───────────────────┼───────────────────────┼──────────────────────┤
│ 2.5 ms  │ 10,000 records │ 127 → 121 │ 1,341 → 1,612     │ 1,303 → 1,386         │ 1.203 [1.195, 1.212] │
└─────────┴────────────────┴───────────┴───────────────────┴───────────────────────┴──────────────────────┘

Signed-off-by: Leonid Ryzhyk <ryzhyk@gmail.com>
A panic in a task that delivers messages from another host went unreported:
the panic hook reports only panics on a runtime's own threads, and the task
runs on a shared Tokio runtime.  The flush or lag notice that the message
carried was lost, so a receiver waiting for flushes waited forever.

Each such task now catches its panic and reports it to its runtime, which
raises the panic signal, so that the runtime's handle fails instead of
waiting.

Signed-off-by: Leonid Ryzhyk <ryzhyk@gmail.com>
@ryzhyk
ryzhyk force-pushed the sharded-accumulator-lag-notices branch from 3de094b to 0cb2072 Compare November 2, 2026 16:51
@ryzhyk
ryzhyk enabled auto-merge November 2, 2026 16:54
@ryzhyk
ryzhyk disabled auto-merge November 2, 2026 17:00
@ryzhyk
ryzhyk added this pull request to the merge queue Nov 2, 2026
@blp

blp commented Nov 2, 2026

Copy link
Copy Markdown
Member

@blp , thanks for the review. Turns out I can't set timeouts <1ms on a mac, so I ran the benchmarks with 1ms+ timeouts. My reading of this is that, as expected, the protocol only introduces overhead in a skewed workload where one of the workers finishes the transaction ahead of the others.

Thanks for checking. Then the benefits outweigh the costs a lot, as long as we're not expecting skewed workloads a lot.

@github-merge-queue
github-merge-queue Bot removed this pull request from the merge queue due to failed status checks Nov 2, 2026
@blp

blp commented Nov 2, 2026

Copy link
Copy Markdown
Member

I'll throw claude against the CI failure; requeuing.

@mythical-fred-oss

Copy link
Copy Markdown
Contributor

Verdict: pre-existing flaky test, not this PR's fault (high confidence).

Next step: re-queueing should pass; this is unrelated to your change.

Merged via the queue into main with commit d5fa739 Nov 2, 2026
1 check passed
@blp
blp deleted the sharded-accumulator-lag-notices branch November 2, 2026 22:59
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

DBSP core Related to the core DBSP library performance

Projects

None yet

Development

Successfully merging this pull request may close these issues.

[dbsp] Let a sharded accumulator receiver finish its flush in the step in which its peers flush

3 participants