2 Phase Locking — различия между версиями
Yeputons (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
| (не показаны 4 промежуточные версии 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]] или пониженные уровни изоляции. | Проблемы, конечно, в том, что если у нас большой запрос по всем строкам таблицы, то нам нужно всё заблокировать, но для этого есть [[Транзакции в распределённых системах#Согласованность и изоляция|MVCC]] или пониженные уровни изоляции. | ||
Текущая версия на 19:08, 4 сентября 2022
Алгоритм двухфазной блокировки используется для взятия блокировок при выполнении распределённых транзакций (например, в СУБД).
Алгоритм требует, чтобы каждая транзакция состояла из двух фаз: на первой мы только набираем блокировки (в любом порядке), а на второй фазе мы их только отпускаем (в любом порядке). Например, если мы работаем с элементами $x$ и $y$, то мы можем сначала взять блокировку на $x$, потом поработать с $x$, потом взять блокировку на $y$, поработать с ним, а потом отпустить все блокировки.
Если все транзакции устроены таким образом, то гарантируется сериализуемость транзакции.
Применение
Так можно брать не все блокировки, а только нужные. Это особенно удобно в СУБД, когда движок заранее не знает, какие блокировки потребуются: он может просто набирать блокировки, как появляются запросы, а в конце, при применении транзакции, их разом отпустить.
Из-за этого могут возникнуть проблемы с взаимными блокировками (потому что порядок взятия блокировок может отличаться в разных транзакциях), поэтому:
- Детектор взаимных блокировок всё равно нужен. Если нашли — то отменяем одну из транзакций и снимаем все её блокировки. Есть разные стратегии выбора, какую транзакцию отменять. Можно самую новую (тогда мы будем дожидаться старой), можно самую долго работающую (тогда у коротких запросов приоритет), можно ещё как-то.
- В некоторых СУБД есть даже специальный SQL-синтаксис для deadlock avoidness, вроде
SELECT FOR UPDATE
Проблемы, конечно, в том, что если у нас большой запрос по всем строкам таблицы, то нам нужно всё заблокировать, но для этого есть MVCC или пониженные уровни изоляции.
