Documentation
¶
Overview ¶
Package hash provides a minimal-memory AnchorHash consistent-hash implementation for Go.
Index ¶
Constants ¶
const (
// Init is what 32 bits hash values should be initialized with.
Init = offset32
)
Variables ¶
This section is empty.
Functions ¶
func FastMod ¶
FastMod see "A fast alternative to the modulo reduction" (Lemire, 2016) https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
Types ¶
type Consistent ¶
type Consistent struct {
// We use an integer array A of size a to represent the Anchor.
//
// Each bucket b ∈ {0, 1, ..., a−1} is represented by A[b] that either equals 0 if b
// is a working bucket (i.e., A[b] = 0 if b ∈ W), or else equals the size of the working
// set just after its removal (i.e., A[b] = |Wb| if b ∈ R).
A []uint16
// K stores the successor for each removed bucket b (i.e. the bucket that replaced it in W).
K []uint16
// W always contains the current set of working blocks in their desired order.
W []uint16
// L stores the most recent location for each bucket within W.
L []uint16
// R saves removed blocks in a LIFO order for possible future bucket additions.
R []uint16
// N is the current length of W
N uint16
}
Consistent a minimal-memory AnchorHash implementation.
func InitConsistent ¶
func InitConsistent(blocks, used int) *Consistent
InitConsistent a new anchor with a given capacity and initial size.
INITANCHOR(a, w) A[b] ← 0 for b = 0, 1, ..., a−1 ◃ |Wb| ← 0 for b ∈ A R ← ∅ ◃ Empty stack N ← w ◃ Number of initially working blocks K[b] ← L[b] ← W[b] ← b for b = 0, 1, ..., a−1 for b = a−1 downto w do ◃ Remove initially unused blocks REMOVEBUCKET(b)
func (*Consistent) AddBlock ¶
func (c *Consistent) AddBlock() uint16
AddBlock add a block to the anchor.
ADDBLOCK()
b ← R.pop()
A[b] ← 0 ◃ W ← W ∪ {b}, delete Wb
L[W[N]] ← N
W[L[b]] ← K[b] ← b
N ← N + 1
return b
func (*Consistent) FindBlock ¶
func (c *Consistent) FindBlock(key uint64) uint16
FindBlock find the blocks which a hash-key is assigned to.
If the path for a given key contains any non-working blocks, the path (and in turn, the assigned bucket for the key) will be determined by the order in which the non-working blocks were removed. To maintain consistency in a distributed system, all agents must reach consensus on the ordering of changes to the working set. For more information, see Section III, Theorem 1 in the paper.
FINDBLOCK(k)
b ← hash(k) mod a
while A[b] > 0 do ◃ b is removed
h ← hb(k) ◃ hb(k) ≡ hash(k) mod A[b]
while A[h] ≥ A[b] do ◃ Wb[h] != h, b removed prior to h
h ← K[h] ◃ search for Wb[h]
b ← h
return b
func (*Consistent) FindPreviousBlock ¶
func (c *Consistent) FindPreviousBlock(key uint64) uint16
FindPreviousBlock find the block recently removed.
func (*Consistent) GetPath ¶
func (c *Consistent) GetPath(key uint64, pathBuffer []uint16) []uint16
GetPath get the path to the bucket which a hash-key is assigned to.
The returned path will contain all blocks traversed while searching for a working bucket. The final bucket in the path will be the assigned bucket for the given key.
Blocks will be appended to the provided buffer, though a different slice will be returned if the length of the path exceeds the capacity of the buffer.
If the path for a given key contains any non-working blocks, the path (and in turn, the assigned bucket for the key) will be determined by the order in which the non-working blocks were removed. To maintain consistency in a distributed system, all agents must reach consensus on the ordering of changes to the working set. For more information, see Section III, Theorem 1 in the paper.
GETPATH(k, P)
b ← hash(k) mod a
P.push(b)
while A[b] > 0 do ◃ b is removed
h ← hb(k) ◃ hb(k) ≡ hash(k) mod A[b]
P.push(h)
while A[h] ≥ A[b] do ◃ Wb[h] != h, b removed prior to h
h ← K[h] ◃ search for Wb[h]
P.push(h)
b ← h
return P
func (*Consistent) RemoveBlock ¶
func (c *Consistent) RemoveBlock(b uint16)
RemoveBlock remove a block from the anchor.
REMOVEBLOCK(b) R.push(b) N ← N − 1 A[b] ← N ◃ Wb ← W \ b, A[b] ← |Wb| W[L[b]] ← K[b] ← W[N] L[W[N]] ← L[b]
Source Files