use std::{
collections::HashMap,
future::Future,
hash::Hash,
sync::{Arc, Weak},
time::{Duration, Instant},
};
use parking_lot::{Mutex, RwLock};
use tokio::sync::Notify;
pub type SharedResult<V, E> = Arc<Result<V, E>>;
enum FlightState<V, E> {
Running,
Complete(SharedResult<V, E>),
Aborted,
}
struct Flight<V, E> {
state: Mutex<FlightState<V, E>>,
changed: Notify,
}
impl<V, E> Flight<V, E> {
fn new() -> Self {
Self {
state: Mutex::new(FlightState::Running),
changed: Notify::new(),
}
}
async fn wait(&self) -> Option<SharedResult<V, E>> {
loop {
let changed = self.changed.notified();
tokio::pin!(changed);
changed.as_mut().enable();
{
let state = self.state.lock();
match &*state {
FlightState::Running => {}
FlightState::Complete(result) => return Some(Arc::clone(result)),
FlightState::Aborted => return None,
}
}
changed.await;
}
}
fn publish(&self, result: SharedResult<V, E>) {
let mut state = self.state.lock();
debug_assert!(matches!(*state, FlightState::Running));
*state = FlightState::Complete(result);
}
fn abort(&self) -> bool {
let mut state = self.state.lock();
if matches!(*state, FlightState::Running) {
*state = FlightState::Aborted;
true
} else {
false
}
}
fn wake_waiters(&self) {
self.changed.notify_waiters();
}
}
pub struct Group<K, V, E> {
flights: Mutex<HashMap<K, Weak<Flight<V, E>>>>,
}
impl<K, V, E> Group<K, V, E> {
#[must_use]
pub fn new() -> Self {
Self {
flights: Mutex::new(HashMap::new()),
}
}
}
impl<K, V, E> Group<K, V, E>
where
K: Eq + Hash + Clone,
{
pub async fn do_call_shared<F, Fut>(&self, key: K, operation: F) -> SharedResult<V, E>
where
F: FnOnce() -> Fut,
Fut: Future<Output = Result<V, E>>,
{
let mut operation = Some(operation);
loop {
let (flight, is_leader) = self.acquire(&key);
if !is_leader {
if let Some(result) = flight.wait().await {
return result;
}
self.remove_if_current(&key, &flight);
continue;
}
let guard = LeaderGuard::new(self, &key, flight);
let operation = operation
.take()
.expect("singleflight operation can only be executed once");
let result = operation().await;
return guard.complete(result);
}
}
pub async fn do_call<F, Fut>(&self, key: K, operation: F) -> Result<V, E>
where
V: Clone,
E: Clone,
F: FnOnce() -> Fut,
Fut: Future<Output = Result<V, E>>,
{
let result = self.do_call_shared(key, operation).await;
match result.as_ref() {
Ok(value) => Ok(value.clone()),
Err(error) => Err(error.clone()),
}
}
fn acquire(&self, key: &K) -> (Arc<Flight<V, E>>, bool) {
let mut flights = self.flights.lock();
if let Some(flight) = flights.get(key).and_then(Weak::upgrade) {
return (flight, false);
}
let flight = Arc::new(Flight::new());
flights.insert(key.clone(), Arc::downgrade(&flight));
(flight, true)
}
fn remove_if_current(&self, key: &K, flight: &Arc<Flight<V, E>>) {
let mut flights = self.flights.lock();
let is_current = flights
.get(key)
.is_some_and(|current| std::ptr::eq(current.as_ptr(), Arc::as_ptr(flight)));
if is_current {
flights.remove(key);
}
}
fn has_active(&self, key: &K) -> bool {
self.flights
.lock()
.get(key)
.and_then(Weak::upgrade)
.is_some()
}
#[cfg(test)]
fn in_flight_len(&self) -> usize {
self.flights.lock().len()
}
}
impl<K, V, E> Default for Group<K, V, E> {
fn default() -> Self {
Self::new()
}
}
struct LeaderGuard<'a, K, V, E>
where
K: Eq + Hash + Clone,
{
group: &'a Group<K, V, E>,
key: &'a K,
flight: Arc<Flight<V, E>>,
armed: bool,
}
impl<'a, K, V, E> LeaderGuard<'a, K, V, E>
where
K: Eq + Hash + Clone,
{
fn new(group: &'a Group<K, V, E>, key: &'a K, flight: Arc<Flight<V, E>>) -> Self {
Self {
group,
key,
flight,
armed: true,
}
}
fn complete(mut self, result: Result<V, E>) -> SharedResult<V, E> {
let result = Arc::new(result);
self.flight.publish(Arc::clone(&result));
self.group.remove_if_current(self.key, &self.flight);
self.flight.wake_waiters();
self.armed = false;
result
}
}
impl<K, V, E> Drop for LeaderGuard<'_, K, V, E>
where
K: Eq + Hash + Clone,
{
fn drop(&mut self) {
if self.armed && self.flight.abort() {
self.group.remove_if_current(self.key, &self.flight);
self.flight.wake_waiters();
}
}
}
struct CacheEntry<V> {
inserted_at: Instant,
value: Arc<V>,
}
struct CacheSlot<V> {
revision: u64,
entry: Option<CacheEntry<V>>,
}
struct CacheState<K, V> {
clear_revision: u64,
slots: HashMap<K, CacheSlot<V>>,
}
impl<K, V> CacheState<K, V> {
fn new() -> Self {
Self {
clear_revision: 0,
slots: HashMap::new(),
}
}
}
#[derive(Clone, Copy)]
struct CacheVersion {
clear_revision: u64,
key_revision: u64,
}
fn next_revision(revision: u64) -> u64 {
let revision = revision.wrapping_add(1);
if revision == 0 { 1 } else { revision }
}
struct CacheAttempt<'a, K, V>
where
K: Eq + Hash + Clone,
{
cache: &'a RwLock<CacheState<K, V>>,
key: &'a K,
version: CacheVersion,
armed: bool,
}
impl<'a, K, V> CacheAttempt<'a, K, V>
where
K: Eq + Hash + Clone,
{
fn new(cache: &'a RwLock<CacheState<K, V>>, key: &'a K) -> Self {
let version = {
let cache = cache.read();
CacheVersion {
clear_revision: cache.clear_revision,
key_revision: cache.slots.get(key).map_or(0, |slot| slot.revision),
}
};
Self {
cache,
key,
version,
armed: true,
}
}
fn cache(mut self, value: Arc<V>) {
let mut cache = self.cache.write();
if cache.clear_revision == self.version.clear_revision {
match cache.slots.get_mut(self.key) {
Some(slot) if slot.revision == self.version.key_revision => {
slot.revision = 0;
slot.entry = Some(CacheEntry {
inserted_at: Instant::now(),
value,
});
}
None if self.version.key_revision == 0 => {
cache.slots.insert(
self.key.clone(),
CacheSlot {
revision: 0,
entry: Some(CacheEntry {
inserted_at: Instant::now(),
value,
}),
},
);
}
Some(_) | None => {
Self::remove_marker(&mut cache, self.key);
}
}
} else {
Self::remove_marker(&mut cache, self.key);
}
self.armed = false;
}
fn remove_marker(cache: &mut CacheState<K, V>, key: &K) {
if cache
.slots
.get(key)
.is_some_and(|slot| slot.revision != 0 && slot.entry.is_none())
{
cache.slots.remove(key);
}
}
}
impl<K, V> Drop for CacheAttempt<'_, K, V>
where
K: Eq + Hash + Clone,
{
fn drop(&mut self) {
if self.armed {
Self::remove_marker(&mut self.cache.write(), self.key);
}
}
}
pub struct CachedGroup<K, V, E> {
flight: Group<K, Arc<V>, Arc<E>>,
cache: RwLock<CacheState<K, V>>,
ttl: Duration,
}
impl<K, V, E> CachedGroup<K, V, E> {
#[must_use]
pub fn new(ttl: Duration) -> Self {
Self {
flight: Group::new(),
cache: RwLock::new(CacheState::new()),
ttl,
}
}
#[must_use]
pub const fn ttl(&self) -> Duration {
self.ttl
}
}
impl<K, V, E> CachedGroup<K, V, E>
where
K: Eq + Hash + Clone,
{
pub async fn get_shared<F, Fut>(&self, key: K, operation: F) -> Result<Arc<V>, Arc<E>>
where
F: FnOnce() -> Fut,
Fut: Future<Output = Result<V, E>>,
{
if let Some(value) = self.cached(&key) {
return Ok(value);
}
let cache_key = key.clone();
let result = self
.flight
.do_call_shared(key, move || async move {
if let Some(value) = self.cached(&cache_key) {
return Ok(value);
}
let cache_attempt = CacheAttempt::new(&self.cache, &cache_key);
match operation().await {
Ok(value) => {
let value = Arc::new(value);
cache_attempt.cache(Arc::clone(&value));
Ok(value)
}
Err(error) => Err(Arc::new(error)),
}
})
.await;
match result.as_ref() {
Ok(value) => Ok(Arc::clone(value)),
Err(error) => Err(Arc::clone(error)),
}
}
pub async fn get<F, Fut>(&self, key: K, operation: F) -> Result<V, E>
where
V: Clone,
E: Clone,
F: FnOnce() -> Fut,
Fut: Future<Output = Result<V, E>>,
{
match self.get_shared(key, operation).await {
Ok(value) => Ok(value.as_ref().clone()),
Err(error) => Err(error.as_ref().clone()),
}
}
pub fn invalidate(&self, key: &K) -> bool {
let has_active = self.flight.has_active(key);
let mut cache = self.cache.write();
if !has_active {
return cache
.slots
.remove(key)
.and_then(|slot| slot.entry)
.is_some();
}
let slot = cache.slots.entry(key.clone()).or_insert(CacheSlot {
revision: 0,
entry: None,
});
slot.revision = next_revision(slot.revision);
let was_cached = slot.entry.take().is_some();
drop(cache);
if !self.flight.has_active(key) {
CacheAttempt::remove_marker(&mut self.cache.write(), key);
}
was_cached
}
pub fn clear(&self) {
let mut cache = self.cache.write();
cache.clear_revision = next_revision(cache.clear_revision);
cache.slots.clear();
}
pub fn purge_expired(&self) -> usize {
let (expired, markers) = {
let mut cache = self.cache.write();
let mut expired = 0;
let mut markers = Vec::new();
cache.slots.retain(|key, slot| {
if slot.revision != 0 {
markers.push(key.clone());
return true;
}
let fresh = slot
.entry
.as_ref()
.is_some_and(|entry| entry.inserted_at.elapsed() < self.ttl);
expired += usize::from(!fresh);
fresh
});
(expired, markers)
};
for key in markers {
if !self.flight.has_active(&key) {
CacheAttempt::remove_marker(&mut self.cache.write(), &key);
}
}
expired
}
fn cached(&self, key: &K) -> Option<Arc<V>> {
let cache = self.cache.read();
cache
.slots
.get(key)
.and_then(|slot| slot.entry.as_ref())
.filter(|entry| entry.inserted_at.elapsed() < self.ttl)
.map(|entry| Arc::clone(&entry.value))
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::{
convert::Infallible,
future::pending,
sync::atomic::{AtomicUsize, Ordering},
};
use tokio::{
sync::{Barrier, Notify},
task::JoinSet,
time::{sleep, timeout},
};
#[tokio::test(flavor = "multi_thread", worker_threads = 4)]
async fn coalesces_concurrent_calls_for_the_same_key() {
const CALLERS: usize = 64;
let group = Arc::new(Group::<&str, usize, Infallible>::new());
let barrier = Arc::new(Barrier::new(CALLERS));
let executions = Arc::new(AtomicUsize::new(0));
let mut calls = JoinSet::new();
for _ in 0..CALLERS {
let group = Arc::clone(&group);
let barrier = Arc::clone(&barrier);
let executions = Arc::clone(&executions);
calls.spawn(async move {
barrier.wait().await;
group
.do_call("channel", || async move {
executions.fetch_add(1, Ordering::SeqCst);
sleep(Duration::from_millis(25)).await;
Ok(42)
})
.await
});
}
while let Some(result) = calls.join_next().await {
assert_eq!(result.unwrap(), Ok(42));
}
assert_eq!(executions.load(Ordering::SeqCst), 1);
assert_eq!(group.in_flight_len(), 0);
}
#[tokio::test]
async fn operations_for_different_keys_are_independent() {
let group = Arc::new(Group::<&str, usize, Infallible>::new());
let first_started = Arc::new(Notify::new());
let release_first = Arc::new(Notify::new());
let first = {
let group = Arc::clone(&group);
let first_started = Arc::clone(&first_started);
let release_first = Arc::clone(&release_first);
tokio::spawn(async move {
group
.do_call("first", || async move {
first_started.notify_one();
release_first.notified().await;
Ok(1)
})
.await
})
};
first_started.notified().await;
let second = timeout(
Duration::from_millis(100),
group.do_call("second", || async { Ok(2) }),
)
.await
.unwrap();
assert_eq!(second, Ok(2));
release_first.notify_one();
assert_eq!(first.await.unwrap(), Ok(1));
}
#[tokio::test]
async fn shares_errors() {
let group = Arc::new(Group::<&str, (), &'static str>::new());
let started = Arc::new(Barrier::new(2));
let leader = {
let group = Arc::clone(&group);
let started = Arc::clone(&started);
tokio::spawn(async move {
group
.do_call("key", || async move {
started.wait().await;
sleep(Duration::from_millis(10)).await;
Err("failed")
})
.await
})
};
started.wait().await;
let follower = group.do_call("key", || async { Ok(()) });
assert_eq!(follower.await, Err("failed"));
assert_eq!(leader.await.unwrap(), Err("failed"));
}
#[tokio::test]
async fn shared_api_supports_non_clone_results() {
#[derive(Debug, PartialEq)]
struct NonClone(usize);
let group = Arc::new(Group::<&str, NonClone, NonClone>::new());
let release = Arc::new(Notify::new());
let started = Arc::new(Notify::new());
let leader = {
let group = Arc::clone(&group);
let release = Arc::clone(&release);
let started = Arc::clone(&started);
tokio::spawn(async move {
group
.do_call_shared("key", || async move {
started.notify_one();
release.notified().await;
Ok(NonClone(7))
})
.await
})
};
started.notified().await;
let follower = {
let group = Arc::clone(&group);
tokio::spawn(async move {
group
.do_call_shared("key", || async { Err(NonClone(9)) })
.await
})
};
tokio::task::yield_now().await;
release.notify_one();
let leader_result = leader.await.unwrap();
let follower_result = follower.await.unwrap();
assert!(Arc::ptr_eq(&leader_result, &follower_result));
assert_eq!(leader_result.as_ref(), &Ok(NonClone(7)));
}
#[tokio::test]
async fn recovers_when_the_leader_is_cancelled() {
let group = Arc::new(Group::<&str, usize, Infallible>::new());
let started = Arc::new(Notify::new());
let recovery_executions = Arc::new(AtomicUsize::new(0));
let leader = {
let group = Arc::clone(&group);
let started = Arc::clone(&started);
tokio::spawn(async move {
group
.do_call("key", || async move {
started.notify_one();
pending::<Result<usize, Infallible>>().await
})
.await
})
};
started.notified().await;
let follower = {
let group = Arc::clone(&group);
let recovery_executions = Arc::clone(&recovery_executions);
tokio::spawn(async move {
group
.do_call("key", || async move {
recovery_executions.fetch_add(1, Ordering::SeqCst);
Ok(11)
})
.await
})
};
tokio::task::yield_now().await;
leader.abort();
assert!(leader.await.unwrap_err().is_cancelled());
assert_eq!(
timeout(Duration::from_secs(1), follower)
.await
.unwrap()
.unwrap(),
Ok(11)
);
assert_eq!(recovery_executions.load(Ordering::SeqCst), 1);
assert_eq!(group.in_flight_len(), 0);
}
#[tokio::test]
async fn cancellation_without_waiters_removes_the_flight() {
let group = Arc::new(Group::<&str, usize, Infallible>::new());
let started = Arc::new(Notify::new());
let leader = {
let group = Arc::clone(&group);
let started = Arc::clone(&started);
tokio::spawn(async move {
group
.do_call("key", || async move {
started.notify_one();
pending::<Result<usize, Infallible>>().await
})
.await
})
};
started.notified().await;
leader.abort();
assert!(leader.await.unwrap_err().is_cancelled());
assert_eq!(group.in_flight_len(), 0);
assert_eq!(group.do_call("key", || async { Ok(12) }).await, Ok(12));
}
#[tokio::test]
async fn recovers_when_the_leader_panics() {
let group = Arc::new(Group::<&str, usize, Infallible>::new());
let started = Arc::new(Notify::new());
let leader = {
let group = Arc::clone(&group);
let started = Arc::clone(&started);
tokio::spawn(async move {
group
.do_call("key", || async move {
started.notify_one();
sleep(Duration::from_millis(10)).await;
panic!("leader failed");
})
.await
})
};
started.notified().await;
let follower = {
let group = Arc::clone(&group);
tokio::spawn(async move { group.do_call("key", || async { Ok(13) }).await })
};
assert!(leader.await.unwrap_err().is_panic());
assert_eq!(follower.await.unwrap(), Ok(13));
assert_eq!(group.in_flight_len(), 0);
}
#[tokio::test]
async fn cached_group_coalesces_and_honors_ttl() {
let group = Arc::new(CachedGroup::<&str, usize, Infallible>::new(
Duration::from_millis(250),
));
let executions = Arc::new(AtomicUsize::new(0));
let barrier = Arc::new(Barrier::new(8));
let mut calls = JoinSet::new();
for _ in 0..8 {
let group = Arc::clone(&group);
let executions = Arc::clone(&executions);
let barrier = Arc::clone(&barrier);
calls.spawn(async move {
barrier.wait().await;
group
.get("key", || async move {
executions.fetch_add(1, Ordering::SeqCst);
sleep(Duration::from_millis(5)).await;
Ok(17)
})
.await
});
}
while let Some(result) = calls.join_next().await {
assert_eq!(result.unwrap(), Ok(17));
}
assert_eq!(executions.load(Ordering::SeqCst), 1);
assert_eq!(group.get("key", || async { Ok(99) }).await, Ok(17));
assert_eq!(executions.load(Ordering::SeqCst), 1);
sleep(Duration::from_millis(275)).await;
assert_eq!(group.purge_expired(), 1);
let executions_for_refresh = Arc::clone(&executions);
assert_eq!(
group
.get("key", || async move {
executions_for_refresh.fetch_add(1, Ordering::SeqCst);
Ok(23)
})
.await,
Ok(23)
);
assert_eq!(executions.load(Ordering::SeqCst), 2);
}
#[tokio::test]
async fn cached_shared_api_avoids_cloning_values() {
#[derive(Debug, PartialEq)]
struct NonClone(usize);
let group = CachedGroup::<&str, NonClone, NonClone>::new(Duration::from_secs(60));
let fetched = group
.get_shared("key", || async { Ok(NonClone(31)) })
.await
.unwrap();
let cached = group
.get_shared("key", || async { Err(NonClone(32)) })
.await
.unwrap();
assert!(Arc::ptr_eq(&fetched, &cached));
assert_eq!(fetched.as_ref(), &NonClone(31));
}
#[tokio::test]
async fn invalidation_wins_against_an_in_flight_result() {
let group = Arc::new(CachedGroup::<&str, usize, Infallible>::new(
Duration::from_secs(60),
));
let started = Arc::new(Notify::new());
let release = Arc::new(Notify::new());
let first = {
let group = Arc::clone(&group);
let started = Arc::clone(&started);
let release = Arc::clone(&release);
tokio::spawn(async move {
group
.get("key", || async move {
started.notify_one();
release.notified().await;
Ok(37)
})
.await
})
};
started.notified().await;
assert!(!group.invalidate(&"key"));
release.notify_one();
assert_eq!(first.await.unwrap(), Ok(37));
assert_eq!(group.get("key", || async { Ok(41) }).await, Ok(41));
assert_eq!(group.get("key", || async { Ok(43) }).await, Ok(41));
}
#[tokio::test]
async fn clear_wins_against_in_flight_results() {
let group = Arc::new(CachedGroup::<&str, usize, Infallible>::new(
Duration::from_secs(60),
));
let started = Arc::new(Notify::new());
let release = Arc::new(Notify::new());
let first = {
let group = Arc::clone(&group);
let started = Arc::clone(&started);
let release = Arc::clone(&release);
tokio::spawn(async move {
group
.get("key", || async move {
started.notify_one();
release.notified().await;
Ok(47)
})
.await
})
};
started.notified().await;
group.clear();
release.notify_one();
assert_eq!(first.await.unwrap(), Ok(47));
assert_eq!(group.get("key", || async { Ok(53) }).await, Ok(53));
assert_eq!(group.get("key", || async { Ok(59) }).await, Ok(53));
}
#[tokio::test]
async fn cached_group_does_not_cache_errors() {
let group = CachedGroup::<&str, usize, &'static str>::new(Duration::from_secs(60));
assert_eq!(
group.get("key", || async { Err("temporary") }).await,
Err("temporary")
);
assert_eq!(group.get("key", || async { Ok(29) }).await, Ok(29));
}
}