hashing

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

https://github.com/lafikl/consistent/blob/master/consistent.go

Index

• Variables
• func SetReplicationFactor(factor int)
• 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) 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) ReadInternals(reader func(map[uint64]string, []uint64, map[string]*Host, 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

Variables

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

ErrNoHosts is an error for no hosts.

Functions

func SetReplicationFactor

func SetReplicationFactor(factor int)

SetReplicationFactor sets the replication factor for actor placement on vnodes.

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) 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) ReadInternals

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

ReadInternals returns the internal data structure of the consistent hash.

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
	AppID 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.