Implementing a Simple Channel and Exploring Tokio's Channel Implementation

The core data structure for concurrent programming in Golang is the channel. Its central idea is to share memory by communicating rather than communicate by sharing memory. Channels are indeed useful and avoid the need to write various complex communication primitives directly. Rust naturally has corresponding implementations as well, and Tokio’s channel implementation is extremely clever and well worth studying. This article briefly introduces the basic concepts of channels, then implements a minimal mpsc unbuffered channel, and finally examines Tokio’s channel implementation.

Minimal Rust Channel Implementation

This section implements a minimal channel. This channel has an unlimited buffer, allows multiple writers, and never blocks writes to the channel. However, if the channel is empty, consumers attempting to consume data from it will be blocked. In other words, this is an mpsc unbuffered channel. This section refers to Chen Tian: Rust Programming First Course, Lesson 35. Chen Tian’s lesson is highly accessible and uses TDD to complete the entire channel design step by step, starting with interface test cases. I will take the same approach here, using TDD and aligning with the standard library’s mspc interface.

Channel Features and Implementation

I expect to implement the following features:

  1. The sender produces data, and the receiver consumes it.
  2. Multiple senders are allowed.
  3. The channel is empty.
  4. All senders exit.
  5. The receiver exits.

The Sender Produces Data, and the Receiver Consumes It

Again using TDD, I will first consider the features I need, assume they have already been implemented, and write the corresponding tests.

1
2
3
4
5
6
#[test]
fn test_chanel_basic() {
let (mut s, mut r) = unbounded();
s.send(1).unwrap();
assert_eq!(r.recv().unwrap(), 1);
}

Calling unbounded creates a channel and returns the corresponding sender and receiver. The sender sends data with send, and the receiver receives data with recv. Why is unwrap needed? When the receiver is dropped or all senders are dropped, the corresponding send and receive operations need to return an Error.

For simplicity, I can use VecDeque directly. Since both the sender and receiver need to modify this buffer, it needs a lock. Since it must be shared between threads, the sender and receiver need to hold Shared through Arc.

1
2
3
4
5
6
7
8
9
10
11
struct Shared<T> {
inner: Mutex<VecDeque<T>>,
}

struct Sender<T> {
inner: Arc<Shared<T>>,
}

struct Receiver<T> {
inner: Arc<Shared<T>>,
}

Allowing Multiple Senders

Calling unbounded provides only one sender. Supporting multiple senders means that Sender needs to implement Clone.

1
2
3
4
5
6
7
8
9
10
11
12
13
#[test]
fn test_clone() {
let (mut s, mut r) = unbounded();
let mut s1 = s.clone();
let mut s2 = s.clone();
s.send(1).unwrap();
s1.send(2).unwrap();
s2.send(3).unwrap();

assert_eq!(1, r.recv().unwrap());
assert_eq!(2, r.recv().unwrap());
assert_eq!(3, r.recv().unwrap());
}

The Channel Is Empty

When the channel is empty, consumers need to be blocked. How, then, should a consumer be awakened? With Condvar! Condvar can block the current thread and wake it when an event occurs. This waiting consumes no additional CPU. Condvar’s wait takes a MutexGuard as its argument. It releases the lock while waiting and reacquires it when notify or notify_all is called, so users need not worry about the lock. This is quite interesting, and the implementation would be worth studying in detail later.

1
2
3
4
struct Shared<T> {
inner: Mutex<VecDeque<T>>,
available: Condvar,
}

How should the test be written? I can have the receiver consume continuously. After it finishes one batch of data, the sender waits for a short period before sending another batch, and the receiver can then continue consuming. Because there is only one receiver, implementing Iterator for it is very useful.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#[test]
fn test_receiver_block() {
let (mut s, mut r) = unbounded();

thread::spawn(move || {
for (idx, i) in r.into_iter().enumerate() {
assert_eq!(idx, i)
}
});

for i in 0..100usize {
s.send(i).unwrap();
}

thread::sleep(Duration::from_millis(1));

for i in 100..200usize {
s.send(i).unwrap();
}
}

All Senders Exit

When all senders have exited, the receiver’s recv needs to return an error. A simple approach is to store the number of senders. When a new sender is created or cloned, increment the count by 1; when a sender is dropped, decrement it by 1. I therefore need to implement a custom Drop method for Sender and notify any waiting receiver to exit when the sender count reaches 0. Below is the final structure. Although it is not especially efficient, it is a working version for ordinary thread-level shared channels.

1
2
3
4
5
6
struct Shared<T> {
inner: Mutex<VecDeque<T>>,
available: Condvar,
sender_cnt: AtomicUsize,
receiver_cnt: AtomicUsize,
}

The test can be written as follows.

1
2
3
4
5
6
#[test]
fn test_no_send() {
let (s, r) = unbounded();
drop(s);
assert!(r.recv().is_err());
}

The Receiver Exits

As above, when the receiver exits, its receiver_cnt needs to be decreased by -1. When a sender calls send and finds that all receivers have exited, it also needs to return an error. The test is as follows.

1
2
3
4
5
#[test]
fn test_no_receiver() {
let (s, _) = unbounded();
assert!(s.send().is_err());
}

For more details, see Chen Tian’s Geektime course. I can also extend this idea: to build a rough mpsc bounded channel, I only need to add one more condvar. One condvar indicates that the buffer contains data to read, while the other indicates that data can be written. However, condvar operates at too coarse a granularity. I could use a semaphore instead: a sender wanting to send data would need to acquire a permit before sending, or else wait.

An Introduction to Tokio’s Channel Implementation

The channel described above is only a toy channel. Production environments impose much higher performance requirements on channels.

Underlying Data Structure

Tokio’s channel implementation is extremely clever. The channel is backed by a linked list, and each element in the list is called a block. Each block can hold multiple channel elements. When reading data, the channel reads from the head of the list. Once a block has been fully read, it is reset and moved to the tail of the list, saving memory-allocation overhead. When writing data, the channel writes from the tail of the list. If the current block does not have enough capacity, it allocates a new block or uses a reset block. The overall structure is shown below. The code contains many details worth studying.

tokio-channel-implemantation

Unbounded Channel

tokio-channel-waker

Writing Data

For a sender to write data to the channel, it essentially operates on the underlying data structure. It mainly finds the appropriate position in the block currently available for writing and writes the data there. After the data is written, if a receiver is waiting to read data, its waker is used to wake that receiver.

  • Sender implements Clone, and all these senders can be safely transferred to other threads. If data is sent concurrently, is a lock needed?

    The answer is no. Each sender only needs to know where it should write. In other words, the next write position is shared through tail_position, a variable of type AtomiUsize, and each write only needs fetch_add + 1.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    /// List queue transmit handle.
    pub(crate) struct Tx<T> {
    /// Tail in the `Block` mpmc list.
    block_tail: AtomicPtr<Block<T>>,

    /// Position to push the next message. This references a block and offset
    /// into the block.
    tail_position: AtomicUsize,
    }
  • Waking the receiver

    When a receiver cannot obtain data, it registers a waker with the underlying channel. When data is available to read, this waker wakes the receiver that registered it.

    1
    2
    3
    4
    pub(crate) struct AtomicWaker {
    state: AtomicUsize,
    waker: UnsafeCell<Option<Waker>>,
    }

Reading Data

The receiver attempts to read data from the channel. If it can read data, it exits; otherwise, it registers its waker with the channel.

Bounded Channel

Compared with an unbounded channel, writes to a bounded channel may also block. Here I need to focus on how a sender is awakened when writing becomes possible and how a receiver is awakened when reading becomes possible. The logic for waking a receiver is broadly the same as for an unbounded channel, so I will skip it for now. How is a sender blocked? Briefly, this is done with a semaphore. A sender wanting to send data must acquire a permit that allows it to send; otherwise, it can only block. Compared with an unbounded channel, after a bounded receiver consumes data, it must also add a permit and wake a sender in the waitlist that is waiting to write data. This is only a broad overview of the implementation; I have not explored it deeply and will add more when I have time.

Summary

This article briefly introduced how to implement a simple channel based on VecDeque. This channel operates at the thread level and uses a coarse-grained lock, so its performance is quite poor. Tokio’s channel implementation offers many valuable ideas, and its code is well worth studying closely.

Author: suikammd
Link: https://suikammd.github.io/2021/11/20/rust-simple-channel/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.