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 cid::Cid;
16use positioned_io::{ReadAt, Size};
17use std::{
18    num::NonZeroUsize,
19    sync::{
20        Arc, LazyLock,
21        atomic::{AtomicUsize, Ordering},
22    },
23};
24
25use crate::utils::{ShallowClone, cache::SizeTrackingLruCache, get_size::CidWrapper};
26
27pub trait RandomAccessFileReader: ReadAt + Size + Send + Sync + 'static {}
28impl<X: ReadAt + Size + Send + Sync + 'static> RandomAccessFileReader for X {}
29
30/// Multiple `.forest.car.zst` archives may use the same cache, each with a
31/// unique cache key.
32pub type CacheKey = u64;
33
34type FrameOffset = u64;
35
36/// According to FRC-0108, v2 snapshots have exactly one root pointing to metadata
37pub const V2_SNAPSHOT_ROOT_COUNT: usize = 1;
38
39pub static ZSTD_FRAME_CACHE_DEFAULT_MAX_SIZE: LazyLock<usize> = LazyLock::new(|| {
40    const ENV_KEY: &str = "FOREST_ZSTD_FRAME_CACHE_DEFAULT_MAX_SIZE";
41    if let Ok(value) = std::env::var(ENV_KEY) {
42        if let Ok(size) = value.parse::<NonZeroUsize>() {
43            let size = size.get();
44            tracing::info!("zstd frame max size is set to {size} via {ENV_KEY}");
45            return size;
46        } else {
47            tracing::error!(
48                "Failed to parse {ENV_KEY}={value}, value should be a positive integer"
49            );
50        }
51    }
52    // 256 MiB
53    256 * 1024 * 1024
54});
55
56pub struct ZstdFrameCache {
57    /// Maximum size in bytes. Pages will be evicted if the total size of the
58    /// cache exceeds this amount.
59    pub max_size: usize,
60    current_size: Arc<AtomicUsize>,
61    // use `hashbrown::HashMap` here because its `GetSize` implementation is accurate
62    // (thanks to `hashbrown::HashMap::allocation_size`).
63    lru: SizeTrackingLruCache<(FrameOffset, CacheKey), hashbrown::HashMap<CidWrapper, Bytes>>,
64}
65
66impl ShallowClone for ZstdFrameCache {
67    fn shallow_clone(&self) -> Self {
68        Self {
69            max_size: self.max_size,
70            current_size: self.current_size.shallow_clone(),
71            lru: self.lru.shallow_clone(),
72        }
73    }
74}
75
76impl Default for ZstdFrameCache {
77    fn default() -> Self {
78        ZstdFrameCache::new(*ZSTD_FRAME_CACHE_DEFAULT_MAX_SIZE)
79    }
80}
81
82impl ZstdFrameCache {
83    pub fn new(max_size: usize) -> Self {
84        ZstdFrameCache {
85            max_size,
86            current_size: Arc::new(AtomicUsize::new(0)),
87            lru: SizeTrackingLruCache::unbounded_with_metrics("zstd_frame".into()),
88        }
89    }
90
91    /// Return a clone of the value associated with `cid`. If a value is found,
92    /// the cache entry is moved to the top of the queue.
93    pub fn get(&self, offset: FrameOffset, key: CacheKey, cid: Cid) -> Option<Option<Bytes>> {
94        self.lru
95            .cache()
96            .write()
97            .get(&(offset, key))
98            .map(|index| index.get(&CidWrapper::from(cid)).cloned())
99    }
100
101    /// Insert entry into lru-cache and evict pages if `max_size` has been exceeded.
102    pub fn put(
103        &self,
104        offset: FrameOffset,
105        key: CacheKey,
106        mut index: hashbrown::HashMap<CidWrapper, Bytes>,
107    ) {
108        index.shrink_to_fit();
109
110        let lru_key = (offset, key);
111        let lru_key_size = lru_key.get_size();
112        let entry_size = index.get_size();
113        // Skip large items
114        if entry_size.saturating_add(lru_key_size) >= self.max_size {
115            return;
116        }
117
118        if let Some(prev_entry) = self.lru.push(lru_key, index) {
119            // keys are cancelled out
120            self.current_size.fetch_add(entry_size, Ordering::Relaxed);
121            self.current_size
122                .fetch_sub(prev_entry.get_size(), Ordering::Relaxed);
123        } else {
124            self.current_size
125                .fetch_add(entry_size.saturating_add(lru_key_size), Ordering::Relaxed);
126        }
127        while self.current_size.load(Ordering::Relaxed) > self.max_size {
128            if let Some((prev_key, prev_entry)) = self.lru.pop_lru() {
129                self.current_size.fetch_sub(
130                    prev_key.get_size().saturating_add(prev_entry.get_size()),
131                    Ordering::Relaxed,
132                );
133            } else {
134                break;
135            }
136        }
137    }
138}
139
140#[cfg(test)]
141mod tests {
142    use super::*;
143    use crate::utils::{multihash::MultihashCode, rand::forest_rng};
144    use fvm_ipld_encoding::IPLD_RAW;
145    use multihash_derive::MultihashDigest;
146    use rand::Rng;
147
148    #[test]
149    fn test_zstd_frame_cache_size() {
150        let mut rng = forest_rng();
151        let cache = ZstdFrameCache::new(10);
152        for i in 0..100 {
153            let index = gen_index(&mut rng);
154            cache.put(i, i, index);
155            assert_eq!(
156                cache.current_size.load(Ordering::Relaxed),
157                cache.lru.size_in_bytes()
158            );
159            let index2 = gen_index(&mut rng);
160            cache.put(i, i, index2);
161            assert_eq!(
162                cache.current_size.load(Ordering::Relaxed),
163                cache.lru.size_in_bytes()
164            );
165        }
166    }
167
168    fn gen_index(rng: &mut impl Rng) -> hashbrown::HashMap<CidWrapper, Bytes> {
169        let mut map = hashbrown::HashMap::default();
170        for _ in 0..10 {
171            let vec_len = rng.gen_range(64..1024);
172            let mut data = vec![0; vec_len];
173            rng.fill_bytes(&mut data);
174            let cid = Cid::new_v1(IPLD_RAW, MultihashCode::Blake2b256.digest(&data));
175            map.insert(cid.into(), data.into());
176        }
177        map
178    }
179}
forest/db/car/mod.rs

forest/db/car/
mod.rs
