Some obvious things about asynchronous network I/O

Async IO and async API is a two different things that often confused. First is what we usually want, second is what we doomed to deal with all the time. But these are not the same thing. You can achieve asynchronicity using only synchronous API but at the same time you can fail to do this using asynchronous calls. This can be illustrated with this boost.asio example:
link to source
It is obvious (for somebody who knows boost.asio API) that this code uses async I/O, `async_read_some` and `async_write` is asynchronous calls. This is a part of the server code. Server reads some data from socket asynchronously first and then it asynchronously writes response to the socket. All input and all output in this program is non-blocking but anyway - this server is synchronous because server can't write data to the socket until it reads something from it!

Yes, this is echo server, it works that way, but this pattern can be found in many "asynchronous" applications. One example - RPC system. You "call" method and your RPC library wraps arguments in a packet and sends it to RPC server. Now server can perform some processing and return error code sending another packet back. In this case no matter what API you use - synchronous or asynchronous, interaction between single client and server will be synchronous anyway.

The worst thing is that performance of such system will be limited by the network latency and not by the network bandwidth. Because each RPC call will result in network round-trip.

So, what's the conclusion?

1. Don't be fulled by `async` buzzword, pay attention to system interaction (protocols), not to API being used to implement that interaction. 
2. Design your protocol in such a way that can utilize high network bandwidth.
3. And finally - do the crazy things! For example, you can perform your RPC calls without waiting for responses assuming that no error was occurred but if this is not the case - you can rollback changes that was made under the wrong assumptions. Or if you know that client will request some data from server with 99.(9)% probability, you can send this data without waiting.

C++ Myths Debunking (part 1)

It is well known that small object allocation in C ++ is slow. This is a quote from Andrey Alexandrescu book “Modern C++ Design”:

For occult reasons, the default allocator is notoriously slow. A possible reason is that it is usually implemented as a thin wrapper around the C heap allocator (malloc/realloc/free). The C heap allocator is not focused on optimizing small chunk allocations.

…
In addition to being slow, the genericity of the default C++ allocator makes it very space inefficient for small objects. The default allocator manages a pool of memory, and such management often requires some extra memory. Usually, the bookkeeping memory amounts to a few extra bytes (4 to 32) for each block allocated with new. If you allocate 1024-byte blocks, the per-block space overhead is insignificant (0.4% to 3%). If you allocate 8-byte objects, the per-object overhead becomes 50% to 400%, a figure big enough to make you worry if you allocate many such small objects.

Book states that memory allocation is in fact slow and more of that, it states that allocation of small objects using malloc and new can cause high memory fragmentation. As far as I understand this is a common knowledge beyond C++ programmers. Many of us believes that fancy allocators and manual memory management is a Good Thing. Maybe this was true when book was released first (more than ten years ago) but not now! Let’s check the facts.

I’ve created this gist to show the state of things - link. This code allocates one million small objects using simple segregated storage (boost.pool) frees memory and then allocates another million of small objects using jemalloc. Time and memory usage is tracked. Result can be surprising - link.

First - malloc is slower than memory pool but not drastically. On my machine it’s five times slower than memory pool if deallocation time was taken into account and only three times slower if it wasn’t (this is relevant for some applications). Second - using jemalloc to allocate memory for small objects actually saves some space! Memory pool have used 20Mb of RAM and jemalloc have managed to fit everything into 16Mb.

This isn’t surprising because jemalloc implements simple segregated storage under the hood. It manages memory better than most of the fancy handwritten memory allocation schemes on Earth. It is a better option than custom allocator most of the time because it’s stable, fast and it can give you some feedback. It can be beaten by some custom allocation scheme in synthetic tests but not in practice.

And finally you can always switch different allocators (jemalloc/tcmalloc/whatsoever) using LD_PRELOAD. This is not the case with custom hand-coded allocators - if you make mistake you can’t fix it without rewriting your code.

Недавно я наконец зарелизил akumuli. Все что планировалось - сделано.Дальше я планирую улучшить компрессию для real значений, избавиться от зависимости из библиотеки boost, оставить только header-only библиотеки оттуда, чтобы упростить deployment. Ну и наконец допилить враппер для Golang.

Теперь о том, что будет дальше. Если кто-то внимательно изучил принцип работы моего движка для хранения данных, то этот человек мог заметить, что он организован не совсем так, как это обычно бывает. Обычно, такие вещи оптимизируются для запросов, возвращающих один временной ряд, чтобы иметь возможность быстро построить по нему график. Это здорово, но это могут делать graphite, influxedb, open tsdb, kairosdb, seriesly и тд. Но это не то что делает time series БД, по сути все вышеперечисленные решения, они не time-series а metrics databases. Они нужны в основном для devops применений, что хорошо, так как количество таких применений растет, но вот делать yet another metrics storage мне не очень интересно.

Akumuli не может быстро вернуть один временной ряд, это все выливается в полное сканирование тома. Это все именно так и задумывалось, потому что я пытаюсь построить TSDB, которая не предназначена для построения графиков, вместо этого, она должна уметь делать similarity search. Мой поинт в том, что чем больше time-series данных вы собираете, тем более бесполезными становятся обычные способы работы с ними ну и тем более бесполезным становится построение графиков по ним. Для того, чтобы работать с такими объемами информации, нужно уметь их эффективно майнить. Именно это akumuli и научится делать в ближайшем будущем. Для mining-а этих данных не нужны ни point-запросы ни способность быстро извлечь одну серию, для этого нужно уметь быстро строить индексы, а для этого нужны уметь быстро сканировать все данные.

Можно коротко описать принцип работы TSDB для майнинга следующим образом:

• Собираем данные и записываем их на диск.
• Делаем из длинных серий короткие с помощью sliding window.
• Делаем dimensionality reduction, есть много методов основанных на преобразовании Фурье, wavelet transform и даже преобразовании в текст.
• Индексируем то что получилось с помощью R-tree, VA-files или чего-нибудь еще.
• Выполняем запросы с погрешностью используя полученные индексы, если нужно - читаем оригинальные данные.

Это все желательно уметь делать не на одной машине а на нескольких.

Небольшой отчет о статусе akumuli. Итак, я реализовал всю основную функциональность.
Запись - работает, пропускную способность по записи я особо изощренно не тестировал, на моем старом ноутбуке, akumuli может прожевать порядка 3х миллионов insert-ов в секунду (и прочитать их потом назад, что немаловажно). На нормальном железе - заметно больше. Это все благодаря тому, что akumuli трансформирует случайную запись в последовательную запись, с которой у современных железок все очень хорошо и замечательно. В будущем производительность будет ниже, так как ей придется немного пожертвовать ради повышения отказоустойчивости. До сих пор не реализованы некоторые важные вещи, например синхронизация чтения и записи при перезаписи старых данных.
Поиск - тоже работает. Он требует оптимизаций (оптимизация с помощью mincore еще не реализована), но корректно ищет все что нужно. Возможно стоит реализовать простой планировщик запросов, например, на основе алгоритма FSCAN.
Я серьезно переработал in-memory индекс для данных, не вышедших за пределы sliding window. Теперь он основан не на B-tree, а на алгоритме patience sort. Подробно с алгоритмом можно ознакомиться в википедии. Если коротко, то все работает примерно так - в начале у нас есть пустой массив, элементами которого являются sorted runs - отсортированные в порядке увеличения меток времени массивы. Когда записывается первый элемент, в этот массив добавляется единственный sorted run из одного, только что добавленного, элемента. Далее, при записи следующего элемента, мы смотрим на его метку времени и, если она больше или равна метке времени предыдущего элемента, то этот элемент добавляется в тот же sorted run, если она меньше - то создается еще один sorted run. Далее, процесс повторяется для каждого последующего элемента, в результате чего, мы получаем набор отсортированных массивов. Их не может быть очень много, так как глубина записи ограничена sliding window. Эти массивы и есть индекс. Когда нужно слить всю информацию на диск (данные вышли за пределы sliding window), они сливаются с помощью простого k-way merge-а, очень быстро и эффективно. В этих массивах можно легко искать простым бинарным поиском, запись в такой индекс происходит быстрее чем запись в b-tree, даже на самых неудобных данных.
В ближайшее время я планирую реализовать синхронизацию между чтением и записью и оптимизировать поиск. После этого, возможно, у меня дойдут руки до whitepaper-а по системе.

Как вы возможно помните, я пишу хранилище для временных рядов - akumuli. В данный момент я занят самим "движком" для хранения данных, однако планирую и frontend, который будет уметь записывать и считывать данные по сети. Для этого, мне нужен какой-нибудь механизм сериализации, само собой - он должен быть быстрым и эффективным, но самое главное - он должен быть безопасным. В идеале - сервер должен уметь торчать в интернет, с оговорками, вроде ограничения количества сообщений от одного клиента в time-frame.
И тут все очень плохо. Очень многие библиотеки сериализации проектировались без учета требований безопасности и позволяют положить сервис одним сообщением. За примерами далеко ходить не надо, вот, например, один товарищ с RSDN написал библиотеку сериализации - YAS (Yet Another Serializer) для С++. Это header only библиотека, умеющая сериализовать как стандартные контейнеры, так и контейнеры из boost и Qt. Можно также сериализовать пользовательские типы, интерфейс похож на boost::serialization. Библиотека YAS заявлена как drop-in replacement (correct me if I wrong) для boost::serialization, что хорошо, и работает заметно быстрее оного, что тоже хорошо. Что не хорошо, так это возможность уронить сервис одним сообщением:


Внимательно смотрим на 13-ю строку. Несложно догадаться, что нам достаточно передать вместо длины списка очень большое число, чтобы сервис упал или ушел в своп, при этом элементы списка можно не передавать вовсе! Вызов list.resize попытается создать нужное количество элементов, сделав столько аллокаций, сколько мы ему скажем, причем в выделенные участки памяти он будет писать, а значит память реально будет выделяться системой. При этом YAS не позволяет задать максимальный размер сообщения и ограничить максимальную длину списка. Этот фокус можно повторить для других типов, поддерживаемых этой библиотекой - deque, stable_vector из boost, может еще что-то.

Можно подумать, что это проблема только одной библиотеки, но на самом деле, такая фича у библиотек сериализации встречается часто (при том, что это самая очевидная ошибка из всех, что они могут сделать). Вот, например, cereal - второй по счету результат в выдаче на github по запросу serialization для языка С++.

Очень похоже, не правда ли? Я проверил, там нигде размер не проверяется.
А теперь внимание, простой вопрос - если настолько простая дыра в безопасности лежит на виду в проекте, у которого больше 300 лайков на github и за которым следят больше сорока человек, то сколько таких дыр будет в проекте попроще? :)
К слову, C++ реализация protocol buffers ничем подобным не страдает, там можно ограничить максимальный размер сообщения сверху (64Мб по умолчанию, но можно задать свое значение), а максимальная длина их base-128 variant-ов ограничена 64-мя битами.

Бывают примеры и посложнее, вот, например реализация message pack для Go, там, на 179-й строке есть функция unpack, которая вызывает сама себя рекурсивно, в зависимости от того, что встретит в потоке данных. Это нужно для того, чтобы парсить всякие вложенные структуры данных, вроде массива строк, т.е. глубина рекурсии зависит от входящих данных! Можно очень легко создать такое сообщение, которое заставит эту функцию вызвать себя очень много раз подряд и сожрать очень много памяти под стек, вообще сколько угодно памяти (в Go не получится переполнение стека из-за особенностей рантайма, но стек расти все равно будет). Если бы это было написано не на Go, а скажем, на Java, мы бы могли получить переполнение стека куда быстрее, чем сожрать всю память :)

В общем, нужно писать хороший и безопасный код и не писать плохой, а также стараться использовать поверенные решения и анализировать сторонний код, используемый в вашем приложении. Спасибо за внимание! :)

Про юнит-тесты

В последнее время модно ругать юнит-тесты, по разным причинам. Сложность поддержки в актуальном состоянии системы юнит-тестов, отсутствие 100% гарантии корректности кода в случае, если тесты проходят, использование интеграционных тестов, очень многий код сложно тестировать с помощью юнит-тестов, существование практики написания тестов тупо ради покрытия и тд.
Я не собираюсь быть адвокатом какой-либо из сторон спора, вместо этого, я хочу показать, что юнит-тесты - вещь простая и естественная, вытекающая из нормальной практики программирования.
Итак, когда опытный программист пишет код функции с нетривиальной логикой, он думает в том числе и в терминах инвариантов. Практически любой код содержит кучу инвариантов (инварианты циклов, инварианты состояния объектов и тд) и желание зафиксировать их в коде - вполне естественно. Обычно, это делается с помощью assert-ов. Assert-ом удобно проверять, например, что счетчик ожидающих обработки элементов, после выполнения цикла, будет равен нулю, либо, что указатель находится внутри массива, перед выбрасыванием исключения можно проверять - не останется ли объект после этого в невалидном состоянии, и тд и тп.
Но более сложные инварианты с помощью assert-а проверить проблематично. Здесь уже программисты часто прибегают к условной компиляции, для того, чтобы вставить дополнительные проверки в отладочный билд.
Все эти проверки засоряют код, который помимо основной логики и логики обработки ошибок, содержит теперь и кучу отладочного кода, который заботливо вырезается компилятором в релизной версии. Если написать много такого кода, то обязательно появится следующая идея - "а почему бы не вынести все это в отдельное место, чтобы оно не мозолило глаза" и появляются юнит тесты. Вот и все :)

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 - работа с периодическими источниками - поиск должен работать просто фантастически быстро.