柚子快报激活码778899分享：学习负载均衡的算法
什么负载均衡
负载均衡是一种计算机技术，用于在多个系统、网络链接、硬盘驱动器、CPU等之间分配工作负载，以优化资源使用、最大化吞吐量、最小化响应时间、并避免任何单一资源的过载。在网络负载均衡的情况下，它可以帮助将网络流量有效地分配到多个服务器。 负载均衡可以在硬件、软件或两者的组合中实现。它通常使用一种算法，如轮询、最少连接、IP哈希或其他自定义方法，来决定将请求发送到哪个服务器。 在微服务架构和大规模并行处理的环境中，负载均衡尤其重要，因为它可以帮助分散大量的请求，并确保系统的稳定性和可靠性。
负载均衡的算法有那些
round-robin （轮询）random（随机）ip-hashpower of 2 random choice （两次随机策略）consistent hash （一致性hash）consistent hash with bounded （有界一致性hash）least-load（最小连接）Weighted Round Robin（权重轮询）
round-robin（轮询）
i的类型是线程安全的，每次请求i就 +1 hosts 是目标服务器中host的slice，可以存储多个host 每次请求我们的i就会+1然后和host是的长度进行取余来轮询我们的目标服务器的ip。
random（随机）
rnd 是个随机来源 我们在调用该函数的时候需要先下一个随机种子
rnd := rand.New(rand.NewSource(time.Now().UnixNano()))
每次我们使用的时候，会根据hosts长度的大小随机一个该长度内的数据来获取一个目标服务器的ip。
ip-hash （ip哈希）
我们通过代码可以看到，传入进来的client的ip是通过crc32进行了hash计算，算出来一个值以后和hosts的长度进行了取余。 该负责均衡的算法有个好处就是同一个ip的用户访问我们的服务会被分配到同一个目标服务器上。
power of 2 random choice （两次随机策略）
type host struct {
name string
load uint64
}
// P2C refer to the power of 2 random choice
type P2C struct {
sync.RWMutex
hosts []*host
rnd *rand.Rand
loadMap map[string]*host
}
// NewP2C create new P2C balancer
func NewP2C(hosts []string) Balancer {
p := &P2C{
hosts: []*host{},
loadMap: make(map[string]*host),
rnd: rand.New(rand.NewSource(time.Now().UnixNano())),
}
for _, h := range hosts {
p.Add(h)
}
return p
}
// Add new host to the balancer
func (p *P2C) Add(hostName string) {
p.Lock()
defer p.Unlock()
if _, ok := p.loadMap[hostName]; ok {
return
}
h := &host{name: hostName, load: 0}
p.hosts = append(p.hosts, h)
p.loadMap[hostName] = h
}
// Remove new host from the balancer
func (p *P2C) Remove(host string) {
p.Lock()
defer p.Unlock()
if _, ok := p.loadMap[host]; !ok {
return
}
delete(p.loadMap, host)
for i, h := range p.hosts {
if h.name == host {
p.hosts = append(p.hosts[:i], p.hosts[i+1:]...)
return
}
}
}
// Balance selects a suitable host according to the key value
func (p *P2C) Balance(key string) (string, error) {
p.RLock()
defer p.RUnlock()
if len(p.hosts) == 0 {
return "", NoHostError
}
n1, n2 := p.hash(key)
host := n2
if p.loadMap[n1].load <= p.loadMap[n2].load {
host = n1
}
return host, nil
}
func (p *P2C) hash(key string) (string, string) {
var n1, n2 string
if len(key) > 0 {
saltKey := key + Salt
n1 = p.hosts[crc32.ChecksumIEEE([]byte(key))%uint32(len(p.hosts))].name
n2 = p.hosts[crc32.ChecksumIEEE([]byte(saltKey))%uint32(len(p.hosts))].name
return n1, n2
}
n1 = p.hosts[p.rnd.Intn(len(p.hosts))].name
n2 = p.hosts[p.rnd.Intn(len(p.hosts))].name
return n1, n2
}
// Inc refers to the number of connections to the server `+1`
func (p *P2C) Inc(host string) {
p.Lock()
defer p.Unlock()
h, ok := p.loadMap[host]
if !ok {
return
}
h.load++
}
// Done refers to the number of connections to the server `-1`
func (p *P2C) Done(host string) {
p.Lock()
defer p.Unlock()
h, ok := p.loadMap[host]
if !ok {
return
}
if h.load > 0 {
h.load--
}
}
我们看到（两次随机策略）的算法和ip-hash一样都是使用crc32的hash算法，只不过ip-hash是对key 进行一次hash然后于hosts的长度进行取余，但是（两次随机策略）是对同一个key进行两次hash，一次是用key直接进行hash，另外一次是对key加盐之后进行hash，这时候就求出来两个值，然后在hosts里面获取两个ip，然后对比他们的连接数，取最小连接数。
我们还发现当我们传入的key是个空值的时候，（两次随机策略）使用的随机策略。
Inc 方法和Done方法是在我们进行访问的时候会对连接的ip进行连接数的加减。
consistent hash （一致性hash）
在学习算法之前我们需要先学习下一致性hash
什么是一致性hash
一致性哈希（Consistent Hashing）是一种特殊的哈希技术，广泛应用于分布式系统中，用于解决数据的分布式存储问题。
在传统的哈希表中，如果哈希空间的大小发生变化（例如，增加或减少服务器），几乎所有的键值对都需要重新映射，这会导致大量的数据迁移，对系统的性能和稳定性产生影响。
一致性哈希通过引入虚拟节点和环形哈希空间的概念，使得哈希空间的大小变化时，只有一小部分的键值对需要重新映射。这大大减少了数据迁移的数量，提高了系统的稳定性。
一致性hash解决什么问题
一致性哈希（Consistent Hashing）主要解决分布式系统中的数据分布和负载均衡问题。
一致性哈希通过创建一个环形的哈希空间，并将节点和数据都映射到这个空间上，使得节点数量的变化只会影响哈希空间中的一小部分数据，大大减少了数据重新分配的数量。这使得一致性哈希非常适合动态变化的系统。
一致性哈希还可以通过引入虚拟节点来解决数据分布不均的问题。通过为每个节点创建多个虚拟节点，可以使得数据更均匀地分布在各个节点上，从而实现更好的负载均衡。
原理
在传统的哈希表中，如果哈希空间的大小发生变化，几乎所有的键值对都需要重新映射，这会导致大量的数据迁移，对系统的性能和稳定性产生影响。
但是一致性哈希通过引入虚拟节点和环形哈希空间的概念，使得哈希空间的大小变化时，只有一小部分的键值对需要重新映射。这大大减少了数据迁移的数量，提高了系统的稳定性。
一致性hash算法是对232 进行取模运算，是一个固定的值。通过和232 次进行取模运算的结果值组织成一个圆环。所以，一致性哈希是指将「存储节点」和「数据」都映射到一个首尾相连的哈希环上。 在hash 环上的结果的映射是顺时针方向第一个节点。 如果hash环上增加了节点，并不会想传统hash一样发生大量数据迁移的情况从而造成（hash洪水），而是只有部分数据会发生迁移。 但是一般的hash环会有个节点分布不均匀的问题，这样会导致如会有大量的数据或请求指向同一个节点上去。 为了解决这个问题我们在hash环上引入虚拟节点来均衡实体节点在hash环上分布不均匀的问题。 这时候节点数量多了以后，节点在hash环上的分布就均匀了。 我们看一致性hash负载均衡的类，里面有hash一致性的函数。
我们在调用一致性hash的add的时候我们看源码发现，针对每个host我们会创建10个虚拟的因子来加入到hash环上。 当我们在发送请求的时候通过我们client ip去获取对应的server ip 这里我们需要看下c.hash这个方法
blake2b.Sum512：这一行代码将key转换为一个字节切片，然后使用BLAKE2b哈希算法计算其512位（64字节）的哈希值。BLAKE2b是一种密码学哈希函数，可以生成不同长度的哈希值，这里生成的是512位的哈希值。计算结果被存储在out中。、binary.LittleEndian.Uint64(out[:])：这一行代码将out的前8个字节（64位）解释为一个小端格式的无符号整数。
我们在看下search函数，该函数使用key计算出来的hash的值和hash环中的值进行比较，并返回index。 我们通过上面函数返回的index获取到hash环中的对应的hash值，在冲hosts中获取到对应的服务器ip。
consistent hash with bounded （有界一致性hash）
什么是有界一致性hash
有界一致性哈希（Bounded Load Consistent Hashing）是一致性哈希的一个改进版本，它在一致性哈希的基础上增加了负载均衡的考虑。
在传统的一致性哈希中，虽然理论上数据会均匀地分布在各个节点上，但在实际应用中，由于哈希函数的随机性，可能会出现某些节点上数据过多，而某些节点上数据过少的情况，这被称为"哈希倾斜"。
有界一致性哈希通过引入一个负载因子的概念来解决这个问题。每个节点都有一个负载因子，表示该节点当前承载的数据量。当一个新的数据项需要被插入时，它不仅会考虑哈希环上的位置，还会考虑各个节点的负载因子，优先选择负载因子较小的节点。
这样，有界一致性哈希不仅保持了一致性哈希的优点（如高可用性和可扩展性），还提高了系统的负载均衡性，使得数据在各个节点之间的分布更加均匀。
有界一致性hash 其实和一致性的hash的添加方式是一样的，不一样是不一样在获取和请求的时候，有界一致性hash多了一个对ip负载的统计，不废话上代码。
Inc是对我们请求的servic ip进行负载的原子操作+1Done是在我们对service ip 请求结束后的进行负载的原子操作-1
通过ip获取到服务器的service ip ，接下来我们看看GetLeast hash和search这两个函数我们在一致性hash的时候解读过了，这里我们看看loadOk 这个函数，这个函数是来比较每个节点的平均负载，获取最小负载的host
通过代码我们可以看出我们要获取到负载小于平均负载的host
我们看到代码中*1.25 为什么这样作呢，是为了引入一个负载因子，使得每个节点可以接受稍微超过平均负载的请求。
乘以1.25就是为了给每个节点提供一些额外的容量，允许其负载稍微超过平均负载，以应对这种情况。这样可以提高系统的灵活性和鲁棒性，使得在节点的负载稍微超过平均负载时，系统仍能正常工作，而不是立即拒绝新的请求。
least-load（最小连接）
“Least Load” 是一种负载均衡策略，其目标是将新的请求分配给当前负载最小的服务器。这种策略可以帮助确保所有的服务器都能得到充分利用，同时避免某些服务器过载。
该策略使用了斐波那契堆来实现
斐波那契堆（Fibonacci Heap）是一种优先队列数据结构，它支持一系列操作，如插入、获取最小值、合并等，具有很好的理论性能。斐波那契堆在图算法（如 Dijkstra 和 Prim）中特别有用，因为它可以更有效地处理减少关键字的操作。
斐波那契堆的特点是：
它是一组最小堆有序树的集合，这些树都满足斐波那契堆的性质（即，每个节点的孩子数大于或等于其父节点的秩）。它有一个指针指向最小元素。它的所有操作（插入、删除最小元素、减少关键字、合并两个堆）都有很好的平摊时间复杂度。
我们在使用该策略的时候发现host让存入了斐波那契堆里面。该堆里面还记录了每个host的负载。 我们在每次请求的时候通过client ip 获取对应的host，但是在请求的时候会堆该host进行负载+1，请求结束以后会进行负载 -1 所以我们在获取service ip的时候就非常方便的从该堆里面获取到负载最小的ip，防止我们某个服务器过载。 我们在初始化该策略的时候会将host 通过斐波那契堆的insert存入到该堆的节点里面。 我们在请求的时候需要堆host进行负载的加减，这两个函数是通过递归的形式对堆里面的元素进行操作的。
柚子快报激活码778899分享：学习负载均衡的算法
相关文章
发表评论