Repository navigation
[dbsp] Finish a sharded accumulator's flush in the step of the last flush. - #7778
Conversation
|
LGTM. I found no blocking issues, and all feldera-pr-checks gates pass. What I ran (debug,
What I checked by hand:
Missing coverage (medium): no test combines uneven flushes with a custom sender that never calls |
|
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
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.
|
|
About the This matters for this PR because it trades one cost for another:
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 The patch below adds a It delays data in latency.patchdiff --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
left a comment
There was a problem hiding this comment.
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.
|
@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): Skewed mode (depth 8): |
…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>
3de094b to
0cb2072
Compare
Thanks for checking. Then the benefits outweigh the costs a lot, as long as we're not expecting skewed workloads a lot. |
|
I'll throw claude against the CI failure; requeuing. |
|
Verdict: pre-existing flaky test, not this PR's fault (high confidence).
Next step: re-queueing should pass; this is unrelated to your change. |
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
Breaking Changes?
Mark if you think the answer is yes for any of these components:
Describe Incompatible Changes