reference from youtube channel

• https://www.youtube.com/watch?v=k8V7tK2RvoE&list=PLzzVuDSjP25T_5nRkp-QDjoqGTGIH_XOq&index=8
• https://www.youtube.com/watch?v=ht8Tx6DWn_E

1.Oder of transaction

• Serial schedule 串行调度
  each transaction runs from start to end without any interveting actions from other transaction.所有事务排队，一个接着一个串行执行,即不允许事务并发

• Schedules are equivalent

  • 2 schedules has the same transactions
  • 2 schedules has the same final state

• Sehedule S is serializable if: S == to some serial schedule
  例子，有2个事务T1，T2. 则说明有2种串行调度s1=T1T2 或者s2=T2T1. 如果S是可串行的，则说明S和s1或者s2等价的

2. Conflicting Operation冲突操作

conflict operation(read/write) -> different final state of database

• 2 operations are conflict if: 2个read操作的事务不会导致冲突
  • by different transactions
  • on the same object
  • at least one of them is write

3. Conflict Serializable Schedule

• Schedules are conflict equivalent:
  • same action of same transactions
  • evera pair of conflicting actions is ordered the same way
• Sehedule S is conflict serializable: 和serializable唯一的不同是不冲突的action的顺序不一样，但是冲突action的顺序必须一样。 所以说conflict serialized is conservative serialized schedule。
  • S conflict equivalent to some some serial schedule
  • implies S is also serializable
    
    
    
    

4.Two phase locking 2PL

• Rules:
  • a transaction must obtain an shared lock(Read Lock) before it reads an object and it must obtain exclusive lock(Write Lock) before it write the object.
    
  • a transaction can not get new locks after it releases any locks

2PL guarantee conflict serializabiliy bot not cascading abort

When a transaction has reached the end of ots acquision phase, it has everythinf it needs locked and any conflicting transactions either:
* started release phase before this point
* are blocked waiting for this transction
这种情况下非常容易形成死锁

Cascding abort

rollback of T1 requires rollback of T2(dirty read)

Strict 2PL

to avoid cascading abort

• same as 2PL, except all locks released together when transaction commits!
  

5. Lock Management

• Lock and unlock request habdled by Lock Manager(Sperr-Manager)
• Lock Manager maintains a hashtable, keyed on names of objects being locked
• Lock Manager keeps an entry for each currently held lock
• Entry:
  • Granted Set: transactions have succeeded in getting their lock requests fulfilled
  • Lock mode (shared or exclusive)
  • Wait Queue
    
    对于A， T1 和 T2 都有获得 read Lock（S mode），T3，T4 等待write lock（X lock）
• Wenn lock request arrives:
  • check the geanted set
    • if no, put the request into granted set
    • if yes, put the request into wait queue
• Lock upgrade: shared lock -> exklusive lock

6. Dead Locks

• Three ways dealing with deallocks
  • prevention
  • avoidance
  • detection and resolution
• Some system doesn't handel deadlock and just use timeout

Dead lock prevention

• handeled by OS (may be restart transaction, mark the transaction,which was restarted again)

Dead lock avodance

• priority bages on age: (now - start_time)
  Ti wants a lock that Tj holds
  • Ti > Tj -> Ti wait or Ti die
  • Ti > Tj -> Tj abort or Ti wait

Dead lock detection

create a "wait-for" graph, if there is a cycle, then there is dead lock
Ti wants a lock that Tj holds: Ti is waiting for Tj

T1 is waiting for T2 T1 -> T2

• how to do deadlocak detection
  • periodically run the wait-for graph
  • find cycles
  • shoot the transaction on the cycle

7. Lock Granularity, what is to lock(锁的精细度)

• Tradeoff
  • fine graned will be nice, but the lock table will be large
  • grob granued will be nice, but transactions can not be synchronous

Multiple locking granilarity

shouldn't have same decision for all transactions

Granularity hierarchy

Wenn a transaction locks a node in the tree explicitly, it implicitly locks all the node's descendants/below in the dame node

If you get a shared lock on T1, you would implicitly have a shared lock on all the objects below T1

• if we want the advance of both trade off, the solution: intent lock protocol

Intention locks

before getting S or X lock, transaction must habe proper intent locks on all its ancestors祖先 int the hierachy tree.

1. Each transaction starts from the root of the hierarchy
2. To get S or IS lock on a node, must hold IS or IX on parent node
3. To get X or IX or SIX on a node, must host IX or SIX on parent node
4. release locks in bottom up order

• Protocol is correct in that it is equivalent to directly setting locks as leaf levels

Lock compatibility matrix

SIX mode: S and IX at the same time

• Idea: If two locks are compatible on those 2 tuples, then their intent locks should be compatible on page P
  S lock on t1 and X lock on t2 from different transtions: compatible -> IS lock on P and IX lock on P compatibale from different transtions
  

8. Isolation levels

What can be conflict result

The phenomena which are prohibited at various levels are:

dirty read

A transaction reads data written by a concurrent uncommitted transaction.
```
write write read
```

nonrepeatable read

A transaction re-reads data it has previously read and finds that data has been modified by another transaction (that committed since the initial read).
```
read write read
```

phantom read

A transaction re-executes a query returning a set of rows that satisfy a search condition and finds that the set of rows satisfying the condition has changed due to another recently-committed transaction.
```
read insert/delete read
```

serialization anomaly

The result of successfully committing a group of transactions is inconsistent with all possible orderings of running those transactions one at a time.

The SQL standard and PostgreSQL-implemented transaction isolation levels are described in Table 13.1.

9. MVCC

Writers do not block readers and readers do not block writers
Read-only transaction can read a consistent snapshot without acquiring locks

example1

My timestamp of T1(A) > then begin time of latest version A0

write transaction create an other version A1 with begin timestamp 2

update the transaction A0 end time at 2

Maintain a transaction status table with timestamp
T1's timestamp is betwenn 0 and 2, so it reads version A0. This avoid repeatable problem

example2

T2 reads version A0 because T1 has not commited

Wait for write commit of T1

update transaction status table with commit

T2(W(A)) create a new version with begin time 2 and version 1 end with time2