среда, 26 февраля 2014 г.

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

вторник, 25 февраля 2014 г.

Akumuli: запись и хранение данных

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

Как известно, данные на диске можно хранить в различных B-деревьях, это такая структура данных, которая позволяет искать по ключу за логарифмическое время, но в тоже время - читая минимальное количество страниц памяти с диска. Для хранения time series данных, умные люди очень давно придумали TSB tree и некоторые другие структуры данных на основе B-tree.
Изначально, я планировал реализовать свой проект на основе TSB-tree, это вполне возможно и мне кажется, это и есть самый правильный дизайн. Но я попытался создать небольшой прототип на питоне и понял, что это не так просто, как кажется. Особенно, если хочется чтобы библиотека использовала фиксированное количество места на диске. Так как это персональный проект и я не могу тратить на него много времени, я решил отказаться от реализации TSB-tree, ведь помимо описанной мной проблемы тут есть проблемы синхронизации, проблемы целостности/восстановления данных, так как структура достаточно сложная.

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

Persistent storage

Итак, данные в akumuli хранятся в томах, размер каждого тома - 4Гб. Все тома создаются заранее, при создании хранилища, и образуют циклический список. В любой момент времени мы можем писать только в один том. При этом, метки времени в соседних томах могут пересекаться. На высоком уровне, алгоритм записи выглядит очень просто - мы пишем в открытый том до тех пор, пока он не заполнится, затем, открываем следующий и пишем в него. Если в следующем томе есть данные - они теряются. Вы уже наверное поняли, что глубина хранения данных определяется размером хранилища, новые данные просто перезатирают самые старые, также как в rrd-tool. Это осмысленное решение а не недостаток дизайна, оно не позволяет задавать глубину хранения для каждого параметра в отдельности, но зато, позволяет писать софт, который работает предсказуемо, не падая от нехватки места на диске. 

Внутри тома все тоже устроено достаточно просто. Том, по сути, очень похож на узел B-tree, но только очень большой. Вначале тома располагается header с метаданными (количество добавленных элементов и тд), далее следует массив смещений, оставшееся место занято непосредственно данными. Каждый элемент данных начинается с заголовка - метки времени и идентификатора параметра, за которым следуют пользовательские данные переменной длины.
Данные записываются начиная с конца тома, в обратном направлении. На изображении, смещения увеличиваются слева направо, при этом элемент данных "А" был добавлен первым, "В" - вторым, а "С" - третьим. В массив смещений записываются смещения элементов данных (как неожиданно!). Причем смещения, как раз записываются в прямом порядке.
На изображении, элемент массива с индексом 0 содержит смещение элемента "А" и был добавлен первым. Запись в том заканчивается тогда, когда массив смещений и данные встречаются, т.е. между последним добавленным элементом массива данных и последним смещением не достаточно места для добавления следующего элемента данных.

Такая схема позволяет, во первых, хранить данные переменной длины, во вторых, записывать данные в том очень быстро (запись линеаризуется, мы используем пропускную способность дисков по максимуму) и самое главное, эта схема позволяет очень быстро сортировать данные, для этого достаточно отсортировать массив смещений. Тот факт, что данные в томе могут быть отсортированы в порядке, отличном от порядка добавления также отражен на рисунке (элементы массива 1 и 2). Помимо этого, данная схема позволяет легко вводить избыточность, которая нужна для эффективного поиска редко обновляющихся данных. Можно добавить смещение старого элемента еще раз, чтобы алгоритму поиска не нужно было сканировать том глубоко (показано пунктирной линией).

Эта схема позволяет также хранить вместе с пользовательскими данными всякую вспомогательную информацию, сводки (rollups), хинты для алгоритма поиска и прочие метаданные.

In-memory cache

Самая главная проблема здесь - как правильно выбрать момент для сортировки данных в томе? Можно сортировать понемногу при добавлении каждого элемента, можно подождать, когда какие-то данные станут достаточно старыми (выйдут за пределы окна записи и станут неизменяемыми) и сортировать этот диапазон массива только после этого. Можно сделать еще лучше и не сортировать данные вообще никогда, вместо этого, записывать  смещения сначала в кэш, в оперативной памяти и постепенно сливать смещения самых старых элементов на диск.

Кэш в памяти у меня построен на основе B-tree (реализация гугла), в качестве ключа используется кортеж из метки времени и ид-ра параметра, значение - смещение элемента в томе. Б-деревья выбраны не случайно, time-series данные имеют одну особенность, метка времени как правило возрастает, это значит, что данные в B-tree добавляются почти всегда в порядке возрастания, а это sweet spot для B-tree. Режим, в котором вставка в B-tree выполняется очень быстро.

Кэш организован следующим образом, данные хранятся в bucket-ах (штука, которая содержит внутри себя дерево и кое какую метаинформацию). Каждый такой bucket отвечает за небольшой интервал времени, кратный глубине окна записи, эти интервалы не пересекаются. Bucket-ы объединены в список, в хронологическом порядке. Устаревшие bucket-ы, запись в которые уже запрещена (они вышли за границу окна записи), извлекаются из конца списка по очереди, их содержимое перебирается в порядке возрастания и получившаяся последовательность смещений записывается в соответствующий сектор массива смещений тома. Future write приводит к созданию нового bucket-а (на самом деле не созданию, а извлечению готового из пула, zero allocation).

Concurrency

В кэш можно писать параллельно из нескольких потоков, чем больше потоков пишут в один bucket, тем больше lock contention и тем все медленнее. Чтобы решить эту проблему, bucket содержит не одно дерево, а несколько, по количеству процессоров/ядер. Каждый поток сначала выбирает свой экземпляр B-tree из bucket-а, лочит его, а затем - пишет в него. Это уменьшает contention и улучшает cache locality, в общем, все работает лучше. При сохранении последовательности смещений на диск, последовательности, полученные от отдельных деревьев сливаются в одну, а уже потом - записываются в том.

Comming soon

В следующей статье я постараюсь описать то, как выполняется поиск.

понедельник, 24 февраля 2014 г.

Несколько месяцев назад, я начал работать над своим собственным open source проектом. Попробую рассказать почему я это все начал и чего хорошего хочу сделать.

Итак, все началось с того, что я не смог найти time-series БД, которая бы являлась продуктом с открытым исходным кодом и при этом нормально работала. Time-series данные, это любые данные снабженные меткой времени и идентификатором параметра (aka идентификатор метрики, aka идентификатор источника). Параметры могут соответствовать, например, разным сенсорам, разным измеряемым величинам, разным пользователям в click stream-е и тд.

Главная проблема time-series данных в том, что их всегда очень много. Представьте себе большой датацентр, в котором работают 10 000 машин, на каждой из которых специальный демон десять раз в секунду измеряет количество свободной памяти, загрузку CPU и отправляет это все в БД. Казалось бы, десять раз в секунду это не очень много, но это уже 100k операций записи в секунду, и это не пик, это sustained write rate, для данных, не помещающихся в память. А что, если потребуется измерять значения параметров не десять раз в секунду, а сто?

Самое известное решение этой проблемы - rrd-tool, де факто стандарт во многих областях, имеет жутко неэффективный формат хранения данных с огромным количеством недостатков. Для того, чтобы понять как плох rrd-tool (но в то же время хорош, для определенных применений), нужно понять как он хранит данные, я не буду вдаваться в подробности, скажу лишь, что точность хранения меток времени там ограничена, количество параметров там также ограничено, чем их больше, тем медленнее все работает. Запись в rrd файл это множество random writes. В общем, rrd подходит для чего-нибудь небольшого и не требовательного.

Представитель принципиально другого класса систем - open tsdb (и 100500 подражателей) тоже не слишком хорош, на мой взгляд. Во первых, оно зависит от hadoop и hbase. Hbase используется для хранения данных. Поэтому, open tsdb нельзя использовать в качестве embedded БД. Если вы пишете софт, который работает на каком нибудь промышленном ПК, собирающем данные от каких-нибудь датчиков, то вы open tsdb использовать не сможете. Помимо этого, open tsdb округляет метки времени. Для мониторинга серверов (задача, для которой open tsdb создавалась) это подходит. Для других применений - не всегда.

Самый главный недостаток всех этих систем - они игнорируют специфику данных. Как правило, они формируют некий ключ, комбинируя идентификатор параметра и метку времени, затем этот ключ используется для записи (в hbase, cassandra, leveldb etc). Для того, чтобы найти это значение, нужно использовать точно такой же ключ. По сути, эти БД работают с точечными данными. Отсюда все эти округления меток времени и тд. Главная задача той же open tsdb - построить сводки (rollups), а не поиск значения параметра X в момент времени Y.

В настоящей time series БД, операция записи создает не точку, а линию. Если мы записали значение параметра в момент времени T0, а затем ищем его значение в момент времени T1, причем T1 > T0, то мы должны найти ранее записанное значение. Это логично, ведь между моментами времени T0 и T1 значение параметра не менялось. К сожалению, большинству time series баз данных это неведомо.

В общем, я пришел к выводу, о необходимости создания специализированного бэкенда для таких данных. LevelDB, HBase и им подобные - не решают всех проблем. Собственно, я собираюсь заполнить данный пробел, создав быстрый и в тоже время "правильный" backend.

Цели пока такие:
  • Способность выдавать порядка миллиона операций записи в секунду на моем ноутбуке.
  • Использование фиксированного количества места на жестком диске (как rrd-tool).
  • Кэширование наиболее актуальных данных в памяти.
  • Хитрый алгоритм поиска, который я придумал, но еще не реализовал :)
Первые две цели уже достигнуты, остальное - в процессе. В ближайшее время я постараюсь описать более подробно архитектуру и алгоритмы, в том виде, в котором это все существует сейчас.

Behold!

воскресенье, 14 апреля 2013 г.

Деление на ноль, это отличная тема для троллинга, между прочим:
Есть такой стандарт — IEEE754, это стандарт на floating point вычисления. Согласно этому стандарту, при делении числа на 0, получается либо +, либо — бесконечность. Но это было сделано не потому что 1/0 = бесконечности, а для того, тобы упростить жизнь программистам. Начнем с того, что в этом стандарте существуют 3 нуля — 0, –0 и +0. Два последних получаются при underflow, при underflow нам не хватает точности для того, чтобы представить число, мы можем сохранить только знак.

Если теперь представить какое–нибудь вычисление, в котором какое–нибудь число делится на постоянно уменьшающееся значение, то при достаточном количестве итераций мы получим underflow, то есть, по сути — ноль. Если бы в FP вычислениях, при делении на ноль получалось бы NaN, как того требует здравый смысл, то мы получили бы NaN вместо результата вычисления. Но вместо этого мы получим Inf, что в данном случае верно и правильно, мало того, мы получим правильный знак у Inf, в зависимости от того, с какой стороны произошел underflow, мы получим либо +Inf либо –Inf, bingo!

И теперь внимание — большинство делений на 0 в реальных программах происходят именно в такой ситуации, как я описал — ноль получается в результате underflow, а не нормальных вычислений. Вычисления с плавающей точкой — это аппроксимация, они априори не точны. В данном случае, разработчики стандарта пожертвовали точностью в угоду корректности. Но из–за этого 90% программистов считают что 1/0 должно быть равно бесконечности :)
Читатель, учись делить на ноль правильно!

воскресенье, 20 января 2013 г.

Restricted Transactional Memory в Haswell

Пожалуй я не сильно ошибусь, сказав что существует всего два механизма управления изменениями - пессимистичный и оптимистичный. Первый мы уже давно используем в своих программах в виде всевозможных мьютексов и семафоров. Второй механизм, до недавнего времени, применялся в различных СУБД.
Software transactional memory (STM) - реализация второго механизма управления изменениями, по сути это просто транзакции в коде. Вы помечаете участок кода, который должен выполняться в рамках одной транзакции. Во время выполнения, система запоминает все что вы читаете и записываете (поддерживает read set и write set). В случае, если произошел конфликт, несколько транзакций попытались изменить одни и те же переменные, происходит откат транзакции, система возвращается в исходное состояние, после чего транзакция выполняется повторно.

Существует множество реализаций STM на разных языках и платформах, тем не менее, это по прежнему экзотика. Про железные реализации я вообще молчу, не случившийся Rock и BlueGene/Q для суперкомпьютера IBM, но есть и повод для оптимизма.
Примерно год назад, Intel анонсировали новый процессор - Haswell, который будет поддерживать набор инструкций Transactional Synchronization Extensions (TSX). Restricted Transactional Memory (RTM) - это часть TSX, добавляющая поддержку транзакционной памяти. Как видно из названия - поддержку ограниченную.

Для программиста, RTM это четыре новых инструкции - XBEGIN, XEND, XABORT и XTEST.
XBEGIN - начинает транзакцию, XEND - ее фиксирует, XABORT - откатывает. Инструкция XTEST позволяет узнать, находимся мы сейчас в транзакции, или нет. В Visual Studio 2012 есть интринсики, с помощью которых можно удобно использовать эти инструкции. Называются они соответственно - _xbegin, _xend, _xabort и _xtest.

Работает это следующим образом, вы вызываете ф-ю _xbegin, которая возвращает статус транзакции. В случае, если ф-я вернула _XBEGIN_STARTED - транзакция была начата, в противном случае - произошел откат транзакции по какой-либо причине. В случае отката транзакции, управление возвращается в ее начало, то есть в _xbegin() и в этом случае, _xbegin вернет статус, отличный от _XBEGIN_STARTED. В конце транзакции вы должны вызвать ф-ю _xend, в этом случае произойдет фиксация транзакции. Ф-я _xabort прерывает выполняющуюся транзакцию, управление вернется в _xbegin. Разные биты статуса _xbegin позволяют определить причину отката транзакции, был это _xabort, конфликт записи или что-нибудь еще.

Но на самом деле все далеко не так радужно, как может показаться. Недаром в названии есть слово `Restricted`, существуют значительные ограничения на код, который может выполняться в транзакциях. Во первых, в транзакции можно выполнять только простые загрузки и сохранения, даже простое переключение контекста прервет транзакцию. Во вторых, размер write-set и read-set ограничен размером L1 кэша, если вы попытаетесь переписать в транзакции мегабайт памяти - ничего не получится. В третьих, RTM работает на уровне линий кэша, поэтому здесь возможен false sharing, в том случае, если разные переменные попадают на одну кэш линию.

Именно по этому, Intel не гарантирует, что транзакция вообще завершится когда-нибудь. Поэтому, код, использующий транзакции, должен следить за тем, сколько раз и по какой причине транзакция откатилась. Реализация должна предусматривать fallback механизм, например, если наша транзакция откатилась N раз, мы можем попытаться захватить соответствующую блокировку и выполнить тот же самый код без транзакции, используя эксклюзивный доступ к данным.

По этим причинам, код, выполняемый в транзакции, должен быть коротким, он не должен пытаться делать I/O или что-нибудь кроме простых загрузок и сохранений в память, он должен изменять и читать как можно меньше данных. Именно по этому, люди, ждущие от RTM чего-то похожего на STM из Haskell будут разочарованы.
На мой взгляд, RTM подходит для создания различных lock-free структур данных. Если без RTM написать lock-free очередь - было делом нетривиальным, то с RTM все станет намного проще. Вместо того, чтобы ломать себе голову над тем, как с помощью CAS реализовать ту или иную операцию, достаточно просто обернуть ее в транзакцию. Я уже молчу о более сложных структурах данных.

Для иллюстрации вышесказанного, я написал простой, lock-free двух-связный список. Элементы можно добавлять и удалять из любого конца списка.

Это всего лишь proof of concept, не более. Здесь не реализован fallback-механизм, поэтому в случае ошибки в коде, он может зациклиться. Помимо этого, данный код не будет работать на обычных процессорах. Он будет падать по `undefined instruction`. Запустить его можно только в эмуляторе:
sde -hsw -rtm-mode full -- appname.exe
На данный момент сложно судить о производительности. Я очень надеюсь на то, что RTM будет позволять писать код, который будет работать быстрее, чем аналогичный код, построенный на CAS. На это можно надеяться, так как транзакции все пишут в кэш, а для обнаружения конфликтов записи используется cache coherency протокол, который есть и сейчас. Насколько я понял, все операции записи внутри транзакции - неблокирующие, в отличии от xchg.

Ссылки:
Exploring Intel® Transactional Synchronization Extensions with Intel® Software Development Emulator
Intel® Software Development Emulator
Intel® Architecture Instruction Set Extensions Programming Reference (Chapter 8)

среда, 13 июня 2012 г.

Singly resizable array

Тема сегодняшнего поста - динамические массивы. Динамический массив, это одна из наиболее часто используемых структур данных. Рассмотрим простой динамический массив, имеющий две операции - добавление элемента в конец массива и поиск элемента массива по индексу. Наивный алгоритм, последовательно добавляющий множество элементов в массив, каждый раз полностью копируя его содержимое, будет иметь квадратичную сложность.

Естественно, операцию push_back в реальной жизни реализуют с помощью метода удвоения. Алгоритм, последовательно добавляющий множество элементов в массив методом удвоения, будет иметь линейную, амортизированую сложность. По памяти все тоже неплохо, в любой момент времени, наш динамический массив будет иметь capacity <= N*2, где N - количество элементов массива, а capacity - его вместительность.

пятница, 1 июня 2012 г.

Производительность, это очень сложно. Существует огромное количество факторов, не имеющих прямого отношения к логике работы программы, которые следует учесть, для того, чтобы приложение эффективно использовало ресурсы процессора.
Вот наглядный пример:
Код, использующий один счетчик и InterlockedIncrement работает, в среднем, в три раза медленнее нежели код, исползующий класс ConcurrentCounter. Почему это происходит, должно быть достаточно очевидно. InterlockedIncrement блокирует шину памяти на время выполнения, т.е. по сути, все потоки получают доступ к переменной по очереди, синхронно.

  • За какой асбракцией не пряталась бы инструкция lock xchg, знать что именно происходит на низком уровне все равно придется.
  • Так же придется знать что такое TLB, write buffer, как происходит инвалидация кэша, что такое false sharing и тд.
  • Загрузка процессора под 100% вовсе не означает что он используется эффективно.
  • Хотелось бы все эти заботы переложить на плечи разработчиков библитек и инструменов разработки.