I may be wrong, but there doesn't seem to be any place in the code where the load of a member (i.e. a node) is incremented. The only place where load distribution happens is when a new node is added or removed. This doesn't let the ring keep track of how much load each member has, especially once new clients/load are being allocated to the members. However, the point of bounded loads is that the load of each member is getting kept track of, so that if a new client comes in and would be allocated to a member with above-average load, the client will be added to another member instead.

In effect, I think your implementation may just be the classic consistent hash but not necessarily with bounded loads.

I'm seeing uneven distribution with certain parameters

package main

import (
	"fmt"

	"github.com/buraksezer/consistent"
	"github.com/cespare/xxhash"
)

type hasher struct{}

func (h hasher) Sum64(data []byte) uint64 {
	return xxhash.Sum64(data)
}

type myMember string

func (m myMember) String() string {
	return string(m)
}

func main() {
	h := hasher{}

	letters := []string{
		"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z",
	}

	for i := 2; i < 20; i++ {
		cfg := consistent.Config{
			PartitionCount:    2,
			ReplicationFactor: i,
			Load:              1.25,
			Hasher:            h,
		}

		allocator := consistent.New(nil, cfg)
		allocator.Add(myMember("shard-0"))
		allocator.Add(myMember("shard-1"))

		shardCounts := make(map[string]int)
		for _, l := range letters {
			shard := allocator.LocateKey([]byte(l))
			shardCounts[shard.String()] = shardCounts[shard.String()] + 1 
		}

		fmt.Printf("with replication factor of %d shard-0 gets %d keys and shard-1 gets %d\n", i, shardCounts["shard-0"], shardCounts["shard-1"])
	}
}

output

with replication factor of 2 shard-0 gets 14 keys and shard-1 gets 12
with replication factor of 3 shard-0 gets 0 keys and shard-1 gets 26
with replication factor of 4 shard-0 gets 0 keys and shard-1 gets 26
with replication factor of 5 shard-0 gets 12 keys and shard-1 gets 14
with replication factor of 6 shard-0 gets 12 keys and shard-1 gets 14
with replication factor of 7 shard-0 gets 12 keys and shard-1 gets 14
with replication factor of 8 shard-0 gets 12 keys and shard-1 gets 14
with replication factor of 9 shard-0 gets 26 keys and shard-1 gets 0
with replication factor of 10 shard-0 gets 26 keys and shard-1 gets 0
with replication factor of 11 shard-0 gets 26 keys and shard-1 gets 0
with replication factor of 12 shard-0 gets 26 keys and shard-1 gets 0
with replication factor of 13 shard-0 gets 26 keys and shard-1 gets 0
with replication factor of 14 shard-0 gets 26 keys and shard-1 gets 0
with replication factor of 15 shard-0 gets 26 keys and shard-1 gets 0
with replication factor of 16 shard-0 gets 26 keys and shard-1 gets 0
with replication factor of 17 shard-0 gets 26 keys and shard-1 gets 0
with replication factor of 18 shard-0 gets 26 keys and shard-1 gets 0
with replication factor of 19 shard-0 gets 14 keys and shard-1 gets 12

There are a lot of 26 vs 0 results, feels weird to me, is it expected, coincidence, coder error, a bug perhaps?

My use case: I am planning to store a bunch of containers as nodes in the hashring. Then, each container would poll periodically to look at its position in the hashring and decide what operations to do based on that. In order to do this, I need to access the hashring itself. Would it possible for you to add a function that returns the ring on the struct or expose the struct itself?

Thanks, Sai

Is this project really follow the origin paper about Consistent Hashing with Bounded Loads? I did not see any partition layer in this paper, there are only two roles: ball & bin.

consistent hashing only balances loads about as well as choosing a random server for each request, when the distribution of requests is equal. But if some content is much more popular than others (as usual for the internet), it can be worse than that.

Why wasn’t there a way to say “use consistent hashing, but please don’t overload any servers”?

https://medium.com/vimeo-engineering-blog/improving-load-balancing-with-a-new-consistent-hashing-algorithm-9f1bd75709ed

keys -> partitions -> members can only support balance between partitions and members. If there are too many keys mapping to same partition, the load of the member that relates to this partition will significant overload.

Besides, I think the result of _examples/load_distribution.go is totally depends on the balance of hash(key) % partitionNum. So, what's the different between this solution and dynamo hashing?

Otherwise, is this project is target to store system rather than connection load balance?

We recently encountered a deadlock with the library. After some digging, we found out that it tries to acquire the read lock in getClosetN, and then in GetPartitionOwner.

https://github.com/buraksezer/consistent/blob/f0660af7331feefacfe92d272ecd86deb7a87c0a/consistent.go#L302-L312

https://github.com/buraksezer/consistent/blob/f0660af7331feefacfe92d272ecd86deb7a87c0a/consistent.go#L284-L287

It's not safe to call RLock and RUnlock twice in one goroutine while having another goroutine call Lock simultaneously. The discussion here and here explain it better than me. In addition, to quote from the RWMutex documentation:

If a goroutine holds a RWMutex for reading and another goroutine might call Lock, no goroutine should expect to be able to acquire a read lock until the initial read lock is released. In particular, this prohibits recursive read locking.

You can also go to this Go playground and replicate it yourself: https://go.dev/play/p/pEhnPbsnDG

The probability is low since it requires a Lock happens immediately after the first RLock, but it would happen when you have a large amount of reads/writes and run for a sufficiently long time.

If there are no members in the hashring, calling the AverageLoad() function results in a "divide-by-zero" panic.

Example, this will result in a panic:

package main

import (
	"fmt"

	"github.com/buraksezer/consistent"
	"github.com/cespare/xxhash"
)

type myMember string

func (m myMember) String() string {
	return string(m)
}

type hasher struct{}

func (h hasher) Sum64(data []byte) uint64 {
	return xxhash.Sum64(data)
}

func main() {
	cfg := consistent.Config{
		PartitionCount:    7,
		ReplicationFactor: 20,
		Load:              1.25,
		Hasher:            hasher{},
	}
	c := consistent.New(nil, cfg)
        fmt.Printf("average load: %f", c.AverageLoad())
}

The AverageLoad() function should check if the number of members is > 0, and if it is not simply return a fixed value (such as 0 or -1).

// Add adds a new member to the consistent hash circle.
func (c *Consistent) Add(member Member) {
}

// Remove removes a member from the consistent hash circle.
func (c *Consistent) Remove(name string) {
}

I've been testing this library as a possible solution and came across this curious behavior. I have a Consistent object with 3 members, and then .Remove()'d one of them, and started getting ErrInsufficientMemberCount, which surprised me.

I see in the code you check against len(c.members)-1, is this a typo or or there some reason why all the members shouldn't be returned?

https://github.com/buraksezer/consistent/blob/master/consistent.go#L308

Hi, line 231, function delSlice, seems be better if make a new slice to store and assign to c.sortedSet or , change in-place like below:

func main(){
	m:=[]int{1,2,3,4,45,6,7,5,3,4,5,4,4,4,4,4}
	for i:=0;i<len(m)-1;{
		if m[i]==4{
			m=append(m[:i],m[i+1:]...)
			continue
		}
		i++
	}
	if m[len(m)-1]==4{
		m=m[:len(m)-1]
	}
	fmt.Println(m)
}

Hi @buraksezer

Thanks for the implementation. I needed some guidance for my use case, will be glad if you can provide recommendation on how should I configure the hash ring.

Here are some details: number of servers: 2-10 number of clients: 200-500 frequency of addition/removal of client: daily/weekly/monthly.

Replica names are created by smashing the member name and the replica number together.

https://github.com/buraksezer/consistent/blob/a1a9c4ab8d2da437ecbf64219cc0b6cf58639b7e/consistent.go#L250

Member names that end in numbers may collide with replicas of other members. For example, with member names of member and member1 with a ReplicationFactor of 11, there will be a collision with the 11th replica of member: member10 and the 1st replica of member1: member10.

@buraksezer First of all, I want to say thanks for this awesome implementation! I've started to use it in one of my projects.

I did, however, have a question about the PartitionCount configuration. I haven't seen a lot of information in the literature about how this impacts the hashing and, more importantly, any strategies on how to best chose the value for any arbitrary type of query workload. What I'm trying to do is uniformly distribute queries for any given resourceID across N cluster members. I like this library because if one of the cluster members fails then the load is redistributed such that any one of the remaining members will receive <= (Load * 100 ) percent of the residual traffic.

But I don't quite yet understand how that goal relates with the PartitionCount, and if I choose a lower value such as 3, 5, or 9 then I experience issues with the library being able to distribute when I add more members. Your input/guidance would be appreciated :)

I read your implementation, but I don't quite understand the variable of PartitionCount. Why not directly use sortedSet to locate the member where the data is located

This demo will panic:

package main

import (
	"github.com/buraksezer/consistent"
	"github.com/cespare/xxhash"
)

type hasher struct{}

type myMember string

func (m myMember) String() string {
	return string(m)
}

func (h hasher) Sum64(data []byte) uint64 {
	// you should use a proper hash function for uniformity.
	return xxhash.Sum64(data)
}

func main() {
	cfg := consistent.Config{
		PartitionCount:    1,
		ReplicationFactor: 1,
		Load:              1,
		Hasher:            hasher{},
	}
	c := consistent.New(nil, cfg)

	node1 := myMember("node1")
	c.Add(node1)
}

Here is the error message:

panic: not enough room to distribute partitions

goroutine 1 [running]:
github.com/buraksezer/consistent.(*Consistent).distributeWithLoad(0x450060, 0x0, 0x0, 0x43e2e0, 0x43e2c0, 0x34c96acd)
	/tmp/gopath552882815/pkg/mod/github.com/buraksezer/[email protected]/consistent.go:165 +0x3a0
github.com/buraksezer/consistent.(*Consistent).distributePartitions(0x450060, 0x1604d0)
	/tmp/gopath552882815/pkg/mod/github.com/buraksezer/[email protected]/consistent.go:196 +0xc0
github.com/buraksezer/consistent.(*Consistent).Add(0x450060, 0x1604d0, 0x40c150, 0x2b5f)
	/tmp/gopath552882815/pkg/mod/github.com/buraksezer/[email protected]/consistent.go:227 +0x180
main.main()
	/tmp/sandbox195891616/prog.go:30 +0xe0

So this is expected behavior or a bug?