業(yè)務(wù)背景

DBMind是openGauss開源的數(shù)據(jù)庫自治運維底座，在設(shè)計和實現(xiàn)上，融合了大量的工程技巧和優(yōu)化。其中，DBMind的一個功能需求是“通過從時序數(shù)據(jù)庫中獲取監(jiān)控數(shù)據(jù)，然后基于該監(jiān)控數(shù)據(jù)進行分析”，上述提到的時序數(shù)據(jù)，可以用于異常檢測、時序預測以及多指標關(guān)聯(lián)分析等。同時，上述DBMind功能總體上可以認為是一個近似使用滑動窗口進行離線分析的功能。

? ?注：時序數(shù)據(jù)至少由兩部分組成，即時間標志（可以是時間戳）和該時間標志上的值。為了方便表示，下文中所有時序數(shù)據(jù)均只表示其時間戳，省略具體值。表示形式可以是 (T1, T2, T3, T4)，也可以縮略為 (1, 2, 3, 4) 二者是等價的。用于表示時間標志為1、2、3、4以及其對應值組成的時間序列。

提出問題

問題1：重復區(qū)間數(shù)據(jù)的緩存

例如，某時刻我們需要使用時間序列 (T0, T1, T2, ..., T99) 這100個樣本點組成的數(shù)據(jù)進行分析；一段時間后，我們可能需要使用的時間序列為 (T50, T51, T52, ..., T149). 這個時間序列的長度仍然是100, 但是，這兩段時間序列之間明顯是有重疊數(shù)據(jù)的。那么，我們不禁可以思考，如何實現(xiàn)一個緩存結(jié)構(gòu)緩存從 (T50, T51, ..., T99) 這一段數(shù)據(jù)呢？

問題2：區(qū)間合并與組織

思考這樣一個問題，DBMind內(nèi)部的某個功能需要檢索時間序列取值從0到49的數(shù)據(jù)，即(T0, T1, T2, ..., T49). 另一個功能檢索了數(shù)據(jù)段從 40 到100，那么，這兩個時間段如果緩存到Buffer中，是可以進行區(qū)間合并的，也就是合并為 (T0, T1, T2, ..., T99, T100). 下次，某個功能如果檢索的時間區(qū)間落在 (0, 100) 區(qū)間，則可以直接返回數(shù)據(jù)，避免從TSDB（時序數(shù)據(jù)庫）中獲取數(shù)據(jù)的網(wǎng)絡(luò)IO.

問題3：時序數(shù)據(jù)的下采樣與上采樣

面前兩個問題，只引出了時序數(shù)據(jù)的起始和終止位置兩個要素，起始時序數(shù)據(jù)還有間隔這個要素。例如，某時間序列 A = (T0, T1, T2, ..., T49) 可以作為時間序列 B = (T0, T2, T4, ..., T48) 的父序列，即可以從時間序列 A 上抽取出時間序列 B，這個過程稱之為下采樣（或降采樣）。反之，如果從間隔更稀疏的數(shù)據(jù)則不可以恢復間隔更稠密的時序數(shù)據(jù)，否則可能會失真。根據(jù)上述描述，當我們已經(jīng)緩存了時序數(shù)據(jù) A，則可以從該時序數(shù)據(jù)中直接提取出時序序列 B，從而避免從TSDB（時序數(shù)據(jù)庫）中獲取數(shù)據(jù)的網(wǎng)絡(luò)IO.

問題4：緩存數(shù)據(jù)的淘汰機制如何設(shè)計？

我們前面只提到了可以將時序數(shù)據(jù)緩存到內(nèi)存中，從而避免從TSDB（時序數(shù)據(jù)庫）中獲取數(shù)據(jù)的網(wǎng)絡(luò)IO，那么，如果只是存儲在內(nèi)存中，不進行淘汰，數(shù)據(jù)遲早會導致系統(tǒng)OOM. 如何組織數(shù)據(jù)的淘汰機制？

問題5：如何進行數(shù)據(jù)對齊？

來自TSDB（時序數(shù)據(jù)庫）中的時序數(shù)據(jù)，可能不是干凈的，也就是可能存在間隔不一致，起止時間不一致的情況，這樣的話，不能直接把數(shù)據(jù)進行合并。例如時序數(shù)據(jù) (100, 200, 300, ..., 1000) 和 (101, 201, 301, ..., 1001) 就沒有對齊，這兩個數(shù)據(jù)涉及到合并的話，還需要有一個 shift 的過程

解決問題

解決問題1：構(gòu)建一個樹形結(jié)構(gòu)

我們拋出了上面的問題2，可以幫助我們分析我們可以使用的數(shù)據(jù)結(jié)構(gòu)。例如某個時間序列 (1,2,3,4,5) 可以是 (1,2) 以及 (4,5) 的父序列。那么，我們可以構(gòu)造某個樹結(jié)構(gòu)，來表示這層關(guān)系，例如：

當然，也可以是其他的形式，例如：

如果是多叉樹的話，則可以表示的形式就更多了。通過分析上述數(shù)據(jù)結(jié)構(gòu)，我們發(fā)現(xiàn)，父節(jié)點其實只需要存儲一個序列的起始值就可以了，具體的數(shù)據(jù)值由葉子節(jié)點來存儲，父節(jié)點只需要存儲指向葉子節(jié)點的引用即可，這樣可以避免數(shù)據(jù)冗余。那么，這顆樹就可以是：

或者是：

這樣設(shè)計的一個好處是，可以容忍缺失值，當下次需要取出完整時序序列區(qū)間的時候，只需要從TSDB（時序數(shù)據(jù)庫）中獲取缺失的數(shù)據(jù)即可，例如：

上面的例子，如果caller需要獲取 (1, 5) 間隔為 1的數(shù)據(jù)，則只需要從TSDB（時序數(shù)據(jù)庫）中獲取序號為3的值，然后放到樹種進行合并（merge），即可生成指定序列。這樣，就減少了網(wǎng)絡(luò)IO.

通過上面的例子，我們可以看到，這個數(shù)的設(shè)計上，有點類似于區(qū)間樹（segment tree）

細心的讀者可能會發(fā)現(xiàn)，這里面我們只是使用了二叉樹，那么為什么用二叉樹，不用多叉樹呢？因為，我們可以把父節(jié)點的左子樹設(shè)置為值更小的序列范圍，右子樹設(shè)置為值更大的序列范圍，這樣的話，我們就可以通過二分搜索，快速地檢索到我們需要定位的葉子節(jié)點了。同時，這個Buffer是存儲在內(nèi)存中的，如果樹的高度比較高的話，開銷也可控。因此，也不必像B-tree那樣，做成一個多叉樹。

但是，還有一個問題，我們前面提到的，如果一個樹很高的話，我們實現(xiàn)的優(yōu)化機制二分搜索的復雜度 O(logN) 就會退化為 O(N), 沒有辦法來優(yōu)化數(shù)據(jù)了。例如：

例如檢索時間編號為1的值，就會遍歷5次，即O(N)的復雜度。所以，老手藝就得用上了，也就是這個樹的旋轉(zhuǎn)和合并。這塊太過于復雜，但總體思路與B-tree, 紅黑樹的策略類似。只不過，這塊我們用不到實現(xiàn)這么復雜，我們說過，葉子節(jié)點存儲具體的值，那么我們就可以將葉節(jié)點向父節(jié)點進行合并，從而減小樹高，提高算法效率。

解決問題2：上、下采樣問題

有了上面的數(shù)據(jù)結(jié)構(gòu)，下采樣就很簡單了，我們只需要首先判斷時序序列的時間間隔是不是更大，如果比現(xiàn)有樹形結(jié)構(gòu)的間隔更大，那么直接定位到指定區(qū)間，然后使用下采樣算法進行數(shù)據(jù)點的抽取即可。下采樣的方法可以取模，也可以使用滑動窗口（計算平均值、中位數(shù)或分位數(shù)）。如果是上采樣，那么就麻煩了，例如當前緩存的樹結(jié)構(gòu)是的時間序列間隔是10，某個caller調(diào)用時，希望使用的時間序列間隔是1, 那顯然不能滿足caller的需求。需要從TSDB（時序數(shù)據(jù)庫）中獲取數(shù)據(jù)，這樣，從TSDB（時序數(shù)據(jù)庫）中獲取到的數(shù)據(jù)，比當前緩存的Tree結(jié)構(gòu)其實更好，這里面會涉及到一個權(quán)衡，即是不是可以把當前已經(jīng)緩存的這個Tree結(jié)構(gòu)淘汰，換用更密集的序列呢？這塊實現(xiàn)也很復雜，此處不贅述。

淘汰機制

我們前面從背景上提到過，DBMind的根本業(yè)務(wù)相當于一個滑動窗口，這樣的話，滑動窗口的長度其實是固定的，我們就可以在內(nèi)存中劃定一個序列的緩存長度，超過這個長度直接淘汰掉就行了。只不過，該如何淘汰呢？應該由誰來驅(qū)動呢? DBMind里面的實現(xiàn)機制是，通過實現(xiàn)一個 EvictThread 來完成的，只不過，線程在數(shù)據(jù)淘汰時候，需要加鎖，否則容易會出現(xiàn)數(shù)據(jù)不一致的情況。而且，鎖的粒度，最好也可以優(yōu)化一下。即某個區(qū)間上的共享鎖。不過，這個機制雖然更好，但是更復雜，實際實現(xiàn)上，只需要控制EvictThread的淘汰觸發(fā)事件即可。

結(jié)語

即便是一個看似很簡單的功能，如果想把它實現(xiàn)得比較優(yōu)雅，那么需要考慮的方面也是足以讓這個問題變得很復雜。對代碼實現(xiàn)邏輯的復雜性、多角度思考，是代碼實現(xiàn)過程中一個非常重要且有樂趣的一環(huán)，也是體現(xiàn)某款軟件的軟件工程能力好壞的重要因素。DBMind是立足于openGauss自治數(shù)據(jù)庫能力的載體，力爭將軟件工程能力做得更好，以便用戶獲得更優(yōu)的軟件體驗。

? 歡迎大家關(guān)注

https://gitee.com/opengauss/openGauss-DBMind?

https://github.com/opengauss-mirror/openGauss-DBMind