hrw

Documentation

Overview

Copyright (c) 2016-2019 Uber Technologies, Inc.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Copyright (c) 2016-2019 Uber Technologies, Inc.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Index

• func BigIntToFloat64(bytesUInt []byte, maxValue []byte, hasher hash.Hash) float64
• func HashKeyFixture(numKeys int, hashFactory HashFactory) []string
• func Murmur3Hash() hash.Hash
• func UInt64ToFloat64(bytesUInt []byte, maxValue []byte, hasher hash.Hash) float64
• type HashFactory
• type NodeKeysTable
• type RendezvousHash
  • func NewRendezvousHash(hashFactory HashFactory, scoreFunc UIntToFloat) *RendezvousHash
  • func RendezvousHashFixture(numKeys int, hashFactory HashFactory, scoreFunc UIntToFloat, weights ...int) (*RendezvousHash, map[string]map[string]struct{})
  • func (rh *RendezvousHash) AddNode(seed string, weight int)
  • func (rh *RendezvousHash) GetNode(name string) (*RendezvousHashNode, int)
  • func (rh *RendezvousHash) GetOrderedNodes(key string, n int) []*RendezvousHashNode
  • func (rh *RendezvousHash) RemoveNode(name string)
• type RendezvousHashNode
  • func (rhn *RendezvousHashNode) Score(key string) float64
• type RendezvousNodesByScore
  • func (a RendezvousNodesByScore) Len() int
  • func (a RendezvousNodesByScore) Less(i, j int) bool
  • func (a RendezvousNodesByScore) Swap(i, j int)
• type UIntToFloat

Functions

func BigIntToFloat64

func BigIntToFloat64(bytesUInt []byte, maxValue []byte, hasher hash.Hash) float64

BigIntToFloat64 converts BigInt to float64.

func HashKeyFixture

func HashKeyFixture(numKeys int, hashFactory HashFactory) []string

HashKeyFixture generate #numkeys random keys according to a hash function

func Murmur3Hash

func Murmur3Hash() hash.Hash

Murmur3Hash is a murmur3 HashFactory.

func UInt64ToFloat64

func UInt64ToFloat64(bytesUInt []byte, maxValue []byte, hasher hash.Hash) float64

UInt64ToFloat64 Converts a uniformly random 64-bit integer to "uniformly" random floating point number on interval [0, 1) The approach is heavily based on this material https://crypto.stackexchange.com/questions/31657/uniformly-distributed-secure-floating-point-numbers-in-0-1 and this https://en.wikipedia.org/wiki/Rendezvous_hashing

Types

type HashFactory

type HashFactory func() hash.Hash

HashFactory is a function object for Hash.New() constructor.

type NodeKeysTable

type NodeKeysTable map[string]map[string]struct{}

NodeKeysTable is a Node to keys map utility type

type RendezvousHash

type RendezvousHash struct {
	Hash         HashFactory           // hash function
	ScoreFunc    UIntToFloat           // conversion function from generated hash to float64
	Nodes        []*RendezvousHashNode // all nodes
	MaxHashValue []byte
}

RendezvousHash represents a Rendezvous Hashing schema. It does not make any assumption about concurrency model so synchronizing access to it is a caller's responsibility.

func NewRendezvousHash

func NewRendezvousHash(hashFactory HashFactory, scoreFunc UIntToFloat) *RendezvousHash

NewRendezvousHash constructs and prepopulates a RendezvousHash object.

func RendezvousHashFixture

func RendezvousHashFixture(numKeys int, hashFactory HashFactory, scoreFunc UIntToFloat, weights ...int) (*RendezvousHash, map[string]map[string]struct{})

RendezvousHashFixture creates a weigthed rendezvous hashing object with specified #numKey of keys, a hash function (we use sha256.New primarely for testing) and the list of weights which define nodes in rendezvous hashing schema and assign weights to them in their natural order. The nodes will be also initialized with seed names equal to their corresponding indices in the array, so for RendezvousHashFixture(10, sha256.New, 100, 200, 300) there will be a RendezvousHash object created with 3 nodes "0": 100, "1":200, "2":300 The fixture will return RendezvousHash object and the node key buckets table

func (*RendezvousHash) AddNode

func (rh *RendezvousHash) AddNode(seed string, weight int)

AddNode adds a node to a hashing ring.

func (*RendezvousHash) GetNode

func (rh *RendezvousHash) GetNode(name string) (*RendezvousHashNode, int)

GetNode gets a node from a hashing ring and its index in array.

func (*RendezvousHash) GetOrderedNodes

func (rh *RendezvousHash) GetOrderedNodes(key string, n int) []*RendezvousHashNode

GetOrderedNodes gets an ordered set of N nodes for a key where score(Node1) > score(N2) > ... score(NodeN). Number of returned nodes = min(N, len(nodes)).

func (*RendezvousHash) RemoveNode

func (rh *RendezvousHash) RemoveNode(name string)

RemoveNode removes a node from a hashing ring.

type RendezvousHashNode

type RendezvousHashNode struct {
	RHash  *RendezvousHash // parent hash structure with all the configuration
	Label  string          // some string ientifying a unique node label
	Weight int             // node weight, usually denotes node's capacity
}

RendezvousHashNode represents a weighted node in a hashing schema.

func (*RendezvousHashNode) Score

func (rhn *RendezvousHashNode) Score(key string) float64

Score computes score of a key for this node in accordance to Weighted Rendezvous Hash. It's using big golang float key as hexidemical encoding of a byte array.

type RendezvousNodesByScore

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

RendezvousNodesByScore is a predicat that supports sorting by score(key).

func (RendezvousNodesByScore) Len

func (a RendezvousNodesByScore) Len() int

Len return length.

func (RendezvousNodesByScore) Less

func (a RendezvousNodesByScore) Less(i, j int) bool

Less is a predicate '<' for a set.

func (RendezvousNodesByScore) Swap

func (a RendezvousNodesByScore) Swap(i, j int)

Swap swaps two elements.

type UIntToFloat

type UIntToFloat func(bytesUInt []byte, maxValue []byte, hasher hash.Hash) float64

UIntToFloat is a conversion function from uint64 to float64. Int could be potentially very big integer, like 256 bits long.