一種資料庫集群系統的負載均衡實現方法和裝置的製作方法
2023-05-30 20:39:31 1
專利名稱：一種資料庫集群系統的負載均衡實現方法和裝置的製作方法
技術領域：
本發明涉及一種資料庫集群系統的負載均衡實現方法和裝置，屬於信息技術領域。
背景技術：
資料庫集群系統是指將一組資料庫伺服器以集群的方式組合起來，使用統一的接口向用戶提供服務。資料庫集群系統利用保存在多個資料庫伺服器上的數據副本獲得更高的可用性；並利用多個資料庫伺服器提供單一資料庫系統所無法提供的更強大的數據管理能力和更高的查詢響應效率。資料庫集群系統中多個資料庫伺服器之間的一致性可以通過基於認證的資料庫複製協議來實現，其過程如下各個資料庫伺服器是等價的，客戶端發來的事務請求(如查詢、更新數據等操作)先由一個資料庫伺服器執行，如果該事務是只讀事務，則由該資料庫伺服器直接提交並應答即可；如果該事務涉及到數據的更新，則廣播該事務的改寫集通知其他所有的資料庫伺服器。當其他的資料庫伺服器接收到廣播的事務改寫集時，會對該事務進行一個認證如果該資料庫伺服器上有已經提交的並且與更新事務相衝突的事務，則該更新事務就會被中止；如果沒有與該更新事務相衝突的事務，該事務會在所有資料庫伺服器上以相同的順序提交。也就是說負載均衡器分配給每個資料庫伺服器的事務是不一樣的，資料庫伺服器之間的一致性由基於認證的複製協議保證。在這種場景下，如何選取效率最高的資料庫伺服器執行客戶端的事務請求，是決定整個集群系統應答效率的關鍵技術。由於系統中的不同事務可能需要共同訪問一些常見的數據項目，如果其中至少有一個事務存在寫操作，則會導致這些事務共同訪問數據時衝突，即這些事務之間存在有衝突關係。當兩個存在有衝突關係的事務在不同的資料庫伺服器中執行時，其中一個事務就有可能被中止執行，如果事務之間的衝突率較高，則會導致系統中止率的提高和並發處理能力的降低。相反，如果將存在有衝突關係的事務交由同一個資料庫伺服器執行，這時資料庫伺服器本地的並發控制機制能有效解決這些衝突問題，從而降低事務執行時的中止率。 因此，我們希望能將具有衝突關係的事務儘可能的集中在最少的資料庫伺服器上執行。但是，將具有衝突關係的事務集中分配給少數的資料庫伺服器，有可能會造成負載不均衡的問題少數的資料庫伺服器發生數據過載；另一些資料庫伺服器處於閒置狀態。由於解決事務衝突會產生相應的鎖衝突，少數的資料庫伺服器會因為過多的鎖衝突而形成數據過載，當數據過載發生時，越來越多的事務被阻塞在執行進程中，事務的響應時間大大增加，同時過多的中止還會導致資源的大量浪費。目前，普遍使用的資料庫集群系統負載均衡方法包括有隨機選擇法、輪詢法、加權輪詢法等，然而這些方法均沒有考慮到事務之間的衝突關係。JC ((Conflict-aware load-balancing techniques for database r印lication》(幹Ij於 2008ACMsymposium on Applied computing. March 16—20 2008)提出了一種用於資料庫集群系統的衝突感知負載均衡技術(簡稱MPF)。該MPF方案通過參數f的調整，從而實現了事務衝突數的最小化和並行數的最大化目標，但由於參數f的選擇很大程度上取決於以下因素互相衝突的交易數、複雜度和系統負載，從而導致最終結果存在有一定的不確定性和複雜性，同時在每個資料庫伺服器上仍有可能會發生數據過載現象。因此，如何將具有衝突關係的事務儘可能的分配至最少的資料庫伺服器上，同時還能使各個資料庫伺服器達到負載均衡，就成為業內科技人員關注的一個新課題。
發明內容
有鑑於此，本發明的目的是提供一種資料庫集群系統的負載均衡實現方法和裝置，能將具有衝突關係的事務儘可能的分配至最少的資料庫伺服器上，同時還使各個資料庫伺服器達到負載均衡。為了達到上述目的，本發明提供了一種資料庫集群系統的負載均衡實現方法，所述方法包括有步驟一、負載均衡器將各個資料庫伺服器的正在執行的事務和客戶端請求的並發事務之間的衝突關係建模為具有權重值的無向圖，其中客戶端請求的並發事務簡稱為請求事務該無向圖中，節點集是資料庫伺服器節點和請求事務節點的集合，其中資料庫伺服器節點代表該資料庫伺服器上的所有正在執行的事務，請求事務節點代表客戶端請求的並發事務；邊集是資料庫伺服器上正在執行的事務和請求事務之間的衝突關係集合，其中所述事務之間的衝突關係是指多個事務共同訪問同一數據項目、並且其中至少有一個事務存在寫操作；所述節點的權重值取決於請求事務的權重值或資料庫伺服器上的所有正在執行事務的權重值之和，其中事務的權重值取決於事務的複雜度；所述邊的權重值取決於存在衝突關係的兩個節點所代表的事務共同訪問的數據項總數；步驟二、採用圖的分割法，將所述無向圖劃分成k個分區，k是所有的資料庫伺服器節點總數，其中每個資料庫伺服器節點都唯一的歸屬於不同的分區中，並按照跨越不同分區的邊的權重值總和最小，同時每個分區內的資料庫伺服器節點權重值達到均衡的分區原則，將所有請求事務節點劃分到相應的分區中；步驟三、負載均衡器根據步驟二的分區結果，逐一將請求事務分配給同一分區內的資料庫伺服器執行、處理。為了達到上述目的，本發明還提供了一種資料庫集群系統的負載均衡裝置，包括有負載均衡器，連接客戶端和資料庫伺服器，用於接收客戶端請求的並發事務，其中客戶端請求的並發事務簡稱為請求事務，並將各個資料庫伺服器的正在執行的事務和請求事務之間的衝突關係建模為具有權重值的無向圖，然後採用圖的分割法，將所述無向圖劃分成k個分區，k是所有的資料庫伺服器節點總數，其中每個資料庫伺服器節點都唯一的歸屬於不同的分區中，並按照跨越不同分區的邊的權重值總和最小，同時每個分區內的資料庫伺服器節點權重值達到均衡的分區原則，將所有請求事務節點劃分到相應的分區中，最後根據分區結果，將所述請求事務分配給同一分區內的資料庫伺服器執行。與現有技術相比，本發明的有益效果是本發明同時考慮了事務之間的衝突關係和資料庫集群系統的負載均衡問題，首先將資料庫伺服器和客戶端的請求事務之間的衝突關係建模為具有權重值的無向圖，再採用圖的分割法，按照跨越不同分區的邊的權重值總和最小，同時每個分區內的資料庫伺服器節點權重值達到均衡的分區原則，將所有請求事務節點劃分到系統中各個資料庫伺服器節點所在的分區中，從而將具有衝突關係的事務儘可能的分配至最少的資料庫伺服器上，有效降低中止率，同時還使各個資料庫伺服器達到負載均衡；由於資料庫伺服器在處理互相衝突的事務時會發生鎖衝突，因此對每個資料庫伺服器中的事務執行和完成狀態進行跟蹤，如果監測到資料庫伺服器中的衝突比例值 Thrashing大於衝突臨界值CR時，則暫緩該資料庫伺服器中下一個請求事務的執行，從而有效避免了因為過多的鎖衝突而形成數據過載現象。
圖1是本發明一種資料庫集群系統的負載均衡實現方法流程圖。圖2是將資料庫伺服器的正在執行的事務和請求事務之間的衝突關係建模為無向圖的一個實施例的示意圖。圖3是圖1步驟二的具體操作流程圖。圖4是針對圖2所示的無向圖實施例，採用圖的分割法將所有請求事務節點進行分區後的結果示意圖。圖5是當負載均衡器向所述資料庫伺服器分配一個請求事務時的具體操作流程圖。圖6本發明一種資料庫集群系統的組成結構示意圖。圖7是採用Random、MPF、GBCA時的中止率隨客戶端連接數的變化曲線圖。圖8是分別採用Random、MPF、GBCA時，資料庫伺服器負載分布隨客戶端連接數的變化曲線圖。圖9是採用Random、MPF、GBCA時的吞吐量隨客戶端連接數的變化曲線圖。圖10是採用Random、MPF、GBCA時的平均響應時間隨客戶端連接數的變化曲線圖。
具體實施例方式為使本發明的目的、技術方案和優點更加清楚，下面結合附圖好實施例對本發明作進一步的詳細描述。參見圖1，客戶端向負載均衡器發送並發事務請求，當負載均衡器同時接收到若干個並發事務請求後，本發明一種資料庫集群系統的負載均衡實現方法包括有步驟一、負載均衡器將各個資料庫伺服器的正在執行的事務和客戶端請求的並發事務(簡稱請求事務)之間的衝突關係建模為具有權重值的無向圖該無向圖中，節點集是資料庫伺服器節點和請求事務節點的集合，其中資料庫伺服器節點代表該資料庫伺服器上的所有正在執行的事務，請求事務節點代表客戶端請求的並發事務；邊集是資料庫伺服器上正在執行的事務和請求事務之間的衝突關係集合，其中所述事務之間的衝突關係是指多個事務共同訪問同一數據項目、並且其中至少有一個事務存在寫操作，當資料庫伺服器上正在執行的事務和請求事務、或者不同的請求事務之間存在有衝突關係時，對應的資料庫伺服器節點和請求事務節點、或者不同的請求事務節點之間存在有一條連接上述兩個節點的邊；所述節點的權重值取決於請求事務的權重值或資料庫伺服器上的所有正在執行事務的權重值之和，其中事務的權重值取決於事務的複雜度，例如事務執行時間、佔用系統資源等；所述邊的權重值取決於存在衝突關係的兩個節點所代表的事務共同訪問的數據項總數，當資料庫伺服器節點和請求事務節點之間存在有一條邊時，所述邊的權重值是該資料庫伺服器上所有正在執行的事務和所述請求事務共同訪問的數據項總數，當不同的請求事務節點之間存在有一條邊時，所述邊的權重值是該兩個請求事務所共同訪問的數據項總數。如圖2所示，是本發明將資料庫伺服器的正在執行的事務和請求事務之間的衝突關係建模為無向圖的一個實施例的示意圖。該無向圖中，包含有3個資料庫伺服器節點(如
R1、R2, R3)和8個請求事務節點(如T1, T2.....T8)，其中資料庫伺服器節點R1上正在執行
事務T1和T3，資料庫伺服器節點民上正在執行事務T2，客戶端請求的並發事務T4、T5. . .、Τ8 同時到達負載均衡器，並由負載均衡器按Τ4、Τ5. . .、Τ8的順序依次調度資料庫伺服器執行該請求事務。設定所有事務的複雜度相等，即所有事務的權重值為1，且衝突事務共同訪問的數據項為1。資料庫伺服器節點R1上正在執行事務T1和T3,因此R1的節點權重值為事務 T1和T3的權重值之和，即R1的節點權重值為2，同樣，資料庫伺服器節點民上正在執行事務 T2,則資料庫伺服器節點民的節點權重值為1，資料庫伺服器節點&上沒有正在執行的事務，則資料庫伺服器節點&的節點權重值為0。由於請求事務節點T4和資料庫伺服器節點 R3上的正在執行事務存在有衝突關係，且共同訪問的數據項總數為1，所以連接請求事務節點T4和資料庫伺服器節點民的邊的權重值為1，同樣，請求事務節點T4和T6存在有衝突關係，且共同訪問的數據項總數為1，所以連接請求事務節點T4和T6的邊的權重值為1。步驟二、採用圖的分割法，將所述無向圖劃分成k個分區，k是所有的資料庫伺服器節點總數，其中每個資料庫伺服器節點都唯一的歸屬於不同的分區中，並按照跨越不同分區的邊的權重值總和最小，同時每個分區內的資料庫伺服器節點權重值達到均衡的分區原則，將所有請求事務節點劃分到相應的分區中。步驟三、負載均衡器根據步驟二的分區結果，逐一將請求事務分配給同一分區內的資料庫伺服器執行、處理。如圖3所示，步驟二進一步包括有步驟21、計算節點總權重Wtotal和資料庫伺服器負載均衡權重1_ 一其中，Wtotal是
無向圖中所有節點的權重值之和，
權利要求
1.一種資料庫集群系統的負載均衡實現方法，其特徵在於，所述方法包括有 步驟一、負載均衡器將各個資料庫伺服器的正在執行的事務和客戶端請求的並發事務之間的衝突關係建模為具有權重值的無向圖，其中客戶端請求的並發事務簡稱為請求事務該無向圖中，節點集是資料庫伺服器節點和請求事務節點的集合，其中資料庫伺服器節點代表該資料庫伺服器上的所有正在執行的事務，請求事務節點代表客戶端請求的並發事務；邊集是資料庫伺服器上正在執行的事務和請求事務之間的衝突關係集合，其中所述事務之間的衝突關係是指多個事務共同訪問同一數據項目、並且其中至少有一個事務存在寫操作；所述節點的權重值取決於請求事務的權重值或資料庫伺服器上的所有正在執行事務的權重值之和，其中事務的權重值取決於事務的複雜度；所述邊的權重值取決於存在衝突關係的兩個節點所代表的事務共同訪問的數據項總數；步驟二、採用圖的分割法，將所述無向圖劃分成k個分區，k是所有的資料庫伺服器節點總數，其中每個資料庫伺服器節點都唯一的歸屬於不同的分區中，並按照跨越不同分區的邊的權重值總和最小，同時每個分區內的資料庫伺服器節點權重值達到均衡的分區原則，將所有請求事務節點劃分到相應的分區中；步驟三、負載均衡器根據步驟二的分區結果，逐一將請求事務分配給同一分區內的資料庫伺服器執行、處理。
2.根據權利要求1所述的方法，其特徵在於，所述步驟二進一步包括有步驟21、計算節點總權重Wt。tal和資料庫伺服器負載均衡權重WavCTage，其中，Wtotal是無"w 「向圖中所有節點的權重值之和，Waverage= f ,「卩表示對1上取整；步驟22、設置可劃分的分區集合S (t)和已劃分的分區集合P(t)，並對S(t)、P(t)分別初始化S(t) = (S1^S2.....，其中S1A2.....&表示K個分區，初始化時無向圖中的每個資料庫伺服器節點都被劃分到S(t)的不同分區中，即每個資料庫伺服器節點在分區後都唯一的歸屬於S (t)中的一個分區；P (t)為空集；步驟23、逐一判斷S (t)中的每一個分區所包含的資料庫伺服器節點的權重值是否大於WavCTa一如果資料庫伺服器節點的權重值大於Waraa一則將所述分區從S (t)中移至P (t) 中；步驟M、判斷無向圖中是否還有未被劃分到分區的請求事務節點？如果是，則繼續步驟25;如果否，則本流程結束；步驟25、提取一個未被劃分到分區的請求事務節點，判斷S(t)所包含的分區個數是否大於0 ？如果是，則繼續步驟沈；如果否，則繼續步驟27 ；步驟沈、判斷無向圖中，和所述請求事務節點相連的其他節點是否存在有歸屬於S(t) 中的分區的節點？如果是，則從S(t)的分區中，找到和所述請求事務節點相連的邊的權重值總和最大的一個S(t)的分區，將所述請求事務節點劃分到所述分區中，並將所述分區中的資料庫伺服器節點的權重值更新為原權重值和所述請求事務節點的權重值之和，轉向步驟23 ；如果否，則比較S(t)中所有分區的資料庫伺服器節點的權重值，將所述請求事務節點劃分到資料庫伺服器節點的權重值最小的分區中，並將所述分區中的資料庫伺服器節點的權重值更新為原權重值和所述請求事務節點的權重值之和，轉向步驟23 ；步驟27、比較P(t)中所有分區的資料庫伺服器節點的權重值，將所述請求事務節點劃分到資料庫伺服器節點的權重值最小的分區中，並將所述分區中的資料庫伺服器節點的權重值更新為原權重值和所述請求事務節點的權重值之和，轉向步驟對。
3.根據權利要求1所述的方法，其特徵在於，負載均衡器為每個資料庫伺服器維護一個事務請求隊列，同時還對每個資料庫伺服器的事務執行和完成狀態進行跟蹤，如果監測到資料庫伺服器中的衝突比例值Thrashing大於衝突臨界值CR時，則暫緩該資料庫伺服器中下一個請求事務的執行，所述CR是一個實數。
4.根據權利要求3所述的方法，其特徵在於，CR的優選值可以是1.3。
5.根據權利要求3所述的方法，其特徵在於，負載均衡器對資料庫伺服器中的衝突比例值Thrashing進行監測，進一步包括有負載均衡器分別從資料庫伺服器的鎖表中讀取當前所有事務所持有鎖的總數Sall和非阻塞事務所持有鎖的總數Snz ；負載均衡器計算衝突比例值
6.根據權利要求3所述的方法，其特徵在於，當負載均衡器向所述資料庫伺服器分配一個請求事務，還包括有步驟Α、負載均衡器判斷所述衝突比例值Thrashing是否小於衝突臨界值CR 如果是， 則繼續步驟B ；如果否，則負載均衡器將該請求事務放入事務請求隊列的隊尾等待；步驟B、負載均衡器判斷為所述資料庫伺服器維護的事務請求隊列是否為空，如果是， 則直接調度該請求事務給資料庫伺服器執行，如果否，則將該請求事務放入事務請求隊列的隊尾，同時調度事務請求隊列的處於隊首的請求事務給資料庫伺服器執行。
7.根據權利要求3所述的方法，其特徵在於，當負載均衡器監測到資料庫伺服器執行完一個請求事務時，還包括有負載均衡器判斷所述衝突比例值Thrashing是否小於衝突臨界值CR ？如果是，則當所述資料庫伺服器的事務請求隊列不為空時，調度事務請求隊列的處於隊首的請求事務給資料庫伺服器執行；如果否，則負載均衡器不調度事務請求隊列中的請求事務。
8.一種資料庫集群系統的負載均衡裝置，其特徵在於，包括有負載均衡器，連接客戶端和資料庫伺服器，用於接收客戶端請求的並發事務，其中客戶端請求的並發事務簡稱為請求事務，並將各個資料庫伺服器的正在執行的事務和請求事務之間的衝突關係建模為具有權重值的無向圖，然後採用圖的分割法，將所述無向圖劃分成k 個分區，k是所有的資料庫伺服器節點總數，其中每個資料庫伺服器節點都唯一的歸屬於不同的分區中，並按照跨越不同分區的邊的權重值總和最小，同時每個分區內的資料庫伺服器節點權重值達到均衡的分區原則，將所有請求事務節點劃分到相應的分區中，最後根據分區結果，將所述請求事務分配給同一分區內的資料庫伺服器執行。
9.根據權利要求8所述的負載均衡裝置，其特徵在於，所述負載均衡器進一步包括有k 個事務請求隊列維護裝置，其中事務請求隊列維護裝置，用於對其中一個資料庫伺服器維護一個事務請求隊列，並同時對所述資料庫伺服器中的事務執行過程進行跟蹤，如果監測到資料庫伺服器中的衝突比例值Thrashing大於衝突臨界值CR時，則等待直至Hirashing小於CR時再繼續該資料庫伺服器中下一個請求事務的執行，其中資料庫伺服器中的衝突比例值Thrashing:Thrashing=^- , Sall> Snz分別是從資料庫伺服器的鎖表中讀取的當前所有事務所持有鎖的總數和非阻塞事務所持有鎖的總數，所述CR是一個實數。
10.根據權利要求9所述的負載均衡裝置，其特徵在於，CR的優選值可以是1. 3。
全文摘要
一種資料庫集群系統的負載均衡實現方法和裝置，所述方法包括有負載均衡器將各個資料庫伺服器的正在執行的事務和客戶端請求的並發事務之間的衝突關係建模為具有權重值的無向圖；採用圖的分割法，將所述無向圖劃分成k個分區，k是所有的資料庫伺服器節點總數，並按照跨越不同分區的邊的權重值總和最小，同時每個分區內的資料庫伺服器節點權重值達到均衡的分區原則，將所有請求事務節點劃分到相應的分區中；根據分區結果，逐一將請求事務分配給同一分區內的資料庫伺服器執行、處理。本發明屬於信息技術領域，能將具有衝突關係的事務儘可能的分配至最少的資料庫伺服器上，同時還使各個資料庫伺服器達到負載均衡。
文檔編號G06F17/30GK102299959SQ20111024123
公開日2011年12月28日 申請日期2011年8月22日 優先權日2011年8月22日
發明者廖建新, 張樂劍, 張磊, 徐童, 朱曉民, 李煒, 樊利民, 沈奇威, 王晶, 王純, 程莉, 鄭安根 申請人:北京郵電大學