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

Question

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

我的第一个想法是编写对这个用例可靠的集成测试的正确方法是“放弃我们的标准”。那么，发布到端点的足够数量的项目 (M) 是多少，以确保 HyperLogLog 将估计项目总数超过 N，并且概率大于等于 0.999999？

或者有更好的方法吗？

标准错误范围是可配置的，但这并不能直接告诉我们我们偶尔可能会看到的最大错误范围 - 这是我关心的，以避免在主服务器上随机失败的 CI 构建导致浪费时间和头发——拉!

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

Answer 1

让我们稍微分解一下。您要测试的主要行为有两种:

Twitter HyperLogLog 实现正确执行，即它给出了对项目数量的良好估计。

使用 HyperLogLog 结构(例如计数器)的代码会在适当的时候增加它们。

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

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

A、当项目数为0时；

B、当元素数量较少时(5、100或1000)；

C、当项目数量很大时(百万/十亿)。

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

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

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