use std::sync::atomic::{AtomicU64, Ordering};
use spider_route::{registrable_domain, AttemptOutcome, SiteMemory, StatusClass};
use url::Url;
pub const DEFAULT_CAPACITY: usize = 256;
const MIN_CAPACITY: usize = 16;
const MAX_CAPACITY: usize = 65_536;
const DECAY: f32 = 0.25;
#[derive(Debug)]
pub struct SiteMemoryStore {
slots: Box<[Slot]>,
}
#[derive(Debug, Default)]
struct Slot {
key: AtomicU64,
packed: AtomicU64,
}
impl Default for SiteMemoryStore {
fn default() -> SiteMemoryStore {
SiteMemoryStore::new(DEFAULT_CAPACITY)
}
}
impl SiteMemoryStore {
pub fn new(capacity: usize) -> SiteMemoryStore {
if capacity == 0 {
return SiteMemoryStore {
slots: Box::default(),
};
}
let wanted = capacity.clamp(MIN_CAPACITY, MAX_CAPACITY);
let slots = wanted.next_power_of_two().min(MAX_CAPACITY);
let mut table = Vec::with_capacity(slots);
table.resize_with(slots, Slot::default);
SiteMemoryStore {
slots: table.into_boxed_slice(),
}
}
pub fn capacity(&self) -> usize {
self.slots.len()
}
pub fn len(&self) -> usize {
self.slots
.iter()
.filter(|slot| slot.key.load(Ordering::Relaxed) != 0)
.count()
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
pub fn get(&self, url: &Url) -> Option<SiteMemory> {
if self.slots.is_empty() {
return None;
}
let key = key_of(url)?;
let slot = self.slot(key)?;
if slot.key.load(Ordering::Relaxed) != key {
return None;
}
let memory = unpack(slot.packed.load(Ordering::Relaxed));
if memory.observations == 0 {
None
} else {
Some(memory)
}
}
pub fn observe(&self, url: &Url, outcome: &AttemptOutcome) {
self.update(url, |memory| fold(memory, outcome));
}
pub fn remember(&self, url: &Url, memory: SiteMemory) {
self.update(url, |_| memory);
}
pub fn clear(&self) {
for slot in &self.slots {
slot.key.store(0, Ordering::Relaxed);
slot.packed.store(0, Ordering::Relaxed);
}
}
fn update(&self, url: &Url, next: impl Fn(SiteMemory) -> SiteMemory) {
if self.slots.is_empty() {
return;
}
let Some(key) = key_of(url) else {
return;
};
let Some(slot) = self.slot(key) else {
return;
};
if slot.key.load(Ordering::Relaxed) != key {
slot.key.store(key, Ordering::Relaxed);
slot.packed.store(0, Ordering::Relaxed);
}
let mut current = slot.packed.load(Ordering::Relaxed);
loop {
let packed = pack(next(unpack(current)));
match slot.packed.compare_exchange_weak(
current,
packed,
Ordering::Relaxed,
Ordering::Relaxed,
) {
Ok(_) => return,
Err(seen) => current = seen,
}
}
}
fn slot(&self, key: u64) -> Option<&Slot> {
let mask = self.slots.len().saturating_sub(1);
self.slots.get((key as usize) & mask)
}
}
fn key_of(url: &Url) -> Option<u64> {
let name = registrable_domain(url)?;
let hashed = fnv1a(name.as_bytes());
Some(if hashed == 0 { 1 } else { hashed })
}
fn fnv1a(bytes: &[u8]) -> u64 {
let mut hash: u64 = 0xcbf2_9ce4_8422_2325;
for byte in bytes {
hash ^= u64::from(byte.to_ascii_lowercase());
hash = hash.wrapping_mul(0x0000_0100_0000_01b3);
}
hash
}
fn fold(memory: SiteMemory, outcome: &AttemptOutcome) -> SiteMemory {
let scored = if outcome.success { 1.0 } else { 0.0 };
let success_rate = if memory.observations == 0 {
scored
} else {
memory.success_rate + (scored - memory.success_rate) * DECAY
};
let streak = match (outcome.success, memory.streak) {
(true, held) if held > 0 => held.saturating_add(1),
(true, _) => 1,
(false, held) if held < 0 => held.saturating_sub(1),
(false, _) => -1,
};
SiteMemory {
observations: memory.observations.saturating_add(1),
success_rate: success_rate.clamp(0.0, 1.0),
streak,
last_status: outcome.status,
}
}
const RATE_STEPS: f32 = u16::MAX as f32;
fn pack(memory: SiteMemory) -> u64 {
let observations = u64::from(memory.observations.min(u32::from(u16::MAX)) as u16);
let rate = u64::from((memory.success_rate.clamp(0.0, 1.0) * RATE_STEPS).round() as u16);
let streak = u64::from(memory.streak as u16);
let status = u64::from(status_code(memory.last_status));
observations | (rate << 16) | (streak << 32) | (status << 48)
}
fn unpack(packed: u64) -> SiteMemory {
let observations = (packed & 0xffff) as u32;
let rate = ((packed >> 16) & 0xffff) as u16;
let streak = ((packed >> 32) & 0xffff) as u16 as i16;
let status = ((packed >> 48) & 0xff) as u8;
SiteMemory {
observations,
success_rate: f32::from(rate) / RATE_STEPS,
streak,
last_status: status_from_code(status),
}
}
fn status_code(status: StatusClass) -> u8 {
match status {
StatusClass::Ok => 1,
StatusClass::Empty => 2,
StatusClass::BadRequest => 3,
StatusClass::NeedsLogin => 4,
StatusClass::Blocked => 5,
StatusClass::NotFound => 6,
StatusClass::RateLimited => 7,
StatusClass::ServerError => 8,
_ => 0,
}
}
fn status_from_code(code: u8) -> StatusClass {
match code {
1 => StatusClass::Ok,
2 => StatusClass::Empty,
3 => StatusClass::BadRequest,
4 => StatusClass::NeedsLogin,
5 => StatusClass::Blocked,
6 => StatusClass::NotFound,
7 => StatusClass::RateLimited,
8 => StatusClass::ServerError,
_ => StatusClass::Unknown,
}
}
#[cfg(test)]
mod tests {
#![allow(
clippy::unwrap_used,
clippy::expect_used,
clippy::panic,
clippy::unreachable,
clippy::indexing_slicing,
clippy::string_slice
)]
use super::*;
fn url(raw: &str) -> Url {
Url::parse(raw).expect("a url")
}
#[test]
fn a_site_is_remembered_and_an_unseen_one_is_not() {
let store = SiteMemoryStore::default();
let seen = url("https://example.com/a");
assert!(store.get(&seen).is_none());
assert!(store.is_empty());
store.observe(&seen, &AttemptOutcome::failed(StatusClass::Blocked, 900));
let memory = store.get(&seen).expect("a record");
assert_eq!(memory.observations, 1);
assert_eq!(memory.streak, -1);
assert_eq!(memory.last_status, StatusClass::Blocked);
assert_eq!(memory.success_rate, 0.0);
assert!(store.get(&url("https://other.example.org/a")).is_none());
}
#[test]
fn every_host_under_one_name_shares_a_record() {
let store = SiteMemoryStore::default();
store.observe(
&url("https://www.example.com/a"),
&AttemptOutcome::failed(StatusClass::Blocked, 100),
);
store.observe(
&url("https://api.example.com/b"),
&AttemptOutcome::failed(StatusClass::Blocked, 100),
);
let memory = store.get(&url("https://example.com/c")).expect("a record");
assert_eq!(memory.observations, 2);
assert_eq!(memory.streak, -2);
assert_eq!(store.len(), 1);
}
#[test]
fn a_streak_turns_around_rather_than_counting_through_zero() {
let store = SiteMemoryStore::default();
let site = url("https://example.com/a");
for _ in 0..3 {
store.observe(&site, &AttemptOutcome::failed(StatusClass::Blocked, 10));
}
assert_eq!(store.get(&site).expect("a record").streak, -3);
store.observe(&site, &AttemptOutcome::ok(2_000, 10));
let memory = store.get(&site).expect("a record");
assert_eq!(memory.streak, 1);
assert_eq!(memory.observations, 4);
assert!(memory.success_rate > 0.0);
}
#[test]
fn the_table_never_grows_past_its_capacity() {
let store = SiteMemoryStore::new(64);
assert_eq!(store.capacity(), 64);
for n in 0..5_000 {
let site = url(&format!("https://site-{n}.example{n}.com/a"));
store.observe(&site, &AttemptOutcome::ok(1_000, 20));
}
assert!(
store.len() <= store.capacity(),
"{} records in {} slots",
store.len(),
store.capacity()
);
assert!(store.len() > 16, "only {} slots filled", store.len());
}
#[test]
fn a_capacity_is_rounded_up_and_held_inside_its_limits() {
assert_eq!(SiteMemoryStore::new(1).capacity(), MIN_CAPACITY);
assert_eq!(SiteMemoryStore::new(100).capacity(), 128);
assert_eq!(SiteMemoryStore::new(usize::MAX).capacity(), MAX_CAPACITY);
}
#[test]
fn zero_capacity_disables_site_memory() {
let store = SiteMemoryStore::new(0);
let site = url("https://example.com/a");
assert_eq!(store.capacity(), 0);
store.observe(&site, &AttemptOutcome::failed(StatusClass::Blocked, 10));
store.remember(
&site,
SiteMemory {
observations: 9,
success_rate: 0.0,
streak: -9,
last_status: StatusClass::Blocked,
},
);
assert!(store.get(&site).is_none());
assert!(store.is_empty());
store.clear();
assert_eq!(store.capacity(), 0);
}
#[test]
fn a_record_survives_the_trip_through_one_word() {
let cases = [
SiteMemory::cold(),
SiteMemory {
observations: 12,
success_rate: 0.5,
streak: -3,
last_status: StatusClass::Blocked,
},
SiteMemory {
observations: u32::MAX,
success_rate: 1.0,
streak: i16::MAX,
last_status: StatusClass::RateLimited,
},
SiteMemory {
observations: 1,
success_rate: 0.0,
streak: i16::MIN,
last_status: StatusClass::Empty,
},
];
for memory in cases {
let read = unpack(pack(memory));
assert_eq!(read.streak, memory.streak, "{memory:?}");
assert_eq!(read.last_status, memory.last_status, "{memory:?}");
assert_eq!(
read.observations,
memory.observations.min(u32::from(u16::MAX)),
"{memory:?}"
);
assert!(
(read.success_rate - memory.success_rate).abs() < 0.001,
"{memory:?} came back at {}",
read.success_rate
);
}
}
#[test]
fn a_literal_address_is_not_a_site_to_remember() {
let store = SiteMemoryStore::default();
let literal = url("http://192.0.2.1/status");
store.observe(&literal, &AttemptOutcome::ok(10, 10));
assert!(store.get(&literal).is_none());
assert!(store.is_empty());
}
#[test]
fn a_record_can_be_written_directly_and_cleared() {
let store = SiteMemoryStore::default();
let site = url("https://example.com/a");
store.remember(
&site,
SiteMemory {
observations: 9,
success_rate: 0.1,
streak: -4,
last_status: StatusClass::Blocked,
},
);
assert_eq!(store.get(&site).expect("a record").observations, 9);
store.clear();
assert!(store.get(&site).is_none());
}
#[test]
fn records_from_many_threads_all_land() {
let store = std::sync::Arc::new(SiteMemoryStore::default());
let site = url("https://example.com/a");
std::thread::scope(|scope| {
for _ in 0..4 {
let store = std::sync::Arc::clone(&store);
let site = site.clone();
scope.spawn(move || {
for _ in 0..50 {
store.observe(&site, &AttemptOutcome::ok(100, 10));
}
});
}
});
assert_eq!(store.get(&site).expect("a record").observations, 200);
}
}