дизайн memory management system

[Big Cheese]

Есть система, которая упрощенно говоря обрабатывает сетевые пакеты и генерирует на их основании события. Все на С/С++ Linux/Windows. Изначально выделение памяти для критических объектов было реализовано через boost'овский pool allocator (если я правильно помню), но потом от этой модели отказались так как allocator не умел "отдавать" память назад. Из-за этого memory usage процесса всегда было на уровне пиковой нагрузки, что не есть хорошо так как нагрузка скачет в разы, а на машине кроме нашего процесса могут бежать другие задачи.

Посему было принять решение все перевести на обычный malloc/free | new/delete, что в какой-то мере решило проблему нерационального расхода памяти, но только на первые пару дней работы - потом видимо начинает сказываться heap fragmentation и процесс начинает подтормаживать и жрать память. Так как задача системы работать беспрерывно от ребута до ребута, то вариант перепнуть процесс каждые Х дней не подходит, и видимо придется искать или писать самим более продвинутый memory manager. Минимальные требования - чтобы умел быстро выделять и отдавать куски памяти разных размеров без деградации производительности, в идеале - чтобы в перспективе можно было прикрутить cache management

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

[Сергей Армянский]

А были конкретные проблемы с memory pool ом? допишите memory release тогда..А вообще правильным пацанам память не нужна: http://lukego.github.io/blog/2013/01/04 ... etworking/, или http://www.linuxjournal.com/article/6345

[Big Cheese]

А были конкретные проблемы с memory pool ом? допишите memory release тогда..

Как вариант да, рассматриваю. Смущает то, что для pool allocator-а, аллокирующего большие блоки памяти, которые он потом сам дробит на allocation unit size chunks, написать release logic представляется нетривиальной задачей. А делать pool который malloc-ает каждый allocation size unit отдельно - особого смысла не вижу, так как непонятно, чем он будет отличаться от обычного malloc/free..

А вообще правильным пацанам память не нужна

Спасибо за ссылки, только нам без памяти не обойтись т.к. вся логика завязана на очень stateful analysis.

[Andriy777]

Может, тогда что-нибудь типа Garbage Collector? Он, правда, будет задержки создавать когда самая длинная сборка будет. Можно поэкспериментировать со многими областями и многими коллекторами. Один на thread, например. Все зависит как приложение работает.

Я на C++ многие подсистемы кодирую с использованием простейших GC-типа аллокаторов для внутренних классов. Иногда удобно, аж жуть.

[Medium-rare]

Примитив. Что-то смутно вспоминается, как большой memory-mapped файл с индивидуальными рекордами фиксированного размера адресованные одним битом в индексе в RAM. 1 бит означает кратный размеру рекорда занятый-незанятый рекорд. Но такой примитив пуленепробиваем и быстр, и растущий по мере нужды, хотя пытаемся забивать нули в индексе до увеличения файла.

[roadman]

Попробуйте вот этот: http://linux.die.net/man/3/jemalloc

[Prosche]

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

[Alexandr]

у меня в HFT сервере сделано примерно так (по сути как в ядре линукса)
buddy allocator - для постраничного оперирования памятью, он умеет брать память как из системы, там и отдавать в систему, используется стандартный алгоритм с low_watermark, high_watermark, batch
так как очень часто buddy_allocator просят выделить и освободить ровно 1 страницу, то он имеет per_cpu списки кешированных страниц (со все тем же per_cpu_low_watermark, per_cpu_highwatermark, per_cpu_batch). Поэтому выделение 1 страницы памяти - это просто взятие из списка без каких либо локов.

над buddy_allocator находится slab_allocator (точно также как и в ядре линукса), он использует buddy_allocator для запроса страниц, далее страницу разбивает на объекты и уже эти объекты может отдавать на запросы. Это в общем-то стандартная технология для аллокатора объектов одинакового размера. Естественно он тоже имеет свои per_cpu списки для быстрой выдачи объектов без локов. Естественно в системе есть несколько инстансов slab_allocator для разных объектов.

над slab_allocator находится slab_creator, который использует slab_allocator для выделения памяти под объект, а также умеет дергать конструкторы и деструкторы при выделении, освобождении.

Также имеется slab_cache, который умеет выдавать объекты "любого" размеры (на уровне компилятора задана верхняя граница), работает наподобии виндового low fragmentation heap, где все размеры на самом деле являются размерами с гранулярностью 8, и соответственно имеем n (зависит от верхней границы) указателей на списки объектов нужного размера.

[IvanF]

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

У меня тоже есть система которая обрабатывает пакеты VOIP звонков. Я сделал так. Память под пакеты выделяется блоками нескольких стандартных размеров (128, 512, 1024, 1536). Это нейтрализует проблему фрагментации памяти. Далее есть пул таких свободных блоков в котором они хранятся до 10 минут после чего они освобождаются. Это решает проблему освобождения неиспользованной памяти.

[Big Cheese]

Может, тогда что-нибудь типа Garbage Collector? Он, правда, будет задержки создавать когда самая длинная сборка будет. Можно поэкспериментировать со многими областями и многими коллекторами. Один на thread, например. Все зависит как приложение работает.

Я на C++ многие подсистемы кодирую с использованием простейших GC-типа аллокаторов для внутренних классов. Иногда удобно, аж жуть.

Задержки очень нежелательны, тк надо успевать обрабатывать данные, которые валятся с довольно большой скоростью. Но за идею спасибо!

[Big Cheese]

Попробуйте вот этот: http://linux.die.net/man/3/jemalloc

Спасибо, буду смотреть

[Big Cheese]

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

В общем и целом согласен, но в данном случае каких-то утечек или багов пока не находится.

[Big Cheese]

у меня в HFT сервере сделано примерно так (по сути как в ядре линукса)
/.../

Вы сами все писали или что-то готовое брали? А как slab_allocator борется с фрагментацией? Ну т.е.:

Допустим, в одну страницу влазит 100 объектов. Запросили 100000 объектов, slab_allocator запросил и заполнил 1000 страниц. Потом 99% из запрошенных объектов прибили в произвольном порядке. В худшем случае получается, что все страницы до сих пор содержат по 1 объекту и отдать их обратно buddy_allocator'y никак нельзя. Понятно, что это worst case, но все равно - как бороться с фрагментацией в такой системе? Или я что-то недопонимаю? Насколько большой overhead от поддержания всех списков/учета занятых/свободных блоков и тп?

[IvanF]

Допустим, в одну страницу влазит 100 объектов. Запросили 100000 объектов, slab_allocator запросил и заполнил 1000 страниц. Потом 99% из запрошенных объектов прибили в произвольном порядке. В худшем случае получается, что все страницы до сих пор содержат по 1 объекту и отдать их обратно buddy_allocator'y никак нельзя. Понятно, что это worst case, но все равно - как бороться с фрагментацией в такой системе? Или я что-то недопонимаю? Насколько большой overhead от поддержания всех списков/учета занятых/свободных блоков и тп?

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

[Big Cheese]

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

У меня тоже есть система которая обрабатывает пакеты VOIP звонков. Я сделал так. Память под пакеты выделяется блоками нескольких стандартных размеров (128, 512, 1024, 1536). Это нейтрализует проблему фрагментации памяти. Далее есть пул таких свободных блоков в котором они хранятся до 10 минут после чего они освобождаются. Это решает проблему освобождения неиспользованной памяти.

У меня размеры в основном от 56 байт до нескольких десятков килобайт, причем мелких объектов одновременно "живет" где-то несколько миллионов, так что я не уверен, что naive freelist-based bucketed pool allocator сильно поможет с фрагментацией. Хотя попробовать можно, тем более что реализация такого аллокатора достаточно тривиальна. А какие объемы Ваша система обрабатывает, если не секрет?

[Alexandr]

Вы сами все писали или что-то готовое брали? А как slab_allocator борется с фрагментацией? Ну т.е.:

сам все написал, так как нужна была максимальна низкая latency, пришлось даже красно-черное дерево самому написать, так как boost::intrusive нифига не впечатлил скоростью. Если нужно быстро написать, то в инете есть готовые реализации buddy system
У slab_allocator физически не может быть фрагментации, так как он предназначен для выделения/освобождения объектов одного и того же размера. Например, в ядре линукса как и у меня есть разные структуры, которые нужно уметь быстро выделять и освобождать, соответственно на каждую такую структуру есть свой slab_allocator (он как шаблон у меня сделан, что-то типа slab_allocator<my_type, .....>)

Допустим, в одну страницу влазит 100 объектов. Запросили 100000 объектов, slab_allocator запросил и заполнил 1000 страниц. Потом 99% из запрошенных объектов прибили в произвольном порядке. В худшем случае получается, что все страницы до сих пор содержат по 1 объекту и отдать их обратно buddy_allocator'y никак нельзя. Понятно, что это worst case, но все равно - как бороться с фрагментацией в такой системе? Или я что-то недопонимаю? Насколько большой overhead от поддержания всех списков/учета занятых/свободных блоков и тп?

я с этим никак не борюсь, так как у меня такой проблемы вообще нет. У меня либо - все время выделяем новую память (для таких рыночных данных как таблица заявок и таблица сделок), либо паттерн - выделил и удалил. В последнем случае оно вообще болтается между per_cpu_low_watermark и per_cpu_high_watermark (так специально настроено) и поэтому любое выделение и освобождение - это просто взятие из списка без локов; также понятно, что тут никакой фрагментации вообще не возникает.

Если бы описанная вами проблема встала я бы действовал следующим образом:
1) если можно при выделении памяти объекты выделять таким образом, чтобы проблема исчезла - так бы и действовал. Например: я выделяю 1000000 объектов и потом все, кроме каждого 100 освобождал, и, предположим это приводит к тому, что остается по 1 объекту на странице. Я бы выделил сначала те объекты, которые останутся, а потом все остальное, понятно, что при освобождении я смогу отдать их системе, так как никакой фрагментации там не будет и мой buddy_allocator их отдаст

2) если вариант 1 не получается, т.е. заранее не известно, что останется. Я бы пошел по следующему пути: после массивного удаления как в вашем примере, тупо бы паковал оставшиеся объекты. Это можно делать и online - по ходу работы приложения, и offline - big lock, pack, big unlock и опять проблема решается.

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

Кстати, еще можно, например, в slab_allocator можно добавить, чтобы он следил за тем, сколько объектов выделено на странице и знать общее количество объектов, при плохом соотношении также можно перепаковать объекты и память отдать системе.

[Alexandr]

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

У меня тоже есть система которая обрабатывает пакеты VOIP звонков. Я сделал так. Память под пакеты выделяется блоками нескольких стандартных размеров (128, 512, 1024, 1536). Это нейтрализует проблему фрагментации памяти. Далее есть пул таких свободных блоков в котором они хранятся до 10 минут после чего они освобождаются. Это решает проблему освобождения неиспользованной памяти.

У меня размеры в основном от 56 байт до нескольких десятков килобайт, причем мелких объектов одновременно "живет" где-то несколько миллионов, так что я не уверен, что naive freelist-based bucketed pool allocator сильно поможет с фрагментацией. Хотя попробовать можно, тем более что реализация такого аллокатора достаточно тривиальна. А какие объемы Ваша система обрабатывает, если не секрет?

Если у вас есть четкая грануляция между мелкими и крупными объектами, например, мелкие: 56,74,88,192,
крупные: 10455, 12677, 13899 и так далее, то вам нужно разделить выделение мелких и крупных объектов в принципе.
и для мелких объектов выделять блоки, которые кратны крупным объектам + за счет чуть большего расхода памяти, сократить, если это возможно, число возможных размеров, которые выделяются.

Но первое, что точно нужно: это разнести крупные и мелкие объекты по разным углам

[Boriskin]

У меня размеры в основном от 56 байт до нескольких десятков килобайт, причем мелких объектов одновременно "живет" где-то несколько миллионов, так что я не уверен, что naive freelist-based bucketed pool allocator сильно поможет с фрагментацией.

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

[Palych]

Интересно, кто-нибудь пробовал Region-based memory management так чтобы разделять объекты не по размеру, а по функциональности: request, session, aapplication?
По идее должно быть эффективно для серверных приложений...

[Sheriff]

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

http://blog.reverberate.org/2009/02/one ... m-all.html

http://google-perftools.googlecode.com/ ... alloc.html
https://code.google.com/p/gperftools/wi ... manceTools

https://www.facebook.com/notes/facebook ... 0222803919

http://en.wikipedia.org/wiki/Region-bas ... management

[Alexandr]

Интересно, кто-нибудь пробовал Region-based memory management так чтобы разделять объекты не по размеру, а по функциональности: request, session, aapplication?
По идее должно быть эффективно для серверных приложений...

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

[Alexandr]

У меня размеры в основном от 56 байт до нескольких десятков килобайт, причем мелких объектов одновременно "живет" где-то несколько миллионов, так что я не уверен, что naive freelist-based bucketed pool allocator сильно поможет с фрагментацией.

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

+ как в buddy_allocator уметь сливать маленькие блоки в бОльшие, где это возможно

[Big Cheese]

Спасибо большое всем, буду копать в наметившихся направлениях.