Работа с памятью в Tarantool: Small — Specialized Memory ALLocators

Tarantool — это персистентная NoSQL СУБД в памяти с хранимыми процедурами на Lua. В него встроен SQLite и дисковый движок (Vinyl). Также для Tarantool написано очень много расширений, поэтому многие считают его «сервером приложений». Здесь есть индексы разных типов, а в одном спейсе кроме первичного индекса может быть множество вторичных. Также в Tarantool есть один transaction thread, который выполняет все транзакции в памяти, есть сетевой thread и WAL thread.

Как же устроена работа с памятью в этой СУБД?

Работа с памятью в Tarantool

Small (Specialized Memory ALLocators) — это коллекция аллокаторов. Зачем они понадобились, почему не использовать обычный malloc? Дело в том, что у нас есть определенные требования, характерные для высокопроизводительных приложений:

• Tarantool должен работать быстро. У нас есть грубая оценка — мы должны выдавать 1 Mrps на чтение и запись. Это, конечно, не в любом случае возможно, но при разработке приходится считать буквально каждую наносекунду.
• Контроль, независимость от стандартного аллокатора. Очень не хочется разбираться в разнице реализации malloc в разных libc, в разных дистрибутивах.
• Предсказуемые затраты памяти. «А сколько ее реально потребуется?». Хочется дать пользователям более или менее точный ответ, иметь свои собственные формулы для этого.
• Настраиваемость затрат памяти. «А можно сделать поменьше?». В некоторых случаях, на определенных данных пользователя, можно пробовать экспериментировать с настройками и экономить память.
• Fibers с маленьким стеком — нужна альтернатива. Поскольку транзакционный поток в Tarantool один, а код хочется писать линейный — мы используем зеленые треды, то есть файберы. Каждый запрос выполняется в своем персональном файбере, который может засыпать при I/O, уступая дорогу другим. Много одновременных запросов — много файберов (тысячи — норма). Поэтому размер стека каждого файбера ограничен (ориентируемся на 64 кБ). Соответственно память на стеке лучше бы по возможности экономить, используя какой-нибудь специальный аллокатор.

Как мы можем повысить производительность или компактность аллокатора?

1. Самостоятельно хранить размер выделяемой памяти:
   

   void free(void *ptr);
   void smfree(struct small_alloc *alloc, void *ptr, size_t size); 

В сигнатуре free видно, что туда передается указатель. По нему система понимает размеры выделяемой памяти. Мы можем помочь аллокатору, передав ему этот размер, ведь мы всё равно его всегда знаем.

1. Сделать несколько аллокаторов и использовать подходящий. Small — это библиотека аллокаторов, поэтому мы можем делать несколько разных и использовать подходящий для конкретного случая. А malloc — инструмент универсальный.
2. Поскольку архитектура Tarantool в основном однопоточная, можно сделать thread local и запретить миграцию памяти между потоками. Malloc же предназначен для работы многопоточной среде, и поэтому имеет свой оверхед.

Альтернативы

Аллокаторов существует множество:

• malloc
• tcmalloc
• jemalloc
• mimalloc
• тысячи их.

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

Small: стэк аллокаторов

Так выглядит статически фиксированная иерархия аллокаторов:


Любой аллокатор является прокси между памятью, которую ему кто-то выдает, и той памятью, которую он выдает своему пользователю. Malloc тоже так работает, в конечном счете он использует что-то вроде mmap или sbrk. У нас более длинная структура. Есть аллокатор Slab arena, которая использует mmap и умеет выдавать память тому, кто просит. Он обращается к Slab cache, который тоже что-то делает и выдает память целой группе аллокаторов. Mempool предоставляет память для Matras и Small alloc. Цветом показано, в каких компонентах Tarantool используются эти инструменты.

Отдельной веткой из одного аллокатора существует static — простой аллокатор очень маленького размера. В его основе лежит не mmap, а статический буфер на 12 кБ. Аллокатор берёт память из этого статического буфера и выдаёт её желающим. Да, его возможности очень ограничены, но у него тот же API, как и у многих других наших аллокаторов. Иногда бывает очень полезен.

Slab arena

void *slab_map(struct slab_arena *arena);
void slab_unmap(struct slab_arena *arena, void *ptr);

Умеет выделять и забирать обратно фрагменты только одного размера (мы используем 16 МБ). Делает это очень быстро и многопоточно. Еще одна особенность Slab arena в том, что он выделяет круглые адреса. То есть 16 младших битов адреса аллокации — это нули. Это сделано для защиты от ABA проблемы в lock-free списке под капотом аллокатора. Размер фрагментов, выделяемых Slab arena, определяется опцией конфигурации (2^N, не менее 64 кБ).

Slab cache

struct slab *slab_get(struct slab_cache *cache, size_t size);
void slab_put(struct slab_cache *cache, struct slab *slab);

Изначально сделан для thread local-использования и работает по принципу Buddy memory system. Для своих нужд использует Slab arena. Этот аллокатор разбивает гигантские куски памяти на более маленькие, в степени двух: например, 16 МБ делит на два фрагмента по 8 МБ, 8 МБ на два по 4 МБ, и так далее.


Если нужно выделить, скажем, 3 МБ, Slab cache берёт у Slab arena 16 МБ, делит на две части по 8 — это много. Тогда он делит 8 ещё вдвое, этого достаточно, и он отдает фрагмент памяти в 4 МБ. Если затем понадобится еще один фрагмент на 5 МБ, то Slab cache выделит 8 МБ, которые у него уже есть. Если нужно выделить 16 кБ, то в первый раз делений пополам надо сделать много раз (ровно 10), но оставшиеся неиспользованными половинки будут аккуратно сохранены и будут использованы при следующей аллокации.

Нюанс в том, что Slab cache отдает фрагмент, как это видно в сигнатуре, как указатель на struct slab. То есть в этом куске размера 2^N уже есть маленький заголовок, от которого нельзя потом избавиться. В этом заголовке аллокатор хранит информацию о своих buddy. Всё, что лежит после этого заголовка (и до конца куска размера 2^N) — уже предназначено для размещения данным пользователем. Реальный получаемый размер аллокации — 2^N — h, где h — что-то вроде сотни байт. С учетом этого, когда пользователь запрашивает блок некоторого размер — сначала этот размер округляется до ближайшего 2^N — h, соответственно в общем случае погрешность получается очень большая.

У Slab cache есть защита от осцилляций. Например, если мы попытаемся удалить фрагмент на 4 МБ, который использовался при запросе 3 МБ, то можем снова восстановить разделённые на две части 8 МБ, и так далее. Но это не всегда хорошо. Если мы будем выделять очень маленький фрагмент на 16 кБ с помощью пустого Slab cache, то придется выполнить десять итераций деления на два. И при удалении этого фрагмента придётся каскадно объединять всё обратно. Таким образом возможна нагрузка на аллокатор, при которой сложность аллокации будет неожиданно высокой. И защита заключается в том, что Slab cache объединяет куски «лениво». Если у него есть свободные фрагменты, он их не объединяет, а откладывает на потом. Таким образом средняя сложность поддерживается на уровне одного деления/слияния на одну аллокацию/освобождение. А это хороший результат.

Region

size_t region_used(struct region *region);
void *region_reserve(struct region *region, size_t size); // Опционально
void *region_alloc(struct region *region, size_t size);
void region_truncate(struct region *region, size_t size);

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

Вот пример работы:

void forward(const List& list)
{
   // Save the region state; the guard will reset the region to the original state upon destruction.
   RegionGuard truncater(&fiber()->gc);
   // We need to construct a list of another type.
   AnotherList fwd;
   for (const Item *item = list.first; item != nullptr; item = item->next) {
     // Allocate another item on the region.
       AnotherItem *next =
           region_alloc_object_xc(&fiber(->gc, AnotherItem);
       // … here *next is initialized … 
       // Add the newly created item to the list.
       fwd.insert(next);
   }
   destination(fwd);
   // The region is truncated here implicitly by truncater’s destructor.
}

Я написал абстрактную прокси-функцию, которая принимает на вход список из неизвестного количества элементов, преобразует его в другой список и передает в другую функцию. Классический вариант — разместить в памяти все эти элементы в списке. Потом нам надо не забыть еще раз пройтись по нему и всё удалить, после чего можем спокойно завершить нашу функцию. Но Region позволяет решить эту проблему несколько изящнее. Мы с самого начала создаем переменную, которая запоминает состояние аллокатора, а потом можем сколько угодно размещать в памяти. А при выходе из нее guard уничтожает всё, что мы выделили.

Еще очень приятно то, что, в отличие от стека, этих Region’ов у исполнителя может быть несколько. Например, в Tarantool при обработке запроса можно использовать Region, принадлежащий текущему файберу. В объекте транзакции также есть экземпляр того же самого типа аллокатора, он используется для размещения стейтментов транзакции, информации для отката транзакции, в общем всего, что требуется для транзакции. Этот транзакционный аллокатор чистится один раз, когда завершается транзакция.


Region использует большой фрагмент памяти (slab) из Slab cache. В начале входа в функцию в нем уже что-то скорее всего выделено. Оно чужое, его трогать нельзя. В процессе работы мы можем что-то размещать в памяти. Иногда для этого потребуется создавать новые slab’ы. Но когда мы выполняем truncate, то удаляем все slabы, которые мы создали, а также участок памяти, который был в slab’е на входе в нашу функцию.

LSRegion

void *lsregion_reserve(struct lsregion *lsregion, size_t size); // Опционально
void *lsregion_alloc(struct lsregion *lsregion, size_t size, int64_t id);
void lsregion_gc(struct lsregion *lsregion, int64_t min_id);

LSRegion расшифровывается как Log structured region. Этот аллокатор похож на предыдущий, только Region при освобождении удаляет последнее, что мы выделили (LIFO), а LSRegion умеет удалять самые старые выделенные им фрагменты (FIFO). Каждое выделение памяти ассоциируется с идентификатором поколения, который от выделения к выделению не убывает. Мы можем размещать в памяти много данных одного поколения, потом переключаться на следующее поколение и снова размещать в памяти много данных. А потом взять и целиком удалить какое-нибудь старое поколение. Это классическая задача LSM-дерева, которое накапливает информацию в памяти, затем скидывает ее на диск и удаляет из памяти.

IBuf

Один из двух сетевых буферов, предназначенный для чтения из сокета. Он работает с запросами, приходящими из сети, причем для обработки запросов они должны быть непрерывны в памяти. Поэтому IBuf запрашивает у Slab cache фрагмент памяти и использует его, а когда не хватает — берет побольше и переносит информацию из предыдущего фрагмента. У IBuf даже API нет, это просто структура с четырьмя указателями, буфером и методом, который умеет делать realloc.

Удобнее всего использовать по два таких буфера на каждое сетевое подключение. При чтении из одного сокета Tarantool вычитывает в один буфер сразу много запросов. Очевидно, после обработки запроса он уже не нужен, но, поскольку он живет в одном буфере с еще нужными запросами, удалить его нельзя. Поэтому по мере накопления запросов в одном буфере берётся следующий буфер — тогда рано или поздно все запросы из первого буфера будут выполнены и его, буфер, можно будет целиком освободить.

OBuf

void *obuf_alloc(struct obuf *buf, size_t size);
void *obuf_reserve(struct obuf *buf, size_t size); // Как обычно, опционально
struct obuf_svp obuf_create_svp(struct obuf *buf);
void obuf_rollback_to_svp(struct obuf *buf, struct obuf_svp *svp);

Второй из сетевых буферов, предназначенный для отправки ответа в сеть. Он не обязан быть непрерывным в памяти. Самое главное, что он умеет делать — сохранять позицию в своем буфере. Когда Tarantool отвечает запрос по сети, первые несколько байтов ответа — это размер ответа. А размер мы не знаем, пока не сформируем весь ответ. Поэтому мы запоминаем позицию в памяти, дописываем все данные, которые потребовались, после чего возвращаемся на ту самую позицию, меняем уже посчитанный размер и работаем дальше. Не rocket science, но для I/O в Tarantool — этого достаточно.

Mempool

void mempool_create(struct mempool *pool, struct slab_cache *cache, uint32_t objsize);
void *mempool_alloc(struct mempool *pool);
void mempool_free(struct mempool *pool, void *ptr);

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


Mempool берет из Slab cache большие slabы и размечает их под требуемый размер. Интересна стратегия переиспользования удаляемых блоков. В каждом slabе хранится свой список удаленных из него блоков (free list). При этом slabы одного Mempoolа делятся по степени заполненности на горячие и холодные. Для нового выделения используется free list по возможности горячего slabа с минимальным адресом. Такая стратегия позволяет хоть как-то бороться с общим бичом всех пулов памяти — фрагментацией.

Представим себе типичную случайную нагрузку на такой аллокатор: пользователь сначала выделил много блоков, а потом начинает циклично выделять новый / удалять случайный старый, причем удалять старые блоки приходится немного чаще, чем выделять новые. Очевидно Mempool не может освободить slab до тех пор, пока в нем содержится хотя бы один используемый блок. Поэтому при такой нагрузке появляется фрагментация — slabов много, в них будет много свободной памяти, но вот освободить их для общих нужд (например для других Mempool) этот Mempool не может. Если использовать один общий free list (что является стандартным подходом при реализации пула памяти) — то новые размещения в памяти будут попадать в случайные slabы, и даже после полной ротации (когда каждый блок из изначально выделенных был освобожден) фрагментация останется. Поэтому Mempool в Tarantool старается новые размещения делать в более плотных и каких-то определенных slabах, и при полной ротации блоков все прочие slabы будут точно пусты и соответственно возвращены обратно в Slab cache.

Small alloc

void *smalloc(struct small_alloc *alloc, size_t size);
void smfree(struct small_alloc *alloc, void *ptr, size_t size);

Это одна из вершин пищевых цепочек наших аллокаторов. Это аллокатор общего назначения, который наиболее эффективно работает с выделениями памяти небольшого размера. Используется для кортежей; в Tarantool кортеж является единицей информации, это данные, которые пользователь вставляет одной операцией insert/replace. Как правило, эти данные невелики, хотя вставлять мегабайтные данные в Tarantool никто не запрещает.

Small alloc — это коллекция Mempool’ов разного размера. Если нам надо выделить, скажем, 28 байт, то для этого выбирается наиболее подходящий Mempool, например который выделяет 32 байта, и такой блок блок будет результатом. При удалении блока его API требует указателя на блок и его изначальный размер — в примере выше — 28 байт. По этому размеру опять находится тот же самый наиболее подходящий Mempool, который и удаляет память.

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

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

Первая группа — это 32 Mempoolа, размер каждого слеующего на 8 больше, чем у предыдущего. Если размер первого — 8, это это размеры 8,16,24,32,...256. Размер самого первого задается специальной настройкой (она в конечном итоге присутствует в конфиге Tarantool).

Вторая группа устроена сложнее, но если описывать поверхностно — это размеры A×k, A×k×k, A×k×k×k, ...A×(k^256), где A — это последний (максимальный) размер в первой группе, а k — опция аллокатора (также выведена в конфиг Tarantool), обычно 1.05.

Таким образом Small alloc дает пользователю самому настроить аллокатор таким образом, чтобы можно было уменьшить потери память в его конкретном случае. По быстродействию же — такого рода аллокаторы считаются лучшими. Однако вместе с быстродействием он страдает типичной для такого рода аллокаторов болезнью — высокой фрагментацией при определенных нагрузках. Допустим, мы храним в Tarantool профиль пользователя, который занимает 100 байт. С течением времени размер профиля растёт, при обновлении становится 110 байт, потом 120 и так далее. При такой миграции размера количество блоков размера 100 становится всё меньше, и соответствующий Mempool постепенно фрагментируется. Поэтому такая нагрузка очень тяжела для Tarantool. Как правило, в такой ситуации мы просим пользователей время от времени перезагружать Tarantool, это плата за скорость и предсказуемость работы аллокатора.

Matras

void *matras_alloc(struct matras *m, matras_id_t *id);
void matras_dealloc(struct matras *m);
void *matras_get(const struct matras *m, matras_id_t id);
void *matras_touch(struct matras *m, matras_id_t id);
void matras_create_read_view(struct matras *m, struct matras_view *v);
void *matras_view_get(const struct matras *m, const struct matras_view *v, matras_id_t id);

Это акроним от Memory Address TRanslation Allocator. А букву s добавили для красоты.

Matras используется как аллокатор, но по сути он является динамическим массивом. Например, мы же можем использовать для размещения в памяти одного типа структур std::vector — добавляя в его конец новый элемент, мы фактически размещаем его в памяти и можем использовать в дальнейшем. Конечно это может привести к переразмещению в памяти внутреннего хранилища данных и испортятся указатели на предыдущие элементы. Но если мы вместо указателей на структуры будем хранить их номера (индексы) в этом массиве, то всё будет в порядке. Ну и удалять можно будет только последнюю структуру в массиве.

Matras очень похожим на std::vector образом выделяет блоки фиксированного размера (причем этот размер должен быть 2^n: 4, 8, 16, 32 и т.д), предполагая, что в дальнейшем эти блоки будут адресоваться не по указатель, а по индексу. И похожим на std::vector образом он может удалять только последний элемент. Однако в отличие от вектора Matras не непрерывен в памяти, он использует довольно крупные блоки одинакового размера, которые берет из специального Mempoolа.

Matras фактически выполняет виртуальную адресацию — пользователь использует виртуальные адреса блоков — компактные 32 битные числа. В любой момент эти виртуальные адреса можно транслировать в настоящие.

И тут мы подходим к самой важной особенности этого аллокатора. Он позволяет создавать copy-on-write read view (не представляю, как это по-русски сказать). Виртуальные адреса (то есть те 32 битные ID) для разных читателей могут разрешаться в разные физические адреса блоков.

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

Использование такого аллокатора позволяет делать удивительные вещи. Допустим мы в блоках храним узлы дерева поиска, с указателями (виртуальными! компактными 32 битными) и какие-то данные. Создавая read view Matrasа мы моментально получаем полностью замороженное текущее состояние дерева, его данные, структуру — всё. И можем передать это в другие потоки и там бесплатно использовать — выполнять поиск, итерироваться — всё это будет работать так, как будто дерево никто не модифицирует. При записи, конечно, появятся накладные расходы, но умеренно, и вообще кто-то же должен за это всё платить.


Допустим, мы создали Matras, который выделяет блоки маленького размера — int. И пусть он уже выделил несколько штук. А какой-то файбер решил создать read view. Он командует зафиксировать текущее состояние всех выделений памяти, которые хранятся в Matras. И перезаписи какого-нибудь элемента будет создана копия блока данных, который содержит этот элемент, а старый останется и будет доступен для читателя. То есть произойдет тот самый copy-on-write. Для писателя элементы для него уже будут лежать в другом месте, а для читателя — в старом.

Matras и Small alloc находятся в самом низу потребительской схемы Tarantool. С помощью Small alloc мы выделяем кортежи разного размера. А разные индексы хранят свои узлы или бакеты в Matras (мы говорим — лежат на матрасе), поэтому мы можем легко сделать read view в терминах базы данных, сделав read view у тех Matrasов, на которых лежат индексы.

Интерфейс

У аллокаторов Tarantool, по возможности, очень похожий интерфейс, за исключением Matras. У него как-то не очень получается. Остальные имеют очень похожую сигнатуру:

• create/destroy
• alloc/free
• reserve
• aligned_alloc
• alloc_object

FAQ

Можно ли использовать Small вне Tarantool?

По большей части, да. Но есть нюансы: если собирать с C++ — он не бросает исключения, а вызывает метод tnt_raise. Поэтому, если использовать в С++, то нужно этот метод где-то определить, буквально двумя строчками. А если использовать только С-часть, то вообще никаких проблем нет: при неудаче выделения памяти будет возвращаться ноль.

Как обеспечивается выравнивание памяти в случае с заголовками?

В Slab cache заголовки фиксированных размеров. Когда slab’ы используют следующий аллокатор, Region или Mempool, они к заголовку что-то дописывают, но тоже фиксированного размера. Выравнивание происходит двумя способами. Region, когда надо, выделяет с запасом — на несколько байт больше, и потом округляет адрес вверх. А Mempool все свои выделения памяти хранит не сразу после заголовка, а как бы так, чтобы последний блок упирался бы в конец slabа. А конец slabа гарантированно максимально выровнен. То есть между последним блоком и концом slabа нет свободного места, а между заголовком и первым выделенным блоком может оставаться маленький неиспользованный кусочек, который обеспечивает выравнивание.

Lua таким аллокатором пользуется?

Нет, Lua пользуется своим аллокатором. Там особая магия, там в 8 байт запихивают всё, что угодно: и число, и double, и указатель, и что-то другое, и потом по этим 8 байтам отличают, что в них лежит. Наверное, поэтому вся память, которую использует Lua должна быть относительно небольшого размера и в начале адресного пространства.

Какая разница в скорости работы Small и Malloc?

Если грубо — Small в несколько раз быстрее. Возможно, в некоторых случаях быстрее в десятки раз. Возможно, существуют паттерны, в которых он ведет себя не так хорошо, но вряд ли хуже malloc. Мы не уделяли много времени тестированию производительности.

Заключение

Библиотека аллокаторов Small используется в Tarantool давным-давно. Она обкатана и очень стабильна. Пользуйтесь на здоровье.

• Исходники small: github.com/tarantool/small
• Исходники Tarantool: github.com/tarantool/tarantool
• Как Tarantool работает с памятью: www.tarantool.io/ru/doc/latest/book/box/engines