大家好,我是程序员牛肉。
想象一下现在我们有这样一个场景:在现代分布式系统中,负载均衡是一个核心问题。不同服务器通常有不同的处理能力,我们希望请求能按照服务器的能力比例分配。
那如果现在有两千台服务器,网关需要在请求的时候从服务器中抽出一台服务器来处理本次请求。
在这一个过程中,抽样特点是等待抽取的样本相对固定(不考虑缩扩容)但是抽样的频率超级高。并且样本的权重不一样。作为服务器,我们当然希望请求优先打到更加稳定的服务器中。
样本固定,抽取频率高,样本权重不一样。如果要考虑性能,我们要使用什么抽样法呢?
抽样的方法其实有很多。
比如说我们就做普通轮训或者加权轮训。但是轮训的问题是不考虑服务器的实时负载。
那最小连接法呢?我们就优先把请求发送到连接数最小的服务器上,又或者是兼顾权重来算比分。这样最小连接法虽然可以考虑到服务器的实时负载,但是需要在全局维护计数器,压力比较大一些。
而现在大多数的服务都在用的是一致性哈希算法。就是构建一个哈希环,将所有的服务器都映射到环上。
当一个请求来的时候,我们对这个请求进行哈希操作映射到哈希环上。当前请求命中哪个服务器节点,或者距离哪个服务器节点最近,就把当前请求路由到哪一个环上。
关于什么是一致性哈希算法,可以看一下我之前写的这一篇:
2024-07-03
但是一致性哈希算法也有缺陷,虽然可以实现高效的查找,但是一致性哈希算法过于依赖哈希算法的质量。
如果哈希算法的质量不高的话,就会出现节点散列度不高的问题,导致部分节点被海量请求打入。而且一致性哈希算法的落地也比较难一些。
纵观以上的抽样算法,你会发现大多数的算法在抽样的时候,时间复杂度基本最小也就是O(nlogn),虽然一致性哈希算法的查找性能能到O(1),但他过度依赖哈希算法的质量了。
而我们今天向大家介绍的算法,可以在查找的时候做到O(1)的时间复杂度。而这就是大名鼎鼎的别名采样算法(Alias Mrthod)
别名采样算法的核心思想是将不均匀的概率分布转化为均匀的概率分布加上一个简单的条件选择。具体来说,它通过构建两个表:
概率表(Probability Table):存储每个元素的修正概率
别名表(Alias Table):存储每个元素的"别名"
这两个表可以让我们在O(1)的时间复杂度内实现一次抽样。简单的来说,如果你学过概率论的话,你就会知道在概率论中,等概率分布和二项分布在抽样的时候时间复杂度都是O(1)。
而别名采样的思想就是想办法把随机权重的待抽样本转化为等概率分布和二项分布。
用图表示会让你更加清楚一些,假设我们现在有五个样本:ABCD。他们的权重分别是0.2,0.4,0.1,0,3。用图来表示的话,就是如下:
我们将这这些权重 * 当前样本数量,得到新的值为0.8, 1.6 , 0.4 ,1.2。用图表示为:
现在我们要对这些值进行拆解,让每一个块中都存在当前值和一个别名(其他值)。让每一个块的权重都回归 1 。
当这些块的权重都回归1的时候,此时你就可以进行等概率分布的抽样了。当你抽中具体的一个块的时候,你就可以进行二项分布的抽样了。
从代码角度看,采样阶段我们会执行两步:
先随机生成一个范围在块个数之间的数字来确定选中哪一个块。当我们选中了块之后,再随机生成一个值在[0-1]之间的数字,来确定当前选择哪个样本。
基于这种思想,我们就实现了在采样的时候时间复杂度为O(1)。真的是天才的设计。
那当然了,有的同学可能还会疑惑:牛肉哥,你都进行了这么多的操作了。还能确保一个元素的权重没有变化吗?
其实你如果仔细看别名采样法的话,你就会发现从本质上来讲,我们并没有对权重值进行改变,而是将一个样本的权重分散到了多个块中,最后得到几个概率相等的块。
对于上述的操作,其实我也可以不对初始概率 * 样本数量,而是直接进行分散,那这样的话,我们就得到了:
就算这样,我们最后只使用变化后的这两块就好了。两块的比例都是0.5,其实和之前的权重都是1的块是一个意思,只不过是等比扩大一遍而已。
有的人又说了:牛肉哥,那两个0.5看得我太难受了,你就不能把他们两个合到一起来进行抽样吗?
你要是这么搞的话,本质上就是轮盘赌随机算法了。随机生成一个数字看这个数字落到哪个区间中,但是由于块中已经有四个区间,早已不是二项分布了。那时间复杂度最快也就是使用二分法,时间复杂度为O(nlogn)。
而让我们回到别名采样法中,有细心的同学已经发现了:牛肉哥是不是搁这忽悠我呢?你说的是采样时候的时间复杂度啊,那前面我们还要对这些权重进行各种预处理操作,那预处理的时间复杂度怎么样呢?
预处理的时间复杂度是O(N),而抽样阶段的时间复杂度是O(1),所以分布采样法是一个预处理的时候性能慢一点,但采样阶段快的要命的算法。所以他天生适合处理那种样本不会频繁变动的案例。
在这里我也给一下别名采样法的代码实现:
// AliasTable 别名方法的数据结构
type AliasTable struct {
Prob []float64// 概率表
Alias []int // 别名表
}
// NewAliasTable 根据权重构建别名表
// 时间复杂度: O(n),其中n是元素的数量
// 空间复杂度: O(n)
func NewAliasTable(weights []float64) *AliasTable {
n := len(weights)
table := &AliasTable{
Prob: make([]float64, n),
Alias: make([]int, n),
}
// 计算权重总和
sumWeight := 0.0
for _, w := range weights {
sumWeight += w
}
// 归一化权重,使其总和为n
scaledWeights := make([]float64, n)
for i, w := range weights {
scaledWeights[i] = w * float64(n) / sumWeight
}
// 将选项分为两组:大于1的和小于1的
small := make([]int, , n)
large := make([]int, , n)
for i, w := range scaledWeights {
if w < 1.0 {
small = append(small, i)
} else {
large = append(large, i)
}
}
// 构建别名表
forlen(small) > && len(large) > {
s := small[len(small)-1]
small = small[:len(small)-1]
l := large[len(large)-1]
large = large[:len(large)-1]
table.Prob[s] = scaledWeights[s]
table.Alias[s] = l
// 更新大选项的权重
scaledWeights[l] = (scaledWeights[l] + scaledWeights[s]) - 1.0
if scaledWeights[l] < 1.0 {
small = append(small, l)
} else {
large = append(large, l)
}
}
// 处理剩余的选项
forlen(large) > {
l := large[len(large)-1]
large = large[:len(large)-1]
table.Prob[l] = 1.0
}
forlen(small) > {
s := small[len(small)-1]
small = small[:len(small)-1]
table.Prob[s] = 1.0
}
return table
}
// Sample 从别名表中采样一个索引
// 时间复杂度: O(1)
func (table *AliasTable) Sample() int {
// 随机选择一个桶
n := len(table.Prob)
i := rand.Intn(n)
// 以概率表中的概率选择该桶或其别名
if rand.Float64() < table.Prob[i] {
return i
} else {
return table.Alias[i]
}
}
// SelectN 使用别名方法选择n个不重复的元素
// 时间复杂度: O(n),其中n是需要选择的元素数量
func SelectN(table *AliasTable, n int) []int {
total := len(table.Prob)
if n > total {
n = total
}
selected := make(map[int]struct{})
result := make([]int, , n)
// 当结果集大小小于n时,继续选择
forlen(result) < n {
// 使用别名方法采样一个索引
idx := table.Sample()
// 如果该索引尚未被选择,则添加到结果集中
if _, exists := selected[idx]; !exists {
selected[idx] = struct{}{}
result = append(result, idx)
}
}
return result
}
别名采样算法的设计思想——通过预处理转化复杂问题以提高运行效率——也值得我们在其他算法设计中借鉴。在算法的世界里,有时候,一点点预处理的投资,可以带来巨大的长期回报。
别名采样算法不仅是一个理论上优美的算法,也是一个在实际应用中非常有价值的工具。其实最近我有一个需求就需要用到这个算法的思想,所以才写了这篇文章。
那今天关于别名采样算法的介绍就到这里了,相信通过我的介绍,你已经大致了解了别名采样法的设计思路。