arriqaaq / xring

An implementation of Consistent Hashing with Bounded Loads (using Red-Black tree)

xring

A consistent hash ring with bounded loads Consistent hashing with bounded loads implementation using Red Black Tree

Example Usage

	nodes := []string{"a", "b", "c"}
	cnf := &xring.Config{
		VirtualNodes: 300,
		LoadFactor:   2,
	}
	hashRing := xring.NewRing(nodes, cnf)
	node,err:=hashRing.Get("foo")

	/*  
		Call this post execution of any function, else 
	 	the traffic would be load balanced, and get stuck if
		all nodes are busy 
	*/
	hashRing.Done(node)

TODO

• Add more test cases
• Performance test for xxhash

Paper

https://ai.googleblog.com/2017/04/consistent-hashing-with-bounded-loads.html

https://www.akamai.com/es/es/multimedia/documents/technical-publication/consistent-hashing-and-random-trees-distributed-caching-protocols-for-relieving-hot-spots-on-the-world-wide-web-technical-publication.pdf

xring Image source: https://ai.googleblog.com/2017/04/consistent-hashing-with-bounded-loads.html

xring's Issues

uneven distribution

Hey,

It seems like there is some issue with the way the distribution is done. If I have 120 keys with 3 nodes (virtual-nodes set to 1 and load-factor set to 1), I would expect each node to get 40 keys. However, I don't see that happening with your implementation. Have you improved upon this version?

Despite setting different values for virtual-nodes and load-factor, I get uneven distribution.

panic on remove

func main() {
	nodes := []string{"shard-1", "shard-2", "shard-3"}
	config := &xring.Config{
		VirtualNodes: len(nodes),
		LoadFactor:   40,
	}
	hashRing := xring.NewRing(nodes, config)
	keyCount := 100

	fmt.Println("with 3 nodes")
	distribution := simulateKeyDistribution(hashRing, keyCount)
	printDistribution(distribution)

	fmt.Println("------------------------------------------------")
	fmt.Println("with 4 nodes")
	hashRing.Add("shard-4")
	distribution = simulateKeyDistribution(hashRing, keyCount)
	printDistribution(distribution)

	fmt.Println("------------------------------------------------")
	fmt.Println("with 5 nodes")
	hashRing.Add("shard-5")
	distribution = simulateKeyDistribution(hashRing, keyCount)
	printDistribution(distribution)

	fmt.Println("------------------------------------------------")
	fmt.Println("with 4 nodes")
	hashRing.Remove("shard-4")
	distribution = simulateKeyDistribution(hashRing, keyCount)
	printDistribution(distribution)

}

and then I got:

------------------------------------------------
with 4 nodes
panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x2 addr=0x0 pc=0x104afbbd8]

goroutine 1 [running]:
github.com/arriqaaq/rbt.(*Tree).delete(0x140000a13e0?, 0x140000aa4e0?)
	/Users/akram/go/pkg/mod/github.com/arriqaaq/[email protected]/rbt.go:265 +0x1e8
github.com/arriqaaq/rbt.(*Tree).Delete(0x104afe391?, 0x140000a13e0?)
	/Users/akram/go/pkg/mod/github.com/arriqaaq/[email protected]/rbt.go:242 +0x2c
github.com/argoproj/xring.(*Ring).Remove(0x140000b8000, {0x104afe5d0, 0x7})
	/Users/akram/go/src/github.com/arriqaaq/xring/xring.go:144 +0x244
main.main()
	/Users/akram/go/src/github.com/arriqaaq/xring/examples/relocation.go:82 +0x2a0
exit status 2