Редактирование: Базы Данных, 26 лекция (от 08 декабря)

Единственный возможный способ решения проблемы фантомов – предикатная синхронизационная блокировка. Она решает не только эту проблему.

Вопрос, который лектор любит задавать на экзамене: предположим, что в качестве механизма блокировокок выбран двухфаз протокол, единица блокировки – строка, пример операции, которую нельзя выполнить. Лектор не знает, как при таком способе выполнить операцию уничтожения таблицы. Для этого нужно сначала выкинуть данные, строка за строкой, и блокировать их. Когда последняя строка удалена, то можно её уничтожить. Но никто не мешает вставить другой кортеж в это время. Нужно блокировать таблицу целиком в режиме X. Если в качестве единицы блокировки таблица целиком, то когда как удалить базу данных? А если блокировать БД целиком, то как тогда выполнять транзакции одновременно? Следовательно, нужно иметь транзакции разных уровней. Как это сделать?

Что придумали разработчики System R: (вероятно, придумал Джимм Грей, по крайней мере, первая публикация его. Bill Gates называет его великим деятелем современной информатики. Вероятно, потому, что он сотрудник Microsoft в течение последних 10 лет. Его считают великим писателем, потому что он любит писать. Кроме 5-6 статей в год, он одновременно готовит собственные произведения, которые редко публикуются. Он, конечно, прославился, как и многие другие, в проекте System R. И в то время тоже очень любил писать. Лектор хочет, чтобы и мы тоже к 25 годам захотели писать. Он больше всех писал о проекте System R.)

 

'''Гранилированные синхрозационные блокировки.'''

Это некоторый способ помочь разобраться менеджеру блокировок при запросе блокировки. Можно представить, что вся БД представляет некоторую иерархию. Она состоит из набора сегментов, каждый сегмент состоит из набора таблиц, каждая таблица состоит из набора строк. Почему это упрощение – потому что ещё есть индексы. Так вот, что, как мы уже убедились, если синхронизация ведётся не на уровне условий а на уровне объектов, то нужно иногда блокировать БД целиком. Если я хочу ывполнить операцию над БД, то я не должен иметь возможности работать с Сегментами, Таблицами и Строками, если с Сегментом, то с другими Сегментами можно, а с этим же сегментом, таблицами и строками в нём не могу. Соотв, должны быть блокировки для каждого уровня. Были предложены три дополнительных блокировки

% блокировки намеряния. (intended block)

Если хочу заблокировать строку в режиме S, тогда надо ещё на таблицу, сегмент и БД поставить IS. Если таблицу X, тогда сегмент и БД на IX.

Как в System R – у них была реализована такая схема гранулированных блокировок. Почему гранулированных – разного размера объекты в менеджере можно блокировать.

Как можно решить проблему гранулированности с помощью предикатных блокировок. Что такое заблокировать таблицу целиком с тз логического условия? Таблица – n-мерное пространство, поэтому чтобы уничтожить таблицу, нужно заблокировать это пространство целиком. Если есть таблица T{A1...An}, то нужно поставить блокировку X с таким условием: X(min1 <= A1 <= max1, ..., minn <= An <= maxn). Что такое заблокировать БД – берутся все типы данных, которые могут быть у атрибутов таблицы и блокируются они все.

Как делали в System R и теперь во всех коммерческих системах: разделяют два случая: вопрос, какое сканирование проводится – прямое сканирование (тогда блокируется таблица целиком) или сканирование через индекс (как правило, оптимизатор запросов выбирает сканирование через индекс, когда для ключевого поля входят условия-диапазаон значения ключа, тогда они применяют вариант предикатной блокировки в одномерном пространстве)

Есть две транзакции, есть два объекта. Т1 блокирует О1 в режиме х, Т2 – о2, потом Т1 хочет получить доступ О2, а Т2 к О1. В этой ситуации ни одна, ни вторая никогда не сдвинуться с места, смертельное объятие. Есть разные схемы, которые позволяют использовать синхронизационные блокировки и избегать такой ситуации, например, перенумеровать все ресурсы и обращаться в порядке возрастания номеров, но это противоречит духу транзакций, так как это последовательность произвольных операций. Поэтому в СУБД приходиться использовать специальную технику, которая называется техникой распознавания и разрушения. Лектор много лет это читает и говорит, что системных программистов лучше всего учить на СУБД, потому что СУБД это такая программная система, в оторой приходиться применять все технологии, которые нужны в СП. То, что применяется в СУБД, нельзя применять в ОС, так как там слишком много разных ресурсов. Всё распознавания тупиков сводится к построению и анализу графа ожидания транзакций. Это один из вариантов, но он понятный и простой. Строить его в виде двудольного графа – вершины одного рода – транзакции, которые либо блокировали что-то, либо ожидают что-то, вторые – блокированные объекты. Графы ориентированные. Если транзакция что-то блокирует, то проводится дуга от транзакции к объекту, если ожидает, то от объекта к транзакции. Легко доказать, что блокировка есть тогда и только тогда, когда есть хотя бы один цикл. Два проблемы: как строить граф и как искать циклы.

Представить себе в уме граф ожидания транзакций произвольной сложности. Находим все такие транзакции, у которых только исходящие дуги. Эти транзакции считаются безопасными, потому что ничего не ждут, значит они могут благополучно закончиться. Тогда мы смотрим, куда эти стрелки. Если у этого объекта есть исходящая стрела, то мы меняем эту стрелку наоборот, считваем, что транзакция удалась. Теперь смотрим ещё раз то же самое. Этот алгоритм железно работает, называется алгоритмом редукции графа. Он требует достаточно большой работы, сложность алгоритма n*m, если есть n транзакций и m-маша объектов.

Одним из способов, известных науке: Выбор жертв. Если двум группам жить плохо, то одну надо истребить, и тогда второй станет жить хорошо. То есть силком сделать роллбэк одной из транзакций, и она начинает его делать. Он делает роллбэк, объекты освобождаются, и смотрим, остались циклы или нет. Как Раскольников – убил миллионщицу, и всем стало хорошо. Но старых убивать плохо, они же почти закончились. Лучше убивать младенцев. Но их тоже убивать плохо, потому что они ещё почти ничего не сделали. Можно выбирать транзакции по весам. А если эта транзакция, которая запущена от имени начальника? Все кипят, работают, а начальнику ресурсов не хватило. Так тоже нельзя.

Все идиоты, а Администратор БД умный, и он должен все проблемы решать. Такое мнение много лет существовалло, и в настоящее время СУБД такой прибор, который мы видим на МКС – там дикое количество ручечек. И настройка СУБД под конкретную организацию, если есть Господь Бог на свете, если есть Администратор. Но администраторы конечны они люди, и дикое количество ручек приводит к тому, что система становится расстроена. А сетапа, то есть вещи, которая возвращает систему в исходное состояния нет, это не телевизор.