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 ¶
- type Lattice
- func (l *Lattice) AddEndpointsForSector(sec, ep []string) error
- func (l *Lattice) GetAllCoordinates() [][]string
- func (l *Lattice) GetAllEndpoints() []string
- func (l *Lattice) GetDimensionName(dNum int) string
- func (l *Lattice) GetDimensionNames() []string
- func (l *Lattice) GetDimensionSize(dName string) int
- func (l *Lattice) GetDimensionValues(dName string) []string
- func (l *Lattice) GetDimensionality() map[string]int
- func (l *Lattice) GetEndpointsForSector(sec []string) ([]string, error)
- func (l *Lattice) SimpleShuffleShard(id []byte, epc int) (*Lattice, error)
- func (l *Lattice) SimulateFailure(dName, dVal string) (*Lattice, error)
- type StatefulSharder
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 ¶
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 ¶
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 ¶
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 ¶
GetAllCoordinates gets a list of all cells in the lattice.
func (*Lattice) GetAllEndpoints ¶
GetAllEndpoints gets all of the end-points in the lattice.
func (*Lattice) GetDimensionName ¶
GetDimensionName get the dimension name for a given numbered dimension.
func (*Lattice) GetDimensionNames ¶
GetDimensionNames gets the list of dimension names for a lattice.
func (*Lattice) GetDimensionSize ¶
GetDimensionSize returns the number of discrete coordinates are there in a given dimension.
func (*Lattice) GetDimensionValues ¶
GetDimensionValues gets the set of values for a given dimension.
func (*Lattice) GetDimensionality ¶
GetDimensionality returns the number of dimensions a lattice has.
func (*Lattice) GetEndpointsForSector ¶
GetEndpointsForSector gets the endpoints in a particular sector.
func (*Lattice) SimpleShuffleShard ¶
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 ¶
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)