машина
Как выбрать лучший алгоритм
И так, у нас есть 4 варианта алгоритма, и нужно как-то в зависимости от условий выбирать лучший. Непонятно как это делать. Можно было бы создать репрезентативный набор данных и железа, затем провести хорошее нагрузочное тестирование и выбрать алгоритм, который лучше в среднем. Но проблема в том, что у нас нет хорошего репрезентативного набора данных. Я взял для тестирования выборку данных Метрики, Директа, Браузера и авиаперелётов в США. Но этого недостаточно - ведь ClickHouse используется сотнями компаний по всему миру, и переоптимизировав его на одном наборе данных, мы можем не заметить падения производительности на других данных. А если результаты зависят от модели процессора - придётся явно вписывать условия на них в код и тестировать его на каждой модели (либо смотреть справочные данные по таймингам инструкций?) Но это слишком трудоёмко.
Вместо этого я решил использовать метод, который очевиден для тех (лучших) коллег, которые не зря учились в ШАДе. Это - "многорукие бандиты".
Суть алгоритма состоит в том, что вариант алгоритма выбирается случайным образом. А затем на основе статистики мы начинаем выбирать чаще те варианты, которые хорошо себя показали.
У нас есть много блоков данных, которые нужно разжать. Это - независимые вызовы функции разжатия данных. Мы можем для каждого блока выбирать какой-нибудь из четырёх алгоритмов и мерять время его работы. Измерение времени работы обычно ничего не стоит по сравнению с обработкой блока данных (который в ClickHouse составляет минимум 64 КБ несжатых данных).
Прочтите эту статью про измерение времени.
Чтобы узнать, как конкретно работает алгоритм "многорукие бандиты", рассмотрим, почему он так называется. Это аналогия с автоматами в казино, у которых есть несколько ручек, за которые можно дёрнуть, и нам выдадут какое-то случайное количество денег. Игрок может много раз дёргать за ручки в любой выбираемой им последовательности. У каждой ручки есть фиксированное соответствующее ей вероятностное распределение количества выдаваемых денег, но игроку оно неизвестно, и он лишь может его оценить исходя из своего опыта игры, чтобы потом использовать для того, чтобы чаще дёргать лучшие ручки.
Один из подходов для максимизации выигрыша состоит в том, что на каждом шаге мы оцениваем вероятностное распределение для каждой ручки исходя из статистики нашей игры на предыдущих шагах. Затем в уме "разыгрываем" случайный выигрыш для каждой ручки исходя из этих распределений. И затем дёргаем за ту ручку, у которой разыгранный "в уме" исход оказался лучше. Этот подход называется Thompson Sampling.
В нашем случае имеем варианты алгоритмов разжатия; при выборе алгоритма, на выходе имеем время работы в пикосекундах на байт: чем меньше - тем лучше. Будем считать это время работы случайной величиной и оценивать её распределение. Чтобы оценивать распределение случайной величины, надо использовать методы математической статистики. Для данной задачи часто используют байесовский подход. Мы его использовать не будем, потому что мне не нравится вписывать сложные формулы в код на C++. Можно использовать параметрический подход - сказать, что случайная величина принадлежит какому-то семейству случайных величин, зависящих от парамеров; и затем оценивать эти параметры.
Как выбрать семейство случайных величин? Для примера, мы могли бы считать, что время выполнения кода имеет нормальное распределение. Но это абсолютно неверно. Во-первых, время работы кода не может быть отрицательным, тогда как нормальное распределение принимает значения на всей числовой прямой. Во-вторых, потому что время работы кода имеет тяжёлый хвост справа (я так думаю).
Впрочем, есть соображения, исходя из которых, использовать оценку нормального распределения лишь для целей Thompson Sampling - неплохая идея даже не смотря на то, что распределение искомой случайной величины заведомо не является нормальным. Причина - нужно оценивать мат-ожидание и дисперсию - это очень просто, а после достаточного количества итераций, нормальное распределение должно быть более-менее узким и будет не сильно отличаться от распределений, которые мы бы получили другими методами. Если нас не очень сильно интересует скорость сходимости на первых шагах, то этими деталями можно пренебречь.
На самом деле, это - невежественный подход. Из опыта известно, что среднее время выполнения запроса, загрузки сайта, и подобных величин, представляет собой мусор, и его не имеет смысла вычислять. Лучше было бы вычислять медиану - "робастную статистику". Но это слегка более сложно, и как мы покажем в дальнейшем, для практических целей, выбранный подход себя оправдывает.
