混合存儲系統中數據庫對象的加權優化放置

白振中，牛保寧

（太原理工大學 計算機科學與技術學院，山西 太原030024）

0 引 言

雖然閃存硬盤 （SSD）有著磁性硬盤 （HDD）無法比擬的優越性，但是在可預見的將來，閃存硬盤很難完全替代磁性硬盤。因為磁性硬盤有著令人滿意的順序訪問性能，并且容量大，每GB 的成本低。另外，數據庫管理系統的數據結構和算法是基于磁性硬盤的，直接用閃存硬盤替換磁性硬盤，無法充分利用閃存硬盤的速度優勢，獲得的性能提升很難達到期望的程度［1］。在存儲層次體系結構中，磁性硬盤仍被認為是不可缺少的。因此，現階段閃存硬盤和磁性硬盤的混合存儲體系結構受到極大關注。

閃存硬盤和磁性硬盤混合存儲系統有3種常見類型：閃存硬盤作為磁性硬盤的擴展［2－4］，以提高磁性硬盤的性能，如圖1 （a）所示；閃存硬盤作為緩沖池的擴展［5－7］，以增加緩沖池的大小，如圖1 （b）所示；磁性硬盤作為閃存硬盤的寫緩存［8］，來延長閃存硬盤的壽命，如圖1 （c）所示。

圖1 SSD 和HDD 的3種混合存儲系統

對于閃存硬盤和磁性硬盤混合存儲系統，要想獲得期望的性能提升必須充分地利用閃存硬盤和磁性硬盤各自的特點。一方面要確定被頻繁訪問的數據對象并放置在閃存硬盤，以利用閃存硬盤的讀寫速度優勢并盡可能把密集型讀數據對象放置在閃存硬盤，以降低對閃存硬盤的損耗。另一方面要考慮把大尺寸和順序訪問的數據對象放置在磁性硬盤，以利用磁性硬盤的大容量和高性價比的順序訪問性能。

一般情況下，不同的負載具有不同的讀／寫比率和隨機訪問／順序訪問比率等特征。混合存儲系統性能的提升高度依賴工作負載的訪問特性。選擇合適的數據對象分別放置在閃存硬盤和磁性硬盤需要有效地、低開銷地維護數據訪問歷史，分析數據的訪問操作特征。

針對混合存儲系統中數據庫對象的放置，本文提出一種對于給定的負載選擇合適的數據庫對象放置在閃存硬盤的方法。該方法通過收集順序讀、順序寫、隨機讀和隨機寫4種操作的信息，根據4種操作在閃存硬盤和磁性硬盤上的不同操作特性，預測把給定對象放置在閃存硬盤獲得的性能改善，以確定在閃存硬盤上放置數據庫對象的最優方案，充分利用閃存硬盤和磁性硬盤各自的優勢，提高數據庫的性能。

1 相關工作

數據放置問題是計算機科學最古老的問題之一［9］。只要計算機系統可以訪問多種不同性能和成本的存儲設備，如何放置數據對象、以較低成本獲得最佳性能就是一項重要的任務。對于分布式環境面向列的數據放置中，文獻［10］通過利用集中式／分布式索引來提高訪問的效率，尤其是順序訪問的效率。本文也考慮隨機和順序操作在不同存儲設備的表現。在云計算平臺下，文獻 ［11］通過引入多維度顆粒方法識別不同大小的子負載，確定數據的最佳放置。文獻 ［12］依據閃存硬盤塊的磨損程度，為每一個閃存硬盤塊作標記，并把預計會頻繁更改的數據放置在標記小的閃存硬盤塊和預計在塊中停留很長時間和很少變化的數據放置在標記大的閃存硬盤塊，從而降低閃存硬盤的寫放大和磨損程度。本文通過寫操作占負載總讀寫操作的比例減少在閃存硬盤上的寫操作次數。

針對閃存數據庫緩沖區替換策略的寫操作優化，文獻［13］用閃存硬盤的讀寫延遲傾斜系數 （閃存硬盤的寫操作所需時間與讀操作所需時間的倍數）區分讀和寫操作在閃存硬盤上的不同代價。本文給予4種操作在性能提升上不同的權重時，利用閃存硬盤和磁性硬盤的讀寫比率。

對于閃存硬盤和磁性硬盤作為存儲介質的混合存儲系統，文獻 ［14－16］通過改造緩沖池替換算法來決定把每個頁或塊放置在閃存硬盤還是磁性硬盤。這種方法以一個頁或塊粒度做出存儲決定，不考慮一個頁或塊與其它頁或塊的關系。現有的方法根據閃存硬盤的成本和容量的限制，找到從磁性硬盤移動到閃存硬盤而獲得最大性能益處的對象。該方法未考慮4種訪問操作在閃存硬盤和磁性硬盤上的不同表現和閃存硬盤的壽命。為此，我們的方法通過賦予4種操作在性能提升上不同的權重來解決這個問題。

2 問題定義與求解

在閃存硬盤和磁性硬盤組成的混合存儲系統中放置數據庫對象就是把數據庫對象分為兩部分，一部分被存放在閃存硬盤，另一部分被存放在磁性硬盤。數據庫對象的優化放置目標是把隨機訪問較多和密集型讀的對象放在閃存硬盤，順序訪問較多和密集型寫的對象放在磁性硬盤以及使訪問數據庫的性能最優。這種性能最優是指對一組給定的數據庫操作所需的訪問時間最短。這組操作通常是對數據庫的典型操作。這種性能最優也可以表示為相對于整個數據庫被放置在磁性硬盤所獲得的性能提升最大。下面給出問題的形式定義。

在一個由閃存硬盤和磁性硬盤組成的混合存儲系統中，閃存硬盤作為磁性硬盤的擴展。假定閃存硬盤的存儲容量為C，磁性硬盤的存儲容量足夠大，能夠滿足數據庫D＝｛O1，O2，…，On｝的所有存儲和操作要求。其中Oi（i＝1，2，…，n）是D 的對象，其大小為ci，存放位置為xi，xi＝0表示存放在磁性硬盤，xi＝1表示存放在閃存硬盤。

對數據庫對象的4 種操作記為χ＝ ｛SR，SW，RR，RW｝，其中：順序讀為SR，順序寫為SW，隨機讀為RR，隨機寫為RW。對于Oi，以操作j∈χ訪問Oi的頁數記，則操作集可以記為：λ＝｛｜i＝1，2，…，n；j∈χ｝。設磁性硬盤和閃存硬盤執行一個該類型的I／O 頁操作各自所需的服務時間為和，把Oi從磁性硬盤移動到閃存硬盤數據庫所得到的性能改善為

鑒于4種操作對數據庫系統的性能具有不同的貢獻，下面討論它們對性能的具體影響。首先，相對于磁性硬盤，在讀寫速度方面，閃存硬盤已處于主導地位。對于隨機讀寫，閃存硬盤比磁性硬盤至少快一個數量級。而對于順序讀寫，閃存硬盤是磁性硬盤的1.5～5倍。閃存硬盤與磁性硬盤的讀寫速度比率可以區分隨機和順序操作在數據庫性能提升上的不同貢獻。其次，閃存硬盤的壽命主要取決于寫操作次數。讀操作幾乎不影響閃存硬盤的壽命，而寫操作的次數有限，損耗閃存硬盤的壽命。對于不同的負載，讀寫操作的占比不同。負載的寫操作所占比例越大，寫操作對閃存硬盤的磨損越頻繁，閃存硬盤的使用時間越短。對于有大量寫操作訪問的數據庫對象，把它從磁性硬盤移動到閃存硬盤會提升數據庫的性能，但是寫操作對閃存硬盤壽命的損耗會導致成本急劇增加，寫操作在數據庫整體性能提升上的相對重要性就會降低。在考慮閃存硬盤壽命的前提下，負載寫操作占負載總讀寫操作的比例與數據庫整體性能的提升負相關，負載讀操作占負載總讀寫操作的比例與數據庫整體性能的提升正相關，即：負載讀操作占負載總讀寫操作的比例可反映寫操作對數據庫性能提升貢獻的程度。

因而，我們把順序讀 （或隨機讀）操作對數據庫獲得性能改善的初始權重設置為閃存硬盤與磁性硬盤的順序讀（或隨機讀）速度比率。對于寫操作，隨著負載寫操作所占比例增加，寫操作對閃存硬盤的損耗變大，寫操作對數據庫整體性能提升的相對重要性降低，所以順序寫 （或隨機寫）操作對數據庫獲得性能改善的初始權重為負載讀操作占比和閃存硬盤與磁性硬盤的順序寫 （或隨機寫）速度比率的乘積。

令閃存硬盤的順序讀、順序寫、隨機讀和隨機寫速度分別記為SSR，SSW，SRR，SRW，單位為MB／S。磁性硬盤的平均順序讀、順序寫、隨機讀和隨機寫速度分別表示為HSR，HSW，HRR，HRW，單位為MB／S。負載的寫操作占比記為PW。則在數據庫性能提升上4種訪問操作的初始權重為

對4個初始權重歸一化處理，從而4種操作對數據庫獲得性能改善的權重為

那么，Oi從磁性硬盤移動到閃存硬盤數據庫獲得的加權性能改善為

要求對給定的操作集λ，尋找存放在閃存硬盤的對象子集S＝｛Oi｜xi＝1且Oi∈D，1≤i≤n｝使得訪問數據庫的性能最優，即

在求解對象的最佳放置時，貪婪算法往往得到是局部最優解，而不能保證獲得最優解。本文提出在對4種操作訪問數據庫對象獲得的性能改善設置權重之后，使用回溯法可獲得最佳放置。我們的放置算法如下：

輸入：n，C，ci，bi／＊n為對象的總個數，C為閃存硬盤的容量，ci為每個對象的大小，bi為每個對象從磁性硬盤移動到閃存硬盤數據庫獲得的加權性能改善＊／

輸出：xi／＊xi為對象的存放情況＊／

Backtracking （i，cb，cc）／＊i為第i個對象的計數值，cb為當前數據庫獲得的加權性能改善，cc為當前已用SSD的容量＊／

（1） IF m＞n THEN／／m 為 在SSD 中 存 放 的 對 象數量

（2） IFcb＞B’THEN／＊B’ 為把對象放在SSD數據

（3） 庫所獲得的最大加權性能改善＊／

（4） B’←cb； ／／把cb的值賦給B’

（5） FOR 對象的存放情況從1到m DO

（6） xi←tempxi；／＊tempxi暫存對象的存

（7） 放情況＊／

（8） END FOR

（9） END IF

（10） ELSE

（11） FORj為整數從0到1DO

（12） tempxi←j；

（13） IFcc＋ci＊tempxi≤C THEN

（14） cc＋＝ci＊tempxi；

（15） cb＋＝bi＊tempxi；

（16） Backtracking （i＋1，cb，cc）；／／遞 歸調用

（17） END IF

（18） END FOR

（19）END IF

（20）END

3 實驗及性能評估

本實驗采用BenchmarkSQL 數據庫性能測試工具，該工具可在Windows和Linux兩套平臺上運行、配置多種數據庫以及內嵌TPC－C測試腳本，能衡量數據庫的OLTP處理能力。TPC－C 是國際事務處理性能委員會模擬OLTP的一種測試環境。其操作環境包括一系列倉庫，每個倉庫有若干個終端，這些終端分別代表銷售站點和查詢站點。TPC－C測試執行5種不同的事務 （neworder，orderstatus，payment，delivery，stock－level），逼真 地 模 擬OLTP 在 高并發環境下的應用。同時我們使用三星830SSD 閃存硬盤的讀寫性能作為評估基準。

3.1 實驗準備

實驗環境是Windows Server 2008＋DB2v9.5 數據庫，TPC－C數據庫模式依據國際標準。同時為提高效率，在customer表 的 （c－w－id，c－d－id，c－last，c－first）列 和order表的（o－w－id，o－d－id，o－c－id，o－id）列上建立索引，并裝入10個倉庫的數據，大約為1G。該實驗使用三星830SSD 閃存硬盤的大小為256MB，其讀寫性能采用官方測試數據。

在實驗中，我們設置5種事務neworder，orderstatus，payment，delivery，stock－level的比重分別為45%，14%，14%，14%，13%和終端數為10。我們采集連續5次的獨立實驗數據，并取其平均值。用我們的算法獲得的優化結果是：對象CUSTOMER，CUSTOMER＿IX，OORDER，NEW＿ORDER，NEW ＿ORDER＿IX，ITEM，ITEM ＿IX，DISTRICT，WAREHOUSE存放在閃存硬盤，其余的放在磁性硬盤。數據存放大小見表1。

表1 在SSD 和HDD 存放數據大小

3.2 數據獲取

3.2.1 對象頁的磁性硬盤訪問時間

為獲得每個對象的磁性硬盤訪問時間，包括平均順序讀、順序寫、隨機讀和隨機寫頁的訪問時間，我們為每一個對象建立單獨的表空間和緩沖池。

IBM DB2的緩沖池快照能監視緩沖池的活動。緩沖池快照中的輸出參數：異步讀取 （或寫入）總計耗用時間，異步池數據 （或索引）頁讀取，異步池數據 （或索引）頁寫入，緩沖池總計讀取 （或寫入）時間，緩沖池數據 （或索引）物理讀取，緩沖池數據 （或索引）寫入可用來計算一個對象頁的平均順序讀、順序寫、隨機讀和隨機寫訪問時間。

（1）對象頁的平均順序訪問時間

當需要從存儲設備順序讀一個對象頁時，DB2使用預取器發出異步讀請求。數據庫管理器代理程序發送這些異步請求到一個通用的預取隊列。在預取器可用時，它們執行這些請求以便從存儲設備獲取被請求的頁到緩沖池。因此，可以使用異步讀訪問參數找到表空間的順序讀時間。與讀相似，異步寫訪問參數可獲得表空間的順序寫時間。緩沖池快照中的異步讀取總計耗用時間表示一個數據 （或索引）頁的順序讀總計花費時間，異步池數據頁讀取提供順序讀數據對象頁的數量，則一個數據對象頁的平均順序讀訪問時間等于異步讀取總計耗用時間除以異步池數據頁讀取。把異步池數據頁讀取換成異步池索引頁讀取可計算索引對象頁的平均順序讀訪問時間。

（2）對象頁的平均隨機訪問時間

由于同步請求取到頁的范圍相對較小，所以DB2不能處理同步I／O 請求。因而，同步訪問時間可測量數據和索引對象頁的隨機訪問時間。緩沖池快照參數不包括同步I／O 時間和同步訪問頁的數量。然而，這些參數可以通過緩沖池快照中的參數計算得到。緩沖池總計讀取時間減去異步讀取總計耗用時間可得到同步讀取總計耗用時間，即一個數據 （或索引）對象頁的隨機讀取總計花費時間。緩沖池數據物理讀取減去異步池數據頁讀取可獲得同步池數據頁讀取，即隨機讀一個數據對象頁的數量。對于索引對象，我們可通過緩沖池索引物理讀取減去異步池索引頁讀取得到索引對象同樣的參數。那么，同步讀取總計耗用時間除以同步池數據頁讀取便可獲得一個數據對象頁的平均隨機讀訪問時間。重復同樣的步驟可計算一個索引對象頁的平均隨機讀訪問時間。對于寫相關的參數，通過把讀相關的參數替換成寫相關的參數，應用同樣的步驟便可得到。

3.2.2 閃存硬盤的讀寫性能

閃存硬盤的讀寫性能，包括順序讀、順序寫、隨機讀和隨機寫一個頁閃存硬盤服務的時間，并且4種操作的訪問時間幾乎是恒定的，這能準確估計對象從磁性硬盤移動到閃存硬盤獲得的性能改善。

3.3 實驗結果分析

如圖2和圖3 所示，與對象放置建議的貪婪法相比，我們的方法在閃存硬盤存放較多隨機訪問的頁和磁性硬盤存放較多順序訪問的頁，這表明閃存硬盤與磁性硬盤的4種操作訪問速度的比率可以體現隨機和順序操作在不同存儲設備上的差異，合理地實現對象在閃存硬盤和磁性硬盤的放置。

圖2 在SSD 中隨機訪問頁的數量

由于閃存硬盤寫操作次數的限制，寫操作會耗損閃存硬盤的壽命，閃存硬盤適合存放密集型讀的對象。通過負載讀操作所占比例體現寫操作在數據庫性能提升上的貢獻程度，閃存硬盤寫入的頁數減少而讀取的頁數增加，從而延長閃存硬盤的壽命，如圖4和圖5所示。

圖3 在HDD 中順序訪問頁的數量

圖4 在SSD 中讀取頁的數量

圖5 在SSD 中寫入頁的數量

TPC－C的性能由TPC－C 吞吐率衡量，單位是tpmC。tpmC是每分鐘內系統處理的新訂單個數。在實驗中，我們獲得TPC－C吞吐率，如圖6所示。閃存硬盤作為磁性硬盤的擴展可提高數據庫的整體性能。另外與對象放置建議提供的方法相比，我們的方法使得隨機訪問較多和密集型讀的對象存放在閃存硬盤，順序訪問較多和密集型寫的對象存放在磁性硬盤，實現數據庫對象的合理放置，從而提高數據庫的整體性能。

4 結束語

圖6 TPC－C吞吐率

本文提出數據庫對象在混合存儲系統中的優化放置方法。針對順序讀、順序寫、隨機讀和隨機寫4 種操作在不同存儲設備上的差異，根據不同的負載，把數據庫對象從磁性硬盤移動到閃存硬盤，本文賦予在4種訪問操作下數據庫獲得的性能改善不同的權重，然后利用回溯法實現對象放置。與現有的方法相比該方法可使數據庫對象存放在合適的存儲設備，充分利用閃存硬盤和磁性硬盤的不同性能特征，提高數據庫的性能。

然而，有些情況是僅需要訪問表或索引中的部分數據，因而希望僅把表或索引中需要的片段放在閃存硬盤，所以全部表和索引的粒度較粗，以細粒度做出存儲決定是我們今后研究的重點。

［1］Koltsidas I，Viglas SD.Data management over flash memory［C］／／Proceedings of the ACM SIGMOD International Conference on Management of Data，2011：1209－1212.

［2］Yang Q，Ren J.I－CASH：Intelligently coupled array of SSD and HDD ［C］／／IEEE 17th International Symposium on High Performance Computer Architecture，2011：278－289.

［3］Chen F，Koufaty DA，Zhang X.Hystor：Making the best use of solid state drives in high performance storage systems［C］／／Proceedings of the International Conference on Supercomputing.ACM，2011：22－32.

［4］XU Chang，SHOU Lidan，CHEN Gang，et al.An flashbased hybrid storage model for database ［J］.Journal of Zhejiang University （Engineering Science），2012，46 （2）：294－300 （in Chinese）.［徐昶，壽黎但，陳剛，等.一種基于閃存的數據庫復合存儲模型 ［J］.浙江大學計算機報，2012，46（2）：294－300.］

［5］Canim M，Mihaila GA，Bhattacharjee B，et al.SSD bufferpool extensions for database systems ［J］.Proceedings of the VLDB Endowment，2010，3 （2）：1435－1446.

［6］Kang WH，Lee SW，Moon B.Flash－based extended cache for higher throughput and faster recovery ［J］.Proceedings of the VLDB Endowment，2012，5 （11）：1615－1626.

［7］Oh Y，Choi J，Lee D，et al.Caching less for better performance：Balancing cache size and update cost of flash memory cache in hybrid storage systems［C］／／Proceedings of the 10th USENIX Conference on File and Storage Technologies.USENIX Association，2012：25.

［8］Soundararajan G，Prabhakaran V，Balakrishnan M，et al.Extending SSD lifetimes with disk－based write caches ［C］／／8th USENIX Conference on File and Storage Technologies，2010：101－114.

［9］Canim M，Mihaila GA，Bhattacharjee B，et al.An object placement advisor for DB2using solid state storage ［J］.Proceedings of the VLDB Endowment，2009，2 （2）：1318－1329.

［10］Zhou M，Xu C.Optimized data placement for column－oriented data store in the distributed environment［G］.LNCS 6637：Database Systems for Adanced Applications.Springer Berlin Heidelberg，2011：440－452.

［11］Lorey J，Naumann F.Towards granular data placement strategies for cloud platforms［C］／／IEEE International Conference on Granular Computing，2010：346－351.

［12］Hu XY，Haas R，Evangelos E.Container marking：Combining data placement，garbage collection and wear levelling for flash ［C］／／IEEE 19th International Symposium on Modeling，Analysis ＆Simulation of Computer and Telecommunica－tion Systems，2011：237－247.

［13］SHOU Lidan，LIAO Dingbai，XU Chang，et al.PWLRU：A buffer replacement algorithm for flash－based database［J］.Journal of Zhejiang University （Engineering Science），2010，44 （12）：2257－2264（in Chinese）.［壽黎但，廖定柏，徐昶，等.PWLRU：一種面向閃存數據庫的緩沖區存取算法 ［J］.浙江大學學報（工學版），2010，44 （12）：2257－2264.］

［14］Liu X，Salem K.Hybrid storage management for database systems［J］.Proceedings of the VLDB Endowment，2013，6（8）：541－552.

［15］Huang S，Wei Q，Chen J，et al.Improving flash－based disk cache with lazy adaptive replacement［C］／／IEEE 29th Symposium on Mass Storage Systems and Technologies，2013：1－10.

［16］Do J，Zhang D，Patel JM，et al.Turbocharging DBMS buffer pool using SSDs［C］／／Proceedings of the ACM SIGMOD International Conference on Management of data，2011：1113－1124.