allocator

package
v1.17.16 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 13, 2026 License: Apache-2.0 Imports: 17 Imported by: 25

Documentation

Overview

Package allocator provides a kvstore based ID allocator

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Allocator 

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

Allocator is a distributed ID allocator backed by a KVstore. It maps arbitrary keys to identifiers. Multiple users on different cluster nodes can in parallel request the ID for keys and are guaranteed to retrieve the same ID for an identical key.

While the details of how keys are stored is delegated to Backend implementations, some expectations exist. See pkg/kvstore/allocator for details about the kvstore implementation.

A node takes a reference to an identity when it is in-use on that node, and the identity remains in-use if there is any node reference to it. When an identity no longer has any node references, it may be garbage collected. No guarantees are made at that point and the numeric identity may be reused. Note that the numeric IDs are selected locally and verified with the Backend.

Lookup ID by key:

  1. Return ID from local cache updated by watcher (no Backend interactions)
  2. Do ListPrefix() on slave key excluding node suffix, return the first result that matches the exact prefix.

Lookup key by ID:

  1. Return key from local cache updated by watcher (no Backend interactions)
  2. Do Get() on master key, return result

Allocate:

  1. Check local key cache, increment, and return if key is already in use locally (no Backend interactions)
  2. Check local cache updated by watcher, if...

... match found: 

2.1 Create a new slave key. This operation is potentially racy as the master
    key can be removed in the meantime.
    - etcd: Create is made conditional on existence of master key
    - consul: locking

... match not found: 

2.1 Select new unused id from local cache
2.2 Create a new master key with the condition that it may not exist
2.3 Create a new slave key

1.1. If found, increment and return (no Backend interactions) 2. Lookup ID by key in local cache or via first slave key found in Backend

Release:

  1. Reduce local reference count until last use (no Backend interactions)
  2. Delete slave key (basePath/value/key1/node1) This automatically guarantees that when the last node has released the key, the key is no longer found by Get()
  3. If the node goes down, all slave keys of that node are removed after the TTL expires (auto release).

func NewAllocator 

func NewAllocator(typ AllocatorKey, backend Backend, opts ...AllocatorOption) (*Allocator, error)

NewAllocator creates a new Allocator. Any type can be used as key as long as the type implements the AllocatorKey interface. A variable of the type has to be passed into NewAllocator() to make the type known. The specified base path is used to prefix all keys in the kvstore. The provided path must be unique.

The allocator can be configured by passing in additional options:

  • WithEvents() - enable Events channel
  • WithMin(id) - minimum ID to allocate (default: 1)
  • WithMax(id) - maximum ID to allocate (default max(uint64))

After creation, IDs can be allocated with Allocate() and released with Release()

func NewAllocatorForGC 

func NewAllocatorForGC(backend Backend, opts ...AllocatorOption) *Allocator

NewAllocatorForGC returns an allocator that can be used to run RunGC()

The allocator can be configured by passing in additional options:

  • WithMin(id) - minimum ID to allocate (default: 1)
  • WithMax(id) - maximum ID to allocate (default max(uint64))

func (*Allocator) Allocate 

func (a *Allocator) Allocate(ctx context.Context, key AllocatorKey) (idpool.ID, bool, bool, error)

Allocate will retrieve the ID for the provided key. If no ID has been allocated for this key yet, a key will be allocated. If allocation fails, most likely due to a parallel allocation of the same ID by another user, allocation is re-attempted for maxAllocAttempts times.

Return values:

  1. allocated ID
  2. whether the ID is newly allocated from kvstore
  3. whether this is the first owner that holds a reference to the key in localkeys store
  4. error in case of failure

func (*Allocator) Delete 

func (a *Allocator) Delete()

Delete deletes an allocator and stops the garbage collector

func (*Allocator) DeleteAllKeys 

func (a *Allocator) DeleteAllKeys()

DeleteAllKeys will delete all keys. It is expected to be used in tests.

func (*Allocator) ForeachCache 

func (a *Allocator) ForeachCache(cb RangeFunc)

ForeachCache iterates over the allocator cache and calls RangeFunc on each cached entry

func (*Allocator) Get 

func (a *Allocator) Get(ctx context.Context, key AllocatorKey) (idpool.ID, error)

Get returns the ID which is allocated to a key. Returns an ID of NoID if no ID has been allocated to this key yet.

func (*Allocator) GetByID 

func (a *Allocator) GetByID(ctx context.Context, id idpool.ID) (AllocatorKey, error)

GetByID returns the key associated with an ID. Returns nil if no key is associated with the ID.

func (*Allocator) GetByIDIncludeRemoteCaches 

func (a *Allocator) GetByIDIncludeRemoteCaches(ctx context.Context, id idpool.ID) (AllocatorKey, error)

GetByIDIncludeRemoteCaches returns the key associated with an ID. Includes the caches of watched remote kvstores in the query. Returns nil if no key is associated with the ID.

func (*Allocator) GetEvents 

func (a *Allocator) GetEvents() AllocatorEventSendChan

GetEvents returns the events channel given to the allocator when constructed. Note: This channel is not owned by the allocator!

func (*Allocator) GetIfLocked 

func (a *Allocator) GetIfLocked(ctx context.Context, key AllocatorKey, lock kvstore.KVLocker) (idpool.ID, error)

GetIfLocked returns the ID which is allocated to a key. Returns an ID of NoID if no ID has been allocated to this key yet if the client is still holding the given lock.

func (*Allocator) GetIncludeRemoteCaches 

func (a *Allocator) GetIncludeRemoteCaches(ctx context.Context, key AllocatorKey) (idpool.ID, error)

GetIncludeRemoteCaches returns the ID which is allocated to a key. Includes the caches of watched remote kvstores in the query. Returns an ID of NoID if no ID has been allocated in any remote kvstore to this key yet.

func (*Allocator) GetNoCache 

func (a *Allocator) GetNoCache(ctx context.Context, key AllocatorKey) (idpool.ID, error)

GetNoCache returns the ID which is allocated to a key in the kvstore, bypassing the local copy of allocated keys.

func (*Allocator) GetWithRetry added in v1.17.0 

func (a *Allocator) GetWithRetry(ctx context.Context, key AllocatorKey) (idpool.ID, error)

func (*Allocator) NewRemoteCache 

func (a *Allocator) NewRemoteCache(remoteName string, remoteAlloc *Allocator) RemoteIDCache

func (*Allocator) Observe 

func (a *Allocator) Observe(ctx context.Context, next func(AllocatorChange), complete func(error))

Observe the identity changes. Conforms to stream.Observable. Replays the current state of the cache when subscribing.

func (*Allocator) Release 

func (a *Allocator) Release(ctx context.Context, key AllocatorKey) (lastUse bool, err error)

Release releases the use of an ID associated with the provided key. After the last user has released the ID, the key is removed in the KVstore and the returned lastUse value is true.

func (*Allocator) RemoveRemoteKVStore 

func (a *Allocator) RemoveRemoteKVStore(remoteName string)

RemoveRemoteKVStore removes any reference to a remote allocator / kvstore, emitting a deletion event for all previously known identities.

func (*Allocator) RunGC 

func (a *Allocator) RunGC(ctx context.Context, rateLimit *rate.Limiter, staleKeysPrevRound map[string]uint64) (map[string]uint64, *GCStats, error)

RunGC scans the kvstore for unused master keys and removes them

func (*Allocator) RunLocksGC 

func (a *Allocator) RunLocksGC(ctx context.Context, staleLocksPrevRound map[string]kvstore.