hash

Documentation

Overview

Package hash contains various Knative specific hashing utilities.

• ChooseSubset is a consistent hashing/mapping function providing a consistent selection of N keys from M (N<=M) keys for a given target.
• BucketSet is a bucketer library which uses ChooseSubset under the the hood in order to implement consistent mapping between keys and set of buckets, identified by unique names. Compared to basic bucket implementation which just does hash%num_buckets, when the number of buckets change only a small subset of keys are supposed to migrate.

Index

• func ChooseSubset(from sets.Set[string], n int, target string) sets.Set[string]
• func GetAny(s sets.Set[string]) (string, bool)
• type Bucket
  • func (b *Bucket) Has(nn types.NamespacedName) bool
  • func (b *Bucket) Name() string
• type BucketSet
  • func NewBucketSet(bucketList sets.Set[string]) *BucketSet
  • func (bs *BucketSet) BucketList() []string
  • func (bs *BucketSet) Buckets() []reconciler.Bucket
  • func (bs *BucketSet) HasBucket(bkt string) bool
  • func (bs *BucketSet) Owner(key string) string
  • func (bs *BucketSet) Update(newB sets.Set[string])

Examples

• ChooseSubset (SelectMany)
• ChooseSubset (SelectOne)

Functions

func ChooseSubset

func ChooseSubset(from sets.Set[string], n int, target string) sets.Set[string]

ChooseSubset consistently chooses n items from `from`, using `target` as a seed value. ChooseSubset is an internal function and presumes sanitized inputs. TODO(vagababov): once initial impl is ready, think about how to cache the prepared data.

Example (SelectMany)

// This example shows how to do consistent bucket
// assignment using ChooseSubset.

tasks := sets.New[string]("task1", "task2", "task3", "task4", "task5")

ret := ChooseSubset(tasks, 2, "my-key1")
fmt.Println(sets.List(ret))

Output:

[task3 task4]

Example (SelectOne)

// This example shows how to do consistent bucket
// assignment using ChooseSubset.

tasks := sets.New[string]("task1", "task2", "task3")

ret := ChooseSubset(tasks, 1, "my-key1")
fmt.Println(ret.UnsortedList()[0])

ret = ChooseSubset(tasks, 1, "something/another-key")
fmt.Println(ret.UnsortedList()[0])

Output:

task3
task2

func GetAny

func GetAny(s sets.Set[string]) (string, bool)

Returns a single element from the set.

Types

type Bucket

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

Bucket implements reconciler.Bucket and wraps around BuketSet for bucketing functions.

func (*Bucket) Has

func (b *Bucket) Has(nn types.NamespacedName) bool

Has returns true if this bucket owns the key and implements reconciler.Bucket interface.

func (*Bucket) Name

func (b *Bucket) Name() string

Name implements Bucket.

type BucketSet

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

BucketSet answers to what bucket does key X belong in a consistent manner (consistent as in consistent hashing).

func NewBucketSet

func NewBucketSet(bucketList sets.Set[string]) *BucketSet

NewBucketSet creates a new bucket set with the given universe of bucket names.

func (*BucketSet) BucketList

func (bs *BucketSet) BucketList() []string

BucketList returns the bucket names of this BucketSet in sorted order.

func (*BucketSet) Buckets

func (bs *BucketSet) Buckets() []reconciler.Bucket

Buckets creates a new list of all possible Bucket based on this bucketset ordered by bucket name.

func (*BucketSet) HasBucket

func (bs *BucketSet) HasBucket(bkt string) bool

HasBucket returns true if this BucketSet has the given bucket name.

func (*BucketSet) Owner

func (bs *BucketSet) Owner(key string) string

Owner returns the owner of the key. Owner will cache the results for faster lookup.

func (*BucketSet) Update

func (bs *BucketSet) Update(newB sets.Set[string])

Update updates the universe of buckets.