Akumuli: поиск и выборка данных

Итак, в прошлом посте мы выяснили, что данные на диске хранятся очень просто - в больших, плоских файлах, отсортированными по возрастанию. Осталось только научиться в них искать. Самое очевидное решение - бинарный поиск. Представим для простоты, что мы ищем конкретные пары значений: метка времени + идентификатор и не занимаемся поиском диапазонов, выборкой срезов и тд, для простоты.

Все плохо

Допустим, мы храним простые, 4х байтовые значения, к которым akumuli добавит 20 байт заголовка - идентификатор параметра и метку времени. Том у нас имеет размер 4Гб, бинарный поиск делает log2(N) итераций в худшем случае, отсюда: log2(4GB/24B) = 27. Это значит, что нам потребуется до 27-ми итераций бинарного поиска. Причем первые итераций эдак 25, будут приводить к hard page fault (я использую отображаемые в память файлы для поиска), если поиск выполняется в первый раз. Если сравнить это с B-tree, для которого нам потребуется загрузить в худшем случае пять страниц (если размер страницы - 4КБ), то сразу станет понятно, почему так никто не делает. Бинарный поиск не является cache oblivious алгоритмом и будет работать не эффективно.

Поиск решения

К счастью, мы можем использовать специфику данных. Источники time series данных, очень часто бывают периодическими, например, это могут быть датчики, передающие показания с определенной частотой. Не обязательно, чтобы каждый источник был периодическим, так как параметров много, можно с высокой долей вероятности ожидать, что информация будет записываться примерно с одинаковой скоростью. А это как раз тот случай, когда можно использовать интерполирующий поиск. Принцип работы этого алгоритма крайне прост: мы знаем максимальную и минимальную метки времени, а также количество элементов в томе, мы делаем предположение о том, что метки времени всех данных распределены равномерно на этом промежутке времени, исходя из этого, мы можем приблизительно определить, где в томе может находиться искомое значение.

Интерполирующий поиск имеет сложность O(log log N), что уже сильно лучше бинарного поиска и близко к B-tree. В случае периодических источников, нам потребуется загрузить ровно столько же страниц, сколько в случае B-tree с размером страницы в 4КБ (выкладки пожалуй не буду приводить, но я считал, правда!). Но это нельзя считать решением, так как в реальности, даже с периодическими источниками можно получить неравномерное распределение, например в случае, если на какое-то время легла сеть и мы ничего не получали. В случае click-stream-ов мы будем наблюдать всякие суточные ритмы и тд. В общем, в реальности распределение может быть неравномерным. В этом случае, интерполирующий поиск будет ошибаться и делать больше итераций чем нужно (потенциально, даже больше чем бинарный поиск). Поэтому, мой алгоритм поиска делает ровно пять шагов интерполирующего поиска, а затем, откатывается на бинарный поиск. Почему именно пять? Это ровно столько, сколько нужно для того, чтобы найти результат в случае равномерного распределения.

Улучшения и оптимизации

Этим все не ограничивается. Алгоритм поиска старается на каждом этапе уменьшить область поиска. В самом начале область поиска равна всему тому, но на каждой итерации интерполирующего поиска одна из границ сдвигается ближе к искомому элементу. В случае, если область поиска сузилась до одной страницы, алгоритм откатывается на бинарный поиск, так как чем меньше масштаб, тем сильнее сказывается неравномерность распределения данных по меткам времени. Интерполирующий поиск старается сместить обе границы, если произошел overshoot, то на следующей итерации он постарается сделать undershoot. Это позволяет быстрее уменьшать область поиска.

Помимо этого, я планирую учитывать состояние страниц виртуальной памяти при поиске. Так как том мапится в память, одни страницы на момент поиска могут быть уже загружены с диска, а другие - еще нет. Мы можем получить эту информацию от операционной системы (системный вызов mincore в linux, в windows не помню как, но это тоже возможно). Во время поиска, мы можем использовать эту информацию для того, чтобы избежать page fault-ов, обращаясь только к загруженным в память страницам. Алгоритм поиска позволяет это делать, интерполирующий поиск может проверить не тот элемент, адрес которого он вычислил, а тот, который находится в ближайшей загруженной странице памяти. Бинарный поиск может проверить элемент не точно в середине области поиска, а ближайший из загруженных. Естественно, иногда все же придется обращаться к страницам, отсутствующим в памяти.

Open problem

Описанные улучшения не решают проблемы неравномерного распределения данных. Есть множество статей, описывающих разные решения этой проблемы. Как правило они предлагают поддерживать какую-либо структуру данных в памяти для ускорения интерполирующего поиска. Что конкретно нужно реализовать в akumuli я еще не решил. Возможно я буду поддерживать эту информацию непосредственно в томе, а может быть наоборот - буду собирать эти данные во время выполнения поиска и кэшировать - я еще не знаю. Это решение нужно принимать, основываясь на каких-то эмпирических данных, а для того, чтобы их получить, нужно реализовать все вышеперечисленное. Так или иначе, поиск, это то, что можно улучшать бесконечно.

Пока что, я ожидаю, что описанный мной алгоритм будет работать достаточно хорошо, как минимум, не хуже чем не специализированные решения. Накопленный опыт позволяет на это надеяться. В случае же попадания в sweet spot - работа с периодическими источниками - поиск должен работать просто фантастически быстро.