前言
在計(jì)算機(jī)中且轨，計(jì)算機(jī)的指令都是由 CPU（Central Processing Unit，中央處理器）來執(zhí)行的，而指令執(zhí)行的過程中就會(huì)涉及到數(shù)據(jù)的讀取與寫入享甸。程序運(yùn)行過程中的臨時(shí)數(shù)據(jù)都是存儲(chǔ)在主存（物理內(nèi)存）中的箩绍，隨著cpu的速度變快孔庭，主存的速度就跟不上cpu的速度了，于是就有了“高速緩存”材蛛，從名字上面我們就可以知道圆到，這個(gè)緩存速度是很快的。這樣在程序的運(yùn)行過程中卑吭，會(huì)將運(yùn)算中需要的數(shù)據(jù)復(fù)制一份到緩存中芽淡，下次再使用的時(shí)候就可以直接從緩存中讀取，從而提高程序的運(yùn)行速度豆赏。后面cpu的速度越來越快吐绵，高速緩存的速度也跟不上cpu的速度的，于是就出現(xiàn)了二級(jí)緩存河绽，在有些計(jì)算機(jī)中甚至更多級(jí)的緩存己单。
同樣思想的就是在我們的應(yīng)用程序中，對于需要頻繁查詢而很少更新的數(shù)據(jù)耙饰，由于每次直接查詢數(shù)據(jù)庫非常耗時(shí)纹笼，所以通常的處理就是在第一次查詢數(shù)據(jù)庫之后，將這些數(shù)據(jù)放入緩存中苟跪，再次查詢的時(shí)候就可以在緩存中讀取廷痘，而不需要再次訪問數(shù)據(jù)庫，這樣不僅減少了數(shù)據(jù)庫的壓力件已，而且加速了數(shù)據(jù)的讀取速度笋额。
總之，CPU 緩存的出現(xiàn)就是為了讀取數(shù)據(jù)更快篷扩，解決cpu和內(nèi)存之間速度不匹配的問題兄猩。
上圖分別為一級(jí)緩存和多級(jí)緩存的示意圖。其中bus代表消息總線（ cpu 和計(jì)算機(jī)其他部件通信是通過消息總線來進(jìn)行的），藍(lán)色代表主存枢冤，綠色代表緩存鸠姨，黃色代表 cpu 。
本文首發(fā)于心安-XinAnzzZ 的個(gè)人博客淹真，轉(zhuǎn)載請注明出處~
局部性原理
有一個(gè)疑問就是讶迁，緩存中包含的只有主存中的部分?jǐn)?shù)據(jù)，那么緩存中不存在所需數(shù)據(jù)的情況就在所難免核蘸，那么就需要直接去主存中讀取巍糯。這樣一來，緩存的出現(xiàn)真的有意義嗎客扎？
局部性原理：
- 時(shí)間局部性
如果某個(gè)數(shù)據(jù)被訪問鳞贷，那么它很可能很快再次被訪問。
比如說在遞歸調(diào)用虐唠、循環(huán)調(diào)用等情況搀愧。
- 空間局部性
如果某個(gè)數(shù)據(jù)被訪問，那么它相鄰的數(shù)據(jù)很可能很快被訪問疆偿。
比如說循環(huán)遍歷一個(gè)數(shù)組咱筛。
由局部性原理我們可以發(fā)現(xiàn)，訪問某個(gè)數(shù)據(jù)杆故，那么很快就可能會(huì)再次訪問和訪問這塊數(shù)據(jù)相鄰的數(shù)據(jù)迅箩，所以將訪問的數(shù)據(jù)和它相鄰的數(shù)據(jù)加入到緩存中，以便不久的將來繼續(xù)使用处铛，這就是緩存出現(xiàn)的意義饲趋。
緩存一致性問題的出現(xiàn)
如上面提到的一樣，當(dāng)計(jì)算機(jī)加入了緩存撤蟆，cpu讀取數(shù)據(jù)的時(shí)候首先會(huì)從緩存讀取奕塑，如果緩存中不存在，則從主存讀取家肯，同時(shí)把該數(shù)據(jù)加入到緩存中龄砰，這樣下次再次使用的時(shí)候就可以直接從緩存中讀取。當(dāng)修改了某些數(shù)據(jù)讨衣，先把修改后的數(shù)據(jù)寫入到緩存中换棚，然后再刷到主存中，以此來提高效率反镇。
這樣的過程在單線程的環(huán)境下是不會(huì)出現(xiàn)問題的固蚤，但是在多線程環(huán)境下就會(huì)出現(xiàn)問題，現(xiàn)在的計(jì)算機(jī)幾乎都是多個(gè)核心的歹茶，多個(gè)線程運(yùn)行在不同的核心中夕玩，每個(gè)核心都有自己的緩存你弦。這時(shí)就會(huì)出現(xiàn)多個(gè)cpu同時(shí)修改了同一個(gè)數(shù)據(jù)的問題，這就是著名的緩存一致性問題风秤。
早期cpu中鳖目，為了解決緩存一致性問題扮叨，計(jì)算機(jī)廠商們通過在消息總線上加鎖來解決的缤弦，也就是說同時(shí)只有一個(gè)cpu能操作同一塊數(shù)據(jù)。這樣的后果就是彻磁，加鎖期間其他cpu無法訪問內(nèi)存碍沐，導(dǎo)致效率低下，因此出現(xiàn)了第二種解決方案衷蜓，就是通過緩存一致性協(xié)議來解決緩存一致性問題累提。
緩存一致性協(xié)議（MESI）
MESI是取自緩存行（Cache line，緩存中存儲(chǔ)數(shù)據(jù)的單元）中數(shù)據(jù)的四種狀態(tài)的英文首字母磁浇，緩存行中數(shù)據(jù)具有四種狀態(tài)斋陪，它們分別是：
- Modified（修改）：數(shù)據(jù)有效，數(shù)據(jù)被修改了置吓，和內(nèi)存中數(shù)據(jù)不一致无虚，數(shù)據(jù)只存在于本Cache中。
- Exclusive（獨(dú)享）：數(shù)據(jù)有效衍锚，數(shù)據(jù)和內(nèi)存中的數(shù)據(jù)一致友题，數(shù)據(jù)只存在于本Cache中。
- Shared（共享）：數(shù)據(jù)有效戴质，數(shù)據(jù)和內(nèi)存中的數(shù)據(jù)一致度宦，數(shù)據(jù)存在多個(gè)Cache中。
- Invalid（無效）：數(shù)據(jù)無效告匠，一旦數(shù)據(jù)被標(biāo)記為無效戈抄，那效果就等同于它從來沒被加載到緩存中。
這四種狀態(tài)之間的轉(zhuǎn)化晦澀難懂后专，所以筆者參考了CSDN博主陌小北zzZ的文章《緩存一致性協(xié)議》呛凶，覺得這個(gè)博主舉得例子非常的生動(dòng)，所以這里借用一下行贪。
舉個(gè)栗子
我們以github為例來講解緩存一致性協(xié)議漾稀。我們的項(xiàng)目存儲(chǔ)在github，那么項(xiàng)目就等于計(jì)算機(jī)中的“數(shù)據(jù)”建瘫，github等于“主存”崭捍。假設(shè)項(xiàng)目組有A、B啰脚、C殷蛇、D四個(gè)人实夹，也就是四個(gè)“cpu”，每個(gè)人都有一臺(tái)計(jì)算機(jī)粒梦，也就是每個(gè)人都有自己的“緩存”亮航。然后我們需要把項(xiàng)目從“主存”github上面拉取到本地計(jì)算機(jī)，也就是“緩存”中匀们。
- 初始狀態(tài)下缴淋，每個(gè)人的計(jì)算機(jī)中都沒有項(xiàng)目，也就是緩存都為空泄朴。
- A同學(xué)把項(xiàng)目拉取到了本地重抖，此時(shí)A的緩存中有了項(xiàng)目，且與遠(yuǎn)程倉庫保持一致祖灰，也就是說只有A的緩存中的存在數(shù)據(jù)钟沛，并且與主存數(shù)據(jù)保持一致，此時(shí)A獨(dú)享數(shù)據(jù)局扶，就是Exclusive恨统。
- B、C三妈、D同學(xué)也把項(xiàng)目拉取到了本地畜埋，此時(shí)多個(gè)緩存中存在同一份數(shù)據(jù)，并且和主存數(shù)據(jù)一致沈跨，此時(shí)大家共享數(shù)據(jù)由捎，就是Shared。
- A同學(xué)進(jìn)行了代碼修改饿凛，此時(shí)狞玛，A同學(xué)就告訴其他同學(xué)，代碼被我改過了涧窒，你們的數(shù)據(jù)都是失效的數(shù)據(jù)心肪，也就是Invalid。而A同學(xué)的數(shù)據(jù)就是Modified纠吴。
- A同學(xué)修改代碼之后提交了代碼硬鞍，此時(shí)只有A同學(xué)的數(shù)據(jù)和主存數(shù)據(jù)一致，所以數(shù)據(jù)從Modified變?yōu)榱霜?dú)享Exclusive戴已。
- 其他同學(xué)需要看A同學(xué)修改的代碼固该，所以拉取了最新的代碼，此時(shí)所有人數(shù)據(jù)和主存數(shù)據(jù)一致糖儡，都成了共享Shared伐坏。
也就是說，當(dāng)數(shù)據(jù)被修改握联，那么其他cpu緩存中的數(shù)據(jù)都會(huì)失效（這里面其實(shí)有一個(gè)監(jiān)聽的機(jī)制桦沉，讀寫操作都會(huì)通知到其他 cpu ）變成Invalid每瞒，被修改的那一份變?yōu)镸odified。當(dāng)其他 cpu 需要讀取這份數(shù)據(jù)纯露，由于這份數(shù)據(jù)是Modified狀態(tài)剿骨，所以需要先將該數(shù)據(jù)寫入到主存，寫入之后就成了獨(dú)享狀態(tài)埠褪，這時(shí)其他cpu就可以讀取這份數(shù)據(jù)浓利，成為共享。
只有當(dāng)緩存段處于 E 或 M 狀態(tài)時(shí)组橄，處理器才能去寫它（往緩存中寫入）荞膘，也就是說只有這兩種狀態(tài)下罚随，處理器是獨(dú)占這個(gè)緩存段的玉工。當(dāng)處理器想寫某個(gè)緩存段時(shí)，如果它沒有獨(dú)占權(quán)淘菩，它必須先發(fā)送一條“我要獨(dú)占權(quán)”的請求給總線遵班，這會(huì)通知其他處理器（使用的是一種類似廣播的形式來進(jìn)行通訊），把它們擁有的同一緩存段的拷貝失效（如果它們有的話）潮改。只有在獲得獨(dú)占權(quán)后狭郑，處理器才能開始修改數(shù)據(jù)——并且此時(shí)，這個(gè)處理器知道汇在，這個(gè)緩存段只有一份拷貝翰萨，在我自己的緩存里，所以不會(huì)有任何沖突糕殉。
反之亩鬼，如果有其他處理器想讀取這個(gè)緩存段，獨(dú)占或已修改的緩存段必須先回到“共享”狀態(tài)阿蝶。如果是已修改的緩存段雳锋，那么還要先把內(nèi)容回寫到內(nèi)存中。
狀態(tài)遷移圖
對于數(shù)據(jù)的讀寫也有四種操作羡洁，分別是local read（從緩存中讀如韫）、local write（寫入到緩存）筑煮、remote read（讀取其他 cpu 的緩存）辛蚊、remote write（寫入到其他 cpu 的緩存中）。當(dāng)內(nèi)核需要訪問的數(shù)據(jù)不在本Cache中真仲，而其它Cache有這份數(shù)據(jù)的備份時(shí)袋马，本Cache既可以從內(nèi)存中導(dǎo)入數(shù)據(jù)，也可以從其它Cache中導(dǎo)入數(shù)據(jù)袒餐，不同的處理器會(huì)有不同的選擇飞蛹。MESI協(xié)議為了使自己更加通用谤狡，沒有定義這些細(xì)節(jié)，只定義了狀態(tài)之間的遷移卧檐。
下面是MESI協(xié)議狀態(tài)遷移圖：
MESI協(xié)議中數(shù)據(jù)的狀態(tài)有4種墓懂，引起狀態(tài)變化的操作也有四種，所以理解MESI協(xié)議就需要對這16種狀態(tài)轉(zhuǎn)換的情況理解清楚霉囚。
多核系統(tǒng)中捕仔，每個(gè)cpu都有自己的緩存，他們共享同一個(gè)主內(nèi)存盈罐。緩存的目的就是減少讀取共享主存的次數(shù)榜跌，數(shù)據(jù)除了在I狀態(tài)下，都是可以滿足讀請求的盅粪。如上圖：
我們先看local read钓葫，也就是綠色的線，在M票顾、E础浮、S狀態(tài)下，三條綠色的線經(jīng)過本地讀取之后又指向了自身奠骄。也就是說共享豆同、獨(dú)享、修改狀態(tài)下含鳞，cpu直接讀取緩存中的數(shù)據(jù)影锈，而不會(huì)導(dǎo)致數(shù)據(jù)狀態(tài)的變化。當(dāng)在I狀態(tài)下時(shí)蝉绷，等同于緩存中沒有這塊數(shù)據(jù)的緩存鸭廷，那么cpu就會(huì)把主存的數(shù)據(jù)復(fù)制到緩存，使其變?yōu)楠?dú)享或者共享潜必。
然后是local write靴姿，紅色的線。當(dāng)數(shù)據(jù)在任意狀態(tài)下時(shí)磁滚，cpu往緩存中寫入數(shù)據(jù)的時(shí)候都會(huì)是數(shù)據(jù)變?yōu)镸狀態(tài)佛吓。
再看一下remote read，就是本緩存中沒有垂攘，從其他cpu的緩存中讀取维雇，對應(yīng)藍(lán)色的線。S狀態(tài)下晒他，讀取之后狀態(tài)不變吱型，M、E狀態(tài)下陨仅，都會(huì)變?yōu)楣蚕怼?/p>
最后看remote write津滞，將數(shù)據(jù)寫入到其他cpu的緩存铝侵，黃色的線。除了I狀態(tài)触徐，其他狀態(tài)下都可以執(zhí)行remote write操作咪鲜，并且寫入后，數(shù)據(jù)全部失效撞鹉。
下面的表格詳細(xì)的表示了數(shù)據(jù)狀態(tài)遷移的過程:
