轮询

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]

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
}

随机

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