Информация

Дата основания
Местоположение
Россия
Сайт
team.mail.ru
Численность
5 001–10 000 человек
Дата регистрации

Блог на Хабре

Обновить

Как избежать скачков во времени отклика и потреблении памяти при снятии снимков состояния в СУБД в оперативной памяти

Блог компании Mail.ru GroupВысокая производительностьАнализ и проектирование системTarantool
Рейтинг +28
Количество просмотров 5,7k Добавить в закладки 44 Читать комментарии 34
Комментарии 34
Еще одна проблема с fork в том, что этот системный вызов копирует таблицу дескрипторов страниц.
и в ссылке у вас GDT. Наверно вы имели ввиду таблицы страниц (PTE которые).
Да, ссылка не туда вообще. Спасибо! Сейчас поправим. Речь про таблицу страниц: https://en.wikipedia.org/wiki/Page_table
danikin, вот тут — http://nadeausoftware.com/articles/2012/05/c_c_tip_how_copy_memory_quickly получают 40Гбайт\сек (т.е. около 6.5 секунд на всю вашу базу). Не очень понятна фраза:
>скорость может составлять 200-500 Мбайт/с для более-менее продвинутых структур данных
т.е. вы получается копируете не непрерывный блок памяти, а дерево (обходом по нодам?)
Почему так?
Потому что так устроены деревья. Они не непрерывно лежат в памяти. Почитайте тут: https://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B0%D1%81%D0%BD%D0%BE-%D1%87%D1%91%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE.

В Тарантуле используются структуры, которые лучше локализованы в памяти чем красно-черные деревья. Можно про них почитать тут: https://habrahabr.ru/company/oleg-bunin/blog/310560/. Но и они не непрерывно лежат в памяти.

Вы, очевидно, знаете о структуре данных, в которой можно хранить деревянный индекс и которая непрерывно лежит в памяти. Можете дать ссылку на описание? Наверное, мы что-то упустили из виду.

Сразу скажу, что дерево, разложенное в массив (по сути, отсортированный массив) — плохая структура. Она, конечно, копируется линейно, но в ней можно за LogN делать поиски, но вставка в нее будет за N.

Ваша ссылка, простите, неактуальна. Там 40Гб/сек они получают при копировании массива в 2 килобайта, потому что он сразу целиком помещается в кэш процессора. Посмотрите внимательней на графики — чем больше размер массива, тем меньше Гб/сек.
Верно, с размера массива, превышающего кеш процессора, скорость порядка 5Гб\сек, т.е. около минуты на 256Гб, тут я ошибся, простите. По поводу расположения в памяти — поясните, какая разница как локализована структура, если использовать placement new или shared memory (задействуя всю мощь аллокаторов), и копировать потом непрерывным блоком весь этот кусок памяти?
Вот именно.

Вы, Роберт, простите, теоретик. Давайте перейдем в область практики. Я у вас попросил вариант структуры в студию. Его все еще нет.

Насчет placement new и т.д., вы, очевидно, забыли, что структура изменяется. Из нее удаляются куски, добавляются новые, изменяются старые. Что делать с дырками? Оставлять как есть и просто выделять память в конец? Вариант структуры, которая не меняется, я привел выше — отсортированный вектор.

P.S.

Если вы сделаете в Тарантул pull-request, который мы примем и который бы поменял там все структуры таким образом, чтобы они копировались в среднем со скоростью 5Gb/s для баз данных в 256Gb, и которые при этом не занимали бы больше памяти, чем имеющиеся, то я вам тут же заплачу 3 миллиона рублей.

P.P.S.

Даже если допустить, что сделать структуры данных применимые для Тарантула, которые можно копировать со скоростью 5Gb/сек, то минута простоя и удвоенное потребление памяти — это все равно не вариант.
В своем проекте я использую key-value хранилище, целиком находящееся в гигантском куске shared memory. В частности, используется std::map и ее реализация берет на себя всю рутину по выделению\освобождению памяти в этом куске памяти (она сама знает как переиспользовать освобожденную память и не добавлять узлы только в конец, например).
Вы поймите: не нужно думать о стуктуре данных вообще: есть выделенный непрерывный кусок памяти, в нем расположена структура с вашими данными (std::map или самописное дерево, массив, неважно, оно какой угодно сложности и формы). Вы знаете где она начинается и где заканчивается. Поэтому вы его копируете непрерывным куском в другой участок памяти, и потом на диск сбрасываете уже сколько угодно долго.

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

Цель дампа (снимка) в том, чтобы быстрее стратовать после перезагрузки. Если у вас есть только логи, то они могут проигрываться долго, потому что в них, скажем, обновления одного и того же элемента данных могут присутствовать много раз, а в снимке — только один раз — финальное значение.
Отвечаю вопросами на ваш вопрос:
1. Вы не выделяете под свою структуру всю доступную память (линейный непрерывный кусок памяти) заранее, а только по мере добавления узлов (запрашивая новый адрес для очередного узла структуры у ОС каждый раз), таким образом вся структура оказывается размазанной и не расположена в непрерывном участке виртуального адресного пространства?
2. Ваша структура — это всего лишь данные и указатели на узлы структуры?
3. Если внутри вашей структуры где-либо используются абсолютные адреса, что стоит переделать ее на использование только относительных (смещений от начала структуры)?
Что происходит при апдейте и удалении? Например, удаляется строка из БД. Или, например, обновляется поле и увеличивается его размер. Я уже как минимум третий раз в различных видах задаю этот вопрос. Ответа нет.
Я вам в третий раз говорю о том, как можно быстро скопировать ВАШУ структуру, вы мне задаете упорно в третий раз вопрос о МОЕЙ структуре из моего проекта
Забудьте, у нас диалог глухого со слепым очевидно…
А я в третий раз спрашиваю — КАК? Наша конкретная структура не линейно лежит в памяти. У вас есть более умная структура? Расскажите, как она устроена. Мой скайп danikin2. Если у вас цель не самопиариться на хабре, а получить ответы на ваши вопросы, то стучитесь мне в скайп — все расскажу, ну или свой скайп оставьте — я вам постучусь.
Любую структуру можно расположить в непрерывно выделенном участке памяти. Это вам должно быть интересно, как (возможно) улучшить ваш проект, мне на него глубоко пофиг… Скайп я вам свой давать не собираюсь, если хотите — стучите в джаббер ara1307@jabber.org.
Постучался вам с гмейла, danikin1@gmail.com

Надеюсь, у вас хватит уверенности в себе пообщаться со мной и вы не будете скрываться :-)

«Любую структуру можно расположить в непрерывно выделенном участке памяти» — ответа на вопрос как это сделать так и не поступило. Возможно, если выйдете на связь, расскажите. Пока звучит голословненько.
Ну и чем закончилось все?
Пришли к общему знаменателю. Роберт, вы не против, если я опубликую нашу переписку?
Читать с конца :-)

Denis Anikin <danikin1@gmail.com> Mon, Dec 12, 2016 at 8:45 AM
Reply-To: Denis Anikin <danikin1@gmail.com>
To: Robert <robert.ayrapetyan@gmail.com>
В целом, идея интересная. Надо экспериментировать и считать, какой там реально выигрыш по цпу и какой проигрыш по памяти на реальных кейсах.

Sent from myMail for iOS

Monday, 12 December 2016, 06:20 +0300 from Robert <robert.ayrapetyan@gmail.com>:
У себя использую Boost.Interprocess segregated storage pool, перемещений там не используется, и память мендежеру сегмента никогда не возвращается (как у вас), но для моих целей это и не нужно.
Это нечто похожее на ваш аллокатор (набор chunks поделенных на ноды фиксированного размера).

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

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

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

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

Поэтому — фактически хуже по памяти (незначительно), но ускорение в копировании — в 10 раз (судя по вашим данным в статье, где вы пишите: скорость может составлять 200-500 Мбайт/с для более-менее продвинутых структур данных).

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

On 12/11/16 13:01, Dennis Anikin wrote:
Давайте по порядку.

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

2. Ваши оптимизации вышеуказанного алгоритма лучше чем вышеуказанный алгоритм по скорости, но хуже по памяти (временная копия будет занимать больше, из-за копирования дырок). Память vs скорость — извечный вопрос. Нельзя, ИМХО, говорить, что жертвовать одним или другим лучше — надо разбираться в конкретной ситуации глубже, а если разобраться нельзя, то хотя бы оставлять юзеру опцию.

3. Нулей (если вы так называете дырки) может быть много. Что я имею в виду тут? Мы аллоцируем сразу столько памяти, сколько пользователь разрешил нам в конфиге и потом уже в ней выделяем все собственными аллокаторами. Если юзер нам сказал аллоцировать 256Гб, и размер базы был сначала 256Гб, а потом оттуда поудалялось случайных записей так, что ее размер упал до 1Гб, то процесс будет потреблять по прежнему 256Гб (в RSS). Потому что мы не перемещаем участки, чтобы они шли подряд — мы оставляем дырки, фиксированного размера, разделенные на группы (каждая группа — свой размер), а потом их заполняем, чтобы выделение памяти было за O(1) (используем алгооритмы сходные с этими https://en.wikipedia.org/wiki/Slab_allocation). В ваших алгооритмах и структурах, возможно, есть перемещение, причем так, что оно не влияет сильно на скорость доступа и при этом, чтобы дырки все убирались изнутри в конец, предполагая таким образом, что копировать надо не все максимальные 256Гб как в нашем случае, а до какой-то отсечки, после которой точно уже идут только дырки. Поделитесь ими, пожалуйста. Почитаем. Если перемещения у вас нет, то 1Гбайтная база будет копироваться в укромное место в памяти путем копирования всех 256Гбайт вместе с дырками.

41 GMT+03:00 Robert <robert.ayrapetyan@gmail.com>:
Голосом я общаться не боюсь, считаю, что технические вопросы обсуждать голосом не продуктивно.

Если вы не против — продолжим общаться письменно (тем более что по сути уже все озвучено, думаю).
Относительная адресация — это лишь один из способов реализации. Есть еще другой — явно запросить линейный адрес начала сегмента при выделении у ОС. Тогда внутри структуры вы можете пользоваться абсолютными адресами и оверхеда на конвертацию не будет. По поводу дырок — ничего страшного, скопируете эти дырки вместе с полезными данными. Это небольшая плата за максимально возможную скорость копирования. Конечно, если у вас в среднем объем дырок сопоставим с объемом данных, то данная стратегия не выгодна, но здесь возникает вопрос об эффективности реализации аллокатора памяти в ваших структурах.
Цитирую ваш комментарий с хабра:

«Если вы сделаете в Тарантул pull-request, который мы примем и который бы поменял там все структуры таким образом, чтобы они копировались в среднем со скоростью 5Gb/s для баз данных в 256Gb, и которые при этом не занимали бы больше памяти, чем имеющиеся, то я вам тут же заплачу 3 миллиона рублей.»

Насколько я понял, скорость здесь важна только для минимизации лока базы при первоначальном копировании (RAM to RAM), а дальше (дамп на диск) уже не критичен по скорости (т.к. здесь уже база разлочена и ничего не мешает работе клиента). Мое предложение отвечает данному запросу (5Гб\с, 256Gb данных и нулей копируются в 256Гб данных и нулей, но не бойтесь — коммитить я не собираюсь и 3 миллиона рублей вы можете раздать своей команде на реализацию этой простой идеи или другой идеи с похожей идеей в основе).

Итого: мой вариант (быстро скопировать и затем медленно сдампить, избавляясь от дефрагментации) выигрывает у изначального в вашей статье (медленно скопировать и чуть быстрее сдампить), т.к. продолжительность лока базы (при копировании RAM to RAM) в разы меньше (именно это критично для бизнес-логики).
Ваша окончательная реализация (насколько я понял — версионирование отдельных страниц), вероятно, окажется эффективнее моего варианта (особенно в случаях, когда данные никто не менял в течении какого-то периода времени, тогда дамп выполниться мгновенно :), но оспаривание этой реализации в моих комментариях нигде нет.

On 12/11/16 11:10, Dennis Anikin wrote:
Вопросы-то те же самые остались. Относительная адресация — это круто! Но во-первых, надо каждый раз при обращении конвертить адреса, что слегка затормозит работу, во-вторых, наши структуры данных содержат «дырки» (но если ваши работают без дырок, то я бы послушал с удовольствием про них). Эти дырки сериализовать — это дополнительная нагрузка на диск, что сделает сериализацию медленнее, потому что узкое место у нас по прежнему диск при сериализации. Итого, ваш метод, если я правильно его понял, в нашем конкретном случае сделает все только хуже. И в качестве дополнительного бонуса при рассериализации сейчас у нас дефрагментация данных автоматом. В вашем случае это будет не так. Надо будет явно дефрагментировать.

Ну и самое главное, что даже в случае 5Гб/сек база данных все равно залипнет на минуту и потребление памяти удвоится (даже больше чем удвоится, если вспомнить про дырки), поэтому решение с копированием, даже с очень быстрым все равно пришлось бы отмести.

Если не боитесь пообщаться голосом, то я готов. Мне кажется, мы так быстрее придем к истине.

2016-12-11 21:49 GMT+03:00 Robert <robert.ayrapetyan@gmail.com>:
Отлично!

Теперь, как же так получается, что разные процессы по разным линейным адресам видят одни и те же данные?

Реализаций тут несколько. Одна из них — использование относительной адресации в струкрурах (т.е. нет никаких ссылок внутри структур, которые бы сконвертились в разные физические адреса в разных процессах, получится каша и несколько процессов не смогут работать с такой разделяемой структурой).
Остановимся на данной реализации.
Я утверждаю, что любую структуру (в том числе и используемую в вашем проекте), можно реализовать используя относительную адресацию. Действительно, относительная адресация есть частный случай абсолютной. Т.е. к некоему заранее известному базовому адресу (начало сегмента памяти) прибавляется некое смещение, хранящееся в полях вашей струкруры).

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

Собственно про это я и пытался сказать на хабре.

Теперь готов выслушать ваши вопросы, и постараться на них ответить.

On 12/11/16 10:39, Dennis Anikin wrote:
Привет.

Ок, звучит разумно.

Ответ на обо заданных вами вопроса — «Да».

Если чуть развернуть, то каждый процесс видит виртуальные свои страницы, которые мапятся на одни и те же физические страницы.

2016-12-11 20:25 GMT+03:00 Robert <robert.ayrapetyan@gmail.com>:
Привет, раз уж ввязался, то готов разъяснить и ответить на вопросы по поводу расположения любой структуры в непрерывно выделенном участке памяти.

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

Вопрос первый:

приходилось ли вам когда-нибудь пользоваться разделяемой памятью (shared memory)?

Если да, то вам известно, что все процессы, получившие доступ к разделяемой памяти, видят и оперируют одним и тем же непрерывно выделенным участком памяти

и структурами любой сложности в ней расположенными.

Известно ли вам о механизмах, лежащих в основе такого поведения?


Regards, Dennis


Regards, Dennis


Regards, Dennis

Давайте я постараюсь угадать, что вы имели в виду в своем комментарии. Вы имели в виду, что почему бы не включить huge pages (2Mb по дефолту, или еще больше) и это бы ускорило радикально fork, и убрало бы описываемую в этой статье проблему. Да?
Да, это один из вариантов. Я согласен, что структуры данных, которые поддерживают версионирование более эффективны, но именно проблему с копированием таблиц страниц можно обойти таким способом. Конечно, у больших страниц есть минусы при случайном доступе, возможно для вашего сценария они неприменимы.
Отличный способ. Меняется одно значение в базе данных и копируется минимум 2Мб (или какой размер страницы вы выбрали?). А на практике — еще больше. Допустим, если у вас дерево и надо его перебалансировать и сделать несколько записей в рандомные куски памяти, то, глядишь, и десяток мегабайт скопируйте. И так на каждое обновление значения в базе (а их может быть и сто тысяч в секунду). Отличное решение.

И да, я прошу прощения за недостаточно развёрнутый комментарий, сказывается низкий навык публичного общения. Slack низводит до уровня чат-бота :)

Ну все ок, я научился уже угадывать, что люди спрашивают. Просто иногда лучше явно спросить, что имели в виду, чтобы человек после уже ответа на вопрос не сказал бы, что «а я имел в виду совсем другое».
А можете поделиться реальным кейсом с цифрами? Размер БД, скорость изменений (как много изменений в БД), за сколько скидывается снимок на диск, сколько при этом накапливается изменений в диффах (соответственно сколько нужно дополнительной памяти), скорость диска, каков прирост вычислительной нагрузки во время сброса снимка на диск и т.д.
В отдельной статье обязательно поделюсь. Не все сразу.
Как только мы скопировали данные в отдельный буфер в оперативной памяти, нужно записать их на диск. Пока идет запись копии, исходные данные в памяти продолжают меняться. Эти изменения как-то нужно отслеживать

Вот этот кусок не понял. Да, данные меняются, но в оригинальной же памяти, зачем за ними следить? При заморозке считали айди последней транзакции из commit log'а и записали рядом. Все, у вас есть полная, консистентная копия, на момент транзакции N.
Я, возможно, криво сформулировал. Но имелось в виду ровно то, что вы написали :-)
Интересная задача, у меня вопрос, почему нельзя использовать отдельный процесс, который бы работал с копией базы на диске и применял к ней лог транзакций? То есть в результате медленно и верно подводил бы базу на диске к состоянию базы в памяти, полная синхронизация достигалась бы в моменты простоя базы, то есть когда не используются операции записи, а исключительно операции чтения. Лог транзакций можно разделить на части, допустим каждый час новый файл, после применения всех транзакций файл удалялся бы, ну или архивировался и отправлялся на долгое хранение в архив. После Х транзакций может делать контрольную сумму таблицы / базы и писать в лог, для проверки консистенции данных после применения транзакций к базе на диске.
«Интересная задача, у меня вопрос, почему нельзя использовать отдельный процесс, который бы работал с копией базы на диске и применял к ней лог транзакций?» — применять как? Загрузить всю базу еще раз в память, удвоив количество необходимой памяти, применив логи и сохранив в новый файл? Поделитесь алгоритмом применения, если не сложно, чтобы он был линейный по времени исполнения и меньше чем линейный по дополнительной памяти. Заранее спасибо.

Денис, а как реплицируются данные в Тарантуле при апдейтах? Это по идее как-то должно быть связано с резервированием? Я чего-то подзабыл:)

Если речь идет о репликации на другой сервер, то через лог транзакций
А зачем вам всю базу в память загружать? Вам необходимо загрузить только необходимые таблицы или части таблиц, либо как вариант процессу шарить конкретно по диску и писать в необходимые файлы пришедшие данные. Не претендую на истину, но SQLight как — то так и работает. Она для каждой записи дергает бд на диске, применяя транзакцию.
Вы имеете в виду пройтись по логу, понять, какие таблицы затронуты, далее считать эти таблицы из снэпшота, применить к каждой из них лог? Ну или распишите ваш алгоритм подробнее. Пока мне кажется, что ваш вариант будет в худшем случае O(N) по памяти, что есть явное ухудшение текущей ситуации, поэтому ответ на ваше «почему нельзя» такой — потому что это потребляет больше памяти.

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