win-minmax(窗口中的最值)算法
一个问题
如果让你设计这样一个信号峰值采集系统，你会如何设计呢？
- 系统每 1s 都可能接收到外界发送的一定强度的一个信号，且信号的强度在 [1,100] 范围内
- 你需要提供一个查询服务，向调用者返回在过去 30s 内信号强度的最大值
最朴素暴力的办法是使用一个能容量为 30 的环形数组，将每秒收到的信号的强度值记录在里面(如果没收到就视为 0)，当有人查询时，遍历整个数组，找到最大的值然后返回，如 Figure-1 所示.WRITE表示新收到的值写入的位置。
Figure.1
这样的系统能用肯定是能用的，但这样每次查询最大值时都要遍历整个缓冲区，效率实在不高。
那么很自然地，我们可以记录下当前窗口中的最大值(用MAX表示其在缓冲区的位置)。这样当需要查询最大值时，直接将MAX所在位置的值返回就行，如 Figure-2 所示
Figure.2
这样，当我们收到新的值时，只需要比较新的值与MAX位置的值的关系，再决定是否更新MAX
Figure.3
但有点麻烦的是，如果收到的值一直小于MAX位置的值，WRITE就会追赶上MAX，这时，我们就需要将MAX移到下一个最大值的地方，这就还是需要遍历整个数组。
Figure.4
也许你会说，还可以将第二大数值的位置记录下来(记为SEC MAX),这样在发生WRITE就会追赶上MAX时，可以很快将SEC MAX变成新的MAX。但这样又会引入新的问题：SEC MAX同样需要遍历整个数组。所以，这不是解决之道。
win-minmax
win-minmax是较新的 Linux 内核中用来记录窗口极值的算法实现。BBR 拥塞控制算法可以它来获得窗口时间内最小 RTT。
win-minmax的实现很小巧，代码见windowed min/max tracker
它用固定的内存记录一个时间窗口内最值(the best)、次最值(2nd best)和再次最值(3rd best)，以及对应的时间戳。有一点特别的是，同时始终保持这三组值的时间从早到晚的顺序为：最值、次最值、再次最值。
以最大值为例，三组值的直观关系是
Figure.5
这样，这样当某个时刻收到新的值时，就根据值的大小更新这三组值。如果此时距收到最大值的时刻还不到一个窗口，就可根据新收到的值与已有的三个值的关系，分为以下四种情况：
Figure.6
总的思想就是，如果新值超过了已有的三个值的一项或者多项，就将超过的”合并”起来。比如，对于第一种情况，新值超过了三个值，那么此时就可以将这三组值归一。通过这种方式，win-minmax可以保持三组值的大小和时间关系。
需要注意的是，为了尽量让三组值尽量widely separated in the time window，算法限制除了重叠情况外,2nd best 的时间戳不会在 1st best 时间戳的 1/4 个窗口内，3rd best 的时间戳不会在 1st best 时间戳的 1/2 时间窗口内。
win-minmax的优点显而易见：
- 使用与窗口大小无关的内存空间(无论窗口多大，都是三组值)
- 无需进行遍历数组操作，可以直接取得最值。