?

Log in

ещё чуть-чуть о работе - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

ещё чуть-чуть о работе [июн. 2, 2003|12:34 am]
Anatoly Vorobey
В дополнение к этому.



В конце концов я переписал программу (она теперь есть в CVS, кстати) так, чтобы она использовала простую версию slab-аллокатора. Вот что это значит на практике. Модуль аллокации памяти выделят только блоки размером степенью двойки, от 27 (т.к. меньше не оказывается нужно в программе, вследствие того, что каждый хранящийся item вместе с контрольной структурой выходит длиннее) до 220. Для каждого класса размера (т.е. для каждого возможного размера от 128 байт до 1Mb) хранится простой связанный список свободных на данный момент блоков этого размера. Когда блок освобождается, он добавляется в этот список; когда требуется новый блок, берётся из этого списка. Вопрос, таким образом, только в том, как в этот список попадают новые свободные блоки. Когда нужен новый блок, а список пуст, вызывается malloc() и у него берётся сразу 1Mb памяти (slab), к-й делится на блоки нужного размера, и их адреса добавляются в список.

Из-за того, что у malloc()'а берётся всегда 1Mb, эта память всегда оказывается выделенной с помощью mmap() (malloc() всегда использует mmap() для запросов размером больше 128kb). Выделенные слэбы никогда не возвращаются в систему. Вследствие этого внешней фрагментации (т.е. фрагментации, возникающей вследствие образования маленьких "дырок" в адресном пространстве) нет в принципе. Зато довольно высока внутренняя фрагментация, т.е. потеря памяти за счёт того, что выделяется обычно больше памяти, чем на самом деле нужно (окгругляется до ближайшей степени двойки).

В данный момент внутренняя фрагментация составляет примерно 33%, т.е. треть памяти расходуется зря. Но нас это не слишком беспокоит. Во-первых, намного важнее, чем расчётливый расход памяти, было довести программу до состояния, когда она гарантированно бежит неограниченно долгое время без проблем — и сейчас она в таком состоянии (и последняя версия уже бежит несколько суток). Даже используемых нами сейчас примерно 5Gb кэша (разбитые на штук 6 процессов) и даже с такой внутренней фрагментацией хватает для того, чтобы очень убыстрить работу сайта. Hit rate при этом дошёл примерно до 80% (т.е. из той инфомации, что кэшируется, только 20% идёт из БД, а остальное из кэша). Во-вторых, slab-аллокатор можно сильно улучшить, чем я займусь через пару дней, наверное. Самое главное — заставить его работать с разными вариантами классов размеров, необяазтельно со степенями двойки. Это очень легко. Потом можно подобрать такие классы, которые именно в случае ЖЖ уменьшают фрагментацию. Мне ещё пока неясно, стоит ли возиться с динамическим анализом (т.е. чтобы аллокатор сам анализировал настоящие размеры запрашиваемых блоков, к-е ему передаются, и перекраивал свои класс размеров динамически) или просто обеспечить возможность чтения размеров из конфиг-файла или по протоколу.
СсылкаОтветить

Comments:
From: w_hole
2003-06-01 02:45 pm

respect
(Ответить) (Thread)
From: tom_ohawk
2003-06-01 03:09 pm

Garbage Collection

а на developer.novell.com нет ничего насчет
алгоритма их отдельной подзадачи "сбора мусора"
("garbage collection") - там "дефрагментатор"
памяти работает как оитдеьный процесс запускаемый
именно счетчиком доступных для объелинения
свободных фрагментов?
(Ответить) (Thread)
[User Picture]From: bugabuga
2003-06-01 05:10 pm
Глупый вопрос. Что бывает когда просят маленький кусок, а его нет? :) Берётся следующий свободный, отгрызается кусок и двигается в список меньшего размера, превращаясь в кучку?
А при возвращении смотрится рядом, и, если там есть кусок такого-же размера, то объединяется, и складывается в список n+1 ? (последнее должно быть не очень сложно, но как такое синхронизировать по-человечески, если оно живёт в несколько потоков)
(Ответить) (Thread)
[User Picture]From: avva
2003-06-01 05:24 pm

Re:

Нет. Я думал так сделать, но потом решил в первой версии сделать всё до глупого просто, а дальше усложнять. А может, и не надо будет усложнять, посмотрим.

Когда просят маленький кусочек, скажем, килобайт, а его нет, берут у системы целый мегабайт, режут его на маленькие кусочки этого размера (1024 кусочка в данном случае) и добавляют в свободный список. split/join -- т.е. разделения кусков большого размера на куски меньшего и наоборот слияния - нет. Просто каждый раз берём ещё мегабайт у системы и режем на куски того размера, которого у нас в данный момент не хватает. Это не страшно, т.к. даже если в худшем случае все остальные куски, кроме заказанного, не понадобятся, то мы терям максимум по одному мегабайту на каждый класс размеров, т.е. ерунду (на практике они понадобятся, конечно).

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

После того, как мы дошли до данного предела памяти, каждый класс размеров остался с теми слэбами (кусками в 1Mb), к-е были ему выделены до сих пор, и уже новых не получит. Но большой размер кэша обеспечивает относительно равномерной распределение слэбов по классам размеров во время заполнения кэша до данного предела.
(Ответить) (Parent) (Thread)
[User Picture]From: bugabuga
2003-06-01 10:41 pm
Понятно. Просто факт округления размера сильно помог бы в случае сборки/разборки больших и маленьких кусочков :) А в следующей версии можно сделать флаг приоритета большие/мелкие куски -- если жалко терять мег из-за одного-двух редко используемых классов.

off-topic: Вообще здорово :) Я на подобные темы не размышлял с университетских времён :) надо будет почитать книжек...
(Ответить) (Parent) (Thread)
[User Picture]From: bish0nen
2003-06-03 02:15 am
off-topic: Вообще здорово :) Я на подобные темы не размышлял с университетских времён :) надо будет почитать книжек...

Кстати, slab allocator в мирных целях впервые массово был применён в Solaris 2.4, в результате чего скорость выделения блоков памяти ядерного memory allocator'а по сравнению с ранее использовавшимся из SVR4, buddy allocator'ом, выросла почти в три раза, а фрагментация - упала в более чем три раза. Ну, и размеры slabs к тому же были подогнаны под размеры cache lines процессора, плюс разбивка полузаготовленных объектов на пулы slab'ов - в сумме дало очень нехилое ускорение Солярису. Потом slab allocator утащили в Линуксовое ядро, году эдак в 1997 или 98.
(Ответить) (Parent) (Thread)
From: 9000
2003-06-02 02:55 am
Краса. ЖЖ реально ускорился :-)

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

Процесс перераспределения можно было бы запускать тогда, когда интенсивность отказов по одному из классов достигала бы заданного значения. Наличие статистики по свободному месту позволит сразу отказаться от [дорогостоящего] перераспределения, если свободного места нет ни у кого (пиковые нагрузки, etc).
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2003-06-02 05:28 am

Re:

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

Если немного точнее быть, то в протоколе общение с кэшем есть команда delete, к-я удаляет ненужный блок, но она использыется на практике в ЖЖ довольно редко, так что свободные блоки, к-е она создаёт, быстро заполняются.

Вследствие того, что сам код кэша настолько "жаден", судить о "несправедливом" использовании одного класса размеров по отношению к другому приходится судить по другим признакам: общему кол-ву слэбов, выделенных на данный класс в процессе заполнения кэша, а также возрастом самого старого элемента в данном классе, в секундах (если в каком-то классе все элементы очень молоды относительно других классов, это значит, что кэш на этом классе менее эффективен и ему надо давать больше памяти). Код для проведения такого анализа и распределения памяти в следующих запусках согласно его результатам ещё предстоит написать ;)
(Ответить) (Parent) (Thread)
[User Picture]From: igorbor
2003-06-02 03:37 am
Может быть, имеет смысл при исчерпании памяти убивать не "самый старый" обьект, а "самый ненужный", предполагая, что для каждого обьекта есть некая мера его популярности - скажем, количество запросов, умноженное на размер? Конечно, поиск таких кусков будет более трудоемким, чем просто поиск самых старых, поэтому, наверное, стоит для начала собрать статистику какую-то.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2003-06-02 04:55 am
"Самый старый" - это я упростил, на самом деле не "старше всех время внесения", а "старше всех время использования". Объекты каждого класса размеров пролинкованы между собой в списке LRU: каждый раз, когда какой-нибудь клиент просит любой объект, этот объект передвигается в вершину своего списка. Когда нужно освободить место, удаляется объект из хвоста списка, таким образом это объект, который больше всего времени никто не просил (из данного класса размеров). Можно было бы учитывать и количество запросов, но не уверен, что действительно нужно.
(Ответить) (Parent) (Thread)
[User Picture]From: igorbor
2003-06-02 06:32 am

Re:

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

Но вообще, конечно, такого рода оптимизации нужно делать только после того, как статистика покажет, что это необходимо. 60% hit rate - это очень хорошо, так что, может быть, это и ненужно.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2003-06-01 05:13 pm
Пожалуйста-пожалуйста. ))

А теперь самое время Liedtke o кэш-сервере поискать, - он как раз вопросами быстродействия заботился.

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

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

И, - не зная архитектуры Вашей системы, сказать наверняка нельзя, - но, возможно, стоит обратить внимание на детали, связанные с кэшом памяти.
(Ответить) (Thread)
[User Picture]From: avva
2003-06-01 05:25 pm

Спасибо, дорогой аноним ;)
(Ответить) (Parent) (Thread)
From: (Anonymous)
2003-06-01 06:20 pm
Да, право, мелочи...

Жду отчет о Лидтке.

))
(Ответить) (Parent) (Thread)
[User Picture]From: arbat
2003-06-01 08:53 pm

Простой настраиваемый аллокатор есть в
"Modern C++ Design" by Andrei Alexandrescu
Addison-Wesley, February 2001, 323 pages, ISBN 0201704315

Собственно, там полно всяких интересностей.

А в чем, собственно, проблемма? Надо ли ее решать с нуля, если она, скорее всего многократно уже решалась? :-)

(Ответить) (Thread)
[User Picture]From: malaya_zemlya
2003-06-01 09:23 pm
Насколько я помню, Александресковский аллокатор заточен под "малые объекты", меньше, скажем, 100 байтов.
Тем не менее, если интересно, исходники библиотеки Loki, описываемой в данной книжке находятся на http://freshmeat.net/projects/lokilibrary/?topic_id=809
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2003-06-02 05:30 am

Re:

Проблема в том, что нужен был исключительно эффективный (поддерживающий 500+ одновременных соединений без излишней нагрузки на CPU) дистрибутивный memory cache. Существующего такого не нашли, поэтому я написал с нуля ;)
(Ответить) (Parent) (Thread)
[User Picture]From: yms
2003-06-02 10:52 pm
а также
ed2k://|file|Addison.Wesley.Modern.C++.Design.Generic.Programming.and.Design.Patterns.Applied.rar|823329|EF70F9DFB84A1585DDB0B33BF5E36E56|/
;)
(Ответить) (Parent) (Thread)
[User Picture]From: 109
2003-06-01 10:48 pm
забавно, что я почти это же хотел предложить позавчера (или когда мы там с вами ругались). но не в точности то же самое. я хотел предложить:
1. построить распределение требуемых кусков по размерам.
2. выделять блоки фиксированного размера, все одинаковые.
3. размер блока вычислять из распределения и допустимого оверхеда (то есть, например, мы допускаем 20% memory waste -> наш блок должен быть 4К).
4. если объект больше, чем размер нашего блока, то просто давать ему несколько блоков.

таким образом снялся бы весь геморрой с дефрагментацией памяти. да-да, я вижу, что вы уже эту проблему по-своему решили.
(Ответить) (Thread)
[User Picture]From: pendelschwanz
2003-06-02 03:52 am
Оно в какой среде? Мокрософта или Уникса?
Хочу сказать (хотя я не люблю Махрософт) что там механизм malloc/mfree вылизан до мелочей и в их "Визжуал С" new и delete железные - правда на это им потребовалось немало лет борьбы, если не десять.
Я поручил как-то раз группе воинов с копьями долбить пробовать на прочность new и delete - по миллионам раз в случайном порядке разными кусками - и удивительно, держит, все удаляет, память остается и не засирается.
(Ответить) (Thread)
[User Picture]From: avva
2003-06-02 05:23 am

Re:

Нет, это под Юниксом (Debian Linux).
(Ответить) (Parent) (Thread)
From: gogabr
2003-06-02 10:20 pm

Бежать

По-русски я, наверное, ни от кого, кроме Вас, не слышал "программа бежит". Я бы сказал "пашет".
Видимо, разные поддиалекты.
(Ответить) (Thread)
[User Picture]From: erez
2003-06-04 09:22 am

Re: Бежать

бежит - это не перевод "runs". пашет - runs, а бежит (вариант: бегает) - значит, хорошо пашет или способна работать при каких-то условиях. "летает" - это как "бежит", но еще быстрее :)

но можно и вместо runs употреблять, наверно.
это все, конечно, IMHO.
(Ответить) (Parent) (Thread)