Позвольте мне начать с того, что на самом деле не предполагается писать собственные распределители памяти. Бергер, Цорн и МакКинли полностью развенчали потребность в них для подавляющего большинства населения в [1]. Если вы ищете быстрый распределитель, такие проекты, как jemalloc, tcmalloc и dlmalloc, проделали такую ​​большую работу по улучшению glibc без изменения интерфейса malloc/free, что вам даже не нужно подумайте о своем распределителе памяти, если только вы не делаете что-то чрезвычайно чувствительное к производительности. Просто накинь на корпус jemalloc и получи бесплатное улучшение производительности, потом больше не заморачивайся. Это была наша теория, когда мы перешли на jemalloc в AppNexus в августе 2011 года, и она остается теорией. Но потом мы все равно построили свой собственный аллокатор. Это история о том, почему и как.

К несчастью для нашего здравомыслия, мы прошли долгий путь с августа 2011 года. На данный момент у меня даже нет графиков скорости запросов, которые уходят так далеко, но наш трафик увеличился более чем в 20 раз с 2013 года. временный и сложный характер многих операций (аукционов), мы делаем много размещений. Существует высокая вероятность как утечек, так и влияния на производительность.

Вообще говоря, наши большие системы имеют две основные категории распределения памяти: чрезвычайно долгоживущие (порядка часов или дней) и чрезвычайно недолговечные (порядка миллисекунд). Долгоживущие выделения составляют подавляющее большинство выделенного пространства, но кратковременные выделения составляют огромное большинство выделений и являются причиной большинства наших утечек памяти, поскольку они Выделяются так часто. Кроме того, malloc и free (и связанные с ними подпрограммы) могут легко составлять 10% профиля производительности наших приложений, даже при работе под управлением jemalloc. При 4-5 миллионах запросов в секунду количество оборудования, необходимого для поддержки 10% нашего профиля производительности, является существенным.

Jemalloc отлично справляется со своей задачей, но нам действительно нужен slab-аллокатор, чтобы добиться высокой производительности. Итак, повторюсь: не следует не писать свой собственный распределитель. Единственным реальным исключением являются распределители на основе регионов, эффективность которых была показана [2]. Тем не менее, распределители регионов делают множество предположений о дизайне интерфейса, которым производственные системы могут не соответствовать. Большинство из них требует, чтобы вы знали, в какой регион поместить выделение для данной транзакции, и чтобы вы освободили весь этот регион в конце транзакции. В этом посте представлен производительный, безопасный распределитель областей без компромиссов интерфейса.

Требования

pool_party был разработан как для предотвращения утечек памяти на пути запроса (краткосрочные выделения), так и для уменьшения количества ресурсов, необходимых только для выделения памяти нашим приложениям. Традиционный способ остановить утечки — написать сборщик мусора, но я только что сказал, что мы собираемся увеличить скорость, так что это исключено. Другой вариант — выделить и освободить только в нескольких местах и ​​очень убедиться, что ваши free верны. Как следует из названия, это то, с чем мы пошли: распределитель пула, привязанный к концепции транзакции, которая в большинстве случаев представляет собой запрос показа на нашем внешнем интерфейсе для рекламы (impbus).

В идеале распределитель пула на основе транзакций должен выделять большой объем памяти ровно один раз в начале запроса и освобождать эту память по завершении запроса. Мы могли бы связать каждый запрос с пулом, но как каждый вызов нашего malloc узнает, в какой пул поместить распределение? Нам придется изменить интерфейс malloc, а это не то, что нас сейчас интересует. Переход на типизированный malloc (an_malloc(type, size)) был не совсем забавным, и наша кодовая база достаточно выросла после этого перехода, что мы определенно не делаем. хочу снова пройти через эту боль.

Итак, требования к нашему новому аллокатору:

  1. по крайней мере, так же быстро, как ванильный джемаллок
  2. предотвращает утечки, распределяя ресурсы по пулам и освобождая эти пулы в хорошо известных и проверенных точках.
  3. не изменяет интерфейс malloc, который у нас есть сейчас.

1) и 2) достаточно просты, особенно в сочетании: выделение в пул обычно представляет собой просто приращение чего-то вроде pool->used. Тем не менее, 3) действительно мешает работе, поскольку мы не знаем, в какой пул выделить ресурсы. Предположение, что все выделения производятся в самый последний пул, работает, когда у вас есть пул для каждого запроса, а запросы запускаются и завершаются без вытеснения, но это не так. Запрос на impbus состоит из нескольких фаз с асинхронными вызовами других элементов сети (например, участников торгов и поставщиков данных). Эти запросы не являются общими, поэтому все является локальным для потока. Эти запросы мультиплексируются в цикл событий одного потока, поэтому в любой момент один и тот же пул может использоваться несколькими запросами.

Стрелять.

Гипотетический первый разрез

Вот самая простая реализация распределителя пула на основе транзакций в качестве основы для понимания некоторых сложностей, которым нужно следовать. Это мой любимый вид псевдокода C/Python, так что, пожалуйста, потерпите меня.

Это действительно так. Это рабочий распределитель пула с отношением «многие ко многим» между транзакциями и пулами. Каждый пул подсчитывается по ссылкам, чтобы убедиться, что ни один запрос не имеет открытых ссылок на него до того, как он будет уничтожен. Когда мы закрываем транзакцию, мы уменьшаем количество ссылок в ее пулах и освобождаем их, если количество ссылок стало равным нулю.

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

И снова с чувством

Единственный раз, когда мы точно знаем, какая транзакция является текущей, — это когда мы создаем транзакцию. Кроме этого, нам потребуется немного магии, чтобы выяснить, к какой транзакции добавить текущий пул в malloc(). Понятно, что нам нужно избавляться от списка пулов в каждой транзакции.

Поскольку мы представляем набор пулов в виде очереди, упорядоченной по времени создания, мы можем использовать время в своих интересах. Возраст в этой системе определяется как относительное положение в однопоточном связанном списке, а не какие-либо функции часов. Мы знаем, что каждая транзакция должна выделять память либо в пул, который был самым молодым на момент создания транзакции, либо в пулы, созданные после этого момента. Таким образом, все пулы, которые нам, возможно, придется освободить при уничтожении транзакции, моложе, чем первый пул, обнаруженный транзакцией. Назовем этот пул pool_created_into.

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

Это работает, потому что теперь мы используем счетчики ссылок только для пометки пулов, которые были самыми молодыми на момент создания транзакции. По сути, это превращает их в «барьеры», за которыми мы не будем уничтожать память, поскольку транзакции могут по-прежнему использовать эти пулы. Я думаю, именно этот взлом заставил моего босса назвать этот проект «волшебным распределителем памяти». Это также делает это формой сбора прокси - последняя транзакция, имеющая счетчик ссылок в пуле, поможет очистить другие транзакции, которые использовали этот пул, когда все они будут завершены.

Вот что мы имеем сейчас:

Характеристики

Во-первых, самый простой: поскольку мы можем memset каждый блок каждого пула, когда мы возвращаем его как указатель, мы амортизируем нулевое заполнение (memset) для всех объектов. Эта амортизация дает значительный прирост производительности — большинство наших объектов должны быть установлены в память при распределении, если они еще не установлены. Н.Б. единственный способ, которым мы можем позволить себе memset 32-мегабайтные регионы для распределения, заключается в том, что мы делаем это постепенно, когда мы выдаем адрес, который выходит за границу страницы. Автоматическое заполнение нулями устраняет целый класс ошибок, самые неприятные из которых связаны с неудачным поиском в хэш-таблице из-за неинициализированного заполнения в составных ключах. Я даже не хочу вспоминать, сколько раз это меня кусало.

Сторонники распределителей регионов (и особенно тех, которые прикрепляют регионы к рабочим единицам) всегда приводили пространственную локальность в качестве причины для их использования, и легко понять, почему: помимо 16-байтового выравнивания, требуемого POSIX, все наши выделения для данная часть транзакции, вероятно, попадает в пул и максимально плотно упакована. В среднем с 32 МБ пулом по умолчанию (очень большие выделенные ресурсы получают свой собственный регион) мы видим следующее (это взято из работающей системы):

epochs_open: 12
allocations_per_epoch: 46243.865013
size_alloced_per_epoch: 13290397.034721
avg_refcount: 56.693243
max_refcount: 327

Таким образом, мы фактически используем в среднем только 12 МБ из наших 32-мегабайтных пулов, и мы можем поместить › 50 запросов в один и тот же пул. В среднем я заметил, что у нас есть почти исключительно один пул на поток в любой момент.

Наконец, у нас есть несколько запросов в одном пуле. Это обеспечивает низкую внешнюю фрагментацию, поскольку рабочий набор потока, скорее всего, будет находиться в одном регионе. В результате нам не нужно так много думать о том, насколько большим должен быть размер нашего пула — чем больше, тем лучше для нас.

Как на самом деле втиснуть это в производственную среду

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

Новый класс ошибок для распределителя пула — это не использование после освобождения, а использование после закрытия транзакции. На самом деле мы стали более терпимыми к использованию после освобождения, когда я развернул pool_party просто потому, что free — это nop, и, таким образом, запрос может получить доступ ко всем когда-либо выделенным объектам, пока весь запрос не будет уничтожен. Исчез еще один класс ошибок. На самом деле, нам даже больше не нужно звонить free, что вызвало ожесточенные дебаты о том, стоит нам это делать или нет.

К сожалению, есть части нашей системы (в основном журналы), которые используют части транзакции после того, как запрос, которому она соответствует, был дан ответ и уничтожен. Мы постепенно переходим к модели, в которой этого не происходит, но в то же время нам нужно было вывести распределитель, и мы не могли быть подвержены сбоям или повреждению данных. Для памяти, которая создается в потоке запросов, а затем используется вне транзакции, мы должны были поддерживать выделения без пула (обычные, автономные).

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

Есть еще одна проблема: как узнать, какой аллокатор использовать при возврате из обратного вызова после сетевого запроса? Существует целый хак динамического замыкания, подробное описание которого заняло бы слишком много времени, но достаточно сказать, что все обратные вызовы без проблем восстанавливают контекст распределителя вызываемого объекта.

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

Наконец, мы заметили, что в нашей системе есть некоторые вещи, которые просто не могут использовать pool party, либо потому, что тип слишком опасен для миграции, либо по другим, более нелепым причинам. Но мы по-прежнему хотим пользоваться преимуществами автоматической очистки! Поэтому мы придумали, как транзакции могут использовать наш механизм, похожий на сбор прокси-серверов, для очистки объектов, которые не используют пул-пати. У каждого пула есть список функций очистки, которые нужно запустить при уничтожении пула, и можно добавить к этому списку функцию с именем an_pool_adopt. Список для добавления — это тот, который принадлежит самому младшему пулу, так же, как и распределения. Это упрощает очистку сложных типов, но не позволяет нам фактически вызвать free() для объекта, поэтому это немного менее устойчиво к ошибкам, чем обычное выделение.

В общем, наш новый аллокатор:

  1. В результате на код jemalloc затрачивается примерно на 40% меньше времени, которое мы можем потратить на то, чтобы сделать каждое выделение calloc, и при этом останется прирост производительности,
  2. Устраняет утечки на пути запроса для объектов, которые выбирают его и,
  3. Не изменяет наш существующий интерфейс распределения.

Pool party уже видел одну повторную реализацию начиная с v1 (спасибо @pkhuong!), и я уверен, что она увидит еще одну, когда мы перенесем больше приложений, чтобы использовать его, и обнаружим новые и патологические варианты использования. Я думаю, что его можно лучше адаптировать к многопоточной среде и сделать его более удобным для использования. Еще не все.

[1] Эмери Д. Бергер, Бенджамин Г. Цорн и Кэтрин С. МакКинли. 2013. OOPSLA 2002: Пересмотр пользовательского распределения памяти. SIGPLAN Нет. 48, 4S (июль 2013 г.), 46–57. DOI=10.1145/2502508.2502522 http://doi.acm.org/10.1145/2502508.2502522

[2] Дэвид Гей и Алекс Эйкен. 1998. Управление памятью с явными областями. SIGPLAN Нет. 33, 5 (май 1998 г.), 313–323. DOI=10.1145/277652.277748 http://doi.acm.org/10.1145/277652.277748

Автор Джон Уиттрок