架构师训练营第五周作业

一致性 Hash 实现（go):

package ring
import (	"errors"	"hash/fnv"	"math/rand"	"sort"	"time")
// Server Physical servertype Server string
// None an empty serverconst None = Server("none")
// Ring Hash ringtype Ring struct {	// random seed used to generate virtual nodes from server	seed *rand.Rand
	// how many virtual nodes will be created from one server	virtualizationRatio int
	// consitutent virtual nodes	nodes []uint32
	// indices map nodes to server	indices map[uint32]Server}
// IsEmpty whether ring is emptyfunc (ring Ring) IsEmpty() bool {	return len(ring.nodes) == 0}
// Contains whether ring contains specified serverfunc (ring Ring) Contains(server Server) bool {	for _, s := range ring.indices {		if s == server {			return true		}	}
	return false}
// Add add new server into the ringfunc (ring Ring) Add(server Server) Ring {	// If server has been added into the ring, nothing to do	if ring.Contains(server) {		return ring	}
	var nodes []uint32 = make([]uint32, len(ring.nodes))	copy(nodes, ring.nodes)
	var indices map[uint32]Server = make(map[uint32]Server)	for k, v := range ring.indices {		indices[k] = v	}
	for number := 1; number <= ring.virtualizationRatio; {		var node = uint32(ring.seed.Int())		if _, existed := ring.indices[node]; existed {			continue		}
		nodes = append(nodes, node)		indices[node] = server		number = number + 1	}	sort.Slice(nodes, func(i, j int) bool {		return nodes[i] < nodes[j]	})
	return Ring{		ring.seed,		ring.virtualizationRatio,		nodes,		indices}}
// Remove Remove server from the ringfunc (ring Ring) Remove(server Server) Ring {	if !ring.Contains(server) {		return ring	}
	var nodes []uint32 = make([]uint32, 0)	for _, node := range ring.nodes {		var nodeServer Server = ring.indices[node]		if nodeServer != server {			nodes = append(nodes, node)		}	}	var indices map[uint32]Server = make(map[uint32]Server)	for _, node := range nodes {		indices[node] = server	}
	return Ring{		ring.seed,		ring.virtualizationRatio,		nodes,		indices}
}
//Of create a new ring from given serversfunc Of(virtualizationRatio int, servers []Server) Ring {	var ring = Ring{		rand.New(rand.NewSource(time.Now().UnixNano())),		virtualizationRatio,		[]uint32{},		make(map[uint32]Server)}
	for _, server := range servers {		ring = ring.Add(server)	}
	return ring}
// Route resolve the server onto which key can be putfunc (ring Ring) Route(key string) (Server, error) {	if ring.IsEmpty() {		return None, errors.New("Can't perform hash operation in an empty ring")	}
	var hash = hash(key)
	var hit uint32 = 0
	for _, node := range ring.nodes {		hit = node		if node >= hash {			break		}	}
	return ring.indices[hit], nil}
func hash(key string) uint32 {	h := fnv.New32a()	h.Write([]byte(key))	return h.Sum32()}

单元测试：

package ring
import (	"fmt"	"math/rand"	"time"
	. "github.com/onsi/ginkgo"	. "github.com/onsi/gomega")
var _ = Describe("consistent hash ring test", func() {	When("There is only one server in the ring", func() {		theServer := Server("one")		oneServerRing := Of(100, []Server{theServer})
		Expect(oneServerRing.Route("hello")).To(Equal(theServer))		Expect(oneServerRing.Route("world")).To(Equal(theServer))	})
	When("There are 100 servers", func() {		servers := make([]Server, 100)		for s := 0; s < len(servers); s++ {			servers[s] = Server(fmt.Sprintf("%s%d", "server_", s))		}		oneHundredRing := Of(100, servers)
		distributions := make(map[Server]int)		for _, server := range servers {			distributions[server] = 0		}
		seed := rand.New(rand.NewSource(time.Now().UnixNano()))		for k := 1; k <= 1_000_000; k++ {			key := fmt.Sprint("key_", k, "_", seed.Int())			server, err := oneHundredRing.Route(key)			if err == nil {				distributions[server] = distributions[server] + 1			}		}
		for server, keys := range distributions {			fmt.Printf("%s(keys on the server: %d, difference: %.2f)\n", server, keys, float64(keys-10000)/10000)		}	})})

测试结果：

server_95(keys on the server: 11899, difference: 0.19)

server_35(keys on the server: 12468, difference: 0.25)

server_40(keys on the server: 9616, difference: -0.04)

server_57(keys on the server: 9019, difference: -0.10)

server_63(keys on the server: 8324, difference: -0.17)

server_67(keys on the server: 10539, difference: 0.05)

server_73(keys on the server: 9428, difference: -0.06)

server_94(keys on the server: 10668, difference: 0.07)

server_31(keys on the server: 10800, difference: 0.08)

server_43(keys on the server: 11304, difference: 0.13)

server_64(keys on the server: 9238, difference: -0.08)

server_77(keys on the server: 10561, difference: 0.06)

server_84(keys on the server: 10870, difference: 0.09)

server_87(keys on the server: 11374, difference: 0.14)

server_88(keys on the server: 9878, difference: -0.01)

server_93(keys on the server: 8944, difference: -0.11)

server_10(keys on the server: 10111, difference: 0.01)

server_15(keys on the server: 10060, difference: 0.01)

server_29(keys on the server: 9746, difference: -0.03)

server_30(keys on the server: 10463, difference: 0.05)

server_33(keys on the server: 9279, difference: -0.07)

server_42(keys on the server: 7877, difference: -0.21)

server_47(keys on the server: 10379, difference: 0.04)

server_99(keys on the server: 9845, difference: -0.02)

server_2(keys on the server: 10440, difference: 0.04)

server_21(keys on the server: 8640, difference: -0.14)

server_22(keys on the server: 9792, difference: -0.02)

server_38(keys on the server: 8439, difference: -0.16)

server_60(keys on the server: 9499, difference: -0.05)

server_76(keys on the server: 9780, difference: -0.02)

server_92(keys on the server: 9640, difference: -0.04)

server_58(keys on the server: 10464, difference: 0.05)

server_5(keys on the server: 9117, difference: -0.09)

server_16(keys on the server: 8575, difference: -0.14)

server_17(keys on the server: 10745, difference: 0.07)

server_27(keys on the server: 10128, difference: 0.01)

server_41(keys on the server: 11191, difference: 0.12)

server_53(keys on the server: 9994, difference: -0.00)

server_56(keys on the server: 10487, difference: 0.05)

server_74(keys on the server: 10944, difference: 0.09)

server_96(keys on the server: 10185, difference: 0.02)

server_1(keys on the server: 8716, difference: -0.13)

server_3(keys on the server: 10516, difference: 0.05)

server_9(keys on the server: 8609, difference: -0.14)

server_18(keys on the server: 12556, difference: 0.26)

server_45(keys on the server: 11134, difference: 0.11)

server_61(keys on the server: 9694, difference: -0.03)

server_7(keys on the server: 8494, difference: -0.15)

server_11(keys on the server: 9293, difference: -0.07)

server_26(keys on the server: 11392, difference: 0.14)

server_68(keys on the server: 8541, difference: -0.15)

server_34(keys on the server: 9288, difference: -0.07)

server_39(keys on the server: 10201, difference: 0.02)

server_54(keys on the server: 9225, difference: -0.08)

server_70(keys on the server: 10451, difference: 0.05)

server_79(keys on the server: 10036, difference: 0.00)

server_46(keys on the server: 9066, difference: -0.09)

server_69(keys on the server: 11278, difference: 0.13)

server_78(keys on the server: 10296, difference: 0.03)

server_85(keys on the server: 7540, difference: -0.25)

server_86(keys on the server: 9892, difference: -0.01)

server_89(keys on the server: 11760, difference: 0.18)

server_97(keys on the server: 11134, difference: 0.11)

server_13(keys on the server: 11109, difference: 0.11)

server_20(keys on the server: 9924, difference: -0.01)

server_80(keys on the server: 10647, difference: 0.06)

server_82(keys on the server: 8748, difference: -0.13)

server_66(keys on the server: 10918, difference: 0.09)

server_4(keys on the server: 9560, difference: -0.04)

server_19(keys on the server: 10321, difference: 0.03)

server_23(keys on the server: 9902, difference: -0.01)

server_25(keys on the server: 10809, difference: 0.08)

server_44(keys on the server: 9818, difference: -0.02)

server_48(keys on the server: 7635, difference: -0.24)

server_62(keys on the server: 12490, difference: 0.25)

server_59(keys on the server: 9881, difference: -0.01)

server_0(keys on the server: 10842, difference: 0.08)

server_6(keys on the server: 9320, difference: -0.07)

server_14(keys on the server: 10896, difference: 0.09)

server_28(keys on the server: 10147, difference: 0.01)

server_32(keys on the server: 9267, difference: -0.07)

server_36(keys on the server: 9313, difference: -0.07)

server_55(keys on the server: 10647, difference: 0.06)

server_65(keys on the server: 10996, difference: 0.10)

server_72(keys on the server: 10081, difference: 0.01)

server_75(keys on the server: 7991, difference: -0.20)

server_24(keys on the server: 11371, difference: 0.14)

server_50(keys on the server: 11255, difference: 0.13)

server_83(keys on the server: 9169, difference: -0.08)

server_98(keys on the server: 9754, difference: -0.02)

server_8(keys on the server: 8953, difference: -0.10)

server_37(keys on the server: 11078, difference: 0.11)

server_49(keys on the server: 11421, difference: 0.14)

server_51(keys on the server: 7361, difference: -0.26)

server_71(keys on the server: 10767, difference: 0.08)

server_90(keys on the server: 8716, difference: -0.13)

server_12(keys on the server: 10565, difference: 0.06)

server_52(keys on the server: 9412, difference: -0.06)

server_81(keys on the server: 8643, difference: -0.14)

server_91(keys on the server: 10411, difference: 0.04)