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
- type RendezvousHashNode
- type RendezvousNodesByScore
- type UIntToFloat
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BigIntToFloat64 ¶
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 UInt64ToFloat64 ¶
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 ¶
HashFactory is a function object for Hash.New() constructor.
type NodeKeysTable ¶
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) 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.
Source Files