race and deadlock

acid.sql

-- Транзакция - связанный набор операций
--
-- Atomicity Атомарность, выполняется либо целиком, либо целиком откатывается/отменяется
-- Вася  Петя
-- 20    10
-- 20-10
-- СБОЙ СИСТЕМЫ
--       10+10

-- Consistency Консистентность, после завершения транзакции система должна оказаться в непротиворечивом состоянии
-- Граф A <-> B
-- NodeID (not null),   ParentId (not null, FK NodeId)
-- BEGIN
-- A                    Null (Запрещено ключами)
-- B                    A
-- UPDATE table SET ParentID = B where NodeID = A
-- COMMIT

-- Isolated Изолированность - Транзации происходящие одновременно с текущей не должны влиять
-- Durable Надежность – Как только произошел коммит, никакой сбой произошедший после коммита не должен на него повлиять

-- Atomicity транзакция выполняется либо полностью либо откатывается целиком
-- Consistency если база данных находится в консистентном состоянии (все инварианты выполнены),
--              то после транзакции база останется в консистентном состоянии
--              внутри транзакции консистентность может нарушаться
-- Isolation эффекты одних транзакций не должны влиять на другие транзакции
-- Durability эффекты от завершенной транзакции должны быть устойчивыми

-- Transaction последовательность операций либо выполняется либо отклонояется


-- Инварианты:
-- Суммарный баланс не должен меняться
-- Баланс >= 0
drop table if exists account;
create table account(client varchar(100) primary key, balance int);
insert into account values
('vasya', 100),
('petya', 200);
select * from account;

-- do check in application petya's balance >= 100
-- BEGIN;
update account set balance = balance - 100 where client = 'petya';
update account set balance = balance + 100 where client = 'vasya';
-- COMMIT;
-- ROLLBACK;
select * from account;


-- Race Condition (Lost Update)

-- Connect1                 Connect2
-- read petya               read petya
-- check petya balance      check petya balance
-- petya -100
-- write 100
--                          petya -200
--                          write 0

BEGIN;
select * from account;
UPDATE account set balance = balance + 10 where client = 'petya';
select * from account;
ROLLBACK;

-- Одновременно во втором коннекте НАЧАЛО
BEGIN;
select * from account;
UPDATE account set balance = balance + 20 where client = 'petya';
select * from account;
COMMIT;
-- Одновременно во втором коннекте КОНЕЦ

-- Option 1 прервать
-- Option 2 перезапустить

-- Deadlock

select * from account;
BEGIN;
UPDATE account set balance = balance + 10 where client = 'petya';
select * from account;
UPDATE account set balance = balance - 10 where client = 'vasya';
select * from account;
COMMIT;

-- Одновременно во втором коннекте НАЧАЛО
select * from account;
BEGIN;
UPDATE account set balance = balance - 10 where client = 'vasya';
select * from account;
UPDATE account set balance = balance + 10 where client = 'petya';
COMMIT;
-- Одновременно во втором коннекте КОНЕЦ

-- Lock, Unlock, Read, Write
-- p == petya
-- v == vasya

-- T1               T2
-- lock(p)
--                  lock(v)
-- read(p)
--                  read(v)
-- write(p)
--                  write(v)
-- lock(v) <- Ждём T2
--                  lock(p) <- Ждём Т1
--                  обнаружена блокировка
--                  rollback T2:
--                  unlock(v)
-- блокировка v успешна
-- read(v)
-- write(v)
-- commit:
-- unlock(v)
-- unlock(p)

-- Список Блокировок
-- T1: p
-- T2: v

-- Граф ожидания
-- T1 <-> T2 (цикл в графе)

-- Процесс поиска блокировок периодически строит граф и ищет в нём циклы

-- Read-Write lock
--      R   W
-- R    +   -
-- W    -   -

-- CAP-theorem consistency/availability/partition-tolerance
-- BASE - Basically Available, Soft state, Eventually Consistent
-- stale/fair

use se;
show schemas;
show tables;

# Cycle
drop table if exists graph;
create table graph(
    id INT primary key,
    parent_id INT not null,
    FOREIGN KEY (parent_id) references graph(id)
);
select * from graph;

# 1, 2
# 2, 1

insert into graph values (1, 2);
insert into graph values (2, 1);

insert into graph values
    (1, 2),
    (2, 1);

insert into graph values (1, NULL);
insert into graph values (2, 1);
UPDATE graph set parent_id = 2 where id = 1;

insert into graph values (1, 1);
insert into graph values (2, 1);
UPDATE graph set parent_id = 2 where id = 1;
select * from graph;

-- mysql not support deferred checks
set foreign_key_checks = 0;
BEGIN;
insert into graph values (1, 2);
insert into graph values (2, 1);
COMMIT;
set foreign_key_checks = 1;

-- copy from console 2
# use se;
# SET SESSION TRANSACTION ISOLATION LEVEL READ UNCOMMITTED;
# BEGIN;
# select * from t;
# ROLLBACK;
#
# SET SESSION TRANSACTION ISOLATION LEVEL READ COMMITTED;
# BEGIN;
# UPDATE t set b = b + 1 WHERE a = 1;
# COMMIT;
#
# SET SESSION TRANSACTION ISOLATION LEVEL REPEATABLE READ;
# BEGIN;
# insert into t values (3, 3);
# select * from t;
# COMMIT;
#
# SET SESSION TRANSACTION ISOLATION LEVEL SERIALIZABLE;
# BEGIN;
# insert into t values (4, 4);
# select * from t;
# COMMIT;

show schemas;
create schema if not exists se;
use se;

drop table if exists t;
create table t (a int primary key, b int);
insert into t values (1, 1), (2, 2);
select * from t;


-- READ UNCOMMITTED
-- READ COMMITTED
-- REPEATABLE READ
-- SERIALIZABLE

-- Isolation Level     Dirty Read              Nonrepeatable Read  Phantom Read            Serialization Anomaly
-- Read uncommitted    Allowed, but not in PG  Possible            Possible                Possible
-- Read committed      Not possible            Possible            Possible                Possible
-- Repeatable read     Not possible            Not possible        Allowed, but not in PG  Possible
-- Serializable        Not possible            Not possible        Not possible            Not possible

-- Lost Update (невозможен)
-- T1                       T2
-- BEING
-- b = b + 1 where a = 1    BEGIN
--                          b = b + 2 where a = 1
-- COMMIT
--                          COMMIT

-- Первый пользователь попытался купить билет
-- Второй пользователь в этот момент увидел что билет куплен
-- У первого пользователя не хватило денег и он отказался

-- Dirty Read
-- T1                       T2
-- b = b + 1 where a = 1
--                          select b
-- rollback

SET SESSION TRANSACTION ISOLATION LEVEL READ UNCOMMITTED;
BEGIN;
UPDATE t set b = b + 1 WHERE a = 1;
select * from t;
ROLLBACK;

show processlist;
kill connection 19;
kill query 19;

-- Non repeatable read
-- T1                       T2
-- select b
--                          b = b + 1 where a = 1
-- select b
-- rollback

SET SESSION TRANSACTION ISOLATION LEVEL READ COMMITTED;
BEGIN;
select * from t;
-- update in t2
select * from t;
ROLLBACK;

-- Phantom read
-- T1                       T2
-- select b
--                          insert b (3, 3)
-- select b
-- rollback

SET SESSION TRANSACTION ISOLATION LEVEL REPEATABLE READ;
BEGIN;
-- select * from t;
-- insert in t2
-- select * from t;
-- mysql does not allow phantom reads, but allow phantom writes
select * from t;
-- insert in t2
update t set b = 10 where a = 3;
select * from t;
COMMIT;

-- Самая строгая изоляция
SET SESSION TRANSACTION ISOLATION LEVEL SERIALIZABLE;
BEGIN;
select * from t;
update t set b = 3 where a = 3;
select * from t;
COMMIT;

-- Нормальные формы
-- Дублирование
-- Аномалии DML
-- Неконсистентность

-- 1НФ
-- Нет повторений
-- Все значения скалярны
drop table if exists cars;
create table cars (brand varchar(100), model varchar(100));
insert into cars values ('BMW', 'X5, X7'), ('NISSAN', 'GT-R'), ('NISSAN', 'GT-R');
select * from cars;

drop table if exists cars;
create table cars (brand varchar(100), model varchar(100), primary key (brand, model));
insert into cars values
    ('BMW', 'X5'),
    ('BMW', 'X7'),
#     ('NISSAN', 'GT-R'),
    ('NISSAN', 'GT-R');
select * from cars;


-- 2НФ
-- 1НФ +
-- Каждый неключевой атрибут неприводимо зависит от каждого потенциального кллюча
-- (схемы с простыми ключами всегда во 2НФ)
-- Аномалии:
-- Избыточность
-- Нельзя создать склад без деталей
-- Удаление детали приводит к потере склада
drop table if exists store;
create table store (
    store varchar(100),
    detail varchar(100),
    count int,
    address varchar(100),
    primary key (store, detail));
insert into store values
('main', 'monitor', 10, 'bakinsky 15'),
('main', 'laptop', 10, 'bakinsky 15'),
('aux', 'mouse', 1, 'kuznetsky 18');
select * from store;

-- Разбиваем составной ключ

drop table if exists stores;
create table stores (
    store varchar(100) primary key,
    address varchar(100));
insert into stores values
('main', 'bakinsky 15'),
('aux', 'kuznetsky 18');

drop table if exists details;
create table details(
    store varchar(100),
    detail varchar(100),
    count int,
    primary key (store, detail),
    foreign key (store) references stores(store)
);
insert into details values
('main', 'monitor', 10),
('main', 'laptop', 10),
('aux', 'mouse', 1);

select * from stores;
select * from details;

select * from stores s join details d on s.store = d.store;

-- 3НФ
-- 2НФ +
-- Ни один неключевой отрибут не находится в зависимости от потенциального ключа
-- (Есть транзитивные зависимости между атрибутами)
drop table if exists employee;
create table employee (name varchar(100) primary key, department varchar(100), phone varchar(100));
insert into employee values
('[email protected]', 'development', '101'),
('[email protected]', 'development', '101'),
('[email protected]', 'qa', '103');
select * from employee;

-- НФБК 3+НФ Бойс Кодд
-- Более строгая 3НФ
-- Каждая нетривиальная неприводимая слева функциональная зависимость
-- имеет в качестве своего детерминанта некоторый потенциальный ключ
-- (Нет зависимостей внутри ключа)
drop table if exists supplier;
create table supplier(
    code int,
    supplier varchar(100),
    detail varchar(100),
    count int,
    primary key (code, supplier, detail));
insert into supplier values
(1, 'gl', 'internet', 100),
(1, 'gl', 'tv', 10),
(2, 'papa', 'pizza', 5);
select * from supplier;

-- 4НФ
-- НФБК +
-- Все нетривиальные многозначные зависимости фактически являются функциональными зависимостями от потенциальных ключей
-- Аномалии:
-- При добавлении пиццы или района необходимо добавить все районы/пиццы/рестораны
-- При удалении теряется информация от районах/пиццах
drop table if exists pizza;
create table pizza (
    restraunt varchar(100),
    pizza varchar(100),
    district varchar(100),
    primary key (restraunt, pizza, district));
insert into pizza values
('sovetsky', 'pepperoni', 'central'),
('sovetsky', 'margarita', 'central'),
('raduga', 'margarita', 'kirovsky'),
('raduga', 'margarita', 'rudnichny');
select * from pizza;

-- Пиццы
-- Рестораны
-- delivery, rest_district Ресторан -> Районы доставки
-- assort Ресторан -> Пиццы

-- order (delivery_id, assort_id, 10)

-- 5НФ
-- 4НФ +
-- Отсутствуют сложные соединения между атррибутами
-- Аномалии:
-- Продавец имеет право торговать только с определенными фирамами
-- данное отношение не может исключать ситуации когода отношение нарушается
drop table if exists seller;
create table seller (
    seller varchar(100),
    supplier varchar(100),
    product varchar(100),
    primary key (seller, supplier, product));
insert into seller values
('ya', 'bosch', 'refrigerator'),
('ya', 'bosch', 'cooker'),
('ya', 'lg', 'vacuum'),
('promenad', 'bosch', 'washing machine'),
('promenad', 'lg', 'vacuum');
select * from seller;
-- Необхоимо разбить на три отношения


-- ДКНФ
-- Каждое наложенное ограничение является логическим следствием  ограничений доменов и
-- ограничений ключей наложенных на данную переменную отношения
-- По-сути задание перечня допустимых значений для каждого типа

-- 6НФ
-- 5НФ +
-- Переменная отношения находится в 6НФ тогда и только тогда когда удовлетворяет всем нетривиальными зависимостям соединения
-- Декомпозиция 6НФ невозможна без потерь
-- Применяется во временных рядах
--
-- id клиента
-- Интервал дат
-- Улица   |
-- Город   |
-- Штат    | - Каждое из полей может изменяться независимоб что приводит к дублированию данных
-- Индекс  |
-- Телефон |

-- Можно разбить на отдельные отношения, но из-за того что интервалы могут не пересекаться сложно джойнить
-- circular inclusion constraint требует при наличии хотя бы одной строки из (улицы, города, штата, индекса)
-- все остальные тоже должны существовать. Это требование невозможно выполнить в современных БД,
-- поэтому ограничения выносятся в слой приложения