placement

Documentation

Overview

Package placement is an implementation of Consistent Hashing and Consistent Hashing With Bounded Loads.

https://en.wikipedia.org/wiki/Consistent_hashing

https://research.googleblog.com/2017/04/consistent-hashing-with-bounded-loads.html

Index

• Variables
• type Consistent
  • func NewConsistentHash() *Consistent
  • func NewFromExisting(hosts map[uint64]string, sortedSet []uint64, loadMap map[string]*Host) *Consistent
  • func (c *Consistent) Add(host, id string, port int64) bool
  • func (c *Consistent) Done(host string)
  • func (c *Consistent) Get(key string) (string, error)
  • func (c *Consistent) GetHost(key string) (*Host, error)
  • func (c *Consistent) GetInternals() (map[uint64]string, []uint64, map[string]*Host, int64)
  • func (c *Consistent) GetLeast(key string) (string, error)
  • func (c *Consistent) GetLoads() map[string]int64
  • func (c *Consistent) Hosts() (hosts []string)
  • func (c *Consistent) Inc(host string)
  • func (c *Consistent) MaxLoad() int64
  • func (c *Consistent) Remove(host string) bool
  • func (c *Consistent) UpdateLoad(host string, load int64)
• type ConsistentHashTables
  • func NewPlacementTables(version string, entries map[string]*Consistent) *ConsistentHashTables
• type Host
  • func NewHost(name, id string, load int64, port int64) *Host
• type Service
  • func NewPlacementService() *Service
  • func (p *Service) PerformTablesUpdate(hosts []daprinternal_pb.PlacementService_ReportDaprStatusServer, ...)
  • func (p *Service) ProcessHost(host *daprinternal_pb.Host)
  • func (p *Service) ProcessRemovedHost(id string)
  • func (p *Service) RemoveHost(srv daprinternal_pb.PlacementService_ReportDaprStatusServer)
  • func (p *Service) ReportDaprStatus(srv daprinternal_pb.PlacementService_ReportDaprStatusServer) error
  • func (p *Service) Run(port string)

Variables

var ErrNoHosts = errors.New("no hosts added")

ErrNoHosts is an error for no hosts

Types

type Consistent

type Consistent struct {
	sync.RWMutex
	// contains filtered or unexported fields
}

Consistent represents a data structure for consistent hashing

func NewConsistentHash

func NewConsistentHash() *Consistent

NewConsistentHash returns a new consistent hash

func NewFromExisting

func NewFromExisting(hosts map[uint64]string, sortedSet []uint64, loadMap map[string]*Host) *Consistent

NewFromExisting creates a new consistent hash from existing values

func (*Consistent) Add

func (c *Consistent) Add(host, id string, port int64) bool

Add adds a host with port to the table

func (*Consistent) Done

func (c *Consistent) Done(host string)

Done decrements the load of host by 1

should only be used with if you obtained a host with GetLeast

func (*Consistent) Get

func (c *Consistent) Get(key string) (string, error)

Get returns the host that owns `key`.

As described in https://en.wikipedia.org/wiki/Consistent_hashing

It returns ErrNoHosts if the ring has no hosts in it.

func (*Consistent) GetHost

func (c *Consistent) GetHost(key string) (*Host, error)

GetHost gets a host

func (*Consistent) GetInternals

func (c *Consistent) GetInternals() (map[uint64]string, []uint64, map[string]*Host, int64)

GetInternals returns the internal data structure of the consistent hash

func (*Consistent) GetLeast

func (c *Consistent) GetLeast(key string) (string, error)

GetLeast uses Consistent Hashing With Bounded loads

https://research.googleblog.com/2017/04/consistent-hashing-with-bounded-loads.html

to pick the least loaded host that can serve the key

It returns ErrNoHosts if the ring has no hosts in it.

func (*Consistent) GetLoads

func (c *Consistent) GetLoads() map[string]int64

GetLoads returns the loads of all the hosts

func (*Consistent) Hosts

func (c *Consistent) Hosts() (hosts []string)

Hosts return the list of hosts in the ring

func (*Consistent) Inc

func (c *Consistent) Inc(host string)

Inc increments the load of host by 1

should only be used with if you obtained a host with GetLeast

func (*Consistent) MaxLoad

func (c *Consistent) MaxLoad() int64

MaxLoad returns the maximum load of the single host which is: (total_load/number_of_hosts)*1.25 total_load = is the total number of active requests served by hosts for more info: https://research.googleblog.com/2017/04/consistent-hashing-with-bounded-loads.html

func (*Consistent) Remove

func (c *Consistent) Remove(host string) bool

Remove deletes host from the ring

func (*Consistent) UpdateLoad

func (c *Consistent) UpdateLoad(host string, load int64)

UpdateLoad sets the load of `host` to the given `load`

type ConsistentHashTables

type ConsistentHashTables struct {
	Version string
	Entries map[string]*Consistent
}

ConsistentHashTables is a table holding a map of consistent hashes with a given version

func NewPlacementTables

func NewPlacementTables(version string, entries map[string]*Consistent) *ConsistentHashTables

NewPlacementTables returns new stateful placement tables with a given version

type Host

type Host struct {
	Name   string
	Port   int64
	Load   int64
	DaprID string
}

Host represents a host of stateful entities with a given name, id, port and load

func NewHost

func NewHost(name, id string, load int64, port int64) *Host

NewHost returns a new host

type Service

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

Service updates the Dapr runtimes with distributed hash tables for stateful entities.

func NewPlacementService

func NewPlacementService() *Service

NewPlacementService returns a new placement service

func (*Service) PerformTablesUpdate

func (p *Service) PerformTablesUpdate(hosts []daprinternal_pb.PlacementService_ReportDaprStatusServer,
	options placementOptions)

PerformTablesUpdate updates the connected dapr runtimes using a 3 stage commit. first it locks so no further dapr can be taken it then proceeds to update and then unlock once all runtimes have been updated

func (*Service) ProcessHost

func (p *Service) ProcessHost(host *daprinternal_pb.Host)

ProcessHost updates the distributed has list based on a new host and its entities

func (*Service) ProcessRemovedHost

func (p *Service) ProcessRemovedHost(id string)

ProcessRemovedHost removes a host from the hash table

func (*Service) RemoveHost

func (p *Service) RemoveHost(srv daprinternal_pb.PlacementService_ReportDaprStatusServer)

RemoveHost removes the host from the hosts list

func (*Service) ReportDaprStatus

func (p *Service) ReportDaprStatus(srv daprinternal_pb.PlacementService_ReportDaprStatusServer) error

ReportDaprStatus gets a heartbeat report from different Dapr hosts

func (*Service) Run

func (p *Service) Run(port string)

Run starts the placement service gRPC server