cbe_program_runtime/
executor_cache.rs

1use {
2    crate::executor::Executor,
3    log::*,
4    rand::Rng,
5    cbe_sdk::{pubkey::Pubkey, saturating_add_assign, slot_history::Slot, stake_history::Epoch},
6    std::{
7        collections::HashMap,
8        fmt::Debug,
9        ops::Div,
10        sync::{
11            atomic::{AtomicU64, Ordering::Relaxed},
12            Arc, RwLock,
13        },
14    },
15};
16
17/// Relation between a TransactionExecutorCacheEntry and its matching BankExecutorCacheEntry
18#[repr(u8)]
19#[derive(Clone, Copy, PartialEq, Eq, Debug)]
20pub enum TxBankExecutorCacheDiff {
21    /// The TransactionExecutorCacheEntry did not change and is the same as the BankExecutorCacheEntry.
22    None,
23    /// The TransactionExecutorCacheEntry was inserted, no matching BankExecutorCacheEntry exists, so it needs to be inserted.
24    Inserted,
25    /// The TransactionExecutorCacheEntry was replaced, the matching BankExecutorCacheEntry needs to be updated.
26    Updated,
27}
28
29/// An entry of the TransactionExecutorCache
30#[derive(Debug)]
31pub struct TransactionExecutorCacheEntry {
32    executor: Arc<dyn Executor>,
33    difference: TxBankExecutorCacheDiff,
34}
35
36/// A subset of the BankExecutorCache containing only the executors relevant to one transaction
37///
38/// The BankExecutorCache can not be updated directly as transaction batches are
39/// processed in parallel, which would cause a race condition.
40#[derive(Default, Debug)]
41pub struct TransactionExecutorCache {
42    pub executors: HashMap<Pubkey, TransactionExecutorCacheEntry>,
43}
44
45impl TransactionExecutorCache {
46    pub fn new(executable_keys: impl Iterator<Item = (Pubkey, Arc<dyn Executor>)>) -> Self {
47        Self {
48            executors: executable_keys
49                .map(|(key, executor)| {
50                    let entry = TransactionExecutorCacheEntry {
51                        executor,
52                        difference: TxBankExecutorCacheDiff::None,
53                    };
54                    (key, entry)
55                })
56                .collect(),
57        }
58    }
59
60    pub fn get(&self, key: &Pubkey) -> Option<Arc<dyn Executor>> {
61        self.executors.get(key).map(|entry| entry.executor.clone())
62    }
63
64    pub fn set(&mut self, key: Pubkey, executor: Arc<dyn Executor>, replacement: bool) {
65        let difference = if replacement {
66            TxBankExecutorCacheDiff::Updated
67        } else {
68            TxBankExecutorCacheDiff::Inserted
69        };
70        let entry = TransactionExecutorCacheEntry {
71            executor,
72            difference,
73        };
74        let _was_replaced = self.executors.insert(key, entry).is_some();
75    }
76
77    pub fn update_global_cache(
78        &self,
79        global_cache: &RwLock<BankExecutorCache>,
80        selector: impl Fn(TxBankExecutorCacheDiff) -> bool,
81    ) {
82        let executors_delta: Vec<_> = self
83            .executors
84            .iter()
85            .filter_map(|(key, entry)| {
86                selector(entry.difference).then(|| (key, entry.executor.clone()))
87            })
88            .collect();
89        if !executors_delta.is_empty() {
90            global_cache.write().unwrap().put(&executors_delta);
91        }
92    }
93}
94
95/// Capacity of `BankExecutorCache`
96pub const MAX_CACHED_EXECUTORS: usize = 256;
97
98/// An entry of the BankExecutorCache
99#[derive(Debug)]
100pub struct BankExecutorCacheEntry {
101    prev_epoch_count: u64,
102    epoch_count: AtomicU64,
103    executor: Arc<dyn Executor>,
104    pub hit_count: AtomicU64,
105}
106
107impl Clone for BankExecutorCacheEntry {
108    fn clone(&self) -> Self {
109        Self {
110            prev_epoch_count: self.prev_epoch_count,
111            epoch_count: AtomicU64::new(self.epoch_count.load(Relaxed)),
112            executor: self.executor.clone(),
113            hit_count: AtomicU64::new(self.hit_count.load(Relaxed)),
114        }
115    }
116}
117
118/// LFU Cache of executors which exists once per bank
119#[derive(Debug)]
120pub struct BankExecutorCache {
121    capacity: usize,
122    current_epoch: Epoch,
123    pub executors: HashMap<Pubkey, BankExecutorCacheEntry>,
124    pub stats: Stats,
125}
126
127impl Default for BankExecutorCache {
128    fn default() -> Self {
129        Self {
130            capacity: MAX_CACHED_EXECUTORS,
131            current_epoch: Epoch::default(),
132            executors: HashMap::default(),
133            stats: Stats::default(),
134        }
135    }
136}
137
138#[cfg(RUSTC_WITH_SPECIALIZATION)]
139impl cbe_frozen_abi::abi_example::AbiExample for BankExecutorCache {
140    fn example() -> Self {
141        // Delegate AbiExample impl to Default before going deep and stuck with
142        // not easily impl-able Arc<dyn Executor> due to rust's coherence issue
143        // This is safe because BankExecutorCache isn't serializable by definition.
144        Self::default()
145    }
146}
147
148impl BankExecutorCache {
149    pub fn new(max_capacity: usize, current_epoch: Epoch) -> Self {
150        Self {
151            capacity: max_capacity,
152            current_epoch,
153            executors: HashMap::new(),
154            stats: Stats::default(),
155        }
156    }
157
158    pub fn new_from_parent_bank_executors(
159        parent_bank_executors: &BankExecutorCache,
160        current_epoch: Epoch,
161    ) -> Self {
162        let executors = if parent_bank_executors.current_epoch == current_epoch {
163            parent_bank_executors.executors.clone()
164        } else {
165            parent_bank_executors
166                .executors
167                .iter()
168                .map(|(&key, entry)| {
169                    let entry = BankExecutorCacheEntry {
170                        prev_epoch_count: entry.epoch_count.load(Relaxed),
171                        epoch_count: AtomicU64::default(),
172                        executor: entry.executor.clone(),
173                        hit_count: AtomicU64::new(entry.hit_count.load(Relaxed)),
174                    };
175                    (key, entry)
176                })
177                .collect()
178        };
179
180        Self {
181            capacity: parent_bank_executors.capacity,
182            current_epoch,
183            executors,
184            stats: Stats::default(),
185        }
186    }
187
188    pub fn get(&self, pubkey: &Pubkey) -> Option<Arc<dyn Executor>> {
189        if let Some(entry) = self.executors.get(pubkey) {
190            self.stats.hits.fetch_add(1, Relaxed);
191            entry.epoch_count.fetch_add(1, Relaxed);
192            entry.hit_count.fetch_add(1, Relaxed);
193            Some(entry.executor.clone())
194        } else {
195            self.stats.misses.fetch_add(1, Relaxed);
196            None
197        }
198    }
199
200    fn put(&mut self, executors: &[(&Pubkey, Arc<dyn Executor>)]) {
201        let mut new_executors: Vec<_> = executors
202            .iter()
203            .filter_map(|(key, executor)| {
204                if let Some(mut entry) = self.remove(key) {
205                    self.stats.replacements.fetch_add(1, Relaxed);
206                    entry.executor = executor.clone();
207                    let _ = self.executors.insert(**key, entry);
208                    None
209                } else {
210                    self.stats.insertions.fetch_add(1, Relaxed);
211                    Some((*key, executor))
212                }
213            })
214            .collect();
215
216        if !new_executors.is_empty() {
217            let mut counts = self
218                .executors
219                .iter()
220                .map(|(key, entry)| {
221                    let count = entry
222                        .prev_epoch_count
223                        .saturating_add(entry.epoch_count.load(Relaxed));
224                    (key, count)
225                })
226                .collect::<Vec<_>>();
227            counts.sort_unstable_by_key(|(_, count)| *count);
228
229            let primer_counts = Self::get_primer_counts(counts.as_slice(), new_executors.len());
230
231            if self.executors.len() >= self.capacity {
232                let mut least_keys = counts
233                    .iter()
234                    .take(new_executors.len())
235                    .map(|least| *least.0)
236                    .collect::<Vec<_>>();
237                for least_key in least_keys.drain(..) {
238                    let _ = self.remove(&least_key);
239                    self.stats
240                        .evictions
241                        .entry(least_key)
242                        .and_modify(|c| saturating_add_assign!(*c, 1))
243                        .or_insert(1);
244                }
245            }
246
247            for ((key, executor), primer_count) in new_executors.drain(..).zip(primer_counts) {
248                let entry = BankExecutorCacheEntry {
249                    prev_epoch_count: 0,
250                    epoch_count: AtomicU64::new(primer_count),
251                    executor: executor.clone(),
252                    hit_count: AtomicU64::new(1),
253                };
254                let _ = self.executors.insert(*key, entry);
255            }
256        }
257    }
258
259    pub fn remove(&mut self, pubkey: &Pubkey) -> Option<BankExecutorCacheEntry> {
260        let maybe_entry = self.executors.remove(pubkey);
261        if let Some(entry) = maybe_entry.as_ref() {
262            if entry.hit_count.load(Relaxed) == 1 {
263                self.stats.one_hit_wonders.fetch_add(1, Relaxed);
264            }
265        }
266        maybe_entry
267    }
268
269    pub fn clear(&mut self) {
270        *self = BankExecutorCache::default();
271    }
272
273    pub fn get_primer_count_upper_bound_inclusive(counts: &[(&Pubkey, u64)]) -> u64 {
274        const PRIMER_COUNT_TARGET_PERCENTILE: u64 = 85;
275        #[allow(clippy::assertions_on_constants)]
276        {
277            assert!(PRIMER_COUNT_TARGET_PERCENTILE <= 100);
278        }
279        // Executor use-frequencies are assumed to fit a Pareto distribution.  Choose an
280        // upper-bound for our primer count as the actual count at the target rank to avoid
281        // an upward bias
282
283        let target_index = u64::try_from(counts.len().saturating_sub(1))
284            .ok()
285            .and_then(|counts| {
286                let index = counts
287                    .saturating_mul(PRIMER_COUNT_TARGET_PERCENTILE)
288                    .div(100); // switch to u64::saturating_div once stable
289                usize::try_from(index).ok()
290            })
291            .unwrap_or(0);
292
293        counts
294            .get(target_index)
295            .map(|(_, count)| *count)
296            .unwrap_or(0)
297    }
298
299    pub fn get_primer_counts(counts: &[(&Pubkey, u64)], num_counts: usize) -> Vec<u64> {
300        let max_primer_count = Self::get_primer_count_upper_bound_inclusive(counts);
301        let mut rng = rand::thread_rng();
302
303        (0..num_counts)
304            .map(|_| rng.gen_range(0, max_primer_count.saturating_add(1)))
305            .collect::<Vec<_>>()
306    }
307}
308
309/// Statistics of the entire `BankExecutorCache`
310#[derive(Debug, Default)]
311pub struct Stats {
312    pub hits: AtomicU64,
313    pub misses: AtomicU64,
314    pub evictions: HashMap<Pubkey, u64>,
315    pub insertions: AtomicU64,
316    pub replacements: AtomicU64,
317    pub one_hit_wonders: AtomicU64,
318}
319
320impl Stats {
321    /// Logs the measurement values
322    pub fn submit(&self, slot: Slot) {
323        let hits = self.hits.load(Relaxed);
324        let misses = self.misses.load(Relaxed);
325        let insertions = self.insertions.load(Relaxed);
326        let replacements = self.replacements.load(Relaxed);
327        let one_hit_wonders = self.one_hit_wonders.load(Relaxed);
328        let evictions: u64 = self.evictions.values().sum();
329        datapoint_info!(
330            "bank-executor-cache-stats",
331            ("slot", slot, i64),
332            ("hits", hits, i64),
333            ("misses", misses, i64),
334            ("evictions", evictions, i64),
335            ("insertions", insertions, i64),
336            ("replacements", replacements, i64),
337            ("one_hit_wonders", one_hit_wonders, i64),
338        );
339        debug!(
340            "Executor Cache Stats -- Hits: {}, Misses: {}, Evictions: {}, Insertions: {}, Replacements: {}, One-Hit-Wonders: {}",
341            hits, misses, evictions, insertions, replacements, one_hit_wonders,
342        );
343        if log_enabled!(log::Level::Trace) && !self.evictions.is_empty() {
344            let mut evictions = self.evictions.iter().collect::<Vec<_>>();
345            evictions.sort_by_key(|e| e.1);
346            let evictions = evictions
347                .into_iter()
348                .rev()
349                .map(|(program_id, evictions)| {
350                    format!("  {:<44}  {}", program_id.to_string(), evictions)
351                })
352                .collect::<Vec<_>>();
353            let evictions = evictions.join("\n");
354            trace!(
355                "Eviction Details:\n  {:<44}  {}\n{}",
356                "Program",
357                "Count",
358                evictions
359            );
360        }
361    }
362}
363
364#[allow(clippy::indexing_slicing)]
365#[cfg(test)]
366mod tests {
367    use {
368        super::*, crate::invoke_context::InvokeContext, cbe_sdk::instruction::InstructionError,
369    };
370
371    #[derive(Debug)]
372    struct TestExecutor {}
373    impl Executor for TestExecutor {
374        fn execute(
375            &self,
376            _invoke_context: &mut InvokeContext,
377        ) -> std::result::Result<(), InstructionError> {
378            Ok(())
379        }
380    }
381
382    #[test]
383    fn test_executor_cache() {
384        let key1 = cbe_sdk::pubkey::new_rand();
385        let key2 = cbe_sdk::pubkey::new_rand();
386        let key3 = cbe_sdk::pubkey::new_rand();
387        let key4 = cbe_sdk::pubkey::new_rand();
388        let executor: Arc<dyn Executor> = Arc::new(TestExecutor {});
389        let mut cache = BankExecutorCache::new(3, 0);
390
391        cache.put(&[(&key1, executor.clone())]);
392        cache.put(&[(&key2, executor.clone())]);
393        cache.put(&[(&key3, executor.clone())]);
394        assert!(cache.get(&key1).is_some());
395        assert!(cache.get(&key2).is_some());
396        assert!(cache.get(&key3).is_some());
397
398        assert!(cache.get(&key1).is_some());
399        assert!(cache.get(&key1).is_some());
400        assert!(cache.get(&key2).is_some());
401        cache.put(&[(&key4, executor.clone())]);
402        assert!(cache.get(&key4).is_some());
403        let num_retained = [&key1, &key2, &key3]
404            .iter()
405            .filter_map(|key| cache.get(key))
406            .count();
407        assert_eq!(num_retained, 2);
408
409        assert!(cache.get(&key4).is_some());
410        assert!(cache.get(&key4).is_some());
411        assert!(cache.get(&key4).is_some());
412        cache.put(&[(&key3, executor.clone())]);
413        assert!(cache.get(&key3).is_some());
414        let num_retained = [&key1, &key2, &key4]
415            .iter()
416            .filter_map(|key| cache.get(key))
417            .count();
418        assert_eq!(num_retained, 2);
419    }
420
421    #[test]
422    fn test_cached_executor_eviction() {
423        let key1 = cbe_sdk::pubkey::new_rand();
424        let key2 = cbe_sdk::pubkey::new_rand();
425        let key3 = cbe_sdk::pubkey::new_rand();
426        let key4 = cbe_sdk::pubkey::new_rand();
427        let executor: Arc<dyn Executor> = Arc::new(TestExecutor {});
428        let mut cache = BankExecutorCache::new(3, 0);
429        assert!(cache.current_epoch == 0);
430
431        cache.put(&[(&key1, executor.clone())]);
432        cache.put(&[(&key2, executor.clone())]);
433        cache.put(&[(&key3, executor.clone())]);
434        assert!(cache.get(&key1).is_some());
435        assert!(cache.get(&key1).is_some());
436        assert!(cache.get(&key1).is_some());
437
438        let mut cache = BankExecutorCache::new_from_parent_bank_executors(&cache, 1);
439        assert!(cache.current_epoch == 1);
440
441        assert!(cache.get(&key2).is_some());
442        assert!(cache.get(&key2).is_some());
443        assert!(cache.get(&key3).is_some());
444        cache.put(&[(&key4, executor.clone())]);
445
446        assert!(cache.get(&key4).is_some());
447        let num_retained = [&key1, &key2, &key3]
448            .iter()
449            .filter_map(|key| cache.get(key))
450            .count();
451        assert_eq!(num_retained, 2);
452
453        cache.put(&[(&key1, executor.clone())]);
454        cache.put(&[(&key3, executor.clone())]);
455        assert!(cache.get(&key1).is_some());
456        assert!(cache.get(&key3).is_some());
457        let num_retained = [&key2, &key4]
458            .iter()
459            .filter_map(|key| cache.get(key))
460            .count();
461        assert_eq!(num_retained, 1);
462
463        cache = BankExecutorCache::new_from_parent_bank_executors(&cache, 2);
464        assert!(cache.current_epoch == 2);
465
466        cache.put(&[(&key3, executor.clone())]);
467        assert!(cache.get(&key3).is_some());
468    }
469
470    #[test]
471    fn test_executor_cache_evicts_smallest() {
472        let key1 = cbe_sdk::pubkey::new_rand();
473        let key2 = cbe_sdk::pubkey::new_rand();
474        let key3 = cbe_sdk::pubkey::new_rand();
475        let executor: Arc<dyn Executor> = Arc::new(TestExecutor {});
476        let mut cache = BankExecutorCache::new(2, 0);
477
478        cache.put(&[(&key1, executor.clone())]);
479        for _ in 0..5 {
480            let _ = cache.get(&key1);
481        }
482        cache.put(&[(&key2, executor.clone())]);
483        // make key1's use-count for sure greater than key2's
484        let _ = cache.get(&key1);
485
486        let mut entries = cache
487            .executors
488            .iter()
489            .map(|(k, v)| (*k, v.epoch_count.load(Relaxed)))
490            .collect::<Vec<_>>();
491        entries.sort_by_key(|(_, v)| *v);
492        assert!(entries[0].1 < entries[1].1);
493
494        cache.put(&[(&key3, executor.clone())]);
495        assert!(cache.get(&entries[0].0).is_none());
496        assert!(cache.get(&entries[1].0).is_some());
497    }
498
499    #[test]
500    fn test_executor_cache_one_hit_wonder_counter() {
501        let mut cache = BankExecutorCache::new(1, 0);
502
503        let one_hit_wonder = Pubkey::new_unique();
504        let popular = Pubkey::new_unique();
505        let executor: Arc<dyn Executor> = Arc::new(TestExecutor {});
506
507        // make sure we're starting from where we think we are
508        assert_eq!(cache.stats.one_hit_wonders.load(Relaxed), 0);
509
510        // add our one-hit-wonder
511        cache.put(&[(&one_hit_wonder, executor.clone())]);
512        assert_eq!(cache.executors[&one_hit_wonder].hit_count.load(Relaxed), 1);
513        // displace the one-hit-wonder with "popular program"
514        cache.put(&[(&popular, executor.clone())]);
515        assert_eq!(cache.executors[&popular].hit_count.load(Relaxed), 1);
516
517        // one-hit-wonder counter incremented
518        assert_eq!(cache.stats.one_hit_wonders.load(Relaxed), 1);
519
520        // make "popular program" popular
521        cache.get(&popular).unwrap();
522        assert_eq!(cache.executors[&popular].hit_count.load(Relaxed), 2);
523
524        // evict "popular program"
525        cache.put(&[(&one_hit_wonder, executor.clone())]);
526        assert_eq!(cache.executors[&one_hit_wonder].hit_count.load(Relaxed), 1);
527
528        // one-hit-wonder counter not incremented
529        assert_eq!(cache.stats.one_hit_wonders.load(Relaxed), 1);
530    }
531
532    #[test]
533    fn test_executor_cache_get_primer_count_upper_bound_inclusive() {
534        let pubkey = Pubkey::default();
535        let v = [];
536        assert_eq!(
537            BankExecutorCache::get_primer_count_upper_bound_inclusive(&v),
538            0
539        );
540        let v = [(&pubkey, 1)];
541        assert_eq!(
542            BankExecutorCache::get_primer_count_upper_bound_inclusive(&v),
543            1
544        );
545        let v = (0u64..10).map(|i| (&pubkey, i)).collect::<Vec<_>>();
546        assert_eq!(
547            BankExecutorCache::get_primer_count_upper_bound_inclusive(v.as_slice()),
548            7
549        );
550    }
551
552    #[test]
553    fn test_executor_cache_stats() {
554        #[derive(Debug, Default, PartialEq)]
555        struct ComparableStats {
556            hits: u64,
557            misses: u64,
558            evictions: HashMap<Pubkey, u64>,
559            insertions: u64,
560            replacements: u64,
561            one_hit_wonders: u64,
562        }
563        impl From<&Stats> for ComparableStats {
564            fn from(stats: &Stats) -> Self {
565                let Stats {
566                    hits,
567                    misses,
568                    evictions,
569                    insertions,
570                    replacements,
571                    one_hit_wonders,
572                } = stats;
573                ComparableStats {
574                    hits: hits.load(Relaxed),
575                    misses: misses.load(Relaxed),
576                    evictions: evictions.clone(),
577                    insertions: insertions.load(Relaxed),
578                    replacements: replacements.load(Relaxed),
579                    one_hit_wonders: one_hit_wonders.load(Relaxed),
580                }
581            }
582        }
583
584        const CURRENT_EPOCH: Epoch = 0;
585        let mut cache = BankExecutorCache::new(2, CURRENT_EPOCH);
586        let mut expected_stats = ComparableStats::default();
587
588        let program_id1 = Pubkey::new_unique();
589        let program_id2 = Pubkey::new_unique();
590        let executor: Arc<dyn Executor> = Arc::new(TestExecutor {});
591
592        // make sure we're starting from where we think we are
593        assert_eq!(ComparableStats::from(&cache.stats), expected_stats,);
594
595        // insert some executors
596        cache.put(&[(&program_id1, executor.clone())]);
597        cache.put(&[(&program_id2, executor.clone())]);
598        expected_stats.insertions += 2;
599        assert_eq!(ComparableStats::from(&cache.stats), expected_stats);
600
601        // replace a one-hit-wonder executor
602        cache.put(&[(&program_id1, executor.clone())]);
603        expected_stats.replacements += 1;
604        expected_stats.one_hit_wonders += 1;
605        assert_eq!(ComparableStats::from(&cache.stats), expected_stats);
606
607        // hit some executors
608        cache.get(&program_id1);
609        cache.get(&program_id1);
610        cache.get(&program_id2);
611        expected_stats.hits += 3;
612        assert_eq!(ComparableStats::from(&cache.stats), expected_stats);
613
614        // miss an executor
615        cache.get(&Pubkey::new_unique());
616        expected_stats.misses += 1;
617        assert_eq!(ComparableStats::from(&cache.stats), expected_stats);
618
619        // evict an executor
620        cache.put(&[(&Pubkey::new_unique(), executor.clone())]);
621        expected_stats.insertions += 1;
622        expected_stats.evictions.insert(program_id2, 1);
623        assert_eq!(ComparableStats::from(&cache.stats), expected_stats);
624
625        // make sure stats are cleared in new_from_parent
626        assert_eq!(
627            ComparableStats::from(
628                &BankExecutorCache::new_from_parent_bank_executors(&cache, CURRENT_EPOCH).stats
629            ),
630            ComparableStats::default()
631        );
632        assert_eq!(
633            ComparableStats::from(
634                &BankExecutorCache::new_from_parent_bank_executors(&cache, CURRENT_EPOCH + 1).stats
635            ),
636            ComparableStats::default()
637        );
638    }
639}
cbe_program_runtime/executor_cache.rs

cbe_program_runtime/
executor_cache.rs
