hashring

package
v1.2.115 Latest Latest
Warning

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

 Go to latest Published: Feb 2, 2024 License: MIT Imports: 8 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)
	// FNV hashes are designed to be fast while maintaining a low collision rate.
	// The FNV speed allows one to quickly hash lots of data while maintaining a
	// reasonable collision rate.
	//
	// @see <a href="http://www.isthe.com/chongo/tech/comp/fnv/">fnv
	//      comparisons</a>
	// @see <a href="http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash">fnv at
	//      wikipedia</a>
	// 32-bit FNV1.
	FNV132Hash = HashFunc(fnv132Hash)
	// Variation of FNV.
	// 32-bit FNV1a.
	FNV1a32Hash = HashFunc(fnv1a32Hash)
	// 64-bit FNV1.
	FNV164Hash = HashFunc(fnv164Hash)
	// 64-bit FNV1a.
	FNV1a64Hash = HashFunc(fnv1a64Hash)
	// 128-bit FNV1.
	FNV1128Hash = HashFunc(fnv1128Hash)
	// 128-bit FNV1a.
	FNV1a128Hash = HashFunc(fnv1a128Hash)
	// 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 EmptyKetamaNodeLocatorOption 

type EmptyKetamaNodeLocatorOption struct{}

EmptyKetamaNodeLocatorOption 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

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
	//
	// <p>
	// 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:
	// <p>
	//
	// <p>
	// <code>myhost/10.0.2.1-0</code>
	// </p>
	//
	// <p>
	// for the second repetition
	// </p>
	//
	// <p>
	// <code>myhost/10.0.2.1-1</code>
	// </p>
	//
	// <p>
	// for a server where reverse lookups are failing the returned keys may look
	// like
	// </p>
	//
	// <p>
	// <code>/10.0.2.1-0</code> and <code>/10.0.2.1-1</code>
	// </p>
	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 {
	// Compute the hash for the given key.
	// @return a positive integer hash
	Hash(k string) []uint32
}

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 func(*NodeLocator)

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

type Node 

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

{} -> 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.

func (*NodeLocator) ApplyOptions 

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

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)

Remove removes nodes from the consistent hash cycle...

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 WithNumberNodeRepetitions 

func WithNumberNodeRepetitions(n int) NodeLocatorOption

func WithWeights 

func WithWeights(weights map[Node]int) NodeLocatorOption

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)

Remove 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.