Выход за рамки одномерных, последовательных программ и использование многоядерного мира

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

Введение

Как говорится в лучшей статье ASPLOS ’17:

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

До недавнего времени мощность компьютеров увеличивалась в результате масштабных улучшений одноядерных машин. Границы производительности удваивались каждые два года, и поскольку приложения в то время были недостаточно развиты, чтобы требовать высокопроизводительных вычислений современности, последовательные программы доминировали на уровне приложений. Постепенно классическая форма закона Мура умерла. Чтобы возродить его тенденции, программисты начали распределять свои рабочие нагрузки по синхронизированным ресурсам и по специализированным вычислительным блокам (привет, GPU). Сегодня вычисления больше не определяются одномерными последовательными программами. Вместо этого программное обеспечение расширилось за пределы логики регистров локальной памяти и распространилось на несколько ядер, где они должны соблюдать некоторую форму согласованности и управления при переменных местоположениях и временах в своих параллельных транзакциях.

Наивные методы синхронизации, такие как поэтапная блокировка, обеспечивают упрощенный, но не масштабируемый подход к управлению разделяемой памятью. С другой стороны, мелкозернистые и асинхронные методы могут быть слишком сложными для обычного разработчика. Использование этих ядер имеет решающее значение для формирования основы любой высокопроизводительной вычислительной среды. Но почему бы не использовать всю мощь стандартного оборудования для всех приложений? Будем надеяться, что это тематическое исследование может дать обычным разработчикам новое понимание того, как создавать параллельные системы и анализировать их производительность с точки зрения основных принципов. А для более опытных разработчиков исследование предлагает более строгий подход к блокировке диапазона, который использует базовую эвристику, чтобы преследовать и приближаться к уровню конкуренции при любой искаженной рабочей нагрузке. Если вы все еще читаете, приготовьтесь к долгой поездке.

Формальная аннотация

Следующий отрывок сформирует руководство по развитию и характеристике Ромула:

Ромулус внедряет планировщик в каждую транзакцию, чтобы рассеять конкуренцию между сериями эластичных разделов, синхронизируя эти ячейки с помощью адаптации чтения-копирования-обновления (RCU) и обеспечивая устойчивое состояние выполнения для всех рабочих нагрузок. Вдохновением для разработки Romulus послужил MapReduce: простая структура, которая организует параллельную обработку различных задач, используя глобальное представление о пространстве состояний для распределения и управления коммуникациями между ресурсами. Основная цель Romulus - автоматически преобразовывать любой последовательный API в параллельную структуру данных, приближаясь к производительности созданных вручную современных алгоритмов. Однако его наиболее значительный вклад - это набор эвристик конкуренции, которые предоставляют системам возможность сходиться к целевым уровням конкуренции. Более подробно, Ромулус быстро адаптируется к неравномерным рабочим нагрузкам, используя новую конструкцию блокировки, которая разделяет и объединяет разделы на основе конфликтов потоков в реальном времени. Соответственно, эту методологию можно распространить на другие приложения, в которых ограниченные ресурсы должны адаптироваться в режиме онлайн, поскольку искаженные рабочие нагрузки выходят за пределы их систем. Кроме того, Ромул переносит концепции проектирования баз данных в локальную память, предоставляя алгоритм для эффективных запросов диапазона в упорядоченных хранилищах значений ключей. В целом Romulus представляет алгоритм планирования, который обеспечивает предсказуемый параллелизм с моделью развертывания plug-and-play.

Решения в архитектуре этого планировщика будут определяться тремя фундаментальными целями:

(1) упрощенная методология, расширяемая до любого упорядоченного хранилища ключей и значений, которая также приближается к производительности современных, созданных вручную решений (2) гарантированная сериализуемость для всех операций (включая запросы диапазона)
( 3) предсказуемая конкуренция за счет эвристики коллизий
(4) высокая устойчивость к перекосам рабочих нагрузок

Теоретические основы лотков / шаров

Основная проблема - это проблема планирования: как подключить ввод к справедливому распределению вычислительных ресурсов (по аналогии с MapReduce), нацеленных на заранее определенный уровень конкуренции и масштабируемых с помощью сотен потоков. Аннотация дает намек на то, что Ромул разделит данные на несколько разделов. Таким образом, прежде чем перейти к разработке Ромула, анализ из первых принципов того, сколько перегородок необходимо для нацеливания на частоту столкновений, может (i) внести ясность в отношении равновесия / преследуемого поведения (ii) быстро выявить ожидаемые характеристики. Кроме того, он предоставит (очень свободную) формальную модель для доказательства сходимости разногласий путем сопоставления ожидаемых конфликтов в Ромулусе с измерениями в одном разделе. Как будет показано в следующих разделах, когда потоки определят, что серия этих дискретных измерений нарушает ожидаемый порог для раздела, они разделят раздел на две половины, чтобы рассеять конкуренцию и адаптироваться к асимметричным рабочим нагрузкам. Таким образом, следующий раздел имеет решающее значение для нашей третьей и четвертой целей.

Математический анализ формируется путем вертикального интегрирования предыдущей работы по классической задаче бункеров в шарах: вероятностные результаты для размещения M шаров в N бункеров. Эта модель ранее применялась во многих формах и формах для балансировки нагрузки в информатике.

В самой базовой модели M мячей проходят через случайную функцию, что приводит к равномерному распределению, и помещаются в одну из N ячеек. В следующем разделе основное внимание уделяется пониманию трех важных явлений: (i) вероятность отсутствия столкновений (ii) вероятность наблюдения высоты больше K в одном интервале (iii) вероятность наблюдения высоты больше K во всех N интервалах. Это поможет нам понять, как масштабировать количество разделов по сравнению с потоками.

Случай первый: вероятность отсутствия столкновений

Если мы позволим X представить вероятность того, что никаких столкновений не наблюдается во всех ячейках, и предположим, что M ≤ N, то тривиально M мячей должно быть размещено в N уникальных ячейках. Используя приближение ряда Тейлора и ограничивая его незначительной ошибкой (зная, что u = 1 / N мало), мы оцениваем Pr [X] следующим образом:

Для константы Pr [X] = C видно, что C = O (m² / n); то есть количество бинов должно масштабироваться со скоростью n = O (м²), чтобы поддерживать постоянную вероятность отсутствия коллизий.

Второй случай: столкновения в одном контейнере

Пусть Pr [Xi ≥ K] представляет вероятность того, что не менее K столкновений в одном бине Xi. Это можно представить как:

Для постоянного Pr [xi ≥ K] = C, если N ≥ M, то требуемые ячейки для поддержания постоянной ожидаемой высоты должны масштабироваться при N = O (M). Эта ожидаемая высота остается относительно постоянной для N = M независимо от абсолютного значения входных данных.

Третий случай: K столкновений для N ячеек

Пусть Pr [X ≥ k] представляет вероятность того, что по крайней мере K столкновений произойдет во всех N ячейках. В предположении, что M = O (N) и каждая ячейка независима от других, верхняя граница формируется с помощью правила объединения:

Мы приближаем соотношение между M: N к 1. Хотя это может быть не так в будущем обсуждении, когда M: N = 0,1, верхняя граница все еще будет сохраняться в этом сценарии и обеспечит достаточный контекст для дальнейшего численного анализа. Применяя это соотношение, можно найти, как K изменяется по мере увеличения N (и, следовательно, M) в сторону больших значений:

Почему ожидаемое значение K остается постоянным в одном интервале, но увеличивается для ряда интервалов, когда N и M масштабируются вместе? С логической точки зрения, поскольку мы увеличиваем количество возможностей возникновения отклонений, мы увеличиваем вероятность того, что K выйдет далеко за пределы ожидаемой высоты в любом отдельном ведре.

Исход

Эти выводы важны для трех ожиданий от Ромула:

(i) Чтобы поддерживать постоянную вероятность отсутствия конфликтов, нужно масштабировать количество ячеек экспоненциально по отношению к количеству шаров со скоростью N = O (M²). Ромул не будет следовать этому подходу, поскольку он неосуществим для большого количества потоков, и поэтому планировщик не будет пытаться удалить все конфликты.

(ii) Если количество ящиков линейно масштабируется в зависимости от количества шаров, ожидаемая средняя высота шаров в каждой ячейке остается постоянной. Хотя для больших значений N и M конфликты в любой дискретный момент времени могут быть выше в горячих точках из-за характера дисперсии. Обратите внимание, что Ромул будет следовать этой модели, и поэтому он будет пытаться поддерживать целевой уровень конфликтов.

(iii) При построении обзора всей системы из отдельной корзины можно создать доверительный интервал о состоянии системы, предполагая равномерную рабочую нагрузку. Более конкретно, измеряя K (то есть высоту очереди шаров) на одном бункере, можно определить, постоянно ли его значение нарушает порог и превышает вероятность. Если это так, планировщик должен спрогнозировать, что перекошенная рабочая нагрузка выходит за пределы системы и нарушает предположение о равномерном распределении.

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

Числовой анализ

Давайте переведем это старое представление в новое представление потоков, выполняющих операции обновления для бункеров.

В следующем разделе подтверждаются теоретические тенденции проблемы бункеров в шары в теоретическом контексте, когда потоки выполняют операции обновления в серии разделов, и выявляются два очевидных явления блокировок в параллельных средах: (1) сокращение разделов блокировок в сторону более точных; гранулированные диапазоны (т.е. увеличение количества ячеек) в результате приводит к уменьшению отдачи от рассеивания конкуренции (2), наиболее оптимальная теоретическая конфигурация при неограниченных ресурсах заключается в максимальном увеличении количества блокировок в минимально возможном разделе. Однако во многих случаях системы могут расходовать лишь небольшое количество ресурсов. Соответственно, блокировки диапазона используются для обеспечения приличного параллелизма без дополнительных затрат памяти, связанных с 40-байтовым pthread_lock_t. Но что наиболее важно, поскольку сокращение разделов блокировок в сторону более детализированных диапазонов дает меньшую отдачу, Ромул теоретически может использовать на порядок меньше блокировок, при этом во многих сценариях все еще приближаясь к ручной работе. < br />
Чтобы смоделировать классические бины в шарики, мы формируем понятие блокировки дальности; существует таблица блокировок из N ячеек, представляющая серию из N абстрактных разделов, которая не зависит от фактического размера нижележащего уровня хранения. Количество потоков представляет собой количество шариков, и они работают через эти разделы с мгновенными вставками / удалениями. Чтобы наблюдать за конфликтами сверхурочно, мы моделируем бесконечную итеративную игру следующим образом:

1) В начале игры потоки случайным образом помещаются в раздел / корзину (т. Е. Блокируются)

2) У каждого раздела есть очередь операций, ожидающих завершения. В каждом раунде игры поток действует как параллельный агент в системе. Все потоки в начале очереди удаляются, перерабатывая себя в другой раздел. Они выбирают следующий раздел, следуя генерации случайных чисел с равномерным распределением. Это представляет поток, который получает право владения разделом, выполняет операцию, освобождает область и переходит к следующей операции. Все потоки, не находящиеся в начале очереди (т.е. позади других в очереди), не выполняют никаких действий и вместо этого ждут, пока они не переместятся в начало очереди в будущих раундах.

3) Игра повторяется вечно, как в реальной системе

Эта модель имеет ряд важных допущений, в первую очередь: все операции выполняются мгновенно и выполняются один раз за раунд, рабочая нагрузка имеет равномерное распределение, а вариативность доступа к памяти, межпотокового взаимодействия и других накладных расходов, связанных с архитектурой, устранена. . Конечно, у реальных систем есть ограничения ресурсов, такие как память и ввод-вывод, которые могут изменить уравнение ценности. Однако, как показывают будущие испытательные стенды, общие тенденции остаются прежними и создают основу для анализа. Эксперименты проводились на Python с раундами 10, 100 и 1 млн. Независимо от продолжительности игры результаты сходились к одним и тем же значениям.

Два рисунка слева изображают высоту очередей для каждого раунда игры в двух крайних условиях, в надежде предоставить качественную иллюстрацию вариации конфликтов в средах с высоким и низким уровнем конкуренции. Первое изображение представляет собой игру с 64 потоками против 48 разделов. Второе изображение представляет игру с 64 потоками против 640 разделов.

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

На этом рисунке мы нацелены на среднюю высоту 1,05 для активных очередей и наносим на график количество разделов, необходимых для достижения этой высоты при различных скоростях потоков. Это рассчитывается путем проведения ряда игр с постоянными 100 000 раундов и определения ближайшего количества разделов, которые создают надлежащую среднюю высоту. Цель этого эксперимента - понять, как сохранить целевой уровень конкуренции между потоками; из результатов и предшествующего анализа подтверждается, что необходимо масштабировать количество разделов как линейную функцию количества потоков для M / N ‹1.

На этом рисунке мы повторяем этот момент и выражаем среднюю высоту как функцию количества потоков, предполагая количество разделов в 10 * потоков. Оптимальное количество блокировок (размер базовой структуры, представленной как 1M) включено, чтобы продемонстрировать последовательную разницу в двух подходах.

Наконец, этот последний эксперимент иллюстрирует убывающую пользу увеличения разделов для рассеивания конкуренции. С логической точки зрения в этом есть смысл. С одним контейнером и 64 шарами в одном контейнере находится 64 шара. При увеличении до двух ящиков шары разделяются равномерно, и средняя высота увеличивается до 32. С четырьмя ячейками шары снова делятся равномерно, но только уменьшают объем с 32 до 16 ячеек. Соответственно, предельный объем от разделения со временем продолжает уменьшаться.

Эти графики раскрывают важные ожидания в отношении первых принципов планирования конкуренции в Ромуле. Прежде всего, Ромул теоретически никогда не сможет превзойти созданный вручную аналог в классических рабочих нагрузках чтения / записи, который проявляет две характеристики: (1) обход без ожидания (2) одна блокировка для каждого элемента (3) стоимость поиска, эквивалентная слой перевода. Это потому, что Ромул не пытается устранить все противоречия в своей системе; он до некоторой степени ограничивает параллелизм в отношении владения рядом элементов, распределяя поэтапные блокировки по меньшим разделам. Как следствие, он будет страдать от большего числа конфликтов, что приведет к снижению производительности конфликтующих потоков на порядок. Однако на практике количество диапазонов, необходимых для достижения разумного уровня параллелизма, будет на порядок меньше, чем количество элементов (при условии 10 * потоков ‹

Назад к проектированию Ромула: методология

Romulus представит планировщик, который разбивает абстрактную структуру данных на ряд эластичных разделов. Бункеры не привязаны к какому-либо размеру, а скорее адаптируются на лету к неравным силам со стороны потоков приложений. Для упорядоченных хранилищ ключей и значений эти разделы представляют собой диапазон ключей. Предположим далее, что программист всегда предоставляет API для упорядоченных хранилищ ключей и значений.

Для формирования Ромула необходимы три важных уровня: адаптируемый уровень перевода, уровень данных и уровень синхронизации. На уровне трансляции алгоритм должен создать правильный раздел для данного входного ключа. Тем не менее, он не должен представлять статический набор диапазонов, подобных хеш-карте, поскольку нужно рефлексивно изменять разделы, чтобы сгладить искаженные входные данные. На уровне данных программист предоставляет абстрактный API для добавления, содержания и удаления для хранения и доступа к элементу. Уровень синхронизации обеспечивает строгую сериализуемость операций и часто интегрируется через уровень трансляции и уровень данных; это важно для создания изоляции и других гарантий сериализуемости в каждом разделе. Для методологии, изображенной на рисунке, мы используем чтение-копирование-обновление (RCU) и создаем две копии данных. Представление писателей (активный раздел данных) - это пространство состояний, в котором писатели могут выполнять операции обновления изолированно и требуют блокировки для взаимного исключения. Представление читателей (реплика раздела данных) позволяет читателям без ожидания проходить через систему. Соответственно, разногласия в Ромулусе возникают только из-за того, что потоки писателей обновляют разделы. Полный круг, вот почему мы не включили читателей в приведенный выше численный анализ.

Методология Ромула предлагает множество вариантов для своей конкретной реализации; то есть его можно рассматривать как абстрактный и модульный подход к параллелизму (но он больше всего подходит для упорядоченных хранилищ ключей и значений). Следовательно, приведенные ниже алгоритмы сфокусированы на оптимизации производительности с точки зрения программиста, хотя многие другие адаптации все еще существуют и обеспечивают правильную семантику. Прежде чем определять конкретную реализацию Ромула, алгоритм планирования должен сначала применить принципы предварительного анализа конкуренции, чтобы решить, как первоначально разделить диапазоны и решить для порога, который позволяет Ромулу на лету адаптироваться к искаженным входным данным.

Применение эвристики конкуренции

В Ромулусе искаженное распределение входных данных можно охарактеризовать как неравное взвешивание входных операций, которые приводят к конфликту. Это означает, что перекос формируется в результате двух явлений: (i) операций с разными весами (ii) неравномерного распределения доступа. При разделении диапазонов, основанном на нарушении эвристики разногласий, методология Ромула не зависит от причины перекоса и просто действует как рефлексивная сила.

Чтобы достичь средней высоты 1,05 в очередях блокировок (теоретически), система разбивается на 10 * t разделов, где t - количество потоков в приложении (на практике это доказало свою эффективность, хотя константа будет смещаться в зависимости от специфика машины). Во время выполнения Ромул следует двум простым эвристикам для разделения / объединения диапазонов:

(1) если потоки приложений измеряют конкуренцию выше порогового значения K, они разбивают диапазон на два новых раздела перед применением операции обновления. K определяется путем применения 95-процентного доверительного интервала к предыдущему теоретическому анализу и нового предположения, что N = 10 * M, где N = количество разделов, а M = количество потоков:

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

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

Реализация Ромула

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

Слой перевода реализован в виде настраиваемого хэш-дерева. Уровень дерева, для которого поток будет хешировать, является самым нижним уровнем с полным набором внутренних разделов.

Уровень данных - это упорядоченное хранилище ключей и значений; требование для эффективной поддержки запросов диапазона.

Уровень синхронизации использует настраиваемую адаптацию RCU, особенно в протоколе фиксации, для оптимизации для считывателей как в запросах диапазона, так и в операциях с одним элементом. Уровень синхронизации перетекает в уровень трансляции, где хранится атомарный счетчик, чтобы сигнализировать потокам записи количество запросов диапазона, выполняющих диапазон разделов. В абстрактных требованиях Ромула верхнее дерево на уровне перевода, построенное вверх из набора разделов, не требуется. Однако для синхронизации запросов диапазона между разделами эта модель расширяет требования Romulus и формирует верхний уровень, называемый CRRQS (запросы диапазона между регионами). В следующих разделах подробно рассматриваются важные аспекты каждого из этих уровней, начиная с требований рабочих нагрузок и последствий, лежащих в глубине стека.

Массовые операции (запросы диапазона)

Чтобы предоставить сериализуемые запросы диапазона, Romulus использует концепции из баз данных, интегрируя синхронизацию с множественной гранулярностью. Существует два крайних подхода к оптимизации: запросы диапазона на основе блокировки и запросы диапазона без блокировки. Для запросов большого диапазона по множеству отдельных разделов реализация на основе блокировок приведет к значительному снижению производительности, в то же время обеспечивая возможность справедливости для различных типов операций. Например, система могла бы реализовать блокировку чтения-записи в активном разделе, блокируя выполнение обновлений до завершения их операции. Накладные расходы на получение серии этих блокировок слишком высоки для практического применения. В результате в начале эксперимента Ромул строит верхний слой дерева поверх разделов, в котором представлена ​​степень детализации диапазонов для синхронизации. Когда запрос диапазона хочет работать с диапазоном, он ищет от корня верхнего слоя дерева вниз, пока не найдет наименьший диапазон, который соответствует его границам. После этого запрос диапазона атомарно увеличивает счетчик в узле и переходит к выполнению своей операции. Это сигнализирует всем другим агентам в системе, что выполняется запрос диапазона, синхронизируя эти операции в безблокировочном механизме с постоянной стоимостью путем централизации необходимого состояния в одном месте. Последствия для потоков записи при фиксации своих операций обсуждаются ниже. Тем не менее, два дополнительных аспекта для диапазона потоков запросов заключаются в том, что они должны читать глобальную эпоху, указывающую метку времени в начале своей операции, и они должны использовать эту метку времени, чтобы указать, обновлять ли свой результат самой последней операцией на перегородка. Однако это требование имеет постоянную стоимость и не оказывает существенного влияния на большие запросы.

RCU

Использование чтения-копирования-обновления (RCU) в качестве механизма синхронизации в Romulus имеет критические эффекты второго порядка. Во-первых, он позволяет выполнять операции чтения для доступа к разделам без блокировки. Во-вторых, это требует дополнительных накладных расходов как на пространство для хранения, так и на операции. Раздел на уровне перевода Ромула представлен следующими метаданными (за исключением указателей на левый и правый дочерние элементы в дереве):

В результате планировщик копирует данные в две структуры, называемые репликой и активной. Указатель реплики обеспечивает запись для потоков чтения на нижележащий уровень хранения, в то время как активный указатель обеспечивает запись для потоков записи на другой уровень. В классическом алгоритме RCU можно скопировать имеющуюся память в локальный адрес потока и выполнять операции изолированно перед фиксацией. В этой реализации данные уже предоставлены, чтобы избежать затрат как на хранение, так и на вычисления из-за копирования большого диапазона памяти при каждом обновлении. Вместо этого, чтобы сохранить сериализуемость операций, поток записи следует другой последовательности действий. Во-первых, поток записи получает право владения разделом через настраиваемый мьютекс. Этот мьютекс содержит «недопустимое» состояние, которое указывает, что операция слияния / разделения произошла ранее, а также количество писателей, борющихся за блокировку. Предполагая, что ничто не было признано недействительным и не требуется слияние / разделение, поток записи выполняет операцию обновления активной структуры данных. После этого, если и только если это допустимо для фиксации операции, поток записи выполняет атомарное сравнение и замену (CAS), чтобы заменить указатель реплики новым состоянием. Это представляет собой точку линеаризации операции обновления. Поскольку планировщику известен результат операции обновления активной структуры, тогда и только тогда, когда операция вернула истину (т.е. успешно обновила элемент), поток будет ждать, пока все потоки считывателя покинут старую реплику, а затем обновит ее устаревшую структуру. в новое состояние при выполнении той же операции. По завершении поток завершает репликацию двух разделов в более новую версию и снимает блокировку. Одним из критических моментов в операции RCU является определение допустимости фиксации операции. В классическом алгоритме RCU потоку записи не нужно ждать фиксации других агентов в системе. Вместо этого операция фиксации выполняется неблокирующим образом. Когда разрешены запросы диапазона, Romulus, поток записи должен убедиться, что он не выполняет операцию обновления, в то время как он считает, что запрос диапазона может работать с его разделом. Чтобы определить, зависит ли запрос диапазона от раздела, средство записи проходит вверх через уровень перевода и проверяет, что у каждого родителя нет запросов диапазона, выполняющихся следующим образом:

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

Есть тривиальное решение проблемы. Перед фиксацией обновления запрос диапазона запишет операцию в MRO раздела с соответствующей глобальной меткой времени. После того, как запрос диапазона записывает свои операции чтения для раздела, он проверяет метку времени. Если будет видно, что метка времени узла не соответствует метке запроса диапазона, то он отменит самую последнюю операцию в своей локальной записи. Следовательно, в запросе диапазона либо не будет конфликтующего обновления, либо он сможет разрешить его без особых накладных расходов. Важно отметить, что при тех же условиях, что и выше, если другой поток записи желает обновить этот раздел, он не будет выполнять другую операцию (которая переопределит MRO), пока не завершится запрос диапазона, поскольку он обязательно увидит сигнал запроса диапазона в обновленная версия пути. Следовательно, можно сказать, что поток записи всегда будет откладывать себя до тех пор, пока в MRO больше не будет необходимости, и он может заменить MRO без дальнейших последствий. Несомненно, приведенная выше реализация оптимизирована для экспериментов с интенсивным чтением, когда запросы диапазона выполняются в серии секций. Запись не только занимает больше времени, чтобы зафиксировать свою операцию, проходя путь от листа до корня, но также может не хватать времени, потому что они блокируют запросы диапазона.

Хеш-дерево

Хеш-дерево представляет собой уровень трансляции в Ромулусе: при наличии ключа ввода оно обеспечивает раздел, в котором этот ключ хранится. Для операции чтения / записи планировщик сначала хеширует ключ, чтобы предоставить потоку начальный начальный уровень для перехода. Расположение хэш-уровня влияет не на правильность, а на производительность и надеется снизить стоимость поиска на уровне перевода, начав с более низкого узла. Отсюда поток должен искать вниз, пока не достигнет листового узла, соответствующего разделу, содержащему его ключ. Листья представляют уровень данных и содержат правильные указатели на структуры; они также связаны, чтобы разрешить линейное продолжение запросов диапазона между секциями. Операции чтения входят в реплику без блокировки, в то время как средства записи следуют пользовательскому алгоритму RCU, описанному выше. Однако перед установкой блокировки писатели увеличивают переменную, которая представляет количество конфликтов записи в разделе.

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

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

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

Слияние / разделение

В последние годы была проделана большая работа по разработке операций слияния / разделения для общих структур данных. Пропускные списки, красно-черные деревья, связанные списки и многие другие структуры могут выполнять операцию разделения с той же временной сложностью, что и их операции поиска. В результате, когда программист предоставляет реализацию fork (K) с этим предположением, операция разделения в Romulus алгоритмически удваивает количество времени для одного из потоков, чтобы завершить свою операцию обновления (за исключением наличия запросов диапазона). Реализация, представленная выше для слияния / разделения, использует потоки приложений для идентификации самих конфликтов и выполнения операций в пределах своего критического пути с помощью синхронного подхода. Это создает в алгоритме риск неправильной классификации горячих точек и требует точной пороговой модели для измерения. Кто-то может возразить, что переложение этой работы на фоновый поток может иметь смысл; однако дальнейший анализ показывает иное. Асинхронная ленивая реакция на конкуренцию через вспомогательный поток может помочь системе достичь устойчивого состояния с полной точностью, но время и сложность определения горячих точек для больших структур данных с помощью одного вспомогательного потока не позволят немедленно устранить перекос рабочих нагрузок. Сказка об игле в стоге сена. В результате параллелизм этих потоков значительно снизится из-за постоянных конфликтов. Соответственно, в большинстве случаев время на разрешение, вероятно, будет стоить больше, чем сами потоки приложения, обрабатывающие разделение. Кроме того, более важным моментом является то, что если перекос продолжает смещаться, то асинхронный поток, вероятно, получит искаженное представление о конфликтах и, возможно, никогда не устранит динамические перекосы. Это распространяется на более общую проблему асинхронной оценки в том, что приближение конкуренции становится намного сложнее моделировать для динамических систем. Такое пренебрежение перекосом рабочих нагрузок может привести к катастрофе для систем, требующих устойчивости в различных сценариях, и, следовательно, помешать массовому внедрению Ромулуса.

Прочие примечания

Форма слоя трансляции отражает искаженные распределения, проходящие через Ромула, как видно на предыдущих рисунках и в будущем анализе; то есть для горячих точек, в которых часто возникают конфликты, Ромул углубит уровень трансляции, чтобы рассеять конкуренцию на большем количестве диапазонов. Интересный вопрос, который следует рассмотреть, - сходится ли уровень трансляции Ромула к устойчивому состоянию при асимметричном распределении. Очень общий формальный анализ и экспериментальные результаты доказывают, что Romulus действительно сходится к устойчивому состоянию при асимметричном распределении, и делает это быстро, проактивно адаптируясь к конфликту через сами потоки приложений, находящиеся в конфликте. Таким образом, Ромул будет добиваться последовательного поведения на уровне перевода, пока новый перекос не выйдет за пределы системы и не вызовет обновление разделов.

Один из аспектов онлайн-систем, который часто снижает производительность, - это процесс восстановления памяти: безопасное освобождение памяти для повторного использования. У Ромула уже есть накладные расходы на восстановление памяти, встроенные в его изоляцию раздела; то есть не нужно добавлять какие-либо новые метаданные к Ромулу, чтобы защитить освобождение памяти. Кроме того, память может быть освобождена синхронно, а не асинхронно (общий подход, который откладывает восстановление до тех пор, пока другие потоки не смогут продолжить путь к списанному элементу)

Результаты

Как алгоритм планирования, общие тенденции производительности в Romulus должны быть известны заранее:
(1) без других узких мест, таких как память, Romulus будет хорошо масштабироваться для большего количества потоков от однопоточной базовой линии
(2) искаженные исходные данные будут решены быстро, и разногласия снизятся до прежних уровней

Это подтверждается приведенными ниже графиками и анализом. С другой стороны, относительную эффективность по сравнению с конкурентами и крайними случаями трудно определить количественно; нужно следить за процессом открытия. Чтобы получить точное представление о производительности Ромула, следует развернуть последовательный список пропусков и сравнить его с двумя современными решениями, созданными вручную, одновременно с решениями списков пропуска: NUMASK и Herihly. Они представляют собой две из самых быстрых структур без блокировки и структуры на основе блокировки соответственно (по крайней мере, на данный момент). Стенд для тестирования, использованный в следующем эксперименте, состоит из сервера с 4 процессорами Intel Xeon Platinum 8160, обеспечивающими в общей сложности 192 потока. Есть 4 сокета, на которых размещаются 4 процессора через 4 зоны NUMA (один к одному) и 768 ГБ памяти. Все числа представляют собой среднее значение десяти испытаний. В экспериментах потоки приложений равномерно распределяются по зонам NUMA. Примечание: конкуренты не предоставляют решения для запроса сериализуемого диапазона, и поэтому мы сравниваем их с их верхней границей, поскольку они небезопасно пересекают структуру и представляют устаревшие результаты в своих массовых операциях. Тем не менее, с 10% -ными запросами диапазона 500 предполагаемых элементов, 70% -ными операциями чтения и 20% -ыми операциями обновления для структуры данных размером 2 миллиона, можно наблюдать следующую производительность:

Структура хорошо масштабируется относительно верхних границ производительности решений, созданных вручную, до 60 потоков. Тем не менее, Romulus невероятно хорош для ускорителя plug-and-play. Одна область, в которой она превзойдет репликацию узлов (признанная лучшей статьей ASPLOS ’17, источник цитаты с самого начала), - это их упорядоченные хранилища ключей и значений; тем не менее, он будет хуже в стеках / очередях / других структурах, где операции появляются исключительно с передней и задней стороны структур - там, где они нашли свое золотое место.

Сравнительный анализ связанных списков - интересный, но недействительный эксперимент, учитывая, что снижение стоимости поиска за счет превосходной алгоритмической производительности уровня перевода приводит к сверхлинейному ускорению.

Теперь, когда мы знаем, что приближаемся к производительности вручную созданных подходов в Skip Lists, остальные утверждения Ромула должны быть исследованы на предмет имеющейся структуры данных; в частности, (i) насколько хорошо Ромул работает при искаженном распределении? (ii) как различные сегменты влияют на производительность обновления / RQ?

Двумя наиболее важными измерениями в определении успеха алгоритма слияния / разделения являются то, насколько быстро он адаптируется к конфликту (то есть время до разрешения) и общее влияние на производительность по сравнению с равномерным распределением. Ромул хорошо показывает себя в обоих отношениях. На следующем графике делается снимок пропускной способности за каждую миллисекунду эксперимента, чтобы получить представление о пропускной способности в зависимости от времени. Потоки приложения вводят асимметричное распределение примерно через 5 секунд, чтобы наблюдать, как (1) Romulus адаптируется к рабочей нагрузке с использованием операций вилки / слияния (2) выигрыш в производительности по сравнению с наивной версией Romulus, где вилка / слияние не используется

Это подтверждает, что даже несмотря на то, что Ромул жертвует краткосрочной производительностью в течение нескольких миллисекунд, долгосрочная производительность системы быстро возвращается к предыдущим уровням из-за имеющегося перекоса.

Рефлексивный характер системы для той же рабочей нагрузки можно изобразить, просмотрев три распределения доступа в листовых узлах Ромула в конце эксперимента. На следующем графике изображены (1) входной перекос (то есть распределение доступа без разветвления / слияния) (2) экспериментальный результат (то есть распределение доступа с включенным разветвлением / слиянием) с 48 потоками и 100% операциями обновления размером 2 миллиона, и (3) целевой теоретический результат этого эксперимента с учетом набора эвристик, с помощью которых Ромул развертывается (K = 3). Он делает это, глядя на процент доступа (наблюдаемые доступы в отдельном разделе / ​​общее количество доступов по разделу) для каждого раздела.

Ромул падает ниже теоретической цели и имеет больше накладных расходов по количеству разделов, чем ожидалось, скорее всего, из-за ослабленной эвристики конкуренции, которая является пессимистической (K = 3). Четко определенный порог с надежными гарантиями критически важен для Ромула, чтобы приблизиться к целевому состоянию окончательного равновесия перегородок. Слишком высокий порог - и эвристика не сможет правильно адаптироваться к искаженным рабочим нагрузкам. Слишком низкое пороговое значение, и система расходует ресурсы сверх первоначальной цели и неправильно классифицирует входное распределение.

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

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

//