Наверх ▲

Tarantool/Silverbox efficient in-memory storage

Юрий Востриков Юрий Востриков Один из ведущих разработчиков Mail.Ru.

Юрий Востриков: Здравствуйте, меня зовут Юрий Востриков, я представляю компанию Mail.Ru. Сегодня я попробую рассказать о решениях класса "in-memory" и их использовании для хранения данных.

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

С другой стороны, скорость последовательного доступа у дисков не так плоха. Она не сильно отличается от памяти: лишь в разы (50). Вывод: если наша база данных каким-либо образом требует произвольного доступа к диску, то о производительности речи не идет. Обычно на такие машины устанавливают определенный объем памяти, достаточный для размещения базы данных на диске целиком. Зачем необходима база данных на диске, когда мы и так все кэшируем?

Логично саму базу полностью поместить в оперативную память, а диском пользоваться как лентой, куда можно периодически скидывать состояние, чтобы можно было перезагрузить сервер или произвести его модернизацию. Руководствуясь этой идеей, мы написали фреймворк, а на его базе – конкретное Key-Value хранилище.

Основное свойство, которое предоставляет фреймворк, - это хранение в памяти. Ничего лишнего поверх сетевого ввода-вывода. Естественно, так как это база, присутствует сетевой ввод-вывод. Чтобы не извлекать его каждый раз, мы предоставляем некую abio.

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

Естественно, фреймворк не получается сам по себе. Обычно он вырастает из известного и успешного продукта.

Так произошло и в нашем случае. В Mail.ru мы накопили определенный опыт, написав 4 или 5 баз. А потом суммировали его, чтобы каждый раз не изобретать велосипед.

Помимо самого фреймворка, я расскажу также о нашем Key-Value хранилище, которое сохраняло кортежи, а не только пары Key-Value.

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

Итак, чуть-чуть подробнее о фреймворке. Это, прежде всего, распределитель (англ. allocator). Многие могут задать вопрос: "Зачем в очередной раз изобретать велосипед, создавая собственный распределитель? Можно пользоваться malloc".

Дело в том, что системный навык не любит такой характер нагрузки, при котором в нем хранится и удаляется большое количество мелких объектов.

Беда в том, что имеет место фрагментация данных. Процесс протекает достаточно медленно, хотя и верно. После трех недель работы сервер начинает тратить на внутренние нужды около 30-40 % процессорного времени. Остается только перезапустить процессор. Естественно, для работы базы данных, имеющих важное значение для вашего сервиса, подобное не допустимо.

К счастью, есть решение, найденное инженерами фирмы SUN. Это так называемое slab-распределение. Оно используется во многих проектах, например, в Memcached. Распределителем из Memcached мы пользовались в предыдущих версиях, но потом решили его улучшить.

Распределение slab характеризуется высокой скоростью работы и предназначено для хранения большого количества малых объектов. С ним связаны достаточно низкие накладные расходы, и, в силу своего дизайна, он не подтвержден к внешней фрагментации.

"Slab" в переводе с английского означает "плита". Вся память распределяется на "плиты" примерно одинакового размера. В нашем случае мы используем 4 мегабайта.

Дальше "плита" форматируется для хранения объектов определенного размера. Все объекты в рамках одной "плиты" имеют один размер. Они "прошиваются" так называемым списком свободных объектов.

Для хранения списка не используется никакой дополнительной памяти. Для этого используются свободные байты прямо из самих объектов. Однако есть некоторые ограничения. Нельзя производить распределение объектов, меньших, чем 1 указатель. Необходимость в столь малых объектах отсутствует.

Соответственно, распределение – это получение первого элемента из начала списка, что является достаточно дешевой операцией. Поиск по дереву производить не требуется.

Следующий неприятный момент – это освобождение памяти. Именно эта процедура нас не устраивала в Memcached. Когда происходило освобождение некоего элемента, требовалось найти "плиту", к которой он принадлежал.

Существует несколько вариантов осуществления поиска. Например, можно хранить в нем указатель. Для каждого выделенного элемента это стало бы своего рода пенальти размером в 4 или 8 байт (в зависимости от архитектуры). Если вы храните 100 миллионов объектов, то на обратные указатели придется потратить 800 мегабайт. Это нерационально.

Второй вариант – это то, что делает Memcached. Внутри они "запоминают" не указатель, а размер. С помощью определенных вычислений, связаных с размером, выясняется, куда его необходимо вернуть. Это работает, но "таскать" с собой размер не всегда удобно.

Мы пользуемся другим алгоритмическим методом. Он заключается в следующем. Все наши slab всегда выровнены на границе четырех мегабайт. Зная адрес объекта, всегда легко найти slab, к которому он принадлежит. Это нехитрая байтовая арифметика. Поэтому все хорошо работает. Дополнительные расходы практически отсутствуют.

Следующий пункт моего выступления  касается сетевой части. Вариантов написания высокопроизводительных сетевых серверов в Unix немного. Это связано с необходимостью использования какого-либо механизма опроса. Архитектуры, которые ответвляются или находятся в потоке выполнения, плохо масштабируются на тысячи соединений.

Чтобы не создавать сетевую часть для каждой системы заново, логично пользоваться некой библиотекой, предоставляющей оберточный сервис. Таких библиотек несколько. Нам нравится библиотека libev. Она замечательная и не тормозит, как libem.

Сетевая часть совместно с библиотекой превращается в своеобразного "паука" функции обратного вызова. Пока обработка запросов остается несложной, все работает хорошо. Многие lib-серверы написаны на этом механизме. Проблемы возникают позже, когда обработка запросов усложняется. Процесс обрастает огромным количеством обратных вызовов и очень плохо управляется.

К счастью, в трехтомнике Дональда Кнута подобная ситуация хорошо описана. Существует механизм, называемый инверсией контроля выполнения. Он позволяет превратить "паукообразный" код обратно в линейный. Он нам всем хорошо знаком, прост в написании и предсказуем.

Используемые механизмы - это сопрограммы (англ. co-routines). Мы используем библиотеку libcoro того же автора, который написал libev. По-другому это можно назвать кооперативной многозадачностью (англ. fiber).

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

Я думаю, здесь присутствуют программисты, которым известен проект Mongrel.

Автор проекта утверждает, будто проект обязан популярностью тому обстоятельству, что парсер http написан благодаря Ragel. Мы ее тоже используем.

Затруднение связано с тем, что при старом подходе из-за обратных вызовов ничего хорошего получиться не может. Авторы сторонних библиотек не предполагали такой вариант их использования.

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

Немного о Persistance. Ничего нового изобретено не было. Мы пользуемся механизмом бинарных логов.

Это выглядит следующим образом. Из сети приходит запрос, мы его читаем и выполняем. Если все получается, в бинарный логин записывается, что транзакция прошла. Далее от диска приходит ответ: была произведена запись или нет. Далее мы или сохраняем транзакцию, или сообщаем клиенту: получилось - не получилось.

Здесь есть одна тонкость. Запись на диске в Unix-системах - блокирующаяся. При этом заранее предсказать степень заблокированности невозможно. Естественно, для сервера, обслуживающего тысячу соединений, блокирование, длящееся даже пару секунд, неприемлемо.

Вариантов решения проблемы несколько. Например, можно использовать отдельный трек, который производит запись на диск. Что касается нас, то мы используем отдельный процесс, с которым происходит общение по сокету. Таким образом, снижение скорости на диске не вызывает замедления самого сервера.

Также хочется отметить, что запись бинарных логов происходит строго последовательно, так как мы всегда дописываем «хвост». Поэтому мы используем диски всегда в максимально эффективном режиме.

В принципе, бинарных логов достаточно для восстановления системы. После загрузки мы проверяем логи и получаем в памяти полноценное состояние. Конечно, с течением времени происходит накопление логов. Со временем логов становится очень много, и восстановление занимает длительное время.

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

В наших системах снимок откладывается примерно раз в 3 часа. Восстановление измеряется минутами.

Как делают снимок? Естественно, основной процесс останавливать нельзя. Поэтому мы создаем ответвление, порождаем «ребенка», в памяти у которого находится полная копия оригинала. Происходит запись на диск.

Надо заметить, что в этот момент не происходит удвоения требований к памяти, т.к. в Windows используется такой механизм, как Copy on Write.

Что касается записи, то стоит отметить ее последовательность. Нам пришлось создавать специальный механизм торможения, чтобы процесс обратного сохранения на диск не "съедал" всю полосу дисков.

Немного о высокой доступности. Для базы, на которой хранятся важные данные, это критично. У нас есть два механизма высокой доступности: локальная реплика и удаленная реплика.

Локальная реплика выглядит достаточно странно. На одной машине запущено два экземпляра (англ. instance). Требования к памяти увеличены вдвое. Зачем? Это оправдано по следующим причинам.

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

Обе базы пытаются соединиться с одним и тем же портом. Получится только у одной. Будем называть ее мастером. Именно она обслуживает клиентов и выполняет текущие запросы.

Behold – так называется база, которая только наблюдает за процессом, т.к. порт занят. Но она может использовать шанс и стать главной. Мастер пропадает, знания подхватываются и выполнение продолжается.

С точки зрения клиента, соединение прерывается. Но недоступность отсутствует: база на эту пару минут не пропадает.

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

Коснемся вопроса конкретной реализации Key-Value хранилища. На самом деле это двойное хранилище, где содержатся кортежи. Оно обслуживает таблицу пользователей «Моего мира». Это примерно 150 записей и около 50 тысяч выборов в секунду. Все работает на одной машине.

Что умеет делать хранилище? В первую очередь, бинарный протокол специально разработан для асинхронных клиентов.

Второй момент. Это не просто Key-Value, это хранение кортежа. Поэтому ключей и значений может быть несколько. Третий момент. Оно специально предназначено для хранения разного рода сессий, записей о пользователях, счетчиков и т.п. Соответственно, производятся битовые и атомарные арифметические операции над числами. Организовать какой-либо счетчик, битовую карту, битовую маску достаточно легко.

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

Второй момент:  пространство имен однозначно поддерживается, поэтому при прибавлении «хвоста» к ключу аннулирования не требуется (как это делает клиент Memcached). Происходит экономия байтов. Так как сервер отличает строчки от чисел, индексы могут быть как числовые, так и строковые.

Хочется отметить, что данный код успешно нами испльзуется больше года.

Помимо бинарного протокола, используется эмуляция Memcache. Однако мы все-таки используем базу, а не кэш, поэтому "evictions" у нас отсутствуют. Данные сервера никогда не пропадают.

Второй момент. Удаление устаревших данных при помощи фонового fiber. C Memcache возникают проблемы, когда накоплено определенное количество устаревших данных. До перезапуска он никуда их не отдаст, если специально не использовать ключ. Это бывает не очень удобно. Fiber в этом отношении гораздо удобнее Memcache. 

Зачем приходится всё же следить? Так как все обновления обязательно попадают в бинарные логи, то для Memcached 100, 200, 300 мегабайт в секунду – это ничто. В нашем случае это достаточно дорогая операция, потому что запись производится на диск. У нас есть Memcache, работающие на этой технологии и генерирующие примерно 50 мегабайт в секунду. Это всё-таки много, так что будьте осторожнее.

К вопросу о производительности сервера, работающего в оперативной памяти. Она настолько высока, что на ее фоне сетевая нагрузка становится весьма заметной.

Предположим, у вас есть сверхбыстрая сеть, задержка которой составляет всего 1 миллисекунду. Чтобы запросить тысячу ключей, тысячу синхронных запросов, потребуется 1 секунда, а это дорого. С другой стороны, если вы попросите 10 раз по 100 ключей, время выполнения составит примерно 10 миллисекунд, т.е. в 100 раз быстрее.

Если есть подходящая возможность, производите группировку запросов. Это касается не только базы, о которой идет речь, но и memcached, и других баз памяти.

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

Следующий важный вопрос – это цена системного вызова. Обычно на обработку одного запроса требуется не менее двух системных вызовов.

Простой пример. Я проводил замеры в режиме эмуляции Memcached. Когда от него приходит достаточно большое количество клиентов и они требуют в каждом запросе по одному ключу, то системные вызовы отнимают 70% процессорного времени. Улучшение клиентского кода не даст желаемых результатов.

Поэтому старайтесь группировать больше данных в один запрос.

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

Что касается наших планов в отношении данного продукта, то мы хотим расширить бинарный протокол, который записывается на диск, чтобы осуществить доставку требуемых сервисов.

Во-первых, можно будет замерять отставание реплик, исчисляемое в секундах (миллисекундах, так как это сетевая задержка).

Во-вторых, можно будет восстанавливать систему по состоянию времени в прошлом. Например, приходит Вася, удаляет половину ваших пользователей в 12:00. Вы это знаете, и восстанавливаете систему на 11:55, чтобы все было, как раньше.

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

В-четвертых, планируется добавить внутрь интерпретатор Lua, который продемонстрировал хорошие результаты по итогам тестирования. Соответственно, появится возможность создавать процедуры с опцией хранения прямо на Lua. Они будут выполняться в контексте сервера.

В-пятых, планируется также эмуляция redis.

Данный продукт является открытым программным обеспечением с лицензией BSD. Например, распределитель slab достается достаточно легко.

Вопрос из зала: Может, переадресация?

Юрий Востриков: Первой версией распределителя slab, которую мы использовали, была версия из Memcached. Она была более-менее отчуждаемая. Но, к сожалению, у нее были проблемы.

Спасибо за внимание. 

Вопросы и ответы

Вопрос из зала:
Что работает с дисками?
Юрий Востриков:
Существует одна библиотека, которую пишет Oracle. Она называется IO. Она тесно интегрирована с потоками. Эта программа записи создается практически отдельным потоком.
В нашем случае запись отдельным процессом лучше тем, что отдельный процесс изолирован. Нет возможности наступить на собственные шнурки.
Вопрос из зала:
Вы смогли бы это делать в реальном времени. Это вас бы не тормозило.
Вопрос из зала:
Насколько я понял, по одному и тому же массиву данных может быть несколько индексов по разным атрибутам. Изменяются ли эти индексы транзакционно? Если да, то какой у них уровень транзакции?
Юрий Востриков:
Поддержка транзакции в том смысле, что можно будет обновить несколько записей за одно движение, сейчас отсутствует.
Вопрос из зала:
Насколько я понял, индексы могут снизить темпы записи. Физически происходит обновление нескольких структур данных?
Юрий Востриков:
Верно. Вам интересен сам механизм?
Вопрос из зала:
Может ли происходить чтение, когда кто-то изменяет индекс?
Юрий Востриков:
Устройство выглядит следующим образом. Вас интересует, конечно же, обновление. Можно ли прочитать грязные данные по какому-либо индексу.
Это невозможно, потому что в момент обновления происходит копирование существующей структуры и все операции выполняются на ней. Указатели на нее никуда еще не ставятся. После того, как мы все успешно сделали и подготовили, у нас получаются данные. Мы отдаем команду «на запись». Нам приходит подтверждение с диска о записи, в одно движение (в этот момент никто вклиниться не может), то есть атомарно, меняются все индексы сразу.
Вопрос из зала:
Мы работали с libcoro, у нас как-то не получилось. Сколько времени вы работали с libcoro. Или она у вас ввелась сразу?
У вас внутри показание работ Tarantool многократные или нет? Логика сама на потоки разбрасывается или все на одном ядре выполняется?
Юрий Востриков:
С coro проблем не было. У нас заработало сразу. Потоков нет - это однопоточный сервер. Соответственно, всегда одно ядро.
Вопрос из зала:
Насколько поддерживаемо решение в данный момент? Я вижу, что по функционалу здесь много пересечений с другими базами. С тем же redis есть параллели. Насколько велика вероятность того, что я буду использовать его в проекте, напишу какую-то функциональность, встречу какой-то баг, сообщу онем – и ошибка будет исправлена. Или подразумевается: сами используете, сами и правьте?
Юрий Востриков:
Эта база используется в качестве основной таблицы маршрутизации в «Моем мире». Зачем нам баги? Если вы нам расскажите, мы с удовольствием поправим.
Вопрос из зала:
Но существует множество багов, которые могут быть лично вам не интересны. Например, я попробую создать нечто на Solaris. Имеются случаи внедрения за пределами Mail.Ru?
Юрий Востриков:
Я про них пока не знаю. По поводу ваших версий странных сборок. Если они будут более или менее вменяемы, мы их будем поддерживать. Если вы там на каком-нибудь QNX собираетесь, то, естественно, нет.
Вопрос из зала:
Вопрос по бинарному протоколу. Это ваш протокол или он на основе чего-то?
Юрий Востриков:
Это внутренний протокол.
Вопрос из зала:
Что вы можете сказать насчет внедрения?
Юрий Востриков:
Есть внедрение для первого продакшна, которая используется в Mail.Ru. Есть игрушечный пример для Ruby, который я написал в качестве примера.
Вопрос из зала:
У вас есть слайд, где изображена схема с двумя загруженными базами данных. Вы сказали, в два раза больше оперативной памяти нужно. Если вдруг одна отключается, вторая подхватывает. Как происходит синхронизация данных между двумя базами, которые одновременно живут?
Второй момент. Если, предположим, мастер в базе, вылетает винчестер, вылетает поток. Есть ли какие-то данные, которые не успели записаться на реплику, чтобы на реплике поднять полноценный мастер? Или на реплику обязательно придет все, и у вас есть маркер – то мастер, то реплика – которые могут моделировать между разными серверами?
Юрий Востриков:
По первому вопросу. Синхронизация выполняется достаточно просто. Так как у нас есть мастер и не мастер, то мастер пишет логи. Эти логи работают постоянно в режиме онлайн.
Репликация - асинхронная. Существует вероятность, что часть данных, которые были на тот момент в сети, потеряется. Синхронная репликация на данный момент не предвидится. Это медленно и замедляет мастера, потому что он должен ждать ответ от реплики. Нас будет сильно беспокоить производительность.
Вопрос из зала:
Вопрос про распределитель. Насколько он медленнее, чем "++" реализации? Можно ли выделять массивы как куски памяти и непосредственно друг за другом, если меня это устраивает?
Юрий Востриков:
Я не сравнивал с «++» реализациями. Реализация нацелена на то, чтобы не было фрагментации heapy и в течение длительной работы сервера не происходила деградация. Производительность каждого конкретного запроса памяти может быть и не очень большой. Думаю, там замедляться особо нечему. Но это было не самоцелью.
По поводу массивов. Схема явно предназначена для хранения объектов одного размера, и вы не контролируете, как они будут расположены.
Вопрос из зала:
Почему везде лицензии, а не Apache или Crips?
Юрий Востриков:
Она демократична. Она нам нравится.
Вопрос из зала:
Не пытались ли вы использовать MySQL, DataBase?
Юрий Востриков:
После того как мы создали все необходимое и поняли, что оно хорошо работает, мы попытались найти альтернативу для Key-Value хранилища в открытом доступе. Посмотрели тогда на Redis, а он взял и "упал".
Вопрос из зала:
Вопрос по поводу слайда, который касается работы мастера и второстепенной поддержки работоспособности. Про поддержку синхронизации данных между групп. Вы сказали, что в реальном времени проигрывается бинлог или бинарные данные. Есть ли какие задержки или проблемы, связанные с чтением диска? Одно дело – ряд решений, сетевые обновления, их прохождение и применение. Но это связано с синхронной задержкой. С какими проблемами вы столкнулись при чтении с диска и проигрывании онлайн?
Юрий Востриков:
Проблем нет, поскольку странички файла, которые нужно читать, остаются некоторое время "горячими". В них пишет мастер. Это все находится в кэше страницы. Механизм работы локальной реплики таков, что она сначала забирает необходимые данные с диска, а потом дает требуемые ответы на различные запросы.

Комментарии

Нет ни одного комментария

Только пользователи могут оставлять комментарии

Возможно, вам будет интересно:

Филипп Торчинский

Филипп Торчинский

С 1994 года популяризирует открытые технологии и UNIX-решения. Работал экспертом по ОС Solaris в Sun Microsystems и Oracle. Автор двух книг по администрированию UNIX и Solaris.

Преподаватель и евангелист Solaris Филипп Торчинский говорит реальном опыте построения сетей с единой аутентификацией, но без Active Directory.

Владимир Габриелян

Владимир Габриелян

Владимир расскажет о различных этапах и инструментах управления разработкой высоконагруженных проектов, а также о возможных проблемах в процессе управления и о способах решения возникших проблем.

Вадим Габриелян демонстрирует грамотный подход ИТ-менеджера к процессу разработки на всех стадиях - от найма специалистов до выбора технологии.

Константин Осипов

Константин Осипов

Разработчик и архитектор СУБД Tarantool.

Доклад о новых возможностях Tarantool, появившихся за последние 6 месяцев, и диалог о планах команды на ближайшие полгода.