基于動(dòng)態(tài)反饋的多源數(shù)據(jù)庫(kù)緩存沖突處理仿真

馬亞軍，孔令信

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

圖1 沖突原理圖

3 基于動(dòng)態(tài)反饋機(jī)制的沖突處理

3.1 動(dòng)態(tài)反饋機(jī)制建立

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

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

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

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

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

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

3.2 多源數(shù)據(jù)庫(kù)負(fù)載情況評(píng)估

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

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

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

(1)

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

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

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

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

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

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

(2)

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

PFDL=ρP0/kD

(3)

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

3.4 BS沖突處理策略

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

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

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

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

PBS=E?L」/PFDLK

(4)

(5)

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

(6)

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)環(huán)境

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

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

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

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

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

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

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

4.3 平均沖突消除率

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

圖5 平均沖突消除率對(duì)比

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

4.4 沖突處理精度

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

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

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

5 結(jié)論

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

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

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