Caché: Борьба с deadlock

Deadlock, или мертвая блокировка - это явление, событие или состояние двух или более процессов, один из которых, заблокировав ресурс 1, ожидает освобождения ресурса 2, но ресурс 2 в свою очередь заблокирован другим процессом, и он ожидает освобождения ресурса 1. Эта ситуация разрешима только указанием времени истечения ожидания и переводом этой ситуации в состояние ошибочной, с откатом в связи с невозможностью выполнить какое-то действие.

Мне было интересно, что может предпринять программист в свою очередь, чтобы не допустить deadlock. Не имея столь же красочного и таинственного русскоязычного термина, буду так и писать - deadlock.

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

В реальной работе базы данных возможности указать порядок блокировок практически невозможно, поскольку в большинстве мест код определяет имена блокировок обращаясь к данным. Узкое в этом смысле место - обновление индексов.

Для иллюстрации примера приведем коды, условно воспроизводящие ситуацию с обновлением нескольких (для простоты двух) объектов, имеющих два простых атрибута, имеющих всего два значения. Функция action выполняет обновление как строки данных (^zAug("data")), так и двух индексов (^zAug("prop1") и ^zAug("prop2")). Функция run1 выполняет имитацию изменения объектов.

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

run1()
 n id,prop1,prop2
 f  d
 . w "."
 . s id=$r(2),prop1=$r(2),prop2=$r(2)
 . d action1(id,prop1,prop2)
 q
action1(id,prop1,prop2)
 n oldprop1,oldprop2
 ;
 s oldprop1=$lg($G(^zAug("data",id)),1)
 s oldprop2=$lg($G(^zAug("data",id)),2)
 ;
 l:oldprop1'="" +^zAug("prop1",oldprop1,id)
 l:oldprop2'="" +^zAug("prop2",oldprop2,id)
 l +^zAug("prop1",prop1,id)
 l +^zAug("prop2",prop2,id)
 ;
 k:oldprop1'="" ^zAug("prop1",oldprop1,id)
 k:oldprop2'="" ^zAug("prop2",oldprop2,id)
 ;
 s ^zAug("prop1",prop1,id)=""
 s ^zAug("prop2",prop2,id)=""
 ;
 s ^zAug("data",id)=$lb(prop1,prop2)
 h .5
 ;
 l:oldprop1'="" -^zAug("prop1",oldprop1,id)
 l:oldprop2'="" -^zAug("prop2",oldprop2,id)
 l -^zAug("prop1",prop1,id)
 l -^zAug("prop2",prop2,id)
 q

После запуска d run1 в двух процессах они в течении нескольких минут уверенно встают в deadlock. Будем использовать этот код как базовый для модернизации с целью предотвращения неприятности.

В книге http://www.afc.deepweb.ru/texts/daitel/glava6.shtml приводятся четыре условия для возникновения deadlock:

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

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

Общий метод выглядит примерно так: разбиваем ресурсы на иерархические группы. Назовем их группа1, группа2, ... группаN. При этом вводится дисциплина блокирования: ресурсы группы n+1 могут быть блокированы только если нет других блокировок группы n+1 или старше и если есть блокировка имен группы n или младше. Группой ноль будем считать отсутствие блокировок. В рамках одной группы блокировку выполняем списком.

Группы следует организовать таким образом, чтобы имена блокировок группы n+1 были известны после блокирования имен группы n. В примере используется инкрементальная блокировка списком чтобы удержать имевшиеся ранее блокировки и добавить к ним новые.

Текст примера для воспроизведения / тестов:

run3()
 n id,prop1,prop2
 f  d
 . w "."
 . s id=$r(2),prop1=$r(2),prop2=$r(2)
 . d action3bit(id,prop1,prop2)
 q
 ; то же самое что action3 но имитируем битовые сегменты
action3bit(id,prop1,prop2)
 n str,old,oldprop1,oldprop2
 s str=$na(^zAug("prop1",prop1,1))_","_
    $na(^zAug("prop2",prop2,1))
 l +^zAug("data",id)
 s oldprop1=$lg(^zAug("data",id),1)
 s oldprop2=$lg(^zAug("data",id),2)
 ; это на случай запуска теста без созданных данных
 s:oldprop1="" oldprop1=" "
 s:oldprop2="" oldprop2=" "
 s old=$na(^zAug("prop1",oldprop1,1))_","_
       $na(^zAug("prop2",oldprop2,1))
 x "l +("_old_","_str_")"
 ; ничего не значит, это имитация.
 ; реально тут битовая операция сброса бита
 x "s ("_str_")="""""
 s ^zAug("data",id)=$lb(prop1,prop2)
 h 0.4
 ; тоже ничего не значит, это имитация.
 ; реально тут битовая операция установки бита
 x "s ("_str_")="""""
 x "l -("_old_","_str_")"
 l -^zAug("data",id)
 q
 ; обычный обратный индекс
action3(id,prop1,prop2)
 n str,old,oldprop1,oldprop2
 s str=$na(^zAug("prop1",prop1,id))_","_
     $na(^zAug("prop2",prop2,id))
 l +^zAug("data",id)
 s oldprop1=$lg(^zAug("data",id),1)
 s oldprop2=$lg(^zAug("data",id),2)
 ; это на случай запуска теста без созданных данных
 s:oldprop1="" oldprop1=" "
 s:oldprop2="" oldprop2=" "
 s old=$na(^zAug("prop1",oldprop1,id))_","_
    $na(^zAug("prop2",oldprop2,id))
 x "l +("_old_","_str_")"
 x "k "_old   ; ну просто совпало так
 s ^zAug("data",id)=$lb(prop1,prop2)
 h 0.4
 x "s ("_str_")="""""  ; тут тоже удачно совпало
 x "l -("_old_","_str_")"
 l -^zAug("data",id)
 q

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

В приведенном примере две группы:

• ^zAug("data",...) - узел данных
• ^zAug("prop1",...) и ^zAug("prop2",...) - узлы индексов

Некоторый условный пример с более осмысленным содержанием: Пусть есть объект документ с объектами - строки документа. Для операций с объектом делим операции и имена блокировок на 4 группы:

1. сохранения документа, вход - ид документа, дальше передаются имена для группы2 (имена индексов) и группы3 (иды объектов - строк документа)
2. индексы документа
3. объекты строк документа, вход - ид объекта строки, дальше передаются имена для группы4 (имена индексов по строкам)
4. индексы строк

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

Также следует отметить, что при использовании в битовых операциях функций семейства $bit из пятой версии Cache проблема deadlock автоматически снимается, поскольку операция

 s $bit(^data,n)=0
 s $bit(^data,n)=1

корректно отрабатывается без необходимости блокирования всего сегмента, корректно работает откат транзакции. При использовании в качестве реализации битовых операций функций семейства $bit получаем выигрыш как в более свободной параллельной работе процессов, так и в существенном снижении объемов журналирования изменений индексных сегментов. Хотя проблема deadlock этим решается, тем не менее появляется проблема фантомов на чтение, впрочем это совсем другая тема.

В решении проблемы помогли советы группы CACHE_RU, особенно Алексей Маслов (СП.АРМ, Ленинград).