基于平衡二叉樹的數(shù)控機床數(shù)據(jù)去重備份算法

秦金祥，楊 萌

(1.西安石油大學(xué)工程訓(xùn)練中心，陜西 西安710065；2.西安石油大學(xué)信息中心，陜西 西安710065)

1 引言

數(shù)控機床技術(shù)進入中國市場較早，產(chǎn)品覆蓋面較廣，但由于數(shù)控系統(tǒng)的功能強大，假如參數(shù)或數(shù)據(jù)出現(xiàn)缺失，就會對機床與數(shù)控系統(tǒng)的運行造成不利影響，例如伺服參數(shù)缺失會導(dǎo)致伺服電機不能正常運行，參數(shù)數(shù)據(jù)丟失會導(dǎo)致數(shù)控機床不能正常工作，嚴(yán)重的會導(dǎo)致人身傷害等。這樣既增加了維護人員與設(shè)計者的工作難度，也給企業(yè)的生產(chǎn)帶來了很大的不便。對此有關(guān)學(xué)者提出了幾種解決方案：其中較為典型的兩種算法即：一致性哈希算法與多維備份算法。一致性哈希算法[1]通過Swift分析數(shù)據(jù)機理與代碼，并加以改進，同時推出優(yōu)化選取策略，在明確出節(jié)點負載的情況下根據(jù)該策略對負載節(jié)點中的數(shù)據(jù)進行備份。但該方法只能根據(jù)節(jié)點的負載情況進行備份，這就導(dǎo)致大量的重復(fù)記錄數(shù)據(jù)也會被備份，使數(shù)據(jù)存儲空間利用率下降；而多維備份算法[2]依靠三種備份策略(在線備份、離線備份、異地備份)對數(shù)據(jù)進行無差別多維備份。該方法的問題與一致性哈希算法的問題相同，在完成數(shù)據(jù)備份之后并沒有刪除冗余數(shù)據(jù)，導(dǎo)致備份完成后，冗余數(shù)據(jù)占據(jù)部分數(shù)控機床系統(tǒng)運行空間的問題，久而久之甚至?xí)?dǎo)致系統(tǒng)出現(xiàn)內(nèi)存占滿的問題。

針對上述問題，提出一種基于平衡二叉樹的數(shù)控機床數(shù)據(jù)去重備份算法。

2 數(shù)控機床數(shù)據(jù)去重

2.1 基于動態(tài)權(quán)重算法的數(shù)據(jù)相似度計算

數(shù)控機床數(shù)據(jù)相似度計算方法有很多種，其中編輯距離法因具有運算簡單、效果顯著的優(yōu)勢，因此該方法最為常用。因此，本文基于編輯距離來進行動數(shù)據(jù)相似度計算。假設(shè)數(shù)控機床數(shù)據(jù)集C={r1，r2，…，rn}，ri代表數(shù)據(jù)集的第i條數(shù)據(jù)，屬性集P={p1，p2，…，pm}，pk代表數(shù)據(jù)的第k種屬性，rik代表數(shù)據(jù)ri的第k種屬性值[3]。假設(shè)隨機兩條數(shù)據(jù)ri與rj的第k種屬性值分別是rjk與rik，使D(rik，rjk)代表其編輯距離，那么數(shù)據(jù)相似度Sim(rik，rjk)就能夠通過式(1)進行描述

(1)

由于數(shù)據(jù)的屬性對于檢測重復(fù)數(shù)據(jù)的貢獻不同，因此需要對不同屬性按貢獻大小賦予其不同權(quán)值[4]即一種較為合理且成熟的方式。擬定各屬性貢獻比例是c1，c2，…，cn，所有屬性權(quán)值之和位1。通過Wk描述屬性Pk的權(quán)重，計算公式即

wk=ck/∑ci

(2)

隨機兩條數(shù)據(jù)間的相似度Sim(ri，rj)能夠通過式(3)進行計算

(3)

在進行數(shù)據(jù)相似度計算時，如果記錄的某項屬性信息丟失，那么該屬性相似度Sim(rik，rjk)=0，這使得數(shù)據(jù)相似度的總值出現(xiàn)下滑，Sim(ri，rj)小于閾值，兩條數(shù)據(jù)被視為不同。然而r1和r2仍有很大可能是相似重復(fù)數(shù)據(jù)，這種固定權(quán)重[5]運算方式因為屬性的丟失，給重復(fù)數(shù)據(jù)相似度計算帶來了較大的干擾，因此在上述基礎(chǔ)上本文提出一種動態(tài)權(quán)值的就散方法。

假設(shè)Valk描述屬性k的有效性，則存在

(4)

假如數(shù)據(jù)某一屬性出現(xiàn)無效或丟失，那么所有屬性的權(quán)重就會出現(xiàn)動態(tài)變化，此時必須縮減因?qū)傩詠G失而出現(xiàn)的干擾。假設(shè)有效性屬性Wk能夠描述成wk=(Valk*ck)/∑(Vali*ci)。因為動態(tài)權(quán)重能夠始終確保數(shù)據(jù)全部有效屬性的權(quán)值和為1，進而降低了因?qū)傩圆煌耆珜?shù)據(jù)相似度計算結(jié)果所造成的干擾。綜上，基于動態(tài)權(quán)重的數(shù)據(jù)間相似度能夠通過式(5)進行計算

(5)

2.2 數(shù)控機床數(shù)據(jù)去重

本文首先利用專家的知識來挑選關(guān)鍵屬性，根據(jù)結(jié)果對數(shù)據(jù)集進行互無交叉的劃分，使用聚類理念，利用一種開銷小的方法對數(shù)據(jù)進行粗聚類，最后在子數(shù)據(jù)集內(nèi)通過兩兩對比精確剔除相似數(shù)據(jù)，大大節(jié)省了搜索空間，縮減計算量，提升時間效率。

2.2.1 關(guān)鍵屬性劃分

因為數(shù)控機床的數(shù)據(jù)較多，一條數(shù)據(jù)通常會由若干屬性值構(gòu)成，屬性能夠表示數(shù)據(jù)的特征，但不同屬性描述數(shù)據(jù)特征時的重要性[6]是不同的，至少有一個關(guān)鍵屬性會對相似度數(shù)據(jù)去重起到?jīng)Q定性的作用。本文的關(guān)鍵屬性劃分使用了一種分組的方式，需要兼顧以下三種方面：

1)關(guān)鍵屬性值需要是可枚舉、離散型的；

2)關(guān)鍵屬性值的枚舉總量較大，這樣聚類組成的子數(shù)據(jù)集就會越小，有利于后續(xù)的重復(fù)數(shù)據(jù)檢測；

3)關(guān)鍵屬性值的平均字符總量需要最小化，這樣聚類的運算總量就會降低。

人工挑選n種存在區(qū)分度的關(guān)鍵屬性或?qū)傩缘奶囟ú糠旨癁镵eyList{key1，key2，key3，…}，通過獨一關(guān)鍵屬性進行排列，隨后依靠擬定的關(guān)鍵屬性數(shù)值，把完整數(shù)據(jù)集劃分為若干種互不相交的子數(shù)據(jù)集[7]。具體流程如下：

1)首先挑選關(guān)鍵屬性key1，將屬性取值相同的數(shù)據(jù)聚類成一類，那么能夠把大數(shù)據(jù)集劃分為N種相交的小數(shù)據(jù)集。

2)如果劃分之后的數(shù)據(jù)集依舊較為龐大，那么挑選key2，對這些數(shù)據(jù)集進行再一次劃分。

3)如機床數(shù)據(jù)集依舊不滿足計算量的需求，那么迭代進行步驟2)，直至數(shù)據(jù)集劃分至較為合理為止。

2.2.2 Canopy算法的機床數(shù)據(jù)聚類

在此階段通過一種用于處理大型數(shù)據(jù)的新型聚類方法—Canopy聚類，對上述的數(shù)據(jù)集進行粗聚類。其主要思想即首先將某一條數(shù)據(jù)作為中心，并將數(shù)據(jù)劃分為可重疊的子集[8]，隨后在Canopy子集內(nèi)精確清洗重復(fù)數(shù)據(jù)。這樣就只需要對Canopy子集內(nèi)的數(shù)據(jù)進行去重，大大縮減了傳統(tǒng)聚類方法內(nèi)對每一種數(shù)據(jù)進行對比的計算量，另外，Canopy聚類能夠允許重疊的子集消除孤立點，提升了方法的容錯性。圖1即Canopy聚類方法的示意圖。

在換分后的子數(shù)據(jù)集內(nèi)隨機選擇一種數(shù)據(jù)A，每一種數(shù)據(jù)與A之間的距離需要小于閾值T1，并利用閾值T1將數(shù)據(jù)標(biāo)記成同一Canopy子集，將與A之間的距離小于某種閾值T2的數(shù)據(jù)從數(shù)據(jù)集內(nèi)剔除，其中T1≥T2。Canopy中心B、C、D、E的組成過程與A相同，利用這些過程實現(xiàn)機床數(shù)據(jù)聚類。

圖1 Canopy示意圖

2.2.3 機床數(shù)據(jù)去重實現(xiàn)

由于機床數(shù)據(jù)源不同，數(shù)據(jù)側(cè)重不同，屬性可能存在不完整的問題，為了降低屬性丟失對去重結(jié)果所帶來的影響，本文依靠動態(tài)權(quán)重算法對機床的重復(fù)記錄數(shù)據(jù)進行剔除。對于上述檢測出的相似數(shù)據(jù)，本文提供三種方式來處理相似重復(fù)數(shù)據(jù)：①挑選其一保留，清除其它重復(fù)數(shù)據(jù)；②合并，將所有重復(fù)數(shù)據(jù)看作完整數(shù)據(jù)的一部分，將其合并成一條更完整的新數(shù)據(jù)；③通過相似度計算結(jié)果評定取舍，并能夠根據(jù)具體狀況的需求挑選不同策略。

3 基于平衡二叉樹的數(shù)據(jù)備份

3.1 數(shù)據(jù)備份

在開啟備份任務(wù)后，需要將在本地客戶端采集到的數(shù)據(jù)傳輸?shù)竭h端服務(wù)器中，在獲得數(shù)據(jù)之后，服務(wù)器會把同數(shù)據(jù)出現(xiàn)響應(yīng)的數(shù)據(jù)塊調(diào)出，并輸送到日志卷內(nèi)，并對與數(shù)據(jù)塊存在關(guān)聯(lián)的數(shù)據(jù)進行處理，獲得元數(shù)據(jù)記錄，隨后在鏡像卷的響應(yīng)位置添加數(shù)據(jù)變化信息。在備份過程中需要對產(chǎn)生的元數(shù)據(jù)記錄進行處理，其流程如下所示：

1)組建元數(shù)據(jù)記錄基礎(chǔ)架構(gòu)，其格式即：

meta-process

其中，NurnOfBlock代表本地數(shù)據(jù)快的總數(shù)，并利用所有數(shù)據(jù)塊構(gòu)成一種平衡二叉樹tree[i](0

2)非分流程，在得到客戶端發(fā)送的數(shù)據(jù)塊信息時，需要評定日志卷還有多少容量，如果出現(xiàn)滿載現(xiàn)象，就把元數(shù)據(jù)結(jié)構(gòu)歸類至元數(shù)據(jù)文件mftx內(nèi)，其中tx為構(gòu)建元數(shù)據(jù)架構(gòu)所消耗的時間，在位圖記錄歸檔即元數(shù)據(jù)位圖文件bftx歸檔后，隨后轉(zhuǎn)至步驟1)。歸檔完成后，并沒有出現(xiàn)滿載，那么進行以下處理：將數(shù)據(jù)傳輸至日志卷內(nèi)，同時生成元數(shù)據(jù)記錄，隨后處理元數(shù)據(jù)記錄，結(jié)果為cdp-metar-reecord(ti，2，4097*7，3)，代表這在ti時間點以第2種數(shù)據(jù)塊當(dāng)做原始坐標(biāo)后而出現(xiàn)的變化，存儲在日志卷的原始偏移坐標(biāo)4096*7，總共出現(xiàn)了兩處變化，解析后即ti時間點數(shù)據(jù)塊2和數(shù)據(jù)塊3出現(xiàn)了變化，其儲存在日志卷的偏移分別為4096*7和4096*8，經(jīng)過上述方法進行解析后，依靠時間點作為平衡基礎(chǔ)，分別引入到圖2元數(shù)據(jù)記錄的基礎(chǔ)結(jié)構(gòu)tree[2]和tree[3]所在的平衡二叉樹中，同時把位圖文件里的第二與第三坐標(biāo)位擬定成1，最后在鏡像卷里傳入相應(yīng)坐標(biāo)的變化數(shù)據(jù)塊，并繼續(xù)運作步驟2)，一直迭代，直至數(shù)據(jù)備份完成。

3.2 數(shù)據(jù)冗余挖掘與二次去重

本文利用數(shù)據(jù)冗余挖掘模型剔除數(shù)據(jù)備份過程中所產(chǎn)生的冗余數(shù)據(jù)。

首先設(shè)定五種表示該模型的關(guān)鍵變量：

假設(shè)St為在t時刻進行數(shù)據(jù)備份所處理的數(shù)據(jù)集，St1∩St2代表在t1時刻與t2時刻所備份的數(shù)據(jù)集之間的重復(fù)數(shù)據(jù)。St1∪St2代表在t1時刻與t2時刻所需要備份的數(shù)據(jù)。Bt代表在t時刻進行數(shù)據(jù)備份時所需要傳輸?shù)臄?shù)據(jù)。Rt代表t時刻完成數(shù)據(jù)恢復(fù)操作所需要傳輸?shù)臄?shù)據(jù)。

為了使數(shù)據(jù)冗余挖掘模型的描述更為精確，經(jīng)過連續(xù)三次的數(shù)據(jù)備份處理案例為例，詳細的描述其在數(shù)據(jù)冗余剔除之后的數(shù)據(jù)備份過程。圖2即經(jīng)過有向圖的方法表示了該數(shù)據(jù)集在時間點t1，t2和t3的三次連續(xù)數(shù)據(jù)備份與在t4時間點的數(shù)據(jù)恢復(fù)過程。

圖2(a)內(nèi)在t1，t2與t3(t1

圖2 連續(xù)的數(shù)據(jù)備份與恢復(fù)有向圖

(6)

圖2表示的即連續(xù)三次數(shù)據(jù)備份之后在t4時刻進行的一次數(shù)據(jù)恢復(fù)處理的全過程，就是把數(shù)據(jù)集在t4時刻的狀態(tài)恢復(fù)到t3時刻的狀態(tài)。t4時刻的數(shù)據(jù)備份恢復(fù)處理需要把t3時刻所備份的整個數(shù)據(jù)集進行恢復(fù)與傳輸，就是Rt4=St3。但是t4時刻數(shù)據(jù)集和t3時刻數(shù)據(jù)集內(nèi)存在很多沒有修改的數(shù)據(jù)。通過消除這些冗余數(shù)據(jù)，t4時刻所需要傳輸與恢復(fù)的數(shù)據(jù)量表示為

Rt4=St3-St3∩St4

(7)

不過，其前提需在t4時刻進行數(shù)據(jù)恢復(fù)與傳輸過程中St3∩St4的數(shù)據(jù)不能出現(xiàn)變化，反之式(7)會不成立。并且，如果t4時刻產(chǎn)生的數(shù)據(jù)災(zāi)難使得在t4時刻所備份的數(shù)據(jù)集不能被訪問，那么St3∩St4=?，Rt4等于St3。

4 實驗證明

為了證明本文所設(shè)計的基于平衡二叉樹的數(shù)控機床數(shù)據(jù)去重備份算法的實用性，需要進行一次實驗。實驗在Matlab2018的環(huán)境下進行，實驗的數(shù)控機床內(nèi)存是4G，CPU是IntelCore，實驗參數(shù)通過表1進行描述。

表1 實驗參數(shù)

在數(shù)控機床數(shù)據(jù)傳輸?shù)乃俾什粩嗵嵘臈l件下，所提算法、一致性哈希算法與多維備份算法的備份帶寬對比結(jié)果如圖3所示。

通過圖3能夠看出，隨著節(jié)點傳輸速率的逐漸提升，所提算法的數(shù)控機床數(shù)據(jù)備份帶寬明顯高于一致性哈希算法與多維備份算法，這是因為該方法先對機床數(shù)據(jù)進行去重，這就能夠剔除掉較多的重復(fù)數(shù)據(jù)記錄，降低機床數(shù)據(jù)庫中由于重復(fù)數(shù)據(jù)傳輸量的提升而引起的帶寬瓶頸效應(yīng)。

圖3 不同速率下數(shù)控機床數(shù)據(jù)備份帶寬對比

在上述基礎(chǔ)上，比較三種算法存儲不同量的數(shù)據(jù)時在機床系統(tǒng)中的空間占用率，結(jié)果如表2所示。

表2 空間占用率對比(%)

分析表2可知，與一致性哈希算法與多維備份算法相比，本文算法的空間占用率最低，可以進一步提升系統(tǒng)運行速度，實現(xiàn)系統(tǒng)性能的大幅度提升。

5 結(jié)束語

為了提高數(shù)控機床系統(tǒng)的空間利用率，提出一種基于平衡二叉樹的數(shù)控機床數(shù)據(jù)去重備份算法，通過相似度計算完成對重復(fù)記錄數(shù)據(jù)的剔除，并使用平衡二叉樹算法備份機床數(shù)據(jù)。雖然該算法在數(shù)據(jù)備份與去重上取得了較好的效果，但隨著本文研究的不斷推進，依舊發(fā)現(xiàn)了一些弊端，即本文算法的備份只能針對單一機床數(shù)據(jù)進行處理，而數(shù)據(jù)機床通常會有數(shù)臺，這就導(dǎo)致算法的可應(yīng)用性受限，因此下一步需要在本文算法的基礎(chǔ)上構(gòu)建系統(tǒng)，并將系統(tǒng)安裝至數(shù)控機床中，實現(xiàn)多臺機床數(shù)據(jù)的同步備份與去重。