Skip to main content

spider_cloud_agent/
memory.rs

1//! What this process remembers about the sites it has fetched.
2//!
3//! The router takes site memory as an input and keeps none of its own, which is
4//! what lets per site adaptivity exist without a site name reaching any weights.
5//! Somebody still has to hold the records, so the client holds them here.
6//!
7//! Three properties are the whole design.
8//!
9//! It is bounded. The table is a fixed number of slots allocated once, and a
10//! new site lands in the slot its key maps to whether or not something was
11//! already there. A map keyed by domain with no ceiling is a leak with extra
12//! steps, and a cache that forgets the least recently used site needs ordering
13//! that every reader would have to agree on.
14//!
15//! It does not lock. Each slot is two atomics: the key, and the whole memory
16//! packed into one word. Packing is what makes a read consistent without a
17//! lock, because the four fields move together or not at all. See
18//! `CONTRIBUTING.md` for why a lock is not an option here.
19//!
20//! It is approximate on purpose. Two tasks recording against one site can race,
21//! and the loser's observation is folded in on the next pass or dropped. A
22//! routing hint that is one attempt stale changes which settings are tried
23//! first, and the policy engine reads what actually came back.
24
25use std::sync::atomic::{AtomicU64, Ordering};
26
27use spider_route::{registrable_domain, AttemptOutcome, SiteMemory, StatusClass};
28use url::Url;
29
30/// How many sites are remembered when nobody says otherwise.
31///
32/// Two hundred and fifty six slots is about four kilobytes and covers far more
33/// distinct sites than one process usually touches in a run. A caller crawling
34/// more than that raises it.
35pub const DEFAULT_CAPACITY: usize = 256;
36
37/// The fewest slots an enabled store may have.
38const MIN_CAPACITY: usize = 16;
39
40/// The most slots a store may have, which is where bounded stops being a word
41/// and starts being a number.
42const MAX_CAPACITY: usize = 65_536;
43
44/// How much one observation moves the success rate.
45///
46/// A quarter, so a site that starts failing is believed within about three
47/// attempts and a single bad fetch does not rewrite the record.
48const DECAY: f32 = 0.25;
49
50/// One site's record, keyed by its registrable name.
51///
52/// Cheap to share: a store is allocated once and read through a shared
53/// reference from any number of tasks.
54#[derive(Debug)]
55pub struct SiteMemoryStore {
56    slots: Box<[Slot]>,
57}
58
59/// One slot of the table.
60///
61/// `key` is zero while the slot has never held a site. `packed` holds the
62/// memory as a single word, so a reader sees four fields from one attempt
63/// rather than a mixture of two.
64#[derive(Debug, Default)]
65struct Slot {
66    key: AtomicU64,
67    packed: AtomicU64,
68}
69
70impl Default for SiteMemoryStore {
71    fn default() -> SiteMemoryStore {
72        SiteMemoryStore::new(DEFAULT_CAPACITY)
73    }
74}
75
76impl SiteMemoryStore {
77    /// A store with room for about this many sites.
78    ///
79    /// Zero disables memory without allocating a table. Otherwise the figure
80    /// is rounded up to a power of two and held between 16 and
81    /// 65536, so the table can be indexed with a mask and so no caller can ask
82    /// for a store that is not bounded.
83    pub fn new(capacity: usize) -> SiteMemoryStore {
84        if capacity == 0 {
85            return SiteMemoryStore {
86                slots: Box::default(),
87            };
88        }
89        let wanted = capacity.clamp(MIN_CAPACITY, MAX_CAPACITY);
90        let slots = wanted.next_power_of_two().min(MAX_CAPACITY);
91        let mut table = Vec::with_capacity(slots);
92        table.resize_with(slots, Slot::default);
93
94        SiteMemoryStore {
95            slots: table.into_boxed_slice(),
96        }
97    }
98
99    /// How many slots the table has, which is the most sites it can remember
100    /// at once.
101    pub fn capacity(&self) -> usize {
102        self.slots.len()
103    }
104
105    /// How many slots hold a site right now.
106    ///
107    /// Never more than [`SiteMemoryStore::capacity`], which is the property
108    /// worth checking.
109    pub fn len(&self) -> usize {
110        self.slots
111            .iter()
112            .filter(|slot| slot.key.load(Ordering::Relaxed) != 0)
113            .count()
114    }
115
116    /// Whether nothing has been recorded yet.
117    pub fn is_empty(&self) -> bool {
118        self.len() == 0
119    }
120
121    /// What is remembered about the site this address belongs to.
122    ///
123    /// `None` when nothing is, which is what a cold start looks like and what
124    /// the router is built to handle.
125    pub fn get(&self, url: &Url) -> Option<SiteMemory> {
126        if self.slots.is_empty() {
127            return None;
128        }
129        let key = key_of(url)?;
130        let slot = self.slot(key)?;
131
132        if slot.key.load(Ordering::Relaxed) != key {
133            return None;
134        }
135
136        let memory = unpack(slot.packed.load(Ordering::Relaxed));
137        if memory.observations == 0 {
138            None
139        } else {
140            Some(memory)
141        }
142    }
143
144    /// Fold one attempt into what is remembered about this site.
145    ///
146    /// A site that has not been seen before takes the slot its key maps to,
147    /// evicting whatever was there. That is the bound: a slot per site, never a
148    /// slot more.
149    pub fn observe(&self, url: &Url, outcome: &AttemptOutcome) {
150        self.update(url, |memory| fold(memory, outcome));
151    }
152
153    /// Write a record directly, replacing whatever was there.
154    ///
155    /// For a caller that keeps its own records elsewhere and wants this process
156    /// to start from them rather than relearn them.
157    pub fn remember(&self, url: &Url, memory: SiteMemory) {
158        self.update(url, |_| memory);
159    }
160
161    /// Forget everything.
162    pub fn clear(&self) {
163        for slot in &self.slots {
164            slot.key.store(0, Ordering::Relaxed);
165            slot.packed.store(0, Ordering::Relaxed);
166        }
167    }
168
169    /// Replace one site's record with what `next` makes of it.
170    fn update(&self, url: &Url, next: impl Fn(SiteMemory) -> SiteMemory) {
171        if self.slots.is_empty() {
172            return;
173        }
174        let Some(key) = key_of(url) else {
175            return;
176        };
177        let Some(slot) = self.slot(key) else {
178            return;
179        };
180
181        // Claiming is a plain write rather than a compare and swap. Two tasks
182        // claiming the same slot for different sites both write a key, and the
183        // one that loses has recorded an attempt against a record that reads
184        // as another site's. That is a stale routing hint for one call, which
185        // is the same cost as the eviction this slot was going to take anyway.
186        if slot.key.load(Ordering::Relaxed) != key {
187            slot.key.store(key, Ordering::Relaxed);
188            slot.packed.store(0, Ordering::Relaxed);
189        }
190
191        let mut current = slot.packed.load(Ordering::Relaxed);
192        loop {
193            let packed = pack(next(unpack(current)));
194            match slot.packed.compare_exchange_weak(
195                current,
196                packed,
197                Ordering::Relaxed,
198                Ordering::Relaxed,
199            ) {
200                Ok(_) => return,
201                Err(seen) => current = seen,
202            }
203        }
204    }
205
206    /// The slot a key maps to.
207    fn slot(&self, key: u64) -> Option<&Slot> {
208        // A power of two table, so the mask is the whole of the indexing.
209        let mask = self.slots.len().saturating_sub(1);
210        self.slots.get((key as usize) & mask)
211    }
212}
213
214/// The key for the site an address belongs to.
215///
216/// The registrable name, so every host under one site shares one record. A
217/// literal address and a url with no host get none, because neither names a
218/// site to remember.
219fn key_of(url: &Url) -> Option<u64> {
220    let name = registrable_domain(url)?;
221    let hashed = fnv1a(name.as_bytes());
222
223    // Zero means an empty slot, so the one site that hashes to it moves over.
224    Some(if hashed == 0 { 1 } else { hashed })
225}
226
227/// A 64 bit FNV-1a, case folded on the way in.
228///
229/// Not a security hash and it does not need to be. Nothing outside this process
230/// sees the value, and the cost of a collision is one site reading another
231/// site's record until the next attempt overwrites it.
232fn fnv1a(bytes: &[u8]) -> u64 {
233    let mut hash: u64 = 0xcbf2_9ce4_8422_2325;
234    for byte in bytes {
235        hash ^= u64::from(byte.to_ascii_lowercase());
236        hash = hash.wrapping_mul(0x0000_0100_0000_01b3);
237    }
238    hash
239}
240
241/// Fold one attempt into a record.
242fn fold(memory: SiteMemory, outcome: &AttemptOutcome) -> SiteMemory {
243    let scored = if outcome.success { 1.0 } else { 0.0 };
244    let success_rate = if memory.observations == 0 {
245        scored
246    } else {
247        memory.success_rate + (scored - memory.success_rate) * DECAY
248    };
249
250    // A streak counts one way or the other and never both, so a success after
251    // failures starts at one rather than climbing back through zero.
252    let streak = match (outcome.success, memory.streak) {
253        (true, held) if held > 0 => held.saturating_add(1),
254        (true, _) => 1,
255        (false, held) if held < 0 => held.saturating_sub(1),
256        (false, _) => -1,
257    };
258
259    SiteMemory {
260        observations: memory.observations.saturating_add(1),
261        success_rate: success_rate.clamp(0.0, 1.0),
262        streak,
263        last_status: outcome.status,
264    }
265}
266
267/// How many steps the success rate is quantized to on the way into a word.
268const RATE_STEPS: f32 = u16::MAX as f32;
269
270/// Pack a record into one word.
271///
272/// Observations saturate at `u16::MAX` and the success rate is quantized to
273/// about one part in sixty five thousand. Both are far finer than the buckets
274/// the featurizer sorts them into.
275fn pack(memory: SiteMemory) -> u64 {
276    let observations = u64::from(memory.observations.min(u32::from(u16::MAX)) as u16);
277    let rate = u64::from((memory.success_rate.clamp(0.0, 1.0) * RATE_STEPS).round() as u16);
278    let streak = u64::from(memory.streak as u16);
279    let status = u64::from(status_code(memory.last_status));
280
281    observations | (rate << 16) | (streak << 32) | (status << 48)
282}
283
284/// Read a record back out of one word.
285fn unpack(packed: u64) -> SiteMemory {
286    let observations = (packed & 0xffff) as u32;
287    let rate = ((packed >> 16) & 0xffff) as u16;
288    let streak = ((packed >> 32) & 0xffff) as u16 as i16;
289    let status = ((packed >> 48) & 0xff) as u8;
290
291    SiteMemory {
292        observations,
293        success_rate: f32::from(rate) / RATE_STEPS,
294        streak,
295        last_status: status_from_code(status),
296    }
297}
298
299/// The number a status class is stored as.
300///
301/// Written out here rather than taken from the router crate, because a stored
302/// number has to keep meaning the same thing and a crate that owns an open enum
303/// is free to renumber it.
304fn status_code(status: StatusClass) -> u8 {
305    match status {
306        StatusClass::Ok => 1,
307        StatusClass::Empty => 2,
308        StatusClass::BadRequest => 3,
309        StatusClass::NeedsLogin => 4,
310        StatusClass::Blocked => 5,
311        StatusClass::NotFound => 6,
312        StatusClass::RateLimited => 7,
313        StatusClass::ServerError => 8,
314        // Including `Unknown`, and including a class added after this was
315        // written. Nothing was recorded is the honest reading of both.
316        _ => 0,
317    }
318}
319
320/// The status class a stored number means.
321fn status_from_code(code: u8) -> StatusClass {
322    match code {
323        1 => StatusClass::Ok,
324        2 => StatusClass::Empty,
325        3 => StatusClass::BadRequest,
326        4 => StatusClass::NeedsLogin,
327        5 => StatusClass::Blocked,
328        6 => StatusClass::NotFound,
329        7 => StatusClass::RateLimited,
330        8 => StatusClass::ServerError,
331        _ => StatusClass::Unknown,
332    }
333}
334
335#[cfg(test)]
336mod tests {
337    // A test may unwrap and may panic: a test that cannot set itself up should
338    // fail loudly rather than quietly measure nothing.
339    #![allow(
340        clippy::unwrap_used,
341        clippy::expect_used,
342        clippy::panic,
343        clippy::unreachable,
344        clippy::indexing_slicing,
345        clippy::string_slice
346    )]
347    use super::*;
348
349    fn url(raw: &str) -> Url {
350        Url::parse(raw).expect("a url")
351    }
352
353    #[test]
354    fn a_site_is_remembered_and_an_unseen_one_is_not() {
355        let store = SiteMemoryStore::default();
356        let seen = url("https://example.com/a");
357
358        assert!(store.get(&seen).is_none());
359        assert!(store.is_empty());
360
361        store.observe(&seen, &AttemptOutcome::failed(StatusClass::Blocked, 900));
362        let memory = store.get(&seen).expect("a record");
363
364        assert_eq!(memory.observations, 1);
365        assert_eq!(memory.streak, -1);
366        assert_eq!(memory.last_status, StatusClass::Blocked);
367        assert_eq!(memory.success_rate, 0.0);
368        assert!(store.get(&url("https://other.example.org/a")).is_none());
369    }
370
371    #[test]
372    fn every_host_under_one_name_shares_a_record() {
373        let store = SiteMemoryStore::default();
374        store.observe(
375            &url("https://www.example.com/a"),
376            &AttemptOutcome::failed(StatusClass::Blocked, 100),
377        );
378        store.observe(
379            &url("https://api.example.com/b"),
380            &AttemptOutcome::failed(StatusClass::Blocked, 100),
381        );
382
383        let memory = store.get(&url("https://example.com/c")).expect("a record");
384        assert_eq!(memory.observations, 2);
385        assert_eq!(memory.streak, -2);
386        assert_eq!(store.len(), 1);
387    }
388
389    #[test]
390    fn a_streak_turns_around_rather_than_counting_through_zero() {
391        let store = SiteMemoryStore::default();
392        let site = url("https://example.com/a");
393
394        for _ in 0..3 {
395            store.observe(&site, &AttemptOutcome::failed(StatusClass::Blocked, 10));
396        }
397        assert_eq!(store.get(&site).expect("a record").streak, -3);
398
399        store.observe(&site, &AttemptOutcome::ok(2_000, 10));
400        let memory = store.get(&site).expect("a record");
401        assert_eq!(memory.streak, 1);
402        assert_eq!(memory.observations, 4);
403        assert!(memory.success_rate > 0.0);
404    }
405
406    #[test]
407    fn the_table_never_grows_past_its_capacity() {
408        let store = SiteMemoryStore::new(64);
409        assert_eq!(store.capacity(), 64);
410
411        for n in 0..5_000 {
412            let site = url(&format!("https://site-{n}.example{n}.com/a"));
413            store.observe(&site, &AttemptOutcome::ok(1_000, 20));
414        }
415
416        assert!(
417            store.len() <= store.capacity(),
418            "{} records in {} slots",
419            store.len(),
420            store.capacity()
421        );
422        // A table that stayed empty would satisfy the bound and prove nothing.
423        assert!(store.len() > 16, "only {} slots filled", store.len());
424    }
425
426    #[test]
427    fn a_capacity_is_rounded_up_and_held_inside_its_limits() {
428        assert_eq!(SiteMemoryStore::new(1).capacity(), MIN_CAPACITY);
429        assert_eq!(SiteMemoryStore::new(100).capacity(), 128);
430        assert_eq!(SiteMemoryStore::new(usize::MAX).capacity(), MAX_CAPACITY);
431    }
432
433    #[test]
434    fn zero_capacity_disables_site_memory() {
435        let store = SiteMemoryStore::new(0);
436        let site = url("https://example.com/a");
437        assert_eq!(store.capacity(), 0);
438        store.observe(&site, &AttemptOutcome::failed(StatusClass::Blocked, 10));
439        store.remember(
440            &site,
441            SiteMemory {
442                observations: 9,
443                success_rate: 0.0,
444                streak: -9,
445                last_status: StatusClass::Blocked,
446            },
447        );
448        assert!(store.get(&site).is_none());
449        assert!(store.is_empty());
450        store.clear();
451        assert_eq!(store.capacity(), 0);
452    }
453
454    #[test]
455    fn a_record_survives_the_trip_through_one_word() {
456        let cases = [
457            SiteMemory::cold(),
458            SiteMemory {
459                observations: 12,
460                success_rate: 0.5,
461                streak: -3,
462                last_status: StatusClass::Blocked,
463            },
464            SiteMemory {
465                observations: u32::MAX,
466                success_rate: 1.0,
467                streak: i16::MAX,
468                last_status: StatusClass::RateLimited,
469            },
470            SiteMemory {
471                observations: 1,
472                success_rate: 0.0,
473                streak: i16::MIN,
474                last_status: StatusClass::Empty,
475            },
476        ];
477
478        for memory in cases {
479            let read = unpack(pack(memory));
480            assert_eq!(read.streak, memory.streak, "{memory:?}");
481            assert_eq!(read.last_status, memory.last_status, "{memory:?}");
482            assert_eq!(
483                read.observations,
484                memory.observations.min(u32::from(u16::MAX)),
485                "{memory:?}"
486            );
487            assert!(
488                (read.success_rate - memory.success_rate).abs() < 0.001,
489                "{memory:?} came back at {}",
490                read.success_rate
491            );
492        }
493    }
494
495    #[test]
496    fn a_literal_address_is_not_a_site_to_remember() {
497        let store = SiteMemoryStore::default();
498        let literal = url("http://192.0.2.1/status");
499
500        store.observe(&literal, &AttemptOutcome::ok(10, 10));
501        assert!(store.get(&literal).is_none());
502        assert!(store.is_empty());
503    }
504
505    #[test]
506    fn a_record_can_be_written_directly_and_cleared() {
507        let store = SiteMemoryStore::default();
508        let site = url("https://example.com/a");
509
510        store.remember(
511            &site,
512            SiteMemory {
513                observations: 9,
514                success_rate: 0.1,
515                streak: -4,
516                last_status: StatusClass::Blocked,
517            },
518        );
519        assert_eq!(store.get(&site).expect("a record").observations, 9);
520
521        store.clear();
522        assert!(store.get(&site).is_none());
523    }
524
525    #[test]
526    fn records_from_many_threads_all_land() {
527        let store = std::sync::Arc::new(SiteMemoryStore::default());
528        let site = url("https://example.com/a");
529
530        std::thread::scope(|scope| {
531            for _ in 0..4 {
532                let store = std::sync::Arc::clone(&store);
533                let site = site.clone();
534                scope.spawn(move || {
535                    for _ in 0..50 {
536                        store.observe(&site, &AttemptOutcome::ok(100, 10));
537                    }
538                });
539            }
540        });
541
542        assert_eq!(store.get(&site).expect("a record").observations, 200);
543    }
544}