tp_state_machine/changes_trie/
build_cache.rs

1// This file is part of Tetcore.
2
3// Copyright (C) 2019-2021 Parity Technologies (UK) Ltd.
4// SPDX-License-Identifier: Apache-2.0
5
6// Licensed under the Apache License, Version 2.0 (the "License");
7// you may not use this file except in compliance with the License.
8// You may obtain a copy of the License at
9//
10// 	http://www.apache.org/licenses/LICENSE-2.0
11//
12// Unless required by applicable law or agreed to in writing, software
13// distributed under the License is distributed on an "AS IS" BASIS,
14// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15// See the License for the specific language governing permissions and
16// limitations under the License.
17
18//! Changes tries build cache.
19
20use std::collections::{HashMap, HashSet};
21
22use crate::StorageKey;
23use tet_core::storage::PrefixedStorageKey;
24
25/// Changes trie build cache.
26///
27/// Helps to avoid read of changes tries from the database when digest trie
28/// is built. It holds changed keys for every block (indexed by changes trie
29/// root) that could be referenced by future digest items. For digest entries
30/// it also holds keys covered by this digest. Entries for top level digests
31/// are never created, because they'll never be used to build other digests.
32///
33/// Entries are pruned from the cache once digest block that is using this entry
34/// is inserted (because digest block will includes all keys from this entry).
35/// When there's a fork, entries are pruned when first changes trie is inserted.
36pub struct BuildCache<H, N> {
37	/// Map of block (implies changes trie) number => changes trie root.
38	roots_by_number: HashMap<N, H>,
39	/// Map of changes trie root => set of storage keys that are in this trie.
40	/// The `Option<Vec<u8>>` in inner `HashMap` stands for the child storage key.
41	/// If it is `None`, then the `HashSet` contains keys changed in top-level storage.
42	/// If it is `Some`, then the `HashSet` contains keys changed in child storage, identified by the key.
43	changed_keys: HashMap<H, HashMap<Option<PrefixedStorageKey>, HashSet<StorageKey>>>,
44}
45
46/// The action to perform when block-with-changes-trie is imported.
47#[derive(Debug, PartialEq)]
48pub enum CacheAction<H, N> {
49	/// Cache data that has been collected when CT has been built.
50	CacheBuildData(CachedBuildData<H, N>),
51	/// Clear cache from all existing entries.
52	Clear,
53}
54
55/// The data that has been cached during changes trie building.
56#[derive(Debug, PartialEq)]
57pub struct CachedBuildData<H, N> {
58	block: N,
59	trie_root: H,
60	digest_input_blocks: Vec<N>,
61	changed_keys: HashMap<Option<PrefixedStorageKey>, HashSet<StorageKey>>,
62}
63
64/// The action to perform when block-with-changes-trie is imported.
65#[derive(Debug, PartialEq)]
66pub(crate) enum IncompleteCacheAction<N> {
67	/// Cache data that has been collected when CT has been built.
68	CacheBuildData(IncompleteCachedBuildData<N>),
69	/// Clear cache from all existing entries.
70	Clear,
71}
72
73/// The data (without changes trie root) that has been cached during changes trie building.
74#[derive(Debug, PartialEq)]
75pub(crate) struct IncompleteCachedBuildData<N> {
76	digest_input_blocks: Vec<N>,
77	changed_keys: HashMap<Option<PrefixedStorageKey>, HashSet<StorageKey>>,
78}
79
80impl<H, N> BuildCache<H, N>
81	where
82		N: Eq + ::std::hash::Hash,
83		H: Eq + ::std::hash::Hash + Clone,
84{
85	/// Create new changes trie build cache.
86	pub fn new() -> Self {
87		BuildCache {
88			roots_by_number: HashMap::new(),
89			changed_keys: HashMap::new(),
90		}
91	}
92
93	/// Get cached changed keys for changes trie with given root.
94	pub fn get(&self, root: &H) -> Option<&HashMap<Option<PrefixedStorageKey>, HashSet<StorageKey>>> {
95		self.changed_keys.get(&root)
96	}
97
98	/// Execute given functor with cached entry for given block.
99	/// Returns true if the functor has been called and false otherwise.
100	pub fn with_changed_keys(
101		&self,
102		root: &H,
103		functor: &mut dyn FnMut(&HashMap<Option<PrefixedStorageKey>, HashSet<StorageKey>>),
104	) -> bool {
105		match self.changed_keys.get(&root) {
106			Some(changed_keys) => {
107				functor(changed_keys);
108				true
109			},
110			None => false,
111		}
112	}
113
114	/// Insert data into cache.
115	pub fn perform(&mut self, action: CacheAction<H, N>) {
116		match action {
117			CacheAction::CacheBuildData(data) => {
118				self.roots_by_number.insert(data.block, data.trie_root.clone());
119				self.changed_keys.insert(data.trie_root, data.changed_keys);
120
121				for digest_input_block in data.digest_input_blocks {
122					let digest_input_block_hash = self.roots_by_number.remove(&digest_input_block);
123					if let Some(digest_input_block_hash) = digest_input_block_hash {
124						self.changed_keys.remove(&digest_input_block_hash);
125					}
126				}
127			},
128			CacheAction::Clear => {
129				self.roots_by_number.clear();
130				self.changed_keys.clear();
131			},
132		}
133	}
134}
135
136impl<N> IncompleteCacheAction<N> {
137	/// Returns true if we need to collect changed keys for this action.
138	pub fn collects_changed_keys(&self) -> bool {
139		match *self {
140			IncompleteCacheAction::CacheBuildData(_) => true,
141			IncompleteCacheAction::Clear => false,
142		}
143	}
144
145	/// Complete cache action with computed changes trie root.
146	pub(crate) fn complete<H: Clone>(self, block: N, trie_root: &H) -> CacheAction<H, N> {
147		match self {
148			IncompleteCacheAction::CacheBuildData(build_data) =>
149				CacheAction::CacheBuildData(build_data.complete(block, trie_root.clone())),
150			IncompleteCacheAction::Clear => CacheAction::Clear,
151		}
152	}
153
154	/// Set numbers of blocks that are superseded by this new entry.
155	///
156	/// If/when this build data is committed to the cache, entries for these blocks
157	/// will be removed from the cache.
158	pub(crate) fn set_digest_input_blocks(self, digest_input_blocks: Vec<N>) -> Self {
159		match self {
160			IncompleteCacheAction::CacheBuildData(build_data) =>
161				IncompleteCacheAction::CacheBuildData(build_data.set_digest_input_blocks(digest_input_blocks)),
162			IncompleteCacheAction::Clear => IncompleteCacheAction::Clear,
163		}
164	}
165
166	/// Insert changed keys of given storage into cached data.
167	pub(crate) fn insert(
168		self,
169		storage_key: Option<PrefixedStorageKey>,
170		changed_keys: HashSet<StorageKey>,
171	) -> Self {
172		match self {
173			IncompleteCacheAction::CacheBuildData(build_data) =>
174				IncompleteCacheAction::CacheBuildData(build_data.insert(storage_key, changed_keys)),
175			IncompleteCacheAction::Clear => IncompleteCacheAction::Clear,
176		}
177	}
178}
179
180impl<N> IncompleteCachedBuildData<N> {
181	/// Create new cached data.
182	pub(crate) fn new() -> Self {
183		IncompleteCachedBuildData {
184			digest_input_blocks: Vec::new(),
185			changed_keys: HashMap::new(),
186		}
187	}
188
189	fn complete<H>(self, block: N, trie_root: H) -> CachedBuildData<H, N> {
190		CachedBuildData {
191			block,
192			trie_root,
193			digest_input_blocks: self.digest_input_blocks,
194			changed_keys: self.changed_keys,
195		}
196	}
197
198	fn set_digest_input_blocks(mut self, digest_input_blocks: Vec<N>) -> Self {
199		self.digest_input_blocks = digest_input_blocks;
200		self
201	}
202
203	fn insert(
204		mut self,
205		storage_key: Option<PrefixedStorageKey>,
206		changed_keys: HashSet<StorageKey>,
207	) -> Self {
208		self.changed_keys.insert(storage_key, changed_keys);
209		self
210	}
211}
212
213#[cfg(test)]
214mod tests {
215	use super::*;
216
217	#[test]
218	fn updated_keys_are_stored_when_non_top_level_digest_is_built() {
219		let mut data = IncompleteCachedBuildData::<u32>::new();
220		data = data.insert(None, vec![vec![1]].into_iter().collect());
221		assert_eq!(data.changed_keys.len(), 1);
222
223		let mut cache = BuildCache::new();
224		cache.perform(CacheAction::CacheBuildData(data.complete(1, 1)));
225		assert_eq!(cache.changed_keys.len(), 1);
226		assert_eq!(
227			cache.get(&1).unwrap().clone(),
228			vec![(None, vec![vec![1]].into_iter().collect())].into_iter().collect(),
229		);
230	}
231
232	#[test]
233	fn obsolete_entries_are_purged_when_new_ct_is_built() {
234		let mut cache = BuildCache::<u32, u32>::new();
235		cache.perform(CacheAction::CacheBuildData(IncompleteCachedBuildData::new()
236			.insert(None, vec![vec![1]].into_iter().collect())
237			.complete(1, 1)));
238		cache.perform(CacheAction::CacheBuildData(IncompleteCachedBuildData::new()
239			.insert(None, vec![vec![2]].into_iter().collect())
240			.complete(2, 2)));
241		cache.perform(CacheAction::CacheBuildData(IncompleteCachedBuildData::new()
242			.insert(None, vec![vec![3]].into_iter().collect())
243			.complete(3, 3)));
244
245		assert_eq!(cache.changed_keys.len(), 3);
246
247		cache.perform(CacheAction::CacheBuildData(IncompleteCachedBuildData::new()
248			.set_digest_input_blocks(vec![1, 2, 3])
249			.complete(4, 4)));
250
251		assert_eq!(cache.changed_keys.len(), 1);
252
253		cache.perform(CacheAction::CacheBuildData(IncompleteCachedBuildData::new()
254			.insert(None, vec![vec![8]].into_iter().collect())
255			.complete(8, 8)));
256		cache.perform(CacheAction::CacheBuildData(IncompleteCachedBuildData::new()
257			.insert(None, vec![vec![12]].into_iter().collect())
258			.complete(12, 12)));
259
260		assert_eq!(cache.changed_keys.len(), 3);
261
262		cache.perform(CacheAction::Clear);
263
264		assert_eq!(cache.changed_keys.len(), 0);
265	}
266}
tp_state_machine/changes_trie/build_cache.rs

tp_state_machine/changes_trie/
build_cache.rs
