Протоколы управления параллелизмом

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

Definition

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

Scope

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

Core questions

• Как двухфазная блокировка гарантирует сериализуемые расписания?
• Как обнаруживаются, предотвращаются или разрешаются взаимоблокировки?
• Чем протоколы упорядочения по меткам времени и оптимистические протоколы отличаются от блокировки?
• Как многоверсионное управление параллелизмом позволяет читателям избегать блокировки писателей?
• Каковы компромиссы в пропускной способности между пессимистическими и оптимистическими методами?

Key concepts

• двухфазная блокировка
• строгая и жесткая 2PL
• разделяемые и эксклюзивные блокировки
• обнаружение и предотвращение взаимоблокировок
• упорядочение по меткам времени
• оптимистическое управление параллелизмом
• многоверсионное управление параллелизмом
• изоляция снимков

Key theories

Двухфазная блокировка

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

Оптимистическое управление параллелизмом

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

Многоверсионное управление параллелизмом

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

Clinical relevance

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

History

Двухфазная блокировка и предикатные блокировки были формализованы Эсвараном и коллегами в System R в 1976 году; Кунг и Робинсон представили оптимистическое управление параллелизмом в 1981 году; а монография Бернштейна, Хадзилакоса и Гудмана 1987 года объединила теорию. Многоверсионные методы и изоляция снимков позже стали доминирующими в широко используемых системах баз данных благодаря их удобству для чтения.

Debates

Изоляция снимков против сериализуемости

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

Key figures

• Jim Gray
• Philip Bernstein
• H. T. Kung

Seminal works

• eswaran1976
• kung1981
• bernstein1987

Frequently asked questions

Что вызывает взаимоблокировку и как она обрабатывается?

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

Когда оптимистическое управление параллелизмом является хорошим выбором?

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