DBMS Implementation

关于DBMS实现上面大概分为下面三个部分的内容：

• 存储管理，包括存储器的层次结构，数据元素的存储方式，索引和多维索引。
• 查询处理，包括如何执行查询，查询编译器和优化器的结构。
• 事务处理，包括讨论如何支持事务的持久性，并发控制，以及分布式环境下的事务。
• 信息集成，对于不同数据源的管理能力。

不同DBMS实现所需要的信息类型包括：

• 数据：数据库自身内容
• 元数据：描述数据库的结构和对数据库的约束的数据库模式
• 统计量：DBMS收集和存储的关于数据库中各个关系或其他成分的大小，取值等信息
• 索引：支持对数据进行高效存取的数据结构

存储介质层次结构

@2012.05.30

介质	介绍	典型大小	访问时间
高速缓冲处理器	通常所说的CPU Cache(L1/L2/L3)	64MB	5ns
主存储器	通常所说的内存RAM	32GB	100ns
虚拟存储器	实际上就是二级存储器，和主存储器之间通信
二级存储器	通常所说的硬盘包括磁盘或者是SSD	1TB	10ms
三级存储器	通常所说的磁带等介质	1PB	10s

虚拟存储器是将二级存储器划分成为多个block.和主存储器之间移动数据是按照系统page来移动的 (通常要求系统使用页式内存管理系统).通常page size在4KB左右。

主存储器为访问任何数据提供的访问时间是不变的，磁盘访问任何数据的时间差别仅为一个很小的因数 (因为盘面转速和磁头移动速度相对来说也比较快)，而三级存储设备的访问时间是一个很宽的范围， 这取决于数据与读写点靠得有多近。

磁盘结构

对于磁盘结构的话我们有一个大致的概念即可。磁盘分为磁盘组合(disk assembly)和磁头组合(head assembly). 磁盘组合由一个或者是多个圆形的盘片(platter)组成，围绕着一根中心主轴旋转。圆盘的上下表面涂覆了一层 很薄的磁性材料，二进制位被存储在这些磁性材料上面。0由在一个方向上定向磁化的小区域表示，1则由在 相反方向上定向磁化的小区域表示。而磁头组合的话则是由多个磁头组成，每个盘面上有一个磁头，极其贴近 地悬浮在盘面上，但是绝对不与盘面接触。磁头读出经过它下面的盘面的磁方向，也能改变其磁方向，以便在磁盘上写信息。 各个磁头被固定在一个磁头臂上，所有盘面的磁头随着磁头臂一同一进一出，磁头臂是固定的磁头组合的一部分。

对于盘片(platter)的话是这么进行组织的。一盘片通常存在两个盘面。然后很多个盘片叠起来形成磁盘( 但是中间是存在空闲的以便磁头可以在盘面上操作).从垂直方向看得话，磁头组合所在盘面的位置形成柱面(cylinder). 每个盘面上有很多同心圆称为磁道(track),磁道由许多点组成，每个点代表一个由它的磁化方向决定的二进制位。 同时每个盘面也被划分称为多个扇区(sector).扇区之间通过间隙(gap)隔开。通常gap占据磁道的10%左右， 用于帮助标识扇区的起点。就读写磁盘而言，扇区是不可分割的单位，就磁盘错误而言，它也是一个不可分割的单位。 倘若一个磁化层被以某种方式损坏的话，以致于它不能在存储信息，那么那些包含这个部分的整个扇区也不再能使用。

访问效率

磁盘控制器(disk controller)则是用来管理一个或者是多个磁盘驱动器。磁盘控制器是一个小处理器，完成下面功能：

• 将磁头组合移动到某一个半径上面(也就是某一柱面上面).寻道时间(seek time)
• 选择准备读写的盘面和扇区，并且旋转磁盘组合主轴。旋转时间(rotate time)
• 读二进制数据到主存储器，或者是将主存储器数据写入。传输时间(transfer time)

通常磁盘的磁道数非常少，寻道时间在10ms左右。旋转时间需要考虑磁盘的RPM通常在5400,7200左右， 对应的旋转时间平均在10ms左右。对于磁盘顺序操作带宽在50MB/s.

为了改善访问效率，通常有下面几个策略：

• 将一起被访问的块放置在同一柱面上。
• 在几个较小的磁盘上分派数据，而不是集中在一个大的磁盘上。使用更多的可独立访问块的磁头组合。
• "镜像"磁盘. 需要磁盘控制器和调度算法的配合才能加快读写速度。
• 修改磁盘调度算法.
• 使用主存储器进行cache.

磁盘故障

磁盘故障分为下面几种类型：

• 间断性故障。读写扇区某次没有成功但是反复尝试可以成功。
• 介质损坏。一个或者是多个二进制位永久地损坏，不能够正确读取扇区。
• 磁盘崩溃。整个磁盘变为永久不可读。

对于间断性故障来说的话我们需要一种机制来区分是否读取成功。这个机制可以是驱动内置的，也可以是在 应用层面完成的。机制实现上可以有奇偶校验这样的方式。对于介质损坏来说，我们需要用来修复二进制位， 机制实现上也可以使用奇偶校验(但是只能够识别1个bit错误)或者是使用hamming code来做纠错。而磁盘崩溃的话 可以采用RAID技术来解决。在RAID里面也会使用到奇偶校验或者是hamming code纠错实现。

关于RAID在arstechnica上面阅读了一篇文章，写得非常详细，我也稍微总结了 一下

B Tree + Hash.

适合数据立方体系统的数据通常组织成为一个事实表(fact table)和若干维表.

书里面给出了几个多维索引数据结构，可以归为两类：类散列表和类树方法

• 网格文件 和 分段散列函数
• 多键索引，KD树(二叉树但是每层可以使用不同的属性做划分), 四叉树(类KD但是每层可以使用两个属性做划分), R树(类B树但是每层是高维子空间而非值范围)

查询编译器：

1. 首先分析查询表达式变为AST
2. 然后对AST进行重写产生更优的逻辑查询计划
3. 结合数据库状态对逻辑查询计划优化产生物理查询计划

产生的物理查询计划交给"查询执行"组件执行。这节主要讨论的是查询实现算法，而下一节则讨论查询优化算法。

#todo:

关于数据库系统的故障可以分为下面几种：

• 错误数据输入。这点可以从程序和数据库约束本身进行检查校验。
• 介质故障。这点之前谈过解决办法包括RAID模式，备份和冗余拷贝。
• 灾难性故障。这点和介质故障解决办法类似，但是且不能使用RAID模式。
• 系统故障。主要针对事务问题。事务在执行的时候发生断电或者是程序异常终止等情况导致事务状态丢失。

其中系统故障恢复依赖于日志技术，书里面给出了下面三种日志：

• undo log. 日志记录修改之前的值。undo log其实更常用于回滚事务(事务期间修改元素写到了磁盘上，但是之后需要回滚)。
• redo log. 日志里面记录修改之后的值。redo log常用于系统故障恢复(事务期间写到了缓冲区上并且提交，在刷到磁盘之前系统出现故障)。
• undo/redo log. 日志里面同时记录修改之前和之后的值。考虑到undo/redo log既可以用于系统故障恢复，又可以回滚事务，所以可能在真实DBMS里面使用。

通过设置检查点可以有效减少恢复过程期间的日志扫描量。此外日志技术还可以用于数据库的在线备份。

• 串行调度使得所有事务按照某种顺序执行，每个事务都是原子执行的。
• 可串行化调度没有将每个事务按照原子执行，但是保证所有事务执行完成后，数据库最终状态和某个串行调度结果一致。
• 冲突可串行性是一个用来判断可串行化的方法。这种方法假设性很强。满足冲突可串行性的调度一定是可串行化调度，但是反之却不一定。

并发控制实现有两个思路，一种是基于锁的调度，一种是基于时间戳的调度。

检测并解决死锁，最简单的方式是利用超时。对事物活跃的时间做出限制，如果事务超过这个时间就将其回滚。

信息集成有三种最常用的方式：

• 联邦数据库。数据源是独立的，但是一个数据源可以访问其他数据源信息。
• 数据仓库。将不同的数据源做格式转换合并到某一个独立的数据源里面。
• Mediation.将用户的查询翻译成为多个数据源的查询然后将结果整合。