rendezvous

Documentation

Overview

Package rendezvous uses rendezvous hashing to help multiple controller replicas agree on which replica should handle an item. The assignment is not atomic, so the controllers' actions need to be safe even if multiple replicas attempt to process the same item simultaneously. However, in the steady state, where all replicas agree on the set of all healthy replicas.

Index

• Variables
• func Hash(item string, replicas []string) string
• type Hasher
  • func New(kc kubernetes.Interface, namespace, applicationName, replicaName string, ...) *Hasher
  • func (h *Hasher) AssignedToThisReplica(ctx context.Context, item string) bool
  • func (h *Hasher) Run(ctx context.Context)

Variables

var ErrNotAssigned = errors.New("item not assigned to this replica")

Functions

func Hash

func Hash(item string, replicas []string) string

Types

type Hasher

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

Hasher is a rendezvous hashing implementation built on top of Kubernetes leases.

Use Hasher when:

* You have multiple replicas of your application.

* You want to partition work items efficiently between them, minimizing redundant work.

* You can tolerate multiple replicas working on the same item at the same time.

As opposed to leader election, rendezvous hashing lets us spread the controller's work across all live replicas of the controller. As controller replicas spin up and down, work items will be gracefully rebalanced among the live replicas. In general, if there are m items, and n replicas running, m/n items will be rebalanced to the remaining live replicas, with most items remaining at the same replica.

Internally, Hasher writes a heartbeat to a specific Lease object, and scans for other Lease objects created by other replicas of your application. If the lease has been renewed recently, the corresponding replica is considered live, otherwise it is considered dead and ignored. Hasher will attempt to clean up owned Lease objects that seem to have been dead for longer than an hour. It is possible for replicas to briefly disagree about the set of live replicas during membership changes, which may lead to affected items being ignored for up to one Lease timeout period. This is no worse than the timeout behavior of Lease-based leader election.

To use Hasher, you provide information about the Lease objects that will be created and queried: namespace and label selector. You also provide the ID of the current replica, which is used as both the name of the replica's Lease and the identity of the owner of the lease. It's fine to use a random UUID for your ID, but you can get greater stability across restarts by choosing a more persistent identifier.

There's no reason to create more than one Hasher instance per binary.

Hasher is based on the FNV-1a 64-bit variant.

func New

func New(kc kubernetes.Interface, namespace, applicationName, replicaName string, replicaUID types.UID, clock clock.Clock) *Hasher

New returns a new Hasher.

func (*Hasher) AssignedToThisReplica

func (h *Hasher) AssignedToThisReplica(ctx context.Context, item string) bool

AssignedToThisReplica uses rendezvous hashing to decide if the given item is assigned to the current replica.

Item needs to be a stable identifier for the work item, like namespace/name or UID. You don't need to treat the keys to make them uniform; that is handled by the rendezvous hashing implementation.

To avoid leaking work items, you should continue to recheck items that are currently not assigned to this replica until they are finished, just in case, they get reassigned to this replica. For example, when processing PodCertificateRequests, if the PCR is not currently assigned to this replica, add it back to the work queue with backoff. Once the PCR is issued, it can be removed from the workqueue.

func (*Hasher) Run

func (h *Hasher) Run(ctx context.Context)

Run starts the Hasher, blocking the current goroutine until ctx is done.