摘要

　　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封裝成的固態硬盤對傳統的磁盤市場產生的巨大的沖擊�？梢灶A見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 小結
　　結論與展望
　　參考文獻
　　致謝

（如您需要查看本篇畢業設計全文，請您聯系客服索�。�