kkdai/maglev

A Google Maglev Hashing Algorithm implement in Golang

Maglev: A Google Maglev Hashing Algorithm implement in Golang

What is Maglev

Maglev is Google’s network load balancer. It is a large distributed software system that runs on commodity Linux servers. Unlike traditional hardware network load balancers, it does not require a specialized physical rack deployment, and its capacity can be easily adjusted by adding or removing servers. (cite from paper)

Here is a Chinese reading note about Maglev: [論文中文導讀] Maglev : A Fast and Reliable Software Network Load Balancer (using Consistent Hashing)

Installation and Usage

Install

go get github.com/kkdai/maglev

Usage

func main() {
	sizeN := 5
	lookupSizeM := 13 //(must be prime number)

	var names []string
	for i := 0; i < sizeN; i++ {
		names = append(names, fmt.Sprintf("backend-%d", i))
	}
	//backend-0 ~ backend-4 

	mm := NewMaglev(names, lookupSizeM)
	v, err := mm.Get("IP1")
	fmt.Println("node1:", v)
	//node1: backend-2
	v, _ = mm.Get("IP2")
	log.Println("node2:", v)
	//node2: backend-1
	v, _ = mm.Get("IPasdasdwni2")
	log.Println("node3:", v)
	//node3: backend-0

	if err := mm.Remove("backend-0"); err != nil {
		log.Fatal("Remove failed", err)
	}
	v, _ = mm.Get("IPasdasdwni2")
	log.Println("node3-D:", v)
	//node3-D: Change from "backend-0" to "backend-1"
}

Inspired By

• Wiki Consistent_hashing
• Go implementation of maglev hashing
• 每天进步一点点——五分钟理解一致性哈希算法(consistent hashing)
• Distributed Systems Part-1: A peek into consistent hashing!

Project52

It is one of my project 52.

License

This is under the Apache 2.0 license. See the LICENSE file for details.

maglev's Issues

useCase error: NewMaglev return *Maglev, error

panic when n = 5 and m = 33

use this patch:

diff --git a/maglev_test.go b/maglev_test.go
index 429b2a3..a74c72e 100644
--- a/maglev_test.go
+++ b/maglev_test.go
@@ -30,7 +30,7 @@ import (
 // }

 const sizeN = 5
-const lookupSizeM = 13 //need prime and
+const lookupSizeM = 33 //need prime and

 func TestDistribution(t *testing.T) {
        var names []string

and run go test, bang!

--- FAIL: TestDistribution (0.00s)
panic: runtime error: index out of range [recovered]
	panic: runtime error: index out of range

goroutine 5 [running]:
testing.tRunner.func1(0xc000094100)
	/Users/cholerae/Documents/gopath/go/src/testing/testing.go:792 +0x387
panic(0x1113be0, 0x121f120)
	/Users/cholerae/Documents/gopath/go/src/runtime/panic.go:513 +0x1b9
github.com/kkdai/maglev.(*Maglev).populate(0xc00004a1e0)
	/Users/cholerae/Documents/gopath/src/github.com/kkdai/maglev/maglev.go:124 +0x1ab
github.com/kkdai/maglev.NewMaglev(0xc000092080, 0x5, 0x8, 0x21, 0x5)
	/Users/cholerae/Documents/gopath/src/github.com/kkdai/maglev/maglev.go:27 +0x82
github.com/kkdai/maglev.TestDistribution(0xc000094100)
	/Users/cholerae/Documents/gopath/src/github.com/kkdai/maglev/maglev_test.go:41 +0x1ae
testing.tRunner(0xc000094100, 0x1141048)
	/Users/cholerae/Documents/gopath/go/src/testing/testing.go:827 +0xbf
created by testing.(*T).Run
	/Users/cholerae/Documents/gopath/go/src/testing/testing.go:878 +0x353
exit status 2
FAIL	github.com/kkdai/maglev	0.007s

Would you mind uploading a license?

Hi Evan!

In your readme, you said that you are releasing this repo under Apache 2.0, but the LICENSE file is missing in the repo. Would you mind uploading a LICENSE file?

Thanks,
Catherine