README
¶
lfchring
Package lfchring provides a wait-free consistent hashing ring immutable in-memory data structure, designed for very efficient frequent reading by multiple readers and less frequent updates by a single writer.
It features efficient handling of a static number of virtual ring nodes per distinct ring node, as well as auto-managed data replication information (using a static replication factor). It also allows users to pass the hash function of their choice, further improving its flexibility.
The API is simple, easy to use, and is documented in godoc.
It has no external dependencies.
Documentation
¶
Overview ¶
Package lfchring provides an efficient lock-free consistent hashing ring data structure, designed for frequent reading by multiple readers and less frequent updates by a single writer.
It features efficient handling of a static number of virtual ring nodes per distinct ring node, as well as auto-managed data replication information (using a static replication factor), and an easy-to-use interface.
It also offers to the users flexibility to choose their own hash function, and there is no dependency other than the standard library.
Index ¶
- type HashRing
- func (r *HashRing) Clone() *HashRing
- func (r *HashRing) HasVirtualNode(key []byte) bool
- func (r *HashRing) Insert(nodes ...Node) ([]*VirtualNode, error)
- func (r *HashRing) NewVirtualNodesIterator() *VirtualNodesIterator
- func (r *HashRing) NewVirtualNodesReverseIterator() *VirtualNodesReverseIterator
- func (r *HashRing) NodesForKey(key []byte) []Node
- func (r *HashRing) NodesForObject(reader io.Reader) ([]Node, error)
- func (r *HashRing) Predecessor(key []byte) (*VirtualNode, error)
- func (r *HashRing) PredecessorNode(key []byte) (*VirtualNode, error)
- func (r *HashRing) Remove(nodes ...Node) ([]*VirtualNode, error)
- func (r *HashRing) Size() int
- func (r *HashRing) String() string
- func (r *HashRing) Successor(key []byte) (*VirtualNode, error)
- func (r *HashRing) SuccessorNode(key []byte) (*VirtualNode, error)
- func (r *HashRing) VirtualNodeForKey(key []byte) *VirtualNode
- func (r *HashRing) VirtualNodes(stop <-chan struct{}) <-chan *VirtualNode
- func (r *HashRing) VirtualNodesReversed(stop <-chan struct{}) <-chan *VirtualNode
- type Node
- type VirtualNode
- type VirtualNodesIterator
- type VirtualNodesReverseIterator
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type HashRing ¶
type HashRing struct {
// contains filtered or unexported fields
}
HashRing is a lock-free consistent hashing ring entity, designed for frequent reads by multiple readers and infrequent updates by one single writer. In addition, it features efficient support of virtual ring nodes per distinct node, as well as "auto-managed" data replication among the distinct nodes.
func NewHashRing ¶
func NewHashRing(hashFunc func([]byte) []byte, replicationFactor, virtualNodeCount int, nodes ...Node) (*HashRing, error)
NewHashRing returns a new HashRing, properly initialized based on the given parameters, or a non-nil error value if the parameters are invalid.
An arbitrary number of nodes may optionally be inserted to the new ring during the initialization through parameter `nodes` (hence, NewHashRing is a variadic function).
func (*HashRing) Clone ¶
Clone allocates, initializes and returns a new ring, which is a deep copy of the original.
func (*HashRing) HasVirtualNode ¶
HasVirtualNode returns true if the given key corresponds to a virtual node in the ring, or false otherwise.
Complexity: O( log(V*N) )
func (*HashRing) Insert ¶
func (r *HashRing) Insert(nodes ...Node) ([]*VirtualNode, error)
Insert is a variadic method to insert an arbitrary number of distinct nodes (i.e. all their virtual nodes) to the ring.
In the case that an already existing distinct node is attempted to be re-inserted to the ring, Insert returns a non-nil error value and the ring is left untouched. Otherwise, the ring is modified as expected, and a slice of the new virtual nodes (not sorted) is returned.
func (*HashRing) NewVirtualNodesIterator ¶
func (r *HashRing) NewVirtualNodesIterator() *VirtualNodesIterator
NewVirtualNodesIterator returns a new VirtualNodesIterator for efficiently iterating through ring's virtual nodes in (alphanumerical) order.
func (*HashRing) NewVirtualNodesReverseIterator ¶
func (r *HashRing) NewVirtualNodesReverseIterator() *VirtualNodesReverseIterator
NewVirtualNodesReverseIterator returns a new VirtualNodesReverseIterator for efficiently iterating through ring's virtual nodes in reverse (alphanumerical) order.
func (*HashRing) NodesForKey ¶
NodesForKey returns a slice of Nodes (of length equal to the configured replication factor) that are currently responsible for holding the given key.
Complexity: O( log(V*N) )
func (*HashRing) NodesForObject ¶
NodesForObject returns a slice of Nodes (of length equal to the configured replication factor) that are currently responsible for holding the object that can be read from the given io.Reader (hashing is applied first). It returns a non-nil error value in the case of a failure while reading from the io.Reader.
Complexity: O( Read ) + O( hash ) + O( log(V*N) )
func (*HashRing) Predecessor ¶
func (r *HashRing) Predecessor(key []byte) (*VirtualNode, error)
Predecessor returns the virtual node which is predecessor to the one that the given key would be assigned to. It returns a non-nil error if the ring is empty.
Complexity: O( log(V*N) )
func (*HashRing) PredecessorNode ¶
func (r *HashRing) PredecessorNode(key []byte) (*VirtualNode, error)
PredecessorNode returns the virtual node which is the first predecessor to the one that the given key would be assigned to, but also belongs to a different distinct node than the latter. It returns a non-nil error if the ring either is empty or consists of a single distinct node.
Complexity: Worst case O(V*N) but should be O( log(V*N) ) on average.
func (*HashRing) Remove ¶
func (r *HashRing) Remove(nodes ...Node) ([]*VirtualNode, error)
Remove is a variadic method to remove an arbitrary number of distinct nodes (i.e. all their virtual nodes) from the ring.
If any of the distinct nodes' virtual nodes cannot be found in the ring, a non-nil error value is returned and the ring is left untouched; otherwise the ring is modified as expected, and a slice of the removed virtual nodes (not sorted) is returned.
func (*HashRing) Size ¶
Size returns the number of *distinct* nodes in the ring, in its current state.
func (*HashRing) String ¶
String returns the slice of virtual nodes of the current state of the ring, along with their replica owners, as a "print-friendly" string.
func (*HashRing) Successor ¶
func (r *HashRing) Successor(key []byte) (*VirtualNode, error)
Successor returns the virtual node which is successor to the one that the given key would be assigned to. It returns a non-nil error if the ring is empty.
Complexity: O( log(V*N) )
func (*HashRing) SuccessorNode ¶
func (r *HashRing) SuccessorNode(key []byte) (*VirtualNode, error)
SuccessorNode returns the virtual node which is the first successor to the one that the given key would be assigned to, but also belongs to a different distinct node than the latter. It returns a non-nil error if the ring either is empty or consists of a single distinct node.
Complexity: Worst case O(V*N) but should be O( log(V*N) ) on average.
func (*HashRing) VirtualNodeForKey ¶
func (r *HashRing) VirtualNodeForKey(key []byte) *VirtualNode
VirtualNodeForKey returns the virtual node in the ring that the given key would be assigned to.
Complexity: O( log(V*N) )
func (*HashRing) VirtualNodes ¶
func (r *HashRing) VirtualNodes(stop <-chan struct{}) <-chan *VirtualNode
VirtualNodes allows iteration over all virtual nodes in the ring, by returning a channel for the caller to read the virtual nodes from.
The stop channel parameter, if used with care, may help avoiding memory leaks when quitting the iteration early.
BUG: If there is a chance for the returned channel not to be drained (i.e. to quit the iteration early), it is highly recommended to use a VirtualNodesIterator instead, which API, although maybe less comfortable, makes sure there will be no memory leaks (specifically, goroutine leaks) in such cases.
func (*HashRing) VirtualNodesReversed ¶
func (r *HashRing) VirtualNodesReversed(stop <-chan struct{}) <-chan *VirtualNode
VirtualNodesReversed allows iteration over all virtual nodes in the ring in reverse order, by returning a channel for the caller to read the virtual nodes from.
The stop channel parameter, if used with care, may help avoiding memory leaks when quitting the iteration early.
BUG: If there is a chance for the returned channel not to be drained (i.e. to quit the iteration early), it is highly recommended to use a VirtualNodesReverseIterator instead, which API, although maybe less comfortable, makes sure there will be no memory leaks (specifically, goroutine leaks) in such cases.
type VirtualNode ¶
type VirtualNode struct {
// contains filtered or unexported fields
}
VirtualNode represents a single virtual node in the ring.
func (*VirtualNode) Name ¶
func (vn *VirtualNode) Name() []byte
Name returns the "name" of the virtual node as it appears on the ring (i.e. as a key in the key space that the ring operates on).
func (*VirtualNode) Node ¶
func (vn *VirtualNode) Node() Node
Node returns the distinct node that the virtual node represents (or "belongs to").
func (*VirtualNode) String ¶
func (vn *VirtualNode) String() string
String returns a representation of the VirtualNode in a print-friendly format.
type VirtualNodesIterator ¶
type VirtualNodesIterator struct {
// contains filtered or unexported fields
}
VirtualNodesIterator is an iterator for efficiently iterating through all virtual nodes in the ring in (alphanumerical) order.
func (*VirtualNodesIterator) HasNext ¶
func (iter *VirtualNodesIterator) HasNext() bool
HasNext returns true if there is at least one more virtual node in the ring to iterate over, and false if there is none.
The user of VirtualNodesIterator should always check the result of HasNext before calling Next to avoid panicking.
func (*VirtualNodesIterator) Next ¶
func (iter *VirtualNodesIterator) Next() *VirtualNode
Next returns the next virtual node of the iteration.
The user of VirtualNodesIterator should always check the result of HasNext before calling Next to avoid panicking.
type VirtualNodesReverseIterator ¶
type VirtualNodesReverseIterator struct {
// contains filtered or unexported fields
}
VirtualNodesReverseIterator is an iterator for efficiently iterating through all virtual nodes in the ring in reverse (alphanumerical) order.
func (*VirtualNodesReverseIterator) HasNext ¶
func (iter *VirtualNodesReverseIterator) HasNext() bool
HasNext returns true if there is at least one more virtual node in the ring to iterate over, and false if there is none.
The user of VirtualNodesReverseIterator should always check the result of HasNext before calling Next to avoid panicking.
func (*VirtualNodesReverseIterator) Next ¶
func (iter *VirtualNodesReverseIterator) Next() *VirtualNode
Next returns the next virtual node of the (reverse) iteration.
The user of VirtualNodesReverseIterator should always check the result of HasNext before calling Next to avoid panicking.
Source Files