Documentation
¶
Overview ¶
Package shard implements a set of consistent hashing algorithms to determine ownership of a key within a cluster.
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
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.
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.
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
)
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.
Source Files