Ловушка параллелизма: как атомарный счетчик остановил конвейер ( conviva.com )
Неплохой компромисс, на который я уже шел в прошлом.
Сложность здесь (которую автор решил с помощью rcu) заключается в том, что здесь ОЧЕНЬ легко создать состояние гонки.
Представьте, что поток A и поток B хотят добавить новое значение в хэш-карту. Они приходят одновременно. Наивное использование arc_swap в конечном итоге приведет к победе одного из потоков и исчезновению значения из другого потока. Не очень здорово.
Но еще одна вещь, которую следует учитывать при использовании этого подхода, заключается в том, что он является дорогостоящим при любом виде конкуренции за запись. Как только записи начинают резко расти, количество выделений увеличивается потенциально очень плохим образом. Если у вас есть 3 потока, которые хотят писать одновременно, один поток создаст 1 полную копию. 1 создаст 2 полных копии, а 3-й поток создаст 3 полных копии. Если вашей базовой структуре данных выделена какая-либо память, это становится довольно плохим компромиссом.
Забавно, но один из простых способов решить эту проблему — снова ввести блокировки, но только для писателя. Возможно, это хорошая идея, если вы тратите более ~1000 циклов на создание структуры данных.
> Большая разница между конкурентной хэш-картой и ArcSwap заключается в том, что ArcSwap требует выгрузки всех базовых данных при каждой записи, но компенсирует это очень дешевыми чтениями. Писатели даже не должны ждать, пока все читатели закончат, поскольку новая эпоха создается с новой версией данных.
Вот где побеждают древовидные структуры данных. Git, Subversion и чистые функциональные языки не заменяют всю структуру данных. Они создают новый элемент и присоединяют его к дереву, создавая новую версию предполагаемого родителя и новую версию его родителя вплоть до корневого элемента.
Так что где-то есть место для гибрида ArcSwap и DashMap, который использует sharded copy on write. Этим ребятам это, вероятно, не нужно, учитывая их низкую скорость записи, но shards должны помочь с конкуренцией записи для других вариантов использования.
Вам по-прежнему нужно что-то близкое к ArcSwap с вашей постоянной структурой данных, поскольку после построения нового дерева (возможно, с использованием переходных процессов) вам необходимо перезаписать старый корень новым, атомарно (и, вероятно, на самом деле в цикле CAS).
Слева-направо — это опция, которая позволяет избежать цикла CAS, поскольку это примитив с одним писателем.
Итак, корневой элемент — это единая точка перегрузки для всех записей, верно?
С файловой системой на основе деревьев этого часто достаточно, чтобы помочь уменьшить количество конфликтов записи. Потому что вы не сериализуете все это черт возьми обратно на диск, а только те части, которые изменились, которые логарифмически зависят от размера истории правок. А git использует GC для обработки записей, которые доходят до конца, а затем терпят неудачу из-за конфликтов одновременного доступа.
Для проблем в памяти есть B-деревья, которые являются более старым решением многих проблем, чем большинство пользователей HN, включая меня. Тогда у вас все еще есть шардинг, который, как я фактически указал, был бы частью лучшего гибридного решения.
im::HashMap — отличный инструмент
Мне бы хотелось, однако, иметь похожую постоянную структуру, где указатели узлов на каждом уровне были бы общими для потоков, вместо использования, например, атомарных. Мутация на ветке могла бы записать, что мутация “только” для потока ID X, который сделал мутацию. В какой-то более поздний момент “коммит” мог бы согласовать хранилище с глобальным, возможно
Да, вы можете легко организовать хэш-карту иерархически.
Неясно, понимает ли автор ложное разделение. Чрезмерное «пинг-понговое» распределение строк кэша между ядрами означает, что строка кэша, на которой находится счетчик, используется совместно с другой памятью, к которой осуществляется конкуренция.
Если убедиться, что переменная счетчика сидит одна на своей собственной строке кэша, это полностью устранит чрезмерное поведение пинг-понга. Строка кэша со счетчиком, конечно, все еще будет пинг-понгом, поскольку она мутирует, но не чрезмерно.
Это может зависеть от архитектуры. ISTR что-то о том, что ядра ARM агрессивны/спекулятивны в отношении предварительной выборки, и это вызывало похожие проблемы с использованием страниц общей памяти CoW в другом проекте, в котором я участвовал, даже когда я старался избегать срабатывания TLB. IIRC, их решением также в конечном итоге стало обновление указателя структуры эпохи на основе CAS/CMPXCHG.
Я не думаю, что ложное разделение имеет здесь значение. Отскок счетчика по кэш-строке, который пишут даже читатели, был бы достаточным для объяснения узкого места. Барьер, который, вероятно, подразумевается или явно подразумевается в атомарном RMW, используемом для обновления счетчика, также остановит конвейер, не позволяя любой другой операции с памятью выполняться одновременно.
Все потоки, многократно обращающиеся к одному и тому же участку памяти, способны поставить любой процессор на колени.
Важнейшей частью исправления является то, что читателям больше не придется изменять какие-либо разделяемые области памяти и полагаться на отложенное освобождение.
> Строка кэша со счетчиком, конечно, все еще будет пинг-понговой, поскольку она мутирует, но не чрезмерно.
И способ решения этой проблемы заключается в использовании отдельного счетчика для каждого ядра, по крайней мере на одну строку кэша друг от друга, чтобы гарантировать, что все они получат отдельные строки кэша. Недостатком является то, что вы теряете возможность считывать счетчик атомарно, но если счетчик увеличивается достаточно быстро, и вам нужны счетчики для каждого ЦП, то значение на определенный момент времени в любом случае по сути бессмысленно.
Для popcounts это классическое решение. Сделайте агрегацию ленивой и беспокойтесь о сохранении точности k меньших чисел дешево, и позвольте читателю беспокоиться о вычислении итога, который, скорее всего, в конечном итоге будет согласованным.
Но для многократного чтения и исключительной записи это никогда не сработает. Или, по крайней мере, без дополнительного кремния. Что, возможно, должно быть чем-то. Проблема, конечно, в том, что многословная атомная инструкция суммы фактически должна будет пересекать строки кэша, чтобы избежать ложного обмена. Так что вы получите счетчики на смежных строках кэша, но занимающие по 64 байта каждая, что очень много.
Это фактически потребовало бы создания специальной области памяти с другим поведением когерентности кэша, и я не вижу, чтобы это было просто, быстро или обеспечивало обратную совместимость, возможно, поэтому мы этого и не делаем.
«Счетчик» здесь — RWMutex (или RWSpinLock). Вы не можете сделать его распределенным, гарантируя взаимное исключение [1]. Вы можете использовать хэш-карту с более мелкозернистой блокировкой, но для решения проблемы повторного хэширования вам в любом случае придется заново изобретать что-то вроде ArcSwap.
[1] Существуют RWMutex с полной блокировкой без записи, но они значительно сложнее и требуют обнаружения эпох, как ArcSwap, поэтому существенных преимуществ нет.
Длинный блог, корпоративное форматирование, покрытое всплывающими окнами и изображениями героев, скриншоты невероятно уродливого графика пламени кетчупа и горчицы, обсуждение с некоторыми ошибками или неопределенностью, совершенно ванильная деталь производительности. Это универсальные ингредиенты полутехнической маркетинговой игры SaaS-компании среднего размера.
Также непонятно, как первый график, ось Y которого обозначена как “req/s”, показывает пик задержки. Задержка на этом графике не видна, AFAICT, только пропускная способность.
Я думаю, что, возможно, стоило бы обратить внимание читателей, не знакомых с проблемной областью, на ложный обмен информацией, но у меня не сложилось впечатления, что это был ложный обмен информацией, а обычный старый обмен информацией.
Я думаю, ты прав.
Почему бы и нет? Если достаточное количество читателей мутируют один и тот же счетчик ссылок с очень короткими критическими значениями, то это определенно может быть проблемой, независимо от ложного обмена.
> Если достаточное количество читателей мутируют один и тот же счетчик ссылок
Ну, если бы они мутировали счетчик ссылок, я бы назвал их писателями, а не читателями. =P
Но да. Многие ошибочно полагают, что запись atomic_int из многих потоков — это очень быстро. Я имею в виду, что это атомарно! Это не может быть меньшим атомом работы! Увы, это невероятно неверно. Даже атомарные int могут быть чрезвычайно медленными.
Они являются логическими читателями, мутация — это деталь реализации.
Что относится к фундаментальному принципу параллельного программирования: «(логические) читатели не должны (физически) писать*».
*к спорной общей памяти
Ну да, отсюда и исправление.
Или, может быть, просто так получилось, что при наблюдаемой нагрузке большинство читателей действительно хотели бы потрогать именно этот счетчик, и в этом случае единственным решением будет избавиться от счетчика.
> Однако дальнейший анализ в среде perf показал, что, хотя и наблюдался резкий рост числа активных сеансов, они постепенно пошли на спад, в то время как время обработки DAG продолжало оставаться высоким.
Громоподобные стада сделают это. Теория очередей. Когда очередь выстраивается, ее расчистка занимает гораздо больше времени, чем подсказывает интуиция.
Не хочу быть таким человеком, но разработчики Go первыми до этого додумались, а затем реализовали (действительно хорошую, на мой взгляд) параллельную хэш-карту, которая делает то же самое, что описано в статье, но без копирования всей хэш-таблицы каждый раз: https://pkg.go.dev/sync#Map
Конкурентные карты часто проще реализовать в языках GC, поскольку вы можете использовать сборщик мусора для очистки старых значений. В то время как без GC вам понадобится альтернатива, например RCU.
Я согласен с утверждением, что в языках GC параллельные структуры проще реализовать (и мне это на самом деле нравится в Go), однако, по сути, языки GC также каким-то образом реализуют саму GC :), так что единственное реальное отличие, я полагаю, заключается в том, что для некоторых (сложных) структур данных вам _нужен_ GC, чтобы реализовать их чисто, и именно это делает RCU.
Я не видел реализации RCU в чистом пользовательском пространстве, которая бы работала хорошо без поддержки ядра. Методологию RCU легко понять, но как реализация в пользовательском пространстве понимает, когда безопасно избавиться от части структуры данных? Разве вам не нужен примитив для запуска некоторого кода на каждом ЦП?
Вам не нужна помощь ядра, чтобы заставить структуры типа RCU пользовательского пространства работать достаточно хорошо. Я делал это дважды. Цена, которую вы платите за отсутствие помощи ядра, заключается в том, что некоторым потокам иногда приходится выполнять дополнительную работу, например, писать ожидающие сигналы, зацикливаться на очень коротком чтении, записывать в указатель опасности, снова читать, пока считанное значение не станет стабильным, или выполнять сборку мусора, но эта цена не слишком высока.
Вам просто нужно отслеживать состояния покоя каждого потока, как бы они ни были реализованы.
Да, но разве это не сложно реализовать в библиотеке?
Локальные переменные потока будут использоваться с ленивой инициализацией. Очистка может быть немного сложной в зависимости от того, какую реализацию локального потока вы используете. Поддержка локального потока не так хороша, как должна быть.
Не совсем. https://github.com/nicowilliams/ctp мой — API не RCU, а более простая и удобная в использовании конструкция «потокобезопасной переменной». Там вы найдете две реализации на языке C. Я использую это в производстве почти десять лет без каких-либо проблем. (Долгое время у меня отсутствовал элемент-член производителя в примитиве create (ой!), но поскольку это происходит только один раз, у меня никогда не возникало никаких проблем.)
Честно говоря, я долго думал об этом. Но сейчас эти методы хорошо известны, так что теперь стало проще «копировать» ход мыслей других, а именно ход мыслей — это и есть трудная часть.
Я бегло просмотрел вашу ссылку. Как это вообще может считаться RCU? Парадигма чтения-копирования-обновления требует, чтобы шаг обновления мог знать, получено ли обновляемое значение из недавней копии. Функция set здесь даже не позволяет вам атомарно сравнивать вашу версию чтения с текущей версией. Представьте, что вы реализуете простой массив с помощью RCU; вы читаете массив, делаете копию, добавляете в массив, а затем вам нужно атомарно сравнить указатель массива pre-append и установить массив, просто чтобы не потерять записи других потоков.
Функция get всегда возвращает стабильное значение, если хотя бы одно значение было записано (иначе вы получите NULL, естественно).
Функция set не сделает недействительными какие-либо значения, видимые функцией get, на которые все еще могут ссылаться, но новое значение будет видно всем последующим функциям get.
Старые значения будут уничтожены, если на них больше не будет ссылок.
Для чтения-копирования-обновления вам нужно будет установить блокировку (которую читатели не устанавливают), получить текущее значение (оно будет текущим, поскольку вы блокируете других записывающих), скопировать его, изменить копию, а затем установить новое значение.
Вам не нужно читать-копировать-обновлять, если новые значения не зависят от предыдущих значений. Так что мой API не заставляет читать-копировать-обновлять, но вы можете сделать RCU с ним.
Понятно. Так что, по сути, вы хотите, чтобы писатели использовали собственную блокировку для координации записи. Хорошо, тогда это делает неудобным иметь дело с читателями, которые могли бы, но нечасто, стать писателями. Им приходится делать второе чтение под блокировкой, чтобы записать. И если выбрать структуру данных, для которой копирование не является дешевой операцией, это может быть медленнее, чем классический RCU.
> Хорошо, тогда это делает неудобным иметь дело с читателями, которые могли бы, но нечасто, стать писателями. Им приходится делать второе чтение под замком, чтобы писать.
Ну, во-первых, чтение очень дешево, так что это не большая проблема. В некоторых системах читатели вообще не поворачиваются, чтобы записать, так что это нормально, а в других они не изменяют текущее значение. Например, в одной из систем, которую я построил, мы используем файлы TinyCDB, и когда новые файлы переименовываются на место, мы открываем их и устанавливаем дескриптор на одну из этих потокобезопасных переменных — здесь нет чтения-изменения.
> А если выбрать структуру данных, для которой копирование не является дешевой операцией, это может оказаться медленнее, чем классический RCU.
В любом случае это RCU. Лучше всего публиковать неизменяемые данные с помощью RCU и проектировать структуры данных, где изменения копирования при записи не должны копировать всю структуру данных, а только небольшие ее части. Например, в дереве вам нужно будет копировать только внутренние узлы из того, который вы изменяете, в корень.
Всегда можно построить хеш-таблицу, где каждая ячейка представляет собой одну из этих потокобезопасных переменных (или обычный старый RCU), хотя для этого придется сделать эти потокобезопасные переменные более легкими, чтобы сделать реалистичным их большое количество (в настоящее время в моей реализации на каждую переменную приходится pthread_key_t, который не масштабируется).
В TFA ArcSwap по сути неотличим от хэш-таблицы, доступной только для чтения, опубликованной в чем-то вроде одной из моих потокобезопасных переменных, и для TFA это сработало лучше, чем доступные альтернативы, несмотря на нагрузку копирования при записи.
Кстати, я изначально создал эту штуку, чтобы глобальная конфигурация была доступна потокам, которые в противном случае ничем не делятся, и чтобы служба могла быть перенастроена во время выполнения. Без чего-то вроде этого (или просто старого доброго RCU) ваши возможности ограничены такими вещами, как использование блокировок чтения-записи (которые намного хуже всего, что вы можете себе представить, чтобы быть плохим в RCU, используемом с неизменяемыми структурами данных). Я был очень недоволен блокировками чтения-записи, когда мне нужно было решить эту конкретную проблему в Sun, но я не создавал эту штуку, пока не ушел из Sun (Oracle).
В настоящее время библиотеки RCU-ish довольно широко доступны. OpenSSL 3.3 (или это был 3.4?) имеет что-то вроде этого после провалов в производительности потоков 3.0. В частности, OpenSSL имеет хэш-таблицу RCU-ish. Она может вас заинтересовать. IIRC (но прошло много времени с тех пор, как я смотрел), она использует один указатель опасности на поток для получения стабильной ссылки на ключ или значение, достаточно длинной, чтобы затем увеличить счетчик ссылок — довольно умно, и это, по сути, способ сделать «потокобезопасную переменную» достаточно легкой, чтобы можно было использовать одну для каждого слота в хэш-таблице.
Мне нравится идея arc_swap, но я попробовал бегло просмотреть код, чтобы проверить, соответствует ли он моей ментальной модели, и обнаружил, что он гораздо сложнее, чем я ожидал.
TFA касается параллельных хэш-карт, которые зависают при большой нагрузке чтения, потому что механизмы синхронизации этих хэш-карт вызывают пинг-понг кэша, и исправлением стало использование RCU со структурой данных копирования-при-записи для хэш-карты. Каждая запись требует клонирования предыдущей хэш-карты, но поскольку читатели не выполняют никаких атомарных операций, кроме одного чтения (для текущей хэш-карты только для чтения), все работает, поскольку строкам кэша не приходится пинг-понгить, учитывая, что читатели не пишут.
Все, что касается “debt”, касается дизайна ArcSwap, который использует “debt” вместо “hazard pointers”. Идея в том, что каждый поток отслеживает последнюю версию hashmap, которую он видел, и это “debt” (ссылки, которые в конечном итоге должны быть освобождены), и этот долг является локальным объектом потока, который связан со всеми долгами других потоков, что по сути позволяет собирать мусор “debt” (сбор долгов?) или что-то в этом роде. Смотрите https://github.com/vorner/arc-swap/blob/master/src/docs/inte…
Я сам реализовал нечто подобное. Вместо реализации RCU пользовательского пространства (что, возможно, мне следовало сделать) я реализовал «потокобезопасную переменную», где чтения не требуют блокировок и ожидания, а писатели оплачивают все расходы. Мой API потокобезопасных переменных очень прост и интуитивно понятен: `create(value_destructor) -> thread_safe_var`, `set(thread_safe_var, value)`, `get(thread_safe_var) -> value`, `release(thread_safe_var)` и `destroy(thread_safe_var)` (предположительно, только во время вызова обработчика atexit() или деструктора разделяемого объекта, если вообще есть). У меня есть две реализации: одна со связанным списком указателей опасностей для каждого потока, а другая с кортежем из {следующая/текущая, текущая/предыдущая} «ячеек» и протоколом, который дает читателям время прочитать ячейки, выяснить, какая из них «текущая», а затем разыменовать и увеличить счетчик ссылок.
Независимо от того, как реализовать эту структуру данных, ключевая концепция заключается в том, что вам необходимо атомарно скомпоновать две отдельные атомарные операции: чтение и разыменование для атомарного увеличения счетчика ссылок — это чрезвычайно сложно!
При наличии GC все очень просто: просто читайте — не нужно увеличивать счетчик ссылок.
С помощью связанного списка указателей опасностей для каждого потока все, что вам нужно сделать, это прочитать что-то, затем записать это в ваш локальный указатель опасности потока, затем снова прочитать, повторяя цикл, пока второе чтение не будет таким же, как и первое чтение. Таким образом, безопасное копирование значения в локальный указатель опасности потока читателя позволяет выполнить условную сборку мусора. Любой поток, который хотел бы выпустить старую версию значения, должен проверить все указатели опасности, чтобы убедиться, что оно не используется, и это равносильно небольшой сборке мусора.
Мне особенно нравится подход с указателями опасности.
См. также MVars (Haskell), транзакционная память, RCU и т. д.
> Хотя мы знали, где искать, это расследование уже заняло несколько недель, и ситуация ухудшилась, когда мы снова обратились к этой проблеме 23 февраля.
Меня поражает, что на отслеживание такой проблемы могут уйти недели . Если бы я был на руководящей должности в этой компании, я бы свернул головы с нехваткой телеметрии или знаний в этой области для этих систем.
Не могу сказать, что я удивлен, честно говоря. Я примерно представлял себе, в чем может быть проблема, просто прочитав название поста. Но мне повезло получить степень бакалавра, где параллельность действительно преподавалась, плюс я многому научился за годы работы в высококонкурентных, асинхронных средах.
Параллельное программирование уже давно стало мейнстримом, но я не думаю, что уровень знаний большинства инженеров сохранился. Это становится наиболее очевидным, когда программное обеспечение начинает сталкиваться с подводными камнями параллелизма: проблемами производительности, взаимоблокировками, UAF и т. д.
За свою карьеру мне пришлось иметь дело с двумя большими сбоями, на диагностику и устранение которых ушла неделя. Один из них был связан с моим кодом, хотя условия, вызвавшие его, включали ошибки в чужом коде, взаимодействующие с ошибками в моем, так что по отдельности ни одна из них не вызвала бы сбой. Диагностика первого заняла две недели, и мне пришлось написать специальные инструменты, чтобы помочь диагностировать его. Второй потребовал сбора большого количества данных, проверки кода и выдвижения и проверки множества гипотез. Ни в одном из случаев головы не полетели. Сотрудники, прошедшие через такое испытание огнем, вышли из него еще более ценными, чем прежде, и это касается и тех, чьей «виной» это могло быть.
Иногда вы не можете заранее иметь необходимые знания в предметной области. Причины могут быть самыми разными. Например, рассматриваемое программное обеспечение может быть коммерческим, и у вас может не быть альтернативного поставщика, на которого можно переключиться. В других случаях ваш «коэффициент шины» мог упасть до некомфортно низких значений не по вине кого-либо в организации (люди слишком быстро уходят по причинам, не имеющим никакого отношения к тому, как управляется организация, люди умирают, численность персонала и бюджеты не позволяют исправить ситуацию, и просто слишком много критических систем, чей коэффициент шины нужно постоянно поддерживать на высоком уровне).
Source: news.ycombinator.com