程 香

(安徽經(jīng)濟管理學院，安徽合肥 230059)

用回溯算法診斷數(shù)據(jù)庫性能故障

程 香

(安徽經(jīng)濟管理學院，安徽合肥 230059)

數(shù)據(jù)庫性能診斷至關重要，本文針對目前數(shù)據(jù)庫性能診斷過程依賴于經(jīng)驗的狀況，研究了一種基于回溯算法的數(shù)據(jù)庫性能診斷方法，提出了數(shù)據(jù)庫性能診斷過程的解空間樹構(gòu)造方法，以及診斷過程詳細的形式化算法，最后給出該方法的使用實例。該方法能夠避免數(shù)據(jù)庫性能診斷的盲目性，也可為其他系統(tǒng)性能診斷提供參考。

性能診斷；回溯算法；數(shù)據(jù)庫性能；自底向上

1 研究背景

數(shù)據(jù)庫出現(xiàn)性能故障，往往嚴重影響系統(tǒng)的運行效率，甚至引發(fā)系統(tǒng)崩潰，造成巨大的損失，因此數(shù)據(jù)庫設計及其運行過程中的性能故障診斷和優(yōu)化都具有重要意義。為了對數(shù)據(jù)庫進行診斷和優(yōu)化，文獻[1]開發(fā)了一個最大數(shù)目為60維的搜索應用程序，幫助用戶鑒別自己偏好查詢。文獻[2]分析了初始化參數(shù)選擇對數(shù)據(jù)庫效率和處理時間的影響，分析得出Oracle數(shù)據(jù)庫調(diào)優(yōu)在一個純粹自動化的方式下是不可能的。文獻[3]設計了一個名為CUDADB的內(nèi)存數(shù)據(jù)庫，以擴展帶CUDA的GPU數(shù)據(jù)庫系統(tǒng)性能。文獻[4]討論了屬性分配和聚集元組的組合問題，通過應用遺傳算法反復歸因分區(qū)和集群元組子問題，為混合碎片問題提出了一個新方法，實驗分析了不同遺傳參數(shù)的效果。

現(xiàn)有的數(shù)據(jù)庫優(yōu)化方法主要從產(chǎn)品設計開發(fā)階段著手[5-9]，但在設計開發(fā)階段對數(shù)據(jù)庫的性能管理有多全面，在實際的數(shù)據(jù)庫應用中不可避免地出現(xiàn)運行速度慢、客戶端卡死等故障。因此，數(shù)據(jù)庫的性能優(yōu)化應該歷經(jīng)軟件系統(tǒng)的設計、開發(fā)、上線整個生命周期。系統(tǒng)上線后數(shù)據(jù)庫性能的診斷是進行數(shù)據(jù)庫性能優(yōu)化的前提。目前，對數(shù)據(jù)庫性能的診斷主要依賴各種性能分析和調(diào)優(yōu)工具[10-13]。而數(shù)據(jù)庫性能故障可能由多種軟硬件原因引起，故障的診斷過程和結(jié)果分析，不僅依賴于輔助工具，還要一個有效的測試過程[14]。數(shù)據(jù)庫診斷過程基本憑借測試人員的經(jīng)驗執(zhí)行。為了優(yōu)化數(shù)據(jù)庫性能診斷過程，本文基于數(shù)據(jù)庫性能表現(xiàn)特征，將數(shù)據(jù)庫性能診斷問題轉(zhuǎn)換成解空間樹，更加清晰地描述和分析整個問題。引入相關經(jīng)驗數(shù)據(jù)，避免了數(shù)據(jù)庫性能診斷盲目性。對性能診斷過程的形式化定義，為與其他自動化化測試工具集成提供可能。

2 數(shù)據(jù)庫性能診斷及研究思路

精準有效的數(shù)據(jù)庫性能診斷主要取決于科學的診斷過程及診斷報告，其中科學的診斷報告主要依賴于測試工具度量的數(shù)據(jù)。性能測試工具種類繁多，且功能又交叉重疊，有IIS服務器工具IISTrace、微軟WinDbag、CLR內(nèi)存分析軟件CLRProfiler、并發(fā)工具LoadRunner、Linux性能監(jiān)控工具linux:nmon等。這些工具多數(shù)是將監(jiān)控和測試數(shù)據(jù)直觀地呈現(xiàn)出來，可以基本滿足對數(shù)據(jù)庫各個層面和各種負載下的診斷。數(shù)據(jù)庫的性能診斷是一項十分復雜的工程，從數(shù)據(jù)庫性能表現(xiàn)來看，不論是軟件或者硬件出現(xiàn)性能問題，都會導致硬件負載異常，而且內(nèi)存、CPU或者I/O等也會相互影響，數(shù)據(jù)庫的性能診斷過程要診斷出其影響性能的真正原因，需要層層剝離表象找出真正的問題。因此，一套有效的診斷方案對數(shù)據(jù)庫的性能故障診斷和優(yōu)化至關重要。

回溯算法是一種系統(tǒng)地從問題的解空間中搜索得到問題的可行解或者最優(yōu)解的算法。該算法通過對部分解進行增量構(gòu)建式搜索得到可行解，在構(gòu)建過程中采用一種試探性的法則。在數(shù)據(jù)庫性能診斷時，性能診斷人員利用經(jīng)驗知識對某性能表現(xiàn)分析得出的種種可能原因就是一個解空間，之后對性能問題的探查過程也正是一個推測與驗證的試探過程。回溯算法搜索過程符合數(shù)據(jù)庫性能診斷的規(guī)律，并且一個可行解向量的反序可為性能優(yōu)化路徑提供思路，即沿著可行解向量中最后一個元素向第一個向量方向出發(fā)，即可進行自底向上的性能優(yōu)化。下文探討如何改進回溯算法以適合診斷數(shù)據(jù)庫性能問題。

3 基于回溯算法的數(shù)據(jù)庫性能故障診斷

3.1 回溯算法設計

3.1.1 解定義

圖1是數(shù)據(jù)庫性能診斷問題的解空間樹表示。

圖1 數(shù)據(jù)庫性能診斷解空間樹結(jié)構(gòu)

本文使用向量V=(v0，v1，…，vh)來表示一個性能診斷的過程。

(1)v0：初始節(jié)點，為性能問題的初始表現(xiàn)；(2)vi：中間節(jié)點，表示經(jīng)由v0，v1，…，vi-1(0≤i≤h)層層深入推測出可能存在性能問題的軟硬件檢查點，其中vi∈(0，1)表示第i個檢查點存在性能問題的概率；(3)vh：葉子節(jié)點，表示經(jīng)由v0，v1，…，vh-1層層深入搜索到并且可度量性能值的檢查點，vh∈{0，1}表示第h個檢查點是否存在性能問題，vh=1表示第h個檢查點存在性能問題，vh=0表示第h個檢查點不存在性能問題。

為了描述性能診斷求解過程和性能診斷結(jié)果中相關元素，進行如下定義：

定義1 在解空間樹構(gòu)建過程中，稱那些未構(gòu)建完全的解V=(v0，v1，…，vj)(j

定義2 在解空間樹構(gòu)建過程中，稱構(gòu)建完全的解V=(v0，v1，…，vj)(j=h)為一個候選解，其中v0至vj均為其父節(jié)點未舍充的孩子中權(quán)值最大的節(jié)點，vj為葉子節(jié)點。

定義3 對于一個候選解，如果vj經(jīng)驗證有性能問題，那么該候選解被定義為一個可行解。其中V=(v0，v1，…，vj)(j=h)為一個診斷出性能問題的過程，vj處驗證出某種性能問題表明對該過程中推測是正確的。此時vj是一個確定的故障點，可作為性能優(yōu)化和調(diào)整的對象。

數(shù)據(jù)庫性能診斷問題的目標是找到一個或所有的可行解，即診斷出某個或多個性能故障。在解空間樹中，從根節(jié)點到葉子節(jié)點的一條路徑即為該問題的一個候選解，該路徑中，第i層節(jié)點到第i+1層節(jié)點之間邊的權(quán)值表示第i+1個節(jié)點存在性能故障的可能性大小，即某個候選解向量中vi+1的值。

3.1.2 葉子節(jié)點及其驗證

在解空間樹的構(gòu)建過程中，葉子節(jié)點的確定與驗證方法如下：

(1)驗證方法。目前有許多進行性能分析的工具可以實現(xiàn)日志跟蹤、服務器進程分析等功能，也有很多數(shù)據(jù)庫專門的性能調(diào)優(yōu)工具，如SQL提供的DMV，可以方便地通過查詢語句、等待與阻塞、索引、I/O操作等的統(tǒng)計信息來確定性能故障。故如果某個節(jié)點可由性能測試工具明確度量出性能參數(shù)(稱可驗證)，則記錄具體性能測試數(shù)值，與事先確定的性能基數(shù)對比，由此確定葉子節(jié)點是否存在性能問題。

(2)確定方法。某個節(jié)點可驗證，就被確定葉子節(jié)點。性能診斷的解向量V=(v0，v1，…，vh)中h的數(shù)值也由此動態(tài)生成，其實質(zhì)為性能診斷的深度。

3.1.3 剪枝函數(shù)

為了避免探測那些不可能產(chǎn)生性能問題的軟硬件，需要利用剪枝函數(shù)來去掉那些節(jié)點及其子孫分支，以減少搜索和驗證的工作量。在解向量的構(gòu)造過程中，為當前推測有性能問題的節(jié)點的每個子節(jié)點定義一個權(quán)值，權(quán)值由當前節(jié)點的性能表現(xiàn)來確定，表示出現(xiàn)概率的大小，并且對該節(jié)點的所有子節(jié)點根據(jù)權(quán)值降序排序，每次搜索某節(jié)點的子樹時，選擇其權(quán)值最大的節(jié)點作為下一個搜索節(jié)點。診斷時定義一個上界約束upbound(0

3.2 基于回溯算法的數(shù)據(jù)庫性能診斷

圖2為數(shù)據(jù)庫性能診斷方案框圖。構(gòu)建數(shù)據(jù)庫性能故障的解空間樹，可以明確勾勒出某性能問題通常涉及的異常表現(xiàn)范圍，對性能故障產(chǎn)生的原因作出更細致的分析。性能子問題搜索與性能子問題驗證是一個推測與驗證的過程。(1)性能子問題搜索，在求解搜索過程中通過歸約和修剪，提高性能診斷的效率。(2)性能子問題驗證，定義性能基數(shù)并利用輔助工具對當前的推測進行驗證。下面將針對數(shù)據(jù)庫系統(tǒng)給出基于回溯算法的性能診斷方法，將解空間樹的構(gòu)建與搜索分開討論。

圖2 數(shù)據(jù)庫性能診斷方案框圖

3.2.1 數(shù)據(jù)庫性能診斷解空間樹構(gòu)建

構(gòu)建數(shù)據(jù)庫性能診斷解空間樹的目的是限制數(shù)據(jù)庫性能故障診斷的范圍，同時將數(shù)據(jù)庫性能故障分解成若干個可能問題，進而作出更深層次的診斷。圖3為一個SQL Server數(shù)據(jù)庫性能診斷解空間樹的部分圖。

圖3 性能問題診斷解空間樹

解空間樹構(gòu)建過程分解如下：

(1)針對數(shù)據(jù)庫性能問題的表現(xiàn)，根據(jù)數(shù)據(jù)庫優(yōu)化工程師的經(jīng)驗，推測出現(xiàn)該異常表現(xiàn)可能的軟硬件原因，并分別估計它們的概率，再進行降序排序，即生成解空間樹根節(jié)點及其子節(jié)點，且對這些子節(jié)點進行降序排序；(2)選擇權(quán)值最大的子節(jié)點為當前節(jié)點，如果該節(jié)點是葉子節(jié)點，經(jīng)驗證有性能問題，則一個可行解構(gòu)建完成，停止構(gòu)建；否則執(zhí)行下一步；(3)針對當前節(jié)點，分析該節(jié)點性能特征的軟硬件原因及其存在概率，即生成某個節(jié)點的子節(jié)點，并分配權(quán)值后降序排序；(4)重復(2)和(3)過程。如果根據(jù)經(jīng)驗估計的概率能較準確反應某個節(jié)點與其子節(jié)點之間的性能表現(xiàn)與產(chǎn)生原因的關聯(lián)程度，則在可能沒有發(fā)生回溯時就已找到了一個可行解。如果沒有找到可行解，則根據(jù)回溯算法向上回溯至某一節(jié)點繼續(xù)構(gòu)造。

3.2.2 數(shù)據(jù)庫性能診斷求解過程描述

采用回溯算法動態(tài)查找數(shù)據(jù)庫性能問題，首先將解向量V設置成Ф，并將當前訪問節(jié)點設置為根節(jié)點v0。接著沿著根節(jié)點向下搜索，選擇解空間樹中第1層權(quán)值最大的節(jié)點v1作為解向量的第一個元素。如果v1不是一個葉子節(jié)點，那么當前解V=(v0)是一個部分解。此時，v1是一個活節(jié)點，下一步搜索以v1為根的子樹，選擇v1的權(quán)值最大的孩子v2作為解向量的第二個元素，如果v2仍然是一個活節(jié)點，繼續(xù)向v2的下一層節(jié)點進行搜索。反之，如果v2是一個死節(jié)點，則從v2回溯至其父節(jié)點v1。當?shù)玫搅艘粋€問題的部分解V=(v0，v1，…，vi)，需要vi+1把添加到解向量末尾時，其詳細操作情況如下：

(1)如果vi+1是一個中間節(jié)點，那么當前解是一個部分解，該部分解存在被構(gòu)建為可行解的可能性，因此對其孩子中權(quán)值最大的節(jié)點vi+2進行搜索。

(2)如果vi+1是一個葉子節(jié)點，此時，若vi+1經(jīng)驗證有性能問題，那么當前解是一個完全解，該完全解是一個可行解；若vi+1經(jīng)驗證無性能問題，則沿著解空間樹回溯至節(jié)點vi+1的父節(jié)點vi，并對其剩余孩子中權(quán)值最大的節(jié)點進行搜索，如果節(jié)點v1的所有孩子節(jié)點都已經(jīng)被搜索完畢，則回溯至節(jié)點vi的父節(jié)點vi-1。

不斷重復步驟(1)和(2)，直到找到一個可行解，或者根節(jié)點變?yōu)樗拦?jié)點。若根節(jié)點變?yōu)樗拦?jié)點時，仍沒有找到一個可行解，則表示利用該解空間樹中無法診斷出性能問題。

3.2.3 算法分析

本算法在找到一個可行解時即終止算法，因此每次搜索只能定位一個性能問題故障點，搜索過程屬于找出局部最優(yōu)解，因此不一定能找到最主要故障點，而可能存在其他性能故障點。因此，若要診斷某個異常表現(xiàn)的所有其他故障點，只有在回溯至解空間樹的根節(jié)點v0且v0的所有孩子節(jié)點都已經(jīng)搜索完畢時才可終止算法，此時整個解空間樹已經(jīng)被搜索完畢。

基于回溯算法的數(shù)據(jù)庫性能診斷是一種圖的深度優(yōu)先搜索，算法的時間復雜度由權(quán)值排序的時間復雜度和圖搜索的復雜度決定，如果要找到一個可行解，其最壞的情況是遍歷完整棵解空間樹，其復雜度為O(m+n+nlogn)，但在實際求解過程中，由于對性能問題分配的權(quán)值有上界約束，找到可行解的迭代次數(shù)遠小于這個值。

4 診斷實例

實例是用戶使用一個信息管理系統(tǒng)的報表查詢功能，查詢速度非常慢，其它功能正常。根據(jù)經(jīng)驗構(gòu)建的解空間樹如圖3所示。圖中各分支即為測試人員對該性能問題的原因分析，各節(jié)點連接線上的權(quán)值即為對各原因存在的概率估計。根據(jù)上節(jié)所述搜索解空間樹的方法，由性能問題描述首先判斷可能是內(nèi)存問題，再使用性能計數(shù)器對運行中的服務器做日志跟蹤，檢查發(fā)現(xiàn)內(nèi)存設置沒有問題，回溯至其父節(jié)點，選擇剩余未訪問的子節(jié)點中權(quán)值最大的進行訪問，即對SQL查詢語句進行診斷，通過監(jiān)控內(nèi)存和Dump內(nèi)存來分析，發(fā)現(xiàn)在代碼中有一方法長時間執(zhí)行致使堆棧中局部大量變量無法釋放。圖3中若要顯性地對SQL語句效率作更具體的形式化分析，則繼續(xù)對效率低的原因進行多維度推測并驗證。

5 結(jié)語

本文的目的是要從內(nèi)存、CPU、磁盤、網(wǎng)絡等性能表現(xiàn)來逐步深入地探測數(shù)據(jù)庫軟、硬件性能故障，甚至探查出數(shù)據(jù)庫的設計、開發(fā)階段的問題，作為對系統(tǒng)性能優(yōu)化和調(diào)整的依據(jù)。本文的主要工作是給出了一種數(shù)據(jù)庫性能診斷過程的解空間樹的構(gòu)建方法，以及以自然語言描述了基于回溯算法的數(shù)據(jù)庫性能診斷的求解過程，為數(shù)據(jù)庫性能診斷提供一個形式化方法，實踐案例表明該方法對性能診斷過程具有指導作用。下一步工作考慮如何將該方法與性能測試工具集成，以及如何減少經(jīng)驗數(shù)據(jù)的主觀性，更好地指導性能問題的搜索過程。

[1]Alwana A A,Ibrahima H,Yipa T C,et al.A performance evaluation of preference evaluation techniques in real high dimensional database[J].Procedia Computer Science,2012(10):894-901.

[2]Kacerka W,Kacerka J.Beyond databases,architectures and structures:Analysis of the effect of chosen initialization parameters on database performance[J].Communications in Computer and Information Science,2015(521):60-68.

[3]Chang Yue-shan,Sheu R K,YUAN Shyan-Ming, et al.Scaling database performance on GPUs[J]. Information Systems Frontiers,2012,14(4):909-924.

[4]Gorla N,Vincent N,Law D M.Improving database performance with a mixed fragmentation design[J].Journal of Intelligent Information Systems,2012,39(3):559-576.

[5]Osman R,Knottenbelt W J.Database system performance evaluation models-A survey[J].Performance Evaluation,2012(69):471-493.

[6]Mrozek D,Paliga A,Mrozek M B,et al.Beyond databases,architectures and structures:database under pressurescaling database performance tests in microsoft azure public cloud[J].Communications in Computer and Information Science,2015(521):69-81.

[7]Ou Y,Harder T.Database systems for advanced applications lecture notes:Improving database performance using a flash-based write cache[J].Computer Science,2012,7240:2-13.

[8]李艷麗,張興忠.云環(huán)境下基于LQNM的數(shù)據(jù)庫性能建模研究[J].計算機應用與軟件,2015(1):55-58.

[9]肖盼,黃萍.基于SQL語言執(zhí)行效能的關系數(shù)據(jù)庫性能測試研究[J].計算機與數(shù)字工程,2012(2):127-129.

[10]Clarke J.Oracle exadata recipes:Host and database performance monitoring[M].Apress,2013:411-444.

[11]Sileika R.Pro python system administration:Automatic MySQL database performance tuning[M].Apress, 2014:349-366.

[12]趙吉志.數(shù)據(jù)庫服務器性能測試方法的研究和實現(xiàn)[J].計算機研究與發(fā)展,2012,49(Suppl):352-356.

[13]徐增敏,張昆,丁勇,等.基于動態(tài)視圖的數(shù)據(jù)庫性能調(diào)[J].計算機應用與軟件,2012,29(12):58-60.

[14]FritcheyY G. SQL server query performance tuning:Data-base performance testing[M].Apress,2014:505-513.

Application of Backtracking Algorithm in Database Performance Diagnosis

CHENG Xiang

(Anhui Institute of Economic and Management, Hefei Anhui 230059, China)

Database performance diagnosis is essential for database systems. For the current situation that the process of database performance diagnosis depends on the experience of testers, this paper studied a database performance diagnosis method based on backtracking algorithm. It gives a way to construct the solution space tree of database performance diagnosis process, and a detailed formalized algorithm of diagnosis process. The paper also presents a concise use case of this method. The method can avoid blindness during the process of database performance diagnosis, and can also be used as a reference of other system performance diagnosis.

performance diagnosis; backtracking algorithm; database performance; bottom-up

2015-07-13

程 香(1982- )，女，安徽合肥人，安徽經(jīng)濟管理學院講師，碩士，從事算法設計、軟件性能分析研究。

TP3

A

2095-7602(2015)12-0030-05