gossip_kv/
lib.rs

Help
1pub mod membership;
2pub mod model;
3
4pub mod server;
5
6pub mod lattices;
7
8pub mod util;
9
10use std::collections::HashSet;
11use std::fmt::Display;
12use std::str::FromStr;
13
14use serde::{Deserialize, Serialize};
15
16use crate::KeyParseError::InvalidNamespace;
17use crate::model::{Clock, Namespaces};
18
19/// The namespace of the key of an entry in the key-value store.
20#[derive(Debug, Eq, PartialEq, Clone, Copy, Serialize, Deserialize, Hash)]
21pub enum Namespace {
22    /// User namespace is for use by the user of the key-value store.
23    User,
24
25    /// System namespace is reserved for use by the key-value store itself.
26    System,
27}
28
29/// Error that can occur when parsing a key from a string.
30#[derive(Debug, Eq, PartialEq, Clone, Copy)]
31pub enum KeyParseError {
32    /// The namespace in the key is invalid. Namespaces must be either `usr` or `sys`.
33    InvalidNamespace,
34
35    /// The key is in an invalid format. Keys must be of the form `/namespace/table/row`.
36    InvalidFormat,
37}
38
39impl Display for KeyParseError {
40    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
41        match self {
42            InvalidNamespace => write!(f, "Invalid namespace"),
43            KeyParseError::InvalidFormat => write!(f, "Invalid key format"),
44        }
45    }
46}
47
48impl FromStr for Namespace {
49    type Err = KeyParseError;
50    fn from_str(s: &str) -> Result<Self, Self::Err> {
51        match s {
52            "usr" => Ok(Namespace::User),
53            "sys" => Ok(Namespace::System),
54            _ => Err(InvalidNamespace),
55        }
56    }
57}
58
59/// The name of a table in the key-value store.
60pub type TableName = String;
61
62/// The key of a row in a table in the key-value store.
63pub type RowKey = String;
64
65/// A key of an entry in the key-value store.
66///
67/// Data in the key-value store is organized into namespaces, tables, and rows. Namespaces are
68/// either `usr` for user data or `sys` for system data. Namespaces contain tables, which contain
69/// rows. Each row has a row key and a row value.
70#[derive(Debug, Eq, PartialEq, Clone, Serialize, Deserialize, Hash)]
71pub struct Key {
72    /// The namespace of the key.
73    pub namespace: Namespace,
74    /// The name of the table in the key.
75    pub table: TableName,
76    /// The key of the row in the table.
77    pub row_key: RowKey,
78}
79
80impl FromStr for Key {
81    type Err = KeyParseError;
82    fn from_str(s: &str) -> Result<Self, Self::Err> {
83        let mut parts: Vec<String> = vec![];
84        let mut current_part = String::new();
85        let mut escaping = false;
86
87        for c in s.chars() {
88            match (escaping, c) {
89                (true, '\\') | (true, '/') => {
90                    current_part.push(c);
91                    escaping = false;
92                }
93                (true, _) => return Err(KeyParseError::InvalidFormat),
94                (false, '\\') => {
95                    escaping = true;
96                }
97                (false, '/') => {
98                    parts.push(current_part);
99                    current_part = String::new();
100                }
101                (false, _) => {
102                    current_part.push(c);
103                }
104            }
105        }
106
107        if escaping {
108            return Err(KeyParseError::InvalidFormat);
109        }
110
111        if !current_part.is_empty() {
112            parts.push(current_part);
113        }
114
115        if parts.len() != 4 {
116            return Err(KeyParseError::InvalidFormat);
117        }
118
119        if !parts[0].is_empty() {
120            return Err(KeyParseError::InvalidFormat);
121        }
122
123        if parts[2].is_empty() || parts[3].is_empty() {
124            return Err(KeyParseError::InvalidFormat);
125        }
126
127        let namespace = parts[1].parse()?;
128        Ok(Key {
129            namespace,
130            table: parts[2].to_string(),
131            row_key: parts[3].to_string(),
132        })
133    }
134}
135
136/// A request from a client to the key-value store.
137#[derive(Debug, Eq, PartialEq, Clone, Serialize, Deserialize)]
138pub enum ClientRequest {
139    /// A request to get the value of a key.
140    Get { key: Key },
141    /// A request to set the value of a key.
142    Set { key: Key, value: String },
143    /// A request to delete the value of a key.
144    Delete { key: Key },
145}
146
147#[derive(Debug, Eq, PartialEq, Clone, Serialize, Deserialize)]
148pub enum ClientResponse {
149    /// A response for a get request. The key is echoed back along with the value, if it exists.
150    /// Multiple values are returned if there were concurrent writes to the key.
151    Get { key: Key, value: HashSet<String> },
152    /// A response for a set request. The success field is true if the set was successful.
153    Set { success: bool },
154    /// A response for a delete request. The success field is true if delete was successful.
155    Delete { success: bool },
156}
157
158#[derive(Debug, Eq, PartialEq, Clone, Serialize, Deserialize)]
159pub enum GossipMessage {
160    /// An "infecting message" to share updates with a peer.
161    Gossip {
162        message_id: String,
163        member_id: String,
164        writes: Namespaces<Clock>,
165    },
166    /// An acknowledgement message sent by a peer in response to a Gossip message, to indicate
167    /// that it hasn't seen some of the writes in the Gossip message before.
168    Ack {
169        message_id: String,
170        member_id: String,
171    },
172    /// A negative acknowledgement sent by a peer in response to a Gossip message, to indicate
173    /// that it has seen all of the writes in the Gossip message before.
174    Nack {
175        message_id: String,
176        member_id: String,
177    },
178}
179
180#[cfg(test)]
181mod tests {
182    use super::{Key, Namespace};
183
184    #[test]
185    fn test_key_parsing_sys_namespace() {
186        // Sys namespace
187        let first = "/sys/sys_table/sys_row".parse::<Key>().unwrap();
188        assert_eq!(first.namespace, Namespace::System);
189        assert_eq!(first.table, "sys_table");
190        assert_eq!(first.row_key, "sys_row");
191    }
192    #[test]
193    fn test_key_parsing_user_namespace() {
194        // User namespace
195        let second = "/usr/usr_table/usr_row".parse::<Key>().unwrap();
196        assert_eq!(second.namespace, Namespace::User);
197        assert_eq!(second.table, "usr_table");
198        assert_eq!(second.row_key, "usr_row");
199    }
200
201    #[test]
202    fn test_key_empty_table() {
203        // Empty table
204        let empty_table = "/usr//usr_row".parse::<Key>();
205        assert!(empty_table.is_err());
206        assert_eq!(
207            empty_table.unwrap_err(),
208            super::KeyParseError::InvalidFormat
209        );
210    }
211
212    #[test]
213    fn test_key_empty_row() {
214        // Empty row
215        let empty_row = "/usr/usr_table/".parse::<Key>();
216        assert!(empty_row.is_err());
217        assert_eq!(empty_row.unwrap_err(), super::KeyParseError::InvalidFormat);
218    }
219
220    #[test]
221    fn test_key_parsing_invalid_namespace() {
222        // Invalid namespace
223        let non_existent_namespace = "/ne_namespace/ne_table/ne_row".parse::<Key>();
224        assert!(non_existent_namespace.is_err());
225        assert_eq!(
226            non_existent_namespace.unwrap_err(),
227            super::KeyParseError::InvalidNamespace
228        );
229    }
230
231    #[test]
232    fn test_key_parsing_invalid_format() {
233        // Invalid format
234        let invalid_format = "/not_even_a_key".parse::<Key>();
235        assert!(invalid_format.is_err());
236        assert_eq!(
237            invalid_format.unwrap_err(),
238            super::KeyParseError::InvalidFormat
239        );
240
241        let invalid_format = "abcd/sys/sys_table/sys_row".parse::<Key>();
242        assert!(invalid_format.is_err());
243        assert_eq!(
244            invalid_format.unwrap_err(),
245            super::KeyParseError::InvalidFormat
246        );
247    }
248
249    #[test]
250    fn test_key_parsing_escaping() {
251        // Escape \
252        let key = r"/usr/usr\/table/usr\/row".parse::<Key>().unwrap();
253        assert_eq!(key.namespace, Namespace::User);
254        assert_eq!(key.table, r"usr/table");
255        assert_eq!(key.row_key, r"usr/row");
256
257        // Escaping /
258        let key = r"/usr/usr\\table/usr\\row".parse::<Key>().unwrap();
259        assert_eq!(key.namespace, Namespace::User);
260        assert_eq!(key.table, r"usr\table");
261        assert_eq!(key.row_key, r"usr\row");
262
263        // Escaping any character
264        let key = r"/usr/usr\table/usr\row".parse::<Key>();
265        assert!(key.is_err());
266        assert_eq!(key.unwrap_err(), super::KeyParseError::InvalidFormat);
267
268        // Dangling escape
269        let key = r"/usr/usr_table/usr_row\".parse::<Key>();
270        assert!(key.is_err());
271        assert_eq!(key.unwrap_err(), super::KeyParseError::InvalidFormat);
272    }
273}
gossip_kv/lib.rs

gossip_kv/
lib.rs
