kvdb/
lib.rs

1// Copyright 2020 Parity Technologies
2//
3// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
4// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
5// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
6// option. This file may not be copied, modified, or distributed
7// except according to those terms.
8
9//! Key-Value store abstraction.
10
11use smallvec::SmallVec;
12use std::io;
13
14mod io_stats;
15
16/// Required length of prefixes.
17pub const PREFIX_LEN: usize = 12;
18
19/// Database value.
20pub type DBValue = Vec<u8>;
21/// Database keys.
22pub type DBKey = SmallVec<[u8; 32]>;
23/// A tuple holding key and value data, used in the iterator item type.
24pub type DBKeyValue = (DBKey, DBValue);
25
26pub use io_stats::{IoStats, Kind as IoStatsKind};
27
28/// Write transaction. Batches a sequence of put/delete operations for efficiency.
29#[derive(Default, Clone, PartialEq)]
30pub struct DBTransaction {
31	/// Database operations.
32	pub ops: Vec<DBOp>,
33}
34
35/// Database operation.
36#[derive(Clone, PartialEq)]
37pub enum DBOp {
38	Insert { col: u32, key: DBKey, value: DBValue },
39	Delete { col: u32, key: DBKey },
40	DeletePrefix { col: u32, prefix: DBKey },
41}
42
43impl DBOp {
44	/// Returns the key associated with this operation.
45	pub fn key(&self) -> &[u8] {
46		match *self {
47			DBOp::Insert { ref key, .. } => key,
48			DBOp::Delete { ref key, .. } => key,
49			DBOp::DeletePrefix { ref prefix, .. } => prefix,
50		}
51	}
52
53	/// Returns the column associated with this operation.
54	pub fn col(&self) -> u32 {
55		match *self {
56			DBOp::Insert { col, .. } => col,
57			DBOp::Delete { col, .. } => col,
58			DBOp::DeletePrefix { col, .. } => col,
59		}
60	}
61}
62
63impl DBTransaction {
64	/// Create new transaction.
65	pub fn new() -> DBTransaction {
66		DBTransaction::with_capacity(256)
67	}
68
69	/// Create new transaction with capacity.
70	pub fn with_capacity(cap: usize) -> DBTransaction {
71		DBTransaction { ops: Vec::with_capacity(cap) }
72	}
73
74	/// Insert a key-value pair in the transaction. Any existing value will be overwritten upon write.
75	pub fn put(&mut self, col: u32, key: &[u8], value: &[u8]) {
76		self.ops
77			.push(DBOp::Insert { col, key: DBKey::from_slice(key), value: value.to_vec() })
78	}
79
80	/// Insert a key-value pair in the transaction. Any existing value will be overwritten upon write.
81	pub fn put_vec(&mut self, col: u32, key: &[u8], value: Vec<u8>) {
82		self.ops.push(DBOp::Insert { col, key: DBKey::from_slice(key), value });
83	}
84
85	/// Delete value by key.
86	pub fn delete(&mut self, col: u32, key: &[u8]) {
87		self.ops.push(DBOp::Delete { col, key: DBKey::from_slice(key) });
88	}
89
90	/// Delete all values with the given key prefix.
91	/// Using an empty prefix here will remove all keys
92	/// (all keys start with the empty prefix).
93	pub fn delete_prefix(&mut self, col: u32, prefix: &[u8]) {
94		self.ops.push(DBOp::DeletePrefix { col, prefix: DBKey::from_slice(prefix) });
95	}
96}
97
98/// Generic key-value database.
99///
100/// The `KeyValueDB` deals with "column families", which can be thought of as distinct
101/// stores within a database. Keys written in one column family will not be accessible from
102/// any other. The number of column families must be specified at initialization, with a
103/// differing interface for each database.
104///
105/// The API laid out here, along with the `Sync` bound implies interior synchronization for
106/// implementation.
107pub trait KeyValueDB: Sync + Send {
108	/// Helper to create a new transaction.
109	fn transaction(&self) -> DBTransaction {
110		DBTransaction::new()
111	}
112
113	/// Get a value by key.
114	fn get(&self, col: u32, key: &[u8]) -> io::Result<Option<DBValue>>;
115
116	/// Get the first value matching the given prefix.
117	fn get_by_prefix(&self, col: u32, prefix: &[u8]) -> io::Result<Option<DBValue>>;
118
119	/// Write a transaction of changes to the backing store.
120	fn write(&self, transaction: DBTransaction) -> io::Result<()>;
121
122	/// Iterate over the data for a given column.
123	fn iter<'a>(&'a self, col: u32) -> Box<dyn Iterator<Item = io::Result<DBKeyValue>> + 'a>;
124
125	/// Iterate over the data for a given column, returning all key/value pairs
126	/// where the key starts with the given prefix.
127	fn iter_with_prefix<'a>(
128		&'a self,
129		col: u32,
130		prefix: &'a [u8],
131	) -> Box<dyn Iterator<Item = io::Result<DBKeyValue>> + 'a>;
132
133	/// Query statistics.
134	///
135	/// Not all kvdb implementations are able or expected to implement this, so by
136	/// default, empty statistics is returned. Also, not all kvdb implementations
137	/// can return every statistic or configured to do so (some statistics gathering
138	/// may impede the performance and might be off by default).
139	fn io_stats(&self, _kind: IoStatsKind) -> IoStats {
140		IoStats::empty()
141	}
142
143	/// Check for the existence of a value by key.
144	fn has_key(&self, col: u32, key: &[u8]) -> io::Result<bool> {
145		self.get(col, key).map(|opt| opt.is_some())
146	}
147
148	/// Check for the existence of a value by prefix.
149	fn has_prefix(&self, col: u32, prefix: &[u8]) -> io::Result<bool> {
150		self.get_by_prefix(col, prefix).map(|opt| opt.is_some())
151	}
152}
153
154/// For a given start prefix (inclusive), returns the correct end prefix (non-inclusive).
155/// This assumes the key bytes are ordered in lexicographical order.
156/// Since key length is not limited, for some case we return `None` because there is
157/// no bounded limit (every keys in the serie `[]`, `[255]`, `[255, 255]` ...).
158pub fn end_prefix(prefix: &[u8]) -> Option<Vec<u8>> {
159	let mut end_range = prefix.to_vec();
160	while let Some(0xff) = end_range.last() {
161		end_range.pop();
162	}
163	if let Some(byte) = end_range.last_mut() {
164		*byte += 1;
165		Some(end_range)
166	} else {
167		None
168	}
169}
170
171#[cfg(test)]
172mod test {
173	use super::end_prefix;
174
175	#[test]
176	fn end_prefix_test() {
177		assert_eq!(end_prefix(&[5, 6, 7]), Some(vec![5, 6, 8]));
178		assert_eq!(end_prefix(&[5, 6, 255]), Some(vec![5, 7]));
179		// This is not equal as the result is before start.
180		assert_ne!(end_prefix(&[5, 255, 255]), Some(vec![5, 255]));
181		// This is equal ([5, 255] will not be deleted because
182		// it is before start).
183		assert_eq!(end_prefix(&[5, 255, 255]), Some(vec![6]));
184		assert_eq!(end_prefix(&[255, 255, 255]), None);
185
186		assert_eq!(end_prefix(&[0x00, 0xff]), Some(vec![0x01]));
187		assert_eq!(end_prefix(&[0xff]), None);
188		assert_eq!(end_prefix(&[]), None);
189		assert_eq!(end_prefix(b"0"), Some(b"1".to_vec()));
190	}
191}
kvdb/lib.rs

kvdb/
lib.rs
