劉穎杰,林子雨*,賴永炫

(1.廈門大學信息科學與技術(shù)學院,2.廈門大學軟件學院,福建廈門361005)

CF-HNLBI:一種新的閃存數(shù)據(jù)庫B-樹索引

劉穎杰1,林子雨1*,賴永炫2

(1.廈門大學信息科學與技術(shù)學院,2.廈門大學軟件學院,福建廈門361005)

提出了一種新的基于B-樹的閃存數(shù)據(jù)庫索引——CF-HNLBI索引.使用鏈表組織緩沖區(qū)中的更新信息,減少了緩沖區(qū)遍歷時間,通過鏈表結(jié)構(gòu)減少冗余信息,提高了緩沖區(qū)利用率.將緩沖區(qū)分為冷區(qū)和熱區(qū),并采用基于更新信息頻度的替換算法,有效地減少了閃存寫操作次數(shù).實驗結(jié)果表明,CF-HNLBI索引比其他已有索引具有更好的性能.

閃存;數(shù)據(jù)庫;索引;B-樹

閃存是一種電可擦除可編程只讀存儲器(electrically erasable programmable read only memory,EEPROM),具有非易失、讀寫速度快、抗震、低功耗、體積小等特性,目前已廣泛應用于嵌入式系統(tǒng)、航空航天、消費電子等領域[1-2].隨著閃存技術(shù)不斷發(fā)展,其相對于磁盤的競爭優(yōu)勢更加明顯,已經(jīng)有越來越多的企業(yè)把基于閃存的存儲產(chǎn)品(比如固態(tài)盤)作為數(shù)據(jù)庫系統(tǒng)的底層存儲介質(zhì)[3].閃存比磁盤具有更高的讀寫速度,因此,閃存數(shù)據(jù)庫系統(tǒng)可以獲得比傳統(tǒng)的磁盤數(shù)據(jù)庫系統(tǒng)更好的性能.但是,由于傳統(tǒng)的數(shù)據(jù)庫系統(tǒng)是面向磁盤設計的,而閃存具有和磁盤截然不同的物理特性[4](比如閃存讀寫不對稱以及隨機讀寫與順序讀寫具有相近的性能),這使得現(xiàn)有的數(shù)據(jù)庫的數(shù)據(jù)結(jié)構(gòu)和算法無法與閃存物理特性相匹配,因此,如果直接將傳統(tǒng)數(shù)據(jù)庫應用在閃存上,將無法發(fā)揮閃存的優(yōu)良性能,在某些特殊負載的情況下(如隨機寫密集型應用),甚至會導致數(shù)據(jù)庫性能的嚴重下降[5-6].因此,必須重新設計針對閃存數(shù)據(jù)庫的數(shù)據(jù)結(jié)構(gòu)和算法.目前,在這個方面已經(jīng)存在大量相關的研究工作[7-22],面向閃存的數(shù)據(jù)庫索引技術(shù)是其中的一個研究熱點.

數(shù)據(jù)庫索引記錄了數(shù)據(jù)和其存儲地址的映射關系,利用索引可快速訪問數(shù)據(jù)庫表中的特定信息,降低I/O操作代價、提高查詢效率.閃存相對于磁盤具有讀寫不對稱的特性,其寫代價遠遠高于讀代價,而傳統(tǒng)的數(shù)據(jù)庫索引結(jié)構(gòu)并沒有考慮這個特點.以B-樹索引為例,B-樹節(jié)點更新往往只是針對小部分數(shù)據(jù)的修改,而閃存以頁為最小單位進行讀寫,少量數(shù)據(jù)更新也會使整個頁面被重寫;同時,由于閃存的寫前擦除特性,索引更新也會帶來大量擦除操作,這將極大降低索引性能和壽命.

為解決上述問題,本文首先提出了一種基于最大節(jié)點更新的HNLBI(head node list B-tree indexing)索引,它以頭結(jié)點鏈表的形式組織緩沖區(qū)中的信息,并將節(jié)點信息存放在鏈表的頭節(jié)點中.HNLBI索引相對于傳統(tǒng)索引結(jié)構(gòu)具有3個優(yōu)勢:1)節(jié)點信息集中存儲在頭節(jié)點中,進一步減少了緩沖區(qū)中的信息冗余;2)在發(fā)生查詢操作或者緩沖區(qū)更新操作時,不必遍歷整個緩沖區(qū),提高了時間效率;3)緩沖區(qū)發(fā)生替換操作時,HNLBI索引遍歷頭節(jié)點選擇更新信息最多的節(jié)點刷新至閃存,提高了閃存的寫操作效率,并減少了閃存寫次數(shù).由于樸素的HNLBI索引并沒有利用節(jié)點訪問頻度的信息,這使得更新頻繁的節(jié)點可能被過早地替換出緩沖區(qū),因此,在HNLBI索引的基礎上,我們提出了改進之后的CF-HNLBI(cold-first head node list B-tree indexing)索引,該索引將緩沖區(qū)分為冷區(qū)和熱區(qū),分別存放不同訪問頻度的節(jié)點信息,當緩沖區(qū)滿時,替換操作發(fā)生在冷區(qū).這使得被頻繁更新的節(jié)點能夠更長時間地駐留在緩沖區(qū)中,進一步減少了閃存寫操作的次數(shù).實驗結(jié)果表明,CF-HNLBI索引相對于傳統(tǒng)索引能夠有效提高緩沖區(qū)利用效率,減少閃存寫操作的次數(shù),并且在不同訪問模式的工作負載下,都能夠取得比其他已有算法更好的性能.

1 相關工作

閃存數(shù)據(jù)庫的相關研究包括若干方面:緩沖區(qū)管理、數(shù)據(jù)庫索引管理、查詢處理和事務恢復等.不少研究人員提出了許多具有代表性的研究方法[7-13],其主要思想分為2種:索引結(jié)構(gòu)優(yōu)化和延時更新.

優(yōu)化索引結(jié)構(gòu)是提高索引性能的一種有效途徑,通過索引結(jié)構(gòu)的更改可以降低索引更新代價并提高數(shù)據(jù)查詢效率,目前主要的優(yōu)化方式包括μ-Tree索引[11]、Mircro Hash索引[12]、PBFilter索引[13]等.延時更新方法將數(shù)據(jù)更新引發(fā)的索引變化首先緩存在內(nèi)存,當緩存的數(shù)據(jù)滿足設定條件時再執(zhí)行批量更新操作.延遲更新通過消除冗余操作和批量提交的方式減少了寫操作代價,相關的主要算法有:BFTL[7]、IBSF[8]、LA-Tree[9]、Lazy-Update B+-Tree[10]等.由于本文采用第2類方法,即延時更新,因此,這里重點介紹該領域的相關研究.

BFTL[7]由緩沖區(qū)和節(jié)點轉(zhuǎn)換表組成,當針對B-樹的某個節(jié)點做插入、刪除或者更改操作時,更新信息將首先被緩存在緩沖區(qū)中;緩沖區(qū)滿后,信息將被更新到閃存中,同時,BFTL將為這些信息建立對應的索引單元,并寫入閃存物理頁中.索引單元和節(jié)點的相對應關系通過節(jié)點轉(zhuǎn)換表來獲得.BFTL存在以下缺點:1)由于B-樹的節(jié)點信息分散在不同的物理頁,因此,當訪問一個節(jié)點時往往引起多次的讀操作;2)節(jié)點轉(zhuǎn)換表必須存儲在內(nèi)存中并不斷增長,這會消耗大量的內(nèi)存空間;3)由于BFTL緩沖區(qū)只是按序記錄更新信息,因此,當節(jié)點發(fā)生分裂或其他操作時容易導致過多的冗余信息,使得緩沖區(qū)利用率較低.

IBSF[8]是針對BFTL的改進方法,它取消了節(jié)點轉(zhuǎn)換表并對緩沖區(qū)中的信息進行了處理,這在一定程度上減少了冗余信息.IBSF的主要思想是:1)將關于同一個節(jié)點的信息存在同一個閃存物理頁中,因此不再需要節(jié)點轉(zhuǎn)換表;2)刪除緩沖區(qū)中的冗余節(jié)點信息從而推遲寫閃存的時間.IBSF的主要缺陷表現(xiàn)在以下幾個方面:1)緩沖區(qū)每個更新單元除記錄更新信息外,還需記錄所屬節(jié)點的信息,這造成了信息冗余;2)緩沖區(qū)中信息依然采用按序記錄的方法,導致每次查詢或者刷新操作時都要遍歷緩沖區(qū);3)執(zhí)行緩沖區(qū)替換操作時,沒有考慮更新信息的冷熱屬性,更新頻繁的節(jié)點數(shù)據(jù)往往會被刷新至閃存,造成更多的寫操作.

相反,本文提出的CF-HNLBI索引能夠有效地解決上述算法中存在的各種問題,緊湊地組織緩沖區(qū)中的更新信息,盡可能地提高緩沖區(qū)利用率,并依據(jù)數(shù)據(jù)訪問頻度以及節(jié)點更新信息的數(shù)量提供高效的替換算法,極大地降低了索引更新的寫代價.

2 基于最長節(jié)點鏈表替換算法的B-樹索引HNLBI

傳統(tǒng)B-樹索引存在緩沖區(qū)利用率不高,閃存寫次數(shù)仍然較多的問題.為了克服上述缺陷,本文提出了基于最長節(jié)點鏈表替換算法的B-樹索引HNLBI.

2.1 傳統(tǒng)B-樹索引的不足

傳統(tǒng)的B-樹索引每一次更新都會導致一次閃存寫操作,頻繁發(fā)生的索引更新將會導致頻繁的閃存寫操作.為了提高閃存數(shù)據(jù)庫索引的性能,很多關于閃存數(shù)據(jù)庫B-樹索引的研究,都采用緩沖區(qū)進行批量索引更新,有效降低了B-樹頻繁更新引起的閃存寫代價;但是,通過大量實驗我們發(fā)現(xiàn),它們都沒有高效地利用緩沖區(qū)空間,同時,在減少閃存的寫操作次數(shù)方面還有很大的改進空間.

IBSF[8]是一種典型的采用延遲更新策略的B-樹索引結(jié)構(gòu),對于B-樹索引節(jié)點的更新信息首先會被寫入緩沖區(qū)中,在滿足適當條件時,將屬于同一個B-樹節(jié)點的更新信息從緩沖區(qū)中寫入到同一個閃存頁中,并且不需要使用節(jié)點轉(zhuǎn)換表.這里通過一個實例來說明IBSF的主要思想.

例1 如圖1所示,我們對B-樹索引進行一系列的值插入和刪除操作.圖2中op(n)表示針對B-樹的實際操作,即操作單元.op(1)表示向節(jié)點B插入3的操作,當op(1)發(fā)生時,IBSF在緩沖區(qū)中新建一個存儲單元N(1),存放該操作的相關信息;當發(fā)生刪除操作時,IBSF創(chuàng)建帶有位圖的刪除索引單元,如對于操作單元op(5)所表示的針對節(jié)點B刪除8的操作, IBSF會為該刪除操作創(chuàng)建新的緩沖區(qū)存儲單元N(5),并將N(5)的鍵值區(qū)域替換為刪除信息位圖(如100 000)來記錄刪除信息.當新的插入或者刪除操作到來時,IBSF依據(jù)操作單元中包含的鍵值對已存在的所有存儲單元進行掃描;對于鍵值相同的存儲單元, IBSF算法刪除舊的存儲單元,創(chuàng)建新的存儲單元,比如,op(9)所表示的刪除5操作發(fā)生時,IBSF會把已存在的、與插入5這個操作對應的緩沖區(qū)中的存儲單元N(4)刪除,然后創(chuàng)建N(9)存儲單元.當緩沖區(qū)滿時會發(fā)生替換操作,IBSF根據(jù)FIFO選擇緩沖區(qū)存儲單元N(1),然后,掃描整個緩沖區(qū),找到所有與N(1)同屬于一個節(jié)點的存儲單元N(3)和N(9),批量刷新至閃存中.

圖1 B-樹更新操作示意圖Fig.1 The operation of B-tree

IBSF索引雖然在一定程度上提高了緩沖區(qū)利用率,但是,在新的插入或刪除信息到來時,為刪除冗余信息,IBSF總是需要遍歷緩沖區(qū)中的所有存儲單元;在發(fā)生替換操作時,選擇要替換的節(jié)點之后,IBSF仍然需要遍歷整個緩沖區(qū),造成很高的掃描代價;此外, IBSF的替換算法的設計過于簡單,沒有考慮到節(jié)點更新不均衡的特點.上述缺陷的存在,使得IBSF在許多實際應用中不能取得很好的效果.

2.2 HNLBI索引的基本思想

為了克服以IBSF為代表的傳統(tǒng)B-樹索引的缺陷,提升閃存數(shù)據(jù)庫B-樹索引的性能,本文提出了一種新的閃存數(shù)據(jù)庫B-樹索引,即HNLBI.HNLBI索引采用延時更新的索引優(yōu)化策略,利用緩沖區(qū)組織節(jié)點更新信息,并在適當?shù)臅r候批量更新至閃存,這種批量更新的方式可以有效減少閃存的寫操作次數(shù).需要指出的是,采用這種優(yōu)化策略以后,在執(zhí)行查找操作時,需要結(jié)合緩沖區(qū)中的信息來重構(gòu)索引,這會在一定程度上增加了額外的開銷;但是,由于寫操作次數(shù)大量減少而帶來的收益遠遠大于這種額外增加的開銷,因此,HNLBI索引可以獲得較好的整體性能.接下來我們詳細介紹HNLBI索引的相關策略.

HNLBI索引采用與IBSF類似的索引單元存儲策略,對B-樹索引節(jié)點的更新信息(插入或刪除信息)首先寫入緩沖區(qū)中,在滿足適當條件時,將對于同一個B-樹節(jié)點的信息寫入同一閃存頁中,不需要使用節(jié)點轉(zhuǎn)換表.與IBSF不同的是,HNLBI索引將緩沖區(qū)內(nèi)的索引單元重新組合,并采用基于最長節(jié)點鏈表的緩沖區(qū)替換算法,其主要思想如下:

(i)當關于某一節(jié)點的更新信息第一次出現(xiàn)時, HNLBI首先在緩沖區(qū)中為該節(jié)點創(chuàng)建頭節(jié)點,并將該頭節(jié)點插入頭節(jié)點鏈表中;頭節(jié)點中記錄了該節(jié)點的具體信息(如鏈表長度),此外,頭節(jié)點中還使用一個位圖來表示刪除操作;如果該更新信息是插入操作,則在頭節(jié)點后添加存儲節(jié)點,保存插入的鍵值;如果該更新信息是刪除操作,則更新頭節(jié)點中的位圖來記錄刪除信息.

圖2 IBSF算法緩沖區(qū)情況Fig.2 The buffer of IBSF

(ii)當關于某個已存在節(jié)點的更新信息到來時, HNLBI首先遍歷頭節(jié)點鏈表,找到該節(jié)點;若該更新信息是插入操作,則在該節(jié)點的更新信息鏈表尾部創(chuàng)建新的存儲節(jié)點,記錄插入信息;若該信息是刪除信息,則遍歷該節(jié)點的更新信息鏈表,若發(fā)現(xiàn)已存在鍵值相同的存儲節(jié)點,則該已存在的存儲節(jié)點是冗余的,刪除該冗余節(jié)點后,更新頭節(jié)點中的位圖記錄刪除信息,若沒有冗余節(jié)點,則直接更新頭節(jié)點中的位圖來記錄刪除信息.

(iii)HNLBI索引的頭節(jié)點鏈表以及每個節(jié)點的更新信息鏈表,實際上連接形成了一個頭結(jié)點鏈表.當緩沖區(qū)滿要進行替換操作時,遍歷頭節(jié)點鏈表,根據(jù)頭節(jié)點信息找出最長的節(jié)點更新信息鏈表進行替換,這樣的替換策略可以為緩沖區(qū)提供更多的空余空間,有效減少了替換操作發(fā)生頻度,從而在較大程度上減少了閃存寫操作次數(shù).

為了更好地理解HNLBI索引的核心思想,下面給出一個實例.

例2 當發(fā)生如圖1的索引更新時,HNLBI對應的緩沖區(qū)信息變化情況如圖3所示.在圖3中,op(n)表示針對B-樹的實際操作,即操作單元.op(1)表示向節(jié)點B插入鍵值3的操作,當該操作發(fā)生時,由于緩沖區(qū)此時沒有節(jié)點B的相關更新信息鏈表,因此,創(chuàng)建關于節(jié)點B的頭節(jié)點,并在頭節(jié)點后增加存儲節(jié)點,鍵值為3,對于op(2)操作單元進行同樣處理;當op(3)索引單元所示的操作發(fā)生時,遍歷頭節(jié)點鏈表,找到與op(3)相關的節(jié)點B后,遍歷節(jié)點B的節(jié)點更新信息鏈表,發(fā)現(xiàn)op(3)插入的鍵值與已存在的存儲節(jié)點無沖突,增加存儲節(jié)點,鍵值為4;當發(fā)生刪除操作時,如op(5)操作單元所表示的刪除節(jié)點C中8的操作,HNLBI找到op(5)相關的節(jié)點C的更新信息鏈表并遍歷,沒有發(fā)現(xiàn)需要刪除的存儲節(jié)點,因此,直接修改頭節(jié)點C中的位圖信息;當發(fā)生op(9)所表示的刪除節(jié)點B中5的操作時,遍歷op(9)相關的節(jié)點B的更新信息鏈表,發(fā)現(xiàn)該鏈表中存在鍵值與op(9)同樣為5的存儲節(jié)點,因此,如圖所示刪除該節(jié)點,然后,修改頭節(jié)點B中的位圖信息,將相應的位設置為1來表示刪除.當緩沖區(qū)滿時,遍歷頭節(jié)點鏈表,找到最長的鏈表,然后將其替換出緩沖區(qū),在本例中選擇節(jié)點C的更新信息鏈表.

2.3 算法設計

HNLBI索引的插入過程如算法1所示.插入前首先檢查緩沖區(qū)是否已滿,若緩沖區(qū)沒有足夠空間,則遍歷頭節(jié)點鏈表,根據(jù)頭節(jié)點中記錄的節(jié)點更新信息鏈表長度,選擇最長的節(jié)點更新信息鏈表鏈表刷新至閃存.然后,遍歷頭節(jié)點鏈表,查找更新信息對應的頭節(jié)點是否存在.若已經(jīng)有對應頭節(jié)點存在,則在該頭節(jié)點的更新信息鏈表尾部插入存儲節(jié)點,并更新頭節(jié)點中的節(jié)點相關信息.若對應的頭節(jié)點不存在,則創(chuàng)建該頭節(jié)點,加入到頭節(jié)點鏈表中,并在該頭節(jié)點所在的鏈表中插入新的存儲節(jié)點,然后更新頭節(jié)點中的信息.

圖3 HNLBI緩沖區(qū)示意圖Fig.3 The buffer of HNLBI

HNLBI索引對于刪除操作的處理如算法2所示.對于刪除操作,首先檢查緩沖區(qū)是否已滿,若緩沖區(qū)滿則執(zhí)行刷新操作,選擇最長的節(jié)點更新信息鏈表刷新至閃存;然后查找頭節(jié)點鏈表,如果對應的頭節(jié)點已存在,則查找要刪除的鍵值是否存在于該節(jié)點對應的更新信息鏈表中,若存在,則刪除該鍵值對應的存儲節(jié)點,若不存在,則直接更新該頭節(jié)點信息.如果對應的頭節(jié)點不存在,則創(chuàng)建對應的頭節(jié)點,用來記錄刪除操作.

2.4 與IBSF索引的比較

IBSF索引采用按序存儲索引單元的方式組織緩沖區(qū)中的數(shù)據(jù),這樣的結(jié)構(gòu)導致在執(zhí)行插入、刪除、查找以及批量更新操作時需要遍歷整個緩沖區(qū);此外,對于IBSF的每一個索引單元都必須記載對應的節(jié)點信息,這也造成了一定的信息冗余.而在HNLBI索引中,進行相關操作時,首先查找對應的節(jié)點,然后針對相關的節(jié)點信息進行集中處理,節(jié)省了遍歷所需的時間;此外,HNLBI索引中的節(jié)點信息集中記錄在頭節(jié)點中,這樣,頭節(jié)點之后的節(jié)點僅需要記錄插入的鍵值,這大大減少了信息冗余.另外,由于IBSF算法沒有對緩沖區(qū)中的信息進行歸類,這導致在批量更新時,IBSF索引只能采用FIFO或者LRU算法.而HNLBI索引采用了基于最長節(jié)點鏈表的替換算法,根據(jù)頭節(jié)點中記錄的信息,選擇更新信息最多的節(jié)點(即節(jié)點的更新信息鏈表最長)將其刷新至閃存中.通過圖2和圖3的比較可知,IBSF選擇節(jié)點B替換出緩沖區(qū),HNLBI索引的更新策略選擇占用更多緩沖空間的節(jié)點C替換出緩沖區(qū),這使得閃存閃存寫操作有更高的效率,并為緩沖區(qū)節(jié)省了更多空間.

3 基于冷熱分區(qū)替換算法的CF-HNLBI索引

HNLBI索引雖然重新組織了緩沖區(qū)中的更新信息,并選擇最長節(jié)點更新信息鏈表替換出緩沖區(qū),但是沒有很好地利用數(shù)據(jù)使用頻度的信息.于是,我們提出了針對HNLBI索引的改進版本——基于冷熱分區(qū)的替換算法的CF-HNLBI索引.CF-HNLBI針對HNLBI算法的緩沖區(qū)替換策略進行了改進,加入了冷熱分區(qū)的概念,熱區(qū)中存放更新頻繁的節(jié)點數(shù)據(jù),冷區(qū)中存放更新不頻繁的節(jié)點數(shù)據(jù).當發(fā)生緩沖區(qū)替換時,CF-HNLBI只選擇冷區(qū)中的節(jié)點進行替換.

3.1 改進策略

HNLBI索引的主要缺陷是緩沖區(qū)替換策略只是簡單選擇最大長度的更新信息鏈表進行替換.但是,當某個B-樹節(jié)點更新頻繁時,即使該B-樹節(jié)點的更新信息在緩沖區(qū)中多于其他B-樹節(jié)點,也應該使該B-樹節(jié)點駐留更長的時間,從而可以防止對同一個B-樹節(jié)點在某一段時間內(nèi)多次寫入閃存.

為解決該問題,CF-HNLBI索引將緩沖區(qū)頭節(jié)點鏈表分為冷區(qū)和熱區(qū),并為頭節(jié)點設置冷標識位來反映該頭節(jié)點所對應的B-樹節(jié)點的更新頻度.當冷標識位為1時,表明該頭節(jié)點為冷節(jié)點,其對應的B-樹節(jié)點更新不頻繁;當冷標識位為0時,表明該頭節(jié)點為熱節(jié)點,其對應的B-樹節(jié)點更新頻繁.此外,當緩沖區(qū)中的冷節(jié)點被再次訪問時,需要將其標記為熱節(jié)點,即將冷標識位設置為0.CF-HNLBI的具體細節(jié)如下:

(i)將索引緩沖區(qū)分為冷區(qū)和熱區(qū),冷區(qū)大小設定下限閾值,熱區(qū)中存放至少更新兩次的節(jié)點,冷區(qū)中存放只更新過一次的節(jié)點.

(ii)每當新的更新信息被加入到緩沖區(qū)之前,首先檢查緩沖區(qū)是否已滿,若緩沖區(qū)已滿,則在冷區(qū)中執(zhí)行緩沖區(qū)替換策略.具體方法是,遍歷冷區(qū)中的頭節(jié)點鏈表,獲取頭節(jié)點中記錄的更新信息鏈表長度信息,選擇冷區(qū)中最長的更新信息鏈表驅(qū)逐出緩沖區(qū)并批量寫入閃存.

(iii)緩沖區(qū)中為某個B-樹節(jié)點新建立的頭節(jié)點存放在冷區(qū),此時該頭節(jié)點冷標識位為1,是一個冷節(jié)點;當該B-樹節(jié)點再次發(fā)生更新時,將該B-樹節(jié)點對應的更新信息鏈表轉(zhuǎn)移到熱區(qū)MRU(most recently used)位置,并設置冷標識位為0;當冷區(qū)中有更新信息鏈表轉(zhuǎn)移至熱區(qū)或者冷區(qū)中有更新信息鏈表被驅(qū)逐出緩存時,如果冷區(qū)中的更新信息鏈表所占的空間小于冷區(qū)大小的下限閾值,則從熱區(qū)中選擇若干個更新信息鏈表轉(zhuǎn)移至冷區(qū);當需要從熱區(qū)中選擇更新信息鏈表轉(zhuǎn)移至冷區(qū)時,首先從熱區(qū)頭節(jié)點鏈表的LRU (least recently used)位置開始遍歷,如果遇到冷標志位為1的頭節(jié)點,說明它是一個冷節(jié)點,則將其更新信息鏈表轉(zhuǎn)移至冷區(qū),如果冷標識位為0,則給該頭節(jié)點第2次機會,將該頭節(jié)點的冷標識位設置為1,繼續(xù)掃描其他頭節(jié)點,如果沒有發(fā)現(xiàn)合適節(jié)點,則重新遍歷熱區(qū),直至找到合適節(jié)點轉(zhuǎn)移至冷區(qū)為止.如果熱區(qū)中的某個頭節(jié)點對應的B-樹節(jié)點被更新,則將該頭節(jié)點的冷標識位重新設置為0,并將其移動至熱區(qū)的MRU位置.

CF-HNLBI索引所采用的替換算法細節(jié)如算法3所示.

3.2 實 例

為了更好地理解CF-HNLBI索引的基本思想,下面給出一個具體實例.

例3 緩沖區(qū)初始狀態(tài)如圖4(a)所示,我們假設頭節(jié)點所占的空間為存儲節(jié)點的2倍,緩沖區(qū)空間上限為可容納24個存儲節(jié)點,而冷區(qū)空間的下限閾值為容納11個存儲節(jié)點.緩沖區(qū)包含6個B-樹節(jié)點(D、E、F、G、H和I)的相關信息,這里用B-樹節(jié)點的名稱作為其對應的緩沖區(qū)頭節(jié)點的名稱,D、E、F位于熱區(qū),G、H、I位于冷區(qū),其中,熱區(qū)中的D與F冷標識位為1,E冷標識位為0,冷區(qū)中的B-樹節(jié)點的冷標識位均為1.當針對B-樹節(jié)點的更新信息到達緩沖區(qū)時,將包含以下兩種可能的情況:

(i)該B-樹節(jié)點所對應的頭節(jié)點已存在于緩沖區(qū)中的情況.在某個時刻,一個針對節(jié)點F的更新操作到達,CF-HNLBI索引檢查緩沖區(qū)后發(fā)現(xiàn)其所對應的的頭節(jié)點F已經(jīng)在緩沖區(qū)中存在(熱區(qū)中),則更新頭節(jié)點F的鏈表信息,然后將F的冷標識位設置為0,并將其移動至熱區(qū)的MRU位置(如圖4(b)所示).在針對F的操作處理結(jié)束后,一個針對B-樹節(jié)點I的更新操作到達,CF-HNLBI索引檢查緩沖區(qū)后發(fā)現(xiàn)其所對應的頭節(jié)點I已在緩沖區(qū)中存在(冷區(qū)中),則更新頭節(jié)點I的鏈表信息,然后,設置其冷標識位為0,使其成為熱節(jié)點,并將頭節(jié)點I的更新信息鏈表移動至熱區(qū)的MRU位置.此時,CF-HNLBI檢測到冷區(qū)更新信息不足,冷區(qū)中只有8個存儲節(jié)點,低于設定的下限閾值(即11個存儲節(jié)點),CF-HNLBI索引從熱區(qū)鏈表的LRU位置開始遍歷,發(fā)現(xiàn)E冷標識位為0,是一個熱節(jié)點,則將其設置為1,使其變?yōu)槔涔?jié)點,給它第二次機會;然后,繼續(xù)遍歷,發(fā)現(xiàn)頭節(jié)點D的冷標識位為1,是一個冷節(jié)點,則將其直接移動至冷區(qū),此時檢測發(fā)現(xiàn)冷區(qū)更新信息已經(jīng)足夠(冷區(qū)擁有13個存儲節(jié)點,大于下限閾值11),停止操作(如圖4(c)所示).

(ii)該B-樹節(jié)點所對應的頭節(jié)點不存在于緩沖區(qū)中的情況.在上述操作完成后,一個新的針對B-樹節(jié)點J的更新操作到來.此時緩沖區(qū)已有24個存儲節(jié)點,達到緩沖區(qū)空間上限值,于是CF-HNLBI索引遍歷冷區(qū)頭節(jié)點鏈表,讀取頭節(jié)點中記錄的更新信息鏈表長度信息,找到更新信息鏈表最長的頭節(jié)點G,將其驅(qū)逐出緩沖區(qū)并寫入閃存;然后,CF-HNLBI遍歷緩沖區(qū),發(fā)現(xiàn)頭節(jié)點J不存在,則創(chuàng)建頭節(jié)點J并將其插入冷區(qū)頭節(jié)點鏈表中;這時冷區(qū)只有10個存儲節(jié)點,再次低于設定的下限閾值11,因此CF-HNLBI選擇熱區(qū)中的頭節(jié)點E,將其移動至冷區(qū)(如圖4(d)所示).

3.3 性能分析

圖4 CF-HNLBI索引冷熱緩沖區(qū)示意圖Fig.4 The cold-hot buffer of CF-HNLBI

相對于IBSF而言,本文的CF-HNLBI索引采用了冷熱分區(qū)的機制,這雖然增加了一定的時間開銷,但是與IBSF相比,本文算法不需要遍歷整個緩沖區(qū),因此總的時間開銷相對于IBSF減少了,這在之后的實驗中將得到進一步驗證.

在讀寫性能方面,我們分別分析不同索引讀閃存的性能和寫閃存的性能.

(ii)閃存寫代價.由于B-樹在構(gòu)建過程中會發(fā)生節(jié)點分裂操作,而該類操作涉及到對父節(jié)點以及同級其他節(jié)點的修改,因此,這會造成額外的3次寫操作;我們假設在插入n條記錄的過程中,會發(fā)生δ次B-樹節(jié)點的分裂操作,則對于普通B-樹的插入,寫操作的次數(shù)為{n+(δ×3)}×Owirte,其中Owrite表示一次寫閃存頁的操作代價.由于BFTL、IBSF和CF-HNLBI索引均使用了緩沖區(qū)進行批量更新操作,因此它們都可以減少閃存寫操作的次數(shù),其寫代價分別如公式(4)～(6)所示.

式(4)中k表示BFTL將一個節(jié)點的信息寫入閃存平均需要寫k個頁,buffer_size表示BFTL索引的緩沖區(qū)大小.式(5)中ρ表示IBSF索引在一次寫閃存操作過程中所更新信息的平均數(shù)量.式(6)中μ表示CF-HNLBI索引在一次寫閃存操作過程中所更新的信息的平均數(shù)量.對于IBSF和CF-HNLBI所言,由于IBSF并未考慮一次寫閃存操作的更新信息數(shù)量,而CF-HNLBI索引每次均選擇冷區(qū)中更新信息最多的節(jié)點(即選擇最長的更新信息鏈表)驅(qū)逐出緩沖區(qū),因此,CF-HNLBI索引在每次寫閃存操作時所更新的信息的平均數(shù)量μ,大于IBSF每次寫閃存操作時所更新的信息的平均數(shù)量ρ,從而可以通過式(5)、(6)得出, CF-HNLBI索引的寫閃存操作的平均次數(shù)小于IBSF索引.

4 實驗設計與結(jié)果

4.1 實驗設計

實驗使用Flash-DBSim[23]平臺模擬閃存存儲系統(tǒng).Flash-DBSim是一種高效的、可重用和可配置的閃存存儲系統(tǒng)仿真平臺.本文模擬一個128 MB的NAND閃存固態(tài)盤,該固態(tài)盤所采用的NAND閃存的數(shù)據(jù)頁大小是2 k B,每個數(shù)據(jù)塊包含64個數(shù)據(jù)頁,讀寫代價比為1∶8,擦除代價為1.5 ms/塊,擦除次數(shù)為100 000.

在運行BFTL、IBSF、CF-HNLBI索引時,我們將緩沖區(qū)的大小設置為40 k B,對于BFTL和IBSF算法,緩沖區(qū)中的索引單元設置為512 bits,對于CFHNLBI索引,頭節(jié)點設置為512 bits,存儲節(jié)點設置為256 bits;所有實驗中B-樹設為40階B-樹.IBSF索引中采用了LRU和FIFO 2種緩沖區(qū)替換算法,但由于其性能相差無幾,這里選擇實現(xiàn)LRU算法進行對比.實驗中,我們選擇插入100 000條記錄,并將插入記錄的鍵值分布情況分為4種情況:完全無序、基本無序、基本有序和完全有序.

4.2 CF-HNLBI索引冷區(qū)下限閾值的選擇

本實驗測試冷區(qū)不同的下限閾值對于索引性能的影響.實驗設定緩沖區(qū)大小為40 kB.如圖5所示,我們對于4種不同分布的插入記錄分別測試了冷區(qū)下限閾值占緩沖區(qū)比值從10%增加至90%的性能變化情況.從圖中實驗結(jié)果來看,在冷區(qū)下限閾值設定為占緩沖區(qū)空間的30%時,CF-HNLBI的閃存寫操作次數(shù)比IBSF最少.所以,本文之后對于CF-HNLBI索引的性能比較均采用30%的冷區(qū)下限閾值.

圖5 冷區(qū)下限占不同比值時算法寫閃存次數(shù)Fig.5 The number of write requests under different minimum sizes of cold area

4.3 不同索引構(gòu)建過程的性能比較

本實驗對BFTL、IBSF和CF-HNLBI分別執(zhí)行100 000條記錄插入操作,從而比較它們的閃存讀寫性能.圖6演示了不同算法的讀寫情況.從圖6(a)中可以看到,BFTL由于同一B-樹節(jié)點可能存儲在不同的閃存頁中,因此,其在建立一棵B-樹時需要更多的讀操作;IBSF索引與本文的CF-HNLBI索引均將同一B-樹節(jié)點信息記錄在同一閃存頁中,因此,它們有相近的閃存讀性能,并且均優(yōu)于BFTL索引.從圖6(b)中可以看出,CF-HNLBI的閃存寫次數(shù)明顯少于BFTL索引和IBSF索引,這得益于CF-HNLBI索引進一步減少了緩沖區(qū)中的信息冗余,并使用了更好的替換算法.總體而言,CF-HNLBI的寫閃存操作次數(shù)平均減少了16.2%.

圖6 BFTL、IBSF、CF-HNLBI索引閃存讀/寫性能比較Fig.6 The read/write performance of BFTL,IBSF,CF-HNLBI

圖7顯示了不同索引構(gòu)建過程的時間開銷.CFHNLBI索引雖然由于冷熱分區(qū)機制而在一定程度上增加了時間開銷,但由于節(jié)省了緩沖區(qū)遍歷的時間和減少了寫閃存次數(shù),因此在總體時間性能上仍然優(yōu)于BFTL和IBSF.總體而言,CF-HNLBI構(gòu)建B-樹的時間開銷比IBSF平均降低了18.2%.

5 結(jié) 論

隨著閃存技術(shù)的發(fā)展,閃存數(shù)據(jù)庫系統(tǒng)會越來越普及.已有的面向閃存數(shù)據(jù)庫的索引結(jié)構(gòu),或者沒有充分考慮到閃存的特性,或者對于緩沖區(qū)的利用不夠高效,仍有很大的提升空間.本文首先提出了一種樸素的HNLBI索引,該索引大量減少了緩沖區(qū)中的冗余信息,提高了緩沖區(qū)的利用效率,同時通過頭節(jié)點的使用更好地組織了緩沖區(qū)中的更新信息,減少了閃存寫操作的次數(shù).但是針對緩沖區(qū)替換算法,HNLBI索引并沒有利用數(shù)據(jù)訪問的局部性特點,因此本文提出了改進的索引結(jié)構(gòu),即CF-HNLBI索引,它將緩沖區(qū)分為冷區(qū)和熱區(qū),當緩沖區(qū)滿時,替換操作僅發(fā)生在冷區(qū),這使得被頻繁訪問的節(jié)點有更多的機會駐留在緩沖區(qū)中,提高了緩沖區(qū)的利用效率,也有效地減少了閃存寫操作的次數(shù).本文研究過程中,和其他已有索引結(jié)構(gòu)(如BFTL、IBSF)進行了對比.然而,不同的閃存設備讀寫代價比是不一樣的,我們將在未來的工作中,在不同的閃存設備上充分測試CF-HNLBI索引的不同性能表現(xiàn),從而為不同讀寫代價比的設備確定最優(yōu)的參數(shù).

圖7 構(gòu)建索引時間對比Fig.7 The time cost for building an index

[1] Chiang M L,Lee P C H,Chang R C.Managing flash memory in personal communication devices[C]∥Consumer Electronics,Proceedings of 1997 IEEE International Symposium.[S.l.]:IEEE,1997:177-182.

[2] Canim M,Mihaila G A,Bhattacharjee B,et al.An object placement advisor for DB2 using solid state storage[J]. Proceedings of the VLDB Endowment,2009,2(2): 1318-1329.

[3] Nath S,Kansal A.FlashDB:dynamic self-tuning database for NAND flash[C]∥Proceedings of the 6th International Conference on Information Processing in Sensor Networks.New Xork:ACM,2007:410-419.

[4] Intel Corporation.Understanding the flash translation layer(FTL)specification[EB/OL].[1998-12-01].http:∥www.docin.com/p-730629258.html.

[5] Lee S W,Moon B.Design of flash-based DBMS:an in-page logging approach[C]∥Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data.New Xork:ACM,2007:55-66.

[6] Lee S W,Moon B,Park C,et al.A case for flash memory ssd in enterprise database applications[C]∥Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data.New Xork:ACM,2008:1075-1086.

[7] Wu C H,Kuo T W,Chang L P.An efficient B-tree layer implementation for flash-memory storage systems[J]. ACM Transactions on Embedded Computing Systems (TECS),2007,6(3):19.

[8] Lee H S,Lee D H.An efficient index buffer management scheme for implementing a B-tree on NAND flash memory [J].Data&Knowledge Engineering,2010,69(9):901-916.

[9] Agrawal D,Ganesan D,Sitaraman R,et al.Lazy-adaptive tree:an optimized index structure for flash devices[J]. Proceedings of the VLDB Endowment,2009,2(1): 361-372.

[10] On S T,Hu H,Li X,et al.Flash-optimized B+-tree[J]. Journal of Computer Science and Technology,2010,25 (3):509-522.

[11] Kang D,Jung D,Kang J U,et al.μ-tree:an ordered index structure for NAND flash memory[C]∥Proceedings of the 7th ACM&IEEE International Conference on Embedded Software.New Xork:ACM,2007:144-153.

[12] Zeinalipour-Xazti D,Lin S,Kalogeraki V,et al.Micro-Hash:an efficient index structure for flash-based sensor devices[J].FAST,2005,5:31-44.

[13] Xin S,Pucheral P,Meng X.PBFilter:indexing flash-resident data through partitioned summaries[C]∥Proceedings of the 17th ACM Conference on Information and Knowledge Management.New Xork:ACM,2008: 1333-1334.

[14] Nath S,Kansal A.FlashDB:dynamic self-tuning database for NAND flash[C]∥Proceedings of the 6th International Conference on Information Processing in Sensor Networks.New Xork:ACM,2007:410-419.

[15] Meng X,Jin P,Cao W,et al.Report on the first international workshop on flash-based database systems(FlashDB 2011)[J].ACM Sigmod Record,2011,40(2):40-44.

[16] Meng X,Xue L,Xu J.Flash-based database systems:experiences from the flashDB project[C]∥Proceedings of the 16th International Conference on Database Systems for Advanced Applications.Berlin:Springer-Verlag,2011:240-240.

[17] Jin P,Ou X,H?rder T,et al.AD-LRU:an efficient buffer replacement algorithm for flash-based databases[J]. Data&Knowledge Engineering,2012,72:83-102.

[18] Lu Z,Qi X,Cao W,et al.LB-logging:a highly efficient recovery technique for flash-based database[M]∥Webage information management.Berlin:Springer-Verlag, 2012:375-386.

[19] Hardock S,Petrov I,Gottstein R,et al.Noftl:database systems on ftl-less flash storage[J].Proceedings of the VLDB Endowment,2013,6(12):1278-1281.

[20] Tang X,Meng X F,Liang Z H,et al.Cost-based buffer management algorithm for flash database systems[J]. Journal of Software,2011,22(12):2951-2964.

[21] Jin P Q,Ou X,Theo H,et al.AD-LRU:an efficient buffer replacement algorithm for flash-based databases [J].Data&Knowledge Engineering,2012,72:83-102.

[22] Zhou D,Liang Z C,Meng X F.HF-tree:an update-efficient index for flash memory[J].Journal of Computer Research and Development,2010,5:832-840.

[23] Su X,Jin P,Xiang X,et al.Flash-DBSim:a simulation tool for evaluating flash-based database algorithms[C]∥Computer Science and Information Technology,2009. 2nd IEEE International Conference.[S.l.]:IEEE,2009: 185-189.

CF-HNLBI:a New B-tree Indexing for Flash-based Databases

LIU Xing-jie1,LIN Zi-yu1*,LAI Xong-xuan2
(1.School of Information Science and Engineering,Xiamen University, 2.School of Software,Xiamen University,Xiamen 361005,China)

A new B-tree-based indexing,called CF-HNLBI,is proposed for flash-based database systems.In CF-HNLBI,indexing units are organized in the form of lists to reduce the time cost of traversal operations.The method involves less redundant information in the index buffer compared to other indexings schemes.It divides the buffer into two areas,i.e.,cold area and hot area,and adopts the buffer replacement algorithm based on updating information frequency to reduce the number of write operations.Extensive experimental results show that CF-HNLBI can achieve better performances than the state-of-the-art methods.

flash;database;index;B-tree

10.6043/j.issn.0438-0479.2015.02.017

TP 311

A

0438-0479(2015)02-0247-10

2014-06-18 錄用日期:2014-11-19

國家自然科學基金(61303004,61370010,61102136,61202012);福建省自然科學基金(2013J05099,2011J05156,2011J05158);中央高?；究蒲袠I(yè)務費專項(2011121049)

*通信作者:ziyulin@xmu.edu.cn

劉穎杰,林子雨,賴永炫.CF-HNLBI:一種新的閃存數(shù)據(jù)庫B-樹索引[J].廈門大學學報:自然科學版,2015,54(2): 247-256.

:Liu Xingjie,Lin Ziyu,Lai Xongxuan.CF-HNLBI:a new B-tree indexing for flash-based databases[J].Journal of Xiamen University:Natural Science,2015,54(2):247-256.(in Chinese)