Database Concurrency Summary

数据库并发控制

Concurrency control

ACID principle for transaction management

Atomicity 原子性 “all or none”

事务所做操作要么全部提交要么全部失败回滚

• 实现： 日志, Shadow paging

Consistency 一致性 “looks correct”

• 数据库一致性 仍遵循完整性约束 未来事务能看到过去事务造成的后果

• 事务一致性 事务前后数据库内容一致 一致意味着多个事务访问相同数据得到相同结果

Isolation 隔离性 “lives alone”

事务所作修改提交前对其他事务不可见

• 两种类别的并发控制协议来保证隔离性
  • 悲观 从最初就避免问题的发生
  • 乐观 假设冲突发生不常见，发生后再处理

Durability 持久性 “survives failure”

事务提交的修改应被持久化，即便系统崩溃也不受影响

Conflict Serializability in transaction scheduling

• Schedules are equivalent to some serial schedule.
• This is what (almost) every DBMS supports when you ask for the SERIALIZABLE isolation level.
• Schedule S is conflict serializable if you are able to transform S into a serial schedule by swapping consecutive non-conflicting operations of different transactions.
• Verify using either the swapping method or dependency graphs.
• A schedule is conflict serializable if and only if its dependency graph is acyclic.

Consistency Conflicts in transaction management

• 读写冲突：
  • 不可重复读 “non-repeatable read” 两个读的中间数据被另一个事务覆写并提交 导致第二次读的同一行值不同
    • transaction reads committed UPDATES from another transaction. The same row now has different values than it did when your transaction began.
    • A non-repeatable read occurs, when during the course of a transaction, a row is retrieved twice and the values within the row differ between reads.
  • 幻读 “phantom read” 两个读的中间被另一个事务插入/删除行并提交 导致第二次读返回的行不同
    • Phantom reads are similar but when reading from committed INSERTS and/or DELETES from another transaction. There are new rows or rows that have disappeared since you began the transaction.
    • A phantom read occurs when, in the course of a transaction, two identical queries are executed, and the collection of rows returned by the second query is different from the first.
  • 避免不可重复读锁行就足够，避免幻影读则需要锁表
• 写读冲突： 脏读 “dirty reads” Reading uncommitted data 读了另一个事务没有提交的数据
• 写写冲突：丢失修改 “lost updates” overwriting uncommitted data 一个事务覆盖另一个事务没有提交的数据

Pessimistic Concurrency Control

Two-Phase Locking CC protocol

• Pessmistic 悲观的 assume there are a lot of contentions in transactions 因此安全程度高 但并发能力会有所限制 (not allow all serializable schedules)

• Two basic types of locks & compatibility matrix

  • Write lock X (exclusive) Read lock S (shared)

• 2PL always gurantee conflicts-serializable schedule = grantee serializable schedule

• 二个阶段 “/\”

  • 生长期 只允许拿锁
  • 收缩期 一旦释放第一个锁 进入收缩期
    • 只允许释放锁 或不释放锁
    • 不允许拿锁

• Problem: can have cascading abort in case of dirty reads 例如t1写 t2读 此时t1还没commit便abort 此时t2不得不abort…如果t2也写了还没来的及提交后面还有读的那这个反应会连锁下去

• Solution: Strong Strict 2PL (SS2PL) 一个事务提交/abort后才允许放锁 一次放完

• Deadlock handling:

  • Detection:
    • run backgroud task that periodically checks for cycles in waits-for graph / 超时检测
    • selects a victim to rollback and breaks the cycle 选择标准和rollback程度取决于具体设计
  • Prevention:
    • assign priority based on timestamp older timestamp = higher priority
    • after comparison, one will get lock, the other waits, this essentially breaks deadlock.

Locking Granularities and hierarchy

MySQL 中提供了两种封锁粒度：行级锁以及表级锁。
应该尽量只锁定需要修改的那部分数据，而不是所有的资源。锁定的数据量越少，发生锁争用的可能就越小，系统的并发程度就越高。
但是加锁需要消耗资源，锁的各种操作（包括获取锁、释放锁、以及检查锁状态）都会增加系统开销。因此封锁粒度越小，系统开销就越大。
在选择封锁粒度时，需要在锁开销和并发程度之间做一个权衡。

• 一个事务想要更新1billion tuples = ask for locks 1 billion times VERY SLOW
• WE NEED a lock hierarchy that reflects what is down there (行级) at high level (表级)

如何更方便的进行多粒度封锁： 意向锁

• 意向锁Intention lock: “lock escalation” 细粒度锁太多时动态的分配可用的粗粒度锁 大大减少lock manager需要处理的锁的请求数量

  Intention locks allow a higher level node to be locked in shared or exclusive mode without having to check all descendant nodes. If a node is in an intention mode, then explicit locking is being done at a lower level in the tree. 基本相当于告诉你下面有什么样的锁 通过兼容矩阵 可以从hierarchy高处如表级快速判断能不能读/写下层具体行的数据

• Intention-Shared (IS):下面某个地方有读锁

  • Intention-Exclusive (IX):下面某个地方有写锁

• Shared+Intention-Exclusive (SIX): 整个子树可共享读，下面某个孩子有写锁

• 各种锁的兼容关系如下：

  
  
  解释如下：
  • 任意 IS/IX 锁之间都是兼容的，因为它们只表示想要对表加锁，而不是真正加锁；
  • 这里兼容关系针对的是表级锁，而表级的 IX 锁和行级的 X 锁兼容，两个事务可以对两个数据行加 X 锁。（事务 T₁ 想要对数据行 R₁ 加 X 锁，事务 T₂ 想要对同一个表的数据行 R₂ 加 X 锁，两个事务都需要对该表加 IX 锁，但是 IX 锁是兼容的，并且 IX 锁与行级的 X 锁也是兼容的，因此两个事务都能加锁成功，对同一个表中的两个数据行做修改。）

三级封锁协议

• 一级封锁协议 事务 T 要修改数据 A 时必须加 X 锁，直到 T 结束才释放锁。可以解决丢失修改问题
• 二级封锁协议 在一级的基础上，要求读取数据 A 时必须加 S 锁，读取完马上释放 S 锁。可以解决读脏数据问题
• 三级封锁协议 在二级的基础上，要求读取数据 A 时必须加 S 锁，直到事务结束了才能释放 S 锁。可以解决不可重复读的问题

MySQL 隐式与显示锁定

MySQL 的 InnoDB 存储引擎采用两段锁协议，会根据隔离级别在需要的时候自动加锁，并且所有的锁都是在同一时刻被释放，这被称为隐式锁定。
InnoDB 也可以使用特定的语句进行显示锁定：

SELECT ... LOCK In SHARE MODE;
SELECT ... FOR UPDATE;

Optimistic Concurrency Control

Ensure ordering using different methods. Assume they are good, handle problems later.

Basic Timestamp ordering (T/O) CC protocol

• Basic idea: assign unique fixed monotonically increasing numeric value “timestamp” to determine commit order.

  • different schemes for implementing timestamp: system clock, logical counter…

• Timestamp smaller TS(i) < TS(j) = transaction i appears before j.

• Method:

  • Transaction r/w object without locks.
  • Every object X is tagged with timestamp of last txn that successfully did read / write. R-TS(X) / W-TS(X)
  • Reads
    • Check timestamp for every operations, if txn k tries to access an object from the future, TS(k) < W-TS(X), (timestamp order of k violates writer of X), k aborts and restarts with newer TS.
    • Otherwise allow txn k to read X, update R-TS(X) = max(R-TS(X), TS(k)), make a local copy of X to ensure repeatable reads for k. (subsequent read occurs in local copy)
  • Writes
    • If TS(k) < R-TS(X) or TS(k) < W-TS(X) abort and restart k.
      • opitimization: in case of write can simply ignore and continue “thomas write rule” this allow us to even commit it. Somewhat useful but will not give us a conflict serializable schedule.
    • else allow k to write X and update W-TS(X), make a local copy of X to ensure repeatable reads for k. (subsequent read occurs in local copy)

• Comments:

  • Can gurantee to generate a conflict serializable schedule if do not use “Thomas write rule”
  • No deadlocks because no “waiting” at all.
  • Can have starvation for long tens if shorter one keep causeing conflicts.
  • permits schedules that are not recoverable 可恢复事务: 他读到的所有事务在他之前commit
  • high overhead of copying data to local workspace and updating timestamps.

Optimistic CC (OCC) protocol

• Basic idea: No locks at all.

  • DBMS creates a private workspace for each transaction
  • any obj read is copied into thread local workspace for following r/w, perform modifications at local workspace
  • Validation: when commits, DBMS compares local workspace to see if it incurrs conflicts with other txns. Get a timestamp.
  • Atomic install to global database if no conflicts.

• 3 Phases

  • 1. Read: make w/r modifications at private thread local workspace
    2. Validation: check if conflicts exist before commit, get a timestamp
    3. Write: valid => apply local changes to global database, abort & restart otherwise.

• Serial Validation Explained

  • Maintain a global view of all active txns.
  • record w/r set while txns running and write into private workspace
  • execute validation and write phase in a protected critical section
  • when txn invokes COMMIT, DBMS checks existence of conflicts through methods like the following, it checks if 双方write set intersects, if so, abort (myself) .
    • Backward Validation: look at all older txns in the system
    • Forward Validation: look at all younger txns in the system.

• Comments:

  • OCC Works well when #conflicts is low, transactions read heavy, mostly accessing disjoint subsets of data. In this case locking is wasteful.
  • High overhead of copying data to local space. Serial Validation/Write bottlenecks. Aborts more wasteful than 2PL because txns have already executed. The validation step also need latches when comparing read write sets because maybe T2 is writing while T1 is reading. latch contention when a lot of concurrent txns ?

Partition-based Timestamp ordering protocol

• Idea:
  • partition db into disjoint subsets called partitions / shards so that we do not need locks.
  • Queued up & assign timestamps upon arrival to order txns for serial execution at each partition. NO Concurrency THIS IS SINGLE-THREADED.
  • Partitions are protected by a single lock. A txn acquires the partition’s lock if it has the lowest timestamp in queue, it starts when it has all the locks of partitions it needs (r/w).
    • A txn can read anything in the partition it have locked
    • write occurs in place, maintains a in-mem buffer to undo changes if aborted.
    • abort & restart if accessing a partition that it does not have the lock.
  • Only check conflicts between txns within same partitions.
  • The finer-grained each partition is the more parallelism we get on disjoint sets of data
• Comments:
  • Fast: when DBMS knows what partitions txn needs before it starts, most txns only need to access a single partition.
  • Mult-partition txns are slower, some partitions can be idle.

Phantom problem

• The above discussed protocols only deal with read/update. But if we have insertions / updates / deletions, we can have the phantom problem.
  • 2PL cannot solve this because these new rows do not even have locks.
  • Predicate locking can solve it but too hard to implement.
  • Index locking can solves it

Isolation Level

产生并发不一致性问题的主要原因是破坏了事务的隔离性，解决方法是通过并发控制来保证隔离性。并发控制可以通过封锁来实现，但是封锁操作需要用户自己控制，相当复杂。数据库管理系统提供了事务的隔离级别，让用户以一种更轻松的方式处理并发一致性问题。

• RU: 事务中的修改，即使没有提交，对其它事务也是可见的。
• RC: 一个事务只能读取已经提交的事务所做的修改。
• RR: 保证在同一个事务中多次读取同一数据的结果是一样的。
• S: 强制事务串行执行，这样多个事务互不干扰，不会出现并发一致性问题。从MVCC并发控制退化为基于锁的并发控制。不区别快照读和当前读，所有的读操作都是当前读，读加读锁（S锁），写加写锁（X锁）。在该隔离级别下，读写冲突，因此并发性能急剧下降，在MySQL/InnoDB中不建议使用。

Multi-version concurrency control

• “Let writers make a “new” copy while readers use an appropriate “old” copy.”

• 最常见的并发控制方法 DBMS. 非常适合读多写少的OLTP workload 可以提供rr级别的隔离程度

• 读=读一个版本 写=创建一个新版本 版本号一般是通过时间戳机制分配

• 只有 写写冲突 通过first commiter/first updater win 解决

• RC RR隔离级别下使用版本链 多个版本的快照存在undo日志中，日志通过回滚指针把一个数据行的所有快照连起来

• MVCC 维护一个read view结构 读的时候判断数据行快照是否可以使用

• mvcc下快照读select…不需要锁，当前读（涉及插入删除更新）仍需要锁

• mysql为了解决rr级别下当前读的幻读问题，使用了next-key lock本质上是索引锁+间隙锁 = 不仅锁定了索引还锁定了索引之间的间隙 就相当于数学上一个大区间中间很多个小区间 我在小区间端点上加锁之外还要在间隙上加锁才能保证安全性

关系数据库设计理论

函数依赖

记 A->B 表示 A uniquely determines B，也可以说 B functionaly dependent on A。

Full Functional Dependency : X is functionally dependent on Y and is not functionally dependent on any proper subset of Y.

A Partial Functional Dependency is when you have a Composite Primary Key (a primary key that is made up of multiple columns), and one of the non-key columns is functionally dependent on a proper subset of the columns that make up the Composite Primary Key.

对于 A->B，B->C，则 A->C 是一个传递函数依赖。

For example : Let there be a relation R ( Course, Sid , Sname , fid, schedule , room , marks )

Full Functional Dependencies : {Course , Sid) -> Sname , {Course , Sid} -> Marks, etc.

Partial Functional Dependencies : Course -> Schedule , Course -> Room

异常

以下的学生课程关系的函数依赖为 {Sno, Cname} -> {Sname, Sdept, Mname, Grade}，键码为 {Sno, Cname}。也就是说，确定学生和课程之后，就能确定其它信息。

Sno	Sname	Sdept	Mname	Cname	Grade
1	学生-1	学院-1	院长-1	课程-1	90
2	学生-2	学院-2	院长-2	课程-2	80
2	学生-2	学院-2	院长-2	课程-1	100
3	学生-3	学院-2	院长-2	课程-2	95

不符合范式的关系，会产生很多异常，主要有以下四种异常：

• 冗余数据：例如 学生-2 出现了两次。
• 修改异常：修改了一个记录中的信息，但是另一个记录中相同的信息却没有被修改。
• 删除异常：删除一个信息，那么也会丢失其它信息。例如删除了 课程-1 需要删除第一行和第三行，那么 学生-1 的信息就会丢失。
• 插入异常：例如想要插入一个学生的信息，如果这个学生还没选课，那么就无法插入。

范式

范式理论是为了解决以上提到四种异常。

高级别范式的依赖于低级别的范式，1NF 是最低级别的范式。

1. 第一范式 (1NF)

原子属性不可分。

2. 第二范式 (2NF)

1NF+每个非主属性不存在部分函数依赖(完全函数依赖于主属性/主键)。

可以通过分解来满足。

Sno	Sname	Sdept	Mname	Cname	Grade
1	学生-1	学院-1	院长-1	课程-1	90
2	学生-2	学院-2	院长-2	课程-2	80
2	学生-2	学院-2	院长-2	课程-1	100
3	学生-3	学院-2	院长-2	课程-2	95

以上学生课程关系中，{Sno, Cname} 为主键，有如下函数依赖：

• Sno -> Sname, Sdept
• Sdept -> Mname
• Sno, Cname-> Grade

Grade 完全函数依赖于主键，它没有任何冗余数据，每个学生的每门课都有特定的成绩。

Sname, Sdept 和 Mname 都部分依赖于主键，当一个学生选修了多门课时，这些数据就会出现多次，造成大量冗余数据。

分解后

关系-1

Sno	Sname	Sdept	Mname
1	学生-1	学院-1	院长-1
2	学生-2	学院-2	院长-2
3	学生-3	学院-2	院长-2

有以下函数依赖：

• Sno -> Sname, Sdept
• Sdept -> Mname

关系-2

Sno	Cname	Grade
1	课程-1	90
2	课程-2	80
2	课程-1	100
3	课程-2	95

有以下函数依赖：

• Sno, Cname -> Grade 完全函数依赖

3. 第三范式 (3NF)

2NF + 非主属性不存在“传递函数依赖”。

关系-1 中存在以下传递函数依赖：

• Sno -> Sdept -> Mname

可以把它分解成以下两个表：

Sno	Sname	Sdept
1	学生-1	学院-1
2	学生-2	学院-2
3	学生-3	学院-2

Sdept	Mname
学院-1	院长-1
学院-2	院长-2

ER 图

• 一对多：带箭头的线
• 一对一：双向带箭头线
• 多对多：不带箭头的线

表示出现多次的关系

一个实体在联系出现几次，就要用几条线连接。

下图表示一个课程的先修关系，先修关系出现两个 Course 实体，第一个是先修课程，后一个是后修课程，因此需要用两条线来表示这种关系。

## 表示子类

# Indexing

• data can only have one actual order sorted by a order

• https://blog.csdn.net/jiadajing267/article/details/54581262

• Clustered : actually order data the same way as index key

• non-clustered: only a list of reference

• index-key what the sort order is based on

• b+树 叶子层有序数组链表+非叶子层平衡多叉树有序索引 同时支持高效等值查询和范围查询 （节点内有序可以2分搜索）

• b+树与b树区别： b+树非叶节点 相当于多级索引，不含指向record的指针 （节省空间储存更多索引项） 叶子层是有序数组链表

• 为什么适合储存：b+树节点要求半满 而且因为是多路查找树 节点内容多 相比红黑 高度压缩非常明显 树的访问查找效率和高度直接相关 b+树非常矮 大大减少IO次数 更适合文件系统和数据储存 支持bulk-loading 更适合文件系统和数据储存

• InnoDB和MyISAM的区别

  1. InnoDB 支持事务，MyISAM 不支持事务。这是 MySQL 将默认存储引擎从 MyISAM 变成 InnoDB 的重要原因之一；

  2. InnoDB 支持外键，而 MyISAM 不支持。对一个包含外键的 InnoDB 表转为 MYISAM 会失败；

  3. InnoDB 是聚集索引，MyISAM 是非聚集索引。聚簇索引的文件存放在主键索引的叶子节点上，因此 InnoDB 必须要有主键，通过主键索引效率很高。但是辅助索引需要两次查询，先查询到主键，然后再通过主键查询到数据。因此，主键不应该过大，因为主键太大，其他索引也都会很大。而 MyISAM 是非聚集索引，数据文件是分离的，索引保存的是数据文件的指针。主键索引和辅助索引是独立的。

  4. InnoDB 不保存表的具体行数，执行 select count(*) from table 时需要全表扫描。而MyISAM 用一个变量保存了整个表的行数，执行上述语句时只需要读出该变量即可，速度很快；

  5. InnoDB 最小的锁粒度是行锁，MyISAM 最小的锁粒度是表锁。一个更新语句会锁住整张表，导致其他查询和更新都会被阻塞，因此并发访问受限。这也是 MySQL 将默认存储引擎从 MyISAM 变成 InnoDB 的重要原因之一；

Nosql

better suited for unstructured data

打赏