« | August 2025 | » | 日 | 一 | 二 | 三 | 四 | 五 | 六 | | | | | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | | | | | | | |
| 公告 |
暂无公告... |
Blog信息 |
blog名称: 日志总数:3 评论数量:5 留言数量:0 访问次数:45690 建立时间:2004年12月28日 |

| |
[POSTGRES..POSTGRESQL]THE DESIGN OF THE POSTGRES STORAGE SYSTEM 读书笔记
typez 发表于 2005/1/16 16:07:04 |
POSTGRES存储管理器的设计目标:
u 提供事务管理但不需要编写大量特定的崩溃恢复(crash recovery)代码
u 使用一次写多次读(WORM)的光盘保存数据库的历史状态,而在普通磁盘上保存当前状态
u 利用专门的硬件
事务系统
每一个事务被赋予一个唯一的事务标识(XID),长度为40位。另外,一个48位交互标识(IID)中的其余8位作为该事务中命令的标识(CID)。
在事务日志(transaction log)中使用2位来指示每一个事务的当前状态:已提交(committed)、已异常终止(aborted)或正在执行(in progress)。提交一个事务的操作如下:把它在事务日志中的状态从正在执行改变为已提交,并把包含该段日志的块(block)写入到持久性的存储器(stable storage)中。
事务日志尾(tail of the log)是指事务日志中记录从最老的(oldest)活动事务(active transaction)状态直到当前事务状态的这一段日志。事务日志体(body of the log)是指事务日志中的其余部分,这部分日志中的事务状态不可能为正在执行,所以只需要分配1位来表示它们的状态。
对于事务频繁的应用程序,事务日志体可能在内存中放不下,则POSTGRES应用了一个可选的压缩技术。由于多数事务的结束状态都为已提交,所以事务日志体中包含的几乎都是“提交”位。因此,对于异常终止的事务,POSTGRES有一个可选的bloom filter[STON86]。事务日志尾是一个占用内存很小的数据结构。
当一个新的关系(relation)被创建时,POSTGRES分配一个文件用于存放该关系的记录(records)。如果一个文件中的空间被耗尽,则POSTGRES扩展该文件,扩展尺寸为多个8K的页面。
磁盘中的每条记录都有一个位掩码(bit mask)指示哪些字段(field)是非空(non-null)的,并且只有这些字段被实际存储。每条记录还包含另外的八个字段:
OID 一个系统赋予的唯一记录标识
Xmin 插入该记录的交互(interaction)的事务标识
Tmin Xmin的提交时间(该记录成为合法记录的时间)
Cmin 插入该记录的交互(interaction)的命令标识
Xmax 删除该记录的交互(interaction)的事务标识
Tmax Xmax的提交时间(该记录成为非法记录的时间)
Cmax 删除该记录的交互(interaction)的命令标识
PTR 一个向前指针(a forward pointer)
当一条记录被插入时,它被赋予一个唯一的OID,Xmin和Cmin则被设置为当前交互的标识,其余五个字段保留为空。
当一条记录被更新时,新版本和老版本通常只有少量字段会不同。为了避免存储一条全新记录的空间耗费,采用了以下所述的压缩技术。初始记录以未压缩的形式存储,并称它为锚点(anchor point)。而对于已被更新的记录,只有那些和锚点中不相同的字段才被存储。此外,锚点中的PTR字段被修改为指向已被更新的记录,它被称为一个差分记录(delta record)。连续的记录更新最终形成了一条从锚点出发的差分记录的单向链表。由于差分记录一般来说是小尺寸的对象,所以它们中的大多数很可能和锚点处于同一操作系统页面中。
一般而言,一条记录在时间T是合法的(valid at time T),如果以下条件为真:
Tmin < T and Xmin is a committed transaction and either:
Xmax is not a committed transaction or
Xmax is null or
Tmax > T
实际上,为了使用户能够读取当前事务中其它命令所写入的还未提交的记录,实际的合法性测试是以下更为复杂的条件。
Xmin = my-transaction and Cmin != my-command and T = “now”
or
Tmin < T and Xmin is a committed transaction and either:
(Xmax is not a committed transaction and Xmax != my-transaction) or
(Xmax = my-transaction and Cmax = my-command) or
Xmax is null or
Tmax > T
如果没有指定T,那么T = “now”是其缺省值,并且一条记录在时间“now”是合法的,如果:
Xmin = my-transaction and Cmin != my-command
or
Xmin is a committed transaction and either:
(Xmax is not a committed transaction and Xmax != my-transaction) or
(Xmax = my-transaction and Cmax = my-command) or
Xmax is null
一般而言,一条记录在时间段[T1, T2]是合法的(valid in the interval [T1, T2]),如果:
Xmin = my-transaction and Cmin != my-command and T2 >= “now”
or
Tmin < T2 and Xmin is a committed transaction and either:
(Xmax is not a committed transaction and Xmax != my-transaction) or
(Xmax = my-transaction and Cmax = my-command) or
Xmax is null or
Tmax > T1
T1和T2都可以被省略,其相应的缺省值为T1 = 0 以及 T2 = +infinity
并发控制和时间戳管理
POSTGRES使用传统的内存锁表(main memory lock table)实现了一个标准的两段式加锁策略。
POSTGRES使用如下的技术来异步地填充Tmin和Tmax字段。POSTGRES包含一个TIME关系(relation)用于存储每一个事务的提交时间。由于时间戳是32位无符号整数,所以字节4*j到4*j+3用于存储事务j的提交时间。当事务提交时,系统读取当前时间并存入TIME关系相应的槽(slot)中。
POSTGRES中的每一个关系创建时都会被标记为以下三种指示之一:
u no archive: 指示不需要对关系的历史记录进行访问
u light archive: 指示需要一个存档(archive)但期望很少对它进行访问
u heavy archive: 指示需要经常对存档进行访问
对于“no archive”状态的关系,Tmin和Tmax永远不会被填充,因为从不需要对历史记录进行访问。
如果指定了“light archive”,则允许对历史记录进行访问。当Tmin或Tmax必须和某些特定的值进行比较时,系统从TIME关系中取出相应事务的提交时间以进行比较。
当处于“heavy archive”条件时,运行时系统使用和“light archive”的情况相同的方法来查找事务的提交时间。然而,它随之把该值写入记录的Tmin或Tmax中,因而把对历史记录的读取操作转变为了写入操作。随后任何访问该记录的合法性验证都不再需要对TIME关系的额外访问。
记录访问
通过顺序扫描可以访问关系中的记录。每个包含记录的页都有一个前向和后向指针,分别指向前一页和后一页。每一页中都有一个行表(line table)[STON76],由指向该页中锚点起始位置的指针组成。
当插入一条记录时,系统构造一个新的锚点并在所有二级索引(secondary index)中插入相应的索引条目(index entry)。每一个索引记录包含键值以及指向被索引记录所在页中行表中的一个入口。该行表入口指向实际的记录。该单级间接访问方式允许锚点在数据页中移动而不必对二级索引进行维护。
当更新一条已存在的记录时,系统构造一个差分记录并链接入相应的锚点记录。如果更新不涉及被索引的字段,则不需要对二级索引进行维护。如果有被索引字段的更新,则会在相应的索引中插入一个新的条目(entry),该条目包含键值和指向锚点记录的指针。在二级索引中不包含直接指向差分记录的指针。因此,只能通过获取相应的锚点并通过向前链接来访问一个差分记录。
使用该技术保证了在更新记录时,只有当二级索引中的键值被改变时才会产生I/O活动。因为一般来说不会改变被索引字段的值,所以确保了二级索引只需要进行少量的插入操作。
归档系统(THE ARCHIVAL SYSTEM)
系统使用一个后台进程(daemon)把不再合法的记录清扫入存档中。该被称为真空吸尘器(vacuum cleaner)的后台进程通过以下的命令被调用:
vacuum rel-name after T
其中T是相对于现在(“now”)的时间差。
该真空吸尘器查找满足以下条件中某个条件的归档候选记录:
Xmax is non empty and is a committed transaction and “now” - Tmax >= T
Xmax is non empty and is an aborted transaction
Xmin is non empty and is an aborted transaction
在上述第二和第三钟情况下,该真空吸尘器仅单纯地回收被记录使用的空间。在第一种情况下,记录必须被拷贝到存档中,除非其所属的关系设置了“no-archive”状态。另外,如果关系被指定了“heavy-archive”,而且在以前的访问中Tmin和Tmax字段还没有被赋值,那么在归档过程中该真空吸尘器必须填充它们。而且,如果可以将锚点和多个差分记录
一起清扫,那么真空化(vacuuming)过程会更有效率。因此,一般来说真空吸尘器会一次性清扫多个记录的链表(chain)。
真空化过程(The Vacuum Process)
真空化过程包括三个阶段,也即:
阶段1: 写入一个归档记录以及相关的索引记录
阶段2: 在当前数据库中写入一个新的锚点
阶段3: 回收旧锚点和它的差分记录所占用的空间 |
|
|