分散式系統中自適應統計資訊收集策略

語言: CN / TW / HK

開務資料庫(原:云溪資料庫)始終堅持在產學研合作領域的創新發展,通過建立校企聯合實驗室,針對國家和行業的重大需求,致力於攻克資料庫技術難題。

如果你對資料庫核心技術、前沿科學研究等感興趣,並希望可以紮根於資料庫領域,那誠邀大家關注“Paper Reading”文章專欄。

我們會邀請全球頂尖的資料庫專家,深入淺出地帶領大家走進學術世界,學習理論,創新實踐!

論文題目>> An Adaptive Strategy for Statistics Collecting in Distributed Database(該論文被收錄於 Front.Comput.SCI)

論文地址>> https://link.springer.com/article/10.1007/s11704-019-9107-z

01.匯入語

在資料庫系中,統計資訊對於查詢優化至關重要,錯誤的統計資訊將嚴重影響到查詢優化的質量。由於統計資訊存在缺失、過時或不充分的情況,優化器經常會選擇次優的執行計劃,但如今已有很多策略能夠保證統計資訊的正確性。

然而在分散式系統下,我們不能忽略統計資訊收集時的效率問題以及對系統的影響。從統計資訊的收集方式來看,一些系統在各節點上收集統計資訊,記為部分統計資訊。

當優化器需要使用統計資訊時,部分統計資訊需要聚合為全域性統計資訊。這種策略可以充分利用平行計算資源來提高收集效率,但是沒有考慮聚合時統計資訊正確性的損失以及對系統性能的負面影響(統計資訊收集時佔據大量系統資源,將影響系統正常運轉)。

從統計資訊收集的頻率來看,收集統計資訊的週期短,能夠更加及時地修正錯誤的統計資訊。然而這會使統計資訊收集的頻率增加,消耗大量系統資源。

綜上所述,統計資訊的收集是一個費時費力的操作。在分散式資料庫中,要想實現有效地收集統計資訊且不影響系統性能和統計資訊的正確性這一想法,具有很高的挑戰性。目前往往只能從單維度考慮統計資訊的收集,忽略了多種相關因素。

因此此篇論文提出了一種自適應收集策略(Adaptive Statistics Collecting),記為 ASC,有效地平衡了收集效率、統計資訊的正確性以及對系統性能的影響。通過本篇論文,大家可以瞭解到:

  • 如何將統計資訊收集流程形式化,並分析與統計資訊收集有關的因素間的相互關係;
  • 自適應元件為統計資訊收集提供魯棒性的策略,平衡與統計資訊收集有關的因素關係;
  • 分析傳統演算法的問題並闡述本文提出的演算法如何解決這些問題;
  • 在分散式環境下,從收集效率,統計資訊的正確性、對系統性能的影響這三個方面評估本文演算法。

02.預備知識

一、收集流程

統計資訊的收集流程往往能劃分為 3 個階段:When、Where 和 How。

When:統計資訊的收集是一個被動的操作,意味著它的執行需要被某些事件觸發,通常是增量資料達到某個閾值; Where:統計資訊的收集與利用是分開的,意味著我們需要選擇合適的位置去儲存它們; How:統計資訊收集的執行方式分為 3 種,如下表所示:

將以上三個階段結合,可以得到傳統的統計資訊收集流程,如下圖所示:

二、與統計資訊收集相關的因素及相互關係

和統計資訊收集相關的因素,如下表所示:

根據一些啟發式規則,給出各因素之間的關係,如下表所示:

注:系統性能的高低可以理解為系統是否能夠正常維持原有的功能。

三、目標函式

對於 Collecting Efficiency(E)、Correctness of Statistics(C)、Negative Effect To System Performance(NEP)3 個因素,函式最終目標是在保證對系統性能 P 影響較低的條件下,儘可能提高統計資訊的收集效率 E 和統計資訊的準確性 C。

03.自適應統計資訊收集

一、ASC 流程

自適應統計資訊收集 ASC 是用三個自適應元件 Adaptive Triggering、 Adaptive Tcheduling、Adaptive Executing 實現目標函式。ASC 的流程圖如下:

對流程圖的解讀如下:

  • 基於事件形成 ESI(可以儲存必要資訊的一個架構),在不同階段之間傳遞,並且動態擴充套件,滿足不同的需求;
  • Adaptive Triggering 元件根據 ESI 決定觸發時間(是否觸發統計資訊的收集),並且產生收集任務,儲存在 ESI 中,傳遞給 Adaptive Scheduling 元件;
  • Adaptive Scheduling 元件為收集任務決定合適的執行模型、執行位置與儲存位置;
  • Adaptive Scheduling 元件可以判斷當前系統狀態是否可以執行收集任務,如果可以,利用對應的執行模型執行收集任務,並將結果儲存在相應位置。

二、ESI

所有的自適應決策需要基於一些資訊,在不同階段這些資訊不同。ESI 儲存這些資訊並根據不同階段動態擴充套件,ESI 的表示式和變數的具體含義如下:

三、Adaptive Triggering

何時收集統計資訊會影響統計資訊的準確性和系統狀態,Adaptive Triggering 元件綜合考慮豐富的資訊,根據 3 個閾值判斷是否觸發收集任務:

WT 為增量資料閾值,與 PostgreSQL 的閾值設定相似,其中 b 代表基礎閾值,預設為 50;X 是元組數量;Θ 為係數因子,預設為 0.1,代表增量的百分比。

HT 代表一張表的重要性,是查詢這張表的頻數,用英文表達是 Query Heat Threshold,σ 的表示式如下,表示 N 張表的平均 Query Heat。

ST 代表著狀態閾值,State Threshold表示比平均可用記憶體數高的節點數量,即健康節點數,K 表示總節點數。

基於以上 3 個閾值,演算法 1 如下:

對演算法的解讀如下:

當系統處於健康狀態時,意味著健康節點數的 25% 大於收集任務數(Line 3),然後我們可以假設系統能夠處理這些收集任務同時保持對系統性能較低的負面影響,因此可以觸發所有的收集任務(Line 4)。

如果不滿足 1 中的條件,對於每個任務,如果它增量元組的數量和重要性(Query Heat)都大於閾值(Line 8),則可以觸發這個任務。

如果 1 和 2 都不滿足,我們可以放寬約束,只判斷是否滿足其中一個閾值條件。但是閾值本身會提高(Line 10),這一判斷能夠確保較為重要的任務或增量資料較多的任務可以被觸發。

最後,如果存在需要被觸發的任務,保留它們並觸發(Line 14-16)。

注:部分常量值,例如演算法 1 Line 10 的 1.5 和 2 通過實驗分析得到。

四、Adaptive Scheduling

Adaptive Scheduling 為每一個收集任務分配合適的執行模型,並確定執行位置和儲存位置。

回顧在前面 How 中提到過的 3 種模型:PCM,PmCM,GCM,存在以下特點:

傳統方法一般只能指定一個模型,缺乏通用性。為解決這個問題,應用一個函式,記為 DM,為每個任務基於它所佔據的節點數決定它的執行模型。DM 函式如下:

其中 Θ 是一個閾值,其表示式為 ε*log2(K/2),其中 K 為分散式系統的總節點數,ε 為係數因子,預設為 2。這樣的設定基於啟發式的理由:大型任務更需要效率,小型任務更需要準確性。

因為 PmCM 與 PCM 比較相似,但 PmCM 的效率低於 PCM,所以作者只考慮從 PCM 和 GCM 兩種執行模型中選擇。

對於 PCM,執行位置和儲存位置都為要收集的物件(表)所在位置;對於 GCM ,執行位置只有一個:包含最多要收集表內容的節點,這使得網路傳輸最小;儲存位置由使用者定義。具體演算法如下:

五、Adaptive Executing

對於一個收集任務,它的執行位置的狀態可能並不允許直接處理這些任務,Adaptive Executing 決定當前收集任務何時執行。具體演算法如下:

演算法 3 中的輸入是收集任務以及它的儲存位置,當檢測到當前節點的狀態(F 代表記憶體利用率)低於某個閾值時(預設為 55%,由經驗所得),才可以執行此任務,執行結果將儲存到對應的儲存位置中(Line 2-9)。

六、演算法總結

傳統的統計資訊收集存在一些共性問題:對於收集統計資訊的時間(觸發條件)判斷簡單,一般只看增量資料,沒有綜合考慮多種因素;執行和儲存模型不通用,不能適應各種情景;收集任務的執行不能自適應地控制。

ASC 用三個元件解決以上問題:Adaptive Triggering 利用更加豐富的資訊判斷何時觸發;Adaptive Scheduling 為每個任務選擇最合適的執行模型和執行位置;Adaptive Executing 自適應地控制任務的執行時間。

下圖為 ASC 的一個例子,比較直觀易懂:

04.實驗評估

本文作者利用 OceanBase 與 TPC-H 資料集,分別對收集效率,收集準確性和對系統性能影響三個方面進行演算法評估,同時和傳統方法進行了對比。

在後面的實驗結果中,本文提出的演算法記為 CS-AP。傳統方法分別記為 CS-PP、CS-PG、CS-GG。其含義和演算法如下:

  • CS-PP:partial collecting and partial storing algorithm
  • CS-PG:partial collecting and global storing algorithm
  • CS-GG:global collecting and global storing algorithm

注:在傳統演算法中,用 WT 表示觸發統計資訊收集的閾值。

一、收集效率

統計不同節點數、不同資料量下的執行時間。

二、收集正確性

本實驗的目的是證明用 ASC,能夠更加合理的利用系統資源,及時為更加重要的任務和增量資料較多的任務觸發統計資訊的收集。

三、對系統性能的影響

其中,MRU 為 Memory Utilization Rate,即記憶體利用率;Q 為只執行查詢但不執行收集任務時的系統;O 為初始狀態的 MUR。