问题

有Q1、Q2、……、Qn n个队列,每个队列有一个权值W1、W2、……、Wn,需要每次从其中一个队列取出一个元素,使得从不同队列取出的元素数量比例服从权值的比例。

解释

这正是网络流量调度场景中的“带权轮询调度”(Weighted Round-Robin Scheduling,WRR),有现成的算法可用。

为了简单起见,先考虑最简单的情况,令 W1 = W2 = ... = Wn,那么“带权轮询调度”退化成“轮询调度”(Round-Robin Scheduling,RR),RR实现很简单,然后考虑权值不同的情况。

实现(python代码)

RR

# count
N = 3

# Round-Robin Scheduling
def rr_select():
    last = N - 1
    while True:
        current = (last + 1) % N
        last = current
        yield current

rr_test = rr_select()
for i in range(1000):
    print(rr_test.__next__())

N是队列的个数,0到N-1数字代表这N个队列。

RR会依次从每个队列取出元素,很简单无需过多叙述。

WRR


# count
N = 3

weight = (60, 30, 10)

# 最大公约数
def gcd(nums):
    m = nums[0]
    for n in nums[1:]:
        while n != 0:
            m, n = n, m % n
    return m

# Weighted Round-Robin Scheduling
def wrr_select():
    current = N - 1
    current_weight = 0

    while True:
        current = (current + 1) % N
        if current == 0:
            current_weight -= gcd(weight)
            if current_weight <= 0:
                current_weight = max(weight)
        if weight[current] >= current_weight:
            yield current

wrr_test = wrr_select()
for i in range(1000):
    print(wrr_test.__next__())

这个算法需要解释一下。

先看一下取前10个元素的结果:

current_weight     从哪些队列取出了元素
60                 0
50                 0
40                 0
30                 0 1
20                 0 1
10                 0 1 2

也就是每次for i in (0, 1, 2)的小周期内,当current_weight > weight[i]时,就把i选出来。当current_weight等于0了,就再从头开始,这算一个大周期。一个大周期包含max(weight)/gcd(weight)个小周期。

那如何证明这样取是符合权值比例的?

可以看到每个小周期中,都是要从权值最大的队列里拿走一个元素的,可以看作拿权值最大的那个作为基准,然后权值较小的直接拿它对比。那仅看权值为10的便可,10是60的1/6,把60分6分,只有1份是应该给10的,所以60知道降到10才满足10的条件。权值30的同理。

其实max(weight)和gcd(weight)都可以选择别的,但选它们两个可以满足最细粒度的平均,即每取出任意10个连续的中间结果,就必然服从权值比例,可以认为是最优的。

随机性考虑

WRR的运行结果是固定的,如果需要考虑随机性的话,需要再做一些额外工作。简单的话可以先对队列的顺序做随机,但这样实际的顺序还是固定的。可以按实际需要频繁暂存一定(随机)数量的结果,再随机处理后依次输出。

参考