cfx_storage/impls/delta_mpt/
node_ref_map.rs

1// Copyright 2019 Conflux Foundation. All rights reserved.
2// Conflux is free software and distributed under GNU General Public License.
3// See http://www.gnu.org/licenses/
4
5#[derive(Clone, MallocSizeOfDerive)]
6pub enum TrieCacheSlotOrCacheAlgoData<CacheAlgoDataT: CacheAlgoDataTrait> {
7    TrieCacheSlot(ActualSlabIndex),
8    CacheAlgoData(CacheAlgoDataT),
9}
10
11// TODO(yz): Rename class and explain how this class interact with the lifecycle
12// of trie node.
13/// CacheableNodeRef maintains the information of cached node and possibly
14/// non-cached children of cached node.
15///
16/// Only CacheableNodeRef for Delta MPT is currently implemented.
17///
18/// CacheableNodeRef for persistent MPT may add a field for storage access key,
19/// and a reference count. For persistent MPT, NodeRef (storage access key) for
20/// non-cached node might be kept, to be able to read child node directly from
21/// disk, otherwise the program have to read the current node again to first
22/// obtain the CacheableNodeRef for the non-cached child node. However a
23/// reference count is necessary to prevent NodeRef for non-cached node from
24/// staying forever in the memory.
25#[derive(Clone, MallocSizeOfDerive)]
26pub struct CacheableNodeRefDeltaMpt<CacheAlgoDataT: CacheAlgoDataTrait> {
27    cached: TrieCacheSlotOrCacheAlgoData<CacheAlgoDataT>,
28}
29
30impl<CacheAlgoDataT: CacheAlgoDataTrait>
31    CacheableNodeRefDeltaMpt<CacheAlgoDataT>
32{
33    pub fn new(cached: TrieCacheSlotOrCacheAlgoData<CacheAlgoDataT>) -> Self {
34        Self { cached }
35    }
36
37    pub fn get_cache_info(
38        &self,
39    ) -> &TrieCacheSlotOrCacheAlgoData<CacheAlgoDataT> {
40        &self.cached
41    }
42
43    pub fn get_slot(&self) -> Option<&ActualSlabIndex> {
44        match &self.cached {
45            TrieCacheSlotOrCacheAlgoData::CacheAlgoData(_) => None,
46            TrieCacheSlotOrCacheAlgoData::TrieCacheSlot(slot) => Some(slot),
47        }
48    }
49}
50
51/// Generally, the db key of MPT node is the merkle hash, however it consumes
52/// too much memory. For Delta MPT, the total number of nodes at 1000tps are
53/// relative small compared to memory consumed by Cached TrieNodes, and we don't
54/// need to persist, therefore we could use "row number" as db key.
55pub type DeltaMptDbKey = RowNumberUnderlyingType;
56// Each DeltaMpt is assigned an index. There are not many DeltaMpts to keep at a
57// time.
58pub type DeltaMptId = u16;
59const MPT_ID_RANGE: usize = std::u16::MAX as usize + 1;
60
61// TODO(yz): Optimize the access like NodeRefMapDeltaMpt. Keep a number of
62// TODO(yz): chunks, each delta mpt maintains a deque of chunks. Whenever all
63// TODO(yz): chunks are filled, reclaim one chunk from the mpt with the lowest
64// TODO(yz): chunk cached rate.
65/// Maintains the cache slot / cache info for multiple Delta MPTs.
66#[derive(MallocSizeOfDerive)]
67pub struct NodeRefMapDeltaMpts<CacheAlgoDataT: CacheAlgoDataTrait> {
68    node_ref_maps:
69        Vec<HashMap<DeltaMptDbKey, CacheableNodeRefDeltaMpt<CacheAlgoDataT>>>,
70    nodes: usize,
71}
72
73impl<CacheAlgoDataT: CacheAlgoDataTrait> NodeRefMapDeltaMpts<CacheAlgoDataT> {
74    pub fn new() -> Self {
75        let mut node_ref_maps = Vec::with_capacity(MPT_ID_RANGE);
76        for _i in 0..MPT_ID_RANGE {
77            node_ref_maps.push(Default::default());
78        }
79
80        Self {
81            node_ref_maps,
82            nodes: 0,
83        }
84    }
85
86    /// Insert may crash due to memory allocation issue, although it won't
87    /// return error in current implementation.
88    pub fn insert(
89        &mut self, key: (DeltaMptId, DeltaMptDbKey), slot: ActualSlabIndex,
90    ) -> Result<()> {
91        if self.node_ref_maps[key.0 as usize]
92            .insert(
93                key.1,
94                CacheableNodeRefDeltaMpt {
95                    cached: TrieCacheSlotOrCacheAlgoData::TrieCacheSlot(slot),
96                },
97            )
98            .is_none()
99        {
100            self.nodes += 1;
101        };
102        Ok(())
103    }
104
105    /// The cache_info is only valid when the element still lives in cache.
106    /// Therefore we return the reference to the cache_info to represent the
107    /// lifetime requirement.
108    pub fn get_cache_info(
109        &self, key: (DeltaMptId, DeltaMptDbKey),
110    ) -> Option<&CacheableNodeRefDeltaMpt<CacheAlgoDataT>> {
111        self.node_ref_maps[key.0 as usize].get(&key.1)
112    }
113
114    pub fn set_cache_info(
115        &mut self, key: (DeltaMptId, DeltaMptDbKey),
116        cache_info: CacheableNodeRefDeltaMpt<CacheAlgoDataT>,
117    ) {
118        if self.node_ref_maps[key.0 as usize]
119            .insert(key.1, cache_info)
120            .is_none()
121        {
122            self.nodes += 1;
123        }
124    }
125
126    pub fn delete(
127        &mut self, key: (DeltaMptId, DeltaMptDbKey),
128    ) -> Option<CacheableNodeRefDeltaMpt<CacheAlgoDataT>> {
129        let maybe_old_value = self.node_ref_maps[key.0 as usize].remove(&key.1);
130        if maybe_old_value.is_some() {
131            self.nodes -= 1;
132        }
133        maybe_old_value
134    }
135
136    pub fn get_all_cache_infos_from_mpt(
137        &self, mpt_id: DeltaMptId,
138    ) -> Vec<(DeltaMptDbKey, CacheableNodeRefDeltaMpt<CacheAlgoDataT>)> {
139        self.node_ref_maps[mpt_id as usize]
140            .iter()
141            .map(|(k, v)| (k.clone(), v.clone()))
142            .collect()
143    }
144
145    pub fn log_usage(&self) {
146        debug!("node_ref_map.BTreeMap: #nodes: {}", self.nodes,);
147    }
148}
149
150pub const DEFAULT_NODE_MAP_SIZE: u32 = 200_000_000;
151
152use super::{
153    super::errors::*, cache::algorithm::CacheAlgoDataTrait,
154    node_memory_manager::ActualSlabIndex, row_number::RowNumberUnderlyingType,
155};
156use hashbrown::HashMap;
157use malloc_size_of_derive::MallocSizeOf as MallocSizeOfDerive;
cfx_storage/impls/delta_mpt/node_ref_map.rs

cfx_storage/impls/delta_mpt/
node_ref_map.rs
