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

    View Source
    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 = "#", '#'
    )

    Variables

    This section is empty.

    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.

                                                            Directories

                                                            Path Synopsis
                                                            Package push_relabel implements a greedy variant of the push/relabel algorithm.
                                                            Package push_relabel implements a greedy variant of the push/relabel algorithm.