[發(fā)明專利]一種時序數(shù)據(jù)亂序操作處理方法和裝置

有效

• 申請?zhí)枺?/td>: 201711322396.1
• 申請日: 2017-12-12
• 公開（公告）號: CN107943519B
• 公開（公告）日: 2018-12-11
• 發(fā)明（設(shè)計）人: 王建民;黃向東;曹高飛;龍明盛;王晨
• 申請（專利權(quán)）人: 清華大學(xué)
• 主分類號: G06F9/38
• 分類號: G06F9/38
• 代理公司: 北京路浩知識產(chǎn)權(quán)代理有限公司 11002
• 代理人: 王瑩;吳歡燕

本發(fā)明提供一種時序數(shù)據(jù)亂序操作處理方法和裝置，所述方法針對三種時序數(shù)據(jù)亂序操作，INSERT(t,v)操作：在時間點t插入新值v；UPDATE(t1,t2,v)操作：將時間段[t1,t2]更新為新值v；DELETE(t)操作：將時間點t之前的數(shù)據(jù)刪除，定義了存儲這三種操作的二叉搜索樹的結(jié)構(gòu)，該二叉樹的每個節(jié)點表征一個時間區(qū)間段操作，所有節(jié)點的fix值滿足小根堆性質(zhì)，所有節(jié)點所存儲的開始時間、結(jié)束時間滿足二叉搜索樹性質(zhì)。每當(dāng)一個新的亂序操作到來時，通過判斷該操作與二叉搜索樹根節(jié)點的交叉關(guān)系來對該操作與該二叉搜索樹進行相應(yīng)的修改，最終使得該二叉搜索樹能夠存儲下該操作并能快速對數(shù)據(jù)進行查詢。

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)存儲技術(shù)領(lǐng)域，更具體地，涉及一種時序數(shù)據(jù)亂序操作處理方法和裝置。

背景技術(shù)

伴隨著云計算、互聯(lián)網(wǎng)、物聯(lián)網(wǎng)等現(xiàn)代技術(shù)的不斷發(fā)展和成熟，時間序列數(shù)據(jù)(簡稱時序數(shù)據(jù))在工業(yè)界及人們的日常生活中占據(jù)了很大的比重。時序數(shù)據(jù)是按時間戳排列形成的有序數(shù)據(jù)，比如一段時間內(nèi)的環(huán)境溫度、股票價格、機器的內(nèi)存使用率等等。其通常具有寫入速度快(寫入需求大于讀取需求)、寫入容量大、近期數(shù)據(jù)關(guān)注度高等特點。

在工業(yè)實際場景中，數(shù)據(jù)采集端的數(shù)據(jù)會傳送至機器的解碼處理程序，再被寫入數(shù)據(jù)庫。在這個過程中，若采集端使用UDP協(xié)議傳送數(shù)據(jù)，則因網(wǎng)絡(luò)延遲可能導(dǎo)致數(shù)據(jù)寫入數(shù)據(jù)庫的順序與數(shù)據(jù)產(chǎn)生的順序不一致。此外，傳感器在一段時間內(nèi)可能由于移動網(wǎng)絡(luò)信號等原因，設(shè)備數(shù)據(jù)在一段時間內(nèi)未上傳，這之后再被用戶將這部分?jǐn)?shù)據(jù)寫入到數(shù)據(jù)庫中。設(shè)備的傳感器還可能因為故障等原因產(chǎn)生了錯誤數(shù)據(jù)。最后，為了節(jié)省空間等目的，一段時間后數(shù)據(jù)還可能被刪除。當(dāng)一個時間序列數(shù)據(jù)存在上述操作時，我們稱該時間序列為亂序時間序列。

上述實際場景涉及的操作可以被定義為時序數(shù)據(jù)的亂序操作：假設(shè)當(dāng)前已存儲時序數(shù)據(jù)的最大時間戳為T，則對所有小于T的時間點的操作為亂序操作，具體可分為以下三種：

1)INSERT(t,v)操作：在時間點t(t≤T)插入新值v。

2)UPDATE(t1,t2,v)操作：將時間段[t1,t2](t1≤t2≤T)內(nèi)已存在的數(shù)據(jù)值更新為新值v。

3)DELETE(t)操作：將時間點t(t≤T)之前的數(shù)據(jù)刪除。

在多數(shù)數(shù)據(jù)存儲系統(tǒng)中尤其是NoSQL存儲系統(tǒng)中，亂序操作會明顯降低時序數(shù)據(jù)庫的寫入及查詢性能。如何高效的對亂序操作進行存取是提升亂序數(shù)據(jù)寫入、查詢性能的關(guān)鍵。

發(fā)明內(nèi)容

本發(fā)明提供一種克服上述問題或者至少部分地解決上述問題的一種時序數(shù)據(jù)亂序操作處理方法和裝置，解決了現(xiàn)有技術(shù)中對時序數(shù)據(jù)亂序操作的寫入、查詢性能低的問題。

根據(jù)本發(fā)明的一個方面，提供一種時序數(shù)據(jù)亂序操作處理方法，包括：

獲取亂序操作TP的操作類型op、起始時間戳s、結(jié)束時間戳e、亂序操作值v，同時獲取二叉樹的根節(jié)點ROOT狀態(tài)；

若判斷獲知所述根節(jié)點ROOT為空，則在所述ROOT中存儲所述op、s、e、v；

若判斷獲知所述ROOT不為空，且滿足第一預(yù)設(shè)條件，則令ROOT.v＝TP.v，其中，若ROOT.op為插入INSERT且TP.op為更新UPDATE，則令ROOT.op＝TP.op，ROOT.v＝TP.v；

所述第一預(yù)設(shè)條件為：TP.s＝ROOT.s，TP.e＝ROOT.e，且不滿足ROOT.op為刪除DELETE時，TP.op為更新UPDATE；

所述ROOT.op為所述根節(jié)點存儲的操作類型，所述ROOT.s為所述根節(jié)點存儲的起始時間戳，ROOT.e為所述根節(jié)點存儲的結(jié)束時間戳；TP.op為所述亂序操作的操作類型；所述TP.s為所述亂序操作的起始時間戳，TP.e為所述亂序操作的結(jié)束時間戳。