Struct lfchring::HashRing

pub struct HashRing<N: ?Sized, H> where
    N: Node,
    H: Hasher,  { /* fields omitted */ }

The consistent hashing ring data structure.

Users will probably interact with this crate mostly through this type, as it is central to its API.

In multi-threaded contexts, it needs to be wrapped in Arc.

To find out more general information regarding its use, refer to the crate-level documentation.

Implementations

impl<N: ?Sized> HashRing<N, DefaultStdHasher> where
    N: Node, 

pub fn with_nodes(
    vnodes_per_node: Vnid,
    replication_factor: u8,
    nodes: &[Arc<N>]
) -> Result<Self>

Create a new HashRing<N, H> configured with the given parameters (i.e., the number of virtual nodes per ring node and the replication factor) and initialize it with the provided Nodes (the ring will be populated by their VirtualNodes automatically).

The new HashRing<N, H> will employ the built-in Hasher that is based on standard library’s DefaultHasher.

Errors

• Returns HashRingError::InvalidConfiguration if either the number of virtual nodes per distinct ring node or the replication factor is 0.

• Returns HashRingError::VirtualNodeAlreadyExists in the case that a hash collision occurs while attempting to insert the given Nodes in the new consistent hashing ring. The reason for this can be one of the following:

  • the output of Node::hashring_node_id for two (or more) of the Nodes provided for insertion is equal;
  • the provided Hasher produces equal hash digests for different outputs of Node::hashring_node_id for two (or more) Nodes among those provided for insertion.

pub fn new(vnodes_per_node: Vnid, replication_factor: u8) -> Result<Self>

Create a new HashRing<N, H> configured with the given parameters (i.e., the number of virtual nodes per ring node and the replication factor), which is initially empty of Nodes (and, of course, empty of VirtualNodes too).

The new HashRing<N, H> will employ the built-in Hasher that is based on standard library’s DefaultHasher.

Errors

Returns HashRingError::InvalidConfiguration if either the number of virtual nodes per distinct ring node or the replication factor is 0.

impl<N: ?Sized, H> HashRing<N, H> where
    N: Node,
    H: Hasher, 

pub fn with_hasher_and_nodes(
    hasher: H,
    vnodes_per_node: Vnid,
    replication_factor: u8,
    nodes: &[Arc<N>]
) -> Result<Self>

Create a new HashRing<N, H> configured with the given parameters (i.e., the number of virtual nodes per ring node and the replication factor) and initialize it with the provided Nodes (the ring will be populated by their VirtualNodes automatically).

The new HashRing<N, H> will employ the provided Hasher for placing the VirtualNodes on the consistent hashing ring.

Errors

• Returns HashRingError::InvalidConfiguration if either the number of virtual nodes per distinct ring node or the replication factor is 0.

• Returns HashRingError::VirtualNodeAlreadyExists in the case that a hash collision occurs while attempting to insert the given Nodes in the new consistent hashing ring. The reason for this can be one of the following:

  • the output of Node::hashring_node_id for two (or more) of the Nodes provided for insertion is equal;
  • the provided Hasher produces equal hash digests for different outputs of Node::hashring_node_id for two (or more) Nodes among those provided for insertion.

pub fn with_hasher(
    hasher: H,
    vnodes_per_node: Vnid,
    replication_factor: u8
) -> Result<Self>

Create a new HashRing<N, H> configured with the given parameters (i.e., the number of virtual nodes per ring node and the replication factor), which is initially empty of Nodes (and, of course, empty of VirtualNodes too).

The new HashRing<N, H> will employ the provided Hasher for placing the VirtualNodes on the consistent hashing ring.

Errors

Returns HashRingError::InvalidConfiguration if either the number of virtual nodes per distinct ring node or the replication factor is 0.

pub fn len_nodes(&self) -> usize

Returns the number of distinct ring nodes that currently populate the consistent hashing ring.

pub fn len_virtual_nodes(&self) -> usize

Returns the number of virtual nodes that currently populate the consistent hashing ring.

This should always be equal to the result of HashRing::len_nodes multiplied by the vnodes_per_node for a particular HashRing<N, H>.

pub fn insert(&self, nodes: &[Arc<N>]) -> Result<()>

Insert the given Nodes to the consistent hashing ring, thereby expanding it.

Errors

HashRingError::VirtualNodeAlreadyExists is returned in the case of a hash collision while attempting to insert the given Nodes in the consistent hashing ring. This can happen if:

• the output of Node::hashring_node_id for one (or more) of the new Nodes is equal to that of one of the Nodes that already exist in the ring;
• the output of Node::hashring_node_id for two (or more) of the new Nodes is equal to each other;
• the provided Hasher produces equal hash digests for different outputs of Node::hashring_node_id for two (or more) Nodes among the new or the already existing ones.

pub fn remove(&self, nodes: &[Arc<N>]) -> Result<()>

Remove the given Nodes from the consistent hashing ring, thereby shrinking it.

Errors

HashRingError::VirtualNodeDoesNotExist is returned in the case that one of the Nodes provided for removal does not currently exist in the consistent hashing ring.

pub fn has_virtual_node<K>(&self, key: &K) -> bool where
    K: Borrow<[u8]>, 

Returns true if the provided key corresponds to an existing VirtualNode of some Node in the consistent hashing ring, or false otherwise.

pub fn virtual_node_for_key<K>(&self, key: &K) -> Result<VirtualNode<N>> where
    K: Borrow<[u8]>, 

Look up in the consistent hashing ring and return a clone of the VirtualNode that the given key should be assigned on.

Errors

Returns HashRingError::EmptyRing if the consistent hashing ring is currently empty of Nodes and therefore the given key cannot be assigned to any VirtualNode (as none exists).

pub fn nodes_for_key<K>(&self, key: &K) -> Result<Vec<Arc<N>>> where
    K: Borrow<[u8]>, 

Look up in the consistent hashing ring and return a Vec of Nodes, each wrapped in an Arc, on which a replica of the given key should be assigned on.

The Nodes are returned according to their order in the consistent hashing ring. Therefore, the first Node is always the one that the particular VirtualNode originally belongs to.

Errors

Returns HashRingError::EmptyRing if the consistent hashing ring is currently empty of Nodes and therefore the given key cannot be assigned to any VirtualNode (as none exists).

pub fn predecessor<K>(&self, key: &K) -> Result<VirtualNode<N>> where
    K: Borrow<[u8]>, 

Look up in the consistent hashing ring and return the VirtualNode which is the predecessor of the one that the given key should be assigned on.

Errors

Returns HashRingError::EmptyRing if the consistent hashing ring is currently empty of Nodes and therefore the given key cannot be assigned to any VirtualNode (as none exists).

pub fn successor<K>(&self, key: &K) -> Result<VirtualNode<N>> where
    K: Borrow<[u8]>, 

Look up in the consistent hashing ring and return the VirtualNode which is the successor of the one that the given key should be assigned on.

Errors

Returns HashRingError::EmptyRing if the consistent hashing ring is currently empty of Nodes and therefore the given key cannot be assigned to any VirtualNode (as none exists).

pub fn predecessor_node<K>(&self, key: &K) -> Result<VirtualNode<N>> where
    K: Borrow<[u8]>, 

Look up in the consistent hashing ring and return the first predecessor VirtualNode to the one that the given key should be assigned on, but which also belongs to a different distinct Node than the latter.

Errors

• Returns HashRingError::EmptyRing if the consistent hashing ring is currently empty of Nodes and therefore the given key cannot be assigned to any VirtualNode (as none exists).
• Returns HashRingError::SingleDistinctNodeRing if the consistent hashing ring currently consists of a single distinct node and therefore all VirtualNodes in the ring actually belong to the same Node.

pub fn successor_node<K>(&self, key: &K) -> Result<VirtualNode<N>> where
    K: Borrow<[u8]>, 

Look up in the consistent hashing ring and return the first successor VirtualNode to the one that the given key should be assigned on, but which also belongs to a different distinct Node than the latter.

Errors

• Returns HashRingError::EmptyRing if the consistent hashing ring is currently empty of Nodes and therefore the given key cannot be assigned to any VirtualNode (as none exists).
• Returns HashRingError::SingleDistinctNodeRing if the consistent hashing ring currently consists of a single distinct node and therefore all VirtualNodes in the ring actually belong to the same Node.

pub fn iter<'guard>(&self, guard: &'guard Guard) -> Iter<'guard, N, H>

Returns an Iter, i.e., an iterator to loop through all VirtualNodes that populate the consistent hashing ring.

See the documentation of Iter for more information regarding its use.

Trait Implementations

impl<N: ?Sized, H> Clone for HashRing<N, H> where
    N: Node,
    H: Hasher, 

fn clone(&self) -> Self

Returns a copy of the value.

pub fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<N: Debug + ?Sized, H: Debug> Debug for HashRing<N, H> where
    N: Node,
    H: Hasher, 

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<N: ?Sized, H> Display for HashRing<N, H> where
    N: Node,
    H: Hasher, 

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<N: ?Sized, H> Extend<Arc<N>> for HashRing<N, H> where
    N: Node,
    H: Hasher, 

fn extend<I: IntoIterator<Item = Arc<N>>>(&mut self, iter: I)

Extend the HashRing<N, H> by the Nodes provided through the given IntoIterator over Arc<N>>.

Note that, due to the restriction of Extend::extend’s signature, a &mut HashRing is required to use this method. The preferred way to extend the ring is via HashRing::insert anyway; read the section below for further details.

Panics

Although the Extend trait is implemented for HashRing<N, H>, it is not the preferred way of extending it. The signature of Extend::extend does not allow to return a Result::Err if the extension attempt fails. Therefore, in case of hash collision (e.g., when inserting an already existing Node in the HashRing<N, H>) this method fails by panicking (although the ring remains in a consistent state, since updating the ring is considered an atomic operation).

The preferred way to add Nodes to the HashRing<N, H> is via HashRing::insert instead, which returns a Result::Err that can be handled in case of a failure. Only use this method if you know for sure that hash collisions are extremely unlikely and practically impossible (e.g., when employing a cryptographically secure hash algorithm and no attempts to re-insert existing Nodes occur).

pub fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

pub fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.