用回溯算法診斷數據庫性能故障

程 香

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

用回溯算法診斷數據庫性能故障

程 香

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

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

性能診斷；回溯算法；數據庫性能；自底向上

1 研究背景

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

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

2 數據庫性能診斷及研究思路

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

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

3 基于回溯算法的數據庫性能故障診斷

3.1 回溯算法設計

3.1.1 解定義

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

圖1 數據庫性能診斷解空間樹結構

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

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

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

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

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

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

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

3.1.2 葉子節點及其驗證

在解空間樹的構建過程中，葉子節點的確定與驗證方法如下：

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

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

3.1.3 剪枝函數

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

3.2 基于回溯算法的數據庫性能診斷

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

圖2 數據庫性能診斷方案框圖

3.2.1 數據庫性能診斷解空間樹構建

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

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

解空間樹構建過程分解如下：

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

3.2.2 數據庫性能診斷求解過程描述

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

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

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

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

3.2.3 算法分析

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

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

4 診斷實例

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

5 結語

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

[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]李艷麗,張興忠.云環境下基于LQNM的數據庫性能建模研究[J].計算機應用與軟件,2015(1):55-58.

[9]肖盼,黃萍.基于SQL語言執行效能的關系數據庫性能測試研究[J].計算機與數字工程,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]趙吉志.數據庫服務器性能測試方法的研究和實現[J].計算機研究與發展,2012,49(Suppl):352-356.

[13]徐增敏,張昆,丁勇,等.基于動態視圖的數據庫性能調[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- )，女，安徽合肥人，安徽經濟管理學院講師，碩士，從事算法設計、軟件性能分析研究。

TP3

A

2095-7602(2015)12-0030-05