Cache即緩存，我們?cè)诤芏嗟胤蕉紩?huì)碰到。比如CPU里面的L1 Cache，L2 Cache；在內(nèi)存中我們會(huì)說(shuō)內(nèi)存cache了某些數(shù)據(jù)；在分布式系統(tǒng)中為了提高速度，我們會(huì)做一些cache；瀏覽器里會(huì)將訪問(wèn)域名服務(wù)器dns后得到的數(shù)據(jù)cache起來(lái)，這樣下次解析同一個(gè)域名時(shí)不需要再次查詢dns。所有這些場(chǎng)景中都會(huì)用到cache。Cache是一個(gè)通用的概念，當(dāng)我們看它時(shí)，首先不是看它本身，而是要了解它為什么會(huì)存在。

Cache為什么存在？我們來(lái)看看計(jì)算機(jī)體系的存儲(chǔ)架構(gòu)。

計(jì)算機(jī)就是為了計(jì)算出某種東西，所以它最終肯定是一個(gè)計(jì)算模塊。于是在整個(gè)金字塔的塔尖，就是我們的計(jì)算單元，它往往是CPU中的計(jì)算電路。計(jì)算單元外部會(huì)存一些數(shù)據(jù)，就是L1 Cache，它存放的數(shù)據(jù)離CPU最近。再遠(yuǎn)一點(diǎn)是L2 Cache，再往后就是內(nèi)存，硬盤，以及最遠(yuǎn)端的云。

看到這個(gè)金字塔，大家可能會(huì)很好奇：為什么需要這么多層的存儲(chǔ)結(jié)構(gòu)呢？而且相鄰存儲(chǔ)之間的訪問(wèn)速度相差十倍甚至以上，尺寸上也相差十倍甚至更多。我們把計(jì)算機(jī)存儲(chǔ)架構(gòu)搞得這么復(fù)雜，似乎非常繁瑣，而并沒(méi)有見(jiàn)到什么好處。能不能在計(jì)算單元下面直接對(duì)應(yīng)硬盤中的數(shù)據(jù)，將硬盤跟計(jì)算單元之間的三層直接省去？其實(shí)并不可以。如果計(jì)算過(guò)程中所有的數(shù)據(jù)都從硬盤中讀取，你會(huì)發(fā)現(xiàn)運(yùn)算速度變得非常非常慢。為什么呢？這就回到計(jì)算的本質(zhì)。那么計(jì)算是什么呢？維基百科上將計(jì)算定義為一種將單一或多個(gè)輸入值轉(zhuǎn)換為單一或多個(gè)結(jié)果的過(guò)程。這個(gè)過(guò)程的運(yùn)行時(shí)間可以這樣表示

**運(yùn)行時(shí)間 ****= 計(jì)算時(shí)間 + 數(shù)據(jù)遷移時(shí)間****
**
其實(shí)絕大多數(shù)情況下，運(yùn)行時(shí)間都主要花在數(shù)據(jù)遷移上。在算法設(shè)計(jì)中評(píng)估算法復(fù)雜度的Big O量級(jí)，就是程序運(yùn)行過(guò)程中讀取數(shù)據(jù)移動(dòng)數(shù)據(jù)的量級(jí)。所以在整個(gè)計(jì)算過(guò)程中，數(shù)據(jù)遷移是很重要的。
回到計(jì)算機(jī)體系存儲(chǔ)結(jié)構(gòu)的金字塔中可以發(fā)現(xiàn)，越往上，離計(jì)算單元越近。所以計(jì)算單元從L1 Cache中拿數(shù)據(jù)的路徑比從L2 Cache要短。路徑越短，速度越快。為了縮短運(yùn)行時(shí)間，我們可以花更高的價(jià)格，做更快的存儲(chǔ)單元，提供更高的速度。然而在計(jì)算單元身邊能夠放下的存儲(chǔ)是有限的。因此離計(jì)算單元近的存儲(chǔ)器就相當(dāng)于精英，單價(jià)高，存儲(chǔ)量少。與精英是普通人的子集相似，上圖金字塔中每一層的數(shù)據(jù)也是下一層的子集。這時(shí)候我們可以引出Cache的概念了：

Cache就是把我們需要的數(shù)據(jù)放到離我們近的地方
**

最優(yōu)策略一定是能夠選擇那些你即將用到的數(shù)據(jù)。在數(shù)據(jù)被使用之前，將數(shù)據(jù)放在離你最近的地方，可以極大減少數(shù)據(jù)遷移時(shí)間。

什么樣的數(shù)據(jù)會(huì)放到身邊呢？根據(jù)啟發(fā)式算法我們知道，之前經(jīng)常被用到的數(shù)據(jù)很可能再次被用到。所以如果數(shù)據(jù)之前被用過(guò)一次，就在身邊緩存一份。

還有什么樣的數(shù)據(jù)呢？那些跟之前被使用的數(shù)據(jù)相鄰的數(shù)據(jù)，也可能會(huì)被用到。比如說(shuō)老師讓小明幫忙拿一支筆過(guò)來(lái)，筆旁邊放著黑板擦。小明不僅拿了筆，還把筆旁邊的黑板擦也拿過(guò)來(lái)。為什么呢？因?yàn)楹诎宀粮P是相鄰的，用筆的時(shí)候很可能要用黑板擦，用黑板擦的時(shí)候也很可能要用筆。因此將兩個(gè)東西一塊拿過(guò)來(lái)就更好好。再比如說(shuō)操作系統(tǒng)中page的概念。內(nèi)存從硬盤中拿數(shù)據(jù)，往往是拿一個(gè)page。為什么呢？因?yàn)槿绻皇悄眯枰臄?shù)據(jù)，那么下次讀取數(shù)據(jù)可能就在附近，與其讓硬盤再轉(zhuǎn)一個(gè)圈，不如將相鄰的一塊都拿過(guò)來(lái)。如果下次訪問(wèn)相鄰的數(shù)據(jù)時(shí)，直接從內(nèi)存中讀取。

兩種方式選擇應(yīng)該緩存起來(lái)的數(shù)據(jù)：一是之前用過(guò)的數(shù)據(jù)，二是跟之前用過(guò)的數(shù)據(jù)相鄰的數(shù)據(jù)。
講到存儲(chǔ)自然要提到替換，因?yàn)镃ache的大小總是有限的，不可能存下所有的數(shù)據(jù)。那么Cache寫滿后該怎么替換呢？剛才提到，之前用過(guò)的數(shù)據(jù)可能再被使用。換句話說(shuō)，那些最近沒(méi)有被使用過(guò)的數(shù)據(jù)就可以被替換了，這就是LRU(Least Recently Used) 。有的人可能會(huì)問(wèn)，有沒(méi)有更好的方法呢？比如說(shuō)看數(shù)據(jù)被使用的頻率，一些論文中就有利用數(shù)據(jù)頻率結(jié)合衰減因子的替換方法。雖然有很多復(fù)雜的算法，但是我們要意識(shí)到，判斷什么數(shù)據(jù)被替換也是需要占用計(jì)算資源的。而采用復(fù)雜的算法進(jìn)行替換往往會(huì)占用更多的時(shí)間來(lái)替換。實(shí)際上在80%以上的場(chǎng)景中，LRU算法就已經(jīng)足夠好了。所以絕大多數(shù)的替換算法都是LRU，它非常簡(jiǎn)單，非?？煽俊?br> 最后總結(jié)一下什么是Cache
· **Cache就是把數(shù)據(jù)放在身邊
**

· **Cache的寫入主要是備份和預(yù)取。
**

· Cache的替換策略主要是LRU
轉(zhuǎn)自：https://www.bittiger.io/blog/post/nhtsY2zPzcEvA4Nzv