use std::{
collections::{HashMap, HashSet, VecDeque},
fmt,
future::Future,
hash::Hash,
pin::Pin,
sync::{Arc, Mutex, MutexGuard, PoisonError, Weak},
task::{Context, Poll},
};
use futures::future::{BoxFuture, FutureExt, Shared, join_all};
type BatchFuture<V, E> = BoxFuture<'static, Vec<Result<V, E>>>;
type BatchFn<K, V, E> = Arc<dyn Fn(Vec<K>) -> BatchFuture<V, E> + Send + Sync>;
type BatchOutput<V, E> = Arc<Vec<Arc<Result<V, E>>>>;
type SharedBatch<V, E> = Shared<BoxFuture<'static, BatchOutput<V, E>>>;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct LoaderConfig {
max_batch_size: usize,
max_queue: usize,
max_attempts: u8,
}
impl LoaderConfig {
#[must_use]
pub const fn new() -> Self {
Self {
max_batch_size: 1000,
max_queue: 10_000,
max_attempts: 3,
}
}
#[must_use]
pub const fn with_max_batch_size(mut self, size: usize) -> Self {
self.max_batch_size = if size == 0 { 1 } else { size };
self
}
#[must_use]
pub const fn with_max_queue(mut self, size: usize) -> Self {
self.max_queue = if size == 0 { 1 } else { size };
self
}
#[must_use]
pub const fn with_max_attempts(mut self, attempts: u8) -> Self {
self.max_attempts = if attempts == 0 { 1 } else { attempts };
self
}
#[must_use]
pub const fn max_batch_size(&self) -> usize {
self.max_batch_size
}
#[must_use]
pub const fn max_queue(&self) -> usize {
self.max_queue
}
#[must_use]
pub const fn max_attempts(&self) -> u8 {
self.max_attempts
}
}
impl Default for LoaderConfig {
fn default() -> Self {
Self::new()
}
}
enum Lookup<V, E> {
Ready(Arc<Result<V, E>>),
Pending {
shared: SharedBatch<V, E>,
index: usize,
},
Missing,
}
enum Entry<V, E> {
Pending { batch: u64, index: usize },
Ready(Arc<Result<V, E>>),
}
struct State<K, V, E> {
entries: HashMap<K, Entry<V, E>>,
queue: VecDeque<K>,
queued: HashSet<K>,
batches: HashMap<u64, SharedBatch<V, E>>,
next_batch: u64,
#[cfg(feature = "tracing")]
deduplicated: usize,
}
struct Inner<K, V, E> {
batch_fn: BatchFn<K, V, E>,
config: LoaderConfig,
state: Mutex<State<K, V, E>>,
weak: Weak<Inner<K, V, E>>,
}
pub struct Loader<K, V, E = gql::GraphQLError> {
inner: Arc<Inner<K, V, E>>,
}
impl<K, V, E> Clone for Loader<K, V, E> {
fn clone(&self) -> Self {
Self {
inner: Arc::clone(&self.inner),
}
}
}
impl<K, V, E> fmt::Debug for Loader<K, V, E> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let state = self
.inner
.state
.lock()
.unwrap_or_else(PoisonError::into_inner);
f.debug_struct("Loader")
.field("max_batch_size", &self.inner.config.max_batch_size)
.field("queued", &state.queue.len())
.field("in_flight", &state.batches.len())
.finish()
}
}
impl<K, V, E> Loader<K, V, E> {
pub fn new<F, Fut>(batch_fn: F) -> Self
where
F: Fn(Vec<K>) -> Fut + Send + Sync + 'static,
Fut: Future<Output = Vec<Result<V, E>>> + Send + 'static,
{
Self::with_config(batch_fn, LoaderConfig::default())
}
pub fn with_config<F, Fut>(batch_fn: F, config: LoaderConfig) -> Self
where
F: Fn(Vec<K>) -> Fut + Send + Sync + 'static,
Fut: Future<Output = Vec<Result<V, E>>> + Send + 'static,
{
let batch_fn: BatchFn<K, V, E> = Arc::new(move |keys| Box::pin(batch_fn(keys)));
let inner = Arc::new_cyclic(|weak| Inner {
batch_fn,
config,
state: Mutex::new(State {
entries: HashMap::new(),
queue: VecDeque::new(),
queued: HashSet::new(),
batches: HashMap::new(),
next_batch: 0,
#[cfg(feature = "tracing")]
deduplicated: 0,
}),
weak: weak.clone(),
});
Self { inner }
}
pub fn new_fallible<F, Fut>(batch_fn: F) -> Self
where
F: Fn(Vec<K>) -> Fut + Send + Sync + 'static,
Fut: Future<Output = Result<Vec<Result<V, E>>, E>> + Send + 'static,
E: Clone + Send + 'static,
{
Self::with_config_fallible(batch_fn, LoaderConfig::default())
}
pub fn with_config_fallible<F, Fut>(batch_fn: F, config: LoaderConfig) -> Self
where
F: Fn(Vec<K>) -> Fut + Send + Sync + 'static,
Fut: Future<Output = Result<Vec<Result<V, E>>, E>> + Send + 'static,
E: Clone + Send + 'static,
{
Self::with_config(
move |keys: Vec<K>| {
let len = keys.len();
batch_fn(keys).map(move |outcome| match outcome {
Ok(results) => results,
Err(error) => (0..len).map(|_| Err(error.clone())).collect(),
})
},
config,
)
}
}
impl<K, V, E> Loader<K, V, E>
where
K: Clone + Eq + Hash + Send + Sync + 'static,
V: Clone + Send + Sync + 'static,
E: Clone + Send + Sync + 'static,
{
pub fn load(&self, key: K) -> impl Future<Output = Result<V, E>> + Send + 'static {
Arc::clone(&self.inner).load(key)
}
pub fn load_many<I>(&self, keys: I) -> impl Future<Output = Vec<Result<V, E>>> + Send + 'static
where
I: IntoIterator<Item = K>,
{
let futures: Vec<_> = keys.into_iter().map(|key| self.load(key)).collect();
async move { join_all(futures).await }
}
pub fn prime(&self, key: K, value: V) {
let mut state = self.inner.lock();
state.queue.retain(|queued| queued != &key);
state.queued.remove(&key);
state.entries.insert(key, Entry::Ready(Arc::new(Ok(value))));
}
pub fn clear(&self) {
let mut state = self.inner.lock();
state
.entries
.retain(|_, entry| matches!(entry, Entry::Pending { .. }));
}
pub fn clear_key(&self, key: &K) {
let mut state = self.inner.lock();
if matches!(state.entries.get(key), Some(Entry::Ready(_))) {
state.entries.remove(key);
}
}
#[must_use]
pub fn is_cached(&self, key: &K) -> bool {
matches!(self.inner.lock().entries.get(key), Some(Entry::Ready(_)))
}
#[must_use]
pub fn cached_len(&self) -> usize {
self.inner
.lock()
.entries
.values()
.filter(|entry| matches!(entry, Entry::Ready(_)))
.count()
}
}
impl<K, V, E> Inner<K, V, E>
where
K: Clone + Eq + Hash + Send + Sync + 'static,
V: Clone + Send + Sync + 'static,
E: Clone + Send + Sync + 'static,
{
fn lock(&self) -> MutexGuard<'_, State<K, V, E>> {
self.state.lock().unwrap_or_else(PoisonError::into_inner)
}
fn enqueue(&self, key: &K) -> Option<Arc<Result<V, E>>> {
let mut state = self.lock();
match state.entries.get(key) {
Some(Entry::Ready(result)) => return Some(Arc::clone(result)),
Some(_) => {
#[cfg(feature = "tracing")]
{
state.deduplicated += 1;
}
return None;
}
None => {}
}
if state.queue.len() >= self.config.max_queue {
self.flush_locked(&mut state);
if state.entries.contains_key(key) {
#[cfg(feature = "tracing")]
{
state.deduplicated += 1;
}
return None;
}
}
if state.queued.insert(key.clone()) {
state.queue.push_back(key.clone());
} else {
#[cfg(feature = "tracing")]
{
state.deduplicated += 1;
}
}
None
}
fn flush_and_lookup(&self, key: &K) -> Lookup<V, E> {
let mut state = self.lock();
self.flush_locked(&mut state);
Self::lookup_locked(&state, key)
}
fn flush_locked(&self, state: &mut State<K, V, E>) {
while !state.queue.is_empty() {
let queued = state.queue.len();
#[cfg(feature = "tracing")]
let deduplicated = std::mem::take(&mut state.deduplicated);
#[cfg(not(feature = "tracing"))]
let deduplicated = 0usize;
let take = queued.min(self.config.max_batch_size);
let keys: Vec<K> = state.queue.drain(..take).collect();
for key in &keys {
state.queued.remove(key);
}
let batch = state.next_batch;
state.next_batch = state.next_batch.wrapping_add(1);
for (index, key) in keys.iter().enumerate() {
state
.entries
.insert(key.clone(), Entry::Pending { batch, index });
}
let shared = self.start_batch(batch, keys, queued, deduplicated);
state.batches.insert(batch, shared);
}
}
fn start_batch(
&self,
batch: u64,
keys: Vec<K>,
_queued: usize,
_deduplicated: usize,
) -> SharedBatch<V, E> {
let batch_fn = Arc::clone(&self.batch_fn);
let weak = self.weak.clone();
async move {
#[cfg(feature = "tracing")]
let started = std::time::Instant::now();
let results: BatchOutput<V, E> = Arc::new(
batch_fn(keys.clone())
.await
.into_iter()
.map(Arc::new)
.collect(),
);
#[cfg(feature = "tracing")]
if tracing::enabled!(target: "gurafi::loader", tracing::Level::DEBUG) {
let errors = results.iter().filter(|result| result.is_err()).count();
tracing::debug!(
target: "gurafi::loader",
queue_len = _queued,
batch_size = keys.len(),
deduplicated = _deduplicated,
duration_us = started.elapsed().as_micros() as u64,
errors,
"gurafi.loader.batch"
);
if errors > 0 {
tracing::debug!(
target: "gurafi::loader",
batch_size = keys.len(),
errors,
"gurafi.loader.error"
);
}
}
if let Some(inner) = weak.upgrade() {
inner.complete(batch, keys, &results);
}
results
}
.boxed()
.shared()
}
fn complete(&self, batch: u64, keys: Vec<K>, results: &BatchOutput<V, E>) {
let mut state = self.lock();
state.batches.remove(&batch);
for (index, key) in keys.into_iter().enumerate() {
let owns_key = matches!(
state.entries.get(&key),
Some(Entry::Pending { batch: owner, .. }) if *owner == batch
);
if !owns_key {
continue;
}
match results.get(index) {
Some(result) => {
state.entries.insert(key, Entry::Ready(Arc::clone(result)));
}
None => {
state.entries.remove(&key);
if state.queued.insert(key.clone()) {
state.queue.push_back(key);
}
}
}
}
}
fn lookup_locked(state: &State<K, V, E>, key: &K) -> Lookup<V, E> {
match state.entries.get(key) {
Some(Entry::Ready(result)) => Lookup::Ready(Arc::clone(result)),
Some(Entry::Pending { batch, index }) => match state.batches.get(batch) {
Some(shared) => Lookup::Pending {
shared: shared.clone(),
index: *index,
},
None => Lookup::Missing,
},
None => Lookup::Missing,
}
}
#[cfg_attr(
feature = "tracing",
tracing::instrument(
skip_all,
level = "debug",
name = "gurafi.loader.load",
fields(
key_type = std::any::type_name::<K>(),
cache_hit = tracing::field::Empty,
)
)
)]
async fn load(self: Arc<Self>, key: K) -> Result<V, E> {
if let Some(result) = self.enqueue(&key) {
#[cfg(feature = "tracing")]
{
let span = tracing::Span::current();
if !span.is_disabled() {
span.record("cache_hit", true);
}
}
return (*result).clone();
}
#[cfg(feature = "tracing")]
{
let span = tracing::Span::current();
if !span.is_disabled() {
span.record("cache_hit", false);
}
}
YieldNow::new().await;
let mut attempts: u8 = 0;
loop {
match self.flush_and_lookup(&key) {
Lookup::Ready(result) => return (*result).clone(),
Lookup::Pending { shared, index } => {
let results = shared.await;
if let Some(result) = results.get(index) {
return (**result).clone();
}
attempts = attempts.saturating_add(1);
if attempts >= self.config.max_attempts {
if let Some(error) =
results.iter().find_map(|result| match result.as_ref() {
Err(error) => Some(error.clone()),
Ok(_) => None,
})
{
return Err(error.clone());
}
panic!(
"gurafi::Loader batch function returned only {} results; a batch \
function must return exactly one result per key",
results.len(),
);
}
}
Lookup::Missing => {
attempts = attempts.saturating_add(1);
if attempts >= self.config.max_attempts {
panic!(
"gurafi::Loader lost the result for a key and could not retry it; \
this indicates a bug in the loader"
);
}
self.enqueue(&key);
}
}
}
}
}
struct YieldNow {
yielded: bool,
}
impl YieldNow {
fn new() -> Self {
Self { yielded: false }
}
}
impl Future for YieldNow {
type Output = ();
fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<()> {
let this = self.get_mut();
if this.yielded {
Poll::Ready(())
} else {
this.yielded = true;
cx.waker().wake_by_ref();
Poll::Pending
}
}
}