296
基於年紀和成本（Age & Cost）的緩存替換(cache replacement)機製
一、客戶端的緩存與緩存替換機製
客戶端的資源緩存：
在客戶端遊戲中，通常有大量的資源要處理，這些可能包括貼圖、動作、模型、特效等等，這些資源往往存在著磁盤文件->內存(->顯存)的數據通路，因為從磁盤文件讀入內存是一個昂貴的的操作，所以很多客戶端中的處理方法是放入一個緩存，當讀入一個文件到內存後，就在內存中為他暫時保留一段時間，下次在讀入這個文件就不用重複從磁盤讀了，這種優化帶來了客戶端效率的極大提升，比如在一個有上百玩家的場景，可能我們用的玩家模型資源都是一個，隻是貼圖不同而已，如果使用緩存，那麼你隻需要從磁盤讀取一次玩家模型的文件，而如果不使用，你可能要反複讀取上百次，IO操作的低效會讓用戶很卡。
緩存替換：
然而我們用戶的內存是有限大的，如果我們把每個資源都讀進去保留而不釋放，遊戲就會越來越吃內存，一個典型的大象網遊的資源可能幾個G，最壞的情況用戶讀入了所有資源到緩存而不釋放，那麼也會因為內存不夠用而崩潰。所以這裏就通常要選擇一些緩存替換機製：即動態的釋放和加入資源到緩存，有進有出，但是要保證盡量讓用戶IO操作減少，一種最樂觀的情況是，存在緩存中的資源恰好是用戶使用的最多的資源，使用較少的會被使用多的交換出去。這模仿了CPU的cache機製。
二、現有的一些緩存替換機製：
基於CPU和操作係統的一些經典的cache replacement算法，客戶端的資源緩存替換機製有以下一些做法：
1.懶人型，最簡單的。就是沒什麼交換算法，隻管讀入緩存，然後隻是定期的或發現緩存太大時一次性的清空緩存重來，這種在清空後會經曆一段加載資源的頓卡，突然發現目前我們遊戲的機製就是這樣的，尷尬。。。但是這可能符合簡單粗暴實用的原則。
2.LRU算發：大名鼎鼎的算法，當出現替換時，總是替換那個 上次使用時間距離限製最遠的那個，這種算法認為最近使用的就是最長使用的，這種算法被多數體係結構使用，不過在某些極端情況下會導致thrash（內存的劇烈顛簸），比如說當一段時間內需要加載的東西過多時，而加載的資源呈有序重複序列時可能緩存會被一遍遍的清空。
3.MRU算法：它與LRU對應，但是它總是交換出最近使用的那個，這個傾向於保存最老的那個，聽起來很奇怪，但是它往往不單獨使用，通常配合LRU使用，當LRU出現thrash時轉到MRU算法會有所幫助
三、基於Age和Cost 的算法：
今天看到了一種算法基於Age和Cost，似乎對客戶端的緩存替換研究的更加到位一些，這種算法梗概如下：
1.Age：
為每個緩存保存一個32位的Age值初始為00000000（也就是第一次載入緩存時）（文檔暫以8位代替），,每當hit一次，當前的最低位置1，每個計數區間（或每一幀）這個Age左移一位，例如某個資源在幾幀內Age的變化
frame1：00000001（used）
frame2：00000011（used）
frame3：00000111（used）
frame4：00011100（not used）
frame5：00111000（not used）
根據當前的age，可以算出Age percentage Cost APC=1的數量/總的位數
APC越高說明這個資源近段時間是越有用的，替換時選擇APC低的替換
基於Age的算法更加精確的得出了最近一段時間內資源的使用率，找出比lru更合理的替換，
2.Age擴展算法：
上麵的每一步是按照幀來算的，實際使用中沒幀來統計肯定是有點過了，可以按照一定時間片來統計，在一定時間片內可能一個資源回被用到n次，因此擴展的Age算法就單純的標記1改為標記n，即這個統計區間內被用到的次數，如上例
time1：00000005（used 5 times）
time2：0000005A（used 9 times）
time3：000005A1（used 1 times）
time4：0005A100（not used）
time5：005A1000（not used）
這樣APC=各位的值相加/最大的可能值
例如某個模型資源在上一段時間內被100個玩家引用，那麼替換他的代價就明顯要高很多，Age的擴展方法考慮的引用的頻次
3.Age&Cost：
在實際的操作中，有些資源的替換成本是非常大的，例如從硬盤讀入一個10m的貼圖顯然比讀入一個100k的貼圖成本大很多，所以替換時不能相同對待，這裏考慮的成本記為relative cost（RC），算法中將最終的緩存替換成本TC=APC*RC，這樣來綜合考慮，通常將APC取值區間規整為0-1，而將rc規整為 1-10（算法作者認為載入文件的時間成本權重更大）。這樣對不同的資源為它賦值不同的載入時間成本RC，再乘以上麵的Age算法中的APC（引用頻率成本），綜合得出了它的緩存替換成本。一種比較簡單的rc的賦值可以用它的文件大小來自動賦值。
幾個例子：
APC RC TC
1 10 10 這說明這個文件的替換成本非常大，主要是文件比較大，同時它引用的頻率特別高，這種資源基本上不會輕易從緩存中替換出來
0.2 8 4 這個文件很大，但是引用頻率還很低，所以替換程度是中等的
1 5 5 文件很小，說明載入很快，但是引用頻率很高，所以可以替換出來（因為再載入的成本低），也可以不替換出來，中等的
0.1 10 1 這個文件很大，載入很慢，但是引用很少，也就是說內存中存在一個很占地方但是幾乎不怎麼用的資源，值得替換出來，節省空間，因為不常用再次載入就算費時也值得
比如我們的遊戲中開場有一個非常大的貼圖資源，用於登錄界麵，它最開始有60M，（遊戲中一般的貼圖在幾百K以下），而它在遊戲中不會再被用到，現有的算法這個很大的資源會一直占在緩存裏，用戶內存被無故吃了很多，但是應用本算法，它的RC在遊戲中可以達到上限10，但是APC基本上是下限，也許0.01，所以他的TC可能隻有0.1，將登陸之後很快的時間內被從內存中釋放出來。
趕緊利用這個算法節省一下我們的內存
最後更新：2017-04-03 16:48:46