core: go.gazette.dev/core/allocator Index | Files | Directories

package allocator

import "go.gazette.dev/core/allocator"

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

Package Files

alloc_state.go allocator.go allocator_key_space.go announce.go doc.go flow_network.go item_state.go sparse_flow_network.go

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

func Allocate Uses

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 Uses

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

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

func ItemAssignmentsPrefix Uses

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

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

func ItemKey Uses

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

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

func MemberKey Uses

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 Uses

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

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

func NewAllocatorKeyValueDecoder Uses

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 Uses

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.

type AllocateArgs Uses

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 Uses

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 Uses

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 Uses

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

Update the value of a current Announcement.

type Assignment Uses

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 Uses

type AssignmentValue interface{}

AssignmentValue is a user-defined Assignment representation.

type Decoder Uses

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 Uses

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 Uses

type Item struct {
    ID  string
    ItemValue
}

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

func LookupItem Uses

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 Uses

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 Uses

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 Uses

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 Uses

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 Uses

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 Uses

type Member struct {
    Zone   string
    Suffix string
    MemberValue
}

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

func LookupMember Uses

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 Uses

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 Uses

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 Uses

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 Uses

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

PathSynopsis
push_relabelPackage push_relabel implements a greedy variant of the push/relabel algorithm.
sparse_push_relabel

Package allocator imports 23 packages (graph) and is imported by 24 packages. Updated 2020-06-18. Refresh now. Tools for package owners.