allocator

Documentation

Overview

Package allocator implements a distributed algorithm for assigning a number of "Items" across a number of "Members", where each Member runs an instance of the Allocator. Items and Members may come and go over time; each may have constraints on desired replication and assignment limits which must be satisfied, and replicas may be placed across distinct failure Zones. Allocator coordinates through Etcd, and uses a greedy, incremental maximum- flow solver to quickly determine minimal re-Assignments which best balance Items across Members (subject to constraints).

Index

• Constants
• func Allocate(args AllocateArgs) error
• func AssignmentKey(ks *keyspace.KeySpace, a Assignment) string
• func ItemAssignmentsPrefix(ks *keyspace.KeySpace, itemID string) string
• func ItemKey(ks *keyspace.KeySpace, id string) string
• func MemberKey(ks *keyspace.KeySpace, zone, suffix string) string
• func NewAllocatorKeySpace(prefix string, decode Decoder) *keyspace.KeySpace
• func NewAllocatorKeyValueDecoder(prefix string, decode Decoder) keyspace.KeyValueDecoder
• func StartSession(args SessionArgs) error
• type AllocateArgs
• type Announcement
  • func Announce(etcd *clientv3.Client, key, value string, lease clientv3.LeaseID) *Announcement
  • func (a *Announcement) Update(value string) error
• type Assignment
• type AssignmentValue
• type Decoder
• type IsConsistentFn
• type Item
  • func LookupItem(ks *keyspace.KeySpace, id string) (Item, bool)
• type ItemValue
• type LeftJoin
  • func (j *LeftJoin) Next() (LeftJoinCursor, bool)
• type LeftJoinCursor
• type LocalItem
• type Member
  • func LookupMember(ks *keyspace.KeySpace, zone, suffix string) (Member, bool)
• type MemberValue
• type SessionArgs
• type State
  • func NewObservedState(ks *keyspace.KeySpace, localKey string, fn IsConsistentFn) *State

Constants

const (
	// ItemsPrefix prefixes Item keys, eg "root/items/id"
	ItemsPrefix = "/items/"
	// MembersPrefix prefixes Member keys, eg "root/members/zone#suffix"
	MembersPrefix = "/members/"
	// AssignmentsPrefix prefixes Assignment keys, eg "prefix/assign/item-id#zone#member-suffix#slot"
	AssignmentsPrefix = "/assign/"
	// '#' is selected as separator, because it's the first visual ASCII character
	// which is not interpreted by shells (preceding visual characters are " and !).
	// The fact that it's lowest-value ensures that the natural ordering of KeySpace
	// entities like Member and Assignment agrees with the lexicographic ordering of
	// their encoded Etcd keys. As fallout, this means ", !, and other non-visual
	// characters below ord('#') = 35 are disallowed (such as ' ', '\t', '\r', '\n'),
	// but everything else is fair game. Note that includes UTF-8, which by design
	// does not collide with the first 128 ASCII code-points.
	Sep, SepByte = "#", '#'
)

Functions

func Allocate

func Allocate(args AllocateArgs) error

Allocate observes the Allocator KeySpace, and if this Allocator instance is the current leader, performs reactive scheduling rounds to maintain the allocation of all Items to Members. Allocate exits on an unrecoverable error, or if:

• The local Member has an ItemLimit of Zero, AND
• No Assignments to the current Member remain.

Eg, Allocate should be gracefully stopped by updating the ItemLimit of the Member identified by Allocator.LocalKey() to zero (perhaps as part of a SIGTERM signal handler) and then waiting for Allocate to return, which it will once all instance Assignments have been re-assigned to other Members.

func AssignmentKey

func AssignmentKey(ks *keyspace.KeySpace, a Assignment) string

AssignmentKey returns the unique key for Assignment |assignment| under the KeySpace.

func ItemAssignmentsPrefix

func ItemAssignmentsPrefix(ks *keyspace.KeySpace, itemID string) string

ItemAssignmentsPrefix returns the unique key prefix for all Assignments of |itemID| under the KeySpace.

func ItemKey

func ItemKey(ks *keyspace.KeySpace, id string) string

ItemKey returns the unique key for an Item with ID |id| under the KeySpace.

func MemberKey

func MemberKey(ks *keyspace.KeySpace, zone, suffix string) string

MemberKey returns the unique key for a Member with |zone| and |suffix| under the KeySpace.

func NewAllocatorKeySpace

func NewAllocatorKeySpace(prefix string, decode Decoder) *keyspace.KeySpace

NewAllocatorKeySpace is a convenience for `NewKeySpace(prefix, NewAllocatorKeyValueDecoder(prefix, decode))`.

func NewAllocatorKeyValueDecoder

func NewAllocatorKeyValueDecoder(prefix string, decode Decoder) keyspace.KeyValueDecoder

NewAllocatorKeyValueDecoder returns a KeyValueDecoder utilizing the supplied Decoder, and suitable for use with NewKeySpace of the same |prefix|. Some implementations may wish to further wrap the returned KeyValueDecoder to enable recognition and decoding of additional custom prefixes and entity types, beyond the Allocator's Members, Items, & Assignments.

func StartSession

func StartSession(args SessionArgs) error

StartSession starts an allocator session. It:

• Validates the MemberSpec.
• Establishes an Etcd lease which conveys "liveness" of this member to its peers.
• Announces the MemberSpec under the lease.
• Loads the KeySpace as-of the announcement revision.
• Queues tasks to the *task.Group which:
• Closes the Etcd lease on task.Group cancellation.
• Monitors SignalCh and zeros the MemberSpec ItemLimit on its signal.
• Runs the Allocate loop, cancelling the *task.Group on completion.

Types

type AllocateArgs

type AllocateArgs struct {
	Context context.Context
	// Etcd client Allocate will use to effect changes to the distributed allocation.
	Etcd *clientv3.Client
	// Allocator state, which is derived from a Watched KeySpace.
	State *State
	// TestHook is an optional testing hook, invoked after each convergence round.
	TestHook func(round int, isIdle bool)
}

type Announcement

type Announcement struct {
	Key      string
	Revision int64
	// contains filtered or unexported fields
}

Announcement manages a unique key which is "announced" to peers through Etcd, with an associated lease and a value which may be updated over time. It's useful for managing keys which simultaneously represent semantics of existence, configuration, and processing live-ness (such as allocator member keys).

func Announce

func Announce(etcd *clientv3.Client, key, value string, lease clientv3.LeaseID) *Announcement

Announce a key and value to etcd under the LeaseID, asserting the key doesn't already exist. If the key does exist, Announce will retry until it disappears (eg, due to a former lease timeout).

func (*Announcement) Update

func (a *Announcement) Update(value string) error

Update the value of a current Announcement.

type Assignment

type Assignment struct {
	ItemID       string
	MemberZone   string
	MemberSuffix string
	Slot         int
	AssignmentValue
}

Assignment composes an Assignment ItemID, MemberZone, MemberSuffix & Slot with its user-defined AssignmentValue.

type AssignmentValue

type AssignmentValue interface{}

AssignmentValue is a user-defined Assignment representation.

type Decoder

type Decoder interface {
	DecodeItem(id string, raw *mvccpb.KeyValue) (ItemValue, error)
	DecodeMember(zone, suffix string, raw *mvccpb.KeyValue) (MemberValue, error)
	DecodeAssignment(itemID, memberZone, memberSuffix string, slot int, raw *mvccpb.KeyValue) (AssignmentValue, error)
}

Decoder decodes "raw" Etcd values of Items, Members, and Assignments into their user-defined representations.

type IsConsistentFn

type IsConsistentFn func(
	item Item,
	itemAssignment keyspace.KeyValue,
	allAssignmentsOfItem keyspace.KeyValues) bool

IsConsistentFn is a free function which determines whether the Item is to be considered "consistent" given its current AssignmentValue and the set of all AssignmentValues of the Item.

The meaning of "consistent" is up to the application: generally it means that assigned replicas of the Item have synchronized with each other and can tolerate the removal of one of their cohort. If an Item is currently inconsistent, the allocator will not remove a current Assignment of the Item and instead waits for replicas to perform synchronization activities, communicated through Etcd, such that IsConsistentFn once again returns true.

type Item

type Item struct {
	ID string
	ItemValue
}

Item composes an Item ID with its user-defined ItemValue.

func LookupItem

func LookupItem(ks *keyspace.KeySpace, id string) (Item, bool)

LookupItem returns the identified Item, or false if not found. The KeySpace must already be locked.

type ItemValue

type ItemValue interface {
	// DesiredReplication for this Item.
	DesiredReplication() int
}

ItemValue is a user-defined Item representation which also supports required APIs for use by Allocator.

type LeftJoin

type LeftJoin struct {
	// length of the collections.
	LenL, LenR int
	// Compare returns -1 if |l| orders before |r|, 0 if they are equal,
	// and 1 if |l| is greater.
	Compare func(l, r int) int

	LeftJoinCursor
}

LeftJoin performs a Left join of two comparable, index-able, and ordered collections.

func (*LeftJoin) Next

func (j *LeftJoin) Next() (LeftJoinCursor, bool)

Next returns the next cursor of the join and true, or if no rows remain in the join, a zero-valued cursor and false.

type LeftJoinCursor

type LeftJoinCursor struct {
	Left, RightBegin, RightEnd int
}

LeftJoinCursor is a LeftJoin result row, relating a |Left| index with a [RightBegin, RightEnd) range of indices comparing as equal.

type LocalItem

type LocalItem struct {
	Item        keyspace.KeyValue  // Item which is locally Assigned.
	Assignments keyspace.KeyValues // All Assignments of the Item.
	Index       int                // The index of the local Assignment within |Assignments|.
}

LocalItem represents an Item which is assigned to the local Allocator.

type Member

type Member struct {
	Zone   string
	Suffix string
	MemberValue
}

Member composes a Member Zone & Suffix with its user-defined MemberValue.

func LookupMember

func LookupMember(ks *keyspace.KeySpace, zone, suffix string) (Member, bool)

LookupMember returns the identified Member, or false if not found. The KeySpace must already be locked.

type MemberValue

type MemberValue interface {
	// ItemLimit is the maximum number of Items this Member may be assigned.
	ItemLimit() int
}

MemberValue is a user-defined Member representation which also supports required APIs for use by Allocator.

type SessionArgs

type SessionArgs struct {
	Etcd  *clientv3.Client
	Tasks *task.Group
	Spec  interface {
		Validate() error
		ZeroLimit()
		MarshalString() string
	}
	State    *State
	LeaseTTL time.Duration
	SignalCh <-chan os.Signal
	TestHook func(round int, isIdle bool)
}

SessionArgs are arguments of StartSession.

type State

type State struct {
	KS           *keyspace.KeySpace
	LocalKey     string         // Unique key of this allocator instance.
	IsConsistent IsConsistentFn // Consistency callback for this allocator.

	// Sub-slices of the KeySpace representing allocator entities.
	Members     keyspace.KeyValues
	Items       keyspace.KeyValues
	Assignments keyspace.KeyValues

	LocalMemberInd int         // Index of |LocalKey| within |Members|, or -1 if not found.
	LocalItems     []LocalItem // Assignments of this instance.

	Zones       []string // Sorted and unique Zones of |Members|.
	ZoneSlots   []int    // Total number of item slots summed across all |Members| of each Zone.
	ItemSlots   int      // Total desired replication slots summed across all |Items|.
	MemberSlots int      // Total available slots for replication summed across all |Members|.
	NetworkHash uint64   // Content-sum which captures Items & Members, and their constraints.

	// Number of total Assignments, and primary Assignments by Member.
	// These share cardinality with |Members|.
	MemberTotalCount   []int
	MemberPrimaryCount []int
}

State is an extracted representation of the allocator KeySpace. Clients may want to inspect State as part of a KeySpace observer to identify changes to local assignments or the overall allocation topology.

func NewObservedState

func NewObservedState(ks *keyspace.KeySpace, localKey string, fn IsConsistentFn) *State

NewObservedState returns a *State instance which extracts and updates itself from the provided KeySpace, pivoted around the Member instance identified by |localKey|. Item consistency is determined using the provided IsConsistentFn. State should be treated as read-only, and a read lock of the parent KeySpace must be obtained before each use.