[−][src]Struct consistent_hash_ring::Ring
A consistent hash ring with support for virtual nodes and key replication.
How it works
Typical hash ring construction. See wikipedia.
Nodes are mapped onto locations on a finite ring using a hash function. Keys are likewise hashed and mapped onto the same ring; the responsible node for a given key is the first node whose hash is greater than or equal to the key's hash.
Virtual Nodes
Because node locations on the ring are only uniformly distributed when looking at the ring containing all possible nodes, we map each node to multiple vnodes to improve the statistical properties of key distribution. The probability of a node being selected for any given key scales linearly with the proportion of assigned vnodes relative to other nodes in the ring.
Replication
Keys may optionally be mapped to a set of disjoint vnodes for fault tolerance or high availability purposes. Each additional replica is located by hashing keys an extra round; the hash is then mapped in the same manner as a single key. If any duplicate nodes arise during replica resolution, a circular scan starting at the index of the offending vnode is used to select the next vnode.
Performance
Mutable and immutable operations on the ring tend toward linear and sublinear complexity respectively.
The figures given below assume that:
- n = total nodes
- k = total vnodes
- v = vnodes per node
- r = replica count
Methods
impl<T: Hash + Eq + Clone, S: BuildHasher> Ring<T, S>
[src]
pub fn len(&self) -> usize
[src]
Returns the number of nodes in the ring (not including any duplicate vnodes).
O(1)
use consistent_hash_ring::*; let ring = RingBuilder::default() .nodes_iter(0..32) .build(); assert_eq!(32, ring.len());
pub fn is_empty(&self) -> bool
[src]
Returns whether or not the ring is empty.
O(1)
use consistent_hash_ring::*; let mut ring = Ring::default(); assert!(ring.is_empty()); ring.insert(&()); assert!(!ring.is_empty());
pub fn vnodes(&self) -> usize
[src]
Returns the total number of vnodes in the ring, across all nodes.
O(1)
use consistent_hash_ring::*; let ring = RingBuilder::default() .vnodes(4) .nodes_iter(0..12) .build(); assert_eq!(48, ring.vnodes()); assert_eq!(12, ring.len());
pub fn weight<Q: ?Sized>(&self, node: &Q) -> Option<usize> where
T: Borrow<Q>,
Q: Hash + Eq,
[src]
T: Borrow<Q>,
Q: Hash + Eq,
Returns the number of vnodes for the provided node, or None
if it does
not exist.
O(log n)
use consistent_hash_ring::*; let mut ring = RingBuilder::default() .vnodes(12) .nodes_iter(0..4) .weighted_node(42, 9) .build(); assert_eq!(Some(12), ring.weight(&3)); assert_eq!(Some(9), ring.weight(&42)); assert_eq!(None, ring.weight(&24));
pub fn insert(&mut self, node: T)
[src]
Insert a node into the ring with the default vnode count.
O(k * v + (v * log k) + log k + n + log n)
use consistent_hash_ring::*; let mut ring = Ring::default(); ring.insert("hello worldo"); assert_eq!(1, ring.len()); assert_eq!(Some(10), ring.weight("hello worldo"));
pub fn insert_weight(&mut self, node: T, vnodes: usize)
[src]
Insert a node into the ring with the provided number of vnodes.
This can be used give some nodes more weight than others - nodes with more vnodes will be selected for larger proportions of keys.
If the provided node is already present in the ring, the count is updated.
O(k * v + (v * log k) + log k + n + log n)
use consistent_hash_ring::*; let mut ring = Ring::default(); ring.insert("hello worldo"); ring.insert_weight("worldo hello", 9); assert_eq!(2, ring.len()); assert_eq!(Some(10), ring.weight("hello worldo")); assert_eq!(Some(9), ring.weight("worldo hello"));
pub fn remove<Q: ?Sized>(&mut self, node: &Q) where
T: Borrow<Q>,
Q: Hash + Eq,
[src]
T: Borrow<Q>,
Q: Hash + Eq,
Remove a node from the ring.
Any keys that were mapped to this node will be uniformly distributed amongst nearby nodes.
O(k + n + log n)
use consistent_hash_ring::*; let mut ring = RingBuilder::default() .nodes_iter(0..12) .build(); assert_eq!(12, ring.len()); assert_eq!(Some(10), ring.weight(&3)); ring.remove(&3); assert_eq!(11, ring.len()); assert_eq!(None, ring.weight(&3));
pub fn try_get<K: Hash>(&self, key: K) -> Option<&T>
[src]
Returns a reference to the first node responsible for the provided key.
Any key type may be used so long as it is Hash.
Returns None
if there are no nodes in the ring.
O(log k)
use consistent_hash_ring::*; let mut ring = RingBuilder::default() .vnodes(12) .build(); assert_eq!(None, ring.try_get("none")); ring.insert("hello worldo"); assert_eq!(Some(&"hello worldo"), ring.try_get(42));
pub fn get<K: Hash>(&self, key: K) -> &T
[src]
Returns a reference to the first node responsible for the provided key.
Any key type may be used so long as it is Hash.
Panics if there are no nodes in the ring.
O(log k)
use consistent_hash_ring::*; let mut ring = RingBuilder::default() .vnodes(12) .nodes_iter(0..1) .build(); assert_eq!(&0, ring.get("by"));
ⓘImportant traits for Candidates<'a, T, S>pub fn replicas<'a, K: Hash>(&'a self, key: K) -> Candidates<'a, T, S>
[src]
Returns an iterator over replication candidates for the provided key.
Prefer Ring::get
instead if only the first node will be used.
O(r * (r + log r + k + log k))
use consistent_hash_ring::*; let ring = RingBuilder::default() .replicas(3) .nodes_iter(0..12) .build(); let expect = vec![&10, &2, &8]; assert_eq!(expect, ring.replicas("key").collect::<Vec<_>>()); assert_eq!(expect[0], ring.get("key")); let ring: Ring<()> = RingBuilder::default() .replicas(3) .build(); assert_eq!(None, ring.replicas("key").next());
Trait Implementations
impl<T: Clone + Hash + Eq, S: Clone> Clone for Ring<T, S>
[src]
fn clone(&self) -> Ring<T, S>
[src]
fn clone_from(&mut self, source: &Self)
1.0.0[src]
Performs copy-assignment from source
. Read more
impl<T: Hash + Eq + Clone> Default for Ring<T>
[src]
impl<K: Hash, T: Hash + Eq + Clone, S: BuildHasher> Index<K> for Ring<T, S>
[src]
Auto Trait Implementations
impl<T, S> Sync for Ring<T, S> where
S: Sync,
T: Sync,
S: Sync,
T: Sync,
impl<T, S> Unpin for Ring<T, S> where
S: Unpin,
T: Unpin,
S: Unpin,
T: Unpin,
impl<T, S> Send for Ring<T, S> where
S: Send,
T: Send,
S: Send,
T: Send,
impl<T, S> UnwindSafe for Ring<T, S> where
S: UnwindSafe,
T: UnwindSafe,
S: UnwindSafe,
T: UnwindSafe,
impl<T, S> RefUnwindSafe for Ring<T, S> where
S: RefUnwindSafe,
T: RefUnwindSafe,
S: RefUnwindSafe,
T: RefUnwindSafe,
Blanket Implementations
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
The type returned in the event of a conversion error.
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,