oasis_core_runtime/storage/mkvs/
mod.rs

1//! Merklized key-value store.
2use std::{
3    iter,
4    ops::{Deref, DerefMut},
5};
6
7use anyhow::{Error, Result};
8
9use crate::common::{crypto::hash::Hash, namespace::Namespace};
10
11use self::sync::Proof;
12
13#[macro_use]
14mod tree;
15mod cache;
16#[cfg(test)]
17pub mod interop;
18pub mod marshal;
19pub mod sync;
20#[cfg(test)]
21mod tests;
22
23pub use tree::{Depth, Key, NodeBox, NodePointer, NodePtrRef, OverlayTree, Root, RootType, Tree};
24
25/// The type of entry in the log.
26#[derive(Copy, Clone, Debug, Eq, PartialEq)]
27pub enum LogEntryKind {
28    Insert,
29    Delete,
30}
31
32/// An entry in the write log, describing a single update.
33#[derive(Clone, Debug, Default, Eq, PartialEq, Hash, cbor::Encode, cbor::Decode)]
34#[cbor(as_array)]
35pub struct LogEntry {
36    /// The key that was inserted or deleted.
37    pub key: Vec<u8>,
38    /// The inserted value (empty if the key was deleted).
39    pub value: Option<Vec<u8>>,
40}
41
42impl LogEntry {
43    pub fn new(key: &[u8], value: &[u8]) -> Self {
44        Self {
45            key: key.to_owned(),
46            value: Some(value.to_owned()),
47        }
48    }
49
50    pub fn kind(&self) -> LogEntryKind {
51        match self.value {
52            Some(_) => LogEntryKind::Insert,
53            None => LogEntryKind::Delete,
54        }
55    }
56}
57
58/// The write log.
59///
60/// The keys in the write log must be unique.
61pub type WriteLog = Vec<LogEntry>;
62
63/// A key prefix.
64#[derive(Clone, Debug, Default, Eq, PartialEq, PartialOrd, Ord, cbor::Encode, cbor::Decode)]
65#[cbor(transparent)]
66pub struct Prefix(Vec<u8>);
67
68impl AsRef<[u8]> for Prefix {
69    fn as_ref(&self) -> &[u8] {
70        &self.0
71    }
72}
73
74impl Deref for Prefix {
75    type Target = Vec<u8>;
76
77    fn deref(&self) -> &Self::Target {
78        &self.0
79    }
80}
81
82impl DerefMut for Prefix {
83    fn deref_mut(&mut self) -> &mut Self::Target {
84        &mut self.0
85    }
86}
87
88impl From<Prefix> for Vec<u8> {
89    fn from(val: Prefix) -> Self {
90        val.0
91    }
92}
93
94impl From<Vec<u8>> for Prefix {
95    fn from(v: Vec<u8>) -> Prefix {
96        Prefix(v)
97    }
98}
99
100/// Merklized key-value store.
101pub trait MKVS {
102    /// Fetch entry with given key.
103    fn get(&self, key: &[u8]) -> Option<Vec<u8>>;
104
105    /// Fetch proof for entry with given key.
106    fn get_proof(&self, key: &[u8]) -> Option<Proof>;
107
108    /// Check if the local MKVS cache contains the given key.
109    ///
110    /// While get can be used to check if the MKVS as a whole contains
111    /// a given key, this function specifically guarantees that no remote
112    /// syncing will be invoked, only checking the local cache.
113    fn cache_contains_key(&self, key: &[u8]) -> bool;
114
115    /// Update entry with given key.
116    ///
117    /// If the database did not have this key present, [`None`] is returned.
118    ///
119    /// If the database did have this key present, the value is updated, and the old value is
120    /// returned.
121    ///
122    /// [`None`]: std::option::Option
123    fn insert(&mut self, key: &[u8], value: &[u8]) -> Option<Vec<u8>>;
124
125    /// Remove entry with given key, returning the value at the key if the key was previously
126    /// in the database.
127    fn remove(&mut self, key: &[u8]) -> Option<Vec<u8>>;
128
129    /// Populate the in-memory tree with nodes for keys starting with given prefixes.
130    fn prefetch_prefixes(&self, prefixes: &[Prefix], limit: u16);
131
132    /// Returns an iterator over the tree.
133    fn iter(&self) -> Box<dyn Iterator + '_>;
134
135    /// Commit all database changes to the underlying store.
136    fn commit(&mut self, namespace: Namespace, version: u64) -> Result<(WriteLog, Hash)>;
137}
138
139/// Merklized key-value store where methods return errors instead of panicking.
140pub trait FallibleMKVS {
141    /// Fetch entry with given key.
142    fn get(&self, key: &[u8]) -> Result<Option<Vec<u8>>>;
143
144    /// Fetch proof for entry with given key.
145    fn get_proof(&self, key: &[u8]) -> Result<Option<Proof>>;
146
147    /// Check if the local MKVS cache contains the given key.
148    ///
149    /// While get can be used to check if the MKVS as a whole contains
150    /// a given key, this function specifically guarantees that no remote
151    /// syncing will be invoked, only checking the local cache.
152    fn cache_contains_key(&self, key: &[u8]) -> bool;
153
154    /// Update entry with given key.
155    ///
156    /// If the database did not have this key present, [`None`] is returned.
157    ///
158    /// If the database did have this key present, the value is updated, and the old value is
159    /// returned.
160    ///
161    /// [`None`]: std::option::Option
162    fn insert(&mut self, key: &[u8], value: &[u8]) -> Result<Option<Vec<u8>>>;
163
164    /// Remove entry with given key, returning the value at the key if the key was previously
165    /// in the database.
166    fn remove(&mut self, key: &[u8]) -> Result<Option<Vec<u8>>>;
167
168    /// Populate the in-memory tree with nodes for keys starting with given prefixes.
169    fn prefetch_prefixes(&self, prefixes: &[Prefix], limit: u16) -> Result<()>;
170
171    /// Returns an iterator over the tree.
172    fn iter(&self) -> Box<dyn Iterator + '_>;
173
174    /// Commit all database changes to the underlying store.
175    fn commit(&mut self, namespace: Namespace, version: u64) -> Result<Hash>;
176}
177
178/// Immutable merkalized key value store.
179pub trait ImmutableMKVS {
180    /// Fetch entry with given key.
181    fn get(&self, key: &[u8]) -> Result<Option<Vec<u8>>>;
182
183    /// Fetch proof for entry with given key.
184    fn get_proof(&self, key: &[u8]) -> Result<Option<Proof>>;
185
186    /// Populate the in-memory tree with nodes for keys starting with given prefixes.
187    fn prefetch_prefixes(&self, prefixes: &[Prefix], limit: u16) -> Result<()>;
188
189    /// Returns an iterator over the tree.
190    fn iter(&self) -> Box<dyn Iterator + '_>;
191}
192
193impl<T> ImmutableMKVS for T
194where
195    T: FallibleMKVS,
196{
197    fn get(&self, key: &[u8]) -> Result<Option<Vec<u8>>> {
198        T::get(self, key)
199    }
200
201    fn get_proof(&self, key: &[u8]) -> Result<Option<Proof>> {
202        T::get_proof(self, key)
203    }
204
205    fn prefetch_prefixes(&self, prefixes: &[Prefix], limit: u16) -> Result<()> {
206        T::prefetch_prefixes(self, prefixes, limit)
207    }
208
209    fn iter(&self) -> Box<dyn Iterator + '_> {
210        T::iter(self)
211    }
212}
213
214/// An MKVS iterator.
215pub trait Iterator: iter::Iterator<Item = (Vec<u8>, Vec<u8>)> {
216    /// Sets the number of next elements to prefetch.
217    fn set_prefetch(&mut self, prefetch: usize);
218
219    /// Return whether the iterator is valid.
220    fn is_valid(&self) -> bool;
221
222    /// Return the error that occurred during iteration if any.
223    fn error(&self) -> &Option<Error>;
224
225    /// Moves the iterator to the first key in the tree.
226    fn rewind(&mut self);
227
228    /// Moves the iterator either at the given key or at the next larger key.
229    fn seek(&mut self, key: &[u8]);
230
231    /// The key under the iterator.
232    fn get_key(&self) -> &Option<Key>;
233
234    /// The value under the iterator.
235    fn get_value(&self) -> &Option<Vec<u8>>;
236
237    /// Advance the iterator to the next key.
238    fn next(&mut self);
239}
240
241impl<T: MKVS + ?Sized> MKVS for &mut T {
242    fn get(&self, key: &[u8]) -> Option<Vec<u8>> {
243        T::get(self, key)
244    }
245
246    fn get_proof(&self, key: &[u8]) -> Option<Proof> {
247        T::get_proof(self, key)
248    }
249
250    fn cache_contains_key(&self, key: &[u8]) -> bool {
251        T::cache_contains_key(self, key)
252    }
253
254    fn insert(&mut self, key: &[u8], value: &[u8]) -> Option<Vec<u8>> {
255        T::insert(self, key, value)
256    }
257
258    fn remove(&mut self, key: &[u8]) -> Option<Vec<u8>> {
259        T::remove(self, key)
260    }
261
262    fn prefetch_prefixes(&self, prefixes: &[Prefix], limit: u16) {
263        T::prefetch_prefixes(self, prefixes, limit)
264    }
265
266    fn iter(&self) -> Box<dyn Iterator + '_> {
267        T::iter(self)
268    }
269
270    fn commit(&mut self, namespace: Namespace, version: u64) -> Result<(WriteLog, Hash)> {
271        T::commit(self, namespace, version)
272    }
273}
274
275impl<T: FallibleMKVS + ?Sized> FallibleMKVS for &mut T {
276    fn get(&self, key: &[u8]) -> Result<Option<Vec<u8>>> {
277        T::get(self, key)
278    }
279
280    fn get_proof(&self, key: &[u8]) -> Result<Option<Proof>> {
281        T::get_proof(self, key)
282    }
283
284    fn cache_contains_key(&self, key: &[u8]) -> bool {
285        T::cache_contains_key(self, key)
286    }
287
288    fn insert(&mut self, key: &[u8], value: &[u8]) -> Result<Option<Vec<u8>>> {
289        T::insert(self, key, value)
290    }
291
292    fn remove(&mut self, key: &[u8]) -> Result<Option<Vec<u8>>> {
293        T::remove(self, key)
294    }
295
296    fn prefetch_prefixes(&self, prefixes: &[Prefix], limit: u16) -> Result<()> {
297        T::prefetch_prefixes(self, prefixes, limit)
298    }
299
300    fn iter(&self) -> Box<dyn Iterator + '_> {
301        T::iter(self)
302    }
303
304    fn commit(&mut self, namespace: Namespace, version: u64) -> Result<Hash> {
305        T::commit(self, namespace, version)
306    }
307}
308
309#[cfg(test)]
310mod _tests {
311    use super::*;
312
313    #[test]
314    fn test_write_log_serialization() {
315        let write_log = vec![LogEntry {
316            key: b"foo".to_vec(),
317            value: Some(b"bar".to_vec()),
318        }];
319
320        let raw = cbor::to_vec(write_log.clone());
321        let deserialized: WriteLog = cbor::from_slice(&raw).unwrap();
322
323        assert_eq!(write_log, deserialized);
324    }
325}
oasis_core_runtime/storage/mkvs/mod.rs

oasis_core_runtime/storage/mkvs/
mod.rs
