allocator

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(typ AllocatorKey, backend Backend, opts ...AllocatorOption) (*Allocator, error)

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

func (a *Allocator) Allocate(ctx