从源码级别分析 metric-core 的抽样算法

metric-core 是一个 java metric 库，用于统计 JVM 层面以及 服务级别 的各种 metric 信息。其中 metric-core 是其核心模块，代码量不多，总共 44 个文件，5700 行左右代码（包括注释）。算是一个很小的开源项目了。由于 metric 在所有项目中都非常重要，因此选择通读该项目，本文分析 metrci-core 中的抽样算法。

metric-core 中的抽样算法

在 metric-core 中总共有四种抽样算法，分别是 ExponentiallyDecayingReservoir, SlidingTimeWindowReservoir, SlidingWindowReservoir, UniformReservoir，其中后面三个抽样算法比较常规，也通常能见到，第一个则出于一篇论文Forward Decay: A Practical Time Decay Model for Streaming Systems，本文会通过源码分析自己对于这种抽样算法的理解。本文暂时只分析后面三种抽样算法，对于第一种，我会单独用一篇文章进行分析。

UniformReservoir 算法

该算法来自于论文Random Sampling with a Reservoir，讲述了一种随机抽样的方法，主要思想是使用一个固定的“蓄水池”装满需要数量的样本，如果当前“蓄水池”未满，将接下来的样本直接放入“蓄水池”，如果“蓄水池”已满，则随机从”蓄水池“中挑选一个样本进行替换（也可能不进行替换），这样在理论上能够保证所有的样本以同样的概率被选中。代码如下：

1
2
3
4
5
6
7
8
9
10
11
public void update(long value) {
	final long c = count.incrementAndGet();//获得当前”蓄水池“的大小
	if (c <= values.length()) { //如果”蓄水池“未满，直接将当前样本放入
		values.set((int) c - 1, value);
	} else {
		final long r = nextLong(c);//随机挑选一个数据（这个随机挑选的数可能在"蓄水池”中，也可能不在“蓄水池”中
		if (r < values.length()) {//如果随机挑选的样本，在”蓄水池“中，则进行替换
			values.set((int) r, value);
		}
	}
}

为了能够更好的理解，先使用样例如下。假设现在总共来了 10 个数 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，而“蓄水池“大小为 3. 那么”蓄水池”的 一种可能 变化如下（说是一种可能的变化，因为这里面牵涉到概率）

  • [1]
  • [1, 2]
  • [1, 2, 3]
  • [1, 2, 4] # 当 4 来的时候，发现“蓄水池”已满，然后从中筛选一个进行替换掉，假设我们替换掉 3
  • [1, 5, 4] # 当 5 来的时候，发现“蓄水池”已满，然后从中筛选一个进行替换掉，假设这次我们替换掉 2
  • [1, 5, 4] # 当 6 来的时候，发现“蓄水池”已满，我们打算从之前的数字中筛选一个进行替换，这个时候假设我们得到的下标是 3 或者 4，发现下标为 3 和 4 的数字不在“蓄水池”中（“蓄水池”的最大下标为 2 – 从 0 开始），因此不进行替换，所以本次“蓄水池”不变
  • [7, 5, 4] # 当 7 来的时候，发现“蓄水池”已满，随机一个下标，我们得到 0,那么将 7 放置到下标为 0 的位置
  • [8, 5, 4] # 同上
  • [8, 5, 9] # 同上
  • [10, 5, 9] # 同上

    SlidingWindowReservoir 抽样算法

    SlidingWindowReservoir 抽样算法则以最近的 N 个样本作为整个数据集的子集，这样简单直接，对于数据波动不大，或者窗口大小 N 足够大的情况下，该算法会有较好的效果。代码如下：
1
2
3
4
public synchronized void update(long value) {//加锁保证线程安全
	        //每次替换掉最旧的数据，保证”蓄水池“中的数据是最近的 N 个样本
	        measurements[(int) (count++ % measurements.length)] = value;
			    }

SlidingTimeWindowReservoir 抽样算法

该算法是上面移动窗口算法的变种，保留的是最近 N 时间单位（支持 TimeUnit 的所有时间单位）内的数据，而不是最近的 N 个数据。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public void update(long value) {
//每 TRIM_THRESHOLD 次操作之后会进行一次 trim() 操作
	if (count.incrementAndGet() % TRIM_THRESHOLD == 0) {
		trim();
	}
			        //直接将该值加入到 ”蓄水池“ 中
	measurements.put(getTick(), value);
	}
//获得当前的时间
private long getTick() {
	for (; ; ) {
		final long oldTick = lastTick.get();
		final long tick = clock.getTick() * COLLISION_BUFFER;
		// ensure the tick is strictly incrementing even if there are duplicate ticks
		final long newTick = tick - oldTick > 0 ? tick : oldTick + 1;
		if (lastTick.compareAndSet(oldTick, newTick)) {
			return newTick;
		}
	}
}
private void trim() {
	measurements.headMap(getTick() - window).clear();
}

这三种算法中，第二种和第三种是大家都很容易想到的，实现起来也很简单，第一种进行简单推导也不难，也算是一种现成的算法“蓄水池抽样”。

思考

如果某个系统每天会有 N 个人请求（N 不确定），需要从这些人中等概率的抽出 K 个中奖者，那么应该怎么做呢？是否可以使用上面抽样算法中的一种呢？

Comments

▲