Технологии мирового класса сочетаются с передовыми исследованиями в Aptos. Для получения более подробной информации см. документ Block-STM и кодовую базу Aptos .

Александр Шпигельман и Рати Гелашвили

TL;DR: мы разработали и внедрили высокоэффективный многопоточный механизм параллельного выполнения в памяти, который может выполнять более 160 000 нетривиальных транзакций Move в секунду, используя предустановленный порядок транзакций и сочетая методы программной транзакционной памяти с новым совместный график.

Соревнование

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

Цель

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

СТМ-подход

Академический подход, впервые предложенный библиотеками Software Transactional Memory (STM) , заключается в использовании доступа к памяти для обнаружения и управления конфликтами. Библиотеки STM с оптимистичным параллелизмом контролируют доступ к памяти во время выполнения, проверяют каждую транзакцию после выполнения и прерывают и повторно выполняют транзакции, когда проверка обнаруживает конфликт. Однако из-за обязательного учета конфликтов и прерываний библиотеки STM часто страдают от ограничений производительности по сравнению с специализированными решениями и поэтому редко развертываются в производстве.

Пример использования блокчейна

В прошлом было показано, что производительность STM может быть значительно увеличена, если они применяются к конкретным вариантам использования. Действительно, при разработке Block-STM руководствуются тремя важными наблюдениями, которые относятся к варианту использования блокчейна.

Нет необходимости совершать транзакции по отдельности: в отличие от STM общего назначения (где каждый поток имеет бесконечный поток транзакций для фиксации на основе запросов, которые могут поступать в произвольное время), в блокчейнах состояние обычно обновляется для каждого блока. Это позволяет Block-STM избежать затрат на синхронизацию при индивидуальном совершении транзакций. Вместо этого Block-STM лениво фиксирует все транзакции в блоке с легкой синхронизацией. Кроме того, сборка мусора проста, так как память может быть очищена между блоками.
Виртуальная машина обеспечивает безопасность для оптимального доступа к памяти: транзакции задаются на языках смарт-контрактов, таких как Move и Solidity , и выполняются в виртуальной машине, которая инкапсулирует их выполнение и обеспечивает безопасное поведение. Это хорошо разделяет абстракции и позволяет Block-STM избежать обработки последствий несогласованных состояний во время параллельного спекулятивного выполнения (свойство, известное как непрозрачность).
Предопределенный порядок снижает синхронизацию: в общем, библиотеки STM нацелены на недетерминизм и рассматривают детерминизм как ограничение системы, снижающее производительность. Это делает их непригодными для варианта использования блокчейна, поскольку валидаторы, выполняющие один и тот же блок, могут привести к разным конечным состояниям. Однако в Block-STM детерминизм считается преимуществом производительности. На самом деле конечный результат гарантированно соответствует последовательному выполнению транзакций в фиксированном заранее заданном порядке, и это ограничение используется в интересах системы. Это возможно, как ранее отмечалось в работе Бома .paper в контексте баз данных, поскольку согласование конкретной сериализации снижает объем синхронизации, необходимой во время выполнения. Например, если есть конфликт между транзакцией tx5 и транзакцией tx9, то tx9 будет ждать tx5 — в противном случае, без порядка, потоки, выполняющие эти транзакции, должны были бы разорвать связь. Таким образом, на интуитивном уровне, где STM общего назначения решал бы более сложную проблему (т. е. форму консенсуса), Block-STM нацелен на более простую проблему (т. е. ему нужно только выполнять транзакции).

Основные методы

Block-STM сочетает в себе известные методы с новыми идеями:

Оптимистичный контроль параллелизма: транзакции выполняются оптимистично параллельно и проверяются после выполнения. Неудачные проверки приводят к повторному выполнению. Из-за предустановленного порядка проверки не являются независимыми друг от друга и должны логически происходить в последовательности. В отличие от предыдущей работы, успешная проверка не означает, что транзакция может быть зафиксирована. Напротив, неудачная проверка транзакции означает, что все более высокие транзакции могут быть зафиксированы только в том случае, если они впоследствии будут успешно проверены.
Структура данных с несколькими версиями: Block-STM использует структуру данных с несколькими версиями, чтобы избежать конфликтов записи и записи. Все операции записи в одно и то же место хранятся вместе с их версиями, которые содержат идентификаторы транзакций и количество раз, когда транзакция записи оптимистично выполнялась повторно. Когда транзакция tx считывает ячейку памяти, она получает из многоверсионной структуры данных значение, записанное в эту ячейку самой высокой транзакцией, которая появляется перед tx в заданном порядке, вместе со связанной версией.
Проверка: во время выполнения транзакции записывают набор для чтения и набор для записи . Во время проверки все ячейки памяти в наборе для чтения считываются, а возвращенные версии сравниваются с соответствующими версиями, хранящимися в наборе для чтения.
Совместный график:Block-STM представляет совместный планировщик для координации задач проверки и выполнения между потоками. Поскольку предустановленный порядок требует, чтобы транзакции были зафиксированы по порядку, успешная проверка выполнения транзакции не гарантирует, что она может быть зафиксирована. Это связано с тем, что прерывание и повторное выполнение более ранней транзакции в блоке может сделать недействительным набор чтения и потребовать повторного выполнения. Следовательно, статическое сопоставление между транзакциями и выполняющимися потоками не работает. Вместо этого совместный планировщик отдает приоритет задачам выполнения и проверки более низких транзакций. Однако известно, что упорядоченные наборы и очереди с приоритетами сложно масштабировать в многоядерных средах. Block-STM обходит эту проблему, используя подход, основанный на подсчете.
Оценка динамической зависимости: Block-STMиспользует предустановленный порядок, чтобы значительно избежать прерываний, что является названием игры производительности для систем STM, поскольку прерывания могут каскадироваться и приводить к чрезмерному количеству напрасной работы. Когда проверка не пройдена, набор записей последнего выполнения транзакции используется для оценки зависимостей, помечая все записи в многоверсионной структуре данных как ESTIMATION. Когда другая транзакция считывает значение ESTIMATION из многозначной структуры данных, она может затем дождаться разрешения зависимости — в то время как без оценки она продолжалась бы, но весьма вероятно (если транзакция, записавшая ESTIMATION, действительно записывает в ту же самую структуру данных). местоположение при следующем повторном выполнении), чтобы позже не пройти проверку и быть прерванным.

Оценка

Мы реализовали Block-STM в безопасном Rust в кодовой базе Aptos с открытым исходным кодом, полагаясь на крейты Rayon, Dashmap и ArcSwap для параллелизма. Мы оценили систему с помощью нетривиальных одноранговых транзакций Move (8 операций чтения и 5 операций записи). На графике ниже мы сравниваем Block-STM с последовательным выполнением блока. Каждый блок содержит 10 000 транзакций, а количество учетных записей определяет уровень конфликтов и разногласий. При низкой конкуренции архивы Block STM ускоряются в 16 раз по сравнению с последовательным выполнением с 32 потоками, а при высокой конкуренции архивы Block-STM ускоряются более чем в 8 раз. Важно отметить, что Block-STM несет небольшие накладные расходы, когда рабочая нагрузка по своей сути является последовательной. В целом, Block-STM способен динамически и прозрачно (без каких-либо подсказок со стороны пользователя) извлекать присущий ему параллелизм из рабочей нагрузки. Подробные сравнения с родственными работами можно найти в статье .

Блокировка производительности STM с различными уровнями конкуренции

Итак, как мы можем получить эту производительность?

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

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

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

Эффективный параллельный упорядоченный набор

Вместо этого Block-STM использует предустановленный порядок транзакций и использует два атомарных счетчика.

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

Возможные статусы транзакции представлены на диаграмме ниже. Параметр i на следующей диаграмме — это количество раз, когда транзакция выполнялась повторно.

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

Ленивый механизм фиксации

Block-STM фиксирует весь блок, чтобы исключить затраты на отслеживание синхронизации, когда отдельные транзакции могут быть безопасно зафиксированы. Короче говоря, весь блок может быть зафиксирован, когда выполняются все следующие условия:

Индексы выполнения и проверки достигают размера блока.
Нет текущих задач проверки и выполнения.
Статусы всех транзакций ВЫПОЛНЕНЫ.

Как мы доказываем в нашем доказательстве #слишком-строгих-для-систем-результатов , первые два условия в алгоритме Block-STM подразумевают третье. Для атомарной проверки (1) и (2) мы ввели два дополнительных счетчика. Первый счетчик отслеживает количество текущих задач. Слишком легко увеличить или уменьшить этот счетчик в неправильном месте кода и никогда не соблюсти (2). Чтобы избежать таких ошибок, мы использовали шаблон Resource Acquisition Is Initialization (RAII), чтобы связать счетчик с охранниками задач, гарантируя, что они увеличиваются и уменьшаются до отправки задачи и после ее завершения соответственно.

Для атомарного считывания этого счетчика вместе со счетчиками, которые отслеживают индексы выполнения и проверки, мы используем метод двойного сбора. Это требует введения четвертого атомарного счетчика для отслеживания количества раз, когда счетчики выполнения и проверки были уменьшены. Затем два раза собираем значения всех счетчиков (порядок важен!) и если в обоих случаях выполняются условия (1) и (2), то (как мы доказываем) в какой-то момент между ними выполняются условия (1) и (2) действительно были одновременно удовлетворены. В этом случае весь блок безопасно фиксируется, так как больше никаких задач проверки и выполнения не требуется и не будет создано.

Если вы, как и мы, увлечены разработкой алгоритмов, их применением на практике и реальным влиянием на будущее Web3, свяжитесь с нами — мы нанимаем в Aptos