hashring

package
v1.2.20 Latest Latest
Warning

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

Go to latest
Published: May 12, 2022 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

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL