Rust Concurrency Cheat Sheet

• Safety
• Overview
• Futures
• Tasks and threads
• Streams
• Share state
• Marker traits
• Concurrency models
• Terminology
• References

Safety

Rust ensures data race safety through the type system (Send and Sync marker traits) as well as the ownership and borrowing rules: it is not allowed to alias a mutable reference, so it is not possible to perform a data race.

Overview

	Problem
Parallelism	Multi-core utilization
Concurrency	Single-core idleness

	Solution	Primitive	Type	Description	Examples
Parallelism	Multithreading	Thread	T: Send	Do work simultaneously on different threads	std::thread::spawn
Concurrency	Single-threaded concurrency	Future	Future	Futures run concurrently on the same thread	futures::future::join, futures::join, tokio::join
Concurrency +Parallelism	Multithreaded concurrency	Task	T: Future + Send	Tasks run concurrently to other tasks; the task may run on the current thread, or it may be sent to a different thread	async_std::task::spawn, tokio::task::spawn

Futures

pub trait Future {
    type Output;
    fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output>;
}

pub enum Poll<T> {
    Ready(T),
    Pending,
}

• Future has to be polled (by the executor) to resume where it last yielded and make progress (async is lazy)
• &mut Self contains state (state machine)
• Pin the memory location because the future contains self-referential data
• Context contains the Waker to notify the executor that progress can be made
• async/await on futures is implemented by generators
• async fn and async blocks return impl Future<Output = T>
• calling .await attempts to resolve the Future: if the Future is blocked, it yields control; if progress can be made, the Future resumes

Futures form a tree of futures. The leaf futures commmunicate with the executor. The root future of a tree is called a task.

Tasks and threads

Computation	Examples
Lightweight (e.g. <100 ms)	async_std::task::spawn, tokio::task::spawn
Extensive (e.g. >100 ms or I/O bound)	async_std::task::spawn_blocking, tokio::task::spawn_blocking
Massive (e.g. running forever or CPU-bound)	std::thread::spawn

Streams

pub trait Stream {
    type Item;
    fn poll_next(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Option<Self::Item>>;

    fn size_hint(&self) -> (usize, Option<usize>) { ... }
}

• Stream<Item = T> is an asynchronous version of Iterator<Item = T>, i.e., it does not block between each item yield

	Parallelism
Iterator	rayon
Stream	tokio, parallel-stream

Operation	Relationship	Examples
Create		futures::stream::iter, futures::stream::once, futures::stream::repeat, futures::stream::repeat_with, async_stream::stream
Create (via channels)		futures::channel::mpsc::Receiver, tokio_stream::wrappers::ReceiverStream
Iterate		futures::stream::StreamExt::next, futures::stream::StreamExt::for_each, futures::stream::StreamExt::for_each_concurrent
Transform	1-1	futures::stream::StreamExt::map, futures::stream::StreamExt::then, futures::stream::StreamExt::flatten
Filter	1-1	futures::stream::StreamExt::filter, futures::stream::StreamExt::take, futures::stream::StreamExt::skip
Buffer	1-1	futures::stream::StreamExt::buffered, futures::stream::StreamExt::buffer_unordered
Combine	n-1	futures::stream::StreamExt::chain, futures::stream::StreamExt::zip, tokio_stream::StreamExt::merge, tokio_stream::StreamMap, tokio::select
Split	1-n	futures::channel::oneshot::Sender::send, async_std::channel::Sender::send

Share state

	Threads	Tasks
channel	std::sync::mpsc (Send), crossbeam::channel (Send, Sync)	futures::channel::oneshot, tokio::sync::mpsc, tokio::sync::oneshot, tokio::sync::broadcast, tokio::sync::watch, async_channel::unbounded, async_channel::bounded, oneshot
mutex	std::sync::Mutex	tokio::sync::Mutex

Marker traits

• Send: safe to send it to another thread
• Sync: safe to share between threads (T is Sync if and only if &T is Send)

Type	Send	Sync	Owners	Interior mutability
Rc<T>	No	No	multiple	No
Arc<T>	Yes (if T is Send and Sync)	Yes (if T is Send and Sync)	multiple	No
Box<T>	Yes (if T is Send)	Yes (if T is Sync)	single	No
Mutex<T>	Yes (if T is Send)	Yes (if T is Send)	single	Yes
RwLock<T>	Yes (if T is Send)	Yes (if T is Send and Sync)	single	Yes
MutexGuard<'a, T: 'a>	No	Yes (if T is Sync)	single	Yes
Cell<T>	Yes (if T is Send	No	single	Yes
RefCell<T>	Yes (if T is Send)	No	single	Yes

Concurrency models

Model	Description
shared memory	threads operate on regions of shared memory
worker pools	many identical threads receive jobs from a shared job queue
actors	many different job queues, one for each actor; actors communicate exclusively by exchanging messages

Runtime	Description
tokio (multithreaded)	thread pool with work-stealing scheduler: each processor maintains its own run queue; idle processor checks sibling processor run queues, and attempts to steal tasks from them
actix_rt	single-threaded async runtime; futures are !Send
actix	actor framework
actix-web	constructs an application instance for each thread; application data must be constructed multiple times or shared between threads

Terminology

Shared reference: An immutable reference (&T); can be copied/cloned.

Exclusive reference: A mutable reference (&mut T); cannot be copied/cloned.

Aliasing: Having several immutable references.

Mutability: Having one mutable reference.

Data race: Two or more threads concurrently accessing a location of memory; one or more of them is a write; one or more of them is unsynchronized.

Race condition: The condition of a software system where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events.

Deadlock: Any situation in which no member of some group of entities can proceed because each waits for another member, including itself, to take action.

Heisenbug: A heisenbug is a software bug that seems to disappear or alter its behavior when one attempts to study it. For example, time-sensitive bugs such as race conditions may not occur when the program is slowed down by single-stepping source lines in the debugger.

Marker trait: Used to give the compiler certain guarantees (see std::marker).

Thread: A native OS thread.

Green threads (or virtual threads): Threads that are scheduled by a runtime library or virtual machine (VM) instead of natively by the underlying operating system (OS).

Context switch: The process of storing the state of a process or thread, so that it can be restored and resume execution at a later point.

Synchronous I/O: blocking I/O.

Asynchronous I/O: non-blocking I/O.

Future (cf. promise): A single value produced asynchronously.

Stream: A series of values produced asynchronously.

Sink: Write data asynchronously.

Task: An asynchronous green thread.

Channel: Enables communication between threads or tasks.

Mutex (mutual exclusion): Shares data between threads or tasks.

Interior mutability: A design pattern that allows mutating data even when there are immutable references to that data.

Executor: Runs asynchronous tasks.

Generator: Used internally by the compiler. Can stop (or yield) its execution and resume (poll) afterwards from its last yield point by inspecting the previously stored state in self.

Reactor: Leaf futures register event sources with the reactor.

Runtime: Bundles a reactor and an executor.

polling: Attempts to resolve the future into a final value.

io_uring: A Linux kernel system call interface for storage device asynchronous I/O operations.

CPU-bound: Refers to a condition in which the time it takes to complete a computation is determined principally by the speed of the CPU.

I/O bound: Refers to a condition in which the time it takes to complete a computation is determined principally by the period spent waiting for input/output operations to be completed. This is the opposite of a task being CPU bound.

References

• Steve Klabnik and Carol Nichols, The Rust Programming Language
• Jon Gjengset, Rust for Rustaceans
• The Rustonomicon
• Asynchronous Programming in Rust
• Tokio tutorial
• Tokio's work-stealing scheduler
• Actix user guide