README
¶
consistent
Go written consistent hashing package inspired by Google's "Consistent Hashing with Bounded Loads"
If you don't know the consistent hashing, please refer to Introducing Consistent Hashing, Teiva Harsanyi to learn about it!
References
- Consistent Hashing with Bounded Loads on Google Research Blog
- Improving load balancing with a new consistent-hashing algorithm on Vimeo Engineering Blog
- Consistent Hashing with Bounded Loads paper on arXiv
Install
Please run to install the package:
$ go get -u github.com/KeisukeYamashita/consistent
Configuration
type Config struct {
// Hasher is responsible for generating unsigned, 64 bit hash of provided byte slice.
Hasher Hasher
// Partition represents the number of partitions created on a ring.
// Partitions are used to divide the ring and assign bin and ball.
// Balls are distributed among partitions. Prime numbers are good to
// distribute keys uniformly. Select a big number if you have too many keys.
Partition int
// Bins are replicated on consistent hash ring.
// It's known as virtual nodes to uniform the distribution.
ReplicationFactor int
// LoadBalancingParameter is used to calculate average load.
// According to the Google paper, one or more bins will be adjusted so that they do not exceed a specific load.
// The maximum number of partitions are calculated by LoadBalancingParameter * (number of balls/number of bins).
LoadBalancingParameter float64
}
Usage
Contributions
All contributions are welcome, please file a issue or a pull request 🚀
License
Acknowledgements
This package was inspired heavily by these packages:
Thank you very much for open sourcing these hard work.
Documentation
¶
Index ¶
- Variables
- type Ball
- type Bin
- type Config
- type Consistent
- func (c *Consistent) Add(bin Bin) error
- func (c *Consistent) Delete(ball Ball) error
- func (c *Consistent) FindPartitionID(key []byte) PartitionID
- func (c *Consistent) GetBalls() []Ball
- func (c *Consistent) GetBallsByBin(bin Bin) ([]Ball, error)
- func (c *Consistent) GetBin(name string) (*Bin, error)
- func (c *Consistent) GetBins() []Bin
- func (c *Consistent) GetPartitionOwner(partID PartitionID) *Bin
- func (c *Consistent) LoadDistribution() map[string]float64
- func (c *Consistent) Locate(ball Ball) *Bin
- func (c *Consistent) MaximumLoad() float64
- func (c *Consistent) Remove(bin Bin) error
- type Hasher
- type PartitionID
Constants ¶
This section is empty.
Variables ¶
var ( //ErrInsufficientBins represents an error which means there are not enough bins to complete the task. ErrInsufficientBins = errors.New("insufficient bins") // ErrBallNotFound represents an error which means requested ball could not be found in consistent hash ring. ErrBallNotFound = errors.New("ball not found") // ErrBinNotFound represents an error which means requested bin could not be found in consistent hash ring. ErrBinNotFound = errors.New("bin not found") // ErrBinAlreadyExist represents an error which means requested bin already exists in the ring ErrBinAlreadyExist = errors.New("bin already exist") // ErrInsufficientPartitionCapacity represents an error which user needs to decrease partition count, increase bin count or increase load factor. ErrInsufficientPartitionCapacity = errors.New("not enough room to distribute partitions") )
Functions ¶
This section is empty.
Types ¶
type Ball ¶
type Ball interface {
// String returns the name of the ball.
String() string
}
Ball represents data to be placed on the ring. In most cases, it is a subsequent server for load balancing, data for sharding, etc but it can be anything unless it implements this interface.
type Bin ¶
type Bin struct {
Name string
PartitionIDs []PartitionID
}
Bin represents an entity that serves the balls. Usually it's a server but it can be anything.
type Config ¶
type Config struct {
// Hasher is responsible for generating unsigned, 64 bit hash of provided byte slice.
Hasher Hasher
// Partition represents the number of partitions created on a ring.
// Partitions are used to divide the ring and assign bin and ball.
// Balls are distributed among partitions. Prime numbers are good to
// distribute keys uniformly. Select a big number if you have too many keys.
Partition uint64 `validate:"required,min=1,max=18446744073709551614"`
// Bins are replicated on consistent hash ring.
// It's known as virtual nodes to uniform the distribution.
ReplicationFactor int `validate:"required,min=1"`
// LoadBalancingParameter is used to calculate average load.
// According to the Google paper, one or more bins will be adjusted so that they do not exceed a specific load.
// The maximum number of partitions are calculated by LoadBalancingParameter * (number of balls/number of bins).
LoadBalancingParameter float64 `validate:"required,gt=0"`
}
Config represents a configuration of the consistent hashing.
type Consistent ¶
type Consistent struct {
// contains filtered or unexported fields
}
Consistent represents the consistent hashing ring.
func New ¶
func New(cfg *Config, bins []Bin) (*Consistent, error)
New generates a new Consistent by passed config.
func (*Consistent) Add ¶
func (c *Consistent) Add(bin Bin) error
Add adds a new bin to the consistent hash ring. After adding the bin, it will recalculate the partitions.
func (*Consistent) Delete ¶
func (c *Consistent) Delete(ball Ball) error
Delete removes a ball from the ring.
func (*Consistent) FindPartitionID ¶
func (c *Consistent) FindPartitionID(key []byte) PartitionID
FindPartitionID returns partition id for given key.
func (*Consistent) GetBalls ¶
func (c *Consistent) GetBalls() []Ball
GetBalls returns all balls in the bin
func (*Consistent) GetBallsByBin ¶ added in v0.0.3
func (c *Consistent) GetBallsByBin(bin Bin) ([]Ball, error)
GetBallsByBin returns the balls associated with the Bin
func (*Consistent) GetBin ¶
func (c *Consistent) GetBin(name string) (*Bin, error)
GetBin returns a thread-safe copy of bins.
func (*Consistent) GetBins ¶
func (c *Consistent) GetBins() []Bin
GetBins returns a thread-safe copy of bins.
func (*Consistent) GetPartitionOwner ¶
func (c *Consistent) GetPartitionOwner(partID PartitionID) *Bin
GetPartitionOwner returns the owner of the given partition.
func (*Consistent) LoadDistribution ¶
func (c *Consistent) LoadDistribution() map[string]float64
LoadDistribution exposes load distribution of bins.
func (*Consistent) Locate ¶
func (c *Consistent) Locate(ball Ball) *Bin
Locate finds a home for given ball
func (*Consistent) MaximumLoad ¶
func (c *Consistent) MaximumLoad() float64
MaximumLoad exposes the current average load.
func (*Consistent) Remove ¶
func (c *Consistent) Remove(bin Bin) error
Remove removes a bin from the consistent hash ring.
Source Files