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

Материал из eSyr's wiki.

Предыдущая лекция | Следующая лекция

Все транзакции работали на общей памяти, которые выделялись RSS, у транзакции не было общей памяти.

Функция 4. Журнализация и восстановление

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

Сейчас лектор расскажет ещё одно решение проблемы.

Единица блокировка – строка таблицы.

Считается хорошим тоном во многих системах – строка системы – наиболее подходящий уровень для установки блокировки.

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

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

Гранилированные синхрозационные блокировки. Это некоторый способ помочь разобраться менеджеру блокировок при запросе блокировки. Можно представить, что вся БД представляет некоторую иерархию. Она состоит из набора сегментов, каждый сегмент состоит из набора таблиц, каждая таблица состоит из набора строк. Почему это упрощение – потому что ещё есть индексы. Так вот, что, как мы уже убедились, если синхронизация ведётся не на уровне условий а на уровне объектов, то нужно иногда блокировать БД целиком. Если я хочу ывполнить операцию над БД, то я не должен иметь возможности работать с Сегментами, Таблицами и Строками, если с Сегментом, то с другими Сегментами можно, а с этим же сегментом, таблицами и строками в нём не могу. Соотв, должны быть блокировки для каждого уровня. Были предложены три дополнительных блокировки % блокировки намеряния. (intended block) 1.Intended to share (IS) 2.Intended to excludive (IX) 3.Shared, intended to exclusive (SIX) Если хочу заблокировать строку в режиме S, тогда надо ещё на таблицу, сегмент и БД поставить IS. Если таблицу X, тогда сегмент и БД на IX.

SIX – таблица в режиме чтения, строки могут быть ещё заблокировать в режиме записи.

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

В SQL порядка 15 разных блокировок.

Как в 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-маша объектов.

Начинать заподозривать наличие тупиков, если транзакции не продвигаются вперёд.

Кроме как таймаут, вариантов нет.

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

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

Двухуровневые блокировки: логическая и физическая блокировка.

Микрооперация – единица физической согласованности БД. С точки зрения RSS каждая микрооперация – маленькие транзакции, которые выполняются внутри RSS, и каждая микрооперация работает с набором блоков, и для того, чтобы гарантировать физ соглас, мы должны блокировать блоки, чтобы другие транзакции не могли их менять. Здесь тоже работает двухфаз мех блокировки, но на уровне блоков. Но тут хочешь-не хочешь приходиться делать синхронизацию на уровне блоков. Очень плохо делать логич единицу синхр блоком. И тут могут возникать тупики. И граф здесь строить очен трудно. Что делать – прибить и запустить заново, об этом даже уровень SQL не знает. Как сделать микрооткат, вопрос тонкий, и там уже тонкости журнализации.

юююЭто подход глубокого пессимиста – если пойду в магазин, то будет очередь, если куплю хлеб, то на этом деньги кончатся... так и в БД: когда хочу писать, обязательно какой-нибудь гад читает, поэтому надо заблокировать.

Механизм синхронизационной блокировки хорош тогда, когда много транзакцией над небольшой БД, тогда затраты оправданы.

Если система распределённая, и есть понятие глобаьной транзакции, операции которой выполняются разными СУБД локально, тогда граф транзакций строить трудно. Лект ору нравится алгоритм, который сделали в Систем Р*. Можно сделать алгоритм без блокировок, но за это платятся транзакции.