Надежный интеграционный тест для кода с использованием HyperLogLog?

Question

Мы используем реализацию Twitter HyperLogLog в Algebird. Учитывая число N и проверку в нашей системе, которая использует HyperLogLog для оценки текущего размера постепенно растущей коллекции и теста, если она больше или меньше N, как мы можем написать интеграционный или системный тест, который проверяет эту проверку и является почти гарантированно пройдет, если наш код, который вызывает HyperLogLog, правильный? Испытуемая система не является детерминированной, поскольку, с одной стороны, она многопоточная.

Моя первая мысль заключалась в том, что правильный способ написать интеграционный тест, который является надежным для этого варианта использования, - это «отказаться от наших стандартов». Итак, какое количество позиций (M) должно быть отправлено в конечную точку, чтобы убедиться, что HyperLogLog будет оценивать общее количество элементов как больше N, с вероятностью, скажем,> = 0.999999?

Или есть лучший подход?

Стандартные границы ошибок настраиваются, но это напрямую не говорит нам о максимальных границах ошибок, которые мы могли бы увидеть некоторое время - это то, о чем я забочусь, чтобы избежать случайных сбоев в построении CI на основе master впустую время и вытягивание волос!

Я также обеспокоен тем, что способ генерации случайных данных в тестах может не генерировать равномерно распределенные случайные данные в соответствующих отношениях, что может существенно повлиять на вычисления вероятности.

Answer 1

Давайте сломаем это немного. Есть два основных поведения, которые вы ищете для теста:

1. Реализация Twitter HyperLogLog выполняет правильно, то это дает хорошую оценку количества элементов.

2. Ваш код, потребляющий структуры HyperLogLog (например, счетчики), при необходимости увеличивает их.

Обратите внимание, что поведение # 2 легко проверить во время сборки с использованием модульных испытаний, а не с интеграционными тестами. Это предпочтительнее и уловит большинство проблем.

Дело № 1 также может быть разбита на три случая:

А, когда число элементов равно 0;

B, когда количество предметов невелико (5, 100 или 1000);

C, когда количество предметов велико (миллионы/миллиарды).

Опять же, случаи A и B можно и нужно тестировать во время сборки с помощью модульных испытаний. Вы должны принять решение о допустимых границах ошибок в зависимости от вашего приложения и утверждать, что оценки находятся в пределах этих границ - на самом деле не имеет значения, что вы выбрали HyperLogLog как базовый метод оценки, тесты должны обрабатывать оценку как черный ящик , В качестве стадиона я бы сказал, что 10% -ная ошибка является разумной для большинства целей, но это действительно зависит от вашего конкретного приложения. Эти ограничения должны представлять собой наихудшую возможную точность, с которой ваше приложение может жить. Например, счетчик критических ошибок может вообще не жить с ЛЮБЫМИ ошибками оценки, поэтому использование HyperLogLog для него должно нарушить единичный тест. Счетчик для числа отдельных пользователей может иметь возможность проживать с ошибкой оценки 50% - это зависит от вас.

Так что это оставляет нас с последним случаем - тестирование того, что реализация HyperLogLog дает хорошую оценку для большого количества элементов.Это невозможно проверить во время сборки, и действительно, интеграционный тест - это путь. Однако, в зависимости от того, насколько вы доверяете реализации HyperLogLog в Twitter, вы можете рассмотреть просто НЕ ИСПЫТАТЬ это вообще - Twitter должен был это сделать уже. Это может показаться перерывом в передовом опыте, но, учитывая накладные расходы, которые могут быть связаны с тестом интеграции, в вашем случае это может стоить.

Если вы решили написать интеграционный тест, вам нужно будет моделировать трафик, который вы ожидаете в процессе производства, и генерировать его из нескольких источников, так как вы будете генерировать миллионы/миллиарды запросов. Вы можете сохранить образец реального производственного трафика и использовать его для тестирования (возможно, самый точный метод) или определить, как выглядит ваш трафик, и создать аналогичный тестовый трафик. Опять же, границы ошибок следует выбирать в соответствии с приложением, и вы должны иметь возможность обменивать метод оценки для лучшего, не нарушая тест.