shuffle

package module
Version: v0.0.0-...-54250c7 Latest Latest
Warning

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

Go to latest
Published: Apr 21, 2021 License: MIT Imports: 9 Imported by: 0

README

go-shuffle-shard
----------------
This package implements the "simple signature" and "stateful searching"
versions of Amazon's Shuffle Sharding technique for load balancing and
fault isolation. Shards generated by this implementation are probabilistic
and derived from a hash of identifiers.

  * Reference:     https://github.com/awslabs/route53-infima
  * Documentation: https://godoc.org/github.com/clickyotomy/go-shuffle-shard

Documentation

Overview

Package shuffle is a implementation of Amazon's Shuffle Sharding technique, a part of Route53's Infima library. This package implements the "simple signature" version of the sharding. Shards generated by this implementation are probabilistic and derived from a hash of identifiers.

Reference: https://github.com/awslabs/route53-infima.

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Lattice

type Lattice struct {
	// DimensionNames is a set of dimensions
	// that can be attributed to a lattice.
	// Note: We'll be using a map of string
	// to bool here instead of sets, because
	// go does not support it natively.
	DimensionNames []string

	// ValuesByDimension represents positions along the dimension
	// and form part of the sector coordinates for an end-point.
	// Each dimension has a valid set of values; for example, the
	// "AvailabilityZone" dimension may have the values:
	//      ["us-x", "us-y", ...].
	ValuesByDimension map[string][]string

	// EndpointsByCoordinate is a map of the end-points by the
	// sector coordinates. For example, if our dimensions are
	// "AvailabilityZone" and "SoftwareVersion" then we might
	// have something like:
	//      ["us-x", "v42"] -> [endpoints-in-us-x-running-v42].
	EndpointsByCoordinate map[string][]string

	// Seed is the seed to use for randomness. Shuffle sharding intends
	// to use the seed as a sort of application ID to allow applications
	// to consistently produce the same results.
	Seed int64
}

Lattice defines an N-dimensional lattice.

func NewLattice

func NewLattice(dims []string) (*Lattice, error)

NewLattice creates an N-dimensional Lattice for a given set of dimension names, where each dimension represents a meaningful availability axis. It uses a seed based on process start time. See NewLatticeWithSeed for seed meaning and behavior.

Example
l, err := shuffle.NewLattice([]string{"az", "go-lang"})
if err != nil {
	fmt.Printf("unable to create a lattice: %v", err)
}

fmt.Printf("%v\n", l.GetDimensionNames())
Output:

[az go-lang]

func NewLatticeWithSeed

func NewLatticeWithSeed(seed int64, dims []string) (*Lattice, error)

NewLatticeWithSeed creates an N-dimensional Lattice for a given set of dimension names, where each dimension represents a meaningful availability axis. Seed is intended to be used as an application ID, so the same application can create consistent results across restarts.

func (*Lattice) AddEndpointsForSector

func (l *Lattice) AddEndpointsForSector(sec, ep []string) error

AddEndpointsForSector adds all of the end-points for that are associated with a particular sector. The order of the sector should match the order of the dimensions the lattice was initialized with.

Example
l, err := shuffle.NewLattice([]string{"az", "go-lang"})
if err != nil {
	fmt.Printf("unable to create a lattice: %v", err)
}

l.AddEndpointsForSector([]string{"us-east-1", "0.9"}, []string{"x", "y"})
l.AddEndpointsForSector([]string{"us-west-1", "1.1"}, []string{"a", "b"})

fmt.Printf("%v\n", l.GetDimensionNames())
fmt.Printf("%v\n", l.GetAllEndpoints())

e, err := l.GetEndpointsForSector([]string{"us-east-1", "0.9"})
if err != nil {
	fmt.Printf(
		"unable to fetch endpoints for sector %v: %v",
		[]string{"us-east-1", "0.9"}, err,
	)
}
fmt.Printf("%v\n", e)
Output:

[az go-lang]
[a b x y]
[x y]

func (*Lattice) GetAllCoordinates

func (l *Lattice) GetAllCoordinates() [][]string

GetAllCoordinates gets a list of all cells in the lattice.

func (*Lattice) GetAllEndpoints

func (l *Lattice) GetAllEndpoints() []string

GetAllEndpoints gets all of the end-points in the lattice.

func (*Lattice) GetDimensionName

func (l *Lattice) GetDimensionName(dNum int) string

GetDimensionName get the dimension name for a given numbered dimension.

func (*Lattice) GetDimensionNames

func (l *Lattice) GetDimensionNames() []string

GetDimensionNames gets the list of dimension names for a lattice.

func (*Lattice) GetDimensionSize

func (l *Lattice) GetDimensionSize(dName string) int

GetDimensionSize returns the number of discrete coordinates are there in a given dimension.

func (*Lattice) GetDimensionValues

func (l *Lattice) GetDimensionValues(dName string) []string

GetDimensionValues gets the set of values for a given dimension.

func (*Lattice) GetDimensionality

func (l *Lattice) GetDimensionality() map[string]int

GetDimensionality returns the number of dimensions a lattice has.

func (*Lattice) GetEndpointsForSector

func (l *Lattice) GetEndpointsForSector(sec []string) ([]string, error)

GetEndpointsForSector gets the endpoints in a particular sector.

func (*Lattice) SimpleShuffleShard

func (l *Lattice) SimpleShuffleShard(id []byte, epc int) (*Lattice, error)

SimpleShuffleShard implementation uses simple probabilistic hashing to compute shuffle shards. This function takes an existing lattice and generates a new sharded lattice for the given indentification and required number of endpoints with the sharded endpoints.

Example
l, err := shuffle.NewLattice([]string{"az", "go-lang"})
if err != nil {
	fmt.Printf("unable to create a lattice: %v", err)
}

l.AddEndpointsForSector([]string{"us-east-1", "0.9"}, []string{"x", "y"})
l.AddEndpointsForSector([]string{"us-east-1", "1.1"}, []string{"a", "b"})
l.AddEndpointsForSector([]string{"us-west-1", "0.9"}, []string{"c", "d"})
l.AddEndpointsForSector([]string{"us-west-1", "1.1"}, []string{"e", "f"})

s, err := l.SimpleShuffleShard([]byte{42}, 1)
if err != nil {
	fmt.Printf("unable to shard the lattice: %v", err)
}

// Should return a pair of endpoints.
fmt.Printf("%v\n", s.GetAllEndpoints())
Output:

func (*Lattice) SimulateFailure

func (l *Lattice) SimulateFailure(dName, dVal string) (*Lattice, error)

SimulateFailure simulates failure of a particular slice of cells in the lattice.

Example
l, err := shuffle.NewLattice([]string{"az", "go-lang"})
if err != nil {
	fmt.Printf("unable to create a lattice: %v", err)
}

l.AddEndpointsForSector([]string{"us-east-1", "0.9"}, []string{"x", "y"})
l.AddEndpointsForSector([]string{"us-west-1", "1.1"}, []string{"a", "b"})

fmt.Printf("%v\n", l.GetAllEndpoints())

s, err := l.SimulateFailure("az", "us-east-1")
if err != nil {
	fmt.Printf("unable to simulate failure for lattice: %v", err)
}
fmt.Printf("%v\n", s.GetAllEndpoints())
Output:

[a b x y]
[a b]

type StatefulSharder

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

func NewStatefulSharder

func NewStatefulSharder() *StatefulSharder

func (*StatefulSharder) StatefulShuffleShard

func (shard *StatefulSharder) StatefulShuffleShard(lattice *Lattice, endpointsPerCell, maximumOverlap int) (*Lattice, error)

Jump to

Keyboard shortcuts

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