校园网站制作,软件开发工程师简历模板,wordpress js load,有哪些做兼职的设计网站有哪些经过上一个章节的学习#xff0c;我们已经知晓了如何搭建了HTTP Server#xff0c;通过HTTP协议与我们定义的路由#xff0c;我们可以远程访问这个节点#xff1b;基于这一点#xff0c;我们可以部署多台实现了HTTP的缓存服务从而实现分布式的特性。这一章节我们要基于此背… 经过上一个章节的学习我们已经知晓了如何搭建了HTTP Server通过HTTP协议与我们定义的路由我们可以远程访问这个节点基于这一点我们可以部署多台实现了HTTP的缓存服务从而实现分布式的特性。这一章节我们要基于此背景下实现分布式缓存的前置条件多节点下的调取。 前文链接 手撕分布式缓存之一 | 定义缓存结构体与实现底层功能函数 手撕分布式缓存之二 | 互斥锁的优化 手撕分布式缓存之三 | HTTP Server搭建 系列目录 1多节点的调取1.1前言1.2一致性哈希算法的讲解与优化1.3多节点的添加与获取1.4代码实现逻辑 1多节点的调取
1.1前言 当服务使用多节点运行时节点之间的负载均衡往往是我们优先需要考虑的问题但缓存服务不同于一般的多节点服务它并非仅仅是通过分摊流量就可以避免某个节点不会出问题因为缓存往往对应着缓存雪崩的问题。举个例子如果一个热点key在节点A中存储着但是之后的大量该热点key的请求并没有都发送到节点A上这样做会导致两个问题① 每个被请求的节点都需要存储此键值对造成了不必要的空间损失 ② 通常情况下缓存中可能存储的key-value对应着用户的Cookie大量的请求失效导致数据库访问激增可能导致数据库服务的崩坏。 因此我们应该主动的判断要请求的key存储在哪个节点中尽量减少缓存穿透的情况出现。 1.2一致性哈希算法的讲解与优化 假设这样一个场景我们根据节点的名称计算出对应的hashKey并根据此value进行排序在通过key进行查找value时我们直接通过取余的方式进行确定应该从哪个节点中HashSearch。这样的方式看起来是行得通的但是节点是动态的如果我们加入了一个节点或者删除了一个节点会导致在key进行取余定位节点时大量的对应关系失效从而导致缓存雪崩。这种影响是致命的每一个key值都会受到影响只有极个别的key值可能重新计算后仍然映射到原本的关系上但是大部分的key值会在节点变动之后找不到映射关系。 我们可以发现上面的影响出现的原因本质上是因为key的映射关系是与节点的数量绑定的如果我们将key-节点的映射算法抽离节点的数量就可以避免上面场景对应问题的发生了。一致性算法就达到了这样的效果一致性算法依旧是将key使用固定的hash算法计算但是将key映射到节点上时并不是采用取模的方式而是去寻找最大的比hashKey小的节点这样做的好处就是当有节点A发生变动后收到影响的key只有那些key-hash是大于节点A对应的hash且小于另一个节点时它们去找到的节点会发生变化。 但是仅这样将真实的节点计算为hash也会有一个问题哈希倾斜。意思时如果大部分节点的hash值都很大而只有一个节点的hash值很小那么会有很多的key选择存储在这个hash值很小的节点中因此当这个节点发生变动时会引起哈希雪崩。针对这一问题我们可以因为虚拟节点这些选择虚拟节点的key最终仍然会存储到某一个真实节点中这样就会使得节点的分布更加的密集避免将一个大范围的key都映射到一个节点上。
1.3多节点的添加与获取 添加节点时我们可以使用节点的唯一性标识作为key值传入然后对节点的唯一性标识计算hash值然后将此值存储节点的hashKey的列表中将列表中的值排序后便于查找hashKey对应的节点并且将key-value存入字典中用于在key选择节点之后根据节点的hashKey查找对应节点的名称值得注意的是我们的虚拟节点的key值定义需要根据实际情况变化最理想的情况是将所有节点包含虚拟节点和真实节点均匀的映射到hashMap中这里的均匀分布不只是物理上节点排列的均匀更好的情况是实际key请求时存储在真实节点上的key也是均匀的。本示例中因为没有实际情况可以测试因此简单的将不同的自然数拼接在真实节点的唯一性标识中以标识该真实节点对应的不同的虚拟节点的唯一性标识。 获取节点的场景发生在有key进行请求时在我们按照相同的算法将key计算为hashKey后在存储节点hashKey的列表中寻找最大的小于此请求hashKey的节点找到这个节点的下标后在列表中找到节点对应的hashValue然后在字典中找到此hashValue对应的真实节点的名称并且返回该名称。
1.4代码实现逻辑
定义Hash函数的传参与响应类型定义Map结构与实现初始化函数 type Hash func(data []byte) uint32表示传参类型是byte类型的列表转换成uint32类型。crc32.ChecksumIEEE是包hash/crc32下的一个将string类型计算hash的函数。 package consistenthashimport (hash/crc32sortstrconv
)// Hash 定义了一个将字节数组映射到uint32的函数类型。
type Hash func(data []byte) uint32// Map 结构体包含所有已经计算过哈希值的key列表并且使用map存储每个虚拟节点对应的真实key。
type Map struct {hash Hash // 指向具体的哈希算法的函数指针replicas int // 每个真实key生成的虚拟节点数量keys []int // Sorted, 按照从小到大排序hashMap map[int]string
}// New 创建一个新的Map实例。如果没有传入Hash参数则默认使用crc32.ChecksumIEEE作为哈希算法。
func New(replicas int, fn Hash) *Map {m : Map{replicas: replicas,hash: fn,hashMap: make(map[int]string),}if m.hash nil { // 如果未提供hash函数则使用crc32.ChecksumIEEEm.hash crc32.ChecksumIEEE}return m
}实现节点的添加 strconv.Itoa(i)是将任何数字都可以转换成字符串而强制类型转换是只能将整数转换成字符串。sort.Ints(m.keys)对整形数据列表m.keys进行升序排列。 func (m *Map) Add(keys ...string) {// 循环每个key对其进行复制并计算哈希值存入hashMapfor _, key : range keys {// 没有真正的节点概念所以可视为虚拟节点因此在生成哈希时使用当前索引和key组合来创建不同的哈希值for i : 0; i m.replicas; i {// 将哈希值与key一起保存到hashMap中hash : int(m.hash([]byte(strconv.Itoa(i) key))m.keys append(m.keys, hash)m.hashMap[hash] key}}// 对keys进行排序以供Get()方法使用二分查找功能sort.Ints(m.keys)
}实现通过key请求选择节点 sort.Search(len(m.keys) 是根据第二个函数参数什么时候返回True来判断是否满足条件当满足条件时返回当前元素的下标如果均不满足则返回len(m.keys)。idx%len(m.keys)对idx做取余操作以实现将hash-value环状的放置的效果 // Get函数获取最接近提供的key的项。
func (m *Map) Get(key string) string {if len(m.keys) 0 { // 如果没有可用的key返回空字符串return }hash : int(m.hash([]byte(key)) // 计算key的哈希值// 二分查找合适的复制品。sort.Search()函数是在sort包中定义的一个泛型搜索函数//该函数会使用给定的判断条件进行二分查找并返回满足条件的元素下标或者插入位置下标。//这里传入的参数len(m.keys)表示要搜索的切片长度而后面的lambda函数则为判断条件//当m.keys[i] hash时就认为已经找到了合适的复制品。idx : sort.Search(len(m.keys), func(i int) bool {// 终止条件是m.keys[i] hashreturn m.keys[i] hash})return m.hashMap[m.keys[idx%len(m.keys)]]
}
