MST

星途 面试题库

面试题:Go语言Map在分布式缓存系统中的一致性哈希实现

在分布式缓存系统中,为了更有效地管理缓存数据分布,一致性哈希是常用的算法。请基于Go语言,描述如何结合Map实现一致性哈希算法,以解决缓存系统中节点添加和删除时的数据重分布问题。包括如何设计数据结构,如何实现哈希函数,以及如何处理节点故障和新节点加入等情况。
39.5万 热度难度
编程语言Go

知识考点

AI 面试

面试题答案

一键面试

1. 数据结构设计

  1. 哈希环:使用 map[uint32]string 来表示哈希环,其中 uint32 是哈希值,string 是节点名称。
  2. 节点列表:使用 []string 来存储所有节点名称,方便遍历和添加新节点。

2. 哈希函数实现

  1. 在Go语言中,可以使用 hash/crc32 包来生成哈希值。示例代码如下:
package main

import (
    "hash/crc32"
)

func hash(key string) uint32 {
    return crc32.ChecksumIEEE([]byte(key))
}

3. 处理节点故障和新节点加入

  1. 节点故障:当某个节点发生故障时,在哈希环中删除对应的节点。由于一致性哈希的特性,只有该节点负责的数据会重新分布到相邻节点上,对其他节点影响较小。
  2. 新节点加入:将新节点名称添加到节点列表,并计算其哈希值,插入到哈希环中。然后重新分配部分数据到新节点。

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"))
}