孫亮

（廣東省深圳市創(chuàng)夢天地有限公司 廣東省深圳市 518000）

1 引言

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，互聯(lián)網(wǎng)中越來越多的網(wǎng)站出現(xiàn)在網(wǎng)絡世界里。在瀏覽器中的緩存設計可以極大提升用戶體驗，更快的網(wǎng)站響應速度。但是瀏覽器中的緩存大小是有限的，怎么在有限的緩存空間中存入足夠大的URL，提升用戶體驗是我們需要思考的問題。

瀏覽器緩存是將一個曾經(jīng)請求過的網(wǎng)頁文件（如HTML文件，圖片數(shù)據(jù)，JavaScript 文件，數(shù)據(jù)文件）拷貝成一個副本數(shù)據(jù)放到瀏覽器中。進而將WEB請求進來的數(shù)據(jù)內(nèi)容保存為輸入內(nèi)容到緩存中，可能是內(nèi)存緩存或者磁盤緩存數(shù)據(jù)。當瀏覽器再次請求數(shù)據(jù)的時候,如果是請求相同的URL數(shù)據(jù),瀏覽器就會通過自動緩存策略，根據(jù)緩存規(guī)則判斷、識別是直接通過瀏覽器的副本響應。如果不存在緩存中需要從源服務器再一次發(fā)出WEB資源請求以獲取網(wǎng)絡資源數(shù)據(jù)。隨著URL的增長,緩存所占據(jù)的內(nèi)存會越來越大,而響應的速率也會越來越緩慢。因此講到瀏覽器緩存,我們必須首先介紹瀏覽器中緩存的種類和其工作的原理。而了解瀏覽器的緩存原理,也就是了解在什么地方對緩存做優(yōu)化可以最大限度的提高緩存的效能,從而提高網(wǎng)頁的反應速度和工作效果,進而改善使用者的體驗。

（1）Memory Cache。內(nèi)存中的緩存。按照操作系統(tǒng)原理知識可以知道。操作系統(tǒng)默認優(yōu)先從讀內(nèi)存讀取數(shù)據(jù)，如內(nèi)存緩存沒有緩存記錄，再讀硬盤讀取數(shù)據(jù)。Memory Cache也是所有緩存中速度最快也是占用存儲空間最小的，同時對存儲效率要求也是最高的緩存類型，大部分的瀏覽器的資源請求都會被瀏覽器根據(jù)緩存規(guī)則緩存到 Memory Cache 中，用來高效的瀏覽WEB資源。從網(wǎng)絡中請求越多的資源，因為瀏覽器的訪問請求的數(shù)量越大，緩存在內(nèi)存空間占用也就有越來越高，正因為操作系統(tǒng)的是內(nèi)存有限的原因，瀏覽器占用的內(nèi)存不能無限擴大，否則會被系統(tǒng)提示內(nèi)存不足，需要收到殺掉進程，以減少內(nèi)存的使用，Memory Cache 一般情況下只是個“短期有效存儲”，通常是有一定的有效期限，這樣提升緩存的效率。一般使用瀏覽器的情況下，瀏覽器的頁簽關閉后，此次瀏覽的 Memory Cache 會自動釋放 (為了給其他 Web圖頁面騰出更多的內(nèi)存空)。在內(nèi)存使用量大的情況下 (若果一個頁面的Memory Cache就占用大量的Memory)，那可能在 瀏覽器頁簽沒關閉之前，排在前面的瀏覽器緩存就會失效。所以在Memory Cache設置有效期很有必要，這樣既能提升用戶體驗和瀏覽器的訪問速度也能節(jié)省不必要的內(nèi)存空間的浪費。

（2）Disk Cache也叫 HTTP cache，顧名思義是存儲在操作系統(tǒng)硬盤上的緩存，通常是也是存在于操作系的文件系統(tǒng)中的，因此它是長久性存儲在操作系統(tǒng)的磁盤的資源數(shù)據(jù)。而且它允許在相同的資源下跨會話請求數(shù)據(jù)，甚至跨WEB站點的情況下使用相同的資源數(shù)據(jù)，例如兩個站點都使用了同一張圖片。Disk Cache 會指定的根據(jù)瀏覽器的緩存規(guī)則以及根據(jù) HTTP頭信息中的各類字段來判定哪些資源不可以緩存到磁盤中，哪些資源可以緩存到磁盤中，這樣做好區(qū)分，但是也能做好存儲空間的共用，提升存儲的效率；根據(jù)緩存有效率策略，哪些資源是在有效期限內(nèi)仍然可用的，哪些資源是超過有效期需要重新請求服務器的。當瀏覽器的請求命中緩存之后，瀏覽器先做判斷，是否存在與硬盤中，如果是Disk Cache便會更具瀏覽器策略從硬盤中讀取Disk Cache資源，雖然比起從內(nèi)存中讀取資源數(shù)據(jù)的速度是慢了一些，但比起網(wǎng)絡請求獲取資源數(shù)據(jù)，在大部分情況下還是快了很多的。相當大部的一部分的緩存都是存儲在Disk Cache。雖然對比Memory Cache 速度慢，但是優(yōu)勢在于可以存儲更多的內(nèi)容。

（3）Service Worker，在上述的緩存策略以及讀取緩存，失效策略，緩存有效性等動作都是由瀏覽器內(nèi)部通過其緩存策略自動判斷進行的一種緩存策略，我們一般通過設置web請求頭的部分字段來強制通知瀏覽器，需要使用哪種策略，不使用哪種策略，而不是自己手動操作瀏覽器使用哪種策略。它具有在瀏覽器也服務器之間的轉(zhuǎn)發(fā)請求功能。判斷哪些請求需要轉(zhuǎn)發(fā)給瀏覽器，如果需要向服務器發(fā)起請求的按照瀏覽器的緩存策略就自動轉(zhuǎn)發(fā)請求到服務器端，就直接使用瀏覽器的內(nèi)存緩存或者磁盤數(shù)據(jù)緩存的數(shù)據(jù)直接返回緩存數(shù)據(jù)，不需要再次轉(zhuǎn)發(fā)給服務器請求資源數(shù)據(jù)。從而極大提高瀏覽器的瀏覽使用體驗。

一個URL的數(shù)據(jù)經(jīng)過多個Hash 函數(shù)生成的 哈希值映射到槽位的一個二進制位，并且是一個固定長度的槽位占有多個二進制位。映射過程就是這個哈希值和一個槽位上多個元素按位LXOR（按位異或）的計算規(guī)則(相同的取0否則取1)。然后多個哈希函數(shù)產(chǎn)生的多個哈希值會映射到多個槽位上，LXOR過濾器會維護這些槽位。通過將這些槽位中的二進制數(shù)據(jù)做整體計算生成一個唯一的哈希函數(shù)的值。最后用戶查找URL地址時會將多個函數(shù)映射的槽位LXOR(按位與)計算。假設通過哈希函數(shù)運算的結(jié)果是T1，同時將URL輸入到上面構(gòu)造的唯一的一個函數(shù)中，計算結(jié)果是T2。如果T1等于T2，則確認URL是存在與LXOR過濾器中，否則不存在。即判斷指紋函數(shù)的元素值和3個哈希函數(shù)對應的K-Bites的值按位異或之后的值是否相等，如果相等則表示元素可能是在LXOR過濾器中否則不存在。

LXOR過濾器類似于集合數(shù)據(jù)結(jié)構(gòu)，添加元素并檢查給定的元素是否存在于集合中。有小概率的錯誤判斷，這種誤報事件為假陽性事件False-Positive Probability。由于LXOR過濾器可以使用比原始集少的內(nèi)存。因此，LXOR過濾器接受一個小概率的錯誤減少內(nèi)存使用。查詢元素是否在集合中的過濾器有很多應用：例如，使用瀏覽器URL緩存。在這樣的存儲中，內(nèi)存數(shù)據(jù)結(jié)構(gòu)避免了磁盤訪問同時使用簡單數(shù)據(jù)結(jié)構(gòu)并且使用更少的內(nèi)存。這樣可以在有限的內(nèi)存中，存入足夠多的URL地址。因此我們提出了基于有限時間與或過濾器的瀏覽器緩存LXOR。

2 相關工作

對于靜態(tài)數(shù)據(jù)集合，使用哈希函數(shù)的指紋可以從根本上實現(xiàn)減少的內(nèi)存使用。但是哈希函數(shù)可能計算需要花費時間，然而Dietzfelbinger 和 Pagh提出了一種新過濾器，我們稱之為異或過濾器。它的建立是基于過濾器，如 Bloom過濾器。我們基于有限時間的異或過濾器作為一種實用的數(shù)據(jù)結(jié)構(gòu)具有優(yōu)勢。

我們發(fā)現(xiàn)許多Bloom 過濾器先關的數(shù)據(jù)結(jié)構(gòu)是基于數(shù)據(jù)庫系統(tǒng)設計，避免內(nèi)磁盤直接訪問。當前主流的數(shù)據(jù)庫引擎必須支持頻繁更新，是一種合并LSM數(shù)據(jù)結(jié)構(gòu)。在高層次LSM 樹內(nèi)存中保持快速批量合并到持久存儲中的數(shù)據(jù)的組件中，內(nèi)存組件累積數(shù)據(jù)庫更新，從而將更新成本分攤到本地存儲中。加速查找，許多 LSM 樹實現(xiàn)（例如 LevelDB）使用Bloom 過濾器。合并組件時，通常會構(gòu)建一個新的過濾器。我們可以更新現(xiàn)有的過濾器支持快速合并的數(shù)據(jù)結(jié)構(gòu)（例如 Bloom 過濾器）需要原始過濾器有額外的容量，合并的結(jié)果有更高的假陽性的可能性。

通常，每當過濾器必須通過與其他計算機的網(wǎng)絡連接（例如，緩存和網(wǎng)絡查詢），通常緩存是可變的。隨著時間變化，訪問不同URL，通過過濾器的緩存會發(fā)生變化?；跁r間的變化策略設置過濾器的緩存策略，記錄URL訪問的時間和次數(shù)，為URL設置訪問的等級和Token。

3 理論基礎

給定一個元素URL，我們使用隨機選擇的密鑰生成它的 k 位指紋哈希函數(shù)，我們假設一個理想化的完全獨立的散列函數(shù)；我們在表1總結(jié)了我們的符號。我們想要構(gòu)造一個從所有可能元素到k位整數(shù)的映射 F，這樣它就可以映射所有密鑰y從集合S到他們的k位指紋（x）。因此，如果我們選擇集合中的任何元素，那么它會得到通過設計映射到其指紋 F(y)=fingerprint(y)。我們的目標是擁有數(shù)組 B 中三個哈希函數(shù)給出的位置處的值與指紋一致(B[h0(x)]xor B[h1 (x)]xor B[h2(x)]=fingerprint(x)) 對于所有元素 x∈S。哈希函數(shù)h0,h1,h2 被假定為獨立于用于指紋的哈希函數(shù)。檢測成員函數(shù)計算哈希函數(shù) h0,h1,h2，然后從表 B 中的這些條目構(gòu)造預期指紋，并將其與給定密鑰的指紋進行比較。如果密鑰在集合中，則該表包含指紋是匹配的。處理時間包括三個哈希函數(shù)的計算以及三個隨機內(nèi)存訪問。盡管其他相關的數(shù)據(jù)結(jié)構(gòu)可能需更少的內(nèi)存訪問，但大多數(shù)由于內(nèi)存級并行性，可以同時并發(fā)訪問三個以上的內(nèi)存。因此，可以減少內(nèi)存訪問的時間。

對于生成的哈希函數(shù)值，按照訪問URL次數(shù)做記錄，根據(jù)頻率設置等級，瀏覽器根據(jù)等級進行概率性選擇存儲在內(nèi)存中。在指定時間內(nèi)刪除訪問頻率低的URL產(chǎn)生的哈希函數(shù)值。保證LXOR過濾器緩存中存儲的是高頻率訪問的URL，本算法將低頻率訪問量的URL設置為較低的緩存等級來增大R，從而使高頻率的訪問的URL以更高概率緩存在LXOR過濾器中，我們可以給出R變化的公式：

其中Frequence是URL訪問頻率等級，a是令牌權(quán)值。f(Frequence,a)代表令牌生成量/消耗量關于內(nèi)容流行度等級與令牌權(quán)值的變化函數(shù)，是一個隨URL等級單調(diào)遞減的函數(shù)，設置二次函數(shù)，例如：

f(Frequence,a)=-a×Frequence+1

對不同的函數(shù)進行實驗來選取其中性能更好作為最后的參數(shù)。a控制了R增加的速率，如果a設置的過大，令牌將難以獲取，高頻率訪問URL不容易被加入到緩存中，對緩存的變化并不敏感，會導致緩存的效率下降。同樣的，如果a設置的過小，令牌將失去意義，因為大部分內(nèi)容都會被進入緩存環(huán)節(jié)，算法會演變?yōu)楦怕市跃彺嫠惴?，從而導致緩存命中率進一步的降低。a值過大或過小都會降低瀏覽器LXOR過濾器緩存的命中率，因此我們會監(jiān)測一段時間內(nèi)緩存命中率的變化趨勢，動態(tài)地調(diào)整a值，調(diào)整算法如算法1所示。

4 算法框架及描述分析

從緩存的角度分析，一定是希望能在緩存中存入經(jīng)可能多的URL地址數(shù)據(jù)，但是為了保證瀏覽器緩存有效的運行，使用ρ控制URL等級的大小。

Hot=ρ×f(c)

其中f(c)是瀏覽器對URL請求對熱度預測函數(shù)。為了實現(xiàn)一段時間內(nèi)的URL熱度的預測，在瀏覽器中控制Token 的數(shù)量大小。在一段時間內(nèi)的Token的中位數(shù)，根據(jù)Token大小變化動態(tài)調(diào)整ρ 的值。動態(tài)調(diào)整算法如算法2所示。

算法1 數(shù)據(jù)標記處理變量：ε←a 的偏移量1: function offsetAlpha()2: count←0 3: for every Δt do 4: h←url access times 5: m←url miss times 6: if h?((m+h))>Hr then 7: count←count+1 8: else 9: count←0 10: ε=‐1·ε 11: end if 12: a=a+ε 13: Hr=h?((m+h))14: end for 15: end function

帶有時間戳和次數(shù)標記的算法LRUF，是在LRU算法基礎設計上，記錄每一個URL在瀏覽器緩存中的停留時間，減少計算量和存儲空間，使用訪問次數(shù)替換為在緩存中存留的時間。每間隔一點時間統(tǒng)計在瀏覽緩存中的存活的時間周期?？梢砸来闻袛郩RL訪問的熱度和URL的等級之間的差異，據(jù)此計算出瀏覽器緩存的概率偏移量。

算法2 ρ的調(diào)整算法變量：ε←ρ的偏移量T←上一個時間段的Tmin的中位數(shù)1: function offsetCache()2: count←0 3: for every Δt do 4: s←sum of Tmin 5: count←number of access 6:7: ?=-1×? 8: end if 9: ρ=ρ+? 10:11: end for 12: end function

5 實驗

我們在配備 MacBook Pro M1 Pro處理器上運行基準測試：M1 Pro 處理器以 2.5 GHz 運行，具有 24 MB L2 緩存。基于一組 1M 或 10M 的原始數(shù)據(jù)構(gòu)建過濾器。我們建造由10M 個隨機查詢鍵組成的集合。這組查詢過濾器的空間使用率和查詢過濾器器的元素多對比。發(fā)現(xiàn)在LXOR過濾器中使用較少的使用空間使用率以及較快的查詢速度。在一定時間范圍內(nèi)，LXOR組成過濾器緩存在假陽性率較低。一定時間范圍內(nèi)的URL請求數(shù)據(jù)熱度較高，在查詢數(shù)據(jù)和內(nèi)存使用率方面有一定的優(yōu)勢。

在內(nèi)存利用率，在不同的數(shù)量URL訪問的場景下的假陽性FPP比對。LXOR過濾器占用內(nèi)存比要低，同時在假陽性率也是低于XOR過濾器，在數(shù)據(jù)量增加的場景下，優(yōu)勢是更加明顯。

在空間內(nèi)存空間使用率方面，如圖1和圖2，LXOR過濾器是低于Bloom過濾器、Cuckoo過濾器、XOR過濾器，隨這個數(shù)據(jù)量增加，LXOR過濾器在假陽性率方面依舊占有優(yōu)勢，在內(nèi)存使用率方面依舊如此。由此可見，在使用時間維度的與或過濾器在緩存的效率和內(nèi)存空間方面的具有優(yōu)勢。

圖1：1M keys場景下的內(nèi)存使用量對比

圖2：10M keys場景下內(nèi)存使用量對比

在基于一定熱點的URL作為key值，在查詢效率方面有優(yōu)勢，查詢效率更高。在增加查詢的URL的場景下優(yōu)勢是更加明顯。在查詢URL查詢方面，由于使用較少內(nèi)存，令URL的查詢更快，超越了XOR過濾器、Cuckoo 過濾器以及Bloom過濾器。雖然在XOR 過濾器在查詢效率有一定的優(yōu)勢，但是在LXOR過濾器加入了時間和次數(shù)的維度，使得空間占有優(yōu)勢，在查詢效率方面亦是如此。如圖3和圖4所示。

圖3：在1M Keys空間使用率下，查詢效率對比

圖4：在10M keys空間使用率下查詢下查詢效率對比

6 結(jié)語

本文提出的基于有時間與或過濾器的瀏覽器緩存設計，目的是為了提高瀏覽器的緩存性能。本文的算法通過有限與或過濾器的方式減少內(nèi)存使用量和提升查詢效率方式。與有效時間內(nèi)的緩存結(jié)合的方式對比，新的方法效率更高，進一步提升了緩存的效率，下一步工作計劃是增加更多應用場景的緩存使用，提升LXOR過濾器緩存的普適性。同時增加URL的模擬數(shù)據(jù)，進一步提升緩存的利用率，在緩存時間和緩存效率之間做平衡，做到最大化利用緩存，存儲更多URL信息。