CMU课程15-721数据库系统设计(第一周)

CMU课程15-721最新一期开课啦!

真是要强烈推荐这门课程:有在线视频,有教案,有作业,甚至还有自动评分工具,除了没老师与TA之外真的分享了几乎所有的课程资源,完全可以让我们这种墙内的后进生们自学。

课程安排

Course Introduction and History of Database Systems

以回顾数据库历史的方式串讲了数据库系统设计中的难点,也就是以后的课程内容目录:

  1. 并发控制
  2. 索引
  3. 存储模型,压缩
  4. join算法
  5. 日志与恢复
  6. 查询优化
  7. 新存储器件

未来所有作业与项目都是用C++11写的(牛逼!),准备好调试多线程
推荐每次上课前写一篇本次课阅读paper的心得,包括:主题思想(两句话)、系统使用与修改情况(一句话)、负载测试情况(一句话)

In-Memory Databases

因为新型存储器件的飞速发展导致内存数据库(其实还有内存文件系统)需求越来越强烈,原始基于硬盘为主存储结构的数据库设计因此会有哪些变化呢?

总结下传统硬盘数据库设计特点为:

  1. 使用内存做缓存池(涉及内存与磁盘上以“页”为单位的数据同步)
  2. 页为单位的索引数据组织(页号、slot号、header、tuple、blob等概念设计)
  3. 所有请求都会先经过缓存池(worker线程需要pin住该页防止被swap到磁盘)
  4. 并发控制保证事务可以等待磁盘数据读取时间,同时锁(lock)要保存到其他数据结构(非页结构)中防止被swap
  5. 使用WAL处理日志与恢复问题
  6. CPU时间统计:30%缓存池、30%锁、28%日志、12%真正操作

设计内存数据库,首先不要考虑使用mmap,缺点:内存操作无法非阻塞了、内存结构与磁盘必须相同、数据库系统不知道哪些页实际在内存中(说白了就是操作系统通用设计不可能比数据库架构师专业设计更好!)

内存数据库IO问题退居二线(DRAM 60ns, SSD 25000~30000ns),需要考虑其他性能问题:

  1. lock/latch
  2. cache-line miss
  3. pointer chasing
  4. predicate evaluations
  5. data move
  6. network

总结下设计特点为:

  1. 不需要缓存池和页结构(直接用指针取代id索引?定长或变长数据?但是一定得使用checksum保证数据正确)
  2. 获得锁时间跟获得数据时间一样!导致可能允许牺牲一点并发度(coarse-grained locking因为数据IO足够快)并且可以将锁信息与数据信息一起保存(增加CPU cache locality,mutex相对太慢,一定改用CAS)
  3. 索引设计问题凸显(需要多考虑一下CPU cache)
  4. 查询处理方式巨大改变(不需要顺序扫描,传统一次处理一个tuple方式相对太慢),考虑vector-at-a-time
  5. 仍然需要WAL,可能可以简化;仍然需要checkpoint操作

内容基本出自92年的文章: High-Performance Concurrency Control Mechanisms for Main-Memory Databases

发布第一次项目作业,等本人做完了另找时间写文章说明。

Concurrency Control I

介绍各种事务模型:nested trx、saga trx(其实在《事务处理》一书里面都已经见识过)

介绍各种并发控制方式:
Two-Phase Locking 和死锁避免方法

  • DL_DETECT
  • NO_WAIT
  • WAIT_DIE

Timestamp Ordering及优化方法

  • Basic T/O
  • MVCC
  • OCC
  • H-STORE

测试结果出自14年的文章: Staring into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores

个人补充:MC涉及多线程访问内存值,CC解决多CPU副本一致性

Memory Consistency和Cache Coherence

Concurrency Control II — Multi-versioning

详细介绍隔离级别:比可串行化级别低一些的级别,包括REPEATABLE_READS, READ_COMMITTED

  • Dirty Read 脏读(提前读到后面修改的内容)
  • Unrepeatable Read 不可重复读(事务里两次读操作,后一次读的不同)
  • Phantom Read 幻读(读到其他事务插入或删除的数据)

产品方面voltDB完美支持可串行化,oracle11g最高支持SNAPSHOT_ISOLATION级别,新增两种级别:

  • CURSOR_STABILITY 内部cursor持有锁,有时防止Lost Update(写操作覆盖顺序不对)

  • SNAPSHOT_ISOLATION 保证事务所见snapshot相同(不能强化到可串行化级别 2009新paper有可串行化snapshot方案),防止Write Skew(部分写更新)

下面介绍多版本MVCC现代实现方法(timestamp-ordered好处在于不需要lock!)

mvcc设计考虑:

  • version chains(oldest-to-newest[w],newest-to-oldest[r])
  • version storage(全量或delta存[回滚段])
  • garbage collection(额外线程或合作,GC在重写负载造成15%额外负载])

Hekaton(SQL Server)

事务开始结束都赋予时间戳, 为每个tuple维护版本链(BEGING, END, POINTER),维护全局事务状态图(ACTIVE, VALIDATING[precommited,2PL不需要这个状态,因为锁即可保证]),事务维护元数据(Read set,Write set,Scan set[避免幻读],Commit dependency),乐观事务在多核表现下明显好于悲观事务

实现方面仅使用lock-free数据结构(没有latch或spin lock,使用bw-tree和skiplist,CAS)

该系统设计11年论文:High-Performance Concurrency Control Mechanisms for Main-Memory Databases

Concurrency Control III — Optimistic

首先讨论存储过程,产生于解决使用交互API问题(可以减少网络通信次数与等待)

  • ODBC/JDBC
  • DBMS wire protocols

存储过程的问题:不好版本控制与调试,不好移植

Optimistic方法 其中validation步骤:(可以并发进行)

  • backword 与已经提交的事务判断
  • forword 与还未提交事务判断

本课未学完待补充

本站总访问量