1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293
// This file is part of lfchring-rs. // // Copyright 2021 Christos Katsakioris // // Licensed under the Apache License, Version 2.0 (the "License"); // you may not use this file except in compliance with the License. // You may obtain a copy of the License at // // http://www.apache.org/licenses/LICENSE-2.0 // // Unless required by applicable law or agreed to in writing, software // distributed under the License is distributed on an "AS IS" BASIS, // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. // See the License for the specific language governing permissions and // limitations under the License. //! This crate implements a concurrent, lock-free [consistent hashing ring] data structure. //! //! # Features //! //! This section documents the features of the data structure implementation. //! //! Information about the supported crate `features` can be found throughout this documentation //! page. //! //! ## Virtual Nodes //! //! The crate includes support for a configurable number of *virtual nodes* per ring node (i.e., //! each node can be mapped and placed multiple times on the ring, and the number of these times is //! configurable) to allow for improved efficiency in load balancing scenarios. //! //! The number of virtual nodes per ring node is configurable only at the time of the creation of //! the data structure. //! //! ## Replication //! //! Moreover, the crate includes support for keeping track of key replication. //! This means that, provided with a replication factor of the caller's choice, looking up keys in //! the consistent hashing ring data structure reports all the distinct ring nodes on which //! replicas of the key at hand are assigned. //! Note that consecutive virtual nodes on a consistent hashing may belong to the same distinct //! ring node; this crate makes sure that keys are assigned to a number of *distinct* ring nodes //! equal to the (configurable) replication factor (as long as they are available), by skipping //! some virtual nodes if required. //! //! The replication factor is configurable only at the time of the creation of the data structure. //! //! ## Original Purpose //! //! The primary purpose of this crate has been to be work correctly in multi-threaded contexts, //! i.e., in cases where multiple threads have access to the consistent hashing ring data //! structure and operate on it at the same time. //! More specifically, it has been designed and implemented mainly for use cases where a large //! number of reader threads may need to access it, whereas write operations are sparse //! (if you are unsure whether you know what *read* and *write* operations may refer to, do not //! worry, please read on). //! Nevertheless, the data structure can be used in single-threaded environments equally well. //! //! --- //! //! The ring data structure is represented by the exported [`HashRing<N, H>`] type, which is //! generic over the [`Node`] and the [`Hasher`]. //! Virtual nodes are represented by the exported [`VirtualNode<N>`] type. //! //! ## Node //! //! Any type can be used as a node of the consistent hashing ring, as long as it implements the //! [`Node`] trait. //! The implementation of this trait requires a method ([`Node::hashring_node_id`]) which allows to //! uniquely represent the type as a byte slice. //! Implementing the [`Node`] trait can be as trivial as: //! //! ```rust //! # use std::borrow::Cow; //! # use lfchring::Node; //! struct ExampleNode { //! various: u64, //! fields: Vec<i32>, //! // . . . //! unique_name: String, //! } //! //! impl Node for ExampleNode { //! fn hashring_node_id(&self) -> Cow<'_, [u8]> { //! Cow::Borrowed(&self.unique_name.as_bytes()) //! } //! } //! ``` //! //! or: //! //! ```rust //! # use std::borrow::Cow; //! # use lfchring::Node; //! struct StrNode(str); //! //! impl Node for StrNode { //! fn hashring_node_id(&self) -> Cow<'_, [u8]> { //! Cow::Borrowed(self.0.as_bytes()) //! } //! } //! ``` //! //! Note that [`Node`] can be unsized and that the crate already provides implementations for the //! following types: //! - `String` //! - `str` //! - `Vec<u8>` //! - `&[u8]` //! - `[u8]` //! //! ## Hasher //! //! For a `Node` to be inserted in (or removed from) the consistent hashing ring, it needs to be //! hashed one or more times (depending on the configured number of virtual nodes per `Node`). //! The produced virtual nodes are then appropriately "placed" on the ring based on their hash //! digests. //! //! Multiple hash algorithms can be used. //! The crate includes an implementation of [`HashRing<N, H>`] that employs standard library's //! [`DefaultHasher`][DefaultHasher] (constructed via [`HashRing::new`] or //! [`HashRing::with_nodes`]). //! However, you may also bring your own hash algorithm implementation by implementing the //! [`Hasher`] trait. //! This trait defines the [`Hasher::digest`] method which, provided an input byte slice, produces //! a hash digest as an owned `Vec<u8>`, to be used for placing the `Node`s on the consistent //! hashing ring in the correct order. //! //! Not relying on standard library's machinery for hashing is a design choice that allows using //! [`HashRing<N, H>`] with hash functions that produce digests longer than `u64`. //! //! ### Feature `blake3-hash` //! //! By enabling the `blake3-hash` crate feature, a [`Hasher`] that employs the [BLAKE3][BLAKE3.io] //! cryptographic hash function as implemented in the [blake3 crate][blake3] is made available. //! //! For more information, refer to the documentation of the [`Blake3Hasher`] type. //! //! ### Feature `blake2b-hash` //! //! A [`Hasher`] implementation based on the [BLAKE2b][BLAKE2b] cryptographic hash function and the //! [blake2b_simd crate][blake2b_simd] is available by enabling the `blake2b-hash` crate feature. //! //! For more information, refer to the documentation of the [`Blake2bHasher`] type. //! //! ## The Two Main Kinds of Operations //! //! All supported operations on the ring fall into two main categories: "read-like" and //! "write-like". //! - *Read operations* require access to the information stored in the ring, but they do *not* //! mutate the ring itself. //! The most common example of such an operation is looking up where a key should be assigned to //! according to the consistent hashing algorithm (e.g., see [`HashRing::nodes_for_key`]). //! Another example is to loop through all the virtual nodes that are contained in the consistent //! hashing ring via an iterator (e.g., see [`HashRing::iter`] and [`Iter`]). //! - *Write operations* are considered those that effectively **mutate** the ring itself. //! Common examples are the [`HashRing::insert`] and [`HashRing::remove`] methods, which insert //! new nodes to the consistent hashing ring, or remove existing ones, respectively. //! //! ## Example //! //! What follows is a basic, single-threaded example to showcase its use: //! //! ```rust //! use std::sync::Arc; //! use hex_literal::hex; //! use lfchring::{HashRing, Node, VirtualNode, Vnid}; //! //! const VIRTUAL_NODES_PER_NODE: Vnid = 2; //! const REPLICATION_FACTOR: u8 = 3; //! //! // Create an empty ring (see the docs for further options on constructing a ring). //! let ring = HashRing::new(VIRTUAL_NODES_PER_NODE, REPLICATION_FACTOR).unwrap(); //! //! // Insert three new Nodes. //! let nodes: Vec<Arc<str>> = vec![Arc::from("Node1"), Arc::from("Node2"), Arc::from("Node3")]; //! ring.insert(&nodes).expect("hash collision when inserting 3 new Nodes"); //! //! assert_eq!(ring.len_nodes(), 3); //! assert_eq!(ring.len_virtual_nodes(), 3 * VIRTUAL_NODES_PER_NODE as usize); //! //! // Look up a key in the ring. //! let key = hex!("232a8a941ee901c1"); //! let virtual_node_clone = ring.virtual_node_for_key(&key).unwrap(); //! //! // The Nodes that should own a replica for the particular key can also be found via: //! let replica_owning_nodes = ring.nodes_for_key(&key).unwrap(); //! assert_eq!(replica_owning_nodes, virtual_node_clone.replica_owners()); //! //! // In this example, since the ring is populated with 3 Nodes and the replication factor is also //! // equal to 3, all Nodes should be assigned with a replica of the key. //! // However, the following assertion would fail, because of the order in which the replica //! // owning Nodes are reported: they are reported according to the order in which their virtual //! // nodes have been placed on the ring, rather than the order of the Nodes were inserted. //! assert_ne!(nodes, replica_owning_nodes); // `ne` due to the order in which Nodes are reported! //! ``` //! //! # Implementation Notes //! //! ## `Arc`s //! //! Mind that in multi-threaded contexts, users of [`HashRing<N, H>`] should explicitly wrap it in //! an [`Arc`][Arc] to share it among the threads. //! Single-threaded contexts may opt out of this to avoid the overhead of atomic reference //! counting; however, [`Arc`][Arc]s are being used internally all over the crate anyway. //! //! ## RCU-like Synchronization //! //! The soundness of the implementation of the crate is undergirded by a //! [Read-Copy-Update][RCU]-like technique for synchronizing concurrent accesses to the consistent //! hashing ring data structure by multiple threads. //! This means that the implementation of the data structure does not rely on locks, but on //! atomically reading a pointer internal to [`HashRing<N, H>`], copying the data, updating the //! local copy and then atomically storing the new address to the pointer. //! The primitives upon which the implementation is based belong to the [`crossbeam_epoch`] crate. //! //! An alternative to this would be to use a [`Mutex`][Mutex] or a [`RwLock`][RwLock], but this is //! not how this crate has been implemented. //! //! ## Garbage Collection //! //! Concurrent read and write operations on a [`HashRing<N, H>`] using a [RCU][RCU]-like technique //! introduce a major issue: //! when a mutation occurs, the underlying data structure pointed to internally by the //! [`HashRing<N, H>`] is no longer needed, and is therefore dropped and immediately freed. //! However, a number of concurrent reader threads may still require access to it. //! Garbage-collected languages, like Java and Go, trivially solve this issue by relying on their //! runtime's garbage collector to clean it up only when no threads can access it. //! Rust's lightweight runtime does not include a garbage collector; it rather relies on its unique //! RAII-based system. //! //! To address this issue, this crate is based on the [`crossbeam_epoch`] crate, which enables //! epoch-based memory reclamation. //! This is also where the [`Guard`] type and the [`pin`] function are re-exported from, for ease //! of use. //! It is highly recommended for anyone that considers using this crate to go through the //! documentation of the [`crossbeam_epoch`] crate as well. //! //! ## Performance //! //! The crate has not been properly benchmarked and evaluated yet. //! //! Informally, it certainly looks and feels fast, especially in the aforementioned cases of //! multiple concurrent reader threads and rare write operations. //! //! //! [consistent hashing ring]: https://en.wikipedia.org/wiki/Consistent_hashing //! [DefaultHasher]: https://doc.rust-lang.org/std/collections/hash_map/struct.DefaultHasher.html //! [BLAKE3.io]: https://blake3.io/ //! [blake3]: https://docs.rs/blake3/0.3/blake3/ //! [BLAKE2b]: https://www.blake2.net/ //! [blake2b_simd]: https://docs.rs/blake2b_simd/0.5/blake2b_simd/ //! [Arc]: https://doc.rust-lang.org/std/sync/struct.Arc.html //! [RCU]: https://en.wikipedia.org/wiki/Read-copy-update //! [Mutex]: https://doc.rust-lang.org/std/sync/struct.Mutex.html //! [RwLock]: https://doc.rust-lang.org/std/sync/struct.RwLock.html //! [`crossbeam_epoch`]: https://docs.rs/crossbeam-epoch/0.9/crossbeam_epoch/index.html // Also see: https://morestina.net/blog/742/exploring-lock-free-rust-1-locks #![doc(html_root_url = "https://docs.rs/lfchring-rs/0.1.3")] #![warn(rust_2018_idioms)] #![deny( missing_docs, //missing_doc_code_examples, // nightly-only? unreachable_pub, broken_intra_doc_links, )] //#![allow(dead_code, unused_variables, unused_imports)] mod iter; mod ring; mod state; mod types; mod vnode; #[cfg(test)] mod tests; pub use iter::Iter; pub use ring::HashRing; pub use types::HashRingError; pub use types::Hasher; pub use types::Node; pub use types::Result; pub use types::Vnid; pub use vnode::VirtualNode; #[cfg(feature = "blake2b-hash")] pub use types::Blake2bHasher; #[cfg(feature = "blake3-hash")] pub use types::Blake3Hasher; pub use crossbeam_epoch::{pin, Guard};