抽样算法之：水塘抽样（Reservoir Sampling）

Spark的分区器实现包含两种：HashPartitioner和RangePartitioner。

• HashPartitioner：根据key % 分区数来进行分区，可能导致数据倾斜问题
• RangePartitioner：对数据集中的key进行采样，根据采样结果对数据进行分区，由于采样可以反应key的分布情况，所以RangePartitioner可以在一定程度上避免数据倾斜。

为了实现数据集的随机采样，Spark使用了水塘抽样算法(Reservoir Sampling)，实现了未知数据量大小场景下的随机抽样（无法一次性加载到内存的大数据、流数据）。

1. 随机采样1条数据

假设有一个长度为未知数N的数据集，从中随机取1条：即每条数据保留的概率为1/N

• 当数据长度为1时：保留第一条数据，即

$P_1=1$

• 当数据长度为2时：

$P_1=1-{1\over2}={1\over2} \qquad P_2={1\over2}$

• 当数据长度为3时：所有数据保留概率为1/3

$P_1=(1-{1\over2})* (1 -{1\over3})={1\over3} \qquad P_2={1\over2} * (1 -{1\over3})={1\over3} \qquad P_3={1\over3}$

• ......

由此总结出规律：遍历到第N条数据时保留的概率为1/N就可以保证1条数据的随机采样。

数学归纳法证明：
当N=1时：

$P_1=1 \text{, 结论成立}$

假设N=i时结论成立，即：

$P_1 = P_2 = ...=P_i={1 \over i}$

当N=i+1时：

$P_1 = P_2=...=P_i={1 \over i } * (1 - P_{i+1}) = {1 \over i} * (1 - {1 \over i+1}) = {1 \over i+1}$

结论成立。

2. 随机采样k条数据

可以直接采用上述结果，即：第i条数据保留概率为k/i，证明过程和上述类似，不再赘述。