немного о работе
May. 26th, 2003 09:20 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaПоследние два дня писал программу на C, впервые года за три наверное.
Программа — memory cache daemon. Принимает TCP-подключения на определённом порту, от клиентов принимает пары ключ/значение и запоминает, а когда начинает заканчиваться память, выбрасывает наименее используемые (по принципу LRU queue. Все элементы прошиты в списке. Входят они в него с головы. Всякий раз, когда какой-то элемент запрашивается клиентом, он передвигается опять в голову. А когда надо освободить память, удаляются элементы с хвоста).
Ничего особенно сложного с алгоритмической точки зрения; суть в том, что это должно быть как можно более эффективно и быстро, и поддерживать много памяти и очень много соединений одновременно. Идея в том, что когда вебсервер пишет какую-то часто используемую информацию в базу данных, он также посылает её в memory cache, а перед чтением таких данных из базы данных — запрашивает кэш. Свободной памяти у нас не так уж и мало. Одна из машин стоит практически неиспользуемая с 12 гигабайтами (когда-то это был глобальный БД-мастер, до того, как мы перешли на кластеры полтора года назад). На ней запустим штук 5 процессов, каждому разрешим два гигабайта. На других машинах — ещё несколько, зависит от эффективности, которую ещё предстоит в точности проверить.
(идея тут в том, конечно, что кэш глобален. Кэширование в памяти одного отдельного httpd-процесса или даже одной машины-вебсервера практически ничего не даёт, за исключением небольшого количества глобальных данных (напр. юзер-интерфейса на всяких языках). Memory cache глобален в том смысле, что, хоть одновременно бегут несколько демонов на разных процессах, данный ключ всегда будет записан в конкретный сервер и прочтён оттуда же — выбор сервера происходит с помощью хэш-функции по ключу)
Брэд написал такой демон на Перле, но когда он его запустил, тот сразу начал жрать 100% CPU. Мы решили с ним, что я перепишу его на C настолько эффективно, насколько смогу. Вот я этим и занимался вчера и позавчера. Получилось вроде бы очень неплохо. Сегодня часа в 2 дня мы запустили три пробных процесса, один из них под gdb (чтобы легко было найти проблему, если грохнется). Каждому из разрешили набирать до 2 гигабайт памяти, вот с тех пор они и набирают. Пока что кэшируются такие вещи, как текст всех записей, текст всех комментов, сабджекты, а также всякие мелочи относительно этого. Но к этому добавится ещё много всего. Тот, который был запущен раньше двоих остальных, набрал уже 1.939 гигабайта из положенных двух, я волнуюсь, т.к. когда он дойдёт до двух, начнёт реально выбрасывать уже существующие данные, и кто его знает, может, там ещё какой баг притаился (один баг на "живых" данных уже был обнаружен и исправлен; правда, это не у меня в демоне был баг, а в перловом коде-клиенте, к-й Брэд написал).
Вот он подползает к пределу (см. выделенные строки):
STAT curr_items 2533938
STAT total_items 6769553
STAT bytes 2023333707
STAT curr_connections 446
STAT total_connections 64416
STAT age 24369
STAT cmd_get 17749753
STAT cmd_set 7982028
STAT get_hits 11364921
STAT get_misses 6384832
STAT bytes_read 2770032780
STAT bytes_written 8880645645
STAT limit_maxbytes 2097152000
STAT limit_maxitems 0
Hit rate у этих серверов уже поднялся до 65% примерно (это значит, что в 65% случаев они получают из кэша то, что просят, иными словами, 65% текста всех записей и комментов читаются не из базы данных и диска, а из памяти). Если никаких неприятных сюрпризов не будет, то запуск пяти-шести таких демонов должен очень значительно разгрузить серверы и очень улучшить качество и скорость работы ЖЖ (для чего всё и задумано, собственно). Так что если в течение ближайших 2-3 дней скорость и качество ЖЖ сильно улучшатся, то в этом будет главным образом моя заслуга; а если не улучшатся — моя вина, что-то не предусмотрел, значит.
Эффективность зато на высоте. Каждый из этих трёх процессов обрабатывает сейчас примерно по 400 соединений одновременно, и хоть бы что. %CPU не повышается выше 1.5% у каждого. Просто загляденье!
Писал я это дело на чистом C под Debian. Где-то за полчаса вернулись все забытые навыки письма (а не чтения, навыки чтения никуда не пропадали) на C, пальцы перестали пытаться проделывать всякие перловские штучки. Пользовался такими замечательными вещами, как epoll (такой улучшенный poll()-like интерфейс, позволяющий очень эффективно поллить сотни и тысячи соединений. Как раз благодаря ему эти 400 соединений бегут сейчас, посвистывая, а в моих тестах и тысячу шутя брал), libevent (удобная библиотека событий, поддерживающая epoll в частности), и Judy (исключительно эффективная имплементация ассоциативного массива. В несколько раз быстрее "ручных" хэш-таблиц. Очень круто. Интерфейс у неё совершенно безумный какой-то. You're in a twisted maze of bizarre macros, all alike. Но я этот безумный интерфейс обкрутил несколькими нормальными функциями, локализовав тем самым безумие).
Приятно.
Программа — memory cache daemon. Принимает TCP-подключения на определённом порту, от клиентов принимает пары ключ/значение и запоминает, а когда начинает заканчиваться память, выбрасывает наименее используемые (по принципу LRU queue. Все элементы прошиты в списке. Входят они в него с головы. Всякий раз, когда какой-то элемент запрашивается клиентом, он передвигается опять в голову. А когда надо освободить память, удаляются элементы с хвоста).
Ничего особенно сложного с алгоритмической точки зрения; суть в том, что это должно быть как можно более эффективно и быстро, и поддерживать много памяти и очень много соединений одновременно. Идея в том, что когда вебсервер пишет какую-то часто используемую информацию в базу данных, он также посылает её в memory cache, а перед чтением таких данных из базы данных — запрашивает кэш. Свободной памяти у нас не так уж и мало. Одна из машин стоит практически неиспользуемая с 12 гигабайтами (когда-то это был глобальный БД-мастер, до того, как мы перешли на кластеры полтора года назад). На ней запустим штук 5 процессов, каждому разрешим два гигабайта. На других машинах — ещё несколько, зависит от эффективности, которую ещё предстоит в точности проверить.
(идея тут в том, конечно, что кэш глобален. Кэширование в памяти одного отдельного httpd-процесса или даже одной машины-вебсервера практически ничего не даёт, за исключением небольшого количества глобальных данных (напр. юзер-интерфейса на всяких языках). Memory cache глобален в том смысле, что, хоть одновременно бегут несколько демонов на разных процессах, данный ключ всегда будет записан в конкретный сервер и прочтён оттуда же — выбор сервера происходит с помощью хэш-функции по ключу)
Брэд написал такой демон на Перле, но когда он его запустил, тот сразу начал жрать 100% CPU. Мы решили с ним, что я перепишу его на C настолько эффективно, насколько смогу. Вот я этим и занимался вчера и позавчера. Получилось вроде бы очень неплохо. Сегодня часа в 2 дня мы запустили три пробных процесса, один из них под gdb (чтобы легко было найти проблему, если грохнется). Каждому из разрешили набирать до 2 гигабайт памяти, вот с тех пор они и набирают. Пока что кэшируются такие вещи, как текст всех записей, текст всех комментов, сабджекты, а также всякие мелочи относительно этого. Но к этому добавится ещё много всего. Тот, который был запущен раньше двоих остальных, набрал уже 1.939 гигабайта из положенных двух, я волнуюсь, т.к. когда он дойдёт до двух, начнёт реально выбрасывать уже существующие данные, и кто его знает, может, там ещё какой баг притаился (один баг на "живых" данных уже был обнаружен и исправлен; правда, это не у меня в демоне был баг, а в перловом коде-клиенте, к-й Брэд написал).
Вот он подползает к пределу (см. выделенные строки):
STAT curr_items 2533938
STAT total_items 6769553
STAT bytes 2023333707
STAT curr_connections 446
STAT total_connections 64416
STAT age 24369
STAT cmd_get 17749753
STAT cmd_set 7982028
STAT get_hits 11364921
STAT get_misses 6384832
STAT bytes_read 2770032780
STAT bytes_written 8880645645
STAT limit_maxbytes 2097152000
STAT limit_maxitems 0
Hit rate у этих серверов уже поднялся до 65% примерно (это значит, что в 65% случаев они получают из кэша то, что просят, иными словами, 65% текста всех записей и комментов читаются не из базы данных и диска, а из памяти). Если никаких неприятных сюрпризов не будет, то запуск пяти-шести таких демонов должен очень значительно разгрузить серверы и очень улучшить качество и скорость работы ЖЖ (для чего всё и задумано, собственно). Так что если в течение ближайших 2-3 дней скорость и качество ЖЖ сильно улучшатся, то в этом будет главным образом моя заслуга; а если не улучшатся — моя вина, что-то не предусмотрел, значит.
Эффективность зато на высоте. Каждый из этих трёх процессов обрабатывает сейчас примерно по 400 соединений одновременно, и хоть бы что. %CPU не повышается выше 1.5% у каждого. Просто загляденье!
Писал я это дело на чистом C под Debian. Где-то за полчаса вернулись все забытые навыки письма (а не чтения, навыки чтения никуда не пропадали) на C, пальцы перестали пытаться проделывать всякие перловские штучки. Пользовался такими замечательными вещами, как epoll (такой улучшенный poll()-like интерфейс, позволяющий очень эффективно поллить сотни и тысячи соединений. Как раз благодаря ему эти 400 соединений бегут сейчас, посвистывая, а в моих тестах и тысячу шутя брал), libevent (удобная библиотека событий, поддерживающая epoll в частности), и Judy (исключительно эффективная имплементация ассоциативного массива. В несколько раз быстрее "ручных" хэш-таблиц. Очень круто. Интерфейс у неё совершенно безумный какой-то. You're in a twisted maze of bizarre macros, all alike. Но я этот безумный интерфейс обкрутил несколькими нормальными функциями, локализовав тем самым безумие).
Приятно.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2003-05-26 11:29 am (UTC)no subject
Date: 2003-05-26 11:30 am (UTC)Re:
Date: 2003-05-26 11:31 am (UTC)no subject
Date: 2003-05-26 11:32 am (UTC)Re:
Date: 2003-05-26 11:37 am (UTC)no subject
Date: 2003-05-26 11:38 am (UTC)no subject
Date: 2003-05-26 11:43 am (UTC)Но посмотрим ещё, как дальше будет.
no subject
Date: 2003-05-26 11:51 am (UTC)no subject
Date: 2003-05-26 12:01 pm (UTC)Re:
Date: 2003-05-26 12:04 pm (UTC)Я, между прочим, волнуюсь насчёт того, как моя программка себя будет вести дня через 2-3 постоянного бега. Она использует обычный glibcшный malloc(), а я не знаю, как у него с дефрагментацией дела. Какая-то дефрагментация у него есть конечно, но вот насколько хорошая - не знаю.
no subject
Date: 2003-05-26 12:58 pm (UTC)У нас речь идет об амазоновских кэшах, где для каждого продукта, а также для каждого offering (два или более продавца могут предлагать один и тот же продукт по разной цене и с разной стоимостью доставки), хранится его цена и различные атрибуты - аллокатор предназначен для размещения сотен тысяч и миллионов структур фиксированного размера. Размещается блок из, например, 1048576*objectSize байт, и к нему прилагается массив из 1048576 битов: занято то или иное место или не занято. Мой алгоритм позволяет легко находить незанятое место, не производя линейное сканирование по всему миллиону битов.
no subject
Date: 2003-05-26 01:00 pm (UTC)(glibc malloc довольно-таки недурён, но best-fit от него ожидать не стоит. плюс к тому большие блоки берутся через mmap (это как-то конфигурируется, впрочем), а уж как mmap дефрагментирует -- это вопрос не к libc.)
no subject
Date: 2003-05-26 01:34 pm (UTC)no subject
Date: 2003-05-26 02:26 pm (UTC)no subject
Date: 2003-05-26 02:32 pm (UTC)Эта стратегия оказалась ошибочной, сервер, на котором бежали процессы, упал (возможно, это связано как-то с тем фактом, что я ещё вызывал mlockall() чтобы они не пейджились). Перед смертью один из процессов успел сказать, что malloc() возвращает ему ошибку.
Any ideas? Я могу аллокировать заранее все 2gb, sure, но если я сам буду своим маллоком, у меня будут те же проблемы с фрагментацией, I guess. Мне нужен хороший алгоритм дефрагментации (я могу двигать аллокированные блоки, мне это не страшно, но хотелось бы эффективности, чтобы поменьше это нужно было) или какие-то другие идеи. Практически все блоки у меня не фиксированного размера.
no subject
Date: 2003-05-26 02:43 pm (UTC)no subject
Date: 2003-05-26 03:15 pm (UTC)Пусть у нас есть битмап "нулевого уровня" из 2**20 = 1048576 битов. Нам нужно быстро находить в нем позицию произвольного нулевого бита.
2**20 битов - это 2**15 32хбитовых слов. Создадим битмап 1го уровня из 2**15 битов, таких, чтобы бит j в нем был равен 1 тогда и только тогда, когда все 32 бита в слове j в битмапе нулевого уровня равны 1. Аналогично создадим битмап 2го уровня из 2**10 битов, и битмап 3го уровня из 2**5 битов, т.е. одного слова.
Алгоритм аллокации: найти в единственном слове битмапа 3го уровня позицию произвольного ноля. Пусть это будет 11. Найти в слове 11 битмапа 2го уровня позицию произвольного ноля. Пусть это будет 30. Найти в слове 11*32+30 битмапа 1го уровня позицию произвольного ноля. Пусть это будет 19. Найти в слове (11*32+30)*32+19 битмапа 0го уровня позицию произвольного ноля. Пусть это будет 6. Свободна запись ((11*32+30)*32+19)*32+6 в блоке. Возвратим ее, но сначала сделаем следующее. Установим бит 6 в слове (11*32+30)*32+19 битмапа 0го уровня равным 1. Если слово (11*32+30)*32+19 битмапа 0го уровня равно 0xFFFFFFFF, установим бит 19 в слове 11*32+30 битмапа 1го уровня равным 1. Если слово 11*32+30 битмапа 1го уровня равно 0xFFFFFFFF, установим бит 30 в слове 11 битмапа 2го уровня равным 1. Если слово 11 битмапа 2го уровня равно 0xFFFFFFFF, установим бит 11 в единственном слове битмапа 3го уровня равным 1.
Алгоритм деаллокации: из позиции в блоке определяется индекс, и все вышеупомянутые биты устанавливаются равными 0.
Найти в 32хбитном слове нулевой бит можно ассемблерной инструкцией BSF, хотя сейчас я использую банальный цикл.
Allocation
Date: 2003-05-26 03:22 pm (UTC)Re:
Date: 2003-05-26 03:51 pm (UTC)что же касается фрагментации, то:
. если процесс и так не поднимаешься выше 1.5% CPU, то возможно просто не стоит об этом беспокоиться.
. если блоки, о которых идёт речь, больше страницы (4K), то ни к какой фрагментации они так и так не чуствительны. (то есть не они, а скорость доступа к ним).
. если всё совсем не так, опиши поподробнее.
no subject
Date: 2003-05-26 03:55 pm (UTC)Re: Allocation
Date: 2003-05-26 03:59 pm (UTC)I'm not sure Ilya's algorithm is better in this regard, though.
no subject
Date: 2003-05-26 04:15 pm (UTC)Фрагментация starts to kick in после того, как процесс доходит до границы положенной ему памяти. Предположим, я сказал ему при запуске не трогать больше 2gb. Он следит за своими malloc()'ами. Когда очередной malloc() грозит перевалить за 2gb в общей сложности, он удаляет столько блоков, сколько нужно, чтобы этот сработал. From this point on постоянно идёт процесс free - malloc.
Мне в принципе не страшно двигать уже аллокированные блоки. malloc() себе этого позволить не может, а я могу, т.к. свои ссылки смогу сам подправить. Вопрос в том, что мне это даёт и стоит ли мне забыть о маллоке и пользоваться чем-нибудь другим с хорошей дефрагментацией, пусть даже двигающей блоки иногда.
Фрагментация меня волнует меньше с точки зрения cpu time, больше по двум другим причинам: 1) memory waste - если реальная фрагментация съедает 50% памяти, то я пользуюсь 2Gb и ещё один трачу зря - слишком щедро. 2) проблема с переходом границы в 3Gb. В Линуксе у user-mode программы есть address space в 3Gb. Если я правильно понял всякие описания, к-е читал, malloc() использует data segment, расширяемый с помощью sbrk(), для первых 900Mb (дальше лежит ld.so и мешает продолжать), а остальное вписывает mmap'om. Но всё равно, при большой фрагментации мои реально используемые 2Gb могут перейти в почти 3Gb адресного пространства, после чего я стану получать ошибки от маллока.
Конкретно крэш сервера случился, как я теперь полагаю, не из-за маллока, а из-за mlockall(). Возможно, Линукс не потянул столь большое количество локнутых страниц в этих трёх процессах.
Re:
Date: 2003-05-26 04:38 pm (UTC)у тебя идеальный случай для generational GC, причём простого. причём более чем идеальный случай, т.к. тебе не надо даже искать кто умер, потому что ты это знаешь, у тебя же индекс LRU поддерживается (да?).
самый наивный (и медленный) вариант -- это когда у тебя только одно поколение. в этом случае алгоритм вырождается в простое сжимание (после удаления/отмечания необходимого количества мусора).
более продвинутый вариант -- переписывание наиболее востребованных вещей в специальный кусок памяти, который ты тоже будешь чистить, конечно, но реже. это будут "квиютники" (tenured objects, в смысле).
можно экстраполировать на сколько угодно поколений.
вможно просто произвольно поделить память на N удобно нарезанных кусков, и для каждого держать минимальный показатель LRU нахходящихся в нём объектов. это и будет определять поколения. когда надо освобождать место, отсортировать по этому показателю и просто явочным порядком объявить кусок с самым низким значением свободным. (чем больше об этом думаю, тем больше мне эта идея нравится, кстати. только она ограничивает максимальный размер объекта величиной <отведённая память>/N).
в принципе, простейший вариант (одно поколение, тривиальное сжимание всего) должен работать нормально, поскольку все данные в физической памяти. ждёт-то тебя сеть, которая скорее всего такой паузы просто не заметит.
бесконечная тема, а мне тут работать надо. :)
no subject
Date: 2003-05-26 05:02 pm (UTC)а меж тем
алгоритм Бонвика (http://citeseer.nj.nec.com/bonwick94slab.html)
уж 10 лет скоро отметит. оригинальный описан и у
Vahalia, и в Solaris Internals, и реализован в ядрах Солариса, Линукса (вроде с глупостями, не смотрел) и т.д.
кое-что
здесь, но лучше всего найти последние статьи Бонвика - не знаю где, помимо Sun.
и еще стоит посмотреть работы J.Liedtke по кэш-серверу (когда он в IBM TJWatson был) (http://linux-mm.org/mm-links.shtml)
no subject
Date: 2003-05-26 05:09 pm (UTC)Extending the Slab Allocator to Many CPUs and Arbitrary Resources
Jeff Bonwick, Sun Microsystems
Jonathan Adams, California Institute of Technology
html (http://www.usenix.org/events/usenix01/full_papers/bonwick/bonwick_html/)
pdf (http://www.parrotcode.org/talks/vmem.pdf)