摘要：基于局部性原理，計(jì)算機(jī)處理器在設(shè)計(jì)時(shí)做了各種優(yōu)化，比如現(xiàn)代的多級(jí)分支預(yù)測(cè)有良好局部性的程序比局部性差的程序運(yùn)行得更快。目前計(jì)算機(jī)設(shè)計(jì)中，都是以塊頁為單位管理調(diào)度存儲(chǔ)，其實(shí)就是在利用空間局部性來優(yōu)化性能。

　　學(xué)過計(jì)算機(jī)底層原理、了解過很多架構(gòu)設(shè)計(jì)或者是做過優(yōu)化的同學(xué)，應(yīng)該很熟悉局部性原理。即便是非計(jì)算機(jī)行業(yè)的人，在做各種調(diào)優(yōu)、提效時(shí)也不得不考慮到局部性，只不過他們不常用局部性一詞。如果抽象程度再高一些，甚至可以說地球、生命、萬事萬物都是局部性的產(chǎn)物，因?yàn)檫@些都是宇宙中熵分布布局、局部的熵低導(dǎo)致的，如果宇宙中處處?kù)匾恢?，有的只有一篇混沌?！　?br>　　所以什么是 局部性 ？這是一個(gè)常用的計(jì)算機(jī)術(shù)語，是指處理器在訪問某些數(shù)據(jù)時(shí)短時(shí)間內(nèi)存在重復(fù)訪問，某些數(shù)據(jù)或者位置訪問的概率極大，大多數(shù)時(shí)間只訪問_局部_的數(shù)據(jù)?；诰植啃栽恚?jì)算機(jī)處理器在設(shè)計(jì)時(shí)做了各種優(yōu)化，比如現(xiàn)代CPU的多級(jí)Cache、分支預(yù)測(cè)…… 有良好局部性的程序比局部性差的程序運(yùn)行得更快。雖然局部性一詞源于計(jì)算機(jī)設(shè)計(jì)，但在當(dāng)今分布式系統(tǒng)、互聯(lián)網(wǎng)技術(shù)里也不乏局部性，比如像用redis這種memcache來減輕后端的壓力，CDN做素材分發(fā)減少帶寬占用率……
　　局部性的本質(zhì)是什么？其實(shí)就是概率的不均等，這個(gè)宇宙中，很多東西都不是平均分布的，平均分布是概率論中幾何分布的一種特殊形式，非常簡(jiǎn)單，但世界就是沒這么簡(jiǎn)單。我們更長(zhǎng)聽到的發(fā)布叫做高斯發(fā)布，同時(shí)也被稱為正態(tài)分布，因?yàn)樗褪钦顟B(tài)下的概率發(fā)布，起概率圖如下，但這個(gè)也不是今天要說的。

　　其實(shí)有很多情況，很多事物有很強(qiáng)的頭部集中現(xiàn)象，可以用概率論中的泊松分布來刻畫，這就是局部性在概率學(xué)中的刻畫形式。


　　上面分別是泊松分布的示意圖和概率計(jì)算公式，$lambda$ 表示單位時(shí)間(或單位面積)內(nèi)隨機(jī)事件的平均發(fā)生次數(shù)，$e$表示自然常數(shù)2.71828..，k表示事件發(fā)生的次數(shù)。要注意在刻畫局部性時(shí)$lambda$表示不命中高頻數(shù)據(jù)的頻度，$lambda$越小，頭部集中現(xiàn)象越明顯。

　　局部性有兩種基本的分類， 時(shí)間局部性 和 空間局部性 ，按Wikipedia的資料，可以分為以下五類，其實(shí)有些就是時(shí)間局部性和空間局部性的特殊情況。

時(shí)間局部性(Temporal locality):

　　如果某個(gè)信息這次被訪問，那它有可能在不久的未來被多次訪問。時(shí)間局部性是空間局部性訪問地址一樣時(shí)的一種特殊情況。這種情況下，可以把常用的數(shù)據(jù)加cache來優(yōu)化訪存。

空間局部性(Spatial locality):

　　如果某個(gè)位置的信息被訪問，那和它相鄰的信息也很有可能被訪問到。 這個(gè)也很好理解，我們大部分情況下代碼都是順序執(zhí)行，數(shù)據(jù)也是順序訪問的。

內(nèi)存局部性(Memory locality):

訪問內(nèi)存時(shí)，大概率會(huì)訪問連續(xù)的塊，而不是單一的內(nèi)存地址，其實(shí)就是空間局部性在內(nèi)存上的體現(xiàn)。目前計(jì)算機(jī)設(shè)計(jì)中，都是以塊/頁為單位管理調(diào)度存儲(chǔ)，其實(shí)就是在利用空間局部性來優(yōu)化性能。

分支局部性(Branch locality)

　　這個(gè)又被稱為順序局部性，計(jì)算機(jī)中大部分指令是順序執(zhí)行，順序執(zhí)行和非順序執(zhí)行的比例大致是5:1，即便有if這種選擇分支，其實(shí)大多數(shù)情況下某個(gè)分支都是被大概率選中的，于是就有了CPU的分支預(yù)測(cè)優(yōu)化。

等距局部性(Equidistant locality)

　　等距局部性是指如果某個(gè)位置被訪問，那和它相鄰等距離的連續(xù)地址極有可能會(huì)被訪問到，它位于空間局部性和分支局部性之間。 舉個(gè)例子，比如多個(gè)相同格式的數(shù)據(jù)數(shù)組，你只取其中每個(gè)數(shù)據(jù)的一部分字段，那么他們可能在內(nèi)存中地址距離是等距的，這個(gè)可以通過簡(jiǎn)單的線性預(yù)測(cè)就預(yù)測(cè)是未來訪問的位置。

　　計(jì)算機(jī)領(lǐng)域關(guān)于局部性非常多的利用，有很多你每天都會(huì)用到，但可能并沒有察覺，另外一些可能離你會(huì)稍微遠(yuǎn)一些，接下來我們舉幾個(gè)例子來深入了解下局部性的應(yīng)用。

　　上圖來自極客時(shí)間徐文浩的《深入淺出計(jì)算機(jī)組成原理》，我們以目前常見的普通家用電腦為例 ，分別說下上圖各級(jí)存儲(chǔ)的大小和訪問速度，數(shù)據(jù)來源于https://people.eecs.berkeley.edu/~rcs/research/interactive_latency.html。

　　從最快的L1 Cache到最慢的HDD，其兩者的訪存時(shí)間差距達(dá)到了6個(gè)數(shù)量級(jí)，即便是和內(nèi)存比較，也有幾百倍的差距。舉個(gè)例子，如果CPU在運(yùn)算是直接從內(nèi)存中讀取指令和數(shù)據(jù)，執(zhí)行一條指令0.3ns，然后從內(nèi)存讀下一條指令，等120ns，這樣CPU 99%計(jì)算時(shí)間都會(huì)被浪費(fèi)掉。但就是因?yàn)橛芯植啃缘拇嬖?，每一層都只有少部分?jǐn)?shù)據(jù)會(huì)被頻繁訪問，我們可以把這部分?jǐn)?shù)據(jù)從底層存儲(chǔ)挪到高層存儲(chǔ)，可以降低大部分的數(shù)據(jù)讀取時(shí)間。
　　
　　可能有些人好奇，為什么不把L1 緩存做的大點(diǎn)，像內(nèi)存那么大，直接替代掉內(nèi)存，不是性能更好嗎？雖然是這樣，但是L1 Cache單位價(jià)格要比內(nèi)存單位的價(jià)格貴好多(大概差200倍)，有興趣可以了解下DRAM和SRAM。
　　我們可以通過編寫高速緩存友好的代碼邏輯來提升我們的代碼性能，有兩個(gè)基本方法 。

讓最常見的情況運(yùn)行的快，程序大部分的運(yùn)行實(shí)際都花在少了核心函數(shù)上，而這些函數(shù)把大部分時(shí)間都花在少量循環(huán)上，把注意力放在這些代碼上。

讓每個(gè)循環(huán)內(nèi)緩存不命中率最小。比如盡量不要列遍歷二維數(shù)組。

　　MemCache在大型網(wǎng)站架構(gòu)中經(jīng)?？吹健B一般公司都會(huì)用mysql，即便是做了分庫(kù)分表，數(shù)據(jù)數(shù)據(jù)庫(kù)單機(jī)的壓力還是非常大的，這時(shí)候因?yàn)榫植啃缘拇嬖?，可能很多?shù)據(jù)會(huì)被頻繁訪問，這些數(shù)據(jù)就可以被cache到像redis這種memcache中，當(dāng)redis查不到數(shù)據(jù)，再去查db，并寫入redis。
　　因?yàn)閞edis的水平擴(kuò)展能力和簡(jiǎn)單查詢能力要比mysql強(qiáng)多了，查起來也快。所以這種架構(gòu)設(shè)計(jì)有幾個(gè)好處：

加快了數(shù)據(jù)查詢的平均速度。

大幅度減少DB的壓力。

　　CDN的全稱是Content Delivery Network，即內(nèi)容分發(fā)網(wǎng)絡(luò)(圖片來自百度百科) 。CDN常用于大的素材下發(fā)，比如圖片和視頻，你在淘寶上打開一個(gè)圖片，這個(gè)圖片其實(shí)會(huì)就近從CDN機(jī)房拉去數(shù)據(jù)，而不是到阿里的機(jī)房拉數(shù)據(jù)，可以減少阿里機(jī)房的出口帶寬占用，也可以減少用戶加載素材的等待時(shí)間。

　　CDN在互聯(lián)網(wǎng)中被大規(guī)模使用，像視頻、直播網(wǎng)站，電商網(wǎng)站，甚至是12306都在使用，這種設(shè)計(jì)對(duì)公司可以節(jié)省帶寬成本，對(duì)用戶可以減少素材加載時(shí)間，提升用戶體驗(yàn)?？吹竭@，有沒有發(fā)現(xiàn)，CDN的邏輯和Memcache的使用很類似，你可以直接當(dāng)他是一個(gè)互聯(lián)網(wǎng)版的cache優(yōu)化。

　　JIT全稱是Just-in-time Compiler，中文名為即時(shí)編譯器，是一種Java運(yùn)行時(shí)的優(yōu)化。Java的運(yùn)行方式和C++不太一樣，因?yàn)闉榱藢?shí)現(xiàn)write once, run anywhere的跨平臺(tái)需求，Java實(shí)現(xiàn)了一套字節(jié)碼機(jī)制，所有的平臺(tái)都可以執(zhí)行同樣的字節(jié)碼，執(zhí)行時(shí)有該平臺(tái)的JVM將字節(jié)碼實(shí)時(shí)翻譯成該平臺(tái)的機(jī)器碼再執(zhí)行。問題在于字節(jié)碼每次執(zhí)行都要翻譯一次，會(huì)很耗時(shí)。

　　圖片來自鄭雨迪Introduction to Graal ，Java 7引入了tiered compilation的概念，綜合了C1的高啟動(dòng)性能及C2的高峰值性能。這兩個(gè)JIT compiler以及interpreter將HotSpot的執(zhí)行方式劃分為五個(gè)級(jí)別：

level 0：interpreter解釋執(zhí)行

level 1：C1編譯，無profiling

level 2：C1編譯，僅方法及循環(huán)back-edge執(zhí)行次數(shù)的profiling

level 3：C1編譯，除level 2中的profiling外還包括branch（針對(duì)分支跳轉(zhuǎn)字節(jié)碼）及receiver type（針對(duì)成員方法調(diào)用或類檢測(cè)，如checkcast，instnaceof，aastore字節(jié)碼）的profiling

level 4：C2編譯

　　通常情況下，一個(gè)方法先被解釋執(zhí)行（level 0），然后被C1編譯（level 3），再然后被得到profile數(shù)據(jù)的C2編譯（level 4）。如果編譯對(duì)象非常簡(jiǎn)單，虛擬機(jī)認(rèn)為通過C1編譯或通過C2編譯并無區(qū)別，便會(huì)直接由C1編譯且不插入profiling代碼（level 1）。在C1忙碌的情況下，interpreter會(huì)觸發(fā)profiling，而后方法會(huì)直接被C2編譯；在C2忙碌的情況下，方法則會(huì)先由C1編譯并保持較少的profiling（level 2），以獲取較高的執(zhí)行效率（與3級(jí)相比高30%）。
　　這里將少部分字節(jié)碼實(shí)時(shí)編譯成機(jī)器碼的方式，可以提升java的運(yùn)行效率。可能有人會(huì)問，為什么不預(yù)先將所有的字節(jié)碼編譯成機(jī)器碼，執(zhí)行的時(shí)候不是更快更省事嗎？首先機(jī)器碼是和平臺(tái)強(qiáng)相關(guān)的，linux和unix就可能有很大的不同，何況是windows，預(yù)編譯會(huì)讓java失去夸平臺(tái)這種優(yōu)勢(shì)。 其次，即時(shí)編譯可以讓jvm拿到更多的運(yùn)行時(shí)數(shù)據(jù)，根據(jù)這些數(shù)據(jù)可以對(duì)字節(jié)碼做更深層次的優(yōu)化，這些是C++這種預(yù)編譯語言做不到的，所以有時(shí)候你寫出的java代碼執(zhí)行效率會(huì)比C++的高。

　　CopyOnWrite寫時(shí)復(fù)制，最早應(yīng)該是源自linux系統(tǒng)，linux中在調(diào)用fork() 生成子進(jìn)程時(shí)，子進(jìn)程應(yīng)該擁有和父進(jìn)程一樣的指令和數(shù)據(jù)，可能子進(jìn)程會(huì)修改一些數(shù)據(jù)，為了避免污染父進(jìn)程的數(shù)據(jù)，所以要給子進(jìn)程多帶帶拷貝一份。出于效率考慮，fork時(shí)并不會(huì)直接復(fù)制，而是等到子進(jìn)程的各段數(shù)據(jù)需要寫入才會(huì)復(fù)制一份給子進(jìn)程，故此得名 寫時(shí)復(fù)制 。
　　在計(jì)算機(jī)的世界里，讀寫的分布也是有很大的局部性的，大多數(shù)情況下讀遠(yuǎn)大于寫， 寫時(shí)復(fù)制 的方式，可以減少大量不必要的復(fù)制，提升性能。 另外這種方式也不僅僅是用在linux內(nèi)核中，java的concurrent包中也提供了CopyOnWriteArrayList CopyOnWriteArraySet。像Spark中的RDD也是用CopyOnWrite來減少不必要的RDD生成。
　　

　　上面列舉了那么多局部性的應(yīng)用，其實(shí)還有很多很多，我只是列舉出了幾個(gè)我所熟知的應(yīng)用，雖然上面這些例子，我們都利用局部性得到了能效、成本上的提升。但有些時(shí)候它也會(huì)給我們帶來一些不好的體驗(yàn)，更多的時(shí)候它其實(shí)就是一把雙刃劍，我們?nèi)绾巫R(shí)別局部性，利用它好的一面，避免它壞的一面？

　　文章開頭也說過，局部性其實(shí)就是一種概率的不均等性，所以只要概率不均等就一定存在局部性，因?yàn)楹芏鄷r(shí)候這種概率不均太明顯了，非常好識(shí)別出來，然后我們對(duì)大頭做相應(yīng)的優(yōu)化就行了。但可能有些時(shí)候這種概率不均需要做很詳細(xì)的計(jì)算才能發(fā)現(xiàn)，最后還得核對(duì)成本才能考慮是否值得去做，這種需要具體問題具體分析了。 　　　
　　如何識(shí)別局部性，很簡(jiǎn)單，看概率分布曲線，只要不是一條水平的直線，就一定存在局部性?！　?/p> 利用

　　發(fā)現(xiàn)局部性之后對(duì)我們而言是如何利用好這些局部性，用得好提升性能、節(jié)約資源，用不好局部性就會(huì)變成阻礙。而且不光是在計(jì)算機(jī)領(lǐng)域，局部性在非計(jì)算機(jī)領(lǐng)域也可以利用。
##### 性能優(yōu)化
　　上面列舉到的很多應(yīng)用其實(shí)就是通過局部性做一些優(yōu)化，雖然這些都是別人已經(jīng)做好的，但是我們也可以參考其設(shè)計(jì)思路。
　　恰巧最近我也在做我們一個(gè)java服務(wù)的性能優(yōu)化，利用jstack、jmap這些java自帶的分析工具，找出其中最吃cpu的線程，找出最占內(nèi)存的對(duì)象。我發(fā)現(xiàn)有個(gè)redis數(shù)據(jù)查詢有問題，因?yàn)槊看涡枰獙⒁粋€(gè)大字符串解析很多個(gè)鍵值對(duì)，中間會(huì)產(chǎn)生上千個(gè)臨時(shí)字符串，還需要將字符串parse成long和double。redis數(shù)據(jù)太多，不可能完全放的內(nèi)存里，但是這里的key有明顯的局部性，大量的查詢只會(huì)集中在頭部的一些key上，我用一個(gè)LRU Cache緩存頭部數(shù)據(jù)的解析結(jié)果，就可以減少大量的查redis+解析字符串的過程了。
　　另外也發(fā)現(xiàn)有個(gè)代碼邏輯，每次請(qǐng)求會(huì)被重復(fù)執(zhí)行幾千次，耗費(fèi)大量cpu，這種熱點(diǎn)代碼，簡(jiǎn)單幾行改動(dòng)減少了不必要的調(diào)用，最終減少了近50%的CPU使用。
　　

非計(jì)算機(jī)領(lǐng)域

　　《高能人士的七個(gè)習(xí)慣》里提到了一種工作方式，將任務(wù)劃分為重要緊急、不重要但緊急、重要但不緊急、不重要不緊急四種，這種劃分方式其實(shí)就是按單位時(shí)間的重要度排序的，按單位時(shí)間的重要度越高收益越大?！禩he Effective Engineer》里直接用leverage(杠桿率)來衡量每個(gè)任務(wù)的重要性。這兩種方法差不多是類似的，都是優(yōu)先做高收益率的事情，可以明顯提升你的工作效率。
　　這就是工作中收益率的局部性導(dǎo)致的，只要少數(shù)事情有比較大的收益，才值得去做。還有一個(gè)很著名的法則__82法則__，在很多行業(yè)、很多領(lǐng)域都可以套用，_80%的xxx來源于20%的xxx_ ，80%的工作收益來源于20%的工作任務(wù)，局部性給我們的啟示“永遠(yuǎn)關(guān)注最重要的20%” 。

　　上面我們一直在講如何通過局部性來提升性能，但有時(shí)候我們需要避免局部性的產(chǎn)生。 比如在大數(shù)據(jù)運(yùn)算時(shí)，時(shí)常會(huì)遇到數(shù)據(jù)傾斜、數(shù)據(jù)熱點(diǎn)的問題，這就是數(shù)據(jù)分布的局部性導(dǎo)致的，數(shù)據(jù)傾斜往往會(huì)導(dǎo)致我們的數(shù)據(jù)計(jì)算任務(wù)耗時(shí)非常長(zhǎng)，數(shù)據(jù)熱點(diǎn)會(huì)導(dǎo)致某些單節(jié)點(diǎn)成為整個(gè)集群的性能瓶頸，但大部分節(jié)點(diǎn)卻很閑，這些都是我們需要極力避免的。
　　一般我們解決熱點(diǎn)和數(shù)據(jù)切斜的方式都是提供過重新hash打亂整個(gè)數(shù)據(jù)讓數(shù)據(jù)達(dá)到均勻分布，當(dāng)然有些業(yè)務(wù)邏輯可能不會(huì)讓你隨意打亂數(shù)據(jù)，這時(shí)候就得具體問題具體分析了。感覺在大數(shù)據(jù)領(lǐng)域，局部性極力避免，當(dāng)然如果沒法避免你就得通過其他方式來解決了，比如HDFS中小文件單節(jié)點(diǎn)讀的熱點(diǎn)，可以通過減少加副本緩解。其本質(zhì)上沒有避免局部性，只增加資源緩解熱點(diǎn)了，據(jù)說微博為應(yīng)對(duì)明星出軌Redis集群也是采取這種加資源的方式。
　

維基百科局部性原理

《計(jì)算機(jī)組成與設(shè)計(jì)》 David A.Patterson / John L.Hennessy

《深入淺出計(jì)算機(jī)組成原理》 極客時(shí)間 徐文浩

《深入理解計(jì)算機(jī)系統(tǒng)》 Randal E.Bryant / David O"Hallaron 龔奕利 / 雷迎春(譯)

Interactive latencies

Introduction to Graal 鄭雨迪