（计算机科学与技术专业论文）基于nand+flash的数据库管理系统优化研究.pdf

基于n a n df l a s h 的数据库管理系统优化研究 摘要 n a n df l a s h 通过f l a s h 转换层把线性地址的f l a s h 抽象成磁盘驱动器，使得基 于磁盘驱动器的传统算法可以无需任何修改就能实现所有功能。但是由于n a n d f l a s h 的写速度小于读速度而且由写前擦除引起的擦除操作时间损耗很大，当写操 作是随机的中小型写操作时，n a n df l a s h 的写性能甚至差于磁盘的写性能。随机 的中小型写操作是一些数据库应用系统的常用操作，比如在线联机处理系统，因 此为了有效的使用n a n df l a s h 作为数据库存储介质，必须修改传统数据库管理系 统的体系结构和算法。 。 本文首先分析n a n df l a s h 的两种典型的f l a s h 转换层：f t l 和n f t l 。n f t l 的 内存消耗量适中，适用于大容量n a n df l a s h ，因此本文选择n f t l 作为未来数据 库管理系统的f l a s h 转换层。其次提出评价基于n f t l 的算法的性能的n e w o m 模 型，n e w o m 模型改进于e w o m 模型。再次使用n e w o m 模型分析数据库管理系 统的相关算法的i o 性能：分析排序算法和连接算法，得出影响其性能的因素和i o 性能公式；分析三种数据库页布局的优缺点和基于p a x 页布局的r a r e 连接算法； 由于n a n df l a s h 的不同读写速度，缓冲区命中率不能正确反映缓冲区i o 性能， 所以分析缓冲区管理算法：l r u 算法和c f l r u 算法。然后根据以上分析提出设计 基于n a n df l a s h 的数据库管理系统的方法：擦除单元块内日志页方法。擦除单元 块内日志页方法改进于页内日志页方法，采用p a x 页布局，消除了p a x 页布局在 多属性值更新时的缺陷。通过仿真实验证明擦除单元块内同志页方法相对于页内 日志方法能提高日志页的利用率，减少内存消耗。为了进一步提高数据库管理系 统的性能和降低成本，最后本文提出基于同志磁盘的擦除单元块内日志页方法， 其用磁盘保存r 志记录，用n a n df l a s h 保存数据。通过仿真实验证明基于日志磁 盘的擦除单元块内日志页方法的i o 性能优于页内日志方法和擦除单元块内同志 页方法的i o 性能。 关键词：n a n df l a s h ；数据库管理系统；写前擦除；日志页 i l 硕十学位论文 a b s t r a c t w i t hap r o p e rs o f t w a r el a y e r , k n o w na st h ef l a s ht r a n s l a t i o nl a y e r , w h i c h m a k e sl i n e a rn a n df l a s ha p p e a rt ou p p e rl a y e rl i k ead i s kd r i v e ，c o n v e n t i o n a l d i s k - b a s e dd a t a b a s ea l g o r i t h m sa n da c c e s sm e t h o d sw i l lf u n c t i o na d e q u a t e l yw i t h o u t a n ym o d i f i c a t i o n o nt h eo t h e rh a n d ，d u et oaf e wl i m i t a t i o n so ff l a s hm e m o r y ，t h i s a p p r o a c hi sn o tl i k e l yt oy i e l dt h eb e s ta t t a i n a b l ep e r f o r m a n c e b e c a u s ew r i t i n ga s e c t o ri sm u c hs l o w e rt h a nr e a d i n gas e c t o ra n do v e r w r i t i n gas e c t o rm u s tb e p r e c e d e db ye r a s i n g t h ee r a s eu n i tc o n t a i n i n gt h es e c t o r ，t h ee f f e c t i v e w r i t e b a n d w i d t ho ff l a s hm e m o r yi se v e nw o r s et h a nd i s k n a n df l a s hh a sp o o rw r i t e p e r f o r m a n c e ，p a r t i c u l a r l yw h e ns m a l l - t o - m o d e r a t e s i z e dw r i t e sa r er e q u e s t e di na r a n d o m ，w h i c hi sq u i t eac o m m o na c c e s sp a t t e r nf o rd a t a b a s ea p p l i c a t i o n ss u c ha s o n 1 i n et r a n s a c t i o np r o c e s s i n g ( o l t p ) s oi no r d e rt oe f f e c t i v e l yu t i l i z ef l a s hm e m o r y a sd a t as t o r a g em e d i a ，w eh a v et oa l t e rs o m ed a t as t r u c t u r e sa n da l g o r i t h m so f d a t a b a s em a n a g e m e n ts y s t e m i n t h i sp a p e rw ea n a l y z en a n df l a s h st w of l a s ht r a n s l a t i o nl a y e r s ：f t la n d n f t l w ec h o o s en f t la st h ef u t u r ef l a s ht r a n s l a t i o nl a y e rf o ri t sm o d e r a t em a i n m e m o r yc o s t f t li sp o p u l a ri n s m a l ls i z en a n df l a s ha n dt h e r ei sa l g o r i t h m p e r f o r m a n c em o d e lo nf t l ，b u tt h e r ei sal a c ko fa l g o r i t h mp e r f o r m a n c em o d e lo n n f t l s ow ep r e s e n tn e w o mm o d e la sa l g o r i t h mp e r f o r m a n c em o d e lo nn f t l ， w h i c hi s i m p r o v e df r o me w o mm o d e l o nf t l t h e nw ea n a l y z et h es o r t i n g a l g o r i t h ma n dj o i na l g o r i t h m o fn a n df l a s hb a s e dd a t a b a s es y s t e m si n q u i r y p r o c e s s i n g ，f i n do u tt h ef a c t o r so ft h e i ri op e r f o r m a n c e ，a n dp r e s e n tt h ef o r m u l ao f t h e i ri op e r f o r m a n c e t h e nw ea n a l y z et h r e ep a g el a y o u t sa n dr a r e j o i na l g o r i t h m o np a xp a g el a y o u t ，r a r e j o i na l g o r i t h m h a sb e t t e ri o p e r f o r m a n c e t h a n g r a c e h a s hj o i n ，b u tp a xp a g el a y o u t sp e r f o r m a n c ei sw o r s et h a nn s mp a g el a y o u t f o rm u l t i p l ea t t r i b u t e s v a l u e sa r eu p d a t e d n a n df l a s h sr e a d i n gi sm u c hf a s t e rt h e n w r i t i n g ，s oh i t r a t ec a n tr e f l e c tt h em e m o r yb u f f e r si op e r f o r m a n c e ，w eh a v et o a n a l y z et h eb u f f e rm a n a g e m e n ta l g o r i t h m s ：l r ua l g o r i t h ma n dc f l r ua l g o r i t h m t h e nw ea n a l y z et h ei n p a g el o g g i n ga p p r o a c h ( i p l ) ，w h i c hh a sm a n ys h o r t c o m i n g s s ow ep r e s e n tl o g g i n gp a g ei n e r a s e b l o c ka p p r o a c h ，w h i c h i m p r o v e s t h ei p l a p p r o a c h s i o p e r f o r m a n c eb yr e d u c i n g m a i nm e m o r yc o s ta n di n c r e a s et h e u t i l i z a t i o nr a t i oo fl o g g i n gp a g e ，f u r t h e rm o r e ，w eu s ep a xp a g el a y o u ta sn a n d l i i 基于n a n df l a s h 的数据库管理系统优化研究 f l a s hb a s e dd a t a b a s em a n a g e m e n ts y s t e m sp a g el a y o u ta n dl o g g i n gp a g ei n e r a s e b l o c ka p p r o a c hc a ne l i m i n a t ep a xp a g el a y o u t s s h o r t c o m i n g w ed e m e n s t r a t et h a t l o g g i n gp a g ei n - e r a s eb l o c ka p p r o a c hh a sb e t t e ri op e r f o r m a n c et h a ni p la p p r o a c h b ys i m u l a t i o ne x p e r i m e n t i no r d e rt oi m p r o v ed b m s sp e r f o r m a n c ea n dr e d u c ei t s c o s t ，w ep r e s e n tl o gd i s kb a s e dl o g g i n gp a g ei n e r a s eb l o c ka p p r o a c h ，w h i c hu t i l i z e s d i s kt os t o r el o g ，u t i l i z e sn a n df l a s ht os t o r ed a t a a tl a s t ，w es i m u l a t et h e l o gd i s k b a s e dl o g g i n gp a g ei n - e r a s eb l o c ka p p r o a c ha n dt e s t i f yt h a tl o gd i s kb a s e dl o g g i n g p a g ei n 。e r a s eb l o c ka p p r o a c hh a sb e t t e ri op e r f o r m a n c et h a nl o g g i n gp a g ei n e r a s e b l o c ka p p r o a c ha n di p l a p p r o a c h k e yw o r d s ：n a n df l a s h ；d a t a b a s em a n a g e m e n ts y s t e m ；e r a s e - - b e f o r e w r i t e ；l o g g i n g p a g e i v 基于n a n df l a s h 的数据库管理系统优化研究 插图索引 图1 1n a n df l a s h 的典型结构2 图2 1n f t l 结构图及实例9 图3 1n s m 页布局结构2 3 图3 2d s m 页布局结构2 3 图3 3p a x 页布局结构2 4 图3 4c f l r u 算法缓冲区结构3 0 图4 1 页内日志方法相关结构3 3 图4 2 擦除单元块内日志页方法相关结构3 6 图4 3 缓冲区大小的影响4 1 图4 4 随机读写次数的影响4 2 图4 5 事务的平均长度的影响4 2 图5 1 缓冲区大小的影响4 8 图5 2 事务的平均日志长度的影响4 8 图5 3 随机读写次数的影响一4 9 v i i i 硕士学位论文 附表索引 表1 1 固态硬盘与磁盘的性能比较3 表1 2n a n df l a s h 与磁盘的访问性能比较3 表3 1r a r e 连接算法相关符号及其意义2 5 i x 硕士学位论文 1 1 研究的背景及意义 第1 章绪论 人类社会已经进入信息社会，而数据库技术就是实现信息化的主要技术之一。 数据库技术的核心是数据库管理系统( d a t a b a s em a n a g es y s t e m ) ，简称d b m s 。 从最早的商业计算机开始，数据处理就一直推动着计算机的发展。实际上数 据处理自动化早于计算机的出现。h e l l e r i t h 发明的穿孔卡片，早在2 0 世纪初就用 来记录美国的人口普查数据，并用机械系统来处理穿孔卡片，然后列出结果。穿 孔卡片后来被广泛的用于将数据输入计算机的一种手段。 数据处理技术的发展和计算机的数据存储技术发展密不可分。2 0 世纪5 0 年 代和6 0 年代早期，磁带技术被用于数据存储。磁带和卡片都是顺序存取，并且磁 带的容量比内存大得多，因此数据处理程序被迫用一种特定的顺序处理通过读取 和合并来自磁带和卡片的数据。2 0 世纪6 0 年代末磁盘的广泛使用，极大的改善 了数据处理的情况，因为磁盘允许直接对数据进行存取。磁盘上的数据的位置变 得相对磁带来说已经无关紧要，因为磁盘上的任何位置都可以在几十毫秒内进行 存取。数据在一定程度上摆脱了顺序访问的限制。有了磁盘，我们才可以创建网 络和层次的数据库，因为可以把表和树这样的数据结构保存在磁盘上的。正是由 于磁盘技术的发展，才有了数据库管理系统的诞生。数据库技术发展已经4 0 多年， 从最初的层次模型、网络模型、到现在的流行的关系模型【1 1 ，所有数据库管理系 统输入输出的相关算法都是优化对磁盘数据的输入输出性能。 1 9 8 9 年，东芝公司发布了n a n df l a s h 结构，强调降低每比特的成本，更高的 性能，并且象磁盘一样可以通过接口轻松升级。n a n df l a s h 中的n a n d 表示f l a s h 的技术架构：单词n a n d 来源于英文词组n o ta n d ，表明电路采用与非门实现。 如今同益普及的p d a 、m p 3 播放器、数码照相机、移动电话、高档笔记本等移动 计算设备广泛采用n a n df l a s h 作为数据的持久性存储介质【2 1 。从1 9 9 6 年起， n a n df l a s h 芯片的密度以超过两倍的年速度发展。到2 0 0 7 年，三星公司已经发 布了3 2 g b 的n a n df l a s h 芯片。从2 0 0 3 年起，n a n df l a s h 芯片技术的发展符 合c h a n g - g y uh w a n g 的c j j 存发展模型| 5j 。根据c h a n g - g y uh w a n g 的闪存发展模型， 到2 0 1 2 年，每个n a n df l a s h 芯片的容量达到2 5 0 g b ，到2 0 1 4 年，每个n a n df l a s h 芯片的容量将达到1 t b 。多颗n a n df l a s h 芯片可以封装成固态硬盘( s o l i dh a r d d i s k ) 引。固态硬盘可以取代传统的磁盘，而整个计算机系统其它组成却不需要改 变。在高档的笔记本市场，固态硬盘已经占据着相当一部分份额。由于n a n df l a s h 基于n a n df l a s h 的数据库管理系统优化研究 是电子设备，相对磁盘具有轻薄、功耗低、无噪音、抗震能力强、读写速度是磁 盘的1 0 0 倍以上等优势。随着n a n df l a s h 的密度不断增大，容量也随之不断增 大；生产工艺的进一步发展和市场占有率的提高，价格在不断下降；n a n df l a s h 的应用研究的发展，使用更加高效，因此由n a n df l a s h 封装成的固态硬盘对传 统的磁盘市场产生的巨大的冲击【7 】。可以预见n a n df l a s h 将在不久的将来取代 磁盘成为数据库系统的持久性数据存储设备1 3 , 4 , 6 j 。 1 2n a n df l a s h 结构 n a n df l a s h 的数据以比特的形式保存在存储单元( m e m o r yc e l l ) q b ，按每个存 储单元保存的比特的数量，可以把n a n df l a s h 分类为m l cn a n df l a s h 和s l c n a n df l a s h ，其中m l c 每个存储单元保存2 比特数据，而s l c 每个存储单元保 存1 比特数据【1 0 】。存储单元以8 个或者1 6 个位单元连成比特线( b i tl i n e ) ，形成8 位字节或者1 6 位字。比特线再组成扇区( s e c t o r ) ( 也称为n a n df l a s h 页，为了区 别操作系统的页机制和数据库管理系统的输入输出数据页，本文采用扇区称谓) 。 每个扇区除了保存数据的主要区域( m a i na r e a ) 外，还包含空闲区域( s p a r ea r e a ) ，也 称为o u to fb a n d ，简称o o b 。扇区主要区域大小一般为5 1 2 b 、2 k b 或4 k b ，扇 区的o o b 的大小一般为1 6 b 。o o b 一般用来保存错误探测和纠错码或者其他软 件应用信息。扇区是n a n df l a s h 的读写基本单位。由于n a n df l a s h 不支持就 地更新( i n p l a c eu p d a t e ) ，所以n a n df l a s h 的写操作必须在空白扇区上，否则就 需要先擦除，然后再写，这就是n a n df l a s h 的写前擦除特性。而写前擦除是以 擦除单元块为基本单位的，每个擦除单元块有多个扇区组成，典型的由3 2 个、6 4 个或1 2 8 个扇区组成一个擦除单元块。图1 1 显示了n a n df l a s h 的典型结构。 5 1 2b y t e s l 8 y t 鼎 lb l o c k 3 2 p a g t 带 m a i n d a t a s 坤k d a t a lljjjllllil 、 s p a r e l x t t ar e g i s t e r e r r c g 州“e f 图1 1h a n df l a s h 的典型结构 2 厂；，；， 1 0 0 0 0 52 5 0 - 2 7 5 2 未使用中抗震度( g m s ) 1 5 0 0 - 2 0 0 0 18 0 0 - 9 0 0 1 使用中噪音( d b ) 0 2 9 第一个特性：写前擦除。n a n df l a s h 的读写的基本单元是扇区，但是扇区 必须是空白的，如果写目标扇区已经有数据，那么写操作就会引起擦除操作。擦 除操作的过程是首先擦除整块数据，然后重新把新的数据写回到块中。表格1 2 的n a n df l a s h 为s a m s u n gk 9 w a g 0 8 u 1 a ，磁盘为s e a g a t eb a r r a c u d a7 2 0 0 7 s t 3 8 0 0 11 a 。最小更新的时问代价为：2 m s + 3 2 8 01 ts + 3 2 * 2 0 01 ts = 1 0 9 6 m s ，其中 还没有计算编程时间，所以写前擦除意味着尽量不要进行覆写【9 l 。 表1 2n a n df l a s h 与磁盘的访问性能比较 s l a c c e s st i m e r e a dw r i t ee r a s e m a g n e t i cd i s k 12 7 m s ( 2 k b ) 1 3 7 m s ( 2 k b ) n a n a n df l a s h 8 0us ( 2 k b )2 0 0l as ( 2 k b )1 5 m s ( 1 2 8 k b ) 第二个特性：无机械延迟。n a n df l a s h 是纯粹的电子存储设备，没有类似 于磁盘的磁头和磁臂等机械移动移动部件。而磁盘输入输出数据总的时l 日j 代价中， 磁头和磁臂的旋转时间占了绝大部分时l 丑j ，因此输入输出算法基本上都以减少磁 盘的搜索时间为优化目标。 第三个特性：不同的读写速度。以表格1 2 的s a m s u n gk 9 w a g 0 8 u 1 as l c n a n df l a s h 特性为例，n a n df l a s h 的读速是8 0 比s ，写速度是2 0 0 9 s 。读速度是 写速度的2 5 倍。传统的磁盘的读写速度基本上相同，在设计输入输出算法时， 对于性能的评价都是以输入输出数据量的总量来评定。由于不同的读写速度，使 得我们要重新评价原有的算法，同时在设计新的算法时候，可以考虑多进行读操 作来减少写操作。 第四个特性：有限的擦除次数。现在n a n df l a s h 的擦除次数的限制一般为 3 基于n a n df l a s h 的数据库管理系统优化研究 1 0 0 0 0 0 次。如果对同一个擦除单元块的擦除次数过多，会产生永久坏块，导致可 用容量减少。因此n a n df l a s h 都能实现耗损平衡( w e a rl e v e l i n g ) 。f l a s h 转换层 ( f l a s ht r a n s l a t i o nl a y e r ) 可以通过擦除单元块的逻辑地址到物理地址的映射，平衡 各个擦除单元块之间的擦除次数的差别。在f l a s h 转换层的耗损平衡的应用下， 3 2 g b 的n a n df l a s h 以4 0 m b s 的速度不停的进行输入输出操作，使用寿命可以 达到2 5 年。考虑一般情况下大多数驱动器都不是完全的利用，n a n df l a s h 的使 用寿命可以达到5 年到1 0 年。因此在n a n df l a s h 的使用寿命上，还是可以让人 接受的。 1 4 基于n a n df l a s h 的d b m s 面临的问题 传统数据库管理系统是基于磁盘设计的，磁盘的特性对数据库管理系统设计 思想影响比较大的有：就地更新和磁盘搜索时间。下面我们首先分别从n a n d f l a s h 的3 个特性出发，然后综合n a n df l a s h 的多个特性分析，说明基于n a n d f l a s h 数据库管理系统的所面临的问题。 写前擦除是基于n a n df l a s h 的数据库管理系统性能降低的最主要原因。传 统的数据库管理系统使用磁盘的就地更新来设计数据存储结构和算法，比如不定 长的记录的块一般都有块头，即使是插入新记录的操作，也要更新块头，就会引 起擦除操作。所以除了对数据库的读操作、更新、插入、删除都可能引起擦除操 作，使得数据库管理系统输入输出性能损耗很大。又如数据库的b 树索引结构， b 树节点更新往往引起一连串反应，导致b 树索引更新代价变得很大【1 2 , 1 3 】。通过 f l a s h 转换层可以减少擦除操作，f l a s h 转换层按其映射表的粒度可以分为基于扇 区的f l a s h 转换层和基于擦除单元块的f l a s h 转换层i l 引。基于扇区的f l a s h 转换层 读写性能好，但是内存消耗太大，不适合数据库应用。基于擦除单元块的f l a s h 转换层的读写性能差，但是内存消耗小，适合数据库应用。随着更新的增多，使 用基于擦除单元块的f l a s h 转换层的n a n df l a s h 不但读写性能急剧下降，而且可 用空闲块大量减少。因此为了能够充分发挥n a n df l a s h 的最大性能，就必须减 少更新操作。要想减少更新操作，就要修改数据库管理系统的体系结构和相关算 法。 传统的基于磁盘的系统软件，都有一个潜在的假设，即读速度和写速度是相 同的。数据库管理系统认为读一块数据到内存和从内存写一块数据到持久存储设 备的时间是相同。几乎所有的缓冲区管理算法认为读操作和写操作是相同的，以 至于长期以来，评判缓冲区管理算法的优劣以“缓冲命中率 来评判。即使缓存 区管理算法的命中率很高，只要产生的较多的写操作，特别是引起擦除操作的写 操作，其i o 性能也可能低于命中率不高，写操作相对较少，读操作较多的情况 下的i o 性能。不同的读写速度，使得我们在设计基于n a n df l a s h 的数据库管 4 硕上学位论文 理系统时，尽量用读操作来代替写操作。 机械延迟是磁盘的主要性能瓶颈，即磁盘的寻道时间和旋转等待时间。相对 于机械延迟，磁盘的读写时间往往很小，因此传统的数据库管理系统算法都尽量 去减少机械延迟。n a n df l a s h 是纯粹的电子设备，没有机械延迟。比如传统的 数据库管理系统为了减少机械延迟，采用比较大的传输i o 单元，一般为1 6 k b 。 采取大数据块主要是基于实际使用经验，性能上的提升主要是支持了大数据的读 写操作和预取未来可能使用的数据，如果预取的数据被使用，那么就节省出了机 械延迟的耗损时间。n a n df l a s h 的没有机械延迟使得我们可以使用更小的输入 输出单元，读入了更少的无用数据，留更多的内存给其他使用缓冲区的服务【1 1 】。 无机械延迟特性允许我们在设计基于n a n df l a s h 的数据库管理系统时，按优化 目标较自由的放置数据存储位置：读操作较多的数据可以适当离散存储，而写操 作较多的数据聚集存储，在同一个扇区内更好l r 7 1 。 n a n df l a s h 的无机械延迟特性和写前擦除特性也影响了数据库的页布局， 基于磁盘的不同的页布局有不同的优缺点，而基于n a n df l a s h 的页布局需要重 新考虑离散数据的读性能和写性能。n a n df l a s h 特性影响了所有数据库管理系 统的i o 相关算法，因此需要重新评价这些算法的i o 性能。 1 5 本文的研究工作 当写操作是随机的中小型写操作时，n a n df l a s h 表现出很差的写性能，而 随机的中小型写操作是数据库应用系统的常用操作，比如在线联机处理系统。因 此为了有效的使用n a n df l a s h 替代磁盘作为数据库存储介质，本文对数据库管 理系统的体系结构和算法进行修改，提出设计基于n a n df l a s h 数据库管理系统 的设计方法。 本文的工作主要有三点： 1 本文分析两类不同的f l a s h 转换层的特点，根据数据库应用系统对n a n d f l a s h 容量的需求，选择n f t l 作为未来的n a n df l a s h 转换层。由于没有基于 n f t l 的算法i o 性能评价模型，本文提出基于n f t l 的e w o m 模型，简称 n e w o m 模型，其改进于基于f t l 的e w o m 模型。 2 使用n e w o m 模型分析数据库相关算法：排序和连接算法的i o 性能，并 得出其性能公式。研究基于n a n df l a s h 的不同的页布局的优缺点，并分析基于 p a x 页布局的r a r e 连接算法。分析传统缓冲区管理算法：l r u 算法和基于n a n d f l a s h 的缓冲区管理算法：c f l r u 算法。 3 提出擦除单元块内日日志页方法，其改进于页内日志方法。擦除单元块内 日志方法采用p a x 页布局，消除了p a x 页布局在多属性值更新时的缺陷。擦除 单元块内日日志页方法相对于页内同志方法减少了内存消耗量，提高了日志页利 5 基于n a n df l a s h 的数据库管理系统优化研究 用率。研究擦除单元块方法下的缓冲区管理算法，选择l r u 算法取代c f l r u 算 法重新作为缓冲区管理算法，然后通过仿真实验证明擦除单元块内日志页方法的 i o 性能好于页内日志方法。为了进一步提高数据库管理系统的性能和降低成本， 本文提出了基于日志磁盘的擦除单元块内日志页方法，其利用了磁盘顺序写性能、 价格优势和n a n df l a s h 的随机读写优势。最后通过仿真实验比较基于日志磁盘 的擦除单元块内日志页方法和页内日志方法的性能，通过实验证明基于日志磁盘 的擦除单元块内日志页方法的i o 性能好于页内日志方法和擦除单元块内日志页 方法的i 0 性能。 1 6 论文结构 本论文的工作是围绕着基于n a n df l a s h 数据库管理系统性能优化这一崭新 的课题进行的，论文的结构安排如下： 第一章：主要介绍了研究背景、研究意义、研究内容和本文的研究工作，由 此引出了其后的具体研究内容。 第二章：分析f l a s h 转换层的特点，选择适合数据库应用的f l a s h 转换层：n f t l 。 提出基于n f t l 的算法i o 性能评价模型：n e w o m 模型。 第三章：用n e w o m 模型分析基于n a n df l a s h 数据库管理系统相关算法的i o 性能：排序算法、连接算法、页布局、缓冲区管理算法。 第四章：分析页内日志方法的缺点，提出擦除单元块内日志页方法，并通过仿 真实验证明擦除单元块内日志页方法的i o 性能好于页内日志方法的i o 性能。 第五章：提出基于日志磁盘的擦除单元块内日志页方法，并通过仿真实验证 明基于日志磁盘的擦除单元块内同志页方法的i o 性能好于擦除单元块内日志页 方法和页内日志方法的i o 性能。 最后总结全文，并展望未来的研究工作。 6 硕上学位论文 2 1 引言 第2 章性能评价模型 n a n df l a s h 需要f l a s h 转换层有三个理由： 第一：n a n df l a s h 的写前擦除特性。n a n df l a s h 不支持就地更新，所有的 写操作，必须在空白的扇区上进行，直接更新代价很大，所以n a n df l a s h 必须 使用延迟更新技术。延迟更新技术的一个基本技术是日志文件技术，通过先保存 记录更新的日志，然后在某个适当的时刻，用日志来更新数据，以减少频繁更新 的代价【1 8 】。n a n df l a s h 的f l a s h 转换层也提供类似于日志文件技术的机制，n a n d f l a s h 会把需要更新的扇区所有数据写在其它空白的扇区上，然后以某种机制替代 原来的扇区，直到产生擦除操作。 第二：n a n df l a s h 的有限擦除次数的特性。n a n df l a s h 的擦除单元块的擦 除次数都有限，需要平衡每个擦除单元块之间的擦除次数，f l a s h 转换层通过擦除 单元块的逻辑地址到擦除单元块的物理地址的映射实现耗损平衡。 第三：提供类磁盘接口。f l a s h 转换层实现了磁盘抽象，使得基于磁盘的系统 可以无需任何的改变，就能直接使用n a n df l a s h 作为永久性存储介质。因此为 了使用n a n df l a s h 代替磁盘作为数据库的永久性存储介质，就必须使用f l a s h 转换层。 正是由于上述三个理由，本文假设所研究的n a n df l a s h 都具有f l a s h 转换层。 数据库管理系统的性能优化，主要集中在输入输出性能的优化上。基于磁盘 的输入输出的性能损耗主要是磁臂的寻道时间和旋转时间，即磁盘的搜索时间。 n a n df l a s h 是电子设备，基本上不需要搜索时间，但其不支持就地更新，需要 写前擦除，使得在进行写操作时，还需要考虑可能产生的擦除操作和相关f l a s h 转换层操作；并且n a n df l a s h 的读写速度不同，相同数据量的写操作时间代价 比读操作时间代价大很多。因此由于n a n df l a s h 的写前擦除、无机械延迟、不 同读写速度等特点，需要提出输入输出算法的新的性能评价模型。 2 2f t l f l a s h 转换层通过一个逻辑地址到物理地址的映射表【2 1 1 ，把扇区的逻辑地址 转换成扇区物理地址： ( ) 。转换表的粒度一般为 擦除单元块或者扇区。 7 基于n a n df l a s h 的数据库管理系统优化研究 f t l 是一种出现较早且较流行的f l a s h 转换层，是一种基于扇区的转换层【1 4 】。 在f t l 中，一个扇区s ，在映射表中的项t f s 】的值保存着相应的擦除单元块和扇区 对 。同时在p 0 扇区所对应的o o b 中保存着扇区s 的序号，还有此扇区p 0 是否有效的标志。通过扇区o o b 的有效标志和替代的扇区序号，可以在重启n a n d f l a s h 以后重新构造f l a s h 转换层的映射表。当更新扇区s 时，f t l 把更新的s 扇区写 到空闲的扇区 ，然后把t s 】的值改成 并且把 的o o b 的有效 标志为无效。f t l 的垃圾回收功能回收废弃的擦除单元块，在垃圾回收的时候， 并适时的更新f l a s h 转换层的映射表。 2 3n f t l f t l 是一个读写性能和垃圾回收性能都很优秀的f l a s h 转换层。但是f t l 的 内存消耗量很大。假设1 g b 的n a n df l a s h ，其扇区大小为5 1 2 b ，f l a s h 转换层 的映射表每一项为8 字节，则f t l 需要的内存大小为1 6 m b ( 1 g b 5 1 2 8 ) 。当n a n d f l a s h 用于数据库应用时，必是大容量的n a n df l a s h 。比如1 0 0 g b 的n a n df l a s h ， 则f t l 需要1 6 0 0 m b ，约为1 6 g b 的内存消耗，显然这么大的内存消耗肯定是不 可接受的。因此需要新的f l a s h 转换层来解决未来的n a n df l a s h 应用面对的问题。 n f t l 是一种流行的基于擦除单元块的f l a s h 转换层【1 5 j 。在n f t l 中把扇区 地址划分为虚拟擦除单元块地址( v i r t u a lb l o c ka d d r e s s ) 和块内扇区偏移量( p a g e o f f s e t ) 。n f t l 的转换层的映射表实现从擦除单元块逻辑地址到擦除单元块物理地 址的映射。物理擦除单元块也称为主擦除单元块( p r i m a r yb l o c k ) ，简称主块。扇区 的第一次写操作写在主擦除单元块，当此扇区的第二次写操作时，把扇区写在替 换擦除单元块( r e p l a c e m e n tb l o c k ) ，简称替换块。当主擦除单元块内的任何扇区更 新时，就把更新的扇区写在替换擦除单元块上。每一个主擦除单元块有一个替换 擦除单元块，主擦除单元块上的更新的扇区连续写到替换擦除单元块上。n f t l 的读性能比f t l 差，因为n f t l 不但要先读入主擦除单元块的o o b ，来查找对 应的替换擦除单元块，而且如果在替换擦除单元块内找不到所要读的扇区，则又 需要读主擦除单元块内对应的扇区。 如图2 1 所示，假设n a n df l a s h 有8 个擦除单元块，每一个擦除单元块有8 个扇区。扇区地址可以划分为3 位块地址和3 为扇区偏移地址。图2 1 中t 1 到t 6 是操作序列。操作序列的格式为：操作类型+ 内容+ 目标扇区地址。所以t 1 指 的是对第9 块扇区进行写操作，写入内容a 。由于9 的二进制表示是( 1 0 0 1 ) ，则可 得块地址为1 ，块内扇区偏移量为1 ，可以表示是为 。因此由块地址1 ，找 到f l a s h 转换层映射表的序号为1 的项( 序号从0 开始) ，读取逻辑块1 对应的主 块的物理地址，这里逻辑块1 对应的物理块为b o 。t 1 的结果是在块b 0 中的第二 个扇区中写入a ( b 0 中的第一个扇区地址是8 ) ，然后在o o b 中标志扇区的逻辑 8 硕上学位论文 地址为9 并且标志扇区有效标志。t 2 是第9 块扇区进行覆写操作，把内容更新为 a 1 ，那么由于n a n df l a s h 不支持就地更新，因此n f t l 为主块分配替换块。n f t l 为主块b 0 分配的替换块为b 1 ，同时在主块b 0 的o o b 上写上b 1 ，使得能从主块 b 0 找到对应的替换块。然后把第9 块扇区的内容写到b 1 的第一个扇区上。t 3 的 写操作对象是 ( 二进制表示) ，首先查看b 0 中对应扇区中的o o b 中是否有 扇区有效的标志，如果没有，则直接写，如果有则写到替代块上。t 3 中第1 1 扇 区第一次写，因此写到主块中。t 4 对第9 扇区进行写操作，通过查看主块上对应 的第9 扇区的o o b 中的扇区有效标志可知是更新操作，所以把更新内容a 2 写到 替换块中，位置为替换块b 1 中的第一个空白扇区。t 5 同t 4 一样，首先查看主块 中的对应的扇区o o b 的扇区有效标志以确认是更新操作还是第一次写操作。t 5 是更新操作，因此把更新内容b 1 写到替换块的第一个空白扇区中。t 6 是读操作， 读第9 扇区的内容。同t 1 一样，9 可以表示为二进制1 0 0 1 ，1 为块地址，0 0 1 为 块内扇区偏移地址。根据块地址1 ，从f l a s h 转换层的映射表中找到物理块地址 b o ，从主块b 0 中找到替换块b 1 信息，即块b 1 的物理地址。然后从b 1 中找寻扇 区地址为9 的且内容为最新版本的扇区。寻找内容为最新版本的扇区的方法是从 空闲扇区指针开始逆向查找。如果没有在替换块中找到，则读取主块b 0 中对应扇 区地址为9 的扇区内容。 b l o c km a p p i n g i a b l e b l a9 v b i l v p r i m a r yb k = + k b l o c k # b 0 a l o t 2 a ：9 t 4 l ；l ii t 5 r e p l a c e m e n tb l o c k 1 3 l o c k # b l f r e e p a g e p o i n t 图2 1n f t l 结构图及实例 替换块的扇区数