常用的负载均衡算法

news/2024/11/23 1:45:45/

轮询

var num = uint(0)var serverList = []string{"192.168.1.1","192.168.1.2","192.168.1.3","192.168.1.4","192.168.1.5",
}func f0() string {defer func() {num++}()return serverList[num%uint(len(serverList))]
}

加权轮询

var num = uint(0)type server struct {addr   stringweight int
}var serverList = []server{{"192.168.1.2", 1},{"192.168.1.1", 2},{"192.168.1.3", 2},{"192.168.1.4", 3},{"192.168.1.5", 2},
}func f1() string {var newServerList []serverfor i := 0; i < len(serverList); i++ {for j := 0; j < serverList[i].weight; j++ {newServerList = append(newServerList, serverList[i])}}defer func() {num++}()return newServerList[num%uint(len(newServerList))].addr
}

var num = uint(0)type server struct {addr   stringweight int
}var serverList = []server{{"192.168.1.1", 2},{"192.168.1.3", 3},{"192.168.1.4", 5},
}func f2() string { // 节省内存开销	sort.Slice(serverList, func(i, j int) bool {return serverList[i].weight < serverList[j].weight})totalWeight := func() int {sum := 0for _, w := range serverList {sum += w.weight}return sum}()defer func() {num++}()cur := num % uint(totalWeight)for _, svr := range serverList {if cur < uint(svr.weight) {return svr.addr}cur -= uint(svr.weight)}return serverList[cur].addr
}

平滑的加权轮询

将访问分散开，避免聚集到同一个服务器。
服务列表: server [“A”,“B”,“C”]
固定权重: weight [2,3,5]
动态权重: currentWeight [0,0,0]

numbercurrentWeight += weightmax(currentWeight)resultmax(currentWeight) -= sum(weight)
12, 3, 55C2, 3, -5
24, 6, 06B4, -4, 0
36, -1, 56A-4, -1, 5
4-2, 2, 1010C-2, 2, 0
50, 5, 55B0, -5, 5
62, -2, 108C2, -2, 0
74, 1, 55C4, 1, -5
86, 4, 06A-4, 4, 0
9-2, 7, 57B-2, -3, 5
100, 0, 1010C0, 0, 0
112, 3, 55C2, 3, -5
12…………
type server struct {addr   stringweight int
}var serverList = []server{{"192.168.1.2", 2},{"192.168.1.3", 3},{"192.168.1.5", 5},
}var currentWeightList = func() []int {return make([]int, len(serverList))
}()var sumWeight = func() int {sum := 0for _, svr := range serverList {sum += svr.weight}return sum
}()func maxCurrentWeightIndex() (index int) {for i := 0; i < len(currentWeightList); i++ {if currentWeightList[i] > currentWeightList[index] {index = i}}return
}func f3() string { // 平滑加权轮询for i := 0; i < len(serverList); i++ {currentWeightList[i] += serverList[i].weight}idx := maxCurrentWeightIndex()currentWeightList[idx] -= sumWeightreturn serverList[idx].addr
}

type server struct {addr          stringweight        intcurrentWeight int
}type serList []serverfunc maxServerIndex(list serList) (idx int) {idx = 0for i := range list {if list[i].currentWeight > list[idx].currentWeight {idx = i}}return
}var sumWeight = 0func loadBalance(list serList) (addr string) {for i := 0; i < len(list); i++ {list[i].currentWeight += list[i].weight}index := maxServerIndex(list)list[index].currentWeight -= sumWeightreturn list[index].addr
}func main() {var list serList = []server{{addr: "A", weight: 2},{addr: "B", weight: 3},{addr: "C", weight: 5},}for i := range list {sumWeight += list[i].weight}for i := 0; i < 30; i++ {fmt.Print(loadBalance(list))}
}

随机

var serverList = []string{"192.168.1.1","192.168.1.2","192.168.1.3","192.168.1.4","192.168.1.5",
}func f4() string {rand.Seed(time.Now().UnixNano())return serverList[rand.Intn(len(serverList))]
}

加权随机

type server struct {addr   stringweight int
}var serverList = []server{{"192.168.1.2", 2},{"192.168.1.3", 3},{"192.168.1.5", 5},
}func f5() string {sort.Slice(serverList, func(i, j int) bool {return serverList[i].weight < serverList[j].weight})rand.Seed(time.Now().UnixNano())totalWeight := func() int {sum := 0for _, w := range serverList {sum += w.weight}return sum}()cur := rand.Intn(totalWeight)for _, svr := range serverList {if cur < svr.weight {return svr.addr}cur -= svr.weight}return serverList[cur].addr
}

源地址散列

目标机器不能离线，否则流量回落空

var serverList = []string{"192.168.1.1","192.168.1.2","192.168.1.3","192.168.1.4","192.168.1.5",
}func f6(ip string) string {hs := sha256.New()hs.Write([]byte(ip))value := hs.Sum(nil)str := hex.EncodeToString(value)index, _ := strconv.ParseUint(str[:16], 16, 64)return serverList[uint(index)%uint(len(serverList))]
}

最小连接数

type server struct {addr         stringweight       intconnectCount int
}func (s *server) GetConnectCount() int {rand.Seed(time.Now().UnixNano())s.connectCount = rand.Intn(10000) // 这里用随机数模拟return s.connectCount
}var serverList = []server{{"192.168.1.2", 2, 0},{"192.168.1.3", 3, 0},{"192.168.1.5", 5, 0},
}func f7() string {minIndex := 0minCount := math.MaxIntfor index, svr := range serverList {count := svr.GetConnectCount() // 检测每个服务的连接数，取最小值if count < minCount {minCount = countminIndex = index}}return serverList[minIndex].addr
}

子集划分算法

该算法由Google提出。
非本人实现，此处引用文章：https://xie.infoq.cn/article/2075b4d8473854bd606ab49e0

// 请求参数:
//  - backends: 表示当前所有的后端, 例如在上面的演示案例中, 就表示100个Account Service机器
//  - clientID: 客户端唯一ID, 例如在上面的演示案例中, 就表示某一台User Service机器
//  - subsetSize: 子集大小, 也就是要连接多少个后端。在上面的演示案例中, 就表示clientID所代表的某一台User Service机器要连接subsetSize个Account Service
// 
// 返回值: 由subset算法返回的subsetSize个后端列表, 供服务进行连接
func Subset(backends []string, clientID, subsetSize int) []string {subsetCount := len(backends) / subsetSize// 将客户端划分为多轮, 每一轮计算使用同样的随机排列的列表round := clientID / subsetCountr := rand.New(rand.NewSource(int64(round)))r.Shuffle(len(backends), func(i, j int) { backends[i], backends[j] = backends[j], backends[i] })// subsetID代表了目前的客户端subsetID := clientID % subsetCountstart := subsetID * subsetSizereturn backends[start : start+subsetSize]
}

一致性哈希算法

非本人实现，此处引用文章：https://juejin.cn/post/6845166890864607240

package mainimport ("crypto/sha1""fmt""sort""strconv"
)//服务器结构体 地址和存储权重
type server struct {addr   stringweight int
}//当前服务器相关信息
var servers []server//默认的hash节点数
const defaultNodeNum = 100//基础虚拟节点
type virtualNode struct {nodeKey stringspotVal uint32
}type nodes struct {virtualNodesArray []virtualNode
}func (p *nodes) Len() int           { return len(p.virtualNodesArray) }
func (p *nodes) Less(i, j int) bool { return p.virtualNodesArray[i].spotVal < p.virtualNodesArray[j].spotVal }
func (p *nodes) Swap(i, j int)      { p.virtualNodesArray[i], p.virtualNodesArray[j] = p.virtualNodesArray[j], p.virtualNodesArray[i] }
func (p *nodes) Sort()              { sort.Sort(p) }//生成对应uint32
func getUint32Val(s string) (v uint32) {//进行sha1h := sha1.New()defer h.Reset()h.Write([]byte(s))hashBytes := h.Sum(nil)//go语言的位运算符处理if len(hashBytes[4:8]) == 4 {v = (uint32(hashBytes[3]) << 24) | (uint32(hashBytes[2]) << 12) | (uint32(hashBytes[1]) << 6) | (uint32(hashBytes[0]) << 3)}return
}func (p *nodes) setVirtualNodesArray(servers []server) {if len(servers) < 1 {return}//根据权重与节点数，维护一个map - 所有的hash圈上的值对应ipfor _, v := range servers {//第一步计算出每台机器对应的虚拟节点数totalVirtualNodeNum := defaultNodeNum * v.weightfor i := 0; i < totalVirtualNodeNum; i++ {iString := strconv.Itoa(i)//虚拟节点地址virtualAddr := fmt.Sprintf("%s:%s", v.addr, iString)virNode := virtualNode{nodeKey: v.addr,spotVal: getUint32Val(virtualAddr),}p.virtualNodesArray = append(p.virtualNodesArray, virNode)}p.Sort()}
}//获取当前数据key对应的存储服务器
func (p *nodes) getNodeSever(w uint32) (addr string){i := sort.Search(len(p.virtualNodesArray), func(i int) bool { return p.virtualNodesArray[i].spotVal >= w })return p.virtualNodesArray[i].nodeKey
}func main() {vNodes := new(nodes)servers = append(servers, server{"127.0.0.1", 1}, server{"127.0.0.2", 2}, server{"127.0.0.3", 3})//先赋值，生成虚拟nodevNodes.setVirtualNodesArray(servers)//传入对应的文件名，作为文件keyfname := "demo.jpg"uint32Val := getUint32Val(fname)ser := vNodes.getNodeSever(uint32Val)fmt.Println("文件对应存储服务器",ser)
}

可以设法优化掉虚拟节点占用的内存。

Reference
https://xie.infoq.cn/article/2075b4d8473854bd606ab49e0
https://juejin.cn/post/6845166890864607240
https://mp.weixin.qq.com/s/-xcrl-u99mZCdfSgUNhYHA


http://www.ppmy.cn/news/371051.html

相关文章

【在 macOS 上安装 Nessus 10】

【在 macOS 上安装 Nessus 10】

在 macOS 上安装 Nessus 10 macOS安装Nessus一、下载二、 安装三、初始化登录四、 安装插件和创建配置文件五、重启服务编译插件六、验证七、如何更新插件 macOS安装Nessus 修复部分破解方法在安装Nessus10重启之后重置授权问题。 一、下载 下载 macOS&#xff1a;https://s…
阅读更多...
android平台驱动开发（二）--设备属性节点的创建

android平台驱动开发（二）--设备属性节点的创建

驱动开发 如何创建设备属性节点 文章目录 驱动开发前言一、代码添加二、编译三、 验证总结 前言 最简单的设备属性节点 一、代码添加 在AU_LINUX_ANDROID_LA.VENDOR.1.0\kernel_platform\msm-kernel\drivers\misc\目录下新建test_device.c #include <linux/init.h> #…
阅读更多...
android平台驱动开发（一）

android平台驱动开发（一）

驱动开发 hello world 文章目录 驱动开发前言一、代码添加二、编译三、 验证总结 前言 最简单的hello world 驱动 一、代码添加 在AU_LINUX_ANDROID_LA.VENDOR.1.0\kernel_platform\msm-kernel\drivers\misc\目录下新建hello_world文件夹 并创建hello_world.c #include <…
阅读更多...
android平台驱动开发（三）--设备类节点实现重启功能

android平台驱动开发（三）--设备类节点实现重启功能

驱动开发 如何创建设备类属性节点 文章目录 驱动开发前言一、代码添加二、编译三、 验证总结 前言 最简单的设备属性累节点创建以及实现底层的重启功能 一、代码添加 在AU_LINUX_ANDROID_LA.VENDOR.1.0\kernel_platform\msm-kernel\drivers\misc\目录下新建test_reboot.c #…
阅读更多...
PostgreSQL 15：新特性预告

PostgreSQL 15：新特性预告

PostgreSQL 15 版本正在开发中&#xff0c;不远的将来就会与大家见面&#xff0c;所以是时候看看未来的一些新功能吧&#xff01; 1.删除public 模式的创建权限 直到今天&#xff0c;使用 PostgreSQL 14&#xff0c;每个人都可以默认写入public 模式。使用 PostgreSQL 15&…
阅读更多...
python中文编码与处理详解（个人认为比较全面详细了）

python中文编码与处理详解（个人认为比较全面详细了）

注意&#xff1a;本文只是针对 python 2&#xff0c;在 python 3 中&#xff0c;编码方式与处理技巧有些许变化&#xff0c;具体请参考&#xff1a; Python 2 与 Python 3 的差异对比&#xff1a; http://my.oschina.net/leejun2005/blog/173553 一、使用中文字符 在pytho…
阅读更多...
python unicode编码转换中文_python unicode转中文及转换默认编码

python unicode编码转换中文_python unicode转中文及转换默认编码

原博文 2016-11-16 22:20 − 一、　 　在爬虫抓取网页信息时常需要将类似"\u4eba\u751f\u82e6\u77ed\uff0cpy\u662f\u5cb8"转换为中文，实际上这是unicode的中文编码。可用以下方法转换： 1、 1 >>> s = u\u4eba\u751f\u82e6\u77ed... 相关推荐 2019-12…
阅读更多...
Linux下安装JDK 及 OpenJDK的卸载

Linux下安装JDK 及 OpenJDK的卸载

今日发现我Linux系统中安装的JDK是1.8的版本&#xff0c;但是在查询时候竟然是1.7的版本&#xff0c;因为我目前从事大数据方向的开发&#xff0c;这对于当前很多流行的技术不是很友好&#xff0c;故解决此问题&#xff0c;也让各位同仁不必再为此烦恼。 1、查询JDK版本 [roo…
阅读更多...
最新文章

Copyright @ 2022~2023