数据库管理系统优化（NAND Flash）

摘要

　　NAND Flash通过Flash转换层把线性地址的Flash抽象成磁盘驱动器,-使得基于磁盘驱动器的传统算法可以无需任何修改就能实现所有功能。但是由于NANDFlash的写速度小于读速度而且由写前擦除引起的擦除操作时间损耗很大,当写操作是随机的中小型写操作时,NAND Flash的写性能甚至差于磁盘的写性能。随机的中小型写操作是一些数据库应用系统的常用操作,比如在线联机处理系统,因此为了有效的使用NAND Flash作为数据库存储介质,必须修改传统数据库管理系统的体系结构和算法。

　　本文首先分析NAND Flash的两种典型的Flash转换层:FTL和NFTL。NFTL的内存消耗量适中,适用于大容量NAND Flash,因此本文选择NFTL作为未来数据库管理系统的Flash转换层。其次提出评价基于NFTL的算法的性能的NEWOM模型,NEWOM模型改进于EWOM模型。再次使用NEWOM模型分析数据库管理系统的相关算法的I/O性能:分析排序算法和连接算法,得出影响其性能的因素和I/O性能公式;分析三种数据库页布局的优缺点和基于PAX页布局的RARE连接算法;由于NAND Flash的不同读写速度,缓冲区命中率不能正确反映缓冲区I/O性能,所以分析缓冲区管理算法:LRU算法和CFLRU算法。然后根据以上分析提出设计基于NAND Flash的数据库管理系统的方法:擦除单元块内日志页方法。擦除单元块内日志页方法改进于页内日志页方法,采用PAX页布局,消除了PAX页布局在多属性值更新时的缺陷。通过仿真实验证明擦除单元块内日志页方法相对于页内日志方法能提高日志页的利用率,减少内存消耗。为了进一步提高数据库管理系统的性能和降低成本,最后本文提出基于日志磁盘的擦除单元块内日志页方法,其用磁盘保存日志记录,用NAND Flash保存数据。通过仿真实验证明基于日志磁盘的擦除单元块内日志页方法的I/O性能优于页内日志方法和擦除单元块内日志页方法的I/O性能。

　　关键词：NAND Flash;数据库管理系统;写前擦除;日志页

　　人类社会已经进入信息社会,而数据库技术就是实现信息化的主要技术之一。数据库技术的核心是数据库管理系统,简称DBMS。

　　从最早的商业计算机开始,数据处理就一直推动着计算机的发展。实际上数据处理自动化早于计算机的出现。Hellerith发明的穿孔卡片,早在20世纪初就用来记录美国的人口普查数据,并用机械系统来处理穿孔卡片,然后列出结果。穿孔卡片后来被广泛的用于将数据输入计算机的一种手段。

　　数据处理技术的发展和计算机的数据存储技术发展密不可分。20世纪50年代和60年代早期,磁带技术被用于数据存储。磁带和卡片都是顺序存取,并且磁带的容量比内存大得多,因此数据处理程序被迫用一种特定的顺序处理通过读取和合并来自磁带和卡片的数据。20世纪60年代末磁盘的广泛使用,极大的改善了数据处理的情况,因为磁盘允许直接对数据进行存取。磁盘上的数据的位置变得相对磁带来说己经无关紧要,因为磁盘上的任何位置都可以在几十毫秒内进行存取。数据在一定程度上摆脱了顺序访问的限制。有了磁盘,我们才可以创建网络和层次的数据库,因为可以把表和树这样的数据结构保存在磁盘上的。正是由于磁盘技术的发展,才有了数据库管理系统的诞生。数据库技术发展已经40多年,从最初的层次模型、网络模型、到现在的流行的关系模型,所有数据库管理系统输入输出的相关算法都是优化对磁盘数据的输入输出性能。

　　1989年,东芝公司发布了NAND Flash结构,强调降低每比特的成本,更高的性能,并且象磁盘一样可以通过接口轻松升级。NAND Flash中的NAND表示Flash的技术架构;单词NAND来源于英文词组NotAnd,表明电路采用与非门实现。如今日益普及的PDA、MP3播放器、数码照相机、移动电话、高档笔记本等移动计算设备广泛采用NAND Flash作为数据的持久性存储介质。从1996年起,NAND Flash芯片的密度以超过两倍的年速度发展。到2007年,三星公司己经发布了32GB的NAND Flash芯片。从2003年起,NAND Flash芯片技术的发展符合ehang一gyuHwang的闪存发展模型。根据ehang一gyuHwang的闪存发展模型,到2012年,每个NAND Flash芯片的容量达到25OGB,到2014年,每个NAND Flash芯片的容量将达到ITB。多颗NAND Flash芯片可以封装成固态硬盘。固态硬盘可以取代传统的磁盘,而整个计算机系统其它组成却不需要改变。在高档的笔记本市场,固态硬盘己经占据着相当一部分份额。由于NAND Flash是电子设备,相对磁盘具有轻薄、功耗低、无噪音、抗震能力强、读写速度是磁盘的100倍以上等优势。随着NAND Flash的密度不断增大,容量也随之不断增大;生产工艺的进一步发展和市场占有率的提高,价格在不断下降;NANDFla户的应用研究的发展,使用更加高效,因此由NAND Flash封装成的固态硬盘对传统的磁盘市场产生的巨大的冲击。可以预见NAND Flash将在不久的将来取代磁盘成为数据库系统的持久性数据存储设备。

　　NAND Flash的数据以比特的形式保存在存储单元中,按每个存储单元保存的比较的数量,可以把NAND Flash分类为MLCNAND Flash和SLCNAND Flash,其中MLC每个存储单元保存2比特数据,而SLC每个存储单元保存储数据。存储单元以s个或者16个位单元连成比特线(bitline),形成s位字节或者16位字。比特线再组成扇区(sector)(也称为NAND Flash页,为了区别操作系统的页机制和数据库管理系统的输入输出数据页,本文采用扇区称谓。

　　每个扇区除了保存数据的主要区域(mainarea)外,还包含空闲区域(sP盯earea),也称为Out Of Band,简称OOB。扇区主要区域大小一般为512B、ZKB或4KB,扇区的OOB的大小一般为16B。OOB一般用来保存错误探测和纠错码或者其他软件应用信息。扇区是NAND Flash的读写基本单位。由于NAND Flash不支持就地更新(in一Placeupdate),所以NAND Flash的写操作必须在空白扇区上,否则就需要先擦除,然后再写,这就是NAND Flash的写前擦除特性。而写前擦除是以擦除单元块为基本单位的,每个擦除单元块有多个扇区组成,典型的由32个、64个或128个扇区组成一个擦除单元块。

　　数据库管理系统优化方法：

缓冲区大小的影响

事务的平均日志长度的影响

随机读写次数的影响

目录

　　学位论文原创性声明和学位论文版权使用授权书
　　摘要
　　AbstraCt
　　目录
　　插图索引
　　附表索引
　　第1章 绪论
　　　　1.1 研究的背景及意义
　　　　1.2 NANDFlash结构
　　　　1.3 NANDFlash的特性
　　　　1.4 基于NANDFlash的DBMS面临的问题
　　　　1.5 本文的研究工作
　　　　1.6 论文结构
　　第2章 性能评价模型
　　　　2.1 引言
　　　　2.2 FTL
　　　　2.3 NFTL
　　　　2.4 NFTL优化技术
　　　　　　2.4.1 查找表技术
　　　　　　2.4.2 扇区缓冲技术
　　　　2.5 EWOM模型
　　　　2.6 基于NFTL的NEWOM模型二
　　　　2.7 小结
　　第3章 基于NANDFlash的DBMS的算法1/0性能分析
　　　　3.1 引言
　　　　3.2 排序
　　　　　　3.2.1 外部归并排序算法介绍
　　　　　　3.2.2 外部归并排序算法性能分析
　　　　3.3 传统连接算法
　　　　　　3.3.1 块嵌套连接算法
　　　　　　3.3.2 归并连接算法
　　　　　　3.3.3 散列连接算法
　　　　3.4 RARE连接算法
　　　　　　3.4.1 NSM和DSM页布局
　　　　　　3.4.2 PAX页布局
　　　　　　3.4.3 RARE连接算法
　　　　3.5 缓冲区管理算法
　　　　　　3.5.1 最近最少使用算法
　　　　　　3.5.2 最近最少使用算法性能分析
　　　　　　3.5.3 CFLRU算法
　　　　3.6 小结
　　第4章 擦除单元块内日志页方法
　　　　4.1 引言
　　　　4.2 页内日志方法
　　　　　　4.2.1 页内日志方法介绍
　　　　　　4.2.2 页内日志方法的缺点
　　　　4.3 擦除单元块内日志页方法
　　　　　　4.3.1 基本定义
　　　　　　4.3.2 写回策略
　　　　　　4.3.3 数据页读写方式
　　　　　　4.3.4 缓冲区管理算法
　　　　　　4.3.5 合并算法
　　　　　　4.3.6 页布局和连接算法
　　　　4.4 性能评价
　　　　4.5 小结
　　第5章 基于日志磁盘的LPIEB方法
　　　　5.1 引言
　　　　5.2 磁盘与NANDFlash混合存储系统
　　　　　　5.2.1 传统DBMS的日志磁盘系统
　　　　　　5.2.2 磁盘和NANDFlash混合存储系统
　　　　5.3 基于日志磁盘的LPIEB方法
　　　　　　5.3.1 基本定义
　　　　　　5.3.2 写回策略
　　　　　　5.3.3 合并算法
　　　　5.4 性能评价
　　　　5.5 小结
　　结论与展望
　　参考文献
　　致谢

（如您需要查看本篇毕业设计全文，请您联系客服索取）