基于深度學習的視頻緩存算法

陶佳能+劉獻忠

摘 要

在視頻深度學習環境下，要提高用戶體驗就必須在視頻訪問速度方面做文章。而對視頻訪問速度的快慢產生影響的主要因素有兩個：服務器響應速度和網絡傳輸效率，但服務器響應用戶請求的速度更是重中之重。目前，在視頻深度學習環境下，采用緩存技術是提升用戶訪問速度的一個有效手段，也被業界廣泛關注，并進行了實際的應用探索。當前，主要的經典算法有 LFU、LRU、LRfU、sc等，本文對他們進行了簡單的介紹，著重就 LFU、LRU 算法作了重點的分析研究，并通過某運營商提供的實際運行數據與在視頻深度學習環境下獲得的模擬數據開展實證比對分析，觀察各算法的實際表現。從各算法的應用結果的具體情況出發，研究視頻深度學習環境下所應采用的緩存算法策略，進而為提高視頻深度學習系統的緩存命中率尋求理論研究根據。

【關鍵詞】視頻深度學習系統 緩存算法 模擬實驗 實證研究

1 引言

在網絡和多媒體技術日趨成熟的今天，視頻深度學習在IPTV、視頻網站等多個平臺上得到了非常普遍的應用，用戶對視頻深度學習環境所獲得的體驗提出了更高的要求，而比較關注的問題主要集中在視頻深度學習速度上面。在視頻深度學習系統里，恰當采用緩存技術對于提高用戶訪問速度非常關鍵。一種基于訪問頻率的算法，它運用計算用戶的熱點資源在一段時間內訪問的頻率，運算得出并確定下一次是否可能將要訪問的資源。這些算法，當然，最容易理解的，因此最容易被接受的，包括LFU（leastfrequentlyused），和二 （2queues）在此基礎上發展起來的，LIRS （LowInterReferenceRecencySet）；基于日志的資源訪問時間，通過時間做出判斷，包括LRU；運用訪問時間和訪問頻率集成的組合算法，包括LRFU等。當然，由于現實中存在多種因素，目前通行的緩存算法都存在著一定不足，所以現在還沒有一種緩存算法能很好的解決所有目前已經發現的緩存問題。從具體情況出發，研究改進現存的緩存算法，盡可能達到我們的目標是問題的關鍵。在現實因素干擾下，上述緩存算法都存在著一定不足，有其一定的適用范圍，必須結合具體情況有針對性的作出調整。

2 算法的原理與實現

高速緩存算法的歷史有一個自己的發展階段，都是在總結研究過去算法的基礎上進行進一步的研究改進的。一些經典的算法如LRU和LFU，它們有實現簡單的巨大優點，是最基本的算法。對于LRU算法的改進，如LRU-K和其他的一些變異算法，都是從不同的角度對LRU算法作出了改進，在有些地方都取得了成功。它結合了LRU和LFU，LRFU，兼顧了LRU和LFU，以及LFU和LFU的優點。其他的一些新算法，如SC和LIRS，它們有運行穩定的特點，在一些特定的環境中使用的效果非常好。

2.1 最近最少使用算法（LRU）

LRU，也就是緩存保留的意思，是指對最近一段時間使用比較多的熱點資源進行緩存保留，并消除掉近期使用比較少的熱點資源數據。所以，替換內容的時候只要把近期排在最少使用范圍的熱點資源數據作出替換就可以了。

LRU在緩存中會自動對內容作出列表，便于存儲最近經常使用的熱點資源數據。當用戶請求響應數據的時候，它將自動跳轉到第一位。而當用戶所請求的熱點資源數據在列表中，這是已經在高速緩存（例如是K），然后原來在K的數據將被拉到后方位置并被消除；而當用戶請求響應的數據不在列表中的時候，就會馬上被提取到緩存里面并自動跳轉到第一位，其他內容的順序位置同時依次往后排，那么排在最后的熱點資源數據就自動消除。

2.2 最少頻率使用算法（LFU）

LRU算法以最近的訪問時間作為最重要的依據。而LFU算法是以訪問的頻率作為最重要的依據，依據內容的訪問頻率并作出一定的排序，這種方法比LRU的考慮更為合理，因為，訪問頻率是最能真實的反映用戶使用熱點資源的。在如今許多后續改進的算法中，大多采用了頻率相關的方法。此外，LFU算法使用緩存機制不同于LRU算法。LFU保持緩沖區中的匯總清單，記錄訪問數量的視頻。如果用戶請求的視頻響應不在緩存中，就可以將本次訪問加入列表，并把表中排在最后的作出消除處理。

2.3 最近最少使用算法（LRU-K）K

LRU算法的緩存標準，是以數據首次被訪問為依據。從某種意義上來講，這是不合理的，因為本次訪問的熱點資源有可能在今后的很長一個時期都不再進行再次訪問，這就造成了緩存資源的極大浪費，從而使經常使用的熱點資源不能進入緩存中，影響用戶的響應體驗。解決方案是在定義的T周期時間內，當熱點資源達到被事先設定的K次訪問時，它就自動被放置在緩存列表的頂部。因此，隨著LRU-K算法。

3 總結分析

基于模擬數據和真實數據上的實驗分析我們可以發現，得出的模擬數據和真實數據的結果存在著一致性。但不同的LIRS算法，與其他算法相比基本相同，研究證明模擬數據與實際數據非常適合，可以說是現實運行情況的真實反映。在視頻深度學習環境中，LFU，LRFU和SC是業界目前3個最好的算法，簡單又易于實現，只考慮Cache的命中率的情況下，LRFU是最佳選擇；如果考慮到用戶實際的服務器容量以及網絡費用等情況，我們可以對這3種算法的差異加以認真研究，針對具體情況選擇最合適的算法。

最后，本論文對現有的視頻深度學習系統中已經采用的一些緩存算法如LFU、 LRU 、LRfU、sc等，本文對他們進行了簡單的介紹，著重就 LFU、 LRU 算法作了重點的分析研究，同時有針對性的給出了各算法的實現模式，利用模擬數據和實際數據實證比較分析了兩者之間的差異，為達到理想的效果，要充分考慮到服務器的容量，選擇相應的算法，對一些參數作出適當的調整。

參考文獻

[1]錢培杰，武娟，高成英.視頻點播環境下的緩存算法研究[J].計算機科學，2015，42（S1）：38-44.

[2]郝偉，蘇秀琴，楊小君，李哲，吳慧蓮.基于隊列式緩存結構的視頻圖像存儲算法[J].光子學報，2006（09）：1431-1434.

作者單位

華東師范大學計算機科學與軟件工程學院 上海市 200062endprint