ring

Documentation

Overview

Package ring implements a simple ring CRDT.

Index

• Variables
• type Ring
  • func New(start, end address.Address, peer router.PeerName) *Ring
  • func (r *Ring) ChoosePeerToAskForSpace(start, end address.Address) (result router.PeerName, err error)
  • func (r *Ring) ClaimForPeers(peers []router.PeerName)
  • func (r *Ring) Contains(addr address.Address) bool
  • func (r *Ring) Empty() bool
  • func (r *Ring) FprintWithNicknames(w io.Writer, m map[router.PeerName]string)
  • func (r *Ring) GrantRangeToHost(start, end address.Address, peer router.PeerName)
  • func (r *Ring) Merge(gossip Ring) error
  • func (r *Ring) OwnedRanges() (result []address.Range)
  • func (r *Ring) Owner(token address.Address) router.PeerName
  • func (r *Ring) PeerNames() map[router.PeerName]struct{}
  • func (r *Ring) PickPeerForTransfer() router.PeerName
  • func (r *Ring) ReportFree(freespace map[address.Address]address.Offset)
  • func (r *Ring) String() string
  • func (r *Ring) Transfer(from, to router.PeerName) ([]address.Range, error)

Variables

var (
	ErrNotSorted        = errors.New("Ring not sorted")
	ErrTokenRepeated    = errors.New("Token appears twice in ring")
	ErrTokenOutOfRange  = errors.New("Token is out of range")
	ErrDifferentSubnets = errors.New("IP Allocator with different subnet detected")
	ErrNewerVersion     = errors.New("Received new version for entry I own!")
	ErrInvalidEntry     = errors.New("Received invalid state update!")
	ErrEntryInMyRange   = errors.New("Received new entry in my range!")
	ErrNoFreeSpace      = errors.New("No free space found!")
	ErrInvalidTimeout   = errors.New("dt must be greater than 0")
	ErrNotFound         = errors.New("No entries for peer found")
)

Errors returned by Merge

Types

type Ring

type Ring struct {
	Start, End address.Address // [min, max) tokens in this ring.  Due to wrapping, min == max (effectively)
	Peer       router.PeerName // name of peer owning this ring instance
	Entries    entries         // list of entries sorted by token
}

Ring represents the ring itself

func New

func New(start, end address.Address, peer router.PeerName) *Ring

New creates an empty ring belonging to peer.

func (*Ring) ChoosePeerToAskForSpace

func (r *Ring) ChoosePeerToAskForSpace(start, end address.Address) (result router.PeerName, err error)

ChoosePeerToAskForSpace chooses a weighted-random peer to ask for space in the range [start, end). Assumes start<end.

func (*Ring) ClaimForPeers

func (r *Ring) ClaimForPeers(peers []router.PeerName)

ClaimForPeers claims the entire ring for the array of peers passed in. Only works for empty rings.

func (*Ring) Contains

func (r *Ring) Contains(addr address.Address) bool

Contains returns true if addr is in this ring

func (*Ring) Empty

func (r *Ring) Empty() bool

Empty returns true if the ring has no entries

func (*Ring) FprintWithNicknames

func (r *Ring) FprintWithNicknames(w io.Writer, m map[router.PeerName]string)

func (*Ring) GrantRangeToHost

func (r *Ring) GrantRangeToHost(start, end address.Address, peer router.PeerName)

GrantRangeToHost modifies the ring such that range [start, end) is assigned to peer. This may insert up to two new tokens. Preconditions: - start < end - [start, end) must be owned by the calling peer

func (*Ring) Merge

func (r *Ring) Merge(gossip Ring) error

Merge the given ring into this ring and return any new ranges added

func (*Ring) OwnedRanges

func (r *Ring) OwnedRanges() (result []address.Range)

OwnedRanges returns slice of Ranges, ordered by IP, indicating which ranges are owned by this peer. Will split ranges which span 0 in the ring.

func (*Ring) Owner

func (r *Ring) Owner(token address.Address) router.PeerName

Owner returns the peername which owns the range containing addr

func (*Ring) PeerNames

func (r *Ring) PeerNames() map[router.PeerName]struct{}

Get the set of PeerNames mentioned in the ring

func (*Ring) PickPeerForTransfer

func (r *Ring) PickPeerForTransfer() router.PeerName

func (*Ring) ReportFree

func (r *Ring) ReportFree(freespace map[address.Address]address.Offset)

ReportFree is used by the allocator to tell the ring how many free ips are in a given range, so that ChoosePeerToAskForSpace can make more intelligent decisions.

func (*Ring) String

func (r *Ring) String() string

func (*Ring) Transfer

func (r *Ring) Transfer(from, to router.PeerName) ([]address.Range, error)

Transfer will mark all entries associated with 'from' peer as owned by 'to' peer and return ranges indicating the new space we picked up