stringtranslate.com

Управление параллелизмом

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

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

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

Управление параллелизмом в базах данных

Комментарии:

  1. Этот раздел применим ко всем транзакционным системам, т. е. ко всем системам, которые используют транзакции баз данных ( атомарные транзакции ; например, транзакционные объекты в управлении системами и в сетях смартфонов , которые обычно реализуют частные, выделенные системы баз данных), а не только базы данных общего назначения. системы управления (СУБД).
  2. СУБД также должны решать проблемы управления параллелизмом, характерные не только для транзакций баз данных, но и для операционных систем в целом. Эти проблемы (например, см. раздел «Управление параллелизмом в операционных системах» ниже) выходят за рамки данного раздела.

Управление параллелизмом в системах управления базами данных (СУБД; например, Bernstein et al. 1987, Weikum and Vossen 2001), других транзакционных объектах и ​​связанных с ними распределенных приложениях (например, Grid-вычислениях и облачных вычислениях ) гарантирует, что транзакции базы данных выполняются одновременно , не нарушая целостность данных соответствующих баз данных . Таким образом, управление параллелизмом является важным элементом корректности в любой системе, где две или более транзакции базы данных, выполняемые с перекрытием во времени, могут получить доступ к одним и тем же данным, например, практически в любой системе баз данных общего назначения. Следовательно, с момента появления систем баз данных в начале 1970-х годов было накоплено огромное количество соответствующих исследований. Хорошо зарекомендовавшая себя теория управления параллелизмом для систем баз данных изложена в упомянутых выше ссылках: теория сериализуемости , которая позволяет эффективно разрабатывать и анализировать методы и механизмы управления параллелизмом. Альтернативная теория параллельного управления атомарными транзакциями над абстрактными типами данных представлена ​​в (Lynch et al. 1993) и ниже не используется. Эта теория более совершенна, сложна, имеет более широкую сферу применения и реже используется в литературе по базам данных, чем классическая теория, описанная выше. Каждая теория имеет свои плюсы и минусы, акценты и понимание . В некоторой степени они дополняют друг друга, и их объединение может быть полезным.

Чтобы гарантировать корректность, СУБД обычно гарантирует, что генерируются только сериализуемые расписания транзакций , если только сериализуемость не ослабляется намеренно для повышения производительности, но только в тех случаях, когда корректность приложения не страдает. Для обеспечения корректности в случаях неудачных (прерванных) транзакций (которые всегда могут произойти по многим причинам) расписания также должны иметь свойство восстанавливаемости (после прерывания). СУБД также гарантирует, что никакой эффект зафиксированных транзакций не будет потерян, а эффект прерванных ( откатных ) транзакций не останется в связанной базе данных. Общая характеристика транзакции обычно резюмируется приведенными ниже правилами ACID . Поскольку базы данных стали распределенными или им потребовалось взаимодействовать в распределенных средах (например, объединенные базы данных в начале 1990-х годов и облачные вычисления в настоящее время), эффективному распределению механизмов управления параллелизмом стало уделяться особое внимание.

Транзакция базы данных и правила ACID

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

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

Зачем нужен контроль параллелизма?

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

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

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

Механизмы управления параллелизмом

Категории

Основными категориями механизмов управления параллелизмом являются:

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

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

Блокировки, взаимоблокировки и прерывания — все это приводит к снижению производительности и, следовательно, к компромиссам между категориями.

Методы

Существует множество методов управления параллелизмом. Большинство из них могут быть реализованы в рамках любой из основных категорий, указанных выше. Основными методами [1] , каждый из которых имеет множество вариантов и в некоторых случаях может частично совпадать или комбинироваться, являются:

  1. Блокировка (например, двухфазная блокировка — 2PL) — управление доступом к данным с помощью блокировок , назначенных данным. Доступ транзакции к элементу данных (объекту базы данных), заблокированному другой транзакцией, может быть заблокирован (в зависимости от типа блокировки и типа операции доступа) до момента снятия блокировки.
  2. Проверка графа сериализации (также называемая проверкой сериализуемости, конфликтов или приоритетов) — проверка циклов в графе расписания и их прерывание.
  3. Порядок меток времени (TO). Назначение меток времени транзакциям, а также контроль или проверка доступа к данным по порядку меток времени.

Другие основные типы управления параллелизмом, которые используются в сочетании с описанными выше методами, включают:

Наиболее распространенным типом механизма в системах баз данных с момента их появления в 1970-х годах была строгая строгая двухфазная блокировка (SS2PL; также называемая строгим планированием или строгим 2PL ), которая является особым случаем (вариантом) двухфазной блокировки (2PL). . Это пессимистично. Несмотря на длинное название (по историческим причинам), идея механизма SS2PL проста: «Снимать все блокировки, примененные транзакцией, только после ее завершения». SS2PL (или строгость) — это также имя набора всех расписаний, которые могут быть созданы с помощью этого механизма, т. е. эти расписания SS2PL (или строгость) обладают свойством SS2PL (или строгость).

Основные цели механизмов управления параллелизмом

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

Корректность

Сериализуемость

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

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

Возможность восстановления
См. «Восстанавливаемость» в сериализуемости.

Управление параллелизмом обычно также обеспечивает свойство «Восстанавливаемость» расписаний для поддержания правильности в случаях прерванных транзакций (что всегда может произойти по многим причинам). Возможность восстановления (после прерывания) означает, что ни одна зафиксированная транзакция в расписании не прочитала данные, записанные прерванной транзакцией. Такие данные исчезают из базы данных (при прерывании) и являются частью неправильного состояния базы данных. Чтение таких данных нарушает правило согласованности ACID. В отличие от сериализуемости, возможность восстановления не может быть скомпрометирована или ослаблена в любом случае, поскольку любое ослабление приводит к быстрому нарушению целостности базы данных при прерывании работы. Основные методы, перечисленные выше, обеспечивают механизмы сериализуемости. Ни один из них в своей общей форме автоматически не обеспечивает возможность восстановления, и для поддержки возможности восстановления необходимы специальные соображения и усовершенствования механизмов. Обычно используемым частным случаем восстановления является Strictness , который позволяет эффективно восстанавливать базу данных после сбоя (но исключает оптимистичные реализации).

Распределение

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

Восстановление

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

Репликация

Для обеспечения высокой доступности объекты базы данных часто реплицируются . Обновления реплик одного и того же объекта базы данных необходимо синхронизировать. Это может повлиять на способ управления параллелизмом (например, Gray et al. 1996 [2] ).

Управление параллелизмом в операционных системах

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

Смотрите также

Рекомендации

Цитаты

  1. ^ Филип А. Бернштейн , Эрик Ньюкомер (2009): Принципы обработки транзакций, 2-е издание. Архивировано 7 августа 2010 г. в Wayback Machine , Морган Кауфманн (Elsevier), июнь 2009 г., ISBN 978-1-55860-623-4 ( стр. 145) 
  2. ^ Грей, Дж .; Хелланд, П.; О'Нил, П .; Шаша, Д. (1996). Материалы Международной конференции ACM SIGMOD 1996 года по управлению данными . Опасности репликации и решение (PDF) . стр. 173–182. дои : 10.1145/233269.233330.[ постоянная мертвая ссылка ]