面试题答案
一键面试1. 数据结构设计
- 哈希环:使用
map[uint32]string
来表示哈希环,其中uint32
是哈希值,string
是节点名称。 - 节点列表:使用
[]string
来存储所有节点名称,方便遍历和添加新节点。
2. 哈希函数实现
- 在Go语言中,可以使用
hash/crc32
包来生成哈希值。示例代码如下:
package main
import (
"hash/crc32"
)
func hash(key string) uint32 {
return crc32.ChecksumIEEE([]byte(key))
}
3. 处理节点故障和新节点加入
- 节点故障:当某个节点发生故障时,在哈希环中删除对应的节点。由于一致性哈希的特性,只有该节点负责的数据会重新分布到相邻节点上,对其他节点影响较小。
- 新节点加入:将新节点名称添加到节点列表,并计算其哈希值,插入到哈希环中。然后重新分配部分数据到新节点。
4. 代码示例
package main
import (
"fmt"
"hash/crc32"
"sort"
)
type ConsistentHash struct {
hashRing map[uint32]string
sortedHashes []uint32
nodes []string
}
func NewConsistentHash() *ConsistentHash {
return &ConsistentHash{
hashRing: make(map[uint32]string),
sortedHashes: make([]uint32, 0),
nodes: make([]string, 0),
}
}
func (ch *ConsistentHash) AddNode(node string) {
h := hash(node)
ch.hashRing[h] = node
ch.sortedHashes = append(ch.sortedHashes, h)
sort.Slice(ch.sortedHashes, func(i, j int) bool {
return ch.sortedHashes[i] < ch.sortedHashes[j]
})
ch.nodes = append(ch.nodes, node)
}
func (ch *ConsistentHash) RemoveNode(node string) {
h := hash(node)
delete(ch.hashRing, h)
for i, v := range ch.sortedHashes {
if v == h {
ch.sortedHashes = append(ch.sortedHashes[:i], ch.sortedHashes[i+1:]...)
break
}
}
for i, v := range ch.nodes {
if v == node {
ch.nodes = append(ch.nodes[:i], ch.nodes[i+1:]...)
break
}
}
}
func (ch *ConsistentHash) GetNode(key string) string {
h := hash(key)
idx := sort.Search(len(ch.sortedHashes), func(i int) bool {
return ch.sortedHashes[i] >= h
})
if idx == len(ch.sortedHashes) {
idx = 0
}
return ch.hashRing[ch.sortedHashes[idx]]
}
可以通过以下方式调用上述代码:
func main() {
ch := NewConsistentHash()
ch.AddNode("node1")
ch.AddNode("node2")
ch.AddNode("node3")
fmt.Println(ch.GetNode("key1"))
ch.RemoveNode("node2")
fmt.Println(ch.GetNode("key1"))
}