немного о работе

[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. Но я этот безумный интерфейс обкрутил несколькими нормальными функциями, локализовав тем самым безумие).

Приятно.

Comments

[sergeax.livejournal.com]

А что-то я этого ни в одном CVS не вижу? Или плохо ищу?

Re:

[avva.livejournal.com]

Не успел ещё Брэд в CVS закинуть, но скоро кинет. Пока там есть только клиентская сторона (cgi-bin/LJ/MemCache.pl, и вызовы MemCache в разных местах кода, пока что только в ljlib.pl, ljprotocol.pl и ljlang.pl, если не ошибаюсь).

[sergeax.livejournal.com]

Раз уж вы так быстро отвечаете :), не могли бы вы заодно прокомментировать новую вводную от whitaker по поводу Birthday Reminders? Меня смущают два пункта - про разбивку запросов по 100000 userids и про пуск-стоп скрипта. Они рушат заказанную вами функциональность "посылать письма френдам одним запросом, а не прогонять по 2-3 тысячи запросов в цикле выяснения у кого день рождения сегодня". Чтобы их реализовать, надо будет откатиться к старому способу генерации оповещений.

[ctpeko3a.livejournal.com]

Кстати, сегодня жж просто летает! Если это благодаря Вам, а не просто погоде - огромное спасибо!

[avva.livejournal.com]

Думаю, что в значительной части благодаря мне, да ;)

Но посмотрим ещё, как дальше будет.

[(Anonymous)]

сегодня (26) в штатах выходной - день Линкольна.

[ctpeko3a.livejournal.com]

Во-первых - Memorial Day. Во-вторых - он был вчера, а сегодня гуляют за воскресенье. В третьих - я сам платный юзер, поэтому я хожу на быстрые сервера. В четвёртых - по личным ощущениям разница между что рабочим днём и буднями больше видна в русскоязычных журналах, нежели в англоязычных. То есть русские пишут с работы, а американцы отовсюду.

Ну и в пятых, для самого себя, анонимусам отвечать - себя не уважать. :оЬ

[tangash.livejournal.com]

айм сори за офтопик, но я у меня вопрос: у ФИФА не отображаються Постинги пользователей, я уже в течении часа вижу только 5 новых постов :(

Re:

[avva.livejournal.com]

Это известная проблема, у которой пока решения нет, увы.

[ex-ilyavinar899.livejournal.com]

А я тут алгоритм для специализированного memory allocation сочинил и закодировал...

Re:

[avva.livejournal.com]

А в чём специализация?

Я, между прочим, волнуюсь насчёт того, как моя программка себя будет вести дня через 2-3 постоянного бега. Она использует обычный glibcшный malloc(), а я не знаю, как у него с дефрагментацией дела. Какая-то дефрагментация у него есть конечно, но вот насколько хорошая - не знаю.

[ex-ilyavinar899.livejournal.com]

Я не знаю ответа на твой вопрос про фрагментацию malloc. Я только знаю, что под Линуксом барьер для "обычного" malloc - около 900MB; дальше нужно использовать mmap с кастом-аллокатором.

У нас речь идет об амазоновских кэшах, где для каждого продукта, а также для каждого offering (два или более продавца могут предлагать один и тот же продукт по разной цене и с разной стоимостью доставки), хранится его цена и различные атрибуты - аллокатор предназначен для размещения сотен тысяч и миллионов структур фиксированного размера. Размещается блок из, например, 1048576*objectSize байт, и к нему прилагается массив из 1048576 битов: занято то или иное место или не занято. Мой алгоритм позволяет легко находить незанятое место, не производя линейное сканирование по всему миллиону битов.

[cmm.livejournal.com]

а ты не аллокируешь всё сразу заранее?   2 гига заранее ведь задаёшь вроде?

(glibc malloc довольно-таки недурён, но best-fit от него ожидать не стоит.   плюс к тому большие блоки берутся через mmap (это как-то конфигурируется, впрочем), а уж как mmap дефрагментирует -- это вопрос не к libc.)

[s1m.livejournal.com]

Если не секрет, какая получилась результирующая скорость (rps)?

Re:

[avva.livejournal.com]

Это я как раз не измерял, сорри.

[malaya-zemlya.livejournal.com]

От балды можно предложить еще следующий вариант: вместо непрерывных кусков памяти выделять цепочки блоков. Поскольку записи содержат, как я это понял, заголовок + текст, то скорость обработки информации практически не изменится (текст обрабатывается последовательно, так?)

Если при этом сделать размер выделяемого блока кратным какому-нибудь числу (например, 80 байтов - чтобы заголовок всегда влазил в один кусок), то проблем с фрагментацией, сбором мусора и проч. не будет вообще. Выделение памяти будет состоять просто в том, чтобы брать куски со свободной кучи, пока не наберется требуемое количество памяти. От последнего куска отрезается лишнее и voila.

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

Надо ебук?

[kukutz.livejournal.com]

Memory Management: Algorithms and Implementation in C/C++
by Bill Blunden.
ISBN: 1-55622-347-1, 360 Pages, February 2003.

Re: Надо ебук?

[avva.livejournal.com]

Давай!

Re: Надо ебук?

[dmierkin.livejournal.com]

и мне !

[blacklion.livejournal.com]

А можно и мне? Давно ищуту книжку...
lev [at] serebryakov [dot] spb [dot] ru

Re: Надо ебук?

[shtraz.livejournal.com]

А можно и мне? если она конечно еще

shtraz@mail.ru (если больше 2-3 мегов, то лучше разбить для верности на несколько писем)

Очень симпатичная статья о memory fragmentation

[photon.livejournal.com]

И называется скромно: The Memory Fragmentation Problem: Solved?

На нее даже Кнут ссылается (в главе о memory management кажется)

Highly recommended

Re: Очень симпатичная статья о memory fragmentation

[avva.livejournal.com]

Спасибо!

[atz-2085.livejournal.com]

Сильно похоже на идеальную ситуацию для применения протокола Bit-Torrent.
если его получится переделать для такой задачи )