使用HyperLogLog对代码进行可靠的集成测试？

Question

我们正在使用Twitter在Algebird中实现HyperLogLog.给定N和我们的系统中的检查,使用HyperLogLog估计逐渐增长的集合的当前大小并测试它是否多于或少于N,我们如何编写测试此检查的集成或系统测试,如果我们调用HyperLogLog的代码是正确的,几乎可以保证通过？被测系统是非确定性的,因为,一方面,它是多线程的.

我的第一个想法是,编写一个对这个用例可靠的集成测试的正确方法是"放弃我们的标准".那么,什么是足够数量的项目(M)发布到端点,以确保HyperLogLog将估计项目的总数超过N,概率,例如,> = 0.999999？

还是有更好的方法？

标准误差界限是可配置的,但这并不直接告诉我们偶尔可能看到的最大误差界限 - 这是我关心的,以避免随机失败的CI构建在主人身上造成浪费的时间和头发-pulling!

我还担心我们在测试中生成随机数据的方式可能不会在相关方面生成均匀分布的随机数据,这可能会对概率计算产生重大影响.

Answer 1

让我们分解一下。您需要测试两种主要行为：

1. Twitter HyperLogLog 实现执行正确，即它可以很好地估计项目数量。

2. 使用 HyperLogLog 结构（例如计数器）的代码会在适当的时候递增它们。

请注意，行为 #2 很容易在构建时使用单元测试进行测试，而不是使用集成测试。这是更可取的并且可以解决大多数问题。

案例#1 也可以分为三种情况：

A、当物品数量为0时；

B、当项目数量较少时（5、100或1000）；

C，当项目数量很大时（数百万/数十亿）。

同样，案例 A 和 B 可以而且应该在构建时使用单元测试进行测试。您应该根据您的应用程序决定可接受的误差范围，并让 UT 断言估计值在这些范围内 - 您选择 HyperLogLog 作为底层估计方法并不重要，测试应该将估计器视为黑匣子。作为一个大概，我想说 10% 的误差对于大多数用途来说是合理的，但这实际上取决于您的特定应用程序。这些界限应该代表您的应用程序可以承受的最差精度。例如，严重错误计数器可能根本无法忍受任何估计错误，因此使用 HyperLogLog 应该会破坏单元测试。不同用户数量的计数器可能能够承受高达 50% 的估计误差 - 这取决于您。

因此，我们只剩下最后一种情况 - 测试 HyperLogLog 实现可以对大量项目提供良好的估计。这是不可能在构建时进行测试的，实际上集成测试是可行的方法。然而，根据您对 Twitter 的 HyperLogLog 实现的信任程度，您可能会考虑完全不测试它 - Twitter 应该已经这样做了。这似乎违背了最佳实践，但考虑到可能与集成测试相关的开销，在您的情况下可能是值得的。

如果您选择编写集成测试，则需要对生产中预期的流量进行建模并从多个来源生成它，因为您将生成数百万/数十亿的请求。您可以保存真实生产流量的样本并将其用于测试（可能是最准确的方法），或者计算出您的流量是什么样子并生成类似的测试流量。同样，应根据应用选择误差范围，并且您应该能够在不破坏测试的情况下将估计方法更换为更好的方法。