consensus

package
v2.0.206+incompatible Latest Latest
Warning

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

Go to latest
Published: Mar 20, 2019 License: MIT Imports: 16 Imported by: 0

Documentation

Overview

Package consensus provides building blocks for solving difficult distributed consensus-related problems atop Etcd, both within and across processes.

Code generated by mockery v1.0.0

Code generated by mockery v1.0.0

Code generated by mockery v1.0.0

Index

Constants

View Source
const (
	MemberPrefix = "members" // Directory root for member announcements.
	ItemsPrefix  = "items"   // Directory root for allocated items.

)

Variables

View Source
var ErrAllocatorInstanceExists = errors.New("Allocator member key exists")

Functions

func Allocate

func Allocate(alloc Allocator) error

Allocate acts on behalf of |alloc| to achieve distributed allocation of items. This is a long-lived call, which will exit only after |alloc|'s member announcement is removed (eg, by Cancel(alloc)) and all allocated items have been safely handed off to ready replicas.

Allocate acts on behalf of an existing member lock. If such a lock does not exist, Allocate will take no action. If it exists but is owned by another process, Allocate will duplicate the item allocations of that process. It is the caller's responsibility to obtain and verify uniqueness of the member lock (eg, via a preceeding Create).

func BlockUntilModified

func BlockUntilModified(watcher etcd.Watcher, index uint64)

BlockUntilModified blocks until the watcher is modified beyond the passed index.

func Cancel

func Cancel(alloc Allocator) error

Cancel cancels |alloc| by deleting its member announcement. The matching Allocate() invocation will begin an orderly release of held items. When all items are released, Allocate() will exit. Note that mastered items will be released only once they have a sufficient number of ready replicas for hand-off.

func CancelItem

func CancelItem(alloc Allocator, item string) error

CancelItem cancels |item| by deleting its announcement. This should be undertaken only under exceptional circumstances, where the local Allocator is unable to service the allocated |item| (eg, because of an unrecoverable local error).

func Child

func Child(parent *etcd.Node, names ...string) *etcd.Node

Child follows the hierarchy under |parent| for each successive path element in |names|, and returns the *etcd.Node of the leaf element if it exists, or nil otherwise.

Precondition: |parent.Nodes| is recursively sorted.

func CopyNode

func CopyNode(node *etcd.Node) *etcd.Node

CopyNode creates a deep-copy of |node|.

func CopyNodes

func CopyNodes(nodes etcd.Nodes) etcd.Nodes

CopyNodes creates a deep-copy of |nodes|.

func Create

func Create(alloc Allocator) error

Create attempts to create an Allocator member lock reflecting instance |alloc|. If the member lock already exists, returns ErrAllocatorInstanceExists. An Allocator member lock should be obtained prior to an Allocate call.

func CreateAndAllocateWithSignalHandling

func CreateAndAllocateWithSignalHandling(alloc Allocator) error

Composes Create and Allocate to run an Allocator which will additionally use an installed signal handler to gracefully Cancel itself on a SIGTERM or SIGINT. Performs a polled retry of Create on ErrAllocatorInstanceExists, until aquired or signaled. Top-level programs implementing an Allocator will generally want to use this.

func FindNode

func FindNode(node *etcd.Node, key string) (parent *etcd.Node, index int)

FindNode performs a recursive search rooted at |node| to identify the |parent| of |key|, and the |index| where |key| exists or would be inserted. If a required parent of |key| does not exist, its insertion-point is returned.

Precondition: |node| is recursively sorted.

func IsEtcdRemoveOp

func IsEtcdRemoveOp(action string) bool

IsEtcdRemoveOp returns whether an etcd.Response.Action is a removal.

func IsEtcdUpsertOp

func IsEtcdUpsertOp(action string) bool

IsEtcdUpsertOp returns whether an etcd.Response.Action is an insert or update.

func PatchTree

func PatchTree(tree *etcd.Node, response *etcd.Response) (*etcd.Node, error)

PatchTree patches |tree| to reflect |response|, returning the new tree root (which may be |tree|). PatchTree() can be fed responses of a RetryWatcher() to provide an incrementally-built consistent view of a keyspace.

Precondition: |tree| and |response| are recursively sorted.

func RetryWatcher

func RetryWatcher(keysAPI etcd.KeysAPI, key string, getOpts *etcd.GetOptions,
	watcherOpts *etcd.WatcherOptions, refreshTicker <-chan time.Time) etcd.Watcher

RetryWatcher composes Get() and Watch() of etcd.KeysAPI to provide a etcd.Watcher implementation with builtin retry for watch errors. RetryWatcher differs from KeysAPI.Watcher() in two key ways:

  • WatcherOptions.AfterIndex is ignored. Instead, RetryWatcher() performs its own Get() on the first call to Next().
  • Watch-related errors will be silently retried via a Get(), which is both passed through and also used to re-establish watch consistency. Callers must be able to handle a periodic "get" response.

func TerminalNodes

func TerminalNodes(node *etcd.Node) etcd.Nodes

TerminalNodes returns all non-directory children under |node| via depth-first search (eg, maintaining key-order invariants of the tree).

func WalkItems

func WalkItems(tree *etcd.Node, fixedItems []string, cb func(name string, route Route))

WalkItems performs a zipped, outer-join iteration of items under ItemsPrefix of |tree|, and |fixedItems| (which must be ordered). The argument callback |cb| is invoked for each item, and must not retain |route| after each call.

Types

type Allocator

type Allocator interface {
	KeysAPI() etcd.KeysAPI
	// Etcd path which roots shared state for this Context.
	PathRoot() string
	// A key uniquely identifying this Allocator within shared state.
	InstanceKey() string
	// The required number of replicas. Except in cases of failure, allocation
	// changes will not be made which would violate having at least this many
	// ready replicas of an item at all times.
	Replicas() int
	// Items which will be created if they do not exist. May be empty, and
	// additional items may be added at any time out-of-band (via creation of
	// a corresponding Etcd directory).
	FixedItems() []string

	// For |item| which is currently a local replica or master, returns a
	// representation of the local item processing state. State is shared with
	// other Allocators via this Allocator's |item| announcement in Etcd.
	ItemState(item string) string
	// For |state| of an item, which may be processed by another Allocator,
	// returns whether the item can safely be promoted at this time.
	ItemIsReadyForPromotion(item, state string) bool
	// Notifies Allocator of |route| for |item|. If |index| == -1, then Allocator
	// has no entry for |item|. Otherwise, |route.Entries[index]| is the entry
	// of this Allocator (and will have basename InstanceKey()). |tree| is given
	// as context: ItemRoute() will often wish to wish to inspect other state
	// within |tree| in response to a route change. Note that |route| or |tree|
	// must be copied if retained beyond this call
	ItemRoute(item string, route Route, index int, tree *etcd.Node)
}

Allocator is an interface which performs distributed allocation of items.

type Inspector

type Inspector interface {
	// InspectChan returns a channel which may request invocations to inspect
	// state in between allocator actions. The callback is invoked from the
	// Allocator's goroutine and has exclusive read access to the |tree| for the
	// call duration. Because of this, callbacks must be non-blocking. The
	// callback must not modify |tree|.
	InspectChan() chan func(tree *etcd.Node)
}

Inspector is an optional interface of an Allocator which allows for inspections of the Allocator state tree.

type KeysAPI

type KeysAPI interface {
	Get(ctx context.Context, key string, opts *etcd.GetOptions) (*etcd.Response, error)
	Set(ctx context.Context, key, value string, opts *etcd.SetOptions) (*etcd.Response, error)
	Delete(ctx context.Context, key string, opts *etcd.DeleteOptions) (*etcd.Response, error)
	Create(ctx context.Context, key, value string) (*etcd.Response, error)
	CreateInOrder(ctx context.Context, dir, value string, opts *etcd.CreateInOrderOptions) (*etcd.Response, error)
	Update(ctx context.Context, key, value string) (*etcd.Response, error)
	Watcher(key string, opts *etcd.WatcherOptions) etcd.Watcher
}

KeysAPI and Watcher duplicate interfaces of github.com/coreos/etcd/client by the same name for mock generation.

TODO(johnny): We'd prefer to compose the etcd interfaces. However, we rely on mockery for mock generation, and first require a fix for https://github.com/vektra/mockery/issues/18.

type MockAllocator

type MockAllocator struct {
	mock.Mock
}

MockAllocator is an autogenerated mock type for the Allocator type

func (*MockAllocator) FixedItems

func (_m *MockAllocator) FixedItems() []string

FixedItems provides a mock function with given fields:

func (*MockAllocator) InstanceKey

func (_m *MockAllocator) InstanceKey() string

InstanceKey provides a mock function with given fields:

func (*MockAllocator) ItemIsReadyForPromotion

func (_m *MockAllocator) ItemIsReadyForPromotion(item string, state string) bool

ItemIsReadyForPromotion provides a mock function with given fields: item, state

func (*MockAllocator) ItemRoute

func (_m *MockAllocator) ItemRoute(item string, route Route, index int, tree *client.Node)

ItemRoute provides a mock function with given fields: item, route, index, tree

func (*MockAllocator) ItemState

func (_m *MockAllocator) ItemState(item string) string

ItemState provides a mock function with given fields: item

func (*MockAllocator) KeysAPI

func (_m *MockAllocator) KeysAPI() client.KeysAPI

KeysAPI provides a mock function with given fields:

func (*MockAllocator) PathRoot

func (_m *MockAllocator) PathRoot() string

PathRoot provides a mock function with given fields:

func (*MockAllocator) Replicas

func (_m *MockAllocator) Replicas() int

Replicas provides a mock function with given fields:

type MockKeysAPI

type MockKeysAPI struct {
	mock.Mock
}

MockKeysAPI is an autogenerated mock type for the KeysAPI type

func (*MockKeysAPI) Create

func (_m *MockKeysAPI) Create(ctx context.Context, key string, value string) (*client.Response, error)

Create provides a mock function with given fields: ctx, key, value

func (*MockKeysAPI) CreateInOrder

func (_m *MockKeysAPI) CreateInOrder(ctx context.Context, dir string, value string, opts *client.CreateInOrderOptions) (*client.Response, error)

CreateInOrder provides a mock function with given fields: ctx, dir, value, opts

func (*MockKeysAPI) Delete

func (_m *MockKeysAPI) Delete(ctx context.Context, key string, opts *client.DeleteOptions) (*client.Response, error)

Delete provides a mock function with given fields: ctx, key, opts

func (*MockKeysAPI) Get

func (_m *MockKeysAPI) Get(ctx context.Context, key string, opts *client.GetOptions) (*client.Response, error)

Get provides a mock function with given fields: ctx, key, opts

func (*MockKeysAPI) Set

func (_m *MockKeysAPI) Set(ctx context.Context, key string, value string, opts *client.SetOptions) (*client.Response, error)

Set provides a mock function with given fields: ctx, key, value, opts

func (*MockKeysAPI) Update

func (_m *MockKeysAPI) Update(ctx context.Context, key string, value string) (*client.Response, error)

Update provides a mock function with given fields: ctx, key, value

func (*MockKeysAPI) Watcher

func (_m *MockKeysAPI) Watcher(key string, opts *client.WatcherOptions) client.Watcher

Watcher provides a mock function with given fields: key, opts

type MockWatcher

type MockWatcher struct {
	mock.Mock
}

MockWatcher is an autogenerated mock type for the Watcher type

func (*MockWatcher) Next

func (_m *MockWatcher) Next(_a0 context.Context) (*client.Response, error)

Next provides a mock function with given fields: _a0

type RingMutexMap

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

RingMutexMap is a ring buffer which maps keys to buffer spaces, each holding a user-defined value and Mutex. Typically a key is a hash value of some kind, and the RingMutexMap allows raced processes colliding on a given hash key to sequence their activities and to share state. RingMutexMap operates over a bounded ring buffer, which means that colliding keys will coordinate only if they compete within a single loop through the ring.

func NewRingMutexMap

func NewRingMutexMap(init func(interface{}) interface{}) *RingMutexMap

NewRingMutexMap returns a RingMutexMap with the user-defined |init| function. If non-nil, |init| is invoked to initialize the value of a newly mapped key. It is passed a previous value stored in the same ring space under a different key.

func (*RingMutexMap) Lock

func (rm *RingMutexMap) Lock(key uint64) (interface{}, *sync.Mutex)

Lock finds or creates a ring entry for |key|. It returns a locked Mutex for coordination over |key|, and the user-defined value it maps to.

type Route

type Route struct {
	// Directory Node of item.
	Item *etcd.Node
	// Entries of |Item.Nodes|, ordered on increasing CreatedIndex. 'Master' is
	// index 0, followed by item replicas. Depending on the target replica count,
	// there may be additional temporary entries which are neither master nor
	// replica (eg, due to a lost allocation race).
	Entries etcd.Nodes
}

Route represents an agreed-upon, ordered set of responsible processes for an item.

func NewRoute

func NewRoute(response *etcd.Response, node *etcd.Node) Route

NewRoute initializes a new Route from the |response| and |node|.

func (Route) Copy

func (rt Route) Copy() Route

Copy performs a deep-copy of Route.

func (Route) Index

func (rt Route) Index(name string) int

Index returns the index of |name| in |rt.Entries|, or -1.

func (Route) IsReadyForHandoff

func (rt Route) IsReadyForHandoff(alloc Allocator) bool

IsReadyForHandoff returns whether all replicas are ready for the item master to hand off item responsibility, without causing a violation of the required replica count.

type StringMap

type StringMap interface {
	Get(key string) string
}

func MapAdapter

func MapAdapter(node *etcd.Node) StringMap

MapAdapter maps |node| into a StringMap which returns the Value of a nested '/'-separated path, or the empty string if the path does not exist.

type Watcher

type Watcher interface {
	Next(context.Context) (*etcd.Response, error)
}

KeysAPI and Watcher duplicate interfaces of github.com/coreos/etcd/client by the same name for mock generation.

TODO(johnny): We'd prefer to compose the etcd interfaces. However, we rely on mockery for mock generation, and first require a fix for https://github.com/vektra/mockery/issues/18.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL