基于K-means的SAMP系統數據庫查詢性能優化策略①

馬 躍,王喆峰,尹震宇,王春曉,李明時,廉夢佳

1(中國科學院大學 計算機與控制學院,北京 100049)

2(中國科學院 沈陽計算技術研究所,沈陽 110168)

目前SAMP 系統以劃分的14 個區域中心為邏輯層級結構，在物理結構設計上采用集中的單系統架構,這使得系統的架構層次變得簡潔.同時隨著系統間與模塊間的交互變得可控,也減輕了系統交換層的壓力.但由于SAMP 系統已在全院114 個所運行,8000 臺設備在線，因此這種架構設計在應對每天千級以上的并發訪問及百萬級以上數據存儲問題時,系統整體性能有待提高.

1 SAMP 系統性能瓶頸分析

1.1 SAMP 系統實體關系概念模型

系統中存在著兩個核心的實體,分別為用戶和儀器.系統中的其他實體,如研究所、儀器管理員、委托單、耗材、實驗標準等均是在用戶與儀器的基礎上抽象衍生出來的.

在實體之間還存在著多種關系,這種關系可能是實體間的包含關系,也可能是實體間的操作關系.例如研究所和儀器之間具有"屬于"的包含關系,用戶和儀器之間具有包括"使用"、"預約"、"查看"或者"收藏"等多種操作關系.根據上面的描述,SAMP 系統實體關系核心概念模型如圖1所示.

圖1 SAMP 系統實體關系核心概念模型圖

1.2 SAMP 系統性能潛在瓶頸

SAMP 系統的核心業務之一為用戶對儀器的預約.由于用戶對儀器的預約操作關系在SAMP 系統實體關系概念模型中是一個多對多的關系,因此在數據庫中需要單獨建表處理該關系,即創建預約表.該表中記錄了用戶的全部預約儀器記錄,這樣導致了以下兩個問題：

(1)隨著請求并發量的提高,由于系統在處理預約操作的時需要對數據庫進行并發場景下的讀寫操作,千級并發量導致系統整體性能明顯下降.

(2)當預約表數據量達到百萬級別時,對預約表進行查詢操作將消耗大量系統資源與時間.

由此可見,用戶對儀器的預約操作以及后續對該預約委托單狀態的維護將使應用服務器與數據庫之間發生頻繁的讀寫操作,因此用戶對儀器的預約操作使得系統整體性能受到影響.

1.3 待解決的核心問題

從數據庫層面去考慮處理高并發與海量數據存儲問題的基本的解決方案[1],國內外現有的研究普遍從如下數據存儲結構與數據查詢性能兩個方面出發提出一系列解決方案.例如文獻[2]中作者提出了一種基于哈希算法的數據庫切分(sharding)策略,并試圖從數據存儲結構方面解決海量數據存儲問題并減少數據庫的負擔,縮短大數據量表的查詢時間,從而達到提升系統整體性能的目的.文獻[3]中作者提出了通過在MySQL數據庫中合理地設置索引與游標的方式達到提高數據表的查詢效率.而在這之前,還需要解決如下問題[4-7]：

(1)確定切分規則,即采用何種策略能夠將數據合理的切分開,使得在后續從不同維度對預約表進行查詢時都能保證查詢性能.預約表與用戶表和儀器表之間存在主外鍵關系,因此預約表中的主鍵為自動遞增的整數,并沒有實際意義.現有研究中通常采用的Hash 取模切分算法將不再適用,必須根據預約表的特點制定合理的切分規則[8-11].

(2)對數據庫進行切分后,處理查詢請求時必須準確定位該請求需要查詢的子庫或子表.

(3)當各個子庫和子表的容量達到閾值時采取何種策略進行擴容.

根據目前SAMP 系統中對區域中心的定義和劃分以及系統架構中的各個所級服務器與中心服務器之間的關系,可以看出用戶對儀器的預約操作存在一定的聚集性.因此,核心問題被定義為：選取合適的特征變量對預約記錄進行聚類分析,并根據聚類結果選取合理的切分規則對數據庫進行水平切分,使得切分后的數據庫能夠提升預約表的查詢性能,從而提高整體系統的性能[12-15].

2 基于聚類的數據庫分表

根據SAMP 系統實體關系概念模型可知,對預約表進行聚類分表時特征變量的選擇需要結合用戶表與儀器表共同分析.用戶表、儀器表以及預約表的核心表結構如表1、表2和表3所示.

表1 用戶表核心表結構

表2 儀器表核心表結構

表3 預約表核心表結構

根據上面對用戶表、儀器表和預約表的核心表字段結構的分析,根據聚類劃分標準的不同,可以分為按照所屬研究所劃分或按照所屬區域中心劃分.但是無論采用哪種方法進行聚類分析,特征變量均包含以下兩個方面.

(1)能夠標識用戶,例如用戶所屬研究院ID 和用戶所屬區域中心ID.

(2)能夠標識儀器,例如儀器所屬研究院ID 和儀器所屬區域中心ID.

同時,在聚類時不僅需要選取合理的特征變量,而且還需要在數據清洗和數據預處理階段保證數據的正確性.例如,需要保證用戶具有預約權限、儀器能夠被預約、預約的時間段有效等.

2.1 聚類分析分表

根據選取的特征變量可以將預約表中的每一條數據使用一個二維向量表示.根據SAMP 系統實際業務架構可知,預約用戶與被預約的儀器均以區域中心為基準呈現一定的聚集性,因此本文采用K-means 聚類算法按照區域中心對預約數據進行聚類.

K-means 聚類算法通過迭代計算各個點與質點之間歐氏距離的平均值,將數據集D 中的數據劃分到K個簇C1,…,Ck中,使得對于1≤i,j≤k,Ci?D且Ci∩Cj=Φ.這樣的劃分結果使得每一個簇內的對象相互相似,而簇與簇之間對象存在差異得到最終分類結果.K-means 聚類算法是一種基于形心的劃分算法,在得到最終K個類的同時也得到K個形心Ci,數據對象P∈Ci與該簇的代表Ci之差用dist(P,Ci)度量,其中dist(x,y)是兩個點x和y之間的歐式距離,因此聚類目標是使得各類的聚類平方和最小,即最小化公式如下：

K-means 聚類算法的時間復雜度與預約表中的數據總量N,聚類后的簇數K,以及程序的迭代次數t具有線性關系.結合實際應用場景中的數據規模可知,K和t為常數級別且均遠小于N.因此當預約數據總量N逐漸變大時,K-means 聚類算法相對可伸縮且有效[13].

根據聚類結果將預約表數據依次劃分到各個分表中.為保證預約表數據讀寫請求能夠準確定位到各個分表,需要在劃分的過程中動態構建分類映射和分類路由.分類映射由分類結果表和分表結果表構成.其中分類結果表的數據在聚類完成后填充的,記錄了聚類結果的類標號、核心點坐標以及聚集類的規模.分表結果表是在聚類的過程中動態填充的,主要記錄了子表標號、子表表名、分類標號以及子表規模.而分類結果表中的類標號與分表結果表中的類標號具有主外鍵關系.分類結果表和分表結果表的表結構如表4、表5所示.

由于分表的策略是根據區域中心ID 進行聚類劃分,因此無論從何種實體角度對預約表進行查詢最終都會將查詢對象按照其所屬的區域中心轉換成去相應分表中查詢的方式.因此分表路由表保存了每一個區域中心被哪些簇所包含,分表路由表結構如表6所示.

表4 分類結果表表結構

表5 分表結果表表結構

表6 分表路由表表結構

當預約表中插入新數據時,要對新插入的數據利用聚類模型進行聚類,步驟如下：

(1)獲取新數據的聚類二維特征點P(x,y).

(2)計算P與聚類模型中各個形心C1,…,Ck的歐式距離d1,…,dk,將P劃分到與各個形心歐式距離最小的簇Cp中,并更新Cp的形心坐標.

(3)更新分類映射和分表路由數據.如果該條預約記錄中涉及到的區域中心ID 與簇Cp的映射在分表路由表中不存在,則將映射關系添加到分表路由表中.

(4)更新分類結果中簇Cp的形心坐標(xp,yp)和該簇的聚類規模Mp如下：

2.2 分表后的擴容策略

即使將預約表進行分表處理后,每一張子表的數據量也會隨著時間增加而增加,當子表的數據量增加到一定的數量級后,子表的查詢性能仍然會下降.因此在分表的同時也需要為子表制定合理的擴容策略來解決由于子表數據量的增加而導致的查詢性能下降問題.

評判分表擴容策略的標準是擴容過程中的數據遷移量.在分表的過程中,維護了分類映射和分表路由,并且設置子表的負載因子f,若每一張子表的數據規模為M,則子表的閾值S與負載因子f和數據規模M具有如下關系：

假設當前存在預約子表T,T所屬的類標號為C,當T的數據容量達到閾值N后需要對T進行擴容處理.系統的擴容策略為：新建預約子表T’,將其添加到子表結果表中,設置T’—所屬的類標號為C,重置T’的數據容量為零,并將T在分表結果表中的數據添加標志位置零,表示不再向T中添加數據.這樣當再有類標號為C的預約數據插入時,會直接分配到T’中,而T中的原始數據仍然保存在T中,從而達到了原始數據零遷移的分表擴容目的.

而當出現新的分類標號導致分表需要增加時,首先將分類結果添加到分類結果表中,創建與之映射的子表,再將子表記錄添加到分表結果表,并更新分表路由,最后將涉及到的區域中心ID 與分類結果ID 添加到分表路由表中,同樣也能實現零數據遷移擴容.

3 實驗分析

本實驗使用SAMP 系統開發環境中仿真鏡像數據庫中存儲的預約記錄、用戶信息及儀器信息.服務器系統為CentOS7,數據庫使用MySQL 5.5，默認存儲引擎InnoDB.

3.1 實驗數據說明與處理

數據分為兩部分使用,部分數據用于構建最小訓練樣本數據集,對預約記錄進行聚類分析;剩余數據用于測試基于區域中心的聚類分表策略對系統查詢性能的提升效果.經過實驗測試發現當預約記錄的數據達到四萬條即可對預約數據集進行有效劃分,因此用于構建最小訓練樣本數據集的數據量N的值為：

實驗對用戶表、儀器表和預約表進行聚類分析時,重點采集了包括用戶ID、用戶所屬區域中心ID、用戶權限標志位、儀器ID、儀器所屬區域中心ID、儀器狀態標志位、預約單開始時間、預約單結束時間和預約記錄ID 在內的九維特征屬性共同對訓練樣本數據集進行處理和分析,并分析得出這些特征屬性具有以下特點：

(1)區域中心ID 為一個取值在[10,24]內的整數,其中處于[10,23]區間內的整數表示現有的14 個區域中心ID,區域中心ID 值為24 表示院外單位.

(2)用戶ID 號是一個八位整數,其中前兩位是用戶所屬的區域中心ID,中間兩位是用戶所屬的研究院ID,后四位是遞增的數字.

(3)儀器ID 同樣是一個八位整數,不同于用戶ID,儀器ID 的前兩位是儀器所屬區域中心ID 乘以四,后六位表示的含義與用戶ID 號相同.

在聚類前需要對樣本數據進行數據清洗與預處理確保數據的正確性,具體過程如下：

(1)去除用戶權限標志位為0 的預約記錄,即去除無預約權限用戶的預約記錄.

(2)去除儀器狀態標志位為0 的預約記錄,即去除預約無效儀器的預約記錄.

(3)根據每一條預約記錄的開始時間和結束時間,去除預約時間少于0.5 小時的預約記錄.

最終每一條預約記錄由一個三維向量(預約記錄ID,用戶ID,儀器ID)唯一表示,并使用其中的后兩維屬性進行聚類.

3.2 實驗方法設計

本實驗對訓練樣本集使用K-means 算法根據用戶所屬區域中心ID 和儀器所屬區域中心ID 進行聚類分析并根據聚類結果將數據庫中的預約表進行水平切分.實驗構建的訓練樣本集數據量為669010.同時根據每一條預約記錄的預約ID 在聚類的過程中動態構建分類結果表和分表結果表,并在完成聚類后構建分表路由表.其初始聚類結果如圖2所示.

圖2 初始聚類結果圖

完成聚類模型的構建后,配合分類映射與分類路由以及分表擴容策略對全部預約數據表進行分表.為了測試分表對整體數據表查詢性能的提升,實驗定義三組查詢測試語句分別從用戶、儀器以及并發預約查詢三方面進行測試.設計實驗測試如下.

分表前,查詢事件在預約總表中查詢,獲取查詢結果,記錄查詢時間.分表后,查詢事件通過以下幾步獲取查詢結果,記錄查詢時間：

(1)獲取查詢對象所屬區域中心ID.

(2)在分類路由中查詢包含此區域中心ID 的子表ID.

(3)在各子表中進行查詢.

在同等實驗條件前提下,通過對三組查詢測試語句執行時間的比較來分析聚類分表對查詢性能的提升效果,設分表前查詢平均執行時間為t1,分表后查詢平均執行時間為t2,則分表查詢提升效率f為：

本實驗對查詢時間及查詢性能的測試均忽悠數據庫對相同查詢結果的緩存影響,即在MySQL 數據庫中對查詢語句添加“sql_no_cache”關鍵字來禁用查詢緩存,從而多次實驗取平均執行時間.

3.3 實驗結果分析

實驗從用戶角度進行查詢測試,選取查詢事件：查詢用戶ID 為userID 的用戶預約的所有儀器.分表前實驗設置在禁用查詢緩存的條件下執行該查詢100 次,平均查詢時間0.364 秒,具體查詢時間分布如圖3所示.

圖3 分表前用戶預約記錄查詢時間分布圖

將預約表進行分表處理后,在同等實驗條件下設置執行該查詢100 次,平均查詢時間0.111 秒,具體查詢時間分布如圖4所示.

實驗從儀器角度進行查詢測試,選取查詢事件：查詢儀器ID 為apparatusID 的儀器所有被預約記錄.分表前實驗設置在禁用查詢緩存的條件下執行該查詢100 次,平均查詢時間0.355 秒,具體查詢時間分布如圖5所示.

圖4 分表后用戶預約記錄查詢時間分布圖

圖5 分表前儀器被預約記錄查詢時間分布圖

將預約表進行分表處理后,在同等實驗條件下設置執行該查詢100 次,平均查詢時間0.075 秒,具體查詢時間分布如圖6所示.

圖6 分表后儀器被預約記錄查詢時間分布圖

實驗選取并發查詢事件為：并發查詢儀器ID 為apparatusID 的儀器被預約的記錄.實驗使用Apache JMeter 工具模擬多用戶同時預約的并發場景,設置所有線程數在一秒內全部啟動,設置數據庫連接池的最大連接數為50,最大等待連接時間為120 秒,并配置數據庫驅動與JDBC 連接參數.根據實際SAMP 系統運行經驗,設置線程并發數為1000,即設置了在同一時間段中的最大并發量為1000.則分表前后對并發查詢事件的查詢性能統計如表7所示.

表7 分表前后對并發查詢事件的查詢性能統計

表7中各個字段的含義如下：

(1)Average：查詢的平均響應時間.

(2)Median：響應時間的中間值,即在全部請求中一半請求的響應時間低于該值,一半請求的響應時間高于該值.

(3)Min：請求的最短響應時間.

(4)Max：請求的最長響應時間.

(5)Throughput：吞吐量,即每秒處理的請求數.

由上述實驗可知,根據SAMP 系統實際區域中心ID 進行聚類分析并按照聚類結果對預約表進行分表處理后,從預約用戶角度對預約表進行查詢操作的查詢性能提升率為69.5%;從被預約的儀器設備角度對預約表進行查詢操作的查詢性能提升率為78.9%;從并發查詢角度對預約表進行查詢操作的查詢性能提升率為88.9%.

4 結論與展望

在SAMP 系統開發環境仿真數據庫中應用基于K-means 聚類的數據庫分表策略,其中包含的的聚類策略以及分表擴容策略均在SAMP 系統的應用中具有實際意義,因此彌補了當前主流數據庫分表策略(例如Hash 取模分表策略)在切分預約表時的不足,對預約表數據的查詢性能提升了70%,達到了優化數據庫查詢性能的目的,解決了SAMP 系統整體系統性能不高的問題.由于現運行的SAMP 系統每天所處理的并發請求以及對數據的讀寫操作較仿真系統而言規模更加龐大復雜，因此將該分表策略應用于現運行的SAMP 系統時對系統性能的提升率要通過系統運行狀態做進一步分析.