ring

package module
v0.0.0-...-76a793e Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 6, 2018 License: BSD-3-Clause Imports: 10 Imported by: 65

README

Ring

Development Repository

Experimental: No stable version of this package yet exists; it is still in early development.

Package ring provides a way to distribute replicas of partitioned items to nodes.

An example would be a distributed storage system, storing duplicate copies of each file on different drives, servers, or even data centers based on the assignments given by the Ring.

If you're not entirely sure what consistent hashing is, reading Basic Hash Ring might help.

API Documentation
Basic Hash Ring
Partition Ring vs. Hash Ring

Other interesting ideas in this space:
Jump consistent hashing - dgryski implementation also dgryski shared key-value store
Multi-probe consistent hashing - dgryski implementation
GreenCHT replication scheme

This is the latest development area for the package.
Eventually a stable version of the package will be established but, for now, all things about this package are subject to change.

Copyright See AUTHORS. All rights reserved.
Use of this source code is governed by a BSD-style
license that can be found in the LICENSE file.

Documentation

Overview

Package ring provides a way to distribute replicas of partitioned items to nodes.

An example would be a distributed storage system, storing duplicate copies of each file on different drives, servers, or even data centers based on the assignments given by the Ring.

See https://github.com/gholt/ring/blob/master/BASIC_HASH_RING.md for a introduction to consistent hashing and hashing rings.

There is a lower-level package github.com/gholt/ring/lowring that underpins this package. It is provided in case you don't need the extra layer this package provides or you would like to create your own extra layer.

Terms Used With This Package

Node: A single unit within a distributed system. For example, a server or a single drive within a server.

Partition: A numeric value from a range of values. Replicas of these partitions are assigned to nodes to indicate each node's responsibilities, such as which data to store or which requests to process. Mapping these data items or requests to partitions is usually done by hashing the name or some other identifier to obtain a number and then using the modulus operator with the overall partition count.

Replica: A copy of a partition. Object storage systems often use 3 replicas, for example.

Ring: Stores the assignments of replicas of partitions to nodes.

Builder: A program to build and maintain a ring.

Capacity: The relative size of a node as compared to other nodes. For example, the amount of disk space available on the node.

Desire: The number of additional, or fewer, partitions a node would like to have assigned in order to reach a balance with the rest of the nodes in a ring.

Tier: Represents the relationship of nodes to one another. For example, a geographic tier might have two values, east and west, and each node would be associated with one of those regions. There can be multiple levels of tiers, such as disk, server, zone, datacenter, region, etc. See the Example (Tiers) for a more in-depth code discussion.

Last Moved: The record of when a given replica of a partition was last reassigned to a different node. The builder uses this information restrict future movements of that replica and of the other replicas for that partition. For example, it might only move 2 of 5 replicas of a partition within an hour, unless absolutely necessary, such as a failed node.

What About Other Distributed Ring Algorithms

Each has their strengths and weaknesses. This package uses more memory than many other ring implementations and it is slower to create and modify the ring. But, it is usually much faster to use once loaded and provides precise node placements. https://github.com/gholt/ring/blob/master/PARTITION_RING_VS_HASH_RING.md has more discussion on the trade offs.

Other interesting ideas in this space:

Amazon's original 2007 Dynamo paper - http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf

Jump consistent hashing - http://arxiv.org/abs/1406.2294 - dgryski implementation https://github.com/dgryski/go-jump - also dgryski shared key-value store https://github.com/dgryski/go-shardedkv

Multi-probe consistent hashing http://arxiv.org/pdf/1505.00062.pdf - dgryski implementation https://github.com/dgryski/go-mpchash

GreenCHT replication scheme http://storageconference.us/2015/Papers/16.Zhao.pdf

Examples For This Package

Below are examples for overall usage of this package, and more in-depth discussions as well. If you're directly reading the code, all the examples are in files named *example_test.go

Example (FromBasicHashRingDocument) 
package main

import (
	"fmt"
	"hash/fnv"
	"math/rand"
	"time"

	"github.com/gholt/ring/lowring"
)

func main() {
	hash := func(x int) uint64 {
		hasher := fnv.New64a()
		hasher.Write([]byte(fmt.Sprintf("%d", x)))
		return hasher.Sum64()
	}
	randIntn := rand.New(rand.NewSource(0)).Intn

	const ITEMS = 1000000
	const NODES = 100

	r := lowring.New(1)
	for n := 0; n < NODES; n++ {
		r.AddNode(1, 0)
	}
	r.Rebalance(randIntn)
	// Copy the essential ring data
	ring1 := make([][]lowring.Node, len(r.ReplicaToPartitionToNode))
	for replica, partitionToNode := range r.ReplicaToPartitionToNode {
		ring1[replica] = make([]lowring.Node, len(partitionToNode))
		copy(ring1[replica], partitionToNode)
	}

	partitionCount1 := uint64(len(ring1[0]))
	countPerNode := make([]int, NODES)
	for i := 0; i < ITEMS; i++ {
		n := ring1[0][hash(i)%partitionCount1]
		countPerNode[n]++
	}
	min := ITEMS
	max := 0
	for n := 0; n < NODES; n++ {
		if countPerNode[n] < min {
			min = countPerNode[n]
		}
		if countPerNode[n] > max {
			max = countPerNode[n]
		}
	}
	t := ITEMS / NODES
	fmt.Printf("%d to %d assignments per node, target was %d.\n", min, max, t)
	fmt.Printf("That's %.02f%% under and %.02f%% over.\n",
		float64(t-min)/float64(t)*100, float64(max-t)/float64(t)*100)

	r.AddNode(1, 0)
	// Reset wait time restrictions
	r.Rebalanced = r.Rebalanced.Add(-(time.Duration(r.ReassignmentWait) * time.Minute))
	r.Rebalance(randIntn)
	// Copy the essential ring data
	ring2 := make([][]lowring.Node, len(r.ReplicaToPartitionToNode))
	for replica, partitionToNode := range r.ReplicaToPartitionToNode {
		ring2[replica] = make([]lowring.Node, len(partitionToNode))
		copy(ring2[replica], partitionToNode)
	}

	partitionCount2 := uint64(len(ring2[0]))
	moved := 0
	for i := 0; i < ITEMS; i++ {
		h := hash(i)
		n1 := ring1[0][h%partitionCount1]
		n2 := ring2[0][h%partitionCount2]
		if n1 != n2 {
			moved++
		}
	}
	fmt.Printf("%d items moved, %.02f%%.\n",
		moved, float64(moved)/float64(ITEMS)*100)

}

Output:

9554 to 10289 assignments per node, target was 10000.
That's 4.46% under and 2.89% over.
9815 items moved, 0.98%.
Example (GroupTiers) 
package main

import (
	"fmt"

	"github.com/gholt/ring"
)

func main() {
	fmt.Println("Group tiers can be confusing, so let's work with a detailed example.")
	fmt.Println("We are going to have two servers, each with two disk drives.")
	fmt.Println("The disk drives are going to be represented by the nodes themselves.")
	fmt.Println("The servers will be represented by groups.")
	fmt.Println("By defining groups, we can tell the Builder to build rings with replicas assigned as far apart as possible, while keeping the whole Ring in balance.")
	fmt.Println("So let's define and build our ring; we'll use two replicas to start with...")
	builder := ring.NewBuilder(2)
	builder.SetMaxPartitionCount(2) // Just to keep the output simpler
	for _, server := range []string{"ServerA", "ServerB"} {
		group := builder.AddGroup(server, nil)
		for _, disk := range []string{"1stDisk", "2ndDisk"} {
			builder.AddNode(disk, 1, group)
		}
	}
	builder.Rebalance()
	rring := builder.Ring()
	printRing := func(rring *ring.Ring) {
		fmt.Println("Here are the ring assignments: partitions horizontally, replicas vertically:")
		fmt.Print("` ")
		for partition := 0; partition < rring.PartitionCount(); partition++ {
			fmt.Print(fmt.Sprintf("  -------P%d------", partition))
		}
		fmt.Println()
		for replica := 0; replica < rring.ReplicaCount(); replica++ {
			fmt.Print(fmt.Sprintf("R%d", replica))
			for partition := 0; partition < rring.PartitionCount(); partition++ {
				node := rring.KeyNodes(partition)[replica]
				fmt.Print("  " + node.Group().Info() + ":" + node.Info())
			}
			fmt.Println()
		}
	}
	printRing(rring)
	// `   -------P0------  -------P1------
	// R0  ServerA:1stDisk  ServerB:2ndDisk
	// R1  ServerB:1stDisk  ServerA:2ndDisk
	fmt.Println("Note that it assigned each replica of a partition to a distinct server.")
	fmt.Println("The node info (disk names) happened to be the same but it doesn't matter since they are on different servers.")
	fmt.Println()
	fmt.Println("Let's up the replica count to 3, where we know it will have to assign multiple replicas to a single server...")
	builder = ring.NewBuilder(3)
	builder.SetMaxPartitionCount(4) // Just to keep the output simpler
	for _, server := range []string{"ServerA", "ServerB"} {
		group := builder.AddGroup(server, nil)
		for _, disk := range []string{"1stDisk", "2ndDisk"} {
			builder.AddNode(disk, 1, group)
		}
	}
	builder.Rebalance()
	rring = builder.Ring()
	printRing(rring)
	// `   -------P0------  -------P1------  -------P2------  -------P3------
	// R0  ServerA:1stDisk  ServerB:2ndDisk  ServerA:2ndDisk  ServerB:1stDisk
	// R1  ServerB:1stDisk  ServerA:1stDisk  ServerB:2ndDisk  ServerA:2ndDisk
	// R2  ServerA:2ndDisk  ServerB:1stDisk  ServerA:1stDisk  ServerB:2ndDisk
	fmt.Println("So now it ended up using servers twice within the same partition, but note that it made sure to pick distinct drives for each replica at least.")
	fmt.Println()
	fmt.Println("Let's get more complicated and define another tier of groups; we'll call it the region tier.")
	fmt.Println("To do this, we simply create the new region groups and set them as the parents of the server groups.")
	fmt.Println("We'll assign our first two servers to the East region, and add two more servers in the Cent region, and even two more servers in the West region.")
	builder = ring.NewBuilder(3)
	builder.SetMaxPartitionCount(4) // Just to keep the output simpler
	for _, region := range []string{"East", "Cent", "West"} {
		regionGroup := builder.AddGroup(region, nil)
		for _, server := range []string{"ServerA", "ServerB"} {
			serverGroup := builder.AddGroup(server, regionGroup)
			for _, disk := range []string{"1stDisk", "2ndDisk"} {
				builder.AddNode(disk, 1, serverGroup)
			}
		}
	}
	builder.Rebalance()
	rring = builder.Ring()
	fmt.Println("Here are the ring assignments: partitions horizontally, replicas vertically:")
	// `   ---------P0---------  ---------P1---------  ---------P2---------  ---------P3---------
	// R0  East:ServerA:1stDisk  Cent:ServerB:2ndDisk  West:ServerB:2ndDisk  East:ServerB:1stDisk
	// R1  Cent:ServerA:1stDisk  East:ServerA:2ndDisk  Cent:ServerA:2ndDisk  West:ServerB:1stDisk
	// R2  West:ServerA:1stDisk  West:ServerA:2ndDisk  East:ServerB:2ndDisk  Cent:ServerB:1stDisk
	fmt.Print("` ")
	for partition := 0; partition < rring.PartitionCount(); partition++ {
		fmt.Print(fmt.Sprintf("  ---------P%d---------", partition))
	}
	fmt.Println()
	for replica := 0; replica < rring.ReplicaCount(); replica++ {
		fmt.Print(fmt.Sprintf("R%d", replica))
		for partition := 0; partition < rring.PartitionCount(); partition++ {
			node := rring.KeyNodes(partition)[replica]
			fmt.Print("  " + node.Group().Parent().Info() + ":" + node.Group().Info() + ":" + node.Info())
		}
		fmt.Println()
	}
	fmt.Println("So now you can see it assigned replicas in distinct regions before worrying about the lower tiers.")

}

Output:

Group tiers can be confusing, so let's work with a detailed example.
We are going to have two servers, each with two disk drives.
The disk drives are going to be represented by the nodes themselves.
The servers will be represented by groups.
By defining groups, we can tell the Builder to build rings with replicas assigned as far apart as possible, while keeping the whole Ring in balance.
So let's define and build our ring; we'll use two replicas to start with...
Here are the ring assignments: partitions horizontally, replicas vertically:
`   -------P0------  -------P1------
R0  ServerA:1stDisk  ServerB:2ndDisk
R1  ServerB:1stDisk  ServerA:2ndDisk
Note that it assigned each replica of a partition to a distinct server.
The node info (disk names) happened to be the same but it doesn't matter since they are on different servers.

Let's up the replica count to 3, where we know it will have to assign multiple replicas to a single server...
Here are the ring assignments: partitions horizontally, replicas vertically:
`   -------P0------  -------P1------  -------P2------  -------P3------
R0  ServerA:1stDisk  ServerB:2ndDisk  ServerA:2ndDisk  ServerB:1stDisk
R1  ServerB:1stDisk  ServerA:1stDisk  ServerB:2ndDisk  ServerA:2ndDisk
R2  ServerA:2ndDisk  ServerB:1stDisk  ServerA:1stDisk  ServerB:2ndDisk
So now it ended up using servers twice within the same partition, but note that it made sure to pick distinct drives for each replica at least.

Let's get more complicated and define another tier of groups; we'll call it the region tier.
To do this, we simply create the new region groups and set them as the parents of the server groups.
We'll assign our first two servers to the East region, and add two more servers in the Cent region, and even two more servers in the West region.
Here are the ring assignments: partitions horizontally, replicas vertically:
`   ---------P0---------  ---------P1---------  ---------P2---------  ---------P3---------
R0  East:ServerA:1stDisk  Cent:ServerB:2ndDisk  West:ServerB:2ndDisk  East:ServerB:1stDisk
R1  Cent:ServerA:1stDisk  East:ServerA:2ndDisk  Cent:ServerA:2ndDisk  West:ServerB:1stDisk
R2  West:ServerA:1stDisk  West:ServerA:2ndDisk  East:ServerB:2ndDisk  Cent:ServerB:1stDisk
So now you can see it assigned replicas in distinct regions before worrying about the lower tiers.
Example (Overview) 
package main

import (
	"fmt"

	"github.com/gholt/ring"
)

func main() {
	// We'll create a new builder for a ring with three replicas:
	builder := ring.NewBuilder(3)
	// And we'll add four nodes we'll label ABCD:
	for n := 'A'; n <= 'D'; n++ {
		builder.AddNode(string(n), 1, nil)
	}
	// Generate the ring:
	builder.Rebalance()
	rring := builder.Ring()
	// Print out the ring assignments: partitions horizontally, replicas vertically:
	// `  P0 P1 P2 P3
	// R0  A  B  C  D
	// R1  B  A  D  C
	// R2  D  C  A  B
	fmt.Print("` ")
	for partition := 0; partition < rring.PartitionCount(); partition++ {
		fmt.Print(fmt.Sprintf(" P%d", partition))
	}
	fmt.Println()
	for replica := 0; replica < rring.ReplicaCount(); replica++ {
		fmt.Print(fmt.Sprintf("R%d", replica))
		for partition := 0; partition < rring.PartitionCount(); partition++ {
			fmt.Print("  " + rring.KeyNodes(partition)[replica].Info())
		}
		fmt.Println()
	}
}

Output:

`  P0 P1 P2 P3
R0  A  B  C  D
R1  B  A  D  C
R2  D  C  A  B

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Builder 

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

Builder will create and maintain rings.

func NewBuilder 

func NewBuilder(replicaCount int) *Builder

NewBuilder creates a new builder with the initial replica count given.

func UnmarshalBuilder 

func UnmarshalBuilder(b io.Reader) (*Builder, error)

UnmarshalBuilder returns a builder based on the JSON+binary encoded information read from the io.Reader, presumably previously written by the builder's Marshal method.

Example 
package main

import (
	"bytes"
	"fmt"

	"github.com/gholt/ring"
)

func main() {
	// Build something to marshal...
	b1 := ring.NewBuilder(2)
	b1.AddNode("Node One", 1, nil)
	b1.AddNode("Node Two", 1, nil)
	b1.Rebalance()
	// And marshal the builder...
	var buf bytes.Buffer
	if err := b1.Marshal(&buf); err != nil {
		panic(err)
	}
	// So we can show how to unmarshal it...
	b2, err := ring.UnmarshalBuilder(&buf)
	if err != nil {
		panic(err)
	}
	// And just do some checks to show they're the same...
	if !b1.Rebalanced().Equal(b2.Rebalanced()) {
		panic("")
	}
	if b1.ReplicaCount() != b2.ReplicaCount() {
		panic(fmt.Sprintln(b1.ReplicaCount(), b2.ReplicaCount()))
	}
	if b1.PartitionCount() != b2.PartitionCount() {
		panic("")
	}
	if b1.ReassignmentWait() != b2.ReassignmentWait() {
		panic("")
	}
	if b1.MaxReplicaReassignableCount() != b2.MaxReplicaReassignableCount() {
		panic("")
	}
	if b1.MaxPartitionCount() != b2.MaxPartitionCount() {
		panic("")
	}
	ns1 := b1.Nodes()
	ns2 := b2.Nodes()
	if len(ns1) != len(ns2) {
		panic("")
	}
	for i := 0; i < len(ns1); i++ {
		if ns1[i].Capacity() != ns2[i].Capacity() {
			panic("")
		}
		if ns1[i].Info() != ns2[i].Info() {
			panic("")
		}
	}
	// And compare their rings for equality...
	r1 := b1.Ring()
	r2 := b2.Ring()
	if !r1.Rebalanced().Equal(r2.Rebalanced()) {
		panic("")
	}
	if r1.ReplicaCount() != r2.ReplicaCount() {
		panic("")
	}
	if r1.PartitionCount() != r2.PartitionCount() {
		panic("")
	}
	compareNodeSlices := func(ns1, ns2 []*ring.Node) {
		if len(ns1) != len(ns2) {
			panic("")
		}
		for i := 0; i < len(ns1); i++ {
			if ns1[i].Capacity() != ns2[i].Capacity() {
				panic("")
			}
			if ns1[i].Info() != ns2[i].Info() {
				panic("")
			}
		}
	}
	compareNodeSlices(r1.Nodes(), r2.Nodes())
	for partition := 0; partition < r1.PartitionCount(); partition++ {
		compareNodeSlices(r1.KeyNodes(partition), r2.KeyNodes(partition))
	}
	fmt.Println("They look the same!")
}

Output:

They look the same!

func (*Builder) AddGroup 

func (b *Builder) AddGroup(info string, parent *BuilderGroup) *BuilderGroup

AddGroup adds another group to the builder. Info is a user-defined string and is not used directly by the builder. The parent group offers a way to tier groups; the builder will do its best to keep similar assignments in dissimilar groups at each tier level. The parent may be nil. Cycles are not allowed, where the parent of a group would end up being a child of the same group.

func (*Builder) AddNode 

func (b *Builder) AddNode(info string, capacity int, group *BuilderGroup) *BuilderNode

AddNode adds another node to the builder. Info is a user-defined string and is not used directly by the builder. Capacity specifies, relative to other nodes, how many assignments the node should have. The group indicates which group the node is in; the builder will do its best to keep similar assignments in dissimilar groups. The group may be nil.

func (*Builder) Assign 

func (b *Builder) Assign(replica, partition int, node *BuilderNode)

Assign will override the current builder's assignment and set a specific replica of a partition to a specific node. This is mostly just useful for testing, as future calls to Rebalance may move this assignment.

func (*Builder) AssignmentCount 

func (b *Builder) AssignmentCount() int

AssignmentCount returns the number of assignments this builder will make; it is the replica count * the partition count.

func (*Builder) Groups 

func (b *Builder) Groups() []*BuilderGroup

Groups returns a slice of all the groups in use by the builder.

func (*Builder) IsMoving 

func (b *Builder) IsMoving(replica, partition int) bool

IsMoving returns true if the specific replica of the partition is currently in "reassignment wait", where a recent rebalance had reassigned the replica to a different node and so is giving time for the data to be moved.

func (*Builder) KeyNodes 

func (b *Builder) KeyNodes(key int) []*BuilderNode

KeyNodes returns the nodes responsible for the key given. There will be on node for each replica; in other words: len(b.KeyNodes(k)) == b.ReplicaCount().

func (*Builder) Marshal 

func (b *Builder) Marshal(w io.Writer) error

Marshal will write a JSON+binary encoded version of its contents to the io.Writer. You can use UnmarshalBuilder to read it back later.

Example 
package main

import (
	"bytes"
	"fmt"

	"github.com/gholt/ring"
)

func main() {
	// Build something to marshal...
	b := ring.NewBuilder(2)
	b.AddNode("Node One", 1, nil)
	b.AddNode("Node Two", 1, nil)
	b.Rebalance()
	// And marshal it...
	var buf bytes.Buffer
	if err := b.Marshal(&buf); err != nil {
		panic(err)
	}
	fmt.Println(len(buf.Bytes()), "bytes written")
	fmt.Println(string(buf.Bytes()[:241]), "...")
	// Note that even though the beginning is just JSON, there is trailing
	// binary for the larger data sets that JSON just isn't suited for.

}

Output:

333 bytes written
{"MarshalVersion":0,"NodeType":16,"ReplicaCount":2,"PartitionCount":2,"Nodes":[{"Info":"Node One","Capacity":1,"Group":0},{"Info":"Node Two","Capacity":1,"Group":0}],"Groups":[{"Info":"","Parent":0}],"MaxPartitionCount":8388608,"Rebalanced": ...

func (*Builder) MaxPartitionCount 

func (b *Builder) MaxPartitionCount() int

MaxPartitionCount returns the maximum partition count the builder will auto-grow to.

func (*Builder) MaxReplicaReassignableCount 

func (b *Builder) MaxReplicaReassignableCount() int

MaxReplicaReassignableCount returns the maximum number of replicas of a partition the builder will set "in motion" during the reassignment wait period.

func (*Builder) MovingAssignmentCount 

func (b *Builder) MovingAssignmentCount() int

MovingAssignmentCount returns the number of assignments that are currently "in motion". If you were to call IsMoving for every replica of every partition and count the true responses, that would equal the MovingAssignmentCount.

func (*Builder) Nodes 

func (b *Builder) Nodes() []*BuilderNode

Nodes returns a slice of all the nodes in the builder.

func (*Builder) PartitionCount 

func (b *Builder) PartitionCount() int

PartitionCount returns the current partition count for the builder.

func (*Builder) PretendElapsed 

func (b *Builder) PretendElapsed(d time.Duration)

PretendElapsed is mostly used for testing and will make the builder pretend the time duration has elapsed, usually freeing up time based reassignment restrictions.

func (*Builder) ReassignmentWait 

func (b *Builder) ReassignmentWait() time.Duration

ReassignmentWait is the time duration the builder will wait after making an assignment before considering reassigning that same data.

func (*Builder) Rebalance 

func (b *Builder) Rebalance()

Rebalance analyzes all information and makes assignments to nodes as best as it can.

func (*Builder) Rebalanced 

func (b *Builder) Rebalanced() time.Time

Rebalanced returns the time the builder last had Rebalance called.

func (*Builder) ReplicaCount 

func (b *Builder) ReplicaCount() int

ReplicaCount returns the current replica count of the builder.

func (*Builder) ReplicaPartitionNode 

func (b *Builder) ReplicaPartitionNode(replica, partition int) *BuilderNode

ReplicaPartitionNode returns the node responsible for a specific replica of a partition.

func (*Builder) Ring 

func (b *Builder) Ring() *Ring

Ring returns an immutable copy of the assignment information contained in the builder.

func (*Builder) SetMaxPartitionCount 

func (b *Builder) SetMaxPartitionCount(v int)

SetMaxPartitionCount sets the maximum partition count the builder will auto-grow to.

func (*Builder) SetMaxReplicaReassignableCount 

func (b *Builder) SetMaxReplicaReassignableCount(v int)

SetMaxReplicaReassignableCount sets the maximum number of replicas of a partition the builder will set "in motion" during the reassignment wait period.

For a full replica use case, you probably want to set this to no more than one less of the majority of replicas so that a majority are always in place at any given time.

For an erasure coding use case, you probably want to set this to no more than the number of parity shards so that there are always enough shards in place at any given time.

func (*Builder) SetReassignmentWait 

func (b *Builder) SetReassignmentWait(v time.Duration)

SetReassignmentWait sets the time duration the builder will wait after making an assignment before considering reassigning that same data.

func (*Builder) SetReplicaCount 

func (b *Builder) SetReplicaCount(v int)

SetReplicaCount changes the replica count of the builder. Lowering the replica count will simply discard the higher replicas. Raising the replica count will create new higher replicas that will be completely unassigned and will require a call to Rebalance to become assigned.

type BuilderGroup 

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

BuilderGroup is a group within a builder; a group is a collection of nodes, and perhaps other groups.

func (*BuilderGroup) AddGroup 

func (g *BuilderGroup) AddGroup(info string) *BuilderGroup

AddGroup adds a new group to the associated builder with this group set as the new group's parent. Info is a user-defined string and is not used directly by the builder.

func (*BuilderGroup) AddNode 

func (g *BuilderGroup) AddNode(info string, capacity int) *BuilderNode

AddNode will create a new node in the associated builder with this group set as the node's parent. Info is a user-defined string and is not used directly by the builder. Capacity specifies, relative to other nodes, how many assignments the node should have.

func (*BuilderGroup) Groups 

func (g *BuilderGroup) Groups() []*BuilderGroup

Groups returns the slice of groups that are the direct children of this group.

func (*BuilderGroup) Info 

func (g *BuilderGroup) Info() string

Info returns the associated info string for the group; this is user-defined and not used directly by the builder.

func (*BuilderGroup) Nodes 

func (g *BuilderGroup) Nodes() []*BuilderNode

Nodes returns the slice of nodes within this group and all its child groups.

func (*BuilderGroup) Parent 

func (g *BuilderGroup) Parent() *BuilderGroup

Parent returns the parent group, or nil if there is no parent, of the group.

func (*BuilderGroup) SetInfo 

func (g *BuilderGroup) SetInfo(v string)

SetInfo sets the associated info string for the group; this is user-defined and not used directly by the builder.

func (*BuilderGroup) SetParent 

func (g *BuilderGroup) SetParent(v *BuilderGroup)

SetParent sets the parent group of this group; it may be nil to indicate this group is a top-level group.

type BuilderNode 

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

BuilderNode is a node within a builder; a node represents a single assignment target of replicas of partitions, such as a single disk in a distributed storage system.

func (*BuilderNode) Assign 

func (n *BuilderNode) Assign(replica, partition int)

Assign will override the current builder's assignment and set a specific replica of a partition to this specific node. This is mostly just useful for testing, as future calls to Rebalance may move this assignment.

func (*BuilderNode) Capacity 

func (n *BuilderNode) Capacity() int

Capacity specifies, relative to other nodes, how many assignments the node should have.

func (*BuilderNode) Group 

func (n *BuilderNode) Group() *BuilderGroup

Group returns the parent group of the node; it may return nil if there is no parent group.

func (*BuilderNode) Info 

func (n *BuilderNode) Info() string

Info returns the user-defined info string; this info is not used directly by the builder.

func (*BuilderNode) Partitions 

func (n *BuilderNode) Partitions() []int

Partitions returns the list of partitions assigned to this node; the list will be in ascending order with no duplicates.

func (*BuilderNode) ReplicaPartitions 

func (n *BuilderNode) ReplicaPartitions(replica int) []int

ReplicaPartitions returns the list of partitions assigned to this node for the given replica; the list will be in ascending order with no duplicates.

func (*BuilderNode) Responsible 

func (n *BuilderNode) Responsible(key int) int

Responsible returns the replica number this node is responsible for with respect to the key given; will return -1 if this node is not responsible for any replica for the key.

func (*BuilderNode) ResponsibleForReplicaPartition 

func (n *BuilderNode) ResponsibleForReplicaPartition(replica, partition int) bool

ResponsibleForReplicaPartition returns true if this node is reponsible for the specific replica and partition given.

func (*BuilderNode) SetCapacity 

func (n *BuilderNode) SetCapacity(v int)

SetCapacity specifies, relative to other nodes, how many assignments the node should have.

func (*BuilderNode) SetGroup 

func (n *BuilderNode) SetGroup(group *BuilderGroup)

SetGroup sets the parent group of the node; it may be set to nil to have no parent group.

func (*BuilderNode) SetInfo 

func (n *BuilderNode) SetInfo(v string)

SetInfo sets the user-defined info string; this info is not used directly by the builder.

type Group 

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

func (*Group) Groups 

func (g *Group) Groups() []*Group

func (*Group) Info 

func (g *Group) Info() string

func (*Group) Nodes 

func (g *Group) Nodes() []*Node

func (*Group) Parent 

func (g *Group) Parent() *Group

type Node 

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

func (*Node) Capacity 

func (n *Node) Capacity() int

func (*Node) Group 

func (n *Node) Group() *Group

func (*Node) Info 

func (n *Node) Info() string

func (*Node) Partitions 

func (n *Node) Partitions() []int

func (*Node) PartitionsForReplica 

func (n *Node) PartitionsForReplica(replica int) []int

func (*Node) Responsible 

func (n *Node) Responsible(key int) int

func (*Node) ResponsibleForReplicaPartition 

func (n *Node) ResponsibleForReplicaPartition(replica, partition int) bool

type Ring 

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

func Unmarshal 

func Unmarshal(r io.Reader) (*Ring, error)
Example 
package main

import (
	"bytes"
	"fmt"

	"github.com/gholt/ring"
)

func main() {
	// Build a ring to marshal...
	b := ring.NewBuilder(2)
	b.AddNode("Node One", 1, nil)
	b.AddNode("Node Two", 1, nil)
	b.Rebalance()
	r1 := b.Ring()
	// And marshal it...
	var buf bytes.Buffer
	if err := r1.Marshal(&buf); err != nil {
		panic(err)
	}
	// So we can show how to unmarshal it...
	r2, err := ring.Unmarshal(&buf)
	if err != nil {
		panic(err)
	}
	// And just do some checks to show they're the same...
	if !r1.Rebalanced().Equal(r2.Rebalanced()) {
		panic("")
	}
	if r1.ReplicaCount() != r2.ReplicaCount() {
		panic(fmt.Sprint(r1.ReplicaCount(), r2.ReplicaCount()))
	}
	if r1.PartitionCount() != r2.PartitionCount() {
		panic("")
	}
	compareNodeSlices := func(ns1, ns2 []*ring.Node) {
		if len(ns1) != len(ns2) {
			panic("")
		}
		for i := 0; i < len(ns1); i++ {
			if ns1[i].Capacity() != ns2[i].Capacity() {
				panic("")
			}
			if ns1[i].Info() != ns2[i].Info() {
				panic("")
			}
		}
	}
	compareNodeSlices(r1.Nodes(), r2.Nodes())
	for partition := 0; partition < r1.PartitionCount(); partition++ {
		compareNodeSlices(r1.KeyNodes(partition), r2.KeyNodes(partition))
	}
	fmt.Println("They look the same!")
}

Output:

They look the same!

func (*Ring) AssignmentCount 

func (r *Ring) AssignmentCount() int

func (*Ring) Groups 

func (r *Ring) Groups() []*Group

func (*Ring) KeyNodes 

func (r *Ring) KeyNodes(key int) []*Node

func (*Ring) Marshal 

func (r *Ring) Marshal(w io.Writer) error
Example 
package main

import (
	"bytes"
	"fmt"

	"github.com/gholt/ring"
)

func main() {
	// Build a ring to marshal...
	b := ring.NewBuilder(2)
	b.AddNode("Node One", 1, nil)
	b.AddNode("Node Two", 1, nil)
	b.Rebalance()
	r := b.Ring()
	// And marshal it...
	var buf bytes.Buffer
	if err := r.Marshal(&buf); err != nil {
		panic(err)
	}
	fmt.Println(len(buf.Bytes()), "bytes written")
	fmt.Println(string(buf.Bytes()[:213]), "...")
	// Note that even though the beginning is just JSON, there is trailing
	// binary for the larger data sets that JSON just isn't suited for.

}

Output:

243 bytes written
{"MarshalVersion":0,"NodeType":16,"ReplicaCount":2,"PartitionCount":2,"Nodes":[{"Info":"Node One","Capacity":1,"Group":0},{"Info":"Node Two","Capacity":1,"Group":0}],"Groups":[{"Info":"","Parent":0}],"Rebalanced": ...

func (*Ring) Nodes 

func (r *Ring) Nodes() []*Node

func (*Ring) PartitionCount 

func (r *Ring) PartitionCount() int

func (*Ring) Rebalanced 

func (r *Ring) Rebalanced() time.Time

func (*Ring) ReplicaCount 

func (r *Ring) ReplicaCount() int

func (*Ring) ResponsibleForReplicaPartition 

func (r *Ring) ResponsibleForReplicaPartition(replica, partition int) *Node

Source Files

View all Source files

Directories

Path Synopsis
info

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.