- PVSM.RU - https://www.pvsm.ru -
Всем привет!
Меня зовут Александр, я руковожу отделом Data Team в Badoo. Сегодня я расскажу вам о том, как мы выбирали оптимальный алгоритм для вычисления квантилей в нашей распределённой системе обработки событий.
Ранее мы рассказывали о том, как устроена наша система обработки событий [1] UDS (Unified Data Stream). Вкратце – у нас есть поток гетерогенных событий, на котором нужно в скользящем окне проводить агрегацию данных в различных разрезах. Каждый тип события характеризуется своим набором агрегатных функций и измерений.
В ходе развития системы нам потребовалось внедрить поддержку агрегатной функции для квантилей. Более подробно о том, что такое перцентили и почему они лучше представляют поведение метрики, чем min/avg/max, вы можете узнать из нашего поста про использование Pinba в Badoo [2]. Вероятно, мы могли бы взять ту же имплементацию, что используется в Pinba, но стоит принять во внимание следующие особенности UDS:
Исходя из этих архитектурных особенностей, мы выдвинули ряд параметров, по которым будем оценивать алгоритмы расчёта квантилей:
Мы решили, что нас устроит точность вычислений вплоть до 1,5%.
Нам важно минимизировать период времени от возникновения события до визуализации его квантилей на графиках. Этот фактор складывается из трёх других:
В нашей системе обрабатываются миллионы метрик, и нам важно следить за разумным использованием вычислительных ресурсов. Под памятью мы подразумеваем следующее:
Также мы выдвигаем следующие условия:
Алгоритм должен поддерживать вычисления для неотрицательных величин, представленных типом double.
Должна присутствовать имплементация на Java без использования JNI.
Чтобы иметь некий референс для сравнения, мы написали реализацию «в лоб», которая хранит все входящие значения в double[]
. При необходимости вычисления квантиля массив сортируется, вычисляется ячейка, соответствующая квантилю, и берётся её значение. Слияние двух промежуточных результатов происходит путём конкатенации двух массивов.
Это решение было найдено нами в ходе рассмотрения алгоритмов, заточенных под Spark (используется в основе UDS). Библиотека Twitter Algebird [3] предназначена для расширения алгебраических операций, доступных в языке Scala. Она содержит ряд широко используемых функций ApproximateDistinct
, CountMinSketch
и, помимо всего прочего, реализацию [4] перцентилей на основании алгоритма Q-Digest. Математическое обоснование алгоритма вы можете найти здесь [5]. Вкратце структура представляет собой бинарное дерево, в котором каждый узел хранит некоторые дополнительные атрибуты.
Библиотека [6] представляет собой улучшение вышеупомянутого алгоритма Q-Digest с заявленным меньшим потреблением памяти, улучшенной производительностью и более высокой точностью.
На этот продукт [7] мы наткнулись при реверс-инжиниринге распределённого SQL-движка Facebook Presto [8]. Было несколько удивительно увидеть реализацию квантилей в REST-фреймворке, но высокая скорость работы и архитектура Presto (схожая с Map/Reduce) подтолкнули нас к тому, чтобы протестировать это решение. В качестве математического аппарата используется опять же Q-Digest.
Это решение [9] являлось идейным вдохновителем реализации перцентилей в Pinba. Его отличительной особенностью является то, что при инициализации структуры необходимо знать верхний диапазон данных. Весь диапазон значений разбивается на N-ное количество ячеек, и при добавлении мы инкрементируем значение в какой-то из них.
Каждое из рассматриваемых программных решений было обёрнуто некоторой прослойкой (моделью) (чтобы адаптировать его под фреймворк для тестирования). Перед проведением performance-тестов для каждой модели были написаны unit-тесты для проверки её достоверности. Эти тесты проверяют, что модель (её нижележащее программное решение) может выдавать квантили с заданной точностью (проверялись точности 1% и 0,5%).
Для каждой из моделей были написаны тесты с использованием JMH [10]. Они были разделены на категории, про каждую из которых я расскажу подробно. Не буду «засорять» пост сырыми выводом от JMH – лучше сразу буду визуализировать в виде графиков.
В этом тесте мы измеряем производительность структур данных на вставку, то есть производятся замеры времени, требуемого на инициализацию структуры и на заполнение её данными. Также мы рассмотрим, как изменяется это время в зависимости от точности и количества элементов. Измерения производились для последовательностей монотонно возрастающих чисел в диапазонах 10, 100, 1000, 10000, 100000, 1000000 при погрешности вычисления 0,5% и 1%. Вставка производилась пачкой (если структура поддерживает) или поэлементно.
В результате мы получили следующую картину (шкала ординат логарифмическая, меньшие значения – лучше):
Результаты приведены для точности 1%, но для точности 0,5% картина принципиально не меняется. Невооружённым глазом видно, что с точки зрения вставки HDR является оптимальным вариантом при условии наличия более чем 1000 элементов в модели.
В этом тесте мы производим замеры объёма, занимаемого моделями в памяти и в сериализованном виде. Модель заполняется последовательностями данных, затем производится оценка её размера. Ожидается, что лучшей окажется модель с меньшим объёмом занимаемой памяти. Замер производится с использованием SizeEstimator [11] из Spark.
Как видно, при незначительном количестве элементов HDR проигрывает прочим имплементациям, однако имеет лучшую скорость роста в дальнейшем.
Оценка сериализованного размера производилась путём сериализации модели через Kryo [12], являющийся де-факто стандартом в области сериализации. Для каждой модели был написан свой сериализатор, который преобразует её максимально быстрым и компактным образом.
Абсолютным чемпионом вновь является HDR.
Этот тест наиболее полно отражает поведение системы в боевой ситуации. Методика теста следующая:
Результаты теста (меньшие значения – лучше):
И в данном тесте мы снова отчётливо видим уверенное доминирование HDR в долгосрочной перспективе.
Проанализировав результаты, мы пришли к выводу, что HDR является оптимальной имплементацией на большом количестве элементов, в то время как на моделях с небольшим количеством данных есть более выгодные реализации. Специфика агрегации по многим измерениям такова, что одно физическое событие влияет на несколько ключей агрегации. Представим себе, что одно событие EPayment должно быть сгруппировано по стране и полу пользователя. В этом случае мы получаем четыре ключа агрегации:
Очевидно, что при обработке потока событий ключи с меньшим числом измерений будут иметь большее число значений для перцентилей. Статистика использования нашей системы даёт нам следующую картину:
Эта статистика позволила нам принять решение о необходимости посмотреть на поведение метрик с большим количеством измерений. В результате мы выяснили, что 90 перцентиль числа событий на одну метрику (то есть нашу тестовую модель) находится в пределах 2000. Как мы видели ранее, при подобном количестве элементов есть модели, которые ведут себя лучше, чем HDR. Так у нас появилась новая модель – Combined, которая объединяет в себе лучшее от двух миров:
Смотрим результаты этого нового участника!
Как видно из приведённых графиков, Combined-модель действительно ведёт себя лучше HDR на малой выборке и сравнивается с ней при увеличении числа элементов.
Если вас интересуют код исследования и примеры API рассмотренных алгоритмов, вы можете найти всё это на GitHub [13]. И если вы знаете реализацию, которую мы могли бы добавить к сравнению, напишите о ней в комментариях!
Автор: Badoo
Источник [14]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/java/259868
Ссылки в тексте:
[1] система обработки событий: https://www.youtube.com/watch?v=3XJhBRiVKW8
[2] про использование Pinba в Badoo: https://habrahabr.ru/company/badoo/blog/331866/#monitoring-ocheredey
[3] Twitter Algebird: https://github.com/twitter/algebird
[4] реализацию: https://github.com/twitter/algebird/blob/d14c81a89a713e947ebe8ce82face4185e511c4b/algebird-core/src/main/scala/com/twitter/algebird/QTree.scala
[5] здесь: http://www.cs.virginia.edu/~son/cs851/papers/ucsb.sensys04.pdf
[6] Библиотека: https://github.com/tdunning/t-digest/
[7] этот продукт: https://github.com/airlift/airlift
[8] Facebook Presto: https://prestodb.io/
[9] решение: https://github.com/HdrHistogram/HdrHistogram
[10] JMH: http://openjdk.java.net/projects/code-tools/jmh/
[11] SizeEstimator: https://github.com/apache/spark/blob/a1e40b1f5d651305bbd0ba05779263a44f607498/core/src/main/scala/org/apache/spark/util/SizeEstimator.scala
[12] Kryo: https://github.com/EsotericSoftware/kryo
[13] на GitHub: https://github.com/alex-krash/quantiles-benchmark
[14] Источник: https://habrahabr.ru/post/332568/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.