Files
crank/crates/crank-runtime/src/cache.rs

781 lines
25 KiB
Rust

use std::{
collections::HashMap,
sync::Arc,
time::{Duration, Instant},
};
use async_trait::async_trait;
use crank_core::{
CacheBackend, CacheScope, CacheStoreError, CachedResponse, CoordinationStateReservation,
CoordinationStateStore, CoordinationStateValue, RateLimitBucketState, RateLimitDecision,
RateLimitStateStore, ReplayGuardStatus, ReplayGuardStore, ResponseCacheStore,
};
use redis::{Client, aio::ConnectionManager};
use serde::de::DeserializeOwned;
use thiserror::Error;
use tokio::sync::RwLock;
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct RuntimeCacheConfig {
pub backend: CacheBackend,
pub url: Option<String>,
}
impl Default for RuntimeCacheConfig {
fn default() -> Self {
Self {
backend: CacheBackend::Memory,
url: None,
}
}
}
impl RuntimeCacheConfig {
pub fn try_new(
backend: CacheBackend,
url: Option<String>,
) -> Result<Self, RuntimeCacheConfigError> {
if backend.is_external() && url.is_none() {
return Err(RuntimeCacheConfigError::MissingUrl { backend });
}
if !backend.is_external() && url.is_some() {
return Err(RuntimeCacheConfigError::UnexpectedUrl);
}
Ok(Self { backend, url })
}
}
#[derive(Clone)]
pub struct RuntimeCacheStores {
pub backend: CacheBackend,
pub response: Arc<dyn ResponseCacheStore>,
pub rate_limit: Arc<dyn RateLimitStateStore>,
pub replay_guard: Arc<dyn ReplayGuardStore>,
pub coordination: Arc<dyn CoordinationStateStore>,
}
#[derive(Clone)]
pub struct RedisCacheStore {
backend: CacheBackend,
connection_manager: ConnectionManager,
}
#[derive(Clone, Debug, Default)]
pub struct InMemoryResponseCacheStore {
entries: Arc<RwLock<HashMap<String, ExpiringValue<CachedResponse>>>>,
}
#[derive(Clone, Debug, Default)]
pub struct InMemoryRateLimitStateStore {
entries: Arc<RwLock<HashMap<String, ExpiringValue<RateLimitBucketState>>>>,
}
#[derive(Clone, Debug, Default)]
pub struct InMemoryReplayGuardStore {
entries: Arc<RwLock<HashMap<String, Instant>>>,
}
#[derive(Clone, Debug, Default)]
pub struct InMemoryCoordinationStateStore {
entries: Arc<RwLock<HashMap<String, ExpiringValue<CoordinationStateValue>>>>,
}
#[derive(Clone, Debug)]
struct ExpiringValue<T> {
value: T,
expires_at: Instant,
}
impl RuntimeCacheStores {
pub async fn from_config(
config: &RuntimeCacheConfig,
) -> Result<Self, RuntimeCacheStoreInitError> {
match config.backend {
CacheBackend::Memory => {
let response = Arc::new(InMemoryResponseCacheStore::default());
let rate_limit = Arc::new(InMemoryRateLimitStateStore::default());
let replay_guard = Arc::new(InMemoryReplayGuardStore::default());
let coordination = Arc::new(InMemoryCoordinationStateStore::default());
Ok(Self {
backend: CacheBackend::Memory,
response,
rate_limit,
replay_guard,
coordination,
})
}
CacheBackend::Valkey | CacheBackend::Redis => {
let url = config
.url
.as_deref()
.ok_or(RuntimeCacheStoreInitError::MissingUrl {
backend: config.backend,
})?;
let store = Arc::new(RedisCacheStore::connect(config.backend, url).await?);
Ok(Self {
backend: config.backend,
response: store.clone(),
rate_limit: store.clone(),
replay_guard: store.clone(),
coordination: store,
})
}
}
}
}
impl RedisCacheStore {
pub async fn connect(
backend: CacheBackend,
url: &str,
) -> Result<Self, RuntimeCacheStoreInitError> {
let client =
Client::open(url).map_err(|_| RuntimeCacheStoreInitError::InvalidUrl { backend })?;
let connection_manager = client
.get_connection_manager()
.await
.map_err(|_| RuntimeCacheStoreInitError::ConnectFailed { backend })?;
Ok(Self {
backend,
connection_manager,
})
}
fn prefixed_key(&self, kind: &str, key: &str) -> String {
format!("crank:{kind}:{key}")
}
fn serialize_value<T: serde::Serialize>(&self, value: &T) -> Result<Vec<u8>, CacheStoreError> {
serde_json::to_vec(value).map_err(|source| CacheStoreError::Serialization {
message: source.to_string(),
})
}
fn deserialize_value<T: DeserializeOwned>(&self, value: &[u8]) -> Result<T, CacheStoreError> {
serde_json::from_slice(value).map_err(|source| CacheStoreError::Serialization {
message: source.to_string(),
})
}
fn ttl_ms(&self, ttl: Duration) -> Result<u64, CacheStoreError> {
if ttl.is_zero() {
return Err(CacheStoreError::InvalidKey {
message: "cache ttl must be greater than zero".to_owned(),
});
}
Ok(u64::try_from(ttl.as_millis()).unwrap_or(u64::MAX))
}
fn unavailable(&self, source: redis::RedisError) -> CacheStoreError {
CacheStoreError::Unavailable {
message: format!("{} backend error: {source}", self.backend),
}
}
async fn get_json<T: DeserializeOwned>(
&self,
kind: &str,
key: &str,
) -> Result<Option<T>, CacheStoreError> {
validate_key(key)?;
let storage_key = self.prefixed_key(kind, key);
let mut connection = self.connection_manager.clone();
let encoded: Option<Vec<u8>> = redis::cmd("GET")
.arg(storage_key)
.query_async(&mut connection)
.await
.map_err(|source| self.unavailable(source))?;
encoded
.map(|bytes| self.deserialize_value(&bytes))
.transpose()
}
async fn put_json<T: serde::Serialize>(
&self,
kind: &str,
key: &str,
value: &T,
ttl: Duration,
) -> Result<(), CacheStoreError> {
validate_key(key)?;
let storage_key = self.prefixed_key(kind, key);
let encoded = self.serialize_value(value)?;
let ttl_ms = self.ttl_ms(ttl)?;
let mut connection = self.connection_manager.clone();
redis::cmd("PSETEX")
.arg(storage_key)
.arg(ttl_ms)
.arg(encoded)
.query_async::<()>(&mut connection)
.await
.map_err(|source| self.unavailable(source))?;
Ok(())
}
async fn delete_kind_key(&self, kind: &str, key: &str) -> Result<(), CacheStoreError> {
validate_key(key)?;
let storage_key = self.prefixed_key(kind, key);
let mut connection = self.connection_manager.clone();
redis::cmd("DEL")
.arg(storage_key)
.query_async::<()>(&mut connection)
.await
.map_err(|source| self.unavailable(source))?;
Ok(())
}
fn coordination_kind(scope: CacheScope) -> &'static str {
match scope {
CacheScope::Response => "coordination:response",
CacheScope::RateLimit => "coordination:rate_limit",
CacheScope::ReplayGuard => "coordination:replay_guard",
CacheScope::Coordination => "coordination:coordination",
}
}
}
#[async_trait]
impl ResponseCacheStore for InMemoryResponseCacheStore {
async fn get(&self, key: &str) -> Result<Option<CachedResponse>, CacheStoreError> {
validate_key(key)?;
let now = Instant::now();
let mut entries = self.entries.write().await;
retain_unexpired(&mut entries, now);
Ok(entries.get(key).map(|entry| entry.value.clone()))
}
async fn put(
&self,
key: &str,
value: CachedResponse,
ttl: Duration,
) -> Result<(), CacheStoreError> {
validate_key(key)?;
let expires_at = expiry_from_ttl(ttl)?;
let mut entries = self.entries.write().await;
entries.insert(key.to_owned(), ExpiringValue { value, expires_at });
Ok(())
}
async fn delete(&self, key: &str) -> Result<(), CacheStoreError> {
validate_key(key)?;
let mut entries = self.entries.write().await;
entries.remove(key);
Ok(())
}
}
#[async_trait]
impl RateLimitStateStore for InMemoryRateLimitStateStore {
async fn get_bucket(&self, key: &str) -> Result<Option<RateLimitBucketState>, CacheStoreError> {
validate_key(key)?;
let now = Instant::now();
let mut entries = self.entries.write().await;
retain_unexpired(&mut entries, now);
Ok(entries.get(key).map(|entry| entry.value))
}
async fn put_bucket(
&self,
key: &str,
value: RateLimitBucketState,
ttl: Duration,
) -> Result<(), CacheStoreError> {
validate_key(key)?;
let expires_at = expiry_from_ttl(ttl)?;
let mut entries = self.entries.write().await;
entries.insert(key.to_owned(), ExpiringValue { value, expires_at });
Ok(())
}
async fn delete_bucket(&self, key: &str) -> Result<(), CacheStoreError> {
validate_key(key)?;
let mut entries = self.entries.write().await;
entries.remove(key);
Ok(())
}
async fn consume_token(
&self,
key: &str,
burst_tokens_micros: u64,
refill_per_second_micros: u64,
now_unix_ms: i64,
ttl: Duration,
) -> Result<RateLimitDecision, CacheStoreError> {
validate_key(key)?;
validate_rate_limit_parameters(burst_tokens_micros, refill_per_second_micros)?;
let expires_at = expiry_from_ttl(ttl)?;
let now = Instant::now();
let mut entries = self.entries.write().await;
retain_unexpired(&mut entries, now);
let state = entries
.get(key)
.map(|entry| entry.value)
.unwrap_or(RateLimitBucketState {
tokens_micros: burst_tokens_micros,
last_refill_unix_ms: now_unix_ms,
});
let (state, decision) = consume_bucket_token(
state,
burst_tokens_micros,
refill_per_second_micros,
now_unix_ms,
);
entries.insert(
key.to_owned(),
ExpiringValue {
value: state,
expires_at,
},
);
Ok(decision)
}
}
#[async_trait]
impl ReplayGuardStore for InMemoryReplayGuardStore {
async fn mark_seen(
&self,
key: &str,
ttl: Duration,
) -> Result<ReplayGuardStatus, CacheStoreError> {
validate_key(key)?;
let expires_at = expiry_from_ttl(ttl)?;
let now = Instant::now();
let mut entries = self.entries.write().await;
entries.retain(|_, entry_expires_at| *entry_expires_at > now);
if entries.get(key).is_some() {
return Ok(ReplayGuardStatus::AlreadySeen);
}
entries.insert(key.to_owned(), expires_at);
Ok(ReplayGuardStatus::Fresh)
}
async fn clear(&self, key: &str) -> Result<(), CacheStoreError> {
validate_key(key)?;
let mut entries = self.entries.write().await;
entries.remove(key);
Ok(())
}
}
#[async_trait]
impl CoordinationStateStore for InMemoryCoordinationStateStore {
async fn get_value(
&self,
scope: CacheScope,
key: &str,
) -> Result<Option<CoordinationStateValue>, CacheStoreError> {
validate_key(key)?;
let storage_key = scoped_key(scope, key);
let now = Instant::now();
let mut entries = self.entries.write().await;
retain_unexpired(&mut entries, now);
Ok(entries.get(&storage_key).map(|entry| entry.value.clone()))
}
async fn put_value(
&self,
scope: CacheScope,
key: &str,
value: CoordinationStateValue,
ttl: Duration,
) -> Result<(), CacheStoreError> {
validate_key(key)?;
let expires_at = expiry_from_ttl(ttl)?;
let storage_key = scoped_key(scope, key);
let mut entries = self.entries.write().await;
entries.insert(storage_key, ExpiringValue { value, expires_at });
Ok(())
}
async fn delete_value(&self, scope: CacheScope, key: &str) -> Result<(), CacheStoreError> {
validate_key(key)?;
let storage_key = scoped_key(scope, key);
let mut entries = self.entries.write().await;
entries.remove(&storage_key);
Ok(())
}
async fn take_value(
&self,
scope: CacheScope,
key: &str,
) -> Result<Option<CoordinationStateValue>, CacheStoreError> {
validate_key(key)?;
let storage_key = scoped_key(scope, key);
let now = Instant::now();
let mut entries = self.entries.write().await;
retain_unexpired(&mut entries, now);
Ok(entries.remove(&storage_key).map(|entry| entry.value))
}
async fn reserve_value(
&self,
scope: CacheScope,
key: &str,
value: CoordinationStateValue,
ttl: Duration,
) -> Result<CoordinationStateReservation, CacheStoreError> {
validate_key(key)?;
let expires_at = expiry_from_ttl(ttl)?;
let storage_key = scoped_key(scope, key);
let now = Instant::now();
let mut entries = self.entries.write().await;
retain_unexpired(&mut entries, now);
if let Some(existing) = entries.get(&storage_key) {
return Ok(CoordinationStateReservation::Existing(
existing.value.clone(),
));
}
entries.insert(storage_key, ExpiringValue { value, expires_at });
Ok(CoordinationStateReservation::Reserved)
}
async fn compare_and_set_value(
&self,
scope: CacheScope,
key: &str,
expected: &CoordinationStateValue,
value: CoordinationStateValue,
ttl: Duration,
) -> Result<bool, CacheStoreError> {
validate_key(key)?;
let expires_at = expiry_from_ttl(ttl)?;
let storage_key = scoped_key(scope, key);
let now = Instant::now();
let mut entries = self.entries.write().await;
retain_unexpired(&mut entries, now);
let matches = entries
.get(&storage_key)
.is_some_and(|entry| entry.value == *expected);
if matches {
entries.insert(storage_key, ExpiringValue { value, expires_at });
}
Ok(matches)
}
}
#[async_trait]
impl ResponseCacheStore for RedisCacheStore {
async fn get(&self, key: &str) -> Result<Option<CachedResponse>, CacheStoreError> {
self.get_json("response", key).await
}
async fn put(
&self,
key: &str,
value: CachedResponse,
ttl: Duration,
) -> Result<(), CacheStoreError> {
self.put_json("response", key, &value, ttl).await
}
async fn delete(&self, key: &str) -> Result<(), CacheStoreError> {
self.delete_kind_key("response", key).await
}
}
#[async_trait]
impl RateLimitStateStore for RedisCacheStore {
async fn get_bucket(&self, key: &str) -> Result<Option<RateLimitBucketState>, CacheStoreError> {
self.get_json("rate_limit", key).await
}
async fn put_bucket(
&self,
key: &str,
value: RateLimitBucketState,
ttl: Duration,
) -> Result<(), CacheStoreError> {
self.put_json("rate_limit", key, &value, ttl).await
}
async fn delete_bucket(&self, key: &str) -> Result<(), CacheStoreError> {
self.delete_kind_key("rate_limit", key).await
}
async fn consume_token(
&self,
key: &str,
burst_tokens_micros: u64,
refill_per_second_micros: u64,
now_unix_ms: i64,
ttl: Duration,
) -> Result<RateLimitDecision, CacheStoreError> {
validate_key(key)?;
validate_rate_limit_parameters(burst_tokens_micros, refill_per_second_micros)?;
let storage_key = self.prefixed_key("rate_limit", key);
let ttl_ms = self.ttl_ms(ttl)?;
let mut connection = self.connection_manager.clone();
let script = r#"
local current = redis.call('GET', KEYS[1])
local tokens = tonumber(ARGV[1])
local last_refill = tonumber(ARGV[3])
if current then
local decoded = cjson.decode(current)
tokens = tonumber(decoded.tokens_micros)
last_refill = tonumber(decoded.last_refill_unix_ms)
end
local effective_now = math.max(tonumber(ARGV[3]), last_refill)
local elapsed = effective_now - last_refill
local replenished = math.floor(elapsed * tonumber(ARGV[2]) / 1000)
tokens = math.min(tonumber(ARGV[1]), tokens + replenished)
local allowed = 0
local retry_after = 0
if tokens >= 1000000 then
tokens = tokens - 1000000
allowed = 1
else
local missing = 1000000 - tokens
retry_after = math.max(1, math.ceil(missing * 1000 / tonumber(ARGV[2])))
end
redis.call('PSETEX', KEYS[1], ARGV[4], cjson.encode({
tokens_micros = tokens,
last_refill_unix_ms = effective_now
}))
return {allowed, retry_after}
"#;
let (allowed, retry_after_ms): (u8, u64) = redis::cmd("EVAL")
.arg(script)
.arg(1)
.arg(storage_key)
.arg(burst_tokens_micros)
.arg(refill_per_second_micros)
.arg(now_unix_ms)
.arg(ttl_ms)
.query_async(&mut connection)
.await
.map_err(|source| self.unavailable(source))?;
Ok(if allowed == 1 {
RateLimitDecision::Allowed
} else {
RateLimitDecision::Rejected { retry_after_ms }
})
}
}
#[async_trait]
impl ReplayGuardStore for RedisCacheStore {
async fn mark_seen(
&self,
key: &str,
ttl: Duration,
) -> Result<ReplayGuardStatus, CacheStoreError> {
validate_key(key)?;
let storage_key = self.prefixed_key("replay_guard", key);
let ttl_ms = self.ttl_ms(ttl)?;
let mut connection = self.connection_manager.clone();
let result: Option<String> = redis::cmd("SET")
.arg(storage_key)
.arg("1")
.arg("PX")
.arg(ttl_ms)
.arg("NX")
.query_async(&mut connection)
.await
.map_err(|source| self.unavailable(source))?;
Ok(if result.is_some() {
ReplayGuardStatus::Fresh
} else {
ReplayGuardStatus::AlreadySeen
})
}
async fn clear(&self, key: &str) -> Result<(), CacheStoreError> {
self.delete_kind_key("replay_guard", key).await
}
}
#[async_trait]
impl CoordinationStateStore for RedisCacheStore {
async fn get_value(
&self,
scope: CacheScope,
key: &str,
) -> Result<Option<CoordinationStateValue>, CacheStoreError> {
self.get_json(Self::coordination_kind(scope), key).await
}
async fn put_value(
&self,
scope: CacheScope,
key: &str,
value: CoordinationStateValue,
ttl: Duration,
) -> Result<(), CacheStoreError> {
self.put_json(Self::coordination_kind(scope), key, &value, ttl)
.await
}
async fn delete_value(&self, scope: CacheScope, key: &str) -> Result<(), CacheStoreError> {
self.delete_kind_key(Self::coordination_kind(scope), key)
.await
}
async fn take_value(
&self,
scope: CacheScope,
key: &str,
) -> Result<Option<CoordinationStateValue>, CacheStoreError> {
validate_key(key)?;
let storage_key = self.prefixed_key(Self::coordination_kind(scope), key);
let mut connection = self.connection_manager.clone();
let encoded: Option<Vec<u8>> = redis::cmd("EVAL")
.arg("local value = redis.call('GET', KEYS[1]); if value then redis.call('DEL', KEYS[1]); end; return value")
.arg(1)
.arg(storage_key)
.query_async(&mut connection)
.await
.map_err(|source| self.unavailable(source))?;
encoded
.map(|bytes| self.deserialize_value(&bytes))
.transpose()
}
async fn reserve_value(
&self,
scope: CacheScope,
key: &str,
value: CoordinationStateValue,
ttl: Duration,
) -> Result<CoordinationStateReservation, CacheStoreError> {
validate_key(key)?;
let storage_key = self.prefixed_key(Self::coordination_kind(scope), key);
let encoded = self.serialize_value(&value)?;
let ttl_ms = self.ttl_ms(ttl)?;
let mut connection = self.connection_manager.clone();
let (reserved, existing): (u8, Vec<u8>) = redis::cmd("EVAL")
.arg("local current = redis.call('GET', KEYS[1]); if current then return {0, current}; end; redis.call('PSETEX', KEYS[1], ARGV[2], ARGV[1]); return {1, ''}")
.arg(1)
.arg(storage_key)
.arg(encoded)
.arg(ttl_ms)
.query_async(&mut connection)
.await
.map_err(|source| self.unavailable(source))?;
if reserved == 1 {
Ok(CoordinationStateReservation::Reserved)
} else {
Ok(CoordinationStateReservation::Existing(
self.deserialize_value(&existing)?,
))
}
}
async fn compare_and_set_value(
&self,
scope: CacheScope,
key: &str,
expected: &CoordinationStateValue,
value: CoordinationStateValue,
ttl: Duration,
) -> Result<bool, CacheStoreError> {
validate_key(key)?;
let storage_key = self.prefixed_key(Self::coordination_kind(scope), key);
let expected = self.serialize_value(expected)?;
let value = self.serialize_value(&value)?;
let ttl_ms = self.ttl_ms(ttl)?;
let mut connection = self.connection_manager.clone();
let replaced: u8 = redis::cmd("EVAL")
.arg("local current = redis.call('GET', KEYS[1]); if current ~= ARGV[1] then return 0; end; redis.call('PSETEX', KEYS[1], ARGV[3], ARGV[2]); return 1")
.arg(1)
.arg(storage_key)
.arg(expected)
.arg(value)
.arg(ttl_ms)
.query_async(&mut connection)
.await
.map_err(|source| self.unavailable(source))?;
Ok(replaced == 1)
}
}
fn consume_bucket_token(
mut state: RateLimitBucketState,
burst_tokens_micros: u64,
refill_per_second_micros: u64,
now_unix_ms: i64,
) -> (RateLimitBucketState, RateLimitDecision) {
let effective_now = now_unix_ms.max(state.last_refill_unix_ms);
let elapsed_ms =
u64::try_from(effective_now.saturating_sub(state.last_refill_unix_ms)).unwrap_or(u64::MAX);
let replenished =
u128::from(elapsed_ms).saturating_mul(u128::from(refill_per_second_micros)) / 1000;
state.tokens_micros = u128::from(state.tokens_micros)
.saturating_add(replenished)
.min(u128::from(burst_tokens_micros))
.try_into()
.unwrap_or(burst_tokens_micros);
state.last_refill_unix_ms = effective_now;
if state.tokens_micros >= 1_000_000 {
state.tokens_micros -= 1_000_000;
return (state, RateLimitDecision::Allowed);
}
let missing = 1_000_000_u64.saturating_sub(state.tokens_micros);
let retry_after_ms = u128::from(missing)
.saturating_mul(1000)
.div_ceil(u128::from(refill_per_second_micros))
.max(1)
.try_into()
.unwrap_or(u64::MAX);
(state, RateLimitDecision::Rejected { retry_after_ms })
}
fn validate_rate_limit_parameters(
burst_tokens_micros: u64,
refill_per_second_micros: u64,
) -> Result<(), CacheStoreError> {
if burst_tokens_micros < 1_000_000 || refill_per_second_micros == 0 {
return Err(CacheStoreError::InvalidKey {
message: "rate limit capacity and refill rate must be positive".to_owned(),
});
}
Ok(())
}
fn validate_key(key: &str) -> Result<(), CacheStoreError> {
if key.trim().is_empty() {
return Err(CacheStoreError::InvalidKey {
message: "cache key must not be empty".to_owned(),
});
}
Ok(())
}
fn expiry_from_ttl(ttl: Duration) -> Result<Instant, CacheStoreError> {
if ttl.is_zero() {
return Err(CacheStoreError::InvalidKey {
message: "cache ttl must be greater than zero".to_owned(),
});
}
Ok(Instant::now() + ttl)
}
fn retain_unexpired<T>(entries: &mut HashMap<String, ExpiringValue<T>>, now: Instant) {
entries.retain(|_, entry| entry.expires_at > now);
}
fn scoped_key(scope: CacheScope, key: &str) -> String {
format!("{scope:?}:{key}")
}
#[derive(Debug, Error)]
pub enum RuntimeCacheConfigError {
#[error("{backend} backend requires CRANK_CACHE_URL")]
MissingUrl { backend: CacheBackend },
#[error("memory cache backend does not accept CRANK_CACHE_URL")]
UnexpectedUrl,
}
#[derive(Debug, Error, PartialEq, Eq)]
pub enum RuntimeCacheStoreInitError {
#[error("{backend} backend requires CRANK_CACHE_URL")]
MissingUrl { backend: CacheBackend },
#[error("invalid {backend} cache url")]
InvalidUrl { backend: CacheBackend },
#[error("failed to connect to {backend} cache backend")]
ConnectFailed { backend: CacheBackend },
}