hashing

Documentation

Index

• func Fnv1a64(data []byte) uint64
• func Jump(key uint64, buckets int) int
• func XorShift(i uint64) uint64
• type CarbonHashRing
  • func NewCarbonHashRing() *CarbonHashRing
  • func (t *CarbonHashRing) AddNode(node Node)
  • func (t *CarbonHashRing) BucketsPerNode() map[string]int
  • func (t *CarbonHashRing) GetNode(key string) Node
  • func (t *CarbonHashRing) GetNodes(key string) []Node
  • func (t *CarbonHashRing) Len() int
  • func (t *CarbonHashRing) Nodes() []Node
  • func (t *CarbonHashRing) RemoveNode(node Node)
  • func (t *CarbonHashRing) Replicas() int
  • func (t *CarbonHashRing) SetReplicas(r int)
  • func (t *CarbonHashRing) String() string
• type HashRing
• type JumpHashRing
  • func NewJumpHashRing(replicas int) *JumpHashRing
  • func (chr *JumpHashRing) AddNode(node Node)
  • func (chr *JumpHashRing) GetNode(key string) Node
  • func (chr *JumpHashRing) GetNodes(key string) []Node
  • func (chr *JumpHashRing) Len() int
  • func (chr *JumpHashRing) Nodes() []Node
  • func (chr *JumpHashRing) RemoveNode(node Node)
  • func (chr *JumpHashRing) Replicas() int
  • func (chr *JumpHashRing) String() string
• type Node
  • func NewNode(server, instance string) (n Node)
  • func (t Node) KeyValue() string
  • func (t Node) String() string
• type RingEntry

Functions

func Fnv1a64

func Fnv1a64(data []byte) uint64

Fnv1a64 returns a 64 bit hash of the given data using the FNV-1a hashing algorithm. Golang's libraries natively support this hashing, but I need something simpler.

func Jump

func Jump(key uint64, buckets int) int

Jump returns a bucket index less that buckets using Google's Jump consistent hashing algorithm: http://arxiv.org/pdf/1406.2294.pdf Note that the return is int for convienance and will not be larger than an int32.

func XorShift

func XorShift(i uint64) uint64

XorShift generates a predictable random-ish hash from the given integer. This method is also used by carbon-c-relay for replication in a Jump hash ring. http://vigna.di.unimi.it/ftp/papers/xorshift.pdf

Types

type CarbonHashRing

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

CarbonHashRing represents Graphite's carbon-cache.py hashing algorithm.

func NewCarbonHashRing

func NewCarbonHashRing() *CarbonHashRing

NewCarbonHashRing sets up a new CarbonHashRing and returns it.

func (*CarbonHashRing) AddNode

func (t *CarbonHashRing) AddNode(node Node)

func (*CarbonHashRing) BucketsPerNode

func (t *CarbonHashRing) BucketsPerNode() map[string]int

func (*CarbonHashRing) GetNode

func (t *CarbonHashRing) GetNode(key string) Node

func (*CarbonHashRing) GetNodes

func (t *CarbonHashRing) GetNodes(key string) []Node

func (*CarbonHashRing) Len

func (t *CarbonHashRing) Len() int

Len return the number of buckets or nodes in the hash ring.

func (*CarbonHashRing) Nodes

func (t *CarbonHashRing) Nodes() []Node

Nodes returns the nodes in the carbon hash ring

func (*CarbonHashRing) RemoveNode

func (t *CarbonHashRing) RemoveNode(node Node)

func (*CarbonHashRing) Replicas

func (t *CarbonHashRing) Replicas() int

func (*CarbonHashRing) SetReplicas

func (t *CarbonHashRing) SetReplicas(r int)

func (*CarbonHashRing) String

func (t *CarbonHashRing) String() string

type HashRing

type HashRing interface {

	// Len returns the number of Nodes or servers in the hash ring.
	Len() int

	// GetNode returns a Node after using the hashing algorithm on the
	// provided key.
	GetNode(key string) Node

	// GetNodes is similar to GetNode but returns a slice of Nodes who's
	// length is the smaller of the number of nodes in the ring or
	// the replication factor.
	GetNodes(key string) []Node

	// AddNode adds a new Node to the hash ring.  This should not be used
	// after you have begun calling GetNode or GetNodes.
	AddNode(node Node)

	// Replicas returns the number of replicas the hash ring is configured
	// for.  This is the number of shards that each key should be stored
	// on.
	Replicas() int

	// Nodes returns a slice of Node detailing all the servers in the hash
	// ring.
	Nodes() []Node
}

HashRing is an interface that allows us to plug in multiple hash ring implementations.

type JumpHashRing

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

JumpHashRing stores the hashring information.

func NewJumpHashRing

func NewJumpHashRing(replicas int) *JumpHashRing

NewJumpHashRing creates a new hashring configured with the given replicas such that the number of solutions matches the number of replicas.

func (*JumpHashRing) AddNode

func (chr *JumpHashRing) AddNode(node Node)

AddNode adds a Node to the Jump Hash Ring. Jump only operates on the number of buckets so we assume that AddNode will not be used to attempt to insert a Node in the middle of the ring as that will affect the mapping of buckets to server addresses. This uses the instance value to define an order of the slice of Nodes. Empty ("") instance values will be appended to the end of the slice.

func (*JumpHashRing) GetNode

func (chr *JumpHashRing) GetNode(key string) Node

GetNode returns a bucket for the given key using Google's Jump Hash algorithm.

func (*JumpHashRing) GetNodes

func (chr *JumpHashRing) GetNodes(key string) []Node

GetNodes returns a slice of Node objects one for each replica where the object is stored.

func (*JumpHashRing) Len

func (chr *JumpHashRing) Len() int

Len returns the number of buckets in the hash ring.

func (*JumpHashRing) Nodes

func (chr *JumpHashRing) Nodes() []Node

Nodes returns the Nodes in the hashring

func (*JumpHashRing) RemoveNode

func (chr *JumpHashRing) RemoveNode(node Node)

RemoveNode removes the last node in the ring regardless of the value of the given node which is here to implement our interface.

func (*JumpHashRing) Replicas

func (chr *JumpHashRing) Replicas() int

Replicas returns the number of replicas the hash ring is configured for.

func (*JumpHashRing) String

func (chr *JumpHashRing) String() string

String displays the buckets in the hashring and their index numbers.

type Node

type Node struct {
	Server   string
	Instance string
}

Node is a server and instance value used in the hash ring. A key is mapped to one or more of the configured Node structs in the hash ring.

func NewNode

func NewNode(server, instance string) (n Node)

NewNode returns a node object setup with the given server string and instance string. None or empty instances should be represented by ""

func (Node) KeyValue

func (t Node) KeyValue() string

Node.KeyValue generates the string representation used in the hash ring just as Graphite's Python code does. Useful only for carbon style hashrings.

func (Node) String

func (t Node) String() string

Node.String returns a string representation of the Node struct

type RingEntry

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

RingEntry is used to record the position of Nodes in the ring. Not used in all implementations.