forest/db/car/
mod.rs

1// Copyright 2019-2026 ChainSafe Systems
2// SPDX-License-Identifier: Apache-2.0, MIT
3mod any;
4pub mod forest;
5mod many;
6pub mod plain;
7
8pub use any::AnyCar;
9pub use forest::ForestCar;
10use get_size2::GetSize as _;
11pub use many::{ManyCar, ReloadableManyCar};
12pub use plain::PlainCar;
13
14use bytes::Bytes;
15use positioned_io::{ReadAt, Size};
16use std::{num::NonZeroUsize, sync::LazyLock};
17
18use crate::prelude::*;
19use quick_cache::Weighter;
20use quick_cache::sync::Cache as QuickCache;
21
22pub trait RandomAccessFileReader: ReadAt + Size + Send + Sync + 'static {}
23impl<X: ReadAt + Size + Send + Sync + 'static> RandomAccessFileReader for X {}
24
25/// Multiple `.forest.car.zst` archives may use the same cache, each with a
26/// unique cache key.
27pub type CacheKey = u64;
28
29type FrameOffset = u64;
30
31/// According to FRC-0108, v2 snapshots have exactly one root pointing to metadata
32pub const V2_SNAPSHOT_ROOT_COUNT: usize = 1;
33
34pub static ZSTD_FRAME_CACHE_DEFAULT_MAX_SIZE: LazyLock<usize> = LazyLock::new(|| {
35    const ENV_KEY: &str = "FOREST_ZSTD_FRAME_CACHE_DEFAULT_MAX_SIZE";
36    if let Ok(value) = std::env::var(ENV_KEY) {
37        if let Ok(size) = value.parse::<NonZeroUsize>() {
38            let size = size.get();
39            tracing::info!("zstd frame max size is set to {size} via {ENV_KEY}");
40            return size;
41        } else {
42            tracing::error!(
43                "Failed to parse {ENV_KEY}={value}, value should be a positive integer"
44            );
45        }
46    }
47    // 512 MiB
48    512 * 1024 * 1024
49});
50
51/// One decompressed zstd frame's index, shared via [`Arc`] so cache lookups
52/// don't deep-copy the inner [`hashbrown::HashMap`]. Snapshot export hits the
53/// cache once per CID; a per-call `HashMap` clone destroys throughput.
54type FrameIndex = Arc<hashbrown::HashMap<CidWrapper, Bytes>>;
55
56/// A [`Weighter`] that bills each entry by `key.get_size() + value.get_size()`.
57/// Used to make [`ZstdFrameCache`] evict by byte size.
58#[derive(Clone, Copy, Debug, Default)]
59pub struct ZstdFrameWeighter;
60
61impl Weighter<(FrameOffset, CacheKey), FrameIndex> for ZstdFrameWeighter {
62    fn weight(&self, key: &(FrameOffset, CacheKey), value: &FrameIndex) -> u64 {
63        // quick_cache treats weight 0 as "do not evict" — clamp to 1 so the
64        // cache never silently pins entries.
65        (key.get_size().saturating_add(value.get_size()) as u64).max(1)
66    }
67}
68
69type ZstdFrameInner = QuickCache<(FrameOffset, CacheKey), FrameIndex, ZstdFrameWeighter>;
70
71#[derive(derive_more::Deref)]
72pub struct ZstdFrameCache {
73    /// Maximum size in bytes. Pages are evicted by the cache when the total
74    /// weight exceeds this amount.
75    pub max_size: usize,
76    #[deref]
77    cache: Arc<ZstdFrameInner>,
78}
79
80impl ShallowClone for ZstdFrameCache {
81    fn shallow_clone(&self) -> Self {
82        Self {
83            max_size: self.max_size,
84            cache: self.cache.shallow_clone(),
85        }
86    }
87}
88
89impl Default for ZstdFrameCache {
90    fn default() -> Self {
91        ZstdFrameCache::new(*ZSTD_FRAME_CACHE_DEFAULT_MAX_SIZE)
92    }
93}
94
95impl ZstdFrameCache {
96    pub fn new(max_size: usize) -> Self {
97        // Items in this cache are decompressed zstd frame indexes — large
98        // hashmaps, so we don't expect many of them. The 64 estimate is a
99        // hint to quick_cache for initial table sizing only; the real bound
100        // is the weight capacity.
101        const ESTIMATED_ITEMS: usize = 64;
102        ZstdFrameCache {
103            max_size,
104            cache: Arc::new(QuickCache::with_weighter(
105                ESTIMATED_ITEMS,
106                max_size as u64,
107                ZstdFrameWeighter,
108            )),
109        }
110    }
111
112    /// Return a clone of the value associated with `cid`. If a value is found,
113    /// the cache entry is touched (moved to the top of the eviction order).
114    pub fn get(&self, offset: FrameOffset, key: CacheKey, cid: Cid) -> Option<Option<Bytes>> {
115        self.cache
116            .get(&(offset, key))
117            .map(|index| index.get(&CidWrapper::from(cid)).cloned())
118    }
119
120    /// Insert entry into the cache. Eviction happens automatically based on
121    /// weight (see [`ZstdFrameWeighter`]).
122    pub fn put(
123        &self,
124        offset: FrameOffset,
125        key: CacheKey,
126        mut index: hashbrown::HashMap<CidWrapper, Bytes>,
127    ) {
128        index.shrink_to_fit();
129
130        let cache_key = (offset, key);
131        let cache_key_size = cache_key.get_size();
132        let entry_size = index.get_size();
133        // Skip individual items larger than the whole cache — they'd evict
134        // everything and still not fit.
135        if entry_size.saturating_add(cache_key_size) > self.max_size {
136            return;
137        }
138        self.insert(cache_key, Arc::new(index));
139    }
140}
141
142#[cfg(test)]
143mod tests {
144    use super::*;
145    use crate::utils::{multihash::MultihashCode, rand::forest_rng};
146    use fvm_ipld_encoding::IPLD_RAW;
147    use multihash_derive::MultihashDigest;
148    use rand::Rng;
149
150    #[test]
151    fn test_zstd_frame_cache_stays_under_max_size() {
152        let mut rng = forest_rng();
153        // Pick a non-trivial cap so a few entries fit before eviction kicks in.
154        let max_size: usize = 64 * 1024;
155        let cache = ZstdFrameCache::new(max_size);
156        for i in 0..100 {
157            cache.put(i, i, gen_index(&mut rng));
158            // After every insert the live weight must remain under the cap;
159            // quick_cache evicts synchronously to keep it that way.
160            assert!(
161                cache.weight() <= max_size as u64,
162                "weight {} exceeds cap {}",
163                cache.weight(),
164                max_size
165            );
166        }
167        // Sanity: after stuffing 100 entries into a cap-bounded cache, at
168        // least one eviction must have happened.
169        assert!(cache.len() < 100);
170    }
171
172    fn gen_index(rng: &mut impl Rng) -> hashbrown::HashMap<CidWrapper, Bytes> {
173        let mut map = hashbrown::HashMap::default();
174        for _ in 0..10 {
175            let vec_len = rng.gen_range(64..1024);
176            let mut data = vec![0; vec_len];
177            rng.fill_bytes(&mut data);
178            let cid = Cid::new_v1(IPLD_RAW, MultihashCode::Blake2b256.digest(&data));
179            map.insert(cid.into(), data.into());
180        }
181        map
182    }
183}
forest/db/car/mod.rs

forest/db/car/
mod.rs
