allocator

Documentation

Overview

Package allocator provides a kvstore based ID allocator

Index

• type Allocator
  • func NewAllocator(basePath string, typ AllocatorKey, opts ...AllocatorOption) (*Allocator, error)
  • func NewAllocatorForGC(basePath string) *Allocator
  • func (a *Allocator) Allocate(ctx context.Context, key AllocatorKey) (idpool.ID, bool, error)
  • func (a *Allocator) Delete()
  • func (a *Allocator) DeleteAllKeys()
  • func (a *Allocator) ForeachCache(cb RangeFunc)
  • func (a *Allocator) Get(ctx context.Context, key AllocatorKey) (idpool.ID, error)
  • func (a *Allocator) GetByID(id idpool.ID) (AllocatorKey, error)
  • func (a *Allocator) GetIfLocked(ctx context.Context, key AllocatorKey, lock kvstore.KVLocker) (idpool.ID, error)
  • func (a *Allocator) GetNoCache(ctx context.Context, key AllocatorKey) (idpool.ID, error)
  • func (a *Allocator) GetNoCacheIfLocked(ctx context.Context, key AllocatorKey, lock kvstore.KVLocker) (idpool.ID, error)
  • func (a *Allocator) Release(ctx context.Context, key AllocatorKey) (lastUse bool, err error)
  • func (a *Allocator) RunGC(staleKeysPrevRound map[string]uint64) (map[string]uint64, error)
  • func (k *Allocator) RunLocksGC(staleKeysPrevRound map[string]kvstore.Value) (map[string]kvstore.Value, error)
  • func (a *Allocator) WaitForInitialSync(ctx context.Context) error
  • func (a *Allocator) WatchRemoteKVStore(backend kvstore.BackendOperations, prefix string) *RemoteCache
• type AllocatorEvent
• type AllocatorEventChan
• type AllocatorKey
• type AllocatorOption
  • func WithEvents(events AllocatorEventChan) AllocatorOption
  • func WithMasterKeyProtection() AllocatorOption
  • func WithMax(id idpool.ID) AllocatorOption
  • func WithMin(id idpool.ID) AllocatorOption
  • func WithPrefixMask(mask idpool.ID) AllocatorOption
  • func WithSuffix(v string) AllocatorOption
  • func WithoutGC() AllocatorOption
• type RangeFunc
• type RemoteCache
  • func (rc *RemoteCache) Close()

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.

Slave keys:

Slave keys are owned by individual nodes:
  - basePath/value/key1/node1 => 1001
  - basePath/value/key1/node2 => 1001
  - basePath/value/key2/node1 => 1002
  - basePath/value/key2/node2 => 1002

If at least one key exists with the prefix basePath/value/keyN then that
key must be considered to be in use in the allocation space.

Slave keys are protected by a lease and will automatically get removed
after ~ kstore.LeaseTTL if the node does not renew in time.

Master key:

• basePath/id/1001 => key1

• basePath/id/1002 => key2

  Master keys provide the mapping from ID to key. As long as a master key for an ID exists, the ID is still in use. However, if a master key is no longer backed by at least one slave key, the garbage collector will eventually release the master key and return it back to the pool.

Lookup ID by key:

1. Return ID from local cache updated by watcher (no kvstore 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 kvstore 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 kvstore 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 kvstore interactions) 2. Lookup ID by key in local cache or via first slave key found in kvstore 2.1 3.

Release:

1. Reduce local reference count until last use (no kvstore interactions)
2. Delete slave key (basePath/value/key1/node1) This automatically guarantees that when the last node has relesed 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(basePath string, typ AllocatorKey, 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
• WithSuffix(string) - customize the node specifix suffix to attach to keys
• 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(basePath string) *Allocator

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

func (*Allocator) Allocate

func (a *Allocator) Allocate(ctx context.Context, key AllocatorKey) (idpool.ID, 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.

Returns the ID allocated to the key, if the ID had to be allocated, then true is returned. An error is returned 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

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(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) 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) 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

func (*Allocator) GetNoCacheIfLocked

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

GetNoCacheIfLocked returns the ID which is allocated to a key in the kvstore if the client is still holding the given lock.

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) RunGC

func (a *Allocator) RunGC(staleKeysPrevRound map[string]uint64) (map[string]uint64, error)

RunGC scans the kvstore for unused master keys and removes them

func (*Allocator) RunLocksGC

func (k *Allocator) RunLocksGC(staleKeysPrevRound map[string]kvstore.Value) (map[string]kvstore.Value, error)

RunLocksGC scans the kvstore for unused locks and removes them. Returns a map of locks that are currently being held, including the ones that have failed to be GCed.

func (*Allocator) WaitForInitialSync

func (a *Allocator) WaitForInitialSync(ctx context.Context) error

WaitForInitialSync waits until the initial sync is complete

func (*Allocator) WatchRemoteKVStore

func (a *Allocator) WatchRemoteKVStore(backend kvstore.BackendOperations, prefix string) *RemoteCache

WatchRemoteKVStore starts watching an allocator base prefix the kvstore represents by the provided backend. A local cache of all identities of that kvstore will be maintained in the RemoteCache structure returned and will start being reported in the identities returned by the ForeachCache() function.

type AllocatorEvent

type AllocatorEvent struct {
	// Typ is the type of event (create / modify / delete)
	Typ kvstore.EventType

	// ID is the allocated ID
	ID idpool.ID

	// Key is the key associated with the ID
	Key AllocatorKey
}

AllocatorEvent is an event sent over AllocatorEventChan

type AllocatorEventChan

type AllocatorEventChan chan AllocatorEvent

AllocatorEventChan is a channel to receive allocator events on

type AllocatorKey

type AllocatorKey interface {
	// GetKey must return the key in string representation
	GetKey() string

	// PutKey must transform the key in string representation back into its
	// original type
	PutKey(v string) (AllocatorKey, error)

	// String must return the key in human readable string representation
	String() string
}

AllocatorKey is the interface to implement in order for a type to be used as key for the allocator

type AllocatorOption

type AllocatorOption func(*Allocator)

AllocatorOption is the base type for allocator options

func WithEvents

func WithEvents(events AllocatorEventChan) AllocatorOption

WithEvents enables receiving of events.

CAUTION: When using this function. The provided channel must be continuously read while NewAllocator() is being called to ensure that the channel does not block indefinitely while NewAllocator() emits events on it while populating the initial cache.

func WithMasterKeyProtection

func WithMasterKeyProtection() AllocatorOption

WithMasterKeyProtection will watch for delete events on master keys and re-created them if local usage suggests that the key is still in use

func WithMax

func WithMax(id idpool.ID) AllocatorOption

WithMax sets the maximum identifier to be allocated

func WithMin

func WithMin(id idpool.ID) AllocatorOption

WithMin sets the minimum identifier to be allocated

func WithPrefixMask

func WithPrefixMask(mask idpool.ID) AllocatorOption

WithPrefixMask sets the prefix used for all ID allocations. If set, the mask will be ORed to all selected IDs prior to allocation. It is the responsibility of the caller to ensure that the mask is not conflicting with min..max.

func WithSuffix

func WithSuffix(v string) AllocatorOption

WithSuffix sets the suffix of the allocator to the specified value

func WithoutGC

func WithoutGC() AllocatorOption

WithoutGC disables the use of the garbage collector

type RangeFunc

type RangeFunc func(idpool.ID, AllocatorKey)

RangeFunc is the function called by RangeCache

type RemoteCache

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

RemoteCache represents the cache content of an additional kvstore managing identities. The contents are not directly accessible but will be merged into the ForeachCache() function.

func (*RemoteCache) Close

func (rc *RemoteCache) Close()

Close stops watching for identities in the kvstore associated with the remote cache and will clear the local cache.