2 Phase Locking — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Применение)
м (rollbackEdits.php mass rollback)
 
(не показано 6 промежуточных версий 3 участников)
Строка 1: Строка 1:
Алгоритм двухфазной блокировки используется для взятия блокировок при выполнении [[Транзакции в распределённых системах|распределённых транзакций]] (например, в СУБД).
+
[[Категория: Параллельное программирование]]
 +
'''Алгоритм двухфазной блокировки''' используется для взятия блокировок при выполнении [[Транзакции в распределённых системах|распределённых транзакций]] (например, в СУБД).
  
Алгоритм требует, чтобы каждая транзакция должна состояла из двух фаз: на первой мы только набираем блокировки (в любом порядке), а на второй фазе мы их только отпускаем (в любом порядке).
+
Алгоритм требует, чтобы каждая транзакция состояла из двух фаз: на первой мы только набираем блокировки (в любом порядке), а на второй фазе мы их только отпускаем (в любом порядке).
 
Например, если мы работаем с элементами $x$ и $y$, то мы можем сначала взять блокировку на $x$, потом поработать с $x$, потом взять блокировку на $y$, поработать с ним, а потом отпустить все блокировки.
 
Например, если мы работаем с элементами $x$ и $y$, то мы можем сначала взять блокировку на $x$, потом поработать с $x$, потом взять блокировку на $y$, поработать с ним, а потом отпустить все блокировки.
  
Строка 13: Строка 14:
  
 
Из-за этого могут возникнуть проблемы с взаимными блокировками (потому что порядок взятия блокировок может отличаться в разных транзакциях), поэтому:
 
Из-за этого могут возникнуть проблемы с взаимными блокировками (потому что порядок взятия блокировок может отличаться в разных транзакциях), поэтому:
* Детектор взаимных блокировок всё равно нужен. Если нашли — то отменяем одну из транзакций и снимаем все её блокировки. Есть разные стратегии выбора, какую транзакцию отменять. Можно самую новую (тогда мы будем дожидаться старой), можно самую долго работающую (тогда у коротких запросов приоритет), можно ещё как-то.
+
* [[Определение взаимной блокировки|Детектор взаимных блокировок]] всё равно нужен. Если нашли — то отменяем одну из транзакций и снимаем все её блокировки. Есть разные стратегии выбора, какую транзакцию отменять. Можно самую новую (тогда мы будем дожидаться старой), можно самую долго работающую (тогда у коротких запросов приоритет), можно ещё как-то.
 
* В некоторых СУБД есть даже специальный SQL-синтаксис для deadlock avoidness, вроде <code>SELECT FOR UPDATE</code>
 
* В некоторых СУБД есть даже специальный SQL-синтаксис для deadlock avoidness, вроде <code>SELECT FOR UPDATE</code>
  
Проблемы, конечно, в том, что если у нас большой запрос по всем строкам таблицы, то нам нужно всё заблокировать.
+
Проблемы, конечно, в том, что если у нас большой запрос по всем строкам таблицы, то нам нужно всё заблокировать, но для этого есть [[Транзакции в распределённых системах#Согласованность и изоляция|MVCC]] или пониженные уровни изоляции.

Текущая версия на 19:08, 4 сентября 2022

Алгоритм двухфазной блокировки используется для взятия блокировок при выполнении распределённых транзакций (например, в СУБД).

Алгоритм требует, чтобы каждая транзакция состояла из двух фаз: на первой мы только набираем блокировки (в любом порядке), а на второй фазе мы их только отпускаем (в любом порядке). Например, если мы работаем с элементами $x$ и $y$, то мы можем сначала взять блокировку на $x$, потом поработать с $x$, потом взять блокировку на $y$, поработать с ним, а потом отпустить все блокировки.

Distributed-2pl.png

Если все транзакции устроены таким образом, то гарантируется сериализуемость транзакции.

Применение

Так можно брать не все блокировки, а только нужные. Это особенно удобно в СУБД, когда движок заранее не знает, какие блокировки потребуются: он может просто набирать блокировки, как появляются запросы, а в конце, при применении транзакции, их разом отпустить.

Из-за этого могут возникнуть проблемы с взаимными блокировками (потому что порядок взятия блокировок может отличаться в разных транзакциях), поэтому:

  • Детектор взаимных блокировок всё равно нужен. Если нашли — то отменяем одну из транзакций и снимаем все её блокировки. Есть разные стратегии выбора, какую транзакцию отменять. Можно самую новую (тогда мы будем дожидаться старой), можно самую долго работающую (тогда у коротких запросов приоритет), можно ещё как-то.
  • В некоторых СУБД есть даже специальный SQL-синтаксис для deadlock avoidness, вроде SELECT FOR UPDATE

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