hashring

package
v1.2.123 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Apr 18, 2025 License: MIT Imports: 10 Imported by: 0

Documentation

Overview

Package hashring provides a consistent hashing function.

HashRing, aka NodeLocator hashing, is often used to distribute requests to a changing set of servers. For example, say you have some cache servers cacheA, cacheB, and cacheC. You want to decide which cache server to use to look up information on a user.

You could use a typical hash table and hash the user id to one of cacheA, cacheB, or cacheC. But with a typical hash table, if you add or remove a server, almost all keys will get remapped to different results, which basically could bring your service to a grinding halt while the caches get rebuilt.

With a consistent hash, adding or removing a server drastically reduces the number of keys that get remapped.

Read more about consistent hashing on wikipedia: http://en.wikipedia.org/wiki/Consistent_hashing

Index

Examples

Constants

This section is empty.

Variables

View Source 
var (
	// CRCHash hash algorithm by crc32.
	CRCHash = HashFunc(crcHash)
	// CRCPerlHash as used by the perl API. This will be more consistent both
	// across multiple API users as well as java versions, but is mostly likely
	// significantly slower.
	CRCPerlHash = HashFunc(crcPerlHash)

	// FNV132Hash hash algorithm by 32-bit FNV1.
	FNV132Hash = HashFunc(fnv132Hash)
	// FNV1a32Hash hash algorithm by Variation of FNV.
	// 32-bit FNV1a.
	FNV1a32Hash = HashFunc(fnv1a32Hash)
	// FNV164Hash hash algorithm by 64-bit FNV1.
	FNV164Hash = HashFunc(fnv164Hash)
	// FNV1a64Hash hash algorithm by FNV1a.
	FNV1a64Hash = HashFunc(fnv1a64Hash)
	// FNV1128Hash hash algorithm by 128-bit FNV1.
	FNV1128Hash = HashFunc(fnv1128Hash)
	// FNV1a128Hash hash algorithm by 128-bit FNV1a.
	FNV1a128Hash = HashFunc(fnv1a128Hash)
	// KetamaHash hash algorithm by MD5-based hash algorithm used by ketama.
	KetamaHash = HashFunc(ketamaHash)
)

Known hashing algorithms for locating a server for a key. Note that all hash algorithms return 64-bits of hash, but only the lower 32-bits are significant. This allows a positive 32-bit number to be returned for all cases.

Functions

This section is empty.

Types

type EmptyHashRingOption 

type EmptyHashRingOption[Node comparable] struct{}

EmptyHashRingOption does not alter the configuration. It can be embedded in another structure to build custom options.

This API is EXPERIMENTAL.

type Format 

type Format int

Format describes known key formats used in Ketama for assigning nodes around the ring 

const (
	// SpyMemcached uses the format traditionally used by spymemcached to map
	// nodes to names. The format is HOSTNAME/IP:PORT-ITERATION
	//
	// This default implementation uses the socket-address of the Node
	// and concatenates it with a hyphen directly against the repetition number
	// for example a key for a particular server's first repetition may look like:
	// "myhost/10.0.2.1-0", for the second repetition: "myhost/10.0.2.1-1"
	//
	// for a server where reverse lookups are failing the returned keys may look
	// like "/10.0.2.1-0" and "/10.0.2.1-1"
	SpyMemcached Format = iota

	// LibMemcached uses the format traditionally used by libmemcached to map
	// nodes to names. The format is HOSTNAME:[PORT]-ITERATION the PORT is not
	// part of the node identifier if it is the default memcached port (11211)
	LibMemcached
)

type Formatter 

type Formatter[Node comparable] interface {
	// FormatNodeKey returns a uniquely identifying key, suitable for hashing by the
	// HashRing algorithm.
	FormatNodeKey(node Node, repetition int) string
}

Formatter is used to format node for assigning nodes around the ring

type FormatterFunc 

type FormatterFunc[Node comparable] func(node Node, repetition int) string

func (FormatterFunc[Node]) FormatNodeKey 

func (f FormatterFunc[Node]) FormatNodeKey(node Node, repetition int) string

type HashAlgorithm 

type HashAlgorithm interface {
	// Hash computes the hash for the given key.
	// @return a positive integer hash
	Hash(k string) []uint32
}

HashAlgorithm intents to provide hash for locating a server for a key.

type HashFunc 

type HashFunc func(k string) []uint32

func (HashFunc) Hash 

func (f HashFunc) Hash(k string) []uint32

type HashRing 

type HashRing[Node comparable] struct {
	// contains filtered or unexported fields
}

HashRing holds the information about the allNodes of the consistent hash nodes.

Node represents a node in the consistent hash ring. {} -> 127.0.0.1:11311 -> 127.0.0.1:11311-0 -> 1234 Node -> Key -> IterateKey -> HashKey

func New 

func New[Node comparable](opts ...HashRingOption[Node]) *HashRing[Node]

New creates a hash ring of n replicas for each entry.

Example 
package main

import (
	"fmt"
	"log"
	"slices"

	"github.com/searKing/golang/go/exp/container/hashring"
)

func main() {
	c := hashring.New[string]()
	c.AddNodes("NodeA")
	c.AddNodes("NodeB")
	c.AddNodes("NodeC")
	var nodes []string
	for node := range c.All() {
		nodes = append(nodes, node)
	}
	slices.Sort(nodes)
	fmt.Printf("all nodes: %v\n", nodes)

	users := []string{"Alice", "Bob  ", "Eve  ", "Carol", "Dave "}
	fmt.Printf("locate nodes...\n")
	for _, u := range users {
		server, has := c.Get(u)
		if !has {
			log.Fatal()
		}
		fmt.Printf("	%s => %s\n", u, server)
	}

}

Output:

all nodes: [NodeA NodeB NodeC]
locate nodes...
	Alice => NodeB
	Bob   => NodeA
	Eve   => NodeA
	Carol => NodeC
	Dave  => NodeA

func (*HashRing[Node]) AddNodes 

func (c *HashRing[Node]) AddNodes(nodes ...Node)

AddNodes inserts nodes into the consistent hash cycle.

Example 
package main

import (
	"fmt"
	"log"

	"github.com/searKing/golang/go/exp/container/hashring"
)

func main() {
	c := hashring.New[string]()
	c.AddNodes("NodeA")
	c.AddNodes("NodeB")
	c.AddNodes("NodeC")
	users := []string{"Alice", "Bob  ", "Eve  ", "Carol", "Dave "}
	fmt.Println("initial state [A, B, C]")
	for _, u := range users {
		server, has := c.Get(u)
		if !has {
			log.Fatal()
		}
		fmt.Printf("%s => %s\n", u, server)
	}
	c.AddNodes("NodeD")
	c.AddNodes("NodeE")
	fmt.Println("\nwith NodeD, NodeE [A, B, C, D, E]")
	for _, u := range users {
		server, has := c.Get(u)
		if !has {
			log.Fatal()
		}
		fmt.Printf("%s => %s\n", u, server)
	}
}

Output:

initial state [A, B, C]
Alice => NodeB
Bob   => NodeA
Eve   => NodeA
Carol => NodeC
Dave  => NodeA

with NodeD, NodeE [A, B, C, D, E]
Alice => NodeB
Bob   => NodeA
Eve   => NodeA
Carol => NodeE
Dave  => NodeA

func (*HashRing[Node]) All 

func (c *HashRing[Node]) All() iter.Seq[Node]

All returns an iterator over all nodes in hashring. If c is empty, the sequence is empty: there is no empty element in the sequence.

func (*HashRing[Node]) ApplyOptions 

func (o *HashRing[Node]) ApplyOptions(options ...HashRingOption[Node]) *HashRing[Node]

ApplyOptions call apply() for all options one by one

func (*HashRing[Node]) Get 

func (c *HashRing[Node]) Get(name string) (Node, bool)

Get returns an element close to where name hashes to in the nodes.

func (*HashRing[Node]) GetSince 

func (c *HashRing[Node]) GetSince(name string) iter.Seq[Node]

GetSince returns an iterator over distinct nodes in hashring, start from where name hashes to in the nodes.

func (*HashRing[Node]) RemoveAllNodes 

func (c *HashRing[Node]) RemoveAllNodes()

RemoveAllNodes removes all nodes in the continuum.

func (*HashRing[Node]) RemoveNodes 

func (c *HashRing[Node]) RemoveNodes(nodes ...Node)

RemoveNodes removes nodes from the consistent hash cycle

Example 
package main

import (
	"fmt"
	"log"

	"github.com/searKing/golang/go/exp/container/hashring"
)

func main() {
	c := hashring.New[string]()
	c.AddNodes("NodeA")
	c.AddNodes("NodeB")
	c.AddNodes("NodeC")
	//users := []string{"Alice", "Bob", "Eve", "Carol", "Dave", "Isaac", "Justin", "Mallory", "Oscar", "Pat", "Victor", "Trent", "Walter"}
	users := []string{"Alice", "Bob  ", "Eve  ", "Carol", "Dave "}
	fmt.Println("initial state [A, B, C]")
	for _, u := range users {
		server, has := c.Get(u)
		if !has {
			log.Fatal()
		}
		fmt.Printf("%s => %s\n", u, server)
	}
	c.RemoveNodes("NodeA")
	fmt.Println("\nNodeA removed [B, C]")
	for _, u := range users {
		server, has := c.Get(u)
		if !has {
			log.Fatal()
		}
		fmt.Printf("%s => %s\n", u, server)
	}
}

Output:

initial state [A, B, C]
Alice => NodeB
Bob   => NodeA
Eve   => NodeA
Carol => NodeC
Dave  => NodeA

NodeA removed [B, C]
Alice => NodeB
Bob   => NodeC
Eve   => NodeB
Carol => NodeC
Dave  => NodeB

func (*HashRing[Node]) SetNodes 

func (c *HashRing[Node]) SetNodes(nodes ...Node)

SetNodes setups the HashRing with the list of nodes it should use. If there are existing nodes not present in nodes, they will be removed. @param nodes a List of Nodes for this HashRing to use in its continuum

type HashRingOption 

type HashRingOption[Node comparable] interface {
	// contains filtered or unexported methods
}

A HashRingOption sets options.

func WithHashRing 

func WithHashRing[Node comparable](v HashRing[Node]) HashRingOption[Node]

WithHashRing sets HashRing.

func WithHashRingAllNodes 

func WithHashRingAllNodes[Node comparable](m map[Node]struct{}) HashRingOption[Node]

WithHashRingAllNodes appends allNodes in HashRing[Node]. <Node>

func WithHashRingAllNodesReplace 

func WithHashRingAllNodesReplace[Node comparable](v map[Node]struct{}) HashRingOption[Node]

WithHashRingAllNodesReplace sets allNodes in HashRing[Node]. <Node>

func WithHashRingHashAlg 

func WithHashRingHashAlg[Node comparable](v HashAlgorithm) HashRingOption[Node]

WithHashRingHashAlg sets hashAlg in HashRing[Node]. The hash algorithm to use when choosing a node in the Ketama consistent hash continuum

func WithHashRingIsWeighted 

func WithHashRingIsWeighted[Node comparable](v bool) HashRingOption[Node]

WithHashRingIsWeighted sets isWeighted in HashRing[Node].

func WithHashRingNodeByKey 

func WithHashRingNodeByKey[Node comparable](m map[uint32]Node) HashRingOption[Node]

WithHashRingNodeByKey appends nodeByKey in HashRing[Node]. <HashKey,Node>

func WithHashRingNodeByKeyReplace 

func WithHashRingNodeByKeyReplace[Node comparable](v map[uint32]Node) HashRingOption[Node]

WithHashRingNodeByKeyReplace sets nodeByKey in HashRing[Node]. <HashKey,Node>

func WithHashRingNodeKeyFormatter 

func WithHashRingNodeKeyFormatter[Node comparable](v Formatter[Node]) HashRingOption[Node]

WithHashRingNodeKeyFormatter sets nodeKeyFormatter in HashRing[Node]. the format used to name the nodes in Ketama, either SpyMemcached or LibMemcached

func WithHashRingNumReps 

func WithHashRingNumReps[Node comparable](v int) HashRingOption[Node]

WithHashRingNumReps sets numReps in HashRing[Node]. the number of discrete hashes that should be defined for each node in the continuum.

func WithHashRingSortedKeys 

func WithHashRingSortedKeys[Node comparable](v ...uint32) HashRingOption[Node]

WithHashRingSortedKeys appends sortedKeys in HashRing[Node]. The List of nodes to use in the Ketama consistent hash continuum

This simulates the structure of keys used in the Ketama consistent hash ring, which stores the virtual node HashKeys on the physical nodes. All nodes in the cluster are topped by virtual nodes. In principle, it is a brute-force search to find the first complete HashKey

For example, Node -> Key -> IterateKey -> HashKey {} -> 127.0.0.1:11311 -> 127.0.0.1:11311-0 -> 1234 {} -> 127.0.0.1:11311 -> 127.0.0.1:11311-160 -> 256 {} -> 127.0.0.1:11311 -> 127.0.0.1:11311-320 -> 692 []HashKey, Index for nodes binary search

func WithHashRingSortedKeysReplace 

func WithHashRingSortedKeysReplace[Node comparable](v ...uint32) HashRingOption[Node]

WithHashRingSortedKeysReplace sets sortedKeys in HashRing[Node]. The List of nodes to use in the Ketama consistent hash continuum

This simulates the structure of keys used in the Ketama consistent hash ring, which stores the virtual node HashKeys on the physical nodes. All nodes in the cluster are topped by virtual nodes. In principle, it is a brute-force search to find the first complete HashKey

For example, Node -> Key -> IterateKey -> HashKey {} -> 127.0.0.1:11311 -> 127.0.0.1:11311-0 -> 1234 {} -> 127.0.0.1:11311 -> 127.0.0.1:11311-160 -> 256 {} -> 127.0.0.1:11311 -> 127.0.0.1:11311-320 -> 692 []HashKey, Index for nodes binary search

func WithHashRingWeightByNode 

func WithHashRingWeightByNode[Node comparable](m map[Node]int) HashRingOption[Node]

WithHashRingWeightByNode appends weightByNode in HashRing[Node]. node weights for ketama, a map from InetSocketAddress to weight as Integer

func WithHashRingWeightByNodeReplace 

func WithHashRingWeightByNodeReplace[Node comparable](v map[Node]int) HashRingOption[Node]

WithHashRingWeightByNodeReplace sets weightByNode in HashRing[Node]. node weights for ketama, a map from InetSocketAddress to weight as Integer

type HashRingOptionFunc 

type HashRingOptionFunc[Node comparable] func(*HashRing[Node])

HashRingOptionFunc wraps a function that modifies HashRing[Node] into an implementation of the HashRingOption[Node comparable] interface.

type KetamaNodeKeyFormatter 

type KetamaNodeKeyFormatter[Node comparable] struct {
	// contains filtered or unexported fields
}

func NewKetamaNodeKeyFormatter 

func NewKetamaNodeKeyFormatter[Node comparable](format Format) *KetamaNodeKeyFormatter[Node]

func (KetamaNodeKeyFormatter[Node]) FormatNodeKey 

func (f KetamaNodeKeyFormatter[Node]) FormatNodeKey(node Node, repetition int) string

FormatNodeKey returns a uniquely identifying key, suitable for hashing by the HashRing algorithm.

@param node The Node to use to form the unique identifier @param repetition The repetition number for the particular node in question 

(0 is the first repetition)

@return The key that represents the specific repetition of the node

func (KetamaNodeKeyFormatter[Node]) GetFormat 

func (f KetamaNodeKeyFormatter[Node]) GetFormat() Format

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.