cfx_storage/impls/delta_mpt/
cache_manager_delta_mpts.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// TODO: On performance, each access may requires a lock because of calling
6// TODO: cache algorithm & cache eviction & TrieNode slab alloc/delete
7// TODO: & noderefmap update. The read & write can not be easily broken
8// TODO: down because of dependency. Calling cache algorithm always
9// TODO: requires write lock to algorithm. cache hit updates can be
10// TODO: batched locally. The caller knows whether a node is hit. But the
11// TODO: element for batched hit update could be evicted by other threads. cache
12// TODO: miss locks mutably for slab alloc/delete, noderefmap update.
13// TODO: can also be batched however the lifetime of TrieNode should be managed.
14#[derive(MallocSizeOfDerive)]
15pub struct CacheManagerDeltaMpts<
16    CacheAlgoDataT: CacheAlgoDataTrait,
17    CacheAlgorithmT: CacheAlgorithm<CacheAlgoData = CacheAlgoDataT>,
18> {
19    /// One of the key problem in implementing a cache for tree node is that,
20    /// when a node is swapped-out from cache into disk, the eviction of
21    /// children should be independent, not only because of cache hit
22    /// property, but also because that a node can have multiple parents. When
23    /// a node is loaded into cache again, it should automatically connects
24    /// to its children in cache, even if the children is shared with some
25    /// other node unknown.
26    ///
27    /// Another problem is that, when a node is swapped-out, the parent's
28    /// children reference must be updated unless the children reference is
29    /// the db key, or something stable. The db key in Conflux is the
30    /// Merkle Hash, which is too large for a Trie node: 16*64B are
31    /// required to store only ChildrenTable.
32    ///
33    /// To solve these problems, we introduce CacheableNodeRef, which should
34    /// remain stable for the lifetime of the TrieNode of the
35    /// ChildrenTable. The key of NodeRefMap shall be db key, and the value
36    /// of NodeRefMap shall point to where the node is cached.
37    ///
38    /// The db key could be made smaller for Delta MPT (4B)
39    /// and maybe for Persistent MPT (8B) by simply using the row number.
40    ///
41    /// If we have to use Merkle Hash (64B) as db key for Persistent MPT,
42    /// storing the key for non-cached node is costly. There are two options,
43    /// a) store key only for cached nodes, there is little addition cost (8B),
44    /// however to load an un-cached child node from disk, caller should first
45    /// read the child's access key by loading the current node, then check
46    /// NodeRefMap, if actual missing load it from disk for the second
47    /// time.
48    /// b) create NodeRef for some children of cached node, store the 64B key
49    /// for disk access, and keep the reference count so that we don't store
50    /// NodeRef for nodes which later becomes irrelevant indefinitely.
51    ///
52    /// Note that there are also dirty nodes, which always live in memory.
53    /// The NodeRef / MaybeNodeRef also covers dirty nodes, but NodeRefMap
54    /// covers only committed nodes.
55    pub(super) node_ref_map: NodeRefMapDeltaMpts<CacheAlgoDataT>,
56    pub(super) cache_algorithm: CacheAlgorithmT,
57}
58
59impl CacheIndexTrait for (DeltaMptId, DeltaMptDbKey) {}
60
61impl<
62        CacheAlgoDataT: CacheAlgoDataTrait,
63        CacheAlgorithmT: CacheAlgorithm<
64            CacheAlgoData = CacheAlgoDataT,
65            CacheIndex = (DeltaMptId, DeltaMptDbKey),
66        >,
67    > CacheManagerDeltaMpts<CacheAlgoDataT, CacheAlgorithmT>
68{
69    pub fn insert_to_node_ref_map_and_call_cache_access(
70        &mut self, cache_index: (DeltaMptId, DeltaMptDbKey),
71        slot: ActualSlabIndex,
72        node_memory_manager: &NodeMemoryManager<
73            CacheAlgoDataT,
74            CacheAlgorithmT,
75        >,
76    ) -> Result<()> {
77        self.node_ref_map.insert(cache_index, slot)?;
78        node_memory_manager.call_cache_algorithm_access(self, cache_index);
79        Ok(())
80    }
81
82    pub fn is_cached(&self, cache_index: (DeltaMptId, DeltaMptDbKey)) -> bool {
83        if let Some(cache_info) = self.node_ref_map.get_cache_info(cache_index)
84        {
85            cache_info.get_slot().is_some()
86        } else {
87            false
88        }
89    }
90
91    pub fn log_usage(&self) {
92        self.node_ref_map.log_usage();
93        self.cache_algorithm.log_usage("trie node cache ");
94    }
95}
96
97use super::{
98    super::errors::*,
99    cache::algorithm::{CacheAlgoDataTrait, CacheAlgorithm, CacheIndexTrait},
100    node_memory_manager::{ActualSlabIndex, NodeMemoryManager},
101    node_ref_map::{DeltaMptDbKey, DeltaMptId, NodeRefMapDeltaMpts},
102};
103use malloc_size_of_derive::MallocSizeOf as MallocSizeOfDerive;
cfx_storage/impls/delta_mpt/cache_manager_delta_mpts.rs

cfx_storage/impls/delta_mpt/
cache_manager_delta_mpts.rs
