緩存應(yīng)用和淘汰機(jī)制的原理和實現(xiàn)

緩存應(yīng)用

緩存系統(tǒng)在計算機(jī)中非常重要，因為不同層級的數(shù)據(jù)訪問速度差異很大。CPU、內(nèi)存和磁盤的訪問速度從幾十納秒到幾毫秒不等。為了避免每次CPU處理數(shù)據(jù)都需從磁盤讀取數(shù)據(jù)，系統(tǒng)會大大降低運行速度。為了解決這一問題，計算機(jī)系統(tǒng)中默認(rèn)有兩種緩存：CPU中的末級緩存（LLC）用于緩存內(nèi)存中的數(shù)據(jù)，避免每次從內(nèi)存中存取數(shù)據(jù)，內(nèi)存中的高速頁緩存（page cache）用于緩存磁盤中的數(shù)據(jù)，避免每次從磁盤中存取數(shù)據(jù)。

在層次化的系統(tǒng)中，緩存是一個快速子系統(tǒng)，在數(shù)據(jù)存在緩存中時，能夠避免每次從慢速子系統(tǒng)中存取數(shù)據(jù)。在互聯(lián)網(wǎng)應(yīng)用中，Redis被視為快速子系統(tǒng)，而數(shù)據(jù)庫則是慢速子系統(tǒng)。Redis是一個獨立的系統(tǒng)軟件，如果應(yīng)用程序想使用Redis緩存，就需要增加相應(yīng)的代碼。因此，Redis也被稱為旁路緩存，即讀取緩存、讀取數(shù)據(jù)庫和更新緩存的操作都需要在應(yīng)用程序中完成。Redis緩存根據(jù)是否接受寫請求，分為只讀緩存和讀寫緩存兩種類型。只讀緩存能夠加速讀請求，而讀寫緩存可以同時加速讀寫請求。讀寫緩存又分為同步直寫和異步寫回，可以根據(jù)業(yè)務(wù)需求在保證性能和數(shù)據(jù)可靠性之間進(jìn)行選擇。

淘汰機(jī)制

緩存的容量是有限的，需要按一定規(guī)則淘汰數(shù)據(jù)以騰出空間，提高緩存命中率，提升應(yīng)用的訪問性能。緩存容量的規(guī)劃通常需要綜合考慮應(yīng)用數(shù)據(jù)實際訪問特征和成本開銷，建議把緩存容量設(shè)置為總數(shù)據(jù)量的15%到30%。對容量的設(shè)置可以通過命令CONFIG SET maxmemory 4gb來進(jìn)行設(shè)置。同時，Redis提供8種淘汰策略：noeviction、volatile-random、volatile-ttl、volatile-lru、volatile-lfu、allkeys-lru、allkeys-random和allkeys-lfu。

這些策略大體可以分為兩類，其中noeviction（不淘汰數(shù)據(jù)）表示當(dāng)緩存已經(jīng)被寫滿時再有寫請求時Redis不再提供服務(wù)，直接返回錯誤。另外7種策略按一定范圍對緩存數(shù)據(jù)進(jìn)行淘汰，針對設(shè)置過期時間的數(shù)據(jù)進(jìn)行淘汰以及對所有數(shù)據(jù)進(jìn)行淘汰。具體包括volatile-ttl，volatile-rando，volatile-lru，volatile-lfu，allkeys-random，allkeys-lru和allkeys-lfu。LRU算法

LRU算法

LRU算法全稱Least Recently Used，按照最近最少使用的原則來篩選數(shù)據(jù)，把最不常用的數(shù)據(jù)淘汰出去，而最近頻繁使用的數(shù)據(jù)會留在緩存中。LRU會把所有的數(shù)據(jù)組織成一個鏈表，鏈表的頭和尾分別表示MRU端和LRU端，分別代表最近最常使用的數(shù)據(jù)和最近最不常用的數(shù)據(jù)。LRU算法在實際實現(xiàn)時，需要用鏈表管理所有的緩存數(shù)據(jù)，并對被訪問的數(shù)據(jù)進(jìn)行鏈表移動操作。為了減輕數(shù)據(jù)淘汰對緩存性能的影響，Redis默認(rèn)會記錄每個數(shù)據(jù)的最近一次訪問的時間戳（由鍵值對數(shù)據(jù)結(jié)構(gòu)RedisObject中的lru字段記錄）。 Redis在需要選擇淘汰的數(shù)據(jù)時，首先會隨機(jī)選擇N個數(shù)據(jù)將它們作為一個候選集合，并比較它們的lru字段，最后淘汰lru字段最小的數(shù)據(jù)。淘汰數(shù)據(jù)時，Redis也會再隨機(jī)選擇一些lru字段比候選集合中最小lru字段還要小的數(shù)據(jù)，將它們放入候選集，如果候選集的數(shù)據(jù)個數(shù)達(dá)到了maxmemory-sample配置的個數(shù)，Redis就開始將lru字段值最小的數(shù)據(jù)淘汰。

LFU算法

LFU策略增加了一個計數(shù)器用以統(tǒng)計訪問次數(shù)。淘汰數(shù)據(jù)時，首先會根據(jù)數(shù)據(jù)的訪問次數(shù)進(jìn)行篩選，把訪問次數(shù)最低的數(shù)據(jù)淘汰出緩存。如果兩個數(shù)據(jù)的訪問次數(shù)相同，則再比較這兩個數(shù)據(jù)的訪問時效性，把距離上一次訪問時間更久的數(shù)據(jù)淘汰出緩存。在實現(xiàn)LFU策略時，Redis把原來24bit大小的lru字段拆分成了兩部分：ldt值和counter值。counter只有8bit，記錄的最大值是255。因此，LFU策略采用了一個非線性遞增的計數(shù)規(guī)則，通過配置不同的lfu_log_factor控制計數(shù)器值的增加速度。此外，Redis還設(shè)計了一個counter值的衰減機(jī)制，通過配置衰減因子lfu_decay_time來控制訪問次數(shù)的衰減。具體操作是計算當(dāng)前時間和數(shù)據(jù)最近一次訪問時間的差值，再換算成分鐘單位，再除以lfu_decay_time值，就是數(shù)據(jù)counter要衰減的值。

• 《哈利波特魔法覺醒》肖像任務(wù)拯救攻略技巧指南（如何完成肖像任務(wù)？一步一步指導(dǎo)）
• 涅槃技能加點技巧攻略秘籍（從零開始，掌握涅槃技能加點的正確方法，讓你的角色更加強(qiáng)大�。�
• 《荒野亂斗》新英雄艾爾普里莫拳王操作技巧攻略指南
• 星際戰(zhàn)甲移植技能攻略指南（增強(qiáng)戰(zhàn)斗力的關(guān)鍵技巧）
• 無限螺旋出裝攻略技巧指南（掌握無限螺旋裝備搭配技巧，成為無敵戰(zhàn)士）