写点什么

架构师训练营第五周作业

用户头像
zamkai
关注
发布于: 2020 年 12 月 27 日

一致性 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)


用户头像

zamkai

关注

还未添加个人签名 2018.02.24 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第五周作业