作业
用你熟悉的编程语言实现一致性 hash 算法。
实现一致性 hash 算法,这里实现的是基于虚拟节点的一致性 hash 算法,也是 redis-cluster 集群使用一种集群管理的负载均衡算法。
package main
import (
"fmt"
"errors"
"kd_hash/con_hash/user"
"kd_hash/con_hash/hashcache"
)
//通过Id从缓存中获取用户信息value值
func GetUserInfo(userId string) (*user.UserInfo, error) {
obj, err := hashcache.GetValue(userId)
if err != nil {
fmt.println("use userid get machineinfo err,", err.Error())
return nil, err
}
data, ok := obj.(string )//模拟实现一种类型
if !ok {
return nil, errors.New("value is not string")
}
userInfo:=&user.UserInfo{}
if err:=userInfo.DecodeJson(data );err!=nil{
return nil, err
}
return userInfo, nil
}
func main() {
hashcache.AddMachine("127.0.0.1")
userId := "111"
userInfo, err := GetUserInfo(userId)
if err != nil {
fmt.Println("use userid get userinfo err,"err.Error())
return
}
fmt.Println("userinfo=%v", userInfo)
}
复制代码
package user
import (
"encoding/json"
"errors"
)
type UserInfo struct{
UserId string `json:"user_id"`
Name string `json:"name"`
}
//实现userinfo信息管理
func (s *UserInfo)NewUser(userId ,name string ) {
s.UserId=userId
s.Name=name
}
func (s *UserInfo)DecodeJson(data string )error {
if err:=json.Unmarshal([]byte(data),s);err!=nil{
return errors.New("value is not userinfo")
}
return nil
}
复制代码
package hashcache
import (
"errors"
"strconv"
"hash/crc32"
"sort"
)
//哈希环,整数范围
const hashRingMax uint32 = 1<<32 - 1
const nodeCountPerMachine = 1024 //单个实例上虚拟节点数
//服务器节点
type machine struct {
machineId uint32 //机器id
ip string //机器的IP地址
}
func (s *machine) GetValue(key string) (interface{}, error) {
//获取机器内存信息
return `{"user_id":"111","name":"test"}`, nil
}
//虚拟存储节点
type virtualNode struct {
*machine //虚拟节点对应的真实机器ID
nodeId uint32 //虚拟节点ID
ringIndex uint32 //该节点在哈希环上的索引
}
//虚拟节点在哈希环上的索引
func (s *virtualNode) getRingIndex() uint32 {
if s.ringIndex == 0 {
s.ringIndex = genHashRingIndex(strconv.Itoa(int(s.machineId + s.nodeId)))
}
return s.ringIndex
}
//所有虚拟存储节点 key为在哈希环上的索引ringIndex
type virtualNodeSlice []*virtualNode
var virtualNodes virtualNodeSlice
func (s virtualNodeSlice)Len()int{
return len(s )
}
func (s virtualNodeSlice)Less(i, j int) bool{
return s[i].ringIndex<s[j].ringIndex
}
func (s virtualNodeSlice)Swap(i, j int) {
s[i]=s[j]
}
//获取哈希环上的点保存到的虚拟节点
func (s virtualNodeSlice)GetNodeByRingIndex(ringIndex uint32) (*virtualNode,bool){
if s.Len()==0{
return nil, false
}
for _,v:=range s{
if ringIndex<v.ringIndex{
return v,true
}
}
//如果是最大的一个 那就返回 最小的节点
return s[0],true
}
//往集群增加一台机器
func AddMachine(ip string) {
id := genHashRingIndex(ip)
machineObj := &machine{machineId: id, ip: ip}
//每台机器对应1024个虚拟节点
var i uint32 = 0
for ; i < nodeCountPerMachine; i++ {
virtualNode := &virtualNode{machine: machineObj, nodeId: i,}
virtualNode.getRingIndex()
virtualNodes = append(virtualNodes, virtualNode)
}
//排序 把虚拟节点按从小到大排列
sort.Sort(virtualNodes)
}
//通过key从缓存中获取数据
func GetValue(key string) (interface{}, error) {
ringIndex := genHashRingIndex(key)
//获取虚拟节点
vNode, ok := virtualNodes.GetNodeByRingIndex(ringIndex)
if !ok {
return nil, errors.New("虚拟节点不存在")
}
return vNode.GetValue(key)
}
//把key做哈希运算并与哈希环取模获取在哈希环上的数值
func genHashRingIndex(key string) (ringIndex uint32) {
return hashKey(key) % hashRingMax
}
//把字符串哈希为uint32
func hashKey(key string) uint32 {
if len(key) < 64 {
var scratch [64]byte
copy(scratch[:], key)
return crc32.ChecksumIEEE(scratch[:len(key)])
}
return crc32.ChecksumIEEE([]byte(key))
}
复制代码
总结
本次主要讲解在整个互联网框架中的两个技术重点:缓存和负载均衡
一 缓存
1.1 读缓存
缓存数据通常来自于内存,比磁盘上的数据有更快的访问速度。
缓存存储数据的最终结果形态,不需要中间计算,减少 CPU 资源的消耗。
缓存降低数据库、磁盘、网络的负载压力,使这些 I/O 设备获得更好的响应特性。
缓存的优点:
支持大数据量存储,不受应用进程重启影响;
数据集中存储,保证数据一致性;
数据读写分离,高性能,高可用;
缓存的常见问题:
缓存选型:
2.2 写缓存-消息队列
消息队列调用架构:
补充:即使是当前的发布订阅模型实现 1 生产多消费的模式,但是对于消息生产和特异性消息的改造成本仍然较高,另外特殊场景下消息投递和数据库写入并行的情况下,消息投递的同步操作,对于消息系统的强依赖仍然对于现在的可用性有较高的要求,也出现通过 canal 实现对于 binlog 的订阅进而进行缓存写入/消息投递等方式。
消息队的优点:
使用较多的消息队列有 RabbitMQ,ZeroMQ,Kafka,RocketMQ,ActiveMQ(人工抛弃)
二 负载均衡
重定向负载均衡:本身架构不够合理,支持上不如反向代理里面的 301 和 302 实现,所以更多是参考重定向负载均衡实现的 dns 寻址上的负载均衡,不过 dns 寻址为了解决单次请求重定向的问题,会在某些场景下增加解析 ip 地址缓存导致负载均衡自动剔除错误节点的延时。
反向代理负载均衡:这里的跟多是 nginx,目前认知中比较长用于 http1 协议,对于 http2 协议目前是支持的, 但是暂时没有大规模的验证,对于基于 http2 的 grpc 协议目前调研看 enovy 的支持效果还不错,还在进一步推广使用阶段,对于 http3 这次暂不发表意见。
IP 层的负载均衡:这里多是 lvs 或者 F5 这类设备利于 HA 实现统一入口,在 7 层之前实现一个四层的负载均衡,性能更高。
数据链路层负载均衡:同上,这里面因为监控/安全等原因,会在 2 层之后增加四层和七层的负载实现一些运维和调度手段。
三 感受
第一个,万物皆 数据结构+算法,这些的东西搞来搞去实现方案最底层还是依赖于不同的数据结果通过各种牛逼的算法实现调度,得好好扎实基础,刷刷算法提了。
第二个,操作系统是一个目前把数据结构+算法用的非常极致的宝藏,当前的所有技术方案和解决方案在操作系统原理里面都有已经实现的办法,学好操作系统!
评论