README
¶
ring
consistent hashing data structure
One Ring to rule them all, One Ring to find them, One Ring to bring them all and in the darkness bind them...
The type ring implements consistent hashing data structure to orchestrate the topology without the global coordinator in the distributed environment. The library is developed after Erlang's consistent hashing data structure, which has been battle tested by author in various contexts.
Inspiration
The concept of consistent hashing has been developed in the past to deal with load-balancing in a dynamic environment. It solves the resizing problem of traditional mod-n hashing technique so that only the k/N fraction of keys needs to be reallocated when topology is modified, while the traditional hashing causes entire remapping of key space. The practical adoption of consistent hashing into distributed systems has shown a need for stricter balancing of keys, therefore hashing schema has been enhanced with the concept of virtual nodes. In this schema, each node claims randomly multiple tokens. The tokens of all nodes are placed on the ring according to their values. Every two consecutive tokens frame the arc, which is claimed by the corresponding node. Virtual node partitioning schema works well for load balancing of CPU bound workload but suffers for storage bounded workload due to the randomness in key ranges as it has been demonstrated by Amazon Dynamo. Virtual nodes do not guarantee determinism on key range reallocation when topology is modified nor predictability of anti-entropy processes.
The ultimate consistent hashing uses unrelated algorithms for partition, allocation and routing. The hash address space 2ᵐ-1 is divided into Q equally sized shards. Each node claims about Q/N shards with the help of T pseudo-randomly assigned tokens. The tokens are mapped into the hash address space to claim governance of shards to the node. When a node leaves the system, its shards are consistently distributed to the remaining nodes. Similarly, when a node joins the system it "steals" shards from nodes in the system in consistent ways. The request routing procedure maps the key into the hash space to determine the shard and corresponding node.
Installing
The latest version of the library is available at main branch. All development, including new features and bug fixes, take place on the main branch using forking and pull requests as described in contribution guidelines. The stable version is available via Golang modules.
- Use
go getto retrieve the library and add it as dependency to your application.
go get -u github.com/fogfish/ring
- Import it in your code
import (
"github.com/fogfish/ring"
)
Quick Example
Here is a minimal example on creating an instance of the ring, assembling topology from individual nodes and then routing the requests. See the full example
package main
import (
"github.com/fogfish/ring"
)
func main() {
/*
create new ring instance with m=64, Q=8, T=8
*/
ringo := ring.New(ring.WithM64(), ring.WithQ(8), ring.WithT(8))
/*
when all nodes join the topology is following
ring: m=64, q=8, t=8
| [0, ffffffffffffffff]
| [ 18.54.73.101 113.181.90.103 102.190.90.78 140.93.207.103 92.106.122.149 ]
|
| 0: 1fffffffffffffff ⇒ 1 ab26472ec2ed62a [18.54.73.101]
| 1: 3fffffffffffffff ⇒ 0 228ad527296bd2d5 [113.181.90.103]
| 2: 5fffffffffffffff ⇒ 2 5949b7cc2ac07642 [140.93.207.103]
| 3: 7fffffffffffffff ⇒ 3 6c13f457b56728ec [18.54.73.101]
| 4: 9fffffffffffffff ⇒ 0 931fb3cd1fc272eb [18.54.73.101]
| 5: bfffffffffffffff ⇒ 0 a22176d726c38cb5 [102.190.90.78]
| 6: dfffffffffffffff ⇒ 1 d613972f28795b25 [140.93.207.103]
| 7: ffffffffffffffff ⇒ 0 f27d0004a29a8dff [140.93.207.103]
*/
ringo.Join("113.181.90.103")
/* ... */
ringo.Join("18.54.73.101")
/*
Lookup successor nodes for the key.
It returns list of primary & handoff nodes
Primary:
1. {ffffffffffffffff | 0 - 140.93.207.103}
2. {ffffffffffffffff | 1 - 18.54.73.101}
3. {ffffffffffffffff | 0 - 113.181.90.103}
Handoff:
- empty
*/
primary, handoff := ringo.SuccessorOf(3, "One ring to rule them all")
// Handoff node and its shards to other
ringo.Handoff("18.54.73.101")
// Permanently leaves the topology
ringo.Leave("18.54.73.101")
}
How To Contribute
The library is Apache 2.0 licensed and accepts contributions via GitHub pull requests:
- Fork it
- Create your feature branch (
git checkout -b my-new-feature) - Commit your changes (
git commit -am 'Added some feature') - Push to the branch (
git push origin my-new-feature) - Create new Pull Request
The build and testing process requires Go latest version.
Build and run in your development console.
git clone https://github.com/fogfish/ring
cd ring
go test
go test -run=^$ -bench=. -cpu 1
commit message
The commit message helps us to write a good release note, speed-up review process. The message should address two question what changed and why. The project follows the template defined by chapter Contributing to a Project of Git book.
bugs
If you experience any issues with the library, please let us know via GitHub issues. We appreciate detailed and accurate reports that help us to identity and replicate the issue.
License
Documentation
¶
Overview ¶
Copyright 2012 Dmitry Kolesnikov, All Rights Reserved
Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
Index ¶
- Variables
- type Handoff
- type Hash
- type Hashes
- type Node
- type Option
- type Primary
- type Ring
- func (ring *Ring) Address(key string) uint64
- func (ring *Ring) After(n uint64, addr uint64) []Node
- func (ring *Ring) AfterKey(n uint64, key string) []Node
- func (ring *Ring) Before(n uint64, addr uint64) []Node
- func (ring *Ring) BeforeKey(n uint64, key string) []Node
- func (ring *Ring) Debug() string
- func (ring *Ring) Handoff(node string) *Ring
- func (ring *Ring) Has(node string) bool
- func (ring *Ring) Join(node string) *Ring
- func (ring *Ring) Leave(node string) *Ring
- func (ring *Ring) Lookup(addr uint64) Node
- func (ring *Ring) LookupKey(key string) Node
- func (ring *Ring) Members() []string
- func (ring *Ring) Nodes() map[string][]Node
- func (ring *Ring) Shards() []Node
- func (ring *Ring) Size() int
- func (ring *Ring) SuccessorOf(n uint64, key string) (Primary, Handoff)
Constants ¶
This section is empty.
Variables ¶
Functions ¶
This section is empty.
Types ¶
type Option ¶
type Option func(ring *Ring)
Option for the ring structure
func WithM16 ¶
func WithM16() Option
WithM16 configures the ring param m=16, so that ring space is 2^m - 1
func WithM32 ¶
func WithM32() Option
WithM32 configures the ring param m=32, so that ring space is 2^m - 1
func WithM64 ¶
func WithM64() Option
WithM64 configures the ring param m=64, so that ring space is 2^m - 1
func WithM8 ¶
func WithM8() Option
WithM8 configures the ring param m=8, so that ring space is 2^m - 1
type Ring ¶
type Ring struct {
// contains filtered or unexported fields
}
Ring is consistent hashing data type.
func (*Ring) SuccessorOf ¶
SuccessorOf return N distinct nodes to route key. The list of nodes is split to primary and handoff replicas.
For each node it returns the address of shard hit by the key, the node identity, the rank of node identity and its address on the ring.
Source Files
Directories