README
¶
package anchor
package anchor provides a minimal-memory AnchorHash consistent-hash implementation for Go.
import "github.com/wdamron/go-anchorhash"
More Info
Benchmarks
-
Go 1.12.1
-
2017 Macbook Pro; noisy, with a number of applications running
-
2.9 GHz Intel Core i7
-
16 GB 2133 MHz LPDDR3
-
Capacity = 10
NewCompactAnchor(10, 10):BenchmarkGetBucket_10_10 200000000 5.81 ns/opNewCompactAnchor(10, 9):BenchmarkGetBucket_9_10 200000000 6.71 ns/opNewCompactAnchor(10, 5):BenchmarkGetBucket_5_10 100000000 10.8 ns/op
-
Capacity = 1,000,000
NewAnchor(1000000, 1000000):BenchmarkGetBucket_1m_1m 200000000 7.47 ns/opNewAnchor(1000000, 900000):BenchmarkGetBucket_900k_1m 200000000 9.26 ns/opNewAnchor(1000000, 500000):BenchmarkGetBucket_500k_1m 100000000 17.6 ns/op
Documentation
¶
Overview ¶
package anchor provides a minimal-memory AnchorHash consistent-hash implementation for Go.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Anchor ¶
type Anchor 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 []uint32
// K stores the successor for each removed bucket b (i.e. the bucket that replaced it in W).
K []uint32
// W always contains the current set of working buckets in their desired order.
W []uint32
// L stores the most recent location for each bucket within W.
L []uint32
// R saves removed buckets in a LIFO order for possible future bucket additions.
R []uint32
// N is the current length of W
N uint32
}
Minimal-memory AnchorHash implementation.
func NewAnchor ¶
Create 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 buckets K[b] ← L[b] ← W[b] ← b for b = 0, 1, ..., a−1 for b = a−1 downto w do ◃ Remove initially unused buckets REMOVEBUCKET(b)
func (*Anchor) AddBucket ¶
Add a bucket to the anchor.
ADDBUCKET()
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 (*Anchor) GetBucket ¶
Get the bucket which a hash-key is assigned to.
If the path for a given key contains any non-working buckets, the path (and in turn, the assigned bucket for the key) will be determined by the order in which the non-working buckets 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.
GETBUCKET(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 (*Anchor) GetPath ¶
Get the path to the bucket which a hash-key is assigned to.
The returned path will contain all buckets traversed while searching for a working bucket. The final bucket in the path will be the assigned bucket for the given key.
Buckets 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 buckets, the path (and in turn, the assigned bucket for the key) will be determined by the order in which the non-working buckets 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 (*Anchor) RemoveBucket ¶
Remove a bucket from the anchor.
REMOVEBUCKET(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]
type CompactAnchor ¶
type CompactAnchor 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 buckets in their desired order.
W []uint16
// L stores the most recent location for each bucket within W.
L []uint16
// R saves removed buckets in a LIFO order for possible future bucket additions.
R []uint16
// N is the current length of W
N uint16
}
Compact, minimal-memory AnchorHash implementation.
Buckets will be stored as unsigned 16-bit integers, so the maximum size of the working set will be limited to 65,536 buckets. This implementation offers improved cache-locality relative to Anchor.
func NewCompactAnchor ¶
func NewCompactAnchor(buckets, used uint16) *CompactAnchor
Create 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 buckets K[b] ← L[b] ← W[b] ← b for b = 0, 1, ..., a−1 for b = a−1 downto w do ◃ Remove initially unused buckets REMOVEBUCKET(b)
func (*CompactAnchor) AddBucket ¶
func (a *CompactAnchor) AddBucket() uint16
Add a bucket to the anchor.
ADDBUCKET()
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 (*CompactAnchor) GetBucket ¶
func (a *CompactAnchor) GetBucket(key uint64) uint16
Get the bucket which a hash-key is assigned to.
If the path for a given key contains any non-working buckets, the path (and in turn, the assigned bucket for the key) will be determined by the order in which the non-working buckets 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.
GETBUCKET(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 (*CompactAnchor) GetPath ¶
func (a *CompactAnchor) GetPath(key uint64, pathBuffer []uint16) []uint16
Get the path to the bucket which a hash-key is assigned to.
The returned path will contain all buckets traversed while searching for a working bucket. The final bucket in the path will be the assigned bucket for the given key.
Buckets 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 buckets, the path (and in turn, the assigned bucket for the key) will be determined by the order in which the non-working buckets 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 (*CompactAnchor) RemoveBucket ¶
func (a *CompactAnchor) RemoveBucket(b uint16)
Remove a bucket from the anchor.
REMOVEBUCKET(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