ещё чуть-чуть о работе
Jun. 2nd, 2003 12:34 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaВ дополнение к этому.
В конце концов я переписал программу (она теперь есть в CVS, кстати) так, чтобы она использовала простую версию slab-аллокатора. Вот что это значит на практике. Модуль аллокации памяти выделят только блоки размером степенью двойки, от 27 (т.к. меньше не оказывается нужно в программе, вследствие того, что каждый хранящийся item вместе с контрольной структурой выходит длиннее) до 220. Для каждого класса размера (т.е. для каждого возможного размера от 128 байт до 1Mb) хранится простой связанный список свободных на данный момент блоков этого размера. Когда блок освобождается, он добавляется в этот список; когда требуется новый блок, берётся из этого списка. Вопрос, таким образом, только в том, как в этот список попадают новые свободные блоки. Когда нужен новый блок, а список пуст, вызывается malloc() и у него берётся сразу 1Mb памяти (slab), к-й делится на блоки нужного размера, и их адреса добавляются в список.
Из-за того, что у malloc()'а берётся всегда 1Mb, эта память всегда оказывается выделенной с помощью mmap() (malloc() всегда использует mmap() для запросов размером больше 128kb). Выделенные слэбы никогда не возвращаются в систему. Вследствие этого внешней фрагментации (т.е. фрагментации, возникающей вследствие образования маленьких "дырок" в адресном пространстве) нет в принципе. Зато довольно высока внутренняя фрагментация, т.е. потеря памяти за счёт того, что выделяется обычно больше памяти, чем на самом деле нужно (окгругляется до ближайшей степени двойки).
В данный момент внутренняя фрагментация составляет примерно 33%, т.е. треть памяти расходуется зря. Но нас это не слишком беспокоит. Во-первых, намного важнее, чем расчётливый расход памяти, было довести программу до состояния, когда она гарантированно бежит неограниченно долгое время без проблем — и сейчас она в таком состоянии (и последняя версия уже бежит несколько суток). Даже используемых нами сейчас примерно 5Gb кэша (разбитые на штук 6 процессов) и даже с такой внутренней фрагментацией хватает для того, чтобы очень убыстрить работу сайта. Hit rate при этом дошёл примерно до 80% (т.е. из той инфомации, что кэшируется, только 20% идёт из БД, а остальное из кэша). Во-вторых, slab-аллокатор можно сильно улучшить, чем я займусь через пару дней, наверное. Самое главное — заставить его работать с разными вариантами классов размеров, необяазтельно со степенями двойки. Это очень легко. Потом можно подобрать такие классы, которые именно в случае ЖЖ уменьшают фрагментацию. Мне ещё пока неясно, стоит ли возиться с динамическим анализом (т.е. чтобы аллокатор сам анализировал настоящие размеры запрашиваемых блоков, к-е ему передаются, и перекраивал свои класс размеров динамически) или просто обеспечить возможность чтения размеров из конфиг-файла или по протоколу.
В конце концов я переписал программу (она теперь есть в CVS, кстати) так, чтобы она использовала простую версию slab-аллокатора. Вот что это значит на практике. Модуль аллокации памяти выделят только блоки размером степенью двойки, от 27 (т.к. меньше не оказывается нужно в программе, вследствие того, что каждый хранящийся item вместе с контрольной структурой выходит длиннее) до 220. Для каждого класса размера (т.е. для каждого возможного размера от 128 байт до 1Mb) хранится простой связанный список свободных на данный момент блоков этого размера. Когда блок освобождается, он добавляется в этот список; когда требуется новый блок, берётся из этого списка. Вопрос, таким образом, только в том, как в этот список попадают новые свободные блоки. Когда нужен новый блок, а список пуст, вызывается malloc() и у него берётся сразу 1Mb памяти (slab), к-й делится на блоки нужного размера, и их адреса добавляются в список.
Из-за того, что у malloc()'а берётся всегда 1Mb, эта память всегда оказывается выделенной с помощью mmap() (malloc() всегда использует mmap() для запросов размером больше 128kb). Выделенные слэбы никогда не возвращаются в систему. Вследствие этого внешней фрагментации (т.е. фрагментации, возникающей вследствие образования маленьких "дырок" в адресном пространстве) нет в принципе. Зато довольно высока внутренняя фрагментация, т.е. потеря памяти за счёт того, что выделяется обычно больше памяти, чем на самом деле нужно (окгругляется до ближайшей степени двойки).
В данный момент внутренняя фрагментация составляет примерно 33%, т.е. треть памяти расходуется зря. Но нас это не слишком беспокоит. Во-первых, намного важнее, чем расчётливый расход памяти, было довести программу до состояния, когда она гарантированно бежит неограниченно долгое время без проблем — и сейчас она в таком состоянии (и последняя версия уже бежит несколько суток). Даже используемых нами сейчас примерно 5Gb кэша (разбитые на штук 6 процессов) и даже с такой внутренней фрагментацией хватает для того, чтобы очень убыстрить работу сайта. Hit rate при этом дошёл примерно до 80% (т.е. из той инфомации, что кэшируется, только 20% идёт из БД, а остальное из кэша). Во-вторых, slab-аллокатор можно сильно улучшить, чем я займусь через пару дней, наверное. Самое главное — заставить его работать с разными вариантами классов размеров, необяазтельно со степенями двойки. Это очень легко. Потом можно подобрать такие классы, которые именно в случае ЖЖ уменьшают фрагментацию. Мне ещё пока неясно, стоит ли возиться с динамическим анализом (т.е. чтобы аллокатор сам анализировал настоящие размеры запрашиваемых блоков, к-е ему передаются, и перекраивал свои класс размеров динамически) или просто обеспечить возможность чтения размеров из конфиг-файла или по протоколу.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Garbage Collection
Date: 2003-06-01 03:09 pm (UTC)алгоритма их отдельной подзадачи "сбора мусора"
("garbage collection") - там "дефрагментатор"
памяти работает как оитдеьный процесс запускаемый
именно счетчиком доступных для объелинения
свободных фрагментов?
no subject
Date: 2003-06-01 05:10 pm (UTC)А при возвращении смотрится рядом, и, если там есть кусок такого-же размера, то объединяется, и складывается в список n+1 ? (последнее должно быть не очень сложно, но как такое синхронизировать по-человечески, если оно живёт в несколько потоков)
Re:
Date: 2003-06-01 05:24 pm (UTC)Когда просят маленький кусочек, скажем, килобайт, а его нет, берут у системы целый мегабайт, режут его на маленькие кусочки этого размера (1024 кусочка в данном случае) и добавляют в свободный список. split/join -- т.е. разделения кусков большого размера на куски меньшего и наоборот слияния - нет. Просто каждый раз берём ещё мегабайт у системы и режем на куски того размера, которого у нас в данный момент не хватает. Это не страшно, т.к. даже если в худшем случае все остальные куски, кроме заказанного, не понадобятся, то мы терям максимум по одному мегабайту на каждый класс размеров, т.е. ерунду (на практике они понадобятся, конечно).
В какой-то момент доходим до предела памяти, которую разрешили брать у системы (при запуске задаётся предел в мегабайтах) и после этого, если просят кусок, а свободных такого размера нету, то просто говорим "нету". Но тогда та часть кода, которая собственно хранит объекты в кэше, и запросила память под новый объект, после получения отказа берёт самый "старый" объект, занимающий блок такого же размера, и освобождает его, после чего повторный вызов функции аллокации вернёт этот самый кусок.
После того, как мы дошли до данного предела памяти, каждый класс размеров остался с теми слэбами (кусками в 1Mb), к-е были ему выделены до сих пор, и уже новых не получит. Но большой размер кэша обеспечивает относительно равномерной распределение слэбов по классам размеров во время заполнения кэша до данного предела.
no subject
Date: 2003-06-01 10:41 pm (UTC)off-topic: Вообще здорово :) Я на подобные темы не размышлял с университетских времён :) надо будет почитать книжек...
no subject
Date: 2003-06-03 02:15 am (UTC)Кстати, slab allocator в мирных целях впервые массово был применён в Solaris 2.4, в результате чего скорость выделения блоков памяти ядерного memory allocator'а по сравнению с ранее использовавшимся из SVR4, buddy allocator'ом, выросла почти в три раза, а фрагментация - упала в более чем три раза. Ну, и размеры slabs к тому же были подогнаны под размеры cache lines процессора, плюс разбивка полузаготовленных объектов на пулы slab'ов - в сумме дало очень нехилое ускорение Солярису. Потом slab allocator утащили в Линуксовое ядро, году эдак в 1997 или 98.
no subject
Date: 2003-06-02 02:55 am (UTC)Может, было бы полезно собирать статистику по отношению количества использованных/выделенных блоков у каждого класса размеров, и по числу отказов. В случае, если в каком-то из классов большой избыток свободных блоков, а в другом из классов -- недостаток, можно было бы попробовать объединять (или резать) лишние свободные блоки "пустующего" класса и выдавать их "нуждающемуся".
Процесс перераспределения можно было бы запускать тогда, когда интенсивность отказов по одному из классов достигала бы заданного значения. Наличие статистики по свободному месту позволит сразу отказаться от [дорогостоящего] перераспределения, если свободного места нет ни у кого (пиковые нагрузки, etc).
Re:
Date: 2003-06-02 05:28 am (UTC)Если немного точнее быть, то в протоколе общение с кэшем есть команда delete, к-я удаляет ненужный блок, но она использыется на практике в ЖЖ довольно редко, так что свободные блоки, к-е она создаёт, быстро заполняются.
Вследствие того, что сам код кэша настолько "жаден", судить о "несправедливом" использовании одного класса размеров по отношению к другому приходится судить по другим признакам: общему кол-ву слэбов, выделенных на данный класс в процессе заполнения кэша, а также возрастом самого старого элемента в данном классе, в секундах (если в каком-то классе все элементы очень молоды относительно других классов, это значит, что кэш на этом классе менее эффективен и ему надо давать больше памяти). Код для проведения такого анализа и распределения памяти в следующих запусках согласно его результатам ещё предстоит написать ;)
no subject
Date: 2003-06-02 03:37 am (UTC)no subject
Date: 2003-06-02 04:55 am (UTC)Re:
Date: 2003-06-02 06:32 am (UTC)Но вообще, конечно, такого рода оптимизации нужно делать только после того, как статистика покажет, что это необходимо. 60% hit rate - это очень хорошо, так что, может быть, это и ненужно.
no subject
Date: 2003-06-01 05:13 pm (UTC)А теперь самое время Liedtke o кэш-сервере поискать, - он как раз вопросами быстродействия заботился.
И еще -- идея slab-allocator в том, все же, что он позволяет работать не с памятью, а с "полуфабрикатными" обьектами, экономя на инициализации и очистке обьектов.
Возиться с неестественным интеллектом, вероятно, не стоит: у Вас стабильные характеристики нагрузки. Стоит просто собрать статистику по трассировкам, и на ее основе посчитать неплохую раскладку размеров.
И, - не зная архитектуры Вашей системы, сказать наверняка нельзя, - но, возможно, стоит обратить внимание на детали, связанные с кэшом памяти.
no subject
no subject
Date: 2003-06-01 06:20 pm (UTC)Жду отчет о Лидтке.
))
no subject
Date: 2003-06-01 08:53 pm (UTC)Простой настраиваемый аллокатор есть в
"Modern C++ Design" by Andrei Alexandrescu (http://www.bookpool.com/.x/n66pfne150/ss/1?qs=alexandrescu)
Addison-Wesley, February 2001, 323 pages, ISBN 0201704315
Собственно, там полно всяких интересностей.
А в чем, собственно, проблемма? Надо ли ее решать с нуля, если она, скорее всего многократно уже решалась? :-)
no subject
Date: 2003-06-01 09:23 pm (UTC)Тем не менее, если интересно, исходники библиотеки Loki, описываемой в данной книжке находятся на http://freshmeat.net/projects/lokilibrary/?topic_id=809
Re:
Date: 2003-06-02 05:30 am (UTC)no subject
Date: 2003-06-02 10:52 pm (UTC)ed2k://|file|Addison.Wesley.Modern.C++.Design.Generic.Programming.and.Design.Patterns.Applied.rar|823329|EF70F9DFB84A1585DDB0B33BF5E36E56|/
;)
no subject
Date: 2003-06-01 10:48 pm (UTC)1. построить распределение требуемых кусков по размерам.
2. выделять блоки фиксированного размера, все одинаковые.
3. размер блока вычислять из распределения и допустимого оверхеда (то есть, например, мы допускаем 20% memory waste -> наш блок должен быть 4К).
4. если объект больше, чем размер нашего блока, то просто давать ему несколько блоков.
таким образом снялся бы весь геморрой с дефрагментацией памяти. да-да, я вижу, что вы уже эту проблему по-своему решили.
no subject
Date: 2003-06-02 03:52 am (UTC)Хочу сказать (хотя я не люблю Махрософт) что там механизм malloc/mfree вылизан до мелочей и в их "Визжуал С" new и delete железные - правда на это им потребовалось немало лет борьбы, если не десять.
Я поручил как-то раз группе воинов с копьями долбить пробовать на прочность new и delete - по миллионам раз в случайном порядке разными кусками - и удивительно, держит, все удаляет, память остается и не засирается.
Re:
Date: 2003-06-02 05:23 am (UTC)Бежать
Date: 2003-06-02 10:20 pm (UTC)Видимо, разные поддиалекты.
Re: Бежать
Date: 2003-06-04 09:22 am (UTC)но можно и вместо runs употреблять, наверно.
это все, конечно, IMHO.