高并发环境下的数据库对象空间管理策略研究与实现

摘要

数据库对象（表或者索引）的空间管理是数据库系统的关键问题，当数据库进行插入时，需要在对象的物理空间中寻找一个可用的页面，这个查找过程既要保证高性能，又要尽可能利用好有限的物理空间。在当前的商业数据库系统中，通常使用空闲空间链表或者页面空闲空间位图等物化数据结构来达到这一目标。
　　然而随着计算机CPU数目和内存容量的飞速增长，数据库系统所承受的并发负载与日俱增。在高并发的在线事务型应用系统中，当对一个对象产生高并发的插入操作时，传统的数据结构和搜索算法已经不能满足实际需求，往往会产生对同一页面的资源争夺而引起并发瓶颈，或是物理空间的快速浪费。
　　在本文中，我们提出了一种新的数据库对象空间管理方法3LSM(3-LayerSpaceManagement)。3LSM方法使用了三层结构来管理数据库对象的空间:在线程级缓存中，对线程私有的页面进行管理，以降低对并发资源的访问;在全局缓存中，通过多入口结构降低全局缓存的并发冲突，通过对页面的轮询分配，消除对同一页面的竞争;在物理存储空间级别，使用异步搜索的策略，通过后台线程来将物理页面装载到全局缓存中。
　　3LSM方法充分考虑了时间和空间上可能产生的瓶颈，使数据库对象空间管理在高并发环境中有良好的延展性。通过基于TPC-C事务的模拟实验，我们证明了相比传统的对象空间管理算法，3LSM方法在高并发环境下，随着并发负载的增加，吞吐率以接近线性的方式增长;尽管3LSM方法的空间利用率不如传统的对象空间管理方法，但两者的差距较小。

目录

摘要

图目录

表目录

第1章 绪论

1．1 课题背景

1．2 研究动机

1．3 本文研究内容

1．4 本文结构

1．5 本章小结

第2章 基础知识与相关工作

2．1 数据库存储层次与空间分配

2．2 传统数据库的对象空间管理

2．2．1 PostgreSQL对象空间管理

2．2．2 Oracle段空间管理

2．2．3 HY(n，u)算法

2．3 数据库并发控制

2．3．1 基于锁的并发控制

2．3．2 时间戳排序并发控制

2．3．3 多版本并发控制

2．4 本章小结

第3章 问题定义

3．1 形式化定义

3．2 基准解决方案

3．2．1 PostgreSQL对象空间分配策略

3．2．2 PostgreSQL空间分配策略并发冲突分析

3．3 本章小结

第4章 3LSM对象空间管理方法

4．1 基础概念

4．2 整体框架

4．2．1 3LSM对象空间分配算法

4．2．2 缓存一致性问题

4．3 线程级缓存管理

4．4 段搜索全局缓存管理

4．4．1 设计准则

4．4．2 数据结构

4．4．3 全局缓存搜索算法

4．5 物理存储空间管理

4．5．1 数据结构

4．5．2 关键算法与并发协议

4．6 本章小结

第5章 实验结果和分析

5．1 实验环境和实验设计

5．2 参数对3LSM方法性能的影响

5．2．1 缓存结点数目对3LSM方法的影响

5．2．2 K值对3LSM方法的影响

5．3 PG策略与3LSM方法的性能对比

5．3．1 吞吐率的对比

5．3．2 并发冲突的对比

5．3．3 空间利用率的对比

5．3．4 临界区长度对吞吐率的影响

5．4 本章小结

第6章 总结和展望

6．1 全文总结

6．2 展望

参考文献

攻读硕士学位期间主要的研究成果

致谢