陳玉標 李建中 李英姝,2 李發(fā)明 高 宏

1(哈爾濱工業(yè)大學計算機科學與技術(shù)學院 哈爾濱 150001) 2(佐治亞州立大學計算機科學與技術(shù)學院 佐治亞州亞特蘭大 30303)(chenyubiao@hit.edu.cn)

從個人電腦到服務(wù)器設(shè)備，基于閃存的固態(tài)硬盤已經(jīng)被廣泛應(yīng)用.閃存固態(tài)硬盤以其耗能低、體積小、高可靠性、讀寫速度快等特點深受歡迎.與此同時，隨著閃存固態(tài)硬盤架構(gòu)的改進，比如集成更多的通道，它具有了豐富的內(nèi)部并行性.近年來，已經(jīng)有人對固態(tài)硬盤這種性質(zhì)進行了研究和應(yīng)用.例如閃存固態(tài)硬盤內(nèi)部并行已經(jīng)被用來加速關(guān)系數(shù)據(jù)庫中索引掃描和聚集[1]，也使B+樹索引結(jié)構(gòu)的性能得到很大提升[2].

R-樹[3]是一種支持高維數(shù)據(jù)索引的平衡樹結(jié)構(gòu),被廣泛用于空間數(shù)據(jù)管理[4].目前Spatial Hadoop,MySQL,PostgreSQL,ArcGIS等系統(tǒng)都支持R-樹索引結(jié)構(gòu).目前，針對閃存的R-樹優(yōu)化工作[5-7]主要考慮的是讀寫不對稱引發(fā)的寫問題以及由頻繁寫帶來的固態(tài)硬盤壽命縮短問題.但是，這些工作并沒有考慮到固態(tài)硬盤的內(nèi)部并行性[8].本文重點研究如何利用固態(tài)硬盤內(nèi)部并行性加速R-樹的查詢和更新操作.根據(jù)我們所知，本文是最早基于固態(tài)硬盤內(nèi)部并行機制對R-樹進行優(yōu)化的文章之一.本文的主要貢獻包括5個方面:

1) 提出了適合于固態(tài)硬盤內(nèi)部并行化的批量異步I/O提交技術(shù);

2) 提出了基于R-樹的貪心批量查詢處理算法;

3) 提出了R-樹的批量更新算法，并基于常數(shù)級別的緩沖，設(shè)計了一個查詢更新的系統(tǒng)結(jié)構(gòu)，該系統(tǒng)結(jié)構(gòu)能大幅度加速更新操作;

4) 從理論上證明了具有豐富內(nèi)部并行性的閃存固態(tài)硬盤批量與順序讀和寫的期望加速比下界.

5) 針對千萬級別的數(shù)據(jù)，對本文提出的基于R-樹的批量查詢處理算法和R-樹批量更新算法進行了測試，證實了利用固態(tài)硬盤內(nèi)部并行性，可以極大地提高了R-樹索引性能.

本文首先介紹利用固態(tài)硬盤內(nèi)部并行特性的相關(guān)工作及技術(shù)原理; 其次給出使用方法，并進行期望加速比下界的理論證明; 然后，提出基于固態(tài)硬盤內(nèi)部并行性的R-樹批量查詢算法和批量更新算法; 最后，通過實驗對比闡述基于固態(tài)硬盤內(nèi)部并行性的R-樹查詢和更新算法的性能優(yōu)勢，驗證有效性.

1 相關(guān)工作

本節(jié)介紹R-樹在閃存固態(tài)硬盤上索引優(yōu)化的現(xiàn)有研究工作.閃存作為存儲器的隨機寫要比隨機讀和順序?qū)懧芏?，人們稱此性質(zhì)為讀寫不對稱性.因此，對R-樹索引進行優(yōu)化時，人們通?？紤]如何通過額外的隨機讀操作來減少隨機寫或者如何把隨機寫盡可能地轉(zhuǎn)換成順序?qū)?經(jīng)過調(diào)查發(fā)現(xiàn)，利用固態(tài)硬盤的R-樹優(yōu)化方法主要分為3類：

1) 優(yōu)化方法是利用緩存策略來減少隨機寫.文獻[9]使用這種策略提出一種優(yōu)化R-樹，通過更新頻繁的樹頭駐留主存、其余節(jié)點按其與樹頭的距離從小到大的次序優(yōu)先級駐留內(nèi)存，實現(xiàn)R-樹的緩沖存儲，以減少更新帶來的隨機寫.文獻[7]基于相同策略提出另一種優(yōu)化R-樹，用批量更新代替即時更新，更新的數(shù)據(jù)順序存儲在內(nèi)存，當內(nèi)存滿時實現(xiàn)R-樹的批量順序更新.由于很多更新被延遲，所以能有效地減少閃存的隨機寫.文獻[10]提出了第3種基于緩存策略的優(yōu)化R-樹，更新操作被緩存在主存中，它對不同節(jié)點的更改分別建立了Hash索引，能夠有效地把同一節(jié)點的多次更新合并為一次更新寫回閃存.

2) 優(yōu)化方法是通過存儲更新日志的方式使用順序?qū)懞皖~外讀操作來代替隨機寫.文獻[6]使用這種策略提出了一種優(yōu)化R-樹，把每個節(jié)點的更新操作信息存儲到更新日志中，僅當節(jié)點被查詢時，R-樹中這個節(jié)點才被真正更新，大大減少了隨機寫的次數(shù).這種方法的缺點是每次更新都需要更新日志文件的讀寫.

3) 優(yōu)化方法是改造R-樹索引，減少R-樹節(jié)點分裂來減少隨機寫.在新的節(jié)點插入R-樹中時，有可能導致R-樹節(jié)點的分裂，節(jié)點的分裂會導致很多額外的隨機寫操作.因此，文獻[6]在非平衡的B-樹[11]的基礎(chǔ)上提出了非平衡的R-樹，通過引入溢出節(jié)點的方式來減少分裂節(jié)點帶來額外的隨機寫.

上述針對閃存固態(tài)硬盤的R-樹優(yōu)化策略，都沒有考慮閃存固態(tài)硬盤內(nèi)部豐富的并行性.本文重點研究充分利用閃存固態(tài)硬盤內(nèi)部并行性來優(yōu)化R-樹查詢和更新操作的問題.

2 固態(tài)硬盤內(nèi)部并行性

本節(jié)介紹固態(tài)硬盤內(nèi)部并行性機理及使用技術(shù)和實現(xiàn)方法.

2.1 內(nèi)部并行性的機理

一個經(jīng)典的固態(tài)硬盤包含4個部分：主機接口邏輯模塊、內(nèi)存緩存模塊、固態(tài)硬盤控制器模塊、閃存包模塊，如圖1所示.閃存包通過數(shù)據(jù)通道連接至閃存控制器，多閃存包共享一個通道.一般情況下，一個固態(tài)硬盤含有2～10個通道.其中通道之間工作是獨立的.閃存包會有很多，不同包之間的工作也是獨立的.那么根據(jù)上述描述，固態(tài)硬盤內(nèi)部存在2個層級上的并行性：

1) 通道級別并行性.固態(tài)硬盤在設(shè)計上采用了多通道技術(shù)，不同通道之間是獨立運行的，從而多通道可以并行運行.如圖1所示，如果對閃存包0和閃存包5同時提交訪問請求，由于它們連接的是不同的通道，訪問可以并行執(zhí)行.

2) 閃存包級別并行性.為了盡可能地充分利用通道資源，每個通道下都連接一系列閃存包.每個閃存包獨立工作，因此閃存包可以并行工作.如圖1所示，當對閃存包2和閃存包4的訪問同時到來時，它們可以獨立并行地處理各自的請求.

Fig.1 Architecture of solid state disk圖1 固態(tài)硬盤架構(gòu)

包級別并行性對加速隨機寫意義重大.閃存的隨機寫比隨機讀慢很多，這種讀寫不對稱性源于閃存的寫前擦除機制，擦除操作延遲很大.利用閃存包級的并行性，可以使多個不在同一個閃存包的多個字讀寫操作并行執(zhí)行，從而也實現(xiàn)了擦除操作的并行執(zhí)行，有效地減低了寫操作的延時.

2.2 如何利用內(nèi)部并行性

本文使用Linux操作系統(tǒng)的異步I/O庫libaio，通過實現(xiàn)批量提交異步I/O來發(fā)揮固態(tài)硬盤內(nèi)部并行性.

1) 當一個閃存固態(tài)硬盤讀寫請求到來時，使用異步I/O庫libaio，讓Linux操作系統(tǒng)把該請求加入I/O請求隊列NCQ(native command queuing)中；

2) Linux操作系統(tǒng)周期地檢查NCQ，如果NCQ中具有讀寫請求，它就將這些請求發(fā)送給固態(tài)硬盤，然后固態(tài)硬盤通過各個通道，分發(fā)給相應(yīng)的閃存包，并啟動相應(yīng)的閃存包，并行處理各自的讀寫請求.

閃存固態(tài)硬盤通過同時自動啟動多個數(shù)據(jù)通道傳輸數(shù)據(jù)的方式實現(xiàn)通道級并行性; 讓批量提交的讀寫請求由不同的閃存包執(zhí)行，實現(xiàn)了閃存包級的并行性.值得注意的是，Linux操作系統(tǒng)周期性地檢查NCQ中的讀寫請求.因此只有批量一次性地提交讀寫請求，才能保證批量提交的讀寫請求是被閃存固態(tài)硬盤同時處理，才能充分發(fā)揮閃存固態(tài)硬盤的內(nèi)部并行性.原因是非一次性提交I/O請求，很有可能被Linux系統(tǒng)的輪詢機制給分成多批處理，減弱批量I/O處理的并行性.

Fig.2 4 KB random read/write and mixed testing圖2 4 KB隨機讀寫混合測試

為了利用固態(tài)硬盤內(nèi)部并行性，我們在libaio的基礎(chǔ)上，實現(xiàn)了一個批量并行讀寫函數(shù)Parallel-IO.它的輸入是讀寫請求集合，輸出是批量讀寫操作結(jié)果.Parallel-IO通過libaio把該讀寫請求集合批量提交給閃存固態(tài)硬盤，利用其內(nèi)部并行性執(zhí)行讀寫請求.在使用Parallel-IO時，要注意避免一次批量提交的讀寫請求中既含有讀也含有寫，因為讀寫耦合會導致性能衰退[8].因此，一定要分別批量提交讀和寫.圖2為本文在3款不同固態(tài)硬盤上進行的隨機讀寫混合測試實驗，本實驗對于隨機讀(如圖2(a)所示)和隨機寫(如圖2(b)所示)以及混合讀寫(如圖2(c)所示)這3款固態(tài)硬盤的詳細參數(shù)參考表3描述，從圖2可以看出，混合隨機讀寫批量提交的平均帶寬比單獨批量提交隨機讀或者單獨提交隨機寫的帶寬都要低.因此，本文在進行R-樹讀寫優(yōu)化時，對于固態(tài)硬盤的讀寫分別進行單獨的批量提交，以防止讀寫混合帶來的性能衰退.另外還需注意的是：在實際應(yīng)用中，Parallel-IO批量提交大量的I/O請求到等待隊列中，可能會直接阻塞其他應(yīng)用的I/O請求，因此對于多應(yīng)用低延遲的場景，該加速方法不適用.

為了便于閱讀，表1列出了本文常用的符號定義.

Table 1 The Symbols to Describe R-tree Optimization 表1 用于描述R-樹優(yōu)化算法符號解釋

3 批量IO并行處理算法

本節(jié)分為2部分，介紹批量并行讀寫函數(shù)Parallel-IO.第1部分介紹Parallel-IO的算法實現(xiàn)；第2部分對Parallel-IO的加速效果進行了理論分析.

3.1 算法實現(xiàn)

如算法1所示，偽代碼展示了如何利用libaio實現(xiàn)Parallel-IO進行批量提交.它的輸入是讀寫請求集合，例如輸入request_queue是讀隊列，bufs作為存儲讀取數(shù)據(jù)緩存，返回bufs作為批量讀取結(jié)果.無論是批量讀請求還是批量寫請求，Parallel-IO均通過libaio庫把該讀寫請求集合批量提交給閃存固態(tài)硬盤，利用其內(nèi)部并行性執(zhí)行讀寫請求.詳情見算法1.

算法1.ParallelIO(request_queue,bufs).

輸入：request_queue是讀寫操作隊列，當其為寫隊列時，bufs為寫數(shù)據(jù)緩存;

輸出：request_queue是讀隊列時，返回是讀結(jié)果.

① 用io_setup創(chuàng)建批量提交的上下文ctx

② 創(chuàng)建NCQ-size大小的IO提交緩存cbs;

③memalign_bufs←獲取request_queue個

512 B對齊的讀寫單元;

④ if (request_queue是寫隊列) then

⑤memalign_bufs←bufs;

⑥ end if

⑦ if (request_queue是寫隊列) then

⑧ 通過io_prep_pwrite把寫請求寫進cbs;

⑨ else

⑩ 通過io_prep_pread把讀請求寫進cbs;

3) 行④～⑥判斷如果request_queue是寫隊列，那么需要先把寫的內(nèi)容bufs先寫進memalign_bufs以寫進外存.

3.2 算法分析

本節(jié)對于Parallel-IO函數(shù)的加速效果進行分析.由于固態(tài)硬盤內(nèi)部為商業(yè)保密對用戶不可見，因此通過Parallel-IO函數(shù)批量提交的異步I/O請求，并不能保證其中每一個異步I/O都通過不同的通道并行工作.不同異步I/O共用通道會引起擁塞，而導致I/O在通道級別的順序執(zhí)行.但是通過理論分析可以發(fā)現(xiàn)，即使存在異步I/O請求使用相同通道的情況，Parallel-IO依然可以提供一個可觀的加速比.本節(jié)將提供理論證明.

3.2.1 問題定義

對于一個通道數(shù)為n的固態(tài)硬盤，假設(shè)一次批量提交m(m≤NCQ-size)個讀寫類型相同的異步IO請求，并且訪問的存儲位置和每個通道相連的概率相等.在只考慮通道級別并行加速效果的情況下，求由Parallel-IO批量提交的并行隨機訪問相較于同步順序隨機訪問相比的期望加速比下界.

3.2.2 度量標準

因為對于固態(tài)硬盤的讀和寫只是數(shù)據(jù)移動方向不同，對加速比下界分析無影響，因此不失一般性，接下來均以讀為例來分析理論加速比下界.假設(shè)完成一個讀寫存儲單元的讀操作，閃存包上執(zhí)行的時間為t1，通道通過的時間為t2,那么對m個讀寫存儲單元的讀操作順序執(zhí)行時間為

Tseq=m×(t1+t2).

(1)

如果將上述m個讀寫單元的讀操作，通過Parallel-IO批量提交.假設(shè)通過n通道時，最多出現(xiàn)k個讀請求通過同一個通道，那么k個讀請求執(zhí)行時間為

Tasy≤k×(t1+t2),

(2)

其中,采取“≤”是因為閃存固態(tài)硬盤內(nèi)部還存在閃存包級別的并行性，最差的情況是通道和閃存包都順序執(zhí)行.所以理論加速比為

(3)

所以，m個請求通過n個通道，同一個通道最多有k個請求的加速比:

(4)

從式(4)可見mk的期望值即是期望加速比下界.

3.2.3 求解期望加速比下界

因為訪問的存儲位置和每個通道相連的概率相等，那么m個訪問中每個訪問通過n個通道的概率都相等，且都為1n.對于第i個通道，通過它的訪問恰好有k個的概率為

(5)

所以通道i中至少有k個訪問的概率為

(6)

根據(jù)式(5)放縮得：

所以得到：

(7)

所以n個通道中存在一個通道至少有k個訪問的概率為

因此得到：

(8)

所以n個通道中至多有k個訪問的概率為

Fig.3 A R-tree example of MAXNODES=2, MINNODES=1圖3 一個MAXNODES=2, MINNODES=1的R-樹例子

因此可得：

(9)

設(shè)m個讀寫單元的讀操作通過n個通道時，單個通道中出現(xiàn)最多k個讀寫操作的概率為p(x)，可以得到結(jié)論：

(10)

根據(jù)式(8)～(10)可推導出期望加速比下界：

(11)

由于k是任意的，所以式(11)可得：

Table 2 Lower Bound of Speed Up Expectation表2 期望加速比下界

Notes:mmeans batch-submitting I/O number,nmeans channel number.

4 R-樹的優(yōu)化

基于Parallel-IO批量并行讀寫函數(shù)，本節(jié)設(shè)計了R-樹的貪心批量查詢處理優(yōu)化算法Batch-Search和基于常數(shù)級別緩存的批量更新優(yōu)化算法Batch-Update.

為了便于理解，這里首先給出一個R-樹例子.圖3(b)是一個在2維平面點上建立的R-樹.圖3(a)是對應(yīng)2維平面的結(jié)構(gòu)圖.圖3中的P1～P6是已經(jīng)插入到R-樹中的點，I1和I2是即將插入到R-樹中的點.圖3中實線矩陣對應(yīng)R-樹節(jié)點的最小覆蓋矩形MBR，E和F對應(yīng)的虛線矩形是插入I1和I2后得到的MBR，此前E和F分別僅包含點P3和P4.這里假設(shè)每個數(shù)據(jù)點和節(jié)點都占據(jù)一個閃存讀寫單位頁.

4.1 查詢操作優(yōu)化

本節(jié)針對區(qū)域查詢操作采用最小化批量提交次數(shù)的貪心策略來加速查詢處理速度.

查詢操作定義：對于一棵外存R-樹，已知根節(jié)點已載入內(nèi)存稱為root，輸入查詢區(qū)域為m，從根節(jié)點root查詢返回所有和m有交集的數(shù)據(jù).

由查詢操作的定義知，這里的查詢是區(qū)域查詢.在圖3中，對應(yīng)虛線查詢區(qū)域m，可以通過觀察快速得知，查詢結(jié)果為{P2，P3，P4，P5}.在R-樹上的傳統(tǒng)查詢過程如下：從根節(jié)點A開始搜索，A有2個branch記做branch1和branch2分別指向B，C2個子節(jié)點.因為branch1.MBR和branch2.MBR都和查詢范圍m相交，因此從外存讀入B，C.然后按照同樣的方式分別處理B，C，直到處理到葉子節(jié)點為止.當處理到葉子節(jié)點D，E，F(xiàn)，G，返回所有和m相交的數(shù)據(jù)索引，此時，判斷發(fā)現(xiàn)D中P2，E中P3，F(xiàn)中P4和G的P5對應(yīng)的MBR和m相交，把它們的外存索引集合ptr返回，最終根據(jù)ptr從外存中讀入P2，P3，P4，P5，作為查詢結(jié)果返回.

設(shè)存儲例子R-樹的固態(tài)硬盤具有2個數(shù)據(jù)通道,每個數(shù)據(jù)通道連接3個閃存包，且{B，C，D，E，F(xiàn)，G}均勻地分布在6個閃存包上.使用Parallel-IO函數(shù)，利用閃存固態(tài)硬盤的內(nèi)部并行性，上述查詢處理可以進行優(yōu)化地處理：

如果B，D，F(xiàn)存儲在第1個數(shù)據(jù)通道連接的閃存包中，C，E，G存儲在第2個數(shù)據(jù)通道連接的閃存包中.Parallel-IO只需要3(T1+T2)的IO時間，性能比順序IO提高了1倍.

如果B，D，F(xiàn)分別存儲在第1個數(shù)據(jù)通道連接的3個閃存包中，C，E，G存儲在第2個數(shù)據(jù)通道連接的3個閃存包中.Parallel-IO可以更優(yōu)化地處理上述查詢：

這種查詢處理方法只需要2T1+3T2的IO時間.

算法2.BatchSearch(root,m).

輸入：root為R樹根節(jié)點、m是搜索范圍MBR;

輸出：滿足m查詢范圍的數(shù)據(jù)索引集合.

①request_queue,node_queue,dataptr_queue

←?；

②node_queue.pushback(root)；

③ while (node_queue或request_queue≠?)

do

④ while (node_queue≠?) do

⑤node←取出node_queue首元素;

⑥ if (node不是葉子節(jié)點) then

⑦ for (tinnode.branchs) do

⑧ if (t.MBR與m相交) then

⑨request_queue.pushback(t.ptr);

⑩ end if

then

元素;

算法2維護3個隊列：查詢隊列request_queue、節(jié)點隊列node_queue和數(shù)據(jù)隊列dataptr_queue，其中request_queue存放待載入內(nèi)存節(jié)點的索引,node_queue存放已經(jīng)載入的內(nèi)存節(jié)點,dataptr_queue存放結(jié)果數(shù)據(jù)索引.

算法2終止條件：當node_queue和request_queue都為空時，意味著所有可能和m有交集的節(jié)點都搜索完畢，算法終止.算法行③是判斷算法是否停止的條件.

算法2主體分為2部分.

1)node_queue≠?時的處理過程詳見行④～.該部分遍歷node_queue中所有節(jié)點，找出所有和m相交的非葉子節(jié)點，把它們存放到request_queue中用以形成批量提交集合，詳見行⑥～.把所有和m相交的葉子節(jié)點放入dataptr_queue作為結(jié)果返回集合，詳見行～.

2)request_queue≠?時的處理過程，詳見行～.固態(tài)硬盤的NCQ隊列的上限值記為NCQ-size.因此,Parallel-IO最多1次批量提交NCQ-size個IO請求.算法構(gòu)建具有NCQ-size個讀請求的批量IO請求集合(詳見行～).如果request_queue中請求數(shù)小于NCQ-size，且沒有內(nèi)存節(jié)點可以遍歷來為request_queue增加新的IO請求,則把request_queue中所有IO請求作為一個批量請求集合.最后，并行讀入批量請求集合中的所有節(jié)點到內(nèi)存，詳見行～.

當整個算法node_queue和request_queue都為空時，遍歷結(jié)束.最終返回dataptr_queue中數(shù)據(jù)索引(詳見行).

算法的偽代碼詳見算法2.

4.2 更新操作優(yōu)化

本節(jié)介紹基于閃存固態(tài)硬盤內(nèi)部并行性的R-樹批量更新的優(yōu)化算法.

更新操作定義：對于一棵外存R-樹，已知根節(jié)點已載入內(nèi)存為root，向R-樹中插入數(shù)據(jù)、修改R-樹中的數(shù)據(jù)以及刪除R-樹中數(shù)據(jù)的操作，統(tǒng)稱為更新操作.

以插入更新操作為例來闡述優(yōu)化思路，如圖3所示，I1和I2為新插入點.在I1插入時，根據(jù)R-樹插入規(guī)則，每次都選擇使得I1加入后MBR擴充面積最小的節(jié)點進行插入操作，因此I1插入路徑是{A，B，E}.最終，I1插入到E節(jié)點.插入I1后，E節(jié)點產(chǎn)生了更改，同時擴充了E的邊界MBR，而E的MBR存儲在B中，因此，B也有更改，因此插入I1產(chǎn)生了2個節(jié)點E，B的更新.更改的節(jié)點需要寫入外存固態(tài)硬盤，所以，插入I1共計產(chǎn)生2次讀和2次寫.僅僅只考慮I1的插入過程，2次讀操作無法并行執(zhí)行，因為E和B存在依賴關(guān)系.而2次寫可以批量提交并行執(zhí)行，因此整個過程需要3次批量請求.插入I2的路徑為{A，C，F(xiàn)}，需要2次讀操作讀入C和F，F(xiàn)的插入使得F原來的MBR擴充，因此C和F節(jié)點都被更新，需要寫回外存固態(tài)硬盤，C和F的讀入因為依賴關(guān)系只能順序執(zhí)行，因此需要2次讀請求，C和F作為更改節(jié)點寫回外存需要1次批量寫請求.共計3次讀寫請求；那么I1和I2的2次插入過程總共需要6次批量讀寫請求.而順序操作也只需要8次讀寫請求，速度提升并不高.速度提升不高的原因有2個：

1) 插入單個元素的插入過程，需依次讀入待插入節(jié)點的過程由于存在依賴關(guān)系只能順序執(zhí)行.

2) 寫操作雖然可以批量提交，但是插入1個元素造成的更改非常少，固態(tài)硬盤的內(nèi)部并行性并不能發(fā)揮優(yōu)勢.

但是更新操作相比于查詢操作還是存在很大的優(yōu)化空間，因為查詢操作必須實時立即返回查詢結(jié)果，而更新操作并沒有這個限制，它可以延遲執(zhí)行.如考慮把I1和I2插入操作合并進行，那么上述插入過程可進行優(yōu)化：

1) 讀入{B，C}的過程，可以建立1個批量IO請求.

2) 讀入{E，F(xiàn)}的過程可以建立1個批量IO請求.

3) 對{B，C，E，F(xiàn)}的寫操作建立1個批量IO請求.

4.2.1 更新隊列

Fig.4 Process of search and update operation with UDQ圖4 基于UDQ查詢和更新操作工作流程

更新隊列UDQ，在更新操作優(yōu)化中用以存儲延遲更新操作，以達到批量提交提高I/O并行性的目的.此時的R-樹，由于更新操作被延遲，當有新的查詢操作到來時，R-樹本身并非含有最新版本的數(shù)據(jù).因此，必須要將查詢操作直接得到的結(jié)果進行UDQ更新處理后，獲取最新版本查詢數(shù)據(jù).如圖4所示，當請求操作op為更新操作時，將該操作op放入UDQ，這時判斷UDQ是否滿，滿則批量更新至外存R-樹上，清空UDQ；如果op是查詢操作，需先向外存R-樹提交查詢op請求，獲取查詢結(jié)果Q，然后依次將UDQ按照入隊順序?qū)進行更新，以保證查詢結(jié)果的正確性，將最終的Q作為查詢結(jié)果返回.

具體算法詳見算法3，行④Batch-Update為算法4所示的批量更新算法.這里面涉及到UDQ-size大小的選擇問題，直觀上講UDQ-size越大，并行性越高，但是UDQ-size并不能無限大.在Batch-Update算法中，最多MINNODES個插入操作可以1次批量提交.因此UDQ-size=MINNODES.這是由于R-樹的節(jié)點分裂策略決定，接下來解釋原因.這里先介紹分裂策略，本文采用最經(jīng)典的R-樹節(jié)點分裂策略.

算法3.Execute(op).

輸入：op——R-樹操作(查詢、插入、修改、刪除);

輸出：查詢結(jié)果.

① if (op是更新操作) then

②UDQ←UDQ∪op；

③ if (UDQ已滿) then

④BatchUpdate(UDQ)；

⑤ end if

⑥UDQ←?；

⑦ else if (op是查詢操作)

⑧Q←BatchSearch(op)；

⑨ for (opiinUDQ) then

⑩opi作用在Q上；

例：設(shè)節(jié)點node擁有b1,b2,…,bm共m個分支，對應(yīng)的最小矩形為MBR1,MBR2,…,MBRm，其中m>MAXNODES.此時，需要對node節(jié)點進行分裂.分裂步驟如下：

1) 創(chuàng)建2個新節(jié)點node1,node2隨機選取2個不同的分支bi，bj分別加入到node1和node2中.

2) 枚舉bk∈{b1,b2,…,bm}(k≠i,j),設(shè)D1=MBR(node1∪bk)-MBR(node1),D2=MBR(node2∪bk)-MBR(node2).如果D1

3) 將node的分支從父節(jié)點中刪除，將node1和node2的分支加入父節(jié)點，依次遞歸判斷父節(jié)點的分裂.

假設(shè)批量UDQ-size最大為x，那么極端情況通過Batch-Update 1次批量提交x個插入操作，均插入到同一個節(jié)點上，設(shè)該節(jié)點最多擁有MAXNODES個分支，那么，依照例子中給出的分裂策略，如果x>MINNODES.就可能出現(xiàn)節(jié)點分裂后，一個節(jié)點只有MINNODES個分支，

而另外一個擁有大于

MAXNODES個分支情況，不滿足R-樹的平衡性.因此，UDQ-size≤MINNODES.

4.2.2 批量更新算法

首先，闡述批量更新算法的思想：

1) 把UDQ每個更新操作下推到作用的葉子節(jié)點進行處理.

2) 對每個葉子節(jié)點的更新過程中，保證嚴格按照更新操作入隊的時間順序進行，確保算法的正確性.

在批量提交更新過程中，算法Batch-Update首先按照廣度優(yōu)先搜索的順序，把更新操作集合由根節(jié)點層層推送到葉子節(jié)點.在此過程中，需要讀取節(jié)點數(shù)據(jù)，通過調(diào)用Parallel-IO進行批量的讀取操作.而對于所有更改的節(jié)點數(shù)據(jù)，聚集起來通過Parallel-IO進行批量提交.如圖5所示，UDQ的更新操作集合批量更新推送到葉子節(jié)點的例子：

例：圖5中UDQ包含{op1，op2，…,opi}共i個更新操作.批量更新時，從root節(jié)點開始下推，以葉子節(jié)點LeafNode1為例，假設(shè)作用于它的更新操作為：{op1，op3，op7}.這3個操作分別是插入、修改、刪除.那么，它們將下推至LeafNode1，而對于LeafNode1的更新過程為：順序?qū)eafNode1執(zhí)行op1，op3，op7,即插入、修改、刪除操作.如果LeafNode1不滿足平衡約束，那么分裂或者重新插入兒子節(jié)點至R-樹，該操作在算法5的Balance-Rtree中進行.

Fig.5 An example of update operation pushing down圖5 更新操作下推例子

通過插入例子和更新下推例子，不難發(fā)現(xiàn)批量更新過程有2個特點：

1) 增加單次批量提交的數(shù)量，可增加單次批量提交I/O數(shù)量；

2) 更新操作之間可能會有重疊的作用節(jié)點.

這2個特點會增加R-樹更新操作的I/O效率.下面具體介紹批量更新算法實現(xiàn).

批量更新算法主要分為2個部分:1)批量更新操作，詳見算法4;2)R-樹的平衡維護算法，詳見算法5.

算法4為批量更新操作部分.同算法2的邏輯,算法4的輸入是R-樹根節(jié)點root和更新操作集合batchs,該部分維護了3個隊列：查詢隊列request_queue、節(jié)點隊列node_queue和數(shù)據(jù)隊列dataptr_queue.

算法4.BatchUpdate(root,batchs).

輸入：root為根節(jié)點、batchs為更新操作集合；

①balance_stack,read_queue,dataptr_queue←?;

②root.batchs←batchs;

③node_queue.pushback(root);

④ while (node_queue≠?‖read_queue≠?) do

⑤ while (node_queue≠?) do

⑥node←取出read_queue隊首節(jié)點;

⑦balancestack.push(node);

⑧ if (node非葉子節(jié)點) then

⑨ for (opinnode.batchs) do

⑩ if (op是插入操作) then

算法4終止條件：當node_queue和request_queue都為空時，意味著所有可能有更新的節(jié)點都搜索完畢，算法終止.見算法4行④.

當node_queue≠?時的詳細處理過程詳見算法4行⑤～.該部分遍歷所有的節(jié)點，找出所有batchs可能作用到的非葉子節(jié)點，把它們放入read_queue以形成批量提交集合，詳見算法4行⑧～.遍歷所有的葉子節(jié)點，將對應(yīng)的插入操作對其進行作用，詳見算法4行～；將非插入操作加入到數(shù)據(jù)子節(jié)點的更新操作中去，詳見算法4行～.最后把有含有更新操作的數(shù)據(jù)節(jié)點加入的dataptr_queue中去.詳見算法4行～.

read_queue≠?時的處理過程詳見算法4行～.固態(tài)硬盤的NCQ隊列的上限值記為NCQ-size.因此,Parallel-IO最多一次批量提交NCQ-size個IO請求.算法4構(gòu)建具有NCQ-size個讀請求的批量IO請求集合(詳見算法4行～).如果read_queue中請求數(shù)小于NCQ-size，且沒有內(nèi)存節(jié)點可以遍歷來為read_queue增加新的IO請求,則把read_queue中所有IO請求作為1個批量請求集合.最后，并行讀入批量請求集合中的所有節(jié)點到內(nèi)存，詳見算法4行～.

算法5.BalanceRtree(balance_stack).

輸入：balance_stack:廣度優(yōu)先遍歷節(jié)點的入棧集合;

① writequeue←?;*存儲有更新的節(jié)點*

②reinsert_list←?;

③ while(balance_stack≠?) do

④node←取出balance_stack棧頂元素;

⑤ if (node有更改) then

⑥ if (node.branchs>MAXNODES) then

⑦node,split_node←分裂node成左右節(jié)點;

⑧ 重新計算node.MBR,split_node.MBR;

⑨ 添加split_node到node.father.branchs;

⑩ if (node是根節(jié)點) then

then

如算法5所示，它有1個輸入?yún)?shù)是balance_stack.在算法4中，把遍歷到的節(jié)點按照廣度優(yōu)先的順序放進balance_stack堆棧(如算法4行⑦)，那么按照balance_stack的出棧順序，就是算法4中廣度優(yōu)先遍歷的逆序進行對R-樹自底向上維護平衡結(jié)構(gòu)，詳見算法5行③～.當node.branchs>MAXNODES時，進行分裂操作(行⑥～)；當node.branchs

5 性能測試

基于本文提出的優(yōu)化技術(shù)，在加州大學伯克利分校Antonin Guttman and Michael Stonebraker提供的開源內(nèi)存R-樹[12]的基礎(chǔ)上，實現(xiàn)經(jīng)典外存R-樹和優(yōu)化的R-樹，這里稱為Para-Rtree.

5.1 實驗設(shè)置

1) 測試平臺.本文測試Para-Rtree的平臺為Dell PowerEdge R730，配置為：2×6核Intel Xeon處理器；主頻1.90 GHz；32 GB內(nèi)存；系統(tǒng)盤為2TB 7200rpm機械硬盤；操作系統(tǒng)CentOS7.1，內(nèi)核版本為3.10.0，Linux內(nèi)部并行實現(xiàn)[13]的libaio庫版本為0.3.109；實驗對象為表3三塊固態(tài)硬盤.為了表達方便，下面將SSDSC2BB480G6R稱為Intel-480 G，SSDSC2BB800G6稱為Intel-800 G，SSDSC2KW240H6X1稱為Intel-240 G.為了消除文件緩存給實驗結(jié)果造成的影響，文件打開模式為O_DIRECT.所有固態(tài)硬盤均為新購買固態(tài)硬盤，實驗前并未進行特別的磨損處理(warm up).

2) 數(shù)據(jù)集合.測試使用的真實數(shù)據(jù)集合為美國50個州的路網(wǎng)數(shù)據(jù)，該數(shù)據(jù)來源于美國國家地理塊數(shù)據(jù)庫[14]，共計11 278 412條數(shù)據(jù)，每個元組包含經(jīng)緯度坐標和一組字符串屬性.查詢、更新操作的數(shù)據(jù)均由其隨機抽樣產(chǎn)生.

3) 實驗測試.本文實驗針對Para-Rtree和傳統(tǒng)R-樹性能對比進行實驗，5.2節(jié)索引構(gòu)建，用以測試Batch-Update對于插入操作的加速效果.在5.3,5.4節(jié)中，分別對于查詢、修改、刪除操作的加速效果進行實驗，并測試范圍對于加速效果的影響.最后，在5.5節(jié)中，對于查詢密集和更新密集2種情況的數(shù)據(jù)操作特點進行測試，檢驗Para-Rtree在2種情況下的加速效果.

Table 3 Testing SSD Parameters表3 待測固態(tài)硬盤規(guī)格參數(shù)

5.2 索引構(gòu)建

下面測試Para-Rtree構(gòu)建的時間代價和加速比.在構(gòu)建過程中，測試不同數(shù)據(jù)規(guī)模對于構(gòu)建代價和加速比的影響.索引構(gòu)建即是連續(xù)插入操作，因此本測試用以測試Batch-Update對于批量插入的優(yōu)化性能.

圖6描述了Para-Rtree的構(gòu)建時間和加速比隨著數(shù)據(jù)量的變化趨勢.這里從數(shù)據(jù)集合隨機抽取2×106～10×106條數(shù)據(jù)的數(shù)據(jù)形成數(shù)據(jù)集合{D2,D4,D6,D8,D10},包含5組測試數(shù)據(jù).用這5組測試數(shù)據(jù)集分別在Intel-240 G,Intel-480 G和Intel-800 G這3個固態(tài)硬盤上進行測試.如圖6(a)～(c)所示，橫坐標是構(gòu)建索引數(shù)據(jù)量，縱坐標為構(gòu)建時間.可以看出Para-Rtree和R-樹的構(gòu)建時間和數(shù)據(jù)規(guī)?；境删€性關(guān)系.圖6(d)展示了Para-Rtree在3款固態(tài)硬盤上對于索引構(gòu)建的加速效果，從圖6中可以看出3款固態(tài)硬盤，對于批量插入操作的加速效果差別很小，都在2倍上下.

Fig.6 Effects of object number on speed-up圖6 數(shù)據(jù)量對構(gòu)建加速的影響

5.3 查詢測試

下面測試Para-Rtree的查詢處理性能，測試內(nèi)容包含：不同查詢范圍對于Para-Rtree的查詢時間和加速效果的影響.設(shè)P為查詢范圍占整個數(shù)據(jù)集合MBR的比例.在索引構(gòu)建過程中，隨機生成的D10數(shù)據(jù)集合，構(gòu)建后會生成索引稱為Full-Index.下面所有的查詢和更新實驗都針對該索引進行.為了測試Para-Rtree對于查詢速度的提升以及范圍對于查詢加速效果的影響，分別生成覆蓋整個Full-Index區(qū)間MBR的0.1%,1%和10%這3組查詢操作，其中每個組查詢操作均有1 000個，這里針對Para-Rtree的Batch-Search和R-樹的傳統(tǒng)搜索算法分別進行實驗，并計算出每個操作的平均執(zhí)行時間.

如圖7所示，圖像展現(xiàn)了不同查詢范圍Para-Rtree和R-樹對查詢操作加速效果的影響.圖7(a)～(c)的橫坐標為3款不同的固態(tài)硬盤，縱坐標為單條查詢操作平均執(zhí)行時間，P用以區(qū)分不同的數(shù)據(jù)集合.圖7(d)展示了不同查詢范圍3款固態(tài)硬盤上Para-Rtree對于查詢的加速比.從圖7可以看出Intel-240 G和Intel-480 G對于查詢范圍的敏感程度低，而Intel-800 G查詢范圍越大，加速比越大.可以推測出Intel-800 G的內(nèi)部并行性更豐富，使得Para-Rtree對于查詢操作的加速效果更明顯.整體上來觀察，Para-Rtree提供了2.6以上的加速比，說明Para-Rtree能提供一個比較好的查詢加速效果.

5.4 更新測試

下面測試Para-Rtree更新處理性能，測試內(nèi)容包括：不同的修改范圍對于修改操作加速性能的影響；不同的刪除范圍對于刪除操作加速性能的影響.插入操作已經(jīng)在索引構(gòu)建時進行了測試，因此本節(jié)不再包含插入操作的性能測試.設(shè)P為查詢范圍占整個數(shù)據(jù)集合MBR的比例.同查詢測試，用D10構(gòu)建索引Full-Index，下面的更新測試均以該索引作為測試對象.為了測試Para-Rtree的Batch-Update對于修改和刪除算法的提升，分別生成覆蓋整個Full-Index區(qū)間MBR的0.1%，1%和10%這3組修改和刪除操作，其中每個組有1 000個操作，這里針對Para-Rtree的Batch-Update和R-樹的傳統(tǒng)修改和刪除算法分別進行實驗，并計算出每個操作的平均執(zhí)行時間.

圖8展現(xiàn)了不同修改范圍對Para-Rtree修改操作加速效果的影響.圖8(a)～(c)的橫坐標表示3款不同的固態(tài)硬盤，縱坐標為單條修改操作平均執(zhí)行時間，P用以區(qū)分不同的數(shù)據(jù)集合.圖8(d)展示了

Fig.7 Effects of search range on speed-up圖7 范圍對查詢操作加速的影響

Fig.8 Effects of modify range on speed-up圖8 范圍對修改操作加速的影響

不同查詢范圍對于3款固態(tài)硬盤上Para-Rtree修改操作加速的影響.從圖8中可以觀察到，無論是Intel-240 G,Intel-480 G還是Intel-800 G，修改范圍對于3款固態(tài)硬盤加速效果影響很小.但是與查詢測試的加速效果相比，Intel-240 G和Intel-480 G加速效果降低，而Intel-800 G卻有很大的提升.因此，進一步驗證：不同固態(tài)硬盤內(nèi)部并行性存在差異，這也導致Para-Rtree的加速效果存在差異.因此，對于內(nèi)部并行性豐富的固態(tài)硬盤，Para-Rtree能提供一個很可觀的修改操作加速效果.

圖9展現(xiàn)了不同修改范圍對Para-Rtree刪除操作加速效果的影響.圖9(a)～(c)的橫坐標表示3款不同的固態(tài)硬盤，縱坐標為單條刪除操作的平均執(zhí)行時間，P用以區(qū)分不同的數(shù)據(jù)集合.圖9(d)展示了不同刪除范圍，對于3款固態(tài)硬盤上Para-Rtree刪除操作加速的影響.可以觀察到刪除操作的加速比相對于查詢和修改都比較小，這是由于刪除會帶來R-樹和Para-Rtree索引的部分節(jié)點不滿足兒子節(jié)點的數(shù)量限制，需要先進行索引再平衡，大量的額外操作會削弱Para-Rtree的I/O并行性.盡管如此，Para-Rtree還是提供了一個可觀的加速比.從范圍對刪除操作加速的影響來看，3款固態(tài)硬盤加速效果相差無幾，且和刪除范圍沒有明顯的相關(guān)性.

Fig.9 Effects of remove range on speed-up圖9 范圍對刪除操作加速的影響

由圖8、圖9的更新測試實驗，可以得出結(jié)論：Para-Rtree對于修改的加速效果最明顯，對于刪除的效果最小.對于修改操作，不同固態(tài)硬盤加速效果差別較大，而刪除操作差別就很小.操作范圍擴大對于提升加速比有一定的提升，但是提升不顯著.

5.5 混合測試

圖10顯示查詢密集和更新密集2種情況下，Para-Rtree的加速比測試結(jié)果，本實驗用以驗證Para-Rtree在不同使用需求下的加速效果.

Fig.10 Effects of search intensive and update intensive on speed-up圖10 查詢密集和更新密集對加速效果影響

本次實驗共生成2組規(guī)模達106的查詢和更新范圍相同的實驗數(shù)據(jù)：第1組為查詢密集型數(shù)據(jù)，查詢數(shù)據(jù)占80%，更新數(shù)據(jù)占20%，在更新數(shù)據(jù)中插入、修改、刪除各占1/3；第2組為更新密集型數(shù)據(jù)，查詢數(shù)據(jù)占20%，而更新數(shù)據(jù)占80%，其中更新數(shù)據(jù)中插入、修改、刪除比例也均等.如圖10(a)為查詢密集型數(shù)據(jù)在3款不同固態(tài)硬盤上對Para-Rtree的測試時間圖，橫坐標為3款不同的固態(tài)硬盤，縱坐標為運行時間；圖10(b)為更新密集型數(shù)據(jù)在3款不同固態(tài)硬盤上對Para-Rtree的測試時間圖，橫縱坐標同圖10(a)所述；圖10(c)給出了加速效果對比圖，可以清晰觀察到，查詢密集型數(shù)據(jù)的加速要比更新密集數(shù)據(jù)的加速效果更好.這和5.2節(jié)查詢測試和5.3節(jié)更新測試的結(jié)果一致.

因此可以得出結(jié)論：Para-Rtree對于查詢密集加速效果突出，對于更新密集依然可以提供一個很好的加速效果.

6 總結(jié)和未來工作

本文基于批量式異步I/O提交技術(shù)，利用固態(tài)硬盤內(nèi)部并行性去加速R-樹查詢和更新操作，為此，根據(jù)R-樹的查詢和更新特點，提出Batch-Search和Batch-Update算法和協(xié)助實現(xiàn)批量提交增加并行性的UDQ隊列.通過理論分析和實驗證明，確定其能有效的提高效率.在實驗中發(fā)現(xiàn)不同的固態(tài)硬盤，內(nèi)部并行性存在差異.因此在選擇固態(tài)硬盤用作數(shù)據(jù)庫存儲盤時，考慮內(nèi)部并行資源豐富的固態(tài)硬盤作為存儲盤，以其能提供更高的并行帶寬.隨著閃存技術(shù)的進步和為擴充容量集成進越來越多的閃存包，固態(tài)硬盤內(nèi)部并行性越來越豐富，它將能起到更好的加速效果.因此，該工作有很大發(fā)展前景.目前批量式異步I/O提交技術(shù)是在文件系統(tǒng)之上實現(xiàn)，這樣以來，數(shù)據(jù)在固態(tài)硬盤上的分布對開發(fā)者來講就是一個黑箱，要想進一步提高加速比，需要直接操作固態(tài)硬盤來進行數(shù)據(jù)的分布和讀寫.因此考慮如何在文件系統(tǒng)下，利用固態(tài)硬盤內(nèi)部并行性進行查詢和更新加速是未來一個研究方向.