README
¶
Aggregated Highest Random Weight Hashing / Aggregated Rendezvous Hashing
AHRW pre-aggregates input objects into specified number of slots and only then distributes these slots across provided nodes. It allows memoization of calculations made for each slot and makes rendezvous hashing practical for large numbers of nodes (or shares of capacity for weighted case) and/or high request rates.
Documentation
¶
Overview ¶
Package implements aggregated rendezvous hashing with O(1) amortized time complexity.
Example ¶
package main
import (
"fmt"
"github.com/SenseUnit/ahrw"
)
func main() {
nodes := []ahrw.Node{
ahrw.NewServer("server1", "red"),
ahrw.NewServer("server2", "orange"),
ahrw.NewServer("server3", "yellow"),
ahrw.NewServer("server4", "green"),
ahrw.NewServer("server5", "blue"),
ahrw.NewServer("server6", "indigo"),
ahrw.NewServer("server7", "violet"),
}
h, err := ahrw.New(16384, nodes)
if err != nil {
panic(err)
}
for _, obj := range []string{"object1", "object2", "object3", "object4", "object5"} {
fmt.Printf("%s -> %s\n", obj, h.NodeForString(obj).(*ahrw.Server).Handle().(string))
}
}
Output:
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ( // ErrZeroSlots indicates incorrect invocation of New with zero slots. ErrZeroSlots = errors.New("number of slots can't be zero") // ErrZeroNodes indicates incorrect invocation of New with empty slice // of nodes. ErrZeroNodes = errors.New("number of nodes can't be zero") // ErrSlotOutOfRange is returned when requested slot is // beyond index range of created AHRW instance. ErrSlotOutOfRange = errors.New("slot out of range") )
Functions ¶
func SlotForBytes ¶
SlotForBytes uniformly maps byte slice identifying some object to some slot.
Types ¶
type AHRW ¶
type AHRW struct {
// contains filtered or unexported fields
}
AHRW stands for Aggregated Highest Random Weight.
It implements Rendezvous Hashing, mapping objects to respective nodes with minimal remapping if set of nodes changes.
AHRW pre-aggregates input objects into specified number of slots and only then distributes these slots across provided nodes. It allows memoization of calculations made for each slot and makes rendezvous hashing practical for large numbers of nodes (or shares of capacity for weighted case) and/or high request rates.
AHRW is safe for concurrent use by multiple goroutines and for efficiency should only be created once and re-used. On the other hand AHRW instance should be recreated to change set of active nodes.
func New ¶
New returns instance of AHRW with nslots slots distributed to nodes.
Reasonable choice of nslots is two orders of magnitude higher than maximal potential number of nodes. It works a bit faster if nslots is power of two. E.g. for expected maximum of 100 nodes reasonable choice would be 16384.
nslots should be the same across instances for different sets of nodes, otherwise AHRW will not maintain minimal difference of distribution. It's fine to have some hardcoded value covering needs for near future.
func (*AHRW) NodeForBytes ¶
NodeForBytes maps slice of bytes identifying some object to one of nodes provided to this AHRW instance.
func (*AHRW) NodeForSlot ¶
NodeForSlot returns mapped node for specified slot. Useful if you'd like to implement hashing of your objects on your own.
func (*AHRW) NodeForString ¶
NodeForString maps string identifying some object to one of nodes provided to this AHRW instance.
type Node ¶
type Node interface {
// NodeID returns slice of bytes unique within set of all targets
// provided to AHRW instance.
NodeID() []byte
}
Node is the interface for load balancing targets (servers, shards etc) of rendezvous hashing algorithm.
type Server ¶
type Server struct {
// contains filtered or unexported fields
}
Server is an implementation of Node interface provided for convenience.
func NewServer ¶
NewServer creates Server identified by name and holding some handle. Handle is useful to reference actual server object. This way Server wraps any type and provides NodeID inferred from unique name.
Source Files