Принципы построения БД Тема 91 Принципы построения и работы баз данных Тема 09: Управление параллельным доступом. - презентация

1 Принципы построения БД Тема 91 Принципы построения и работы баз данных Тема 09: Управление параллельным доступом

2 Принципы построения БД Тема 92 Параллельный доступ (разделение данных) T1T2…Tn БД (ограничения целостности)

3 Принципы построения БД Тема 93 Пример: T1:Read(A)T2:Read(A) A A+100A A 2Write(A)Read(B) B B+100B B 2Write(B) Ограничение: A=B

4 Принципы построения БД Тема 94 График (расписание) A T1T2 Read(A); A A+100 Write(A); Read(B); B B+100; Write(B); Read(A);A A 2; Write(A); Read(B);B B 2; Write(B); AB

5 Принципы построения БД Тема 95 График B T1T2 Read(A);A A 2; Write(A); Read(B);B B 2; Write(B); Read(A); A A+100 Write(A); Read(B); B B+100; Write(B); AB

6 Принципы построения БД Тема 96 График C T1T2 Read(A); A A+100 Write(A); Read(A);A A 2; Write(A); Read(B); B B+100; Write(B); Read(B);B B 2; Write(B); AB

7 Принципы построения БД Тема 97 График D T1T2 Read(A); A A+100 Write(A); Read(A);A A 2; Write(A); Read(B);B B 2; Write(B); Read(B); B B+100; Write(B); AB

8 Принципы построения БД Тема 98 График E T1T2 Read(A); A A+100 Write(A); Read(A);A A 1; Write(A); Read(B);B B 1; Write(B); Read(B); B B+100; Write(B); AB То же, что и график D но с новой транзакцией T2

9 Принципы построения БД Тема 99 Мы хотим «хорошие графики», не зависящие от –Начального состояния и –Семантики (смысла) транзакции Достаточно рассмотреть порядок операторов read и write Sc=r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B) T1 T2 упорядоченный график, действия Т1 и Т2 не перекрываются Пример: Sc=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)

10 Принципы построения БД Тема 910 Однако, для Sd: Sd=r1(A)w1(A)r2(A)w2(A) r2(B)w2(B)r1(B)w1(B) На самом деле,T2 должна предшествовать T1 в любом эквивалентном расписании, т.е. T2 T1 С другой стороны, если смотреть на изменение А, то T1 должна предшествовать T2, т.е. T1 T2 T1 T2 Sd не может быть преобразовано в упорядоченный график Sd не эквивалентно никакому упорядоченному графику Sd - «плохой» график

11 Принципы построения БД Тема 911 Вернемся к Sc Sc=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B) T1 T2 T1 T2 циклов нет Sc эквивалентно упорядоченному расписанию (в данном случае T1,T2)

12 Принципы построения БД Тема 912 Идеи Транзакция: последовательность действий ri(x), wi(x) Конфликтующие действия: r1(A) w2(A) w1(A) w2(A) r1(A) w2(A) График: представляет хронологический порядок выполнения действий Упорядоченный график: действия транзакций не перекрываются (для любой пары транзакций одна из них должна быть полностью завершена до того, как начнет выполняться другая)

13 Принципы построения БД Тема 913 Возможны ли параллельные действия? T1 выдаетСистема Input(x) t x read(x,t)выдаетзавершен input(x) время T2 выдает write(b,s) Система выдает input(b) завершен b s Система выдает output(b) завершен Следовательно, в результате имеем S=…r1(x)…w2(b)… либо S=…w2(b)…r1(x)…

14 Принципы построения БД Тема 914 Предполагается, что действия эквивалентны либо r1(A) w2(A), либо w2(A) r1(A) Низкоуровневый механизм синхронизации Предполагается, что действия могут быть представлены в виде той или иной последовательности атомарных действий Что происходит в параллельными конфликтующими действиями над одним и тем же объектом? начало r1(A)конец r1(A) начало w2(A) конец w2(A) время

15 Принципы построения БД Тема 915 Определение S1, S2 называются конфликтно-эквивалентными графиками, если S1 может быть преобразовано в S2 последовательность перестановок не конфликтующих действий. График называется конфликтно-упорядочиваемым, если он конфликтно-эквивалентен некоторому упорядоченному графику.

16 Принципы построения БД Тема 916 Вершины: транзакции в S Дуги: провести Ti Tj когда - pi(A), qj(A) – действия в S - pi(A) < S qj(A) - по крайней мере одно из действий -write Каков будет P(S) для S = w3(A) w2(C) r1(A) w1(B) r1(C) w2(A) r4(A) w4(D) Является ли S конфликтно-упорядочиваемым? Граф предшествования P(S) (S - график)

17 Принципы построения БД Тема 917 Лемма Если S1, S2 конфликтно-эквивалентны, то P(S1)=P(S2) Доказательство: Предположим противное, т.е.что P(S1) P(S2) Ti: Ti Tj принадлежит S1 и не принадлежит S2 S1 = …pi(A)... qj(A)… pi, qj образуют S2 = …qj(A)…pi(A)... конфликт S1, S2 не являются конфликтно-эквивалентными Замечание: из P(S1)=P(S2) не следует, что S1, S2 конфликтно-эквивалентны, контрпример S1=w1(A) r2(A) w2(B) r1(B) S2=r2(A) w1(A) r1(B) w2(B)

18 Принципы построения БД Тема 918 Теорема Граф P(S1) ацикличен график S1 является конфликтно-упорядочиваемым ( ) Предположим, что S1 - конфликтно-упорядочиваем Ss: Ss, S1 конфликтно-эквивалентны P(Ss) = P(S1) P(S1) ацикличен, поскольку ацикличен P(Ss). ( ) Пусть P(S1) ацикличен. Преобразуем график S1: (1)В качестве T1 возьмем транзакцию без входящих дуг (2)Перенесем все действия T1 в начало S1 = ……. qj(A)…….p1(A)….. (3) Теперь S1 = (4) Повторить шаги (1)-(3) для упорядочения остального! T1 T2 T3 T4

19 Принципы построения БД Тема 919 Как обеспечить упорядочиваемость графиков? Одна возможность: в процессе работы система, записать протокол ее работы и построить граф предшествования P(S); если P(S) не содержит циклов, то график был «хорошим» Другая возможность 2: предотвращать появление циклов в графе P(S) Т1 Т2... Тn Диспетчер БД

20 Принципы построения БД Тема 920 Протокол блокировки Два новых действия: заблокировать (исключительно): li (A) разблокировать: ui (A) правило #1: правильные транзакции Ti: … li(A) … pi(A) … ui(A)... правило #2: задача диспетчера обеспечить S = …….. li(A) ………... ui(A) ……... диспетчер T1 T2 Таблица блокировок нет lj(A)

21 Принципы построения БД Тема 921 Какие графики правильные? Какие транзакции правильные? S1 = l1(A)l1(B)r1(A)w1(B)l2(B)u1(A)u1(B) r2(B)w2(B)u2(B)l3(B)r3(B)u3(B) S2 = l1(A)r1(A)w1(B)u1(A)u1(B) l2(B)r2(B)w2(B)l3(B)r3(B)u3(B) S3 = l1(A)r1(A)u1(A)l1(B)w1(B)u1(B) l2(B)r2(B)w2(B)u2(B)l3(B)r3(B)u3(B) Упражнение:

22 Принципы построения БД Тема 922 График F T1 T2 l 1 (A);Read(A) A A+100;Write(A);u 1 (A) l 2 (A);Read(A) A Ax2;Write(A);u 2 (A) l 2 (B);Read(B) B Bx2;Write(B);u 2 (B) l 1 (B);Read(B) B B+100;Write(B);u 1 (B)

23 Принципы построения БД Тема 923 График F T1 T l 1 (A);Read(A) A A+100;Write(A);u 1 (A) 125 l 2 (A);Read(A) A Ax2;Write(A);u 2 (A) 250 l 2 (B);Read(B) B Bx2;Write(B);u 2 (B) 50 l 1 (B);Read(B) B B+100;Write(B);u 1 (B) A B

24 Принципы построения БД Тема 924 Правило #3 Двухфазная блокировка(2PL) Ti = ……. li(A) ………... ui(A) ……... Нет ui(*) Нет li(*) # блок. для Ti время Фаза роста Фаза сжатия

25 Принципы построения БД Тема 925 График G задержано

26 Принципы построения БД Тема 926 График G задержано

27 Принципы построения БД Тема 927 График G задержано

28 Принципы построения БД Тема 928 График H (T2 в обратном порядке) задержано

29 Принципы построения БД Тема 929 Предполагается, что транзакции, создающие тупик, отменяются –Они не имеют эффекта –Они не появляются в графике Например, график H = Следующий шаг: Показать, что правила #1,2,3 обеспечивают получение конфликтно_упорядочиваемых графиков

30 Принципы построения БД Тема 930 Что считать конфликтом для li(A), ui(A): li(A), lj(A) - конфликт li(A), uj(A) - конфликт Замечание: не образуют конфликтов следующие примеры,,... Теорема Использование правил #1,2,3 приводит к конфликтно-упорядочиваемым графикам Для помощи в доказательстве: Определение Shrink(Ti) = SH(Ti) = первая разблокировка транзакции Ti

31 Принципы построения БД Тема 931 Лемма Если Ti Tj в S, то SH(Ti) < S SH(Tj) Доказательство леммы: Ti Tj означает, что S = … pi(A) … qj(A) …; p,q образуют конфликт По правилам #1,2: S = … pi(A) … ui(A) … lj(A)... qj(A) … По правилу 3: SH(Ti) SH(Tj) Следовательно, SH(Ti) < S SH(Tj)

32 Принципы построения БД Тема 932 Доказательство теоремы: (1) Предположим, что P(S) имеет цикл T1 T2 …. Tn T1 (2) По лемме: SH(T1) < SH(T2)

33 Принципы построения БД Тема 933 В дополнение к простой двухфазной блокировке, остальные вопросы посвящены улучшению производительности и большему параллелизму. –Разделяемые блокировки –Разные уровни блокировки –Вставки, удаления и фантомы –Другие типы управления параллельным доступом

34 Принципы построения БД Тема 934 Разделяемые блокировки До сих пор: S =...l1(A) r1(A) u1(A) … l2(A) r2(A) u2(A) … На самом деле не конфликтуют Вместо этого можно ввести: S=... ls1(A) r1(A) ls2(A) r2(A) …. us1(A) us2(A)

35 Принципы построения БД Тема 935 Действия, связанные с блокировкой l-t i (A): заблокировать A в режиме t ( t is S or X ) u-t i (A): разблокировать A в режиме t ( t is S or X ) Упрощение: u i (A): разблокировать любой режим введенный транзакцией Ti для атрибута A Новое правило #1 Правильные транзакции Ti =... l-S 1 (A) … r 1 (A) … u 1 (A) … Ti =... l-X 1 (A) … w 1 (A) … u 1 (A) …

36 Принципы построения БД Тема 936 Как быть с транзакциями, которые читают и записывают один и тот же объект? Возможность 1: Потребовать исключительную блокировку Ti =...l-X 1 (A) … r 1 (A)... w 1 (A)... u(A) … Возможность 2: Повышение статуса ( нужно читать и, возможно, писать ) Ti=... l-S 1 (A) … r 1 (A)... l-X 1 (A) …w 1 (A)...u(A)… Можно рассматривать как требование второго блока для А, либо отмены разделяемого и требования исключительного блока

37 Принципы построения БД Тема 937 Новое правило #2 Задача диспетчера - обеспечить S =....l-S i (A) … … u i (A) … нет l-X j (A) S =... l-X i (A) … … u i (A) … нет l-X j (A) нет l-S j (A) Матрица совместимости Функция comp S X S true false Xfalse false

38 Принципы построения БД Тема 938 Новое правило # 3 Транзакции с двухфазной блокировкой (2PL) Нет изменений, за исключением изменения статуса: (I) Если требуется больше блокировок (например, S {S, X}) – нет изменений! (II) Если блокировка отменяется с заменой на более строгую (например, разделяемая на исключительную, S X) - она разрешена на фазе роста

39 Принципы построения БД Тема 939 Доказательство: подобно случаю X блокировок Детали: l-ti(A), l-rj(A) не сонфликтуют если comp(t,r)=true l-ti(A), u-rj(A) не конфликтуют если comp(t,r)=true Теорема Использование правил #1,2,3 с X/S блокировками приводит к конфликтно- упорядочиваемым графикам

40 Принципы построения БД Тема 940 Дополнительные типы блокировок Примеры: (1) инкрементальная блокировка (2) блокировка для обновления Пример инкрементальной блокировки Атомарное действие: INi(A) {Read(A); A A+k; Write(A)} INi(A), INj(A) не конфликтуют! A=7 A=5 A=17 A=15 INi(A) +2 INj(A) +10 INj(A) +2 INi(A) Функция comp SX I STF F XFF F IFF T

41 Принципы построения БД Тема 941 Блокировка для обновления Решение. Если транзакция Ti хочет читать A и знает, что позже возможна запись, она требует блокировки для обновления (а не разделяемой). Только в этом случае статус может быть повышен. Comp S X U S T F T X F F F U F F F Новое требование Уже действ. блокировка

42 Принципы построения БД Тема 942 Замечание: объект A может иметь одновременно несколько блокировок... S 1 =...l-S 1 (A)…l-S 2 (A)…l-U 3 (A)… l-S 4 (A)…? l-U 4 (A)…? Чтобы разрешить новую блокировку ее режим должен быть совместимым со всеми текущими блокировками

43 Принципы построения БД Тема 943 Как блокировка реализуется на практике? Каждая система имеет свои особенности (Например, может даже не обеспечивать конфликтно-упорядочиваемые графики) Можно использовать следующий (упрощенный) подход... (1)Не доверять транзакциям при блокировании/разблокировании (2)Сохранять все блокировки до завершения транзакции Число блок. время

44 Принципы построения БД Тема 944 Ti Read(A),Write(B) l(A),Read(A),l(B),Write(B)… Read(A),Write(B) диспетчер, часть I диспетчер, часть II БД таблица блокир.

45 Принципы построения БД Тема 945 Таблица блокировок (концептуально) A B C... Инф. о блокир. для B Инф. о блокир. для C если null, объект не блокирован Каждый возможный объект

46 Принципы построения БД Тема 946 Используется хэширование: A Если объект не найден в хэш-таблице, он не блокирован Инф. о блокир. для A A... H

47 Принципы построения БД Тема 947 Инф. о блокировках для A - пример тран. Реж. ожид.? Nxt T_link объект:A Груп.режим:U Ожидание:да Список: T1 S no T2 U no T3X yes К другим записям Т3

48 Принципы построения БД Тема 948 Какие объекты мы блокируем? ? Отнош. A Отнош. B... кортеж A кортеж B кортеж C... Диск. блок A Диск. блок B... БД

49 Принципы построения БД Тема 949 Блокирование работаеи во всех случаях, но должны ли мы блокировать большие или маленькие объекты? Если мы блокируем большие объекты (например, отношения) –Нужно хранить и обрабатывать меньше блокировок –Меньше возможностей для параллельного доступа Если мы блокируем маленькие объекты(например, кортежи или отдельные поля) –Нужно хранить и обрабатывать больше блокировок –Больше возможностей для параллельного доступа

50 Принципы построения БД Тема 950 Можно использовать и то и другое!! Спросите любого санитара про решение... холл Каб. 1Каб. 2Каб. 3Каб. 4 туалет

51 Принципы построения БД Тема 951 Примеры R1 t1 t2t3 t4 T1(IS) T1(S), T2(S) R1 t1 t2t3 t4 T1(IS) T1(S), T2(IX) T2(IX)

52 Принципы построения БД Тема 952 Пример R1 t1 t2t3 t4 T1(IS) T1(S), T2(IX) T2(IX)

53 Принципы построения БД Тема 953 Множественная детализация (многоуровневая блокировка) CompRequestor IS IX S SIX X IS Holder IX S SIX X

54 Принципы построения БД Тема 954 Множественная детализация (многоуровневая блокировка) Функция Comp Требующий IS IX S SIX X IS Держатель IX S SIX X TTTTF F F F FFFFF FFFT FTFT FFTT Режим блок. Доступный режим родителя блок. потомка IS IX S SIX X P C IS, S IS, S, IX, X, SIX [S, IS] not necessary X, IX, [SIX] none

55 Принципы построения БД Тема 955 Правила (1) Следовать функции совместимости comp (2) Вначале потребовать блокировку корня, для любого режима (3) Узел Q может быть блокирован транзакцией Ti в режиме S или IS только если родитель(Q) блокирован той же транзакцией Ti в режиме IX или IS (4) Узел Q может быть блокирован транзакцией Ti в режиме X,SIX,IX только если родитель(Q) блокирован той же транзакцией Ti в режиме IX,SIX (5) Ti использует двухфазную блокировку (6) Ti может разблокировать узел Q только если ни один из потомков Q не блокирован той же транзакцией Ti

56 Принципы построения БД Тема 956 Упражнение: Может ли T2 получить доступ к f 2.2 в режиме X ? Какие блокировки будут получены T2 в результате? R1 t1t1 t2t2 t3t3 t4t4 T 1 (IX) f 2.1 f 2.2 f 3.1 f 3.2 T 1 (IX) T 1 (X)

57 Принципы построения БД Тема 957 Упражнение: Может ли T2 получить доступ к f 2.2 в режиме X ? Какие блокировки будут получены T2 в результате? R1 t1t1 t2t2 t3t3 t4t4 T 1 (X) f 2.1 f 2.2 f 3.1 f 3.2 T 1 (IX)

58 Принципы построения БД Тема 958 Упражнение: Может ли T2 получить доступ к f 3.1 в режиме X ? Какие блокировки будут получены T2 в результате? R1 t1t1 t2t2 t3t3 t4t4 T 1 (S) f 2.1 f 2.2 f 3.1 f 3.2 T 1 (IS)

59 Принципы построения БД Тема 959 Упражнение: Может ли T2 получить доступ к f 2.2 в режиме S ? Какие блокировки будут получены T2 в результате? R1 t1t1 t2t2 t3t3 t4t4 T 1 (IX) f 2.1 f 2.2 f 3.1 f 3.2 T 1 (SIX) T 1 (X)

60 Принципы построения БД Тема 960 Упражнение: Может ли T2 получить доступ к f 2.2 в режиме X ? Какие блокировки будут получены T2 в результате? R1 t1t1 t2t2 t3t3 t4t4 T 1 (IX) f 2.1 f 2.2 f 3.1 f 3.2 T 1 (SIX) T 1 (X)

61 Принципы построения БД Тема 961 Операции вставки и удаления Вставка Модификация правил блокировки: (1) Получить исключительную блокировку на объект A перед удалением A (2) При вставке A транзакцией Ti, она получает исключительную блокировку на объект A A Z a...

62 Принципы построения БД Тема 962 Все еще есть проблемы: Фантомы Пример: отношение R (E#,name,…) ограничение: E# является ключом использовать блокировку кортежей RE#Name…. o155Smith o275Jones

63 Принципы построения БД Тема 963 T1: Вставить в R T2: Вставить в R T1 T2 S1(o1) S2(o1) S1(o2) S2(o2) Проверить ограничение Вставить o3[99,Gore,..] Вставить o4[99,Bush,..] Решение Использовать многоуровневую блокировку Перед вставкой Q, блокировать parent(Q) в X... R1 t1 t2t3

64 Принципы построения БД Тема 964 Вернемся к примеру T 1 : Вставить T 2 : Вставить T 1 T 2 X 1 (R) Проверить ограничение Вставить U(R) X 2 (R) Проверить ограничение Ошибка! e# = 99 уже в R! delayed

65 Принципы построения БД Тема 965 Вместо использования R, можно использовать индекс на R: Пример: R индекс 0

66 Принципы построения БД Тема 966 Далее Управление параллельным доступом для древовидных структур данных Параллельный доступ с проверкой достоверности

67 Принципы построения БД Тема 967 Пример A B C D EF Доступ ко всем объектам происходит через корень, с помощью указателей T 1 блок Можно ли разблокировать A Если он больше не нужен?

68 Принципы построения БД Тема 968 Идея: обход с использованиемОбезьяньей лестницы A B C D EF T 1 блок

69 Принципы построения БД Тема 969 Почему это работает ? Предположим, все Ti начинаются с корня; требуя исключительной блокировки Ti Tj Ti блокирует корень раньше Tj Работает даже если не всегда начинаем с корня Root Q T i T j

70 Принципы построения БД Тема 970 Правила: древовидный протокол (исключительные блокировки) (1) Первая блокировка Ti может быть для любого элемента (2) После этого, элемент Q может быть блокирован транзакцией Ti только если parent(Q) блокирован это транзакцией (3) Элементы могут быть разблокированы в любой момент (4) После того как Ti разблокировала Q, она не может его вновь заблокировать

71 Принципы построения БД Тема 971 Древовидный протокол обычно используется для параллельного доступа к B-tree Например, во время вставки родитель не разблокируется до тех пор, пока не будет ясно, что потомок не будет расщеплен корень

72 Принципы построения БД Тема 972 Проверка достоверности Транзакции имеют 3 фазы: (1) Чтение –Все нужные значения БД прочитаны в рабочую (временную) память –Нет блокировок (2) Проверка достоверности –Проверить, что до сих пор график является упорядочиваемым (3) Запись –Если проверка была успешной, записать в БД

73 Принципы построения БД Тема 973 Ключевая идея Сделать проверку атомарной Если T 1, T 2, T 3, … порядок, для которого происходит проверка, то результирующий график будет конфликтно-эквивалентным графику S s = T 1 T 2 T 3... Для реализации проверки достоверности система поддерживает два множества: FIN = транзакции, завершившие фазу 3 (следовательно – полностью завершенные) VAL = транзакции, успешно завершившие фазу 2 (проверку достоверности)

74 Принципы построения БД Тема 974 Пример того, что должна предотвращать проверка: RS(T2)={B} RS(T3)={A,B} WS(T2)={B,D} WS(T3)={C} время T 2 начало T 2 проверена T 3 проверена T 3 начало =

75 Принципы построения БД Тема 975 T 2 закончила фазу 3 Пример того, что должна предотвращать проверка: RS(T2)={B} RS(T3)={A,B} WS(T2)={B,D} WS(T3)={C} время T 2 начало T 2 проверена T 3 проверена T 3 начало = разрешать T 3 начало

76 Принципы построения БД Тема 976 Другой пример того, что проверка должна предотвращать: RS(T2)={A} RS(T3)={A,B} WS(T2)={D,E} WS(T3)={C,D} время T 2 проверена T 3 проверена заверш. T 2 дефект: w 3 (D) w 2 (D)

77 Принципы построения БД Тема 977 заверш. T 2 Другой пример того, что проверка должна предотвращать: RS(T2)={A} RS(T3)={A,B} WS(T2)={D,E} WS(T3)={C,D} time T 2 проверена T 3 проверена разрешать заверш. T 2

78 Принципы построения БД Тема 978 Правила проверки достоверности для Tj : (1) Когда Tj начинает фазу 1: ignore(Tj) FIN (2) Во время проверки Tj: если check (Tj) то [ VAL VAL U {Tj}; выполнить фазу записи; FIN FIN U {Tj} ]

79 Принципы построения БД Тема 979 Процедура проверки сheck (Tj): для Ti VAL - ignore (Tj) выполнить если [ WS(Ti) RS(Tj) OR Ti FIN ] то RETURN false; RETURN true; Не является ли такая проверка слишком ограничительной ?

80 Принципы построения БД Тема 980 Улучшенная процедура проверки сheck (Tj): для Ti VAL - ignore (Tj) выполнить если [ WS(Ti) RS(Tj) OR (Ti FIN AND WS(Ti) WS(Tj) )] то RETURN false; RETURN true;

81 Принципы построения БД Тема 981 Упражнение: T: RS(T)={A,B} WS(T)={A,C} V: RS(V)={B} WS(V)={D,E} U: RS(U)={B} WS(U)={D} W: RS(W)={A,D} WS(W)={A,C} начало проверена завершение

82 Принципы построения БД Тема 982 Управление параллельным доступом с проверкой достоверности (называемое также оптимистичным контролем параллельного доступа) полезно в некоторых случаях: - Конфликты редки - Имеется достаточно системных ресурсов - Имеются динамически формируемые ограничения целостности

83 Принципы построения БД Тема 983 Итоги Изучили механизмы управления параллельным доступом, используемые на практике - двухфазная блокировка (2 PL) - многоуровневая блокировка - древовидные протоколы - проверка достоверности