馬亞軍，孔令信

(重慶工商大學派斯學院，重慶 401520)

1 引言

現(xiàn)階段，網(wǎng)絡(luò)信息傳輸[1]業(yè)務得到廣泛應用和快速發(fā)展，在為人們帶來更多方便的同時，也給該技術(shù)的應用平臺和限制因素帶來了新的技術(shù)考驗。社會對網(wǎng)絡(luò)的依賴性越來越高，從工作瑣事到日常所需，網(wǎng)絡(luò)已經(jīng)無處不在，同時海量的數(shù)據(jù)也加重數(shù)據(jù)庫傳輸存儲負擔，容易產(chǎn)生緩存沖突[2]、數(shù)據(jù)失效等問題，影響網(wǎng)絡(luò)正常運行。

在數(shù)據(jù)傳輸?shù)倪^程中，當有兩個或兩個以上數(shù)據(jù)包在相同的傳輸信道上[3]，同時進行傳輸指令，那么就會產(chǎn)生數(shù)據(jù)緩存沖突包。傳統(tǒng)的解決方法是根據(jù)光緩存策略[4]，通過在一定程度上對緩存沖突包的暫時存放，從而達到緩解數(shù)據(jù)緩存沖突帶來的影響及損失。配置了光緩存核心節(jié)點的同時，還可以在一定程度上大幅度降低沖突包的數(shù)據(jù)丟失幾率。此方法雖然能夠完好的解決緩存沖突的問題[5]，但從根本上來說，光緩存策略沒有考慮到數(shù)據(jù)傳輸優(yōu)化問題，導致數(shù)據(jù)庫緩存沖突消除率較低。

張吉贊[6]等人針對帶有沖突感知總線的嵌入式多源結(jié)構(gòu)，提出了一種基于bank-column緩存劃分的訪存請求沖突延遲上限優(yōu)化方法，根據(jù)bank沖突次數(shù)與沖突延遲上限間的關(guān)系，通過優(yōu)化bank的核映射來減少bank沖突發(fā)生次數(shù)，從而減小沖突延遲上限和WCET估算值。該方法的沖突數(shù)據(jù)包丟失率較高，降低了多源數(shù)據(jù)庫緩存沖突處理精度。

因此，本文提出基于動態(tài)反饋的多源數(shù)據(jù)庫緩存沖突處理方法，該方法在傳統(tǒng)方法的基礎(chǔ)上，針對緩存沖突的數(shù)據(jù)包進行分割調(diào)整，根據(jù)反饋機制可以有效對沖突的緩存數(shù)據(jù)進行傳輸信道分配，從根本上減少沖突的情況出現(xiàn)，以達到傳輸流暢、效率高的目的。

2 多源數(shù)據(jù)庫緩存沖突分析

現(xiàn)階段，網(wǎng)絡(luò)世界日新月異，需要存儲的信息急速增長，導致多源數(shù)據(jù)庫緩存時常會出現(xiàn)沖突現(xiàn)象。根據(jù)沖突報告，數(shù)據(jù)庫內(nèi)部將會更新沖突的緩存數(shù)據(jù)，以達到數(shù)據(jù)基本的一致性。一般可以將緩存沖突分成無狀態(tài)策略和狀態(tài)策略兩種。

(1)無狀態(tài)策略：是指數(shù)據(jù)庫內(nèi)部不需要對緩存狀態(tài)進行特殊檢測，在數(shù)據(jù)緩存發(fā)生沖突的時候，會有固定的沖突報告，數(shù)據(jù)庫將根據(jù)沖突報告來解決其緩存問題。

傳統(tǒng)的無狀態(tài)策略算法具有時間戳[7]，該算法的特征是數(shù)據(jù)緩存?zhèn)鬏斴^為容易，缺陷是在數(shù)據(jù)庫繁雜的情況下，不能夠很好的將數(shù)據(jù)緩存，導致眾多數(shù)據(jù)緩存沖突失效。

(2)狀態(tài)策略：每一個數(shù)據(jù)庫終端都會有數(shù)據(jù)緩存記錄，根據(jù)緩存記錄即可得知該數(shù)據(jù)緩存的基本狀態(tài)。

傳統(tǒng)的狀態(tài)策略是異步態(tài)算法[8]，由于數(shù)據(jù)庫終端具有針對緩存的記錄功能，所以在數(shù)據(jù)緩存過程中會根據(jù)記錄，在一定程度上避免緩存沖突失效的情況出現(xiàn)。

這種方法被認為是一種在不需要特殊媒介緩存情況下，用來解決其緩存沖突的措施。當有一種數(shù)據(jù)在進行緩存輸出時，又有一個數(shù)據(jù)做出了同樣的指令工作，這樣就會使兩個數(shù)據(jù)之間指令發(fā)生沖突，進而導致兩個數(shù)據(jù)流緩沖沖突，造成失效的結(jié)果。詳細沖突原理圖如圖1所示。

圖1 沖突原理圖

3 基于動態(tài)反饋機制的沖突處理

3.1 動態(tài)反饋機制建立

動態(tài)反饋是在網(wǎng)絡(luò)服務器的基礎(chǔ)上，反饋出某時間段內(nèi)網(wǎng)絡(luò)運行負載與執(zhí)行的情況，并且根據(jù)服務器的整體狀況對請求指令進行比例調(diào)整。在此基礎(chǔ)上，針對反饋的結(jié)果進行及時處理，以防止部分服務器出現(xiàn)過于負載但仍不斷接受指令請求的狀況，進而從根本上提高網(wǎng)絡(luò)數(shù)據(jù)的緩存?zhèn)鬏斝省?/p>

動態(tài)反饋的原理圖如圖2所示。

圖2 動態(tài)反饋模型圖

根據(jù)圖2動態(tài)反饋原理圖可以得知，數(shù)據(jù)權(quán)值的調(diào)整是在f(W(i))，L(i))的基礎(chǔ)上完成的，f(W(i))，L(i))根據(jù)每個不同服務器節(jié)點的總體負載值L(i)和當前數(shù)據(jù)權(quán)值W(i)，計算出另一組數(shù)據(jù)權(quán)值W′(i)。如果另一組數(shù)據(jù)權(quán)值W′(i)與當前數(shù)據(jù)權(quán)值W(i)間的數(shù)值高于總閾值fa，那么就會出現(xiàn)另一組數(shù)據(jù)權(quán)值W′(i)替換當前數(shù)據(jù)權(quán)值W(i)的情況。假設(shè)新數(shù)據(jù)權(quán)值數(shù)值不大于設(shè)定閾值，那么就保持原來的數(shù)據(jù)權(quán)值不變；如果新數(shù)據(jù)權(quán)值數(shù)值大于設(shè)定閾值，且在不替代原來權(quán)值的情況下，就會出現(xiàn)數(shù)值差過大，導致失誤現(xiàn)象發(fā)生。

當總體負載值L(i)呈現(xiàn)出服務器較忙的狀態(tài)時，新的數(shù)據(jù)權(quán)值W′(i)與其當前數(shù)據(jù)權(quán)值W(i)相比，當前數(shù)據(jù)權(quán)值W(i)要小，這樣分配到該服務器的數(shù)據(jù)緩存指令就會相對少一些；當總體負載值L(i)呈現(xiàn)出該服務器利用率低的情況時，新的數(shù)據(jù)權(quán)值W′(i)與當前數(shù)據(jù)權(quán)值W(i)相比，當前數(shù)據(jù)權(quán)值W(i)要大，這樣就會有增加分配的請求。

動態(tài)反饋機制可以在一定程度上提高網(wǎng)絡(luò)整體傳輸效率，因為在網(wǎng)絡(luò)運行的過程中，動態(tài)反饋可以很好的反饋出某階段網(wǎng)絡(luò)負載能力，根據(jù)反饋出的情況，進行合理的傳輸與分配。

3.2 多源數(shù)據(jù)庫負載情況評估

在此基礎(chǔ)上，根據(jù)數(shù)據(jù)庫負載情況得到數(shù)據(jù)相關(guān)的概念理論：服務器的集合點S{s1，s2，…，sn}；相對應的集群節(jié)點權(quán)值集合W(si)={W(s1)，W(s2)，…，W(sn)}；負載集合L(si)={L(s1)，L(s2)，…，L(sn)}。

在對數(shù)據(jù)傳輸運行進行反饋時，其中最重要的一個參數(shù)值就是當前網(wǎng)絡(luò)整體的負載承受力，因為隨著該參數(shù)的變化，即會直接對整個服務器造成影響。所以在這種情況下，對于整體環(huán)境的負載承受力評估就很重要，同時也因為這一因素，得知了對負載參數(shù)的影響。

在這其中，綜合的負載又可以分為輸入型指標和服務型指標，服務器i在固定的時間間隔內(nèi)，接收到的連接數(shù)為Ni，那么就可以根據(jù)接收到的連接數(shù)Ni，寫出服務器的具體輸入指標L(Ni)，其表達式為：

(1)

式中，n表示服務器總數(shù)。由于服務類型不同，所以不同指標對負載的影響也不盡相同。在這種情況下，即可根據(jù)實時情況的權(quán)值來調(diào)節(jié)每個指標在負載中所擔任的地位。

針對當前的負載情況、數(shù)據(jù)權(quán)值，計算出需要改變的數(shù)據(jù)權(quán)值大小。當服務器在傳輸時，會根據(jù)指令在傳輸初始設(shè)定一個當前數(shù)據(jù)權(quán)值W(i)，假設(shè)這個數(shù)據(jù)值不等同于零，那么會出現(xiàn)每間隔一個時間周期的輸出時間T，并對節(jié)點負載數(shù)據(jù)進行檢測，根據(jù)檢測結(jié)果，評估出整體負載的情況。

3.3 沖突數(shù)據(jù)包丟失現(xiàn)象

通過上述動態(tài)反饋機制以及多源數(shù)據(jù)庫負載情況評估可以得知，當數(shù)據(jù)緩存發(fā)生沖突的時候，內(nèi)部核心的調(diào)度器會針對沖突數(shù)據(jù)包進行分割，讓沖突的數(shù)據(jù)包具有一定的緩存時間，根據(jù)調(diào)度原則[9]，計算出原來要進行緩存?zhèn)鬏數(shù)臄?shù)據(jù)包，然后選取所需要的延遲線[10]單元數(shù)量Nb，使緩存可以為沖突的數(shù)據(jù)包爭取出一個與輸出時間T最靠近的時間點T′=bNb，假設(shè)T′>T，那么即可把這個數(shù)據(jù)包的整體延遲時間變長。

根據(jù)最長延遲時間，可以將緩存數(shù)據(jù)庫看作為一個M/M/K/D的排隊模型，在該模型中D表示為在緩存過程中可以提供的最大容量，即可以容納最大數(shù)據(jù)沖突包的數(shù)量，其公式可以表示為

D=L(Ni)+L(Ni)N

(2)

在上述公式中，N表示全部延遲線(FDL)的總數(shù)量，這樣根據(jù)M/M/K/D模型，計算沖突丟失數(shù)據(jù)包PFDL，其表達式為

PFDL=ρP0/kD

(3)

其中，P0表示核心多源數(shù)據(jù)庫中沒有沖突數(shù)據(jù)包傳輸?shù)母怕?，ρ表示網(wǎng)絡(luò)負荷，可以表示為λ/μ，k表示信道數(shù)量。

3.4 BS沖突處理策略

根據(jù)上述動態(tài)反饋機制可知，在網(wǎng)絡(luò)運行的傳輸信道負載情況下，當某一條信道接收的傳輸指令超負荷于本身的負載能力時，就會間接導致數(shù)據(jù)緩存沖突的產(chǎn)生。

本文采用了基于BS[11]的分割策略，當數(shù)據(jù)在緩存的過程中發(fā)生沖突時，就可以運用分割策略對其數(shù)據(jù)進行分割，讓部分沖突的數(shù)據(jù)可以得到傳輸，從而提升傳輸效率，并且基于BS方法解決沖突數(shù)據(jù)包丟失的現(xiàn)象，具有較好的沖突處理效果。由于沖突數(shù)據(jù)包發(fā)生了沖突而被分割后，其它的數(shù)據(jù)就會被分配到另一個數(shù)據(jù)包所在的信道中，一起進行傳輸。

假設(shè)在正常k個信道之外，還有著無數(shù)個虛擬信道[12]，這就進一步可以認為分割后的沖突數(shù)據(jù)包并沒有交換到正常信道中進行傳輸，而是交換到了一條虛擬信道，進行單獨的數(shù)據(jù)傳輸。

根據(jù)上述情況，采用基于BS的分割策略對沖突數(shù)據(jù)包進行分割，則分割后的沖突數(shù)據(jù)包傳輸信道狀態(tài)信息PBS可表示為

PBS=E?L」/PFDLK

(4)

(5)

其中，P(k+1)是屬于上述M/M/∞模型中的k+j個虛擬信道全部被占用的概率值，從根本上講，P(k+j)完全服從Poisson分布，則根據(jù)分配后的沖突數(shù)據(jù)包對多源數(shù)據(jù)庫緩存沖突進行處理，其表達式為：

(6)

4 實驗分析

4.1 實驗環(huán)境

為了驗證基于動態(tài)反饋的多源數(shù)據(jù)庫緩存沖突處理方法在處理數(shù)據(jù)緩存沖突中的實際應用性能，進行實驗分析。實驗環(huán)境為CPU雙核2.53GHz操作系統(tǒng)，內(nèi)存為4.0G，64位Windows10，開發(fā)環(huán)境為MatlabR2010a。圖3為多源數(shù)據(jù)庫數(shù)據(jù)傳輸終端。

圖3 多源數(shù)據(jù)庫數(shù)據(jù)傳輸終端

在數(shù)據(jù)傳輸終端下，利用遠程服務，對多源數(shù)據(jù)庫中的數(shù)據(jù)進行遠程傳輸。

4.2 沖突數(shù)據(jù)包丟失率

在數(shù)據(jù)傳輸?shù)倪^程中，根據(jù)數(shù)據(jù)傳輸反饋出的負載情況，采用本文提出的基于動態(tài)反饋的多源數(shù)據(jù)庫緩存沖突處理方法，基于光緩存策略的多源數(shù)據(jù)庫緩存沖突處理方法和基于bank-column緩存劃分的訪存請求沖突延遲上限優(yōu)化方法，分別對沖突數(shù)據(jù)包丟失率進行監(jiān)測，監(jiān)測結(jié)果如下圖4所示。

圖4 沖突數(shù)據(jù)包丟失率對比圖

圖4是在設(shè)定了K=2的前提下獲得的實驗結(jié)果。根據(jù)圖4可知，隨著數(shù)據(jù)庫承受的負載不斷增加，沖突數(shù)據(jù)包丟失控制不穩(wěn)定。采用本文提出的基于動態(tài)反饋的多源數(shù)據(jù)庫緩存沖突處理方法的沖突數(shù)據(jù)包丟失率在50%以下，而基于光緩存策略的多源數(shù)據(jù)庫緩存沖突處理方法和基于bank-column緩存劃分的訪存請求沖突延遲上限優(yōu)化方法的沖突數(shù)據(jù)包丟失率在100%和90%以下，本文提出的基于動態(tài)反饋的多源數(shù)據(jù)庫緩存沖突處理方法的沖突數(shù)據(jù)包丟失率比基于光緩存策略的多源數(shù)據(jù)庫緩存沖突處理方法和基于bank-column緩存劃分的訪存請求沖突延遲上限優(yōu)化方法的沖突數(shù)據(jù)包丟失率低。

4.3 平均沖突消除率

為了驗證本文方法的有效性，采用本文提出的基于動態(tài)反饋的多源數(shù)據(jù)庫緩存沖突處理方法，基于光緩存策略的多源數(shù)據(jù)庫緩存沖突處理方法和基于bank-column緩存劃分的訪存請求沖突延遲上限優(yōu)化方法，對多源數(shù)據(jù)庫緩存沖突處理效果進行對比分析，對比結(jié)果如圖5所示。

圖5 平均沖突消除率對比

根據(jù)圖5可知，本文提出的基于動態(tài)反饋的多源數(shù)據(jù)庫緩存沖突處理方法的平均沖突消除率最高可達80%，最低為46%；基于光緩存策略的多源數(shù)據(jù)庫緩存沖突處理方法的平均沖突消除率最高可達58%，最低為30%；而基于bank-column緩存劃分的訪存請求沖突延遲上限優(yōu)化方法的平均沖突消除率最高只有30%。本文方法的平均沖突消除率比基于光緩存策略的多源數(shù)據(jù)庫緩存沖突處理方法和基于bank-column緩存劃分的訪存請求沖突延遲上限優(yōu)化方法的平均沖突消除率高，說明本文方法的多源數(shù)據(jù)庫緩存沖突處理效果較好，是因為本文采用了基于BS的分割策略，當數(shù)據(jù)在緩存的過程中發(fā)生沖突時，就可以運用分割策略對其數(shù)據(jù)進行分割，讓部分沖突的數(shù)據(jù)可以得到傳輸，解決沖突數(shù)據(jù)包丟失的現(xiàn)象，具有較好的沖突處理效果。

4.4 沖突處理精度

為了進一步驗證本文方法的有效性，對本文提出的基于動態(tài)反饋的多源數(shù)據(jù)庫緩存沖突處理方法，基于光緩存策略的多源數(shù)據(jù)庫緩存沖突處理方法和基于bank-column緩存劃分的訪存請求沖突延遲上限優(yōu)化方法的多源數(shù)據(jù)庫緩存沖突處理結(jié)果與實際測試的多源數(shù)據(jù)庫緩存沖突處理結(jié)果進行誤差對比，對比結(jié)果如圖6所示。

圖6 多源數(shù)據(jù)庫緩存沖突處理結(jié)果

根據(jù)圖6可知，本文提出的基于動態(tài)反饋的多源數(shù)據(jù)庫緩存沖突處理方法的多源數(shù)據(jù)庫緩存沖突處理結(jié)果與實際測試的多源數(shù)據(jù)庫緩存沖突處理結(jié)果基本一致，而基于光緩存策略的多源數(shù)據(jù)庫緩存沖突處理方法和基于bank-column緩存劃分的訪存請求沖突延遲上限優(yōu)化方法的多源數(shù)據(jù)庫緩存沖突處理結(jié)果與實際測試的多源數(shù)據(jù)庫緩存沖突處理結(jié)果的誤差較大，說明本文方法的多源數(shù)據(jù)庫緩存沖突處理精度較高，處理效果較好。

5 結(jié)論

本文提出了一種基于動態(tài)反饋的多源數(shù)據(jù)庫緩存沖突處理方法，利用基本緩存沖突原理與動態(tài)反饋機制，構(gòu)建了基于分割策略的沖突的緩存數(shù)據(jù)處理方法。

動態(tài)反饋可以對多源數(shù)據(jù)庫負載承受能力進行實施反饋，根據(jù)不同的數(shù)據(jù)傳輸信道負載情況，對其緩存信息進行合理分配，從根本上減少沖突的產(chǎn)生。

利用分割策略，在本文動態(tài)反饋的基礎(chǔ)上，通過對傳輸信道的反饋得知信道能力。當兩個數(shù)據(jù)包在同一信道發(fā)出同時傳輸?shù)闹噶顣r，那么就會產(chǎn)生數(shù)據(jù)包沖突，根據(jù)分割策略，將沖突的數(shù)據(jù)分割到其它傳輸信道中，這樣就可以有效的減少數(shù)據(jù)丟失率，提升多源數(shù)據(jù)庫緩存沖突消除率，解決沖突數(shù)據(jù)包丟失現(xiàn)象，具有較好的沖突處理效果，從根本上增加傳輸?shù)挠行?，提高傳輸效率?/p>