快閃記憶體之原生高效率資料存取暨檔案管理方法

Abstract

由於快閃記憶體的良好物理特性，如非揮發性，耐震，以及省電，使得它一向是嵌入式 系統中儲存媒體的最好選擇。而概觀一個嵌入式系統存取儲存媒體的方式，不外乎有 三：韌體(firmware)直接存取重要系統資料，應用程式透過檔案系統(file systems)存取檔 案，以及應用程式透過資料庫介面(database)存取資料紀錄。這些資料的存取方法，本質 上都是將某種固定格式套用在儲存空間上，並以參照指標將資料連接組織起來，以利快 速存取。由此可見，參照指標的讀寫動作，是任何結構性資料的基礎。這樣的動作在 RAM 或是磁碟這類以往的記憶體上並不成問題。不過，在快閃記憶體上面實作參照指 標則相當困難。這主要肇因於快閃記憶體的物理特性，如一次寫入，大塊抹除，最小讀 寫單位之限制，乃至於被參照的資料會不由自主地被垃圾收集或是平均磨損策略所移 動。以往之解決方案，則為賦予每份資料物件一個邏輯位址。這樣一來，資料的邏輯位 址並不隨著它的實體位址改動而變化，而資料彼此之間的參照指標也因為使用邏輯位址 而不需要直接更新到媒體上。但此法帶來幾個基本的問題，如需要大量RAM 空間的需 求，以及冗長的啟動時間。 本研究計畫的核心議題在於，如何摒棄以往使用邏輯位址(logical addresses)之作法，而 直接在快閃記憶體上使用參照指標將資料物件以物理位址 (physical addresses)來組織 起來。若實體參照指標可以成功地在快閃記憶體上實作，那麼既有之索引結構或結構性 資料便可以原生地在快閃記憶體上實作，並可以避免上述因使用邏輯位址造成的問題。 而解決這個基本議題後，基於參照指標的任何結構性資料存取方法，如檔案系統或資料 庫系統，其長久以來的設計議題便可以嶄新的角度解決。不過，實作實體參照指標卻也 在快閃記憶體上帶來幾個基本的議題，如額外之資料寫入，指標更新之傳遞問題，垃圾 回收之死結問題，平均磨損的問題，以及資料更新動作易受電源跳脫之破壞等等。為研 究此相關衍生議題，本研究計畫分為兩年度：第一年度之研究標的為研究如何在NOR 與 NAND 兩種不同的快閃記憶體上，透過使用實體參照，以有效率的方法實作索引結構， 並研究如何解決前開之基本議題。我們各自以skip list 與 B-tree 在NOR 與 NAND 上 的實作為標的來進行研究。第二年，基於第一年的學理成果，我們將會把主題帶進如何 在NOR 與NAND 上實作有效率的檔案系統與資料庫系統，並與現存之使用邏輯參照指 標之各種方法作比較。依個人淺見，由於快閃記憶體容量不斷提昇，為了減少RAM 空 間的需求以及快速啟動，在快閃記憶體上實施實體參照取代邏輯位址將逐漸成為必要作 法。這也是本研究計畫之核心目標。