shard

Documentation

Overview

Package shard implements a set of consistent hashing algorithms to determine ownership of a key within a cluster.

Example

package main

import (
	"fmt"

	"github.com/grafana/ckit/peer"
	"github.com/grafana/ckit/shard"
)

func main() {
	// We can create a sharder to determine which Peers in a cluster are
	// responsible for certain keys.
	//
	// Here we use the Ring hash.
	ring := shard.Ring(256)

	// A ring must be given the set of Peers to consider for hashing. A ring can
	// be automatically updated as the cluster changes by providing the sharder
	// in ckit.Config.
	//
	// For this example, we'll manually set the peers.
	ring.SetPeers([]peer.Peer{
		// The State of a Peer determines whether it can be used for hashing.
		//
		// Viewer nodes are never used for hashing; they're meant to be view-only
		// watchers of the cluster state.
		//
		// Participant nodes are used for hashing and can handle read or write
		// operations.
		//
		// Terminating nodes are Participant nodes that are shutting down; they can
		// no longer handle write operations, but they are still valid for read
		// operations.

		{Name: "viewer-a", State: peer.StateViewer},
		{Name: "viewer-b", State: peer.StateViewer},
		{Name: "viewer-c", State: peer.StateViewer},
		{Name: "node-a", State: peer.StateParticipant},
		{Name: "node-b", State: peer.StateParticipant},
		{Name: "node-c", State: peer.StateTerminating},
	})

	// Once SetPeers is called, you can determine the owner for some key. We'll
	// convert the "example-key" string into a Key and see which node should be
	// used for storing data for that key. This will always return the same
	// result for the same set of input peers.
	//
	// You can request any number of owners for a key, as long as that number of
	// nodes are eligible for the provided operation. We have 2 participant nodes,
	// so we can request up to 2 owners for OpReadWrite.
	owners, err := ring.Lookup(shard.StringKey("example-key"), 1, shard.OpReadWrite)
	if err != nil {
		panic(err)
	}

	fmt.Printf("Owner of example-key: %s\n", owners[0].Name)

}

Output:

Owner of example-key: node-b

Index

• type Key
  • func StringKey(s string) Key
• type KeyBuilder
  • func NewKeyBuilder() *KeyBuilder
  • func (kb *KeyBuilder) Key() Key
  • func (kb *KeyBuilder) Reset()
  • func (kb *KeyBuilder) Write(b []byte) (n int, err error)
• type Op
  • func (ht Op) String() string
• type Sharder
  • func Multiprobe() Sharder
  • func Rendezvous() Sharder
  • func Ring(numTokens int) Sharder

Examples

• Package

Types

type Key

type Key uint64

A Key is used to identify the set of owners for some given objects. Keys may be constructed from a string by calling StringKey or by writing data through a KeyBuilder.

func StringKey

func StringKey(s string) Key

StringKey generates a Key directly from a string. It is equivalent to writing the input string to a new KeyBuilder.

type KeyBuilder

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

KeyBuilder generate Keys for performing hash lookup. To generate a Key, first write to the KeyBuilder, then call Key. The KeyBuilder can be re-used afterwards by calling Reset. KeyBuilder can not be used concurrently.

KeyBuilder implements io.Writer.

func NewKeyBuilder

func NewKeyBuilder() *KeyBuilder

NewKeyBuilder returns a new KeyBuilder that can generate keys.

func (*KeyBuilder) Key

func (kb *KeyBuilder) Key() Key

Key computes the key from kb's current state.

func (*KeyBuilder) Reset

func (kb *KeyBuilder) Reset()

Reset resets kb's state.

func (*KeyBuilder) Write

func (kb *KeyBuilder) Write(b []byte) (n int, err error)

Write appends b to kb's state. Write always returns len(b), nil.

type Op

type Op uint8

Op is used to signify how a hash is intended to be used.

const (
	// OpRead is used for read-only lookups. Only nodes in the Participant
	// or Terminating state are considered.
	OpRead Op = iota
	// OpReadWrite is used for read or write lookups. Only nodes in the
	// Participant state are considered.
	OpReadWrite
)

func (Op) String

func (ht Op) String() string

String returns a string representation of the Op.

type Sharder

type Sharder interface {
	// Lookup returns numOwners Peers for the provided key. The provided op
	// is used to determine which peers may be considered potential owners.
	//
	// An error will be returned if the type of eligible peers for the provided
	// op is less than numOwners.
	Lookup(key Key, numOwners int, op Op) ([]peer.Peer, error)

	// Peers gets the current set of non-viewer peers used for sharding.
	Peers() []peer.Peer

	// SetPeers updates the set of peers used for sharding. Peers will be ignored
	// if they are a viewer.
	SetPeers(ps []peer.Peer)
}

A Sharder can lookup the owner for a specific key.

func Multiprobe

func Multiprobe() Sharder

Multiprobe implements a multi-probe sharder: https://arxiv.org/abs/1505.00062

Multiprobe is optimized for a median peak-to-average load ratio of 1.05. It performs a lookup in O(K * log N) time, where K is 21.

func Rendezvous

func Rendezvous() Sharder

Rendezvous returns a rendezvous sharder (HRW, Highest Random Weight).

Rendezvous is optimized for excellent load distribution, but has a runtime complexity of O(N).

func Ring

func Ring(numTokens int) Sharder

Ring implements a ring sharder. numTokens determines how many tokens each node should have. Tokens are mapped to the unit circle, and then ownership of a key is determined by finding the next token on the unit circle. If two nodes have the same token, the node that lexicographically comes first will be used as the first owner.

Ring is extremely fast, running in O(log N) time, but increases in memory usage as numTokens increases. Low values of numTokens will cause poor distribution; 256 or 512 is a good starting point.