这段时间心血来潮要看一下关于缓存架构的设计与实现, 之前也会一直看资料, 都是在文章内描述一致性hash来实现memcache的分布式存储, 这样能更好的应对机器的不确定性, 比如动态添加机器或删减机器.
看了一些文章的实现, 似懂非懂. 平时拿来主义的我就想着自己来实现一个类似的简单算法加深理解, 什么是圆环, 什么是虚拟节点.
写案例的过程中也催生了很多疑问, 这些疑问后期在深入了解, 比如crc32出来的值可能会一致, 那么如果在虚拟节点的时候会不会出现节点覆盖不一致(数量)等情况.
下面是用go实现了一个简单的一致性算法(也有参考地方):
package main
import (
"errors"
"fmt"
"hash/crc32"
"math/rand"
"sort"
"strconv"
"time"
)
type serverInfo struct {
No uint8
Address string
}
// 每个服务器生成虚拟节点个数
var (
everyServVmNodeNum = 20
crcNodeNums []uint32
nodes = map[uint32]serverInfo{}
totalNode int
)
func init() {
rand.Seed(time.Now().UnixNano())
}
func main() {
// 设置服务器列表
servList := []string{
"127.0.0.1:32796",
"127.0.0.1:32797",
"127.0.0.1:32798",
}
totalNode = everyServVmNodeNum * len(servList)
crcNodeNums = make([]uint32, totalNode)
for k, v := range servList {
for i := 0; i < everyServVmNodeNum; i++ {
nodeNum := fmt.Sprintf("%s_%d", v, i)
// 这里发现如果crc32的值正好相同怎么办.. 有概率吗?
crcNodeNum := crc32.ChecksumIEEE([]byte(nodeNum))
crcNodeNums[k*everyServVmNodeNum+i] = crcNodeNum
nodes[crcNodeNum] = serverInfo{No: uint8(i), Address: v}
}
}
// 排序 方便后续查找节点
sort.Slice(crcNodeNums, func(i, j int) bool {
return crcNodeNums[i] < crcNodeNums[j]
})
// 做10000次测试
for i := 0; i < 10000; i++ {
key := randStr()
srv, num, srvNum := pickServer(key)
fmt.Println(
string(key),
"存储到",
srv.Address, "的第",
srv.No, "号虚拟节点",
"key="+strconv.Itoa(int(num)),
"server="+strconv.Itoa(int(srvNum)),
"getContinuousThreeNode=", getContinuousThreeNode(srvNum),
)
if srvNum != crcNodeNums[0] && num > srvNum {
panic(errors.New(fmt.Sprintf("%s ==> keyNum=%d, srvNum=%d", "出错了!,预期不一致", num, srvNum)))
}
}
}
// 获取连续三个节点的值
func getContinuousThreeNode(num uint32) []uint32 {
var res []uint32
for k, v := range crcNodeNums {
if v == num {
if k-1 >= 0 {
res = append(res, crcNodeNums[k-1])
} else {
res = append(res, 0)
}
res = append(res, num)
if k+1 < len(crcNodeNums) {
res = append(res, crcNodeNums[k+1])
} else {
res = append(res, 0)
}
}
}
return res
}
func pickServer(key []byte) (serverInfo, uint32, uint32) {
data := crcNodeNums[:]
nodeNum := crc32.ChecksumIEEE(key)
if s, ok := nodes[nodeNum]; ok {
return s, nodeNum, nodeNum
}
if len(data) == 1 {
return nodes[0], nodeNum, nodeNum
}
/**超出圆环最后一个节点则落点到第一台服务器**/
if crcNodeNums[totalNode-1] < nodeNum {
return nodes[crcNodeNums[0]], nodeNum, crcNodeNums[0]
}
var idx = totalNode / 2
var nearbyBigNodeNum uint32
// 怎么二分节点并且能保留靠近的节点 ? !
for len(data) > 1 {
// 选取点的值大于了key的值
if data[idx] > nodeNum {
nearbyBigNodeNum = data[idx]
data = data[:idx]
} else { // 选取点小于了key的值, 取后半段
data = data[idx:]
}
idx = len(data) / 2
}
if nearbyBigNodeNum > 0 {
return nodes[nearbyBigNodeNum], nodeNum, nearbyBigNodeNum
}
if len(data) >= 2 {
panic("错误了!!!!")
}
return nodes[data[0]], nodeNum, data[0]
}
func randStr() []byte {
salt := "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()_+1234567890-=<>,.?"
var b []byte
for i := 0; i < 10; i++ {
b = append(b, salt[rand.Intn(len(salt))])
}
return b
}
存储key查找节点用的二分查找, 并且用一个变量nearbyBigNodeNum来存储最近一次大于key的crc值.
代码还是比较简陋的, 很多命名比较难看. 在本机测试没有发现查找节点不正确的情况. 所以理论上这个逻辑是没问题的.
go语言中gomemcache的star数还是不少的, 有一定的参考意义, 这类的模块一般都为开发者实现好了一部分调度算法, 阅读gomemcache代码发现他们没有虚拟节点, 直接使用的取模来查找的服务器, 应该是上边说的取模算法吧??, 不过今天实现了小型的程序来加深印象,还是挺开心的~~~
不过现在还不知道到怎么实现类似redis的那种集群
主从复制的功能, 下去在继续了解
memcache 特点补充
- memcache容易发生单点故障(因为没有主从复制功能)
- memcache没有直接提供数据同步功能 , 不过现在好的开发者实现了类似的功能. 比如
magent,repcached等等. - Memcached单个key-value大小有限，一个value最大只支持1MB
- Memcached只是个内存缓存，对可靠性无要求；而Redis更倾向于内存数据库，因此对对可靠性方面要求比较高；
参考文章:
memcache 分布式集群算法