Сериализуемость по конфликтам и граф сериализуемости  

Сериализуемость по конфликтам и граф сериализуемости

Конспект стр. 48 п. 4.2.2

Молина, стр. 888

Планировщик поддерживает граф конфликтов, в котором вершины и дуги добавляются динамически в зависимости от операций, которые получает на вход планировщик. При этом конфликтующими называются любые две операции над одним и тем же элементом данных, если хотя бы одна из них является операцией модификации. Другими словами, для конфликтующих операций существенен порядок их выполнения. Таким образом, планирование конфликтующих операций накладывает ограничение на порядок сериализации транзакций. Эти ограничения и выражает граф конфликтов. Теперь рассмотрим, как происходит планирование очередной операции pi(x) с помощью SGT-планировщика.

1. Если это первая операция транзакции ti, поступившая планировщику, то создается новый узел в графе сериализации.

2. В граф добавляются дуги вида (tj, ti) для каждой запланированной ранее операции qj(x) (i ≠ j), конфликтующей с pi(x). Теперь возможны два варианта:

a. Результирующий граф содержит циклы. В этом случае транзакция ti откатывается.

b. Полученный граф ацикличен. В этом случае действие добавляется к списку запланированных.

Функции Диспетчера транзакций. Типы диспетчеров.

Конспект стр. 49

43. Использование замков: двухфазный протокол блокирования.

Молина стр. 895- замки, 897- двухфазный протокол

конспект стр. 49-50

4-consistency, слайд 18

Корректность двухфазного протокола блокирования.

Молина стр. 898

transactions, слайд 60

4-consistency, слайд 21

45. Тупики: обнаружение и разрешение.

(из конспекта, стр. 51) 4.3.4. Тупики

Также возможно возникновение тупиков. Для борьбы с ними применяются различные методы, однако сперва их необходимо обнаружить. Для этой цели мы будем строить граф ожидания (вершины — транзакции, дуги проводим из ожидающей транзакции в ту, которая удерживает замок).Наличие тупика равносильно наличию контура в графе. Для разрешения тупика нам нужно выбрать жертву, прервать и откатить транзакцию, у которой «не сложилась судьба».

Стратегии бывают разные (например, случайный выбор), но фактически нельзя указать самую эффективную (здесь под эффективностью подразумевается выбор жертвы таким образом, чтобы минимизировать количество обрывов в расписании). В некоторых БД применяется такой метод разрешения тупиков—обрыв по тайм-ауту.

4-consistency, слайд 21

transactions, слайд 62-65

Протокол установки замков для дерева.



http://www.cs.ucsb.edu/~agrawal/spring2011/grad/Lecture7.pdf, стр. 19

Слайды: 4-consistency, стр. 22-23

молина, стр. 924 (на самом деле, там протокол немного отличается от того, что рассказывал Новиков. Например, в Молине первым без всяких адских требований можно захватывать любую вершину дерева, а не только корень. И там корректность труднее доказывается).

4.3.5 конспект

Мультигранулярные замки.

http://msdn.microsoft.com/en-us/library/ms175519.aspx

Слайды: 4-consistency, стр. 25-26

Молина, стр. 919

http://serversql.ru/upravlenie-parallelnoj-rabotoj/rezhimy-blokirovki.html - на русском

Уровни изоляции в SQL и оптимистические замки.

конспект, стр. 51, 52

4-consistency, слайд 26, 28, 29, 32

Уровни изоляции

http://ru.wikipedia.org/wiki/Уровень%20изолированности%20транзакций

В идеале транзакции разных пользователей должны выполняться так, чтобы создавалась иллюзия, что пользователь текущей транзакции — единственный. Однако в реальности, по соображениям производительности и для выполнения некоторых специальных задач, СУБД предоставляют различные уровни изоляции транзакций. Уровни описаны в порядке увеличения изоляции транзакций и надёжности работы с данными.

● 0 — Неподтверждённое чтение (Read Uncommitted, Dirty Read, грязное чтение) — чтение незафиксированных изменений своей транзакции и конкурирующих транзакций, возможны нечистые, неповторяемые чтения и фантомы

● 1 — Подтверждённое чтение (Read Committed) — чтение всех изменений своей транзакции и зафиксированных изменений конкурирующих транзакций, нечистые чтения невозможны, возможны неповторяемые чтения и фантомы

● 2 — Повторяемое чтение (Repeatable Read, Snapshot) — чтение всех изменений своей транзакции, любые изменения, внесённые конкурирующими транзакциями после начала своей, недоступны, нечистые и неповторяемые чтения невозможны, возможны фантомы



● 3 — Упорядоченный — (Serializable, сериализуемый) — упорядоченные (сериализуемые) транзакции. Идентичен ситуации, при которой транзакции выполняются строго последовательно, одна после другой. То есть транзакции, результат действия которых не зависит от порядка выполнения шагов транзакции (запрещено чтение всех данных, изменённых с начала транзакции, в том числе и своей транзакцией). Фантомы невозможны.

Чем выше уровень изоляции, тем больше требуется ресурсов, чтобы их поддерживать.

В СУБД уровень изоляции транзакций можно выбрать как для всех транзакций сразу, так и для одной конкретной транзакции. По умолчанию в большинстве баз данных используется уровень 1 (Read Committed). Уровень 0 используется в основном для отслеживания изменений длительных транзакций или для чтения редко изменяемых данных. Уровни 2 и 3 используются при повышенных требованиях к изолированности транзакций.

http://www.t-sql.ru/post/nolock.aspx - много кода про уровни изоляции


9137244748409295.html
9137361940127631.html

9137244748409295.html
9137361940127631.html
    PR.RU™