跳到主内容

how to read paper?

在学习分布式系统和数据库的道路上看了很多论文, 最近开始上中阶课程uc cs262, 是数据库红宝书的作者Joseph M. Hellerstein开的哦,这门课是一个论文选读课吧。第一节课就是学习如何读论文,这里做个记录,以后自己读论文也要按照这个方法读。

更多…

brpc阅读笔记

brpc是百度最近开源的一个项目,以优秀文档著称,其文档考虑了实际应用中的种种场景,公认为一个优秀的开源项目。特定过来学习一番。

更多…

how to prove the Log Matching Property of Raft

最近在跟着6.824实现raft协议,lab很有趣,也推荐喜欢分布式的同学做做。 其中,lab2b需要实现其中的日志复制,而日志复制满足Log Matching Property:

  1. 在不同server中的日志中,存在两条记录, 他们的term和index都相等,那么这两条记录存有相同的指令
  2. 在不同server中的日志中,存在两条记录,它们的term和index都相等,那么这两条记录前的所有记录都相同

论文1 中粗略介绍了如何使用归纳法证明,但是感觉还是不容易看懂,这里就做一个思考纪录, 给出一个比较详细的证明.

更多…

Charpter 2 of 《Transaction Processing》

物理数据库中的操作

逻辑数据库中的元组集合被存储在一个底层物理数据库中,由固定大小的数据页组成,这些页存储在非易失的随机访问存储器中, 一般是磁盘。为了读取或更新逻辑数据库中的元组,包含该元组的页必须先从磁盘中读取到数据库的内存缓存中,被更新的页之后被写回磁盘,替代旧版本。 数据库管理系统的缓存管理模块管理经常访问的数据库页,使之尽可能久地保存在缓存中, 以减少昂贵的随机读写需求.

在本章中,我们讨论物理数据库中的主题: 逻辑数据库层的事务管理和逻辑数据库行为所触发的底层物理数据库结构的管理之间的相互影响. 这些主题包括数据库的基于页的构造, 在缓存中固定页以减少访问页时间, 物理数据库中的完整性约束,将页锁起来以防止其他并发线程导致影响, 实现在物理数据库中的结构修改作为一个原子操作序列,

2.1 服务器中的数据结构和处理

两个持久话(非易失)的数据集合维护在事务服务器中:

  1. 数据磁盘: 包含数据库的关系、索引和系统目录或数据字典
  2. 日志磁盘: 包含为数据库更新的日志记录

当数据库的一个实例在运行时,以下易失性数据结构维护在服务器进程的虚拟内存中:

  1. 缓存池或数据库缓存,缓存从磁盘中读取的数据库页.
  2. 日志缓存(log buffer), 用于缓存日志文件.
  3. 活跃事务表, 存储关于活跃事务的信息.
  4. 修改页表, 存储关于缓存页的信息.
  5. 锁表, 存储被活跃事务持有锁的信息(当事务并发控制是基于锁实现时)
  6. 其他易失结构, 比如一个查询计划缓存,存储可重用的已编译的查询执行计划

数据磁盘和数据库缓存基于数据库页的随机访问(通过页标识码), 而日志磁盘和日志缓存是只可顺序添加的文件. 每个数据库更新操作在一个从数据磁盘中读入数据库缓存的页上, 该更新以一条日志条目添加到日志缓存中。该日志记录持有足够的信息,保证能够重做对页上旧版本数据的更新(当更新因为错误而丢失时)或者撤销该更新(在事务回滚的时候).

在事务提交或日志缓存满的时候, 日志中的内容被刷新到日志磁盘中,这些日志记录被添加到上一次刷入的结尾. 因此,每一个提交的事务都至少将它的所有更新持久化到日志磁盘。

在基于日志的系统中,事务处理的最重要的效率来源是数据磁盘不需要立刻反映事务的更新: 数据库缓存中的更新页不需要在事务提交时被写入。 为了保证操作的正确性,一个更新的数据页一定不能在更新对应的日志记录被写入前写入。

在一个数据库系统实例中, 若干数据库进程在磁盘上的共享数据以及共享虚拟内存数据结构上进行操作:

  1. 服务器进程和它们的线程(前面提到的), 响应从应用进程过来的请求并且生成事务
  2. 数据库写进程将已更新的数据库页从缓冲区中刷入到磁盘中
  3. 日志写进程在日志缓冲满的时候或当服务器进程在事务提交时要求时,会将日志从缓冲区写入到磁盘中
  4. Checkpoint 进程周期性的设置一个checkpoint, 保证之前的相关易失数据写入到磁盘中
  5. 进程监视器进程监视系统的其他系统,并且负责故障进程的恢复,包括丢弃或回滚之前由于服务器进程发生故障而终止的事务。
  6. 锁管理器进程,为进程获取或释放数据项的锁,并且负责死锁检测。

为了减少进程间的消息数量,在许多系统中,服务器进程通过直接更新共享锁表来锁住数据项,而不是发送请求给特意的锁管理器进程。在这种情况下,锁表必须被互斥机制(信号量)或者其他任何进程间共享的虚拟内存结构。

数据页和文件

物理数据库是由包含记录的页组成的集合。页是磁盘中固定大小(比如4、8或者16 kB)的区域,一般占一个磁盘块,如果页比一个磁盘块大的话,则为几个连续的磁盘块。一个磁盘块是一个包含一个或更多在磁盘表面上同一个磁道上的连续区块。举个例子,如果块大小为8kB,sector的大小为512字节,那么一个块就包好16个连续的sector。sector是磁盘的最小可寻址单位。

物理数据库的操作包括从磁盘中取出(读)页到内存中的数据库缓存和从缓存中刷新(写)页到磁盘中。这两个操作都执行一个磁盘访问操作,包括寻找到正确的磁道和读或写组成页的连续磁盘块序列。

逻辑数据库使用物理数据库来存储页中的数据库元组来实现。包括元组的页被称为数据页。除了数据页,物理数据库还包括索引页来高效查询数据页。索引页的结构依赖于元组在页中的组织方式。为了管理数据库,存在一些其他页类型。

一个元组一般存储为数据页中的一条记录。如果一个元组比一页还大是,就需要被分为连接在一起的多条记录。

页包括一个页头,记录区域以及记录索引。页头至少包含以下信息:

  1. Page id: 页的唯一标志符
  2. Page type: "relation data page"(一个关系的元组), "cluster data page"(来自多个关系的元组), "index page"(关系索引的一部分),"free space"(一个未分配页),"data-dictionary page"(数据库的数据字典的一部分),或"storage-map page"(描述其他页的分配状态的页),以及其他.
  3. 内部标识符,关系、索引或其他页所属的结构
  4. 记录数: 该页所包含的元素数
  5. 空余空间数:用于维护该页空闲空间区域的信息,比如说最长连续空余区域的长度以及该页空闲空间的总量。
  6. Page-LSN: 最近一条对页的更新日志记录的日志序列数(LSN)。当一个缓存页更新时,页的Page-LSN被设置为本次更新的日志记录LSN. 在重启恢复时,该页在磁盘上的版本的PAGE-LSN会被用于确定这些对页的更新在系统故障时已经走了多远(详见第四章)。 在一般处理中,页的目前版本的PAGE-LSNs用于加速撤销动作(见4.3节)和索引结构的遍历(见第七章)。
  7. 下一页:在页链表中的"下一页"的页标识(依据图结构)

页的记录区域包含该页的实际数据。数据页中的内容是逻辑数据库中的元组。记录区域从头到尾填充(从页头开始).

页中的记录索引是一个在页结尾的数组m。数组的一个元素m[i]包括字节偏移量,指向记录区域的第i个记录。记录索引从结尾向上增长:m1是在页的末尾,m2在它前面。Figure2.1展示页924中在位置m3的元组。

数据库的页常常被归组为文件或者段,每一个都由一页或多个连续页组成。一般来说,分组根据记录的类型。关系型数据库的一个关系常常放置于它自己的文件中。在一些系统中,通过外键联系的两个或者多个关系的元组可以被存储在同一个文件中,这种组织形式一般被称为聚簇文件。

当然也可以将数据库管理系统的文件直接映射到操作系统提供的文件系统中的一个文件。那么,数据库系统可以使用操作系统提供的服务,数据库管理软件可以变得更小和更简单。

然而,文件系统并不能提供所有特性

Footnotes:

1

DEFINITION NOT FOUND.

2

DEFINITION NOT FOUND.

3

DEFINITION NOT FOUND.

STM学习

STM是软件事务内存(software transaction memory)的简称。 我在PPCP中对它进行了一些学习,这里做个记录。

更多…