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: 9 Imported by: 1

Documentation

Overview

Package hashring provides a consistent hashing function.

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 EmptyNodeLocatorOption added in v1.2.121 

type EmptyNodeLocatorOption struct{}

EmptyNodeLocatorOption 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" "/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 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 KetamaNodeKeyFormatter 

type KetamaNodeKeyFormatter struct {
	// contains filtered or unexported fields
}

func NewKetamaNodeKeyFormatter 

func NewKetamaNodeKeyFormatter(format Format) *KetamaNodeKeyFormatter

func (KetamaNodeKeyFormatter) GetFormat 

func (f KetamaNodeKeyFormatter) GetFormat() Format

type KetamaNodeLocatorOptionFunc 

type KetamaNodeLocatorOptionFunc = NodeLocatorOptionFunc

type Node 

type Node interface {
	// Stringer returns the SocketAddress of the server to which this node is connected.
	fmt.Stringer
}

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

->     IterateKey    -> HashKey
->     IterateKey    -> HashKey

type NodeLocator 

type NodeLocator struct {
	// contains filtered or unexported fields
}

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

func New 

func New(opts ...NodeLocatorOption) *NodeLocator

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

Example 
package main

import (
	"fmt"
	"log"

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

func main() {
	c := hashring.New()
	c.AddNodes(hashring.StringNode("NodeA"))
	c.AddNodes(hashring.StringNode("NodeB"))
	c.AddNodes(hashring.StringNode("NodeC"))
	users := []string{"Alice", "Bob  ", "Eve  ", "Carol", "Dave "}
	for _, u := range users {
		server, has := c.Get(u)
		if !has {
			log.Fatal()
		}
		fmt.Printf("%s => %s\n", u, server)
	}
}

Output:

Alice => NodeB
Bob   => NodeA
Eve   => NodeA
Carol => NodeC
Dave  => NodeA

func (*NodeLocator) AddNodes 

func (c *NodeLocator) AddNodes(nodes ...Node)

AddNodes inserts nodes into the consistent hash cycle.

Example 
package main

import (
	"fmt"
	"log"

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

func main() {
	c := hashring.New()
	c.AddNodes(hashring.StringNode("NodeA"))
	c.AddNodes(hashring.StringNode("NodeB"))
	c.AddNodes(hashring.StringNode("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(hashring.StringNode("NodeD"))
	c.AddNodes(hashring.StringNode("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 (*NodeLocator) ApplyOptions 

func (o *NodeLocator) ApplyOptions(options ...NodeLocatorOption) *NodeLocator

ApplyOptions call apply() for all options one by one

func (*NodeLocator) Get 

func (c *NodeLocator) Get(name string) (Node, bool)

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

func (*NodeLocator) GetAllNodes 

func (c *NodeLocator) GetAllNodes() []Node

GetAllNodes returns all available nodes

func (*NodeLocator) GetMaxHashKey 

func (c *NodeLocator) GetMaxHashKey() (uint32, error)

GetMaxHashKey returns the last available node's HashKey that is, Maximum HashKey in the Hash Cycle

func (*NodeLocator) GetN 

func (c *NodeLocator) GetN(name string, n int) ([]Node, bool)

GetN returns the N closest distinct elements to the name input in the nodes.

func (*NodeLocator) GetPrimaryNode 

func (c *NodeLocator) GetPrimaryNode(name string) (Node, bool)

GetPrimaryNode returns the first available node for a name, such as “127.0.0.1:11311-0” for "Alice"

func (*NodeLocator) GetTwo 

func (c *NodeLocator) GetTwo(name string) (Node, Node, bool)

GetTwo returns the two closest distinct elements to the name input in the nodes.

func (*NodeLocator) RemoveAllNodes 

func (c *NodeLocator) RemoveAllNodes()

RemoveAllNodes removes all nodes in the continuum....

func (*NodeLocator) RemoveNodes 

func (c *NodeLocator) RemoveNodes(nodes ...Node)

RemoveNodes removes nodes from the consistent hash cycle...

Example 
package main

import (
	"fmt"
	"log"

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

func main() {
	c := hashring.New()
	c.AddNodes(hashring.StringNode("NodeA"))
	c.AddNodes(hashring.StringNode("NodeB"))
	c.AddNodes(hashring.StringNode("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(hashring.StringNode("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 (*NodeLocator) SetNodes 

func (c *NodeLocator) SetNodes(nodes ...Node)

SetNodes setups the NodeLocator 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 NodeLocator to use in its continuum

type NodeLocatorOption 

type NodeLocatorOption interface {
	// contains filtered or unexported methods
}

A NodeLocatorOption sets options.

func WithFormatter 

func WithFormatter(formatter *KetamaNodeKeyFormatter) NodeLocatorOption

func WithHashAlg 

func WithHashAlg(hashAlg HashAlgorithm) NodeLocatorOption

func WithNodeLocator added in v1.2.121 

func WithNodeLocator(v NodeLocator) NodeLocatorOption

WithNodeLocator sets NodeLocator.

func WithNodeLocatorAllNodes added in v1.2.121 

func WithNodeLocatorAllNodes(m map[Node]struct{}) NodeLocatorOption

WithNodeLocatorAllNodes appends allNodes in NodeLocator. <Node>

func WithNodeLocatorAllNodesReplace added in v1.2.121 

func WithNodeLocatorAllNodesReplace(v map[Node]struct{}) NodeLocatorOption

WithNodeLocatorAllNodesReplace sets allNodes in NodeLocator. <Node>

func WithNodeLocatorHashAlg added in v1.2.121 

func WithNodeLocatorHashAlg(v HashAlgorithm) NodeLocatorOption

WithNodeLocatorHashAlg sets hashAlg in NodeLocator. The hash algorithm to use when choosing a node in the Ketama consistent hash continuum

func WithNodeLocatorIsWeighted added in v1.2.121 

func WithNodeLocatorIsWeighted(v bool) NodeLocatorOption

WithNodeLocatorIsWeighted sets isWeighted in NodeLocator.

func WithNodeLocatorNodeByKey added in v1.2.121 

func WithNodeLocatorNodeByKey(m map[uint32]Node) NodeLocatorOption

WithNodeLocatorNodeByKey appends nodeByKey in NodeLocator. <HashKey,Node>

func WithNodeLocatorNodeByKeyReplace added in v1.2.121 

func WithNodeLocatorNodeByKeyReplace(v map[uint32]Node) NodeLocatorOption

WithNodeLocatorNodeByKeyReplace sets nodeByKey in NodeLocator. <HashKey,Node>

func WithNodeLocatorNodeKeyFormatter added in v1.2.121 

func WithNodeLocatorNodeKeyFormatter(v *KetamaNodeKeyFormatter) NodeLocatorOption

WithNodeLocatorNodeKeyFormatter sets nodeKeyFormatter in NodeLocator. the format used to name the nodes in Ketama, either SpyMemcached or LibMemcached

func WithNodeLocatorNumReps added in v1.2.121 

func WithNodeLocatorNumReps(v int) NodeLocatorOption

WithNodeLocatorNumReps sets numReps in NodeLocator. the number of discrete hashes that should be defined for each node in the continuum.

func WithNodeLocatorSortedKeys added in v1.2.121 

func WithNodeLocatorSortedKeys(v ...uint32) NodeLocatorOption

WithNodeLocatorSortedKeys appends sortedKeys in NodeLocator. 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 WithNodeLocatorSortedKeysReplace added in v1.2.121 

func WithNodeLocatorSortedKeysReplace(v ...uint32) NodeLocatorOption

WithNodeLocatorSortedKeysReplace sets sortedKeys in NodeLocator. 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 WithNodeLocatorWeightByNode added in v1.2.121 

func WithNodeLocatorWeightByNode(m map[Node]int) NodeLocatorOption

WithNodeLocatorWeightByNode appends weightByNode in NodeLocator. node weights for ketama, a map from InetSocketAddress to weight as Integer

func WithNodeLocatorWeightByNodeReplace added in v1.2.121 

func WithNodeLocatorWeightByNodeReplace(v map[Node]int) NodeLocatorOption

WithNodeLocatorWeightByNodeReplace sets weightByNode in NodeLocator. node weights for ketama, a map from InetSocketAddress to weight as Integer

func WithNumberNodeRepetitions 

func WithNumberNodeRepetitions(n int) NodeLocatorOption

func WithWeights 

func WithWeights(weights map[Node]int) NodeLocatorOption

type NodeLocatorOptionFunc added in v1.2.121 

type NodeLocatorOptionFunc func(*NodeLocator)

NodeLocatorOptionFunc wraps a function that modifies NodeLocator into an implementation of the NodeLocatorOption interface.

type StringNode 

type StringNode string

func (StringNode) String 

func (n StringNode) String() string

type StringNodeLocator 

type StringNodeLocator struct {
	// contains filtered or unexported fields
}

StringNodeLocator derived from NodeLocator, but explicit specialization with string

func NewStringNodeLocator 

func NewStringNodeLocator(opts ...NodeLocatorOption) *StringNodeLocator

func (*StringNodeLocator) AddNodes 

func (c *StringNodeLocator) AddNodes(nodes ...string)

AddNodes inserts nodes into the consistent hash cycle.

func (*StringNodeLocator) Get 

func (c *StringNodeLocator) Get(name string) (string, bool)

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

func (*StringNodeLocator) GetAllNodes 

func (c *StringNodeLocator) GetAllNodes() []string

GetAllNodes returns all available nodes

func (*StringNodeLocator) GetMaxHashKey 

func (c *StringNodeLocator) GetMaxHashKey() (uint32, error)

GetMaxHashKey returns the last available node's HashKey that is, Maximum HashKey in the Hash Cycle

func (*StringNodeLocator) GetN 

func (c *StringNodeLocator) GetN(name string, n int) ([]string, bool)

GetN returns the N closest distinct elements to the name input in the nodes.

func (*StringNodeLocator) GetPrimaryNode 

func (c *StringNodeLocator) GetPrimaryNode(name string) (string, bool)

GetPrimaryNode returns the first available node for a name, such as “127.0.0.1:11311-0” for "Alice"

func (*StringNodeLocator) GetTwo 

func (c *StringNodeLocator) GetTwo(name string) (string, string, bool)

GetTwo returns the two closest distinct elements to the name input in the nodes.

func (*StringNodeLocator) RemoveAllNodes 

func (c *StringNodeLocator) RemoveAllNodes()

RemoveAllNodes removes all nodes in the continuum....

func (*StringNodeLocator) RemoveNodes 

func (c *StringNodeLocator) RemoveNodes(nodes ...string)

RemoveNodes removes nodes from the consistent hash cycle...

func (*StringNodeLocator) SetNodes 

func (c *StringNodeLocator) SetNodes(nodes ...string)

SetNodes setups the NodeLocator 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 NodeLocator to use in its continuum

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.