Support broadcast channel

[tisonkun]

Motivation

I'm going to factor out the async runtime code in foyer (cc @MrCroxx) to make madsim an opt-outable feature.

Typically, it would be like a runtime module to hide the implementation.

Before that, I noticed foyer uses several tokio::sync primitives which can be replaced with mea:

• tokio::sync::Barrier can be mea::barrier::Barrier
• tokio::sync::oneshot can be mea::oneshot
• tokio::sync::Mutex can be mea::mutex::Mutex
• tokio::sync::broadcast is lacking

Thus, I think we can support the broadcast channel in mea to replace all tokio::sync usage in foyer.

Design and Implementation

The most common design is to use a circular queue, where senders put elements at the end, and each receiver tracks its current position and consumes new elements if any are available.

Some decision points:

1. What if a receiver lags too much until the next new elements put would overflow its current position?

tokio's broadcast would trigger a Lagged error and forward the receiver's position to the oldest value contained by the channel.

async-broadcast supports different overflow policy: (1) like what tokio's broadcast does, (2) sender waits for all the receivers to move forward.

2. Then we need to decide the API structure, like:

• How to make a broadcast channel?
• How to make a new sender/receiver of the broadcast channel?
• How sender's/receiver's (try) send/recv signatures look like, esp. sync/async. faillible, etc.

3. How to bridge Rust's Future & Waker mechanism?

Typically, each receiver would consume elements until there are no more and register a waker on that cell. Once a sender puts a new element in that cell, it can wake up all the wakers so that receivers can consume the new elements.

The main point here is how we can efficiently mutate the shared circular queue and reduce lock usage as much as possible.

Besides, if we allow sender to wait on channel full, we may need to register wakers for wating senders.

Reference

• https://docs.rs/async-broadcast/latest/async_broadcast/index.html
• https://docs.rs/tokio/latest/tokio/sync/broadcast/index.html
• https://docs.rs/postage/0.5.0/postage/broadcast/index.html
• https://docs.rs/broadcaster/1.0.0/broadcaster/

cc @BewareMyPower @orthur2

[tisonkun]

Different overflow policies specs for later follow-up if it's necessary:

Broadcast Channel Overflow Policies Specification

This document outlines common strategies for handling the "Slow Receiver Problem" in broadcast channels, where the producer's rate exceeds a consumer's processing rate.

1. Tail Drop (Current Implementation in feat: impl broadcast channel #90)

   • Philosophy: "Real-time priority." Old data is less valuable than new data.
   • Behavior: The sender never blocks. If the buffer is full, the oldest message is overwritten.
   • Consumer Impact: Slow consumers detect a gap in the sequence and receive a Lagged(count) error, forcing them to skip to the latest available message.
   • Pros: Zero impact on the sender or fast consumers; high throughput; predictable memory usage.
   • Cons: Data loss for slow consumers.
   • Ecosystems: Rust (tokio::sync::broadcast, async-broadcast), Unix Sockets.

2. Strict Backpressure (Block Sender)

   • Philosophy: "Data consistency priority." No message is ever lost.
   • Behavior: The sender blocks (suspends) until all consumers have available capacity.
   • Consumer Impact: No data loss.
   • Pros: Guaranteed delivery to all subscribers.
   • Cons: Head-of-Line Blocking. A single slow consumer reduces the entire system's throughput to its speed, potentially causing a deadlock or system-wide slowdown.
   • Ecosystems: Java (LMAX Disruptor), Go (Naive channel patterns).

3. Drop Newest (Reject Write)

   • Philosophy: "Stability priority." Existing buffered data is critical; do not overwrite it.
   • Behavior: If the buffer is full, the sender either fails immediately (returns error) or the new message is silently dropped.
   • Consumer Impact: Consumers process old data at their own pace but miss the latest updates.
   • Pros: Preserves historical context (e.g., logs leading up to a crash).
   • Cons: Loss of recent events; sender must handle write failures.
   • Ecosystems: .NET (System.Threading.Channels), Network routers (AQM).

4. Unbounded (Grow)

   • Philosophy: "Availability priority." Assume temporary bursts will be consumed eventually.
   • Behavior: The buffer grows dynamically to accommodate all messages.
   • Consumer Impact: No immediate data loss or errors.
   • Pros: Handles bursty traffic well without blocking or dropping.
   • Cons: Risk of Out-Of-Memory (OOM) crashes if a consumer is permanently slow. Unpredictable latency.
   • Ecosystems: Erlang/Elixir (Mailboxes), Python asyncio (Queue).

[tisonkun]

In short, we can have three level 1 policies:

1. unbouned
2. overflow the current impl
3. backpressure - with a level 2 policy to drop the new message or block until the slowest receivers move forward

Option 1 requires an unlimited growable buffer and properly drops the head when the last receiver moves forward.

Option 3 requires the sender to know whether there is any receiver awaiting, and perhaps the sender needs to await and being waken up.