學(xué)過(guò)計(jì)算機(jī)底層原理、了解過(guò)很多架構(gòu)設(shè)計(jì)或者是做過(guò)優(yōu)化的同學(xué)杆麸，應(yīng)該很熟悉局部性原理搁进。即便是非計(jì)算機(jī)行業(yè)的人，在做各種調(diào)優(yōu)昔头、提效時(shí)也不得不考慮到局部性饼问，只不過(guò)他們不常用局部性一詞。如果抽象程度再高一些揭斧，甚至可以說(shuō)地球莱革、生命、萬(wàn)事萬(wàn)物都是局部性的產(chǎn)物讹开，因?yàn)檫@些都是宇宙中熵分布布局盅视、局部的熵低導(dǎo)致的，如果宇宙中處處?kù)匾恢碌┩颍械闹挥幸黄煦缒只鳌！　?br> 　　所以什么是 局部性 成艘？這是一個(gè)常用的計(jì)算機(jī)術(shù)語(yǔ)赏半，是指處理器在訪問(wèn)某些數(shù)據(jù)時(shí)短時(shí)間內(nèi)存在重復(fù)訪問(wèn)，某些數(shù)據(jù)或者位置訪問(wèn)的概率極大淆两，大多數(shù)時(shí)間只訪問(wèn)局部的數(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來(lái)減輕后端的壓力，CDN做素材分發(fā)減少帶寬占用率……
　　局部性的本質(zhì)是什么性含？其實(shí)就是概率的不均等洲赵，這個(gè)宇宙中，很多東西都不是平均分布的商蕴，平均分布是概率論中幾何分布的一種特殊形式叠萍，非常簡(jiǎn)單，但世界就是沒(méi)這么簡(jiǎn)單绪商。我們更長(zhǎng)聽(tīng)到的發(fā)布叫做高斯發(fā)布苛谷，同時(shí)也被稱為正態(tài)分布，因?yàn)樗褪钦顟B(tài)下的概率發(fā)布格郁，起概率圖如下腹殿，但這個(gè)也不是今天要說(shuō)的独悴。

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

局部性分類(lèi)

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

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

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

空間局部性(Spatial locality):

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

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

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

分支局部性(Branch locality)

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

等距局部性(Equidistant locality)

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

實(shí)際應(yīng)用

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

計(jì)算機(jī)存儲(chǔ)層級(jí)結(jié)構(gòu)

極客時(shí)間

在這里插入圖片描述

1. 讓最常見(jiàn)的情況運(yùn)行的快霎箍，程序大部分的運(yùn)行實(shí)際都花在少了核心函數(shù)上奇钞，而這些函數(shù)把大部分時(shí)間都花在少量循環(huán)上，把注意力放在這些代碼上漂坏。
2. 讓每個(gè)循環(huán)內(nèi)緩存不命中率最小景埃。比如盡量不要列遍歷二維數(shù)組。

MemCache

在這里插入圖片描述

1. 加快了數(shù)據(jù)查詢的平均速度涨椒。
2. 大幅度減少DB的壓力。

CDN

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

在這里插入圖片描述

Java JIT

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í)行几睛。問(wèn)題在于字節(jié)碼每次執(zhí)行都要翻譯一次房轿，會(huì)很耗時(shí)。
　　

在這里插入圖片描述

• level 0：interpreter解釋執(zhí)行
• level 1：C1編譯焕济，無(wú)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)用或類(lèi)檢測(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)為通過(guò)C1編譯或通過(guò)C2編譯并無(wú)區(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ì)問(wèn)辨赐，為什么不預(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ù)編譯語(yǔ)言做不到的，所以有時(shí)候你寫(xiě)出的java代碼執(zhí)行效率會(huì)比C++的高钥星。

CopyOnWrite

CopyOnWrite寫(xiě)時(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)程單獨(dú)拷貝一份缕探。出于效率考慮，fork時(shí)并不會(huì)直接復(fù)制还蹲，而是等到子進(jìn)程的各段數(shù)據(jù)需要寫(xiě)入才會(huì)復(fù)制一份給子進(jìn)程爹耗，故此得名 寫(xiě)時(shí)復(fù)制 。
　　在計(jì)算機(jī)的世界里谜喊，讀寫(xiě)的分布也是有很大的局部性的鲸沮，大多數(shù)情況下讀遠(yuǎn)大于寫(xiě)， 寫(xiě)時(shí)復(fù)制 的方式锅论，可以減少大量不必要的復(fù)制讼溺，提升性能。 另外這種方式也不僅僅是用在linux內(nèi)核中最易，java的concurrent包中也提供了CopyOnWriteArrayList CopyOnWriteArraySet怒坯。像Spark中的RDD也是用CopyOnWrite來(lái)減少不必要的RDD生成。

處理

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

識(shí)別

文章開(kāi)頭也說(shuō)過(guò)呀舔，局部性其實(shí)就是一種概率的不均等性，所以只要概率不均等就一定存在局部性扩灯，因?yàn)楹芏鄷r(shí)候這種概率不均太明顯了媚赖，非常好識(shí)別出來(lái)，然后我們對(duì)大頭做相應(yīng)的優(yōu)化就行了珠插。但可能有些時(shí)候這種概率不均需要做很詳細(xì)的計(jì)算才能發(fā)現(xiàn)惧磺，最后還得核對(duì)成本才能考慮是否值得去做，這種需要具體問(wèn)題具體分析了捻撑。 　　　
　　如何識(shí)別局部性磨隘，很簡(jiǎn)單，看概率分布曲線布讹，只要不是一條水平的直線琳拭，就一定存在局部性。

利用

發(fā)現(xiàn)局部性之后對(duì)我們而言是如何利用好這些局部性描验，用得好提升性能白嘁、節(jié)約資源，用不好局部性就會(huì)變成阻礙膘流。而且不光是在計(jì)算機(jī)領(lǐng)域絮缅，局部性在非計(jì)算機(jī)領(lǐng)域也可以利用。

性能優(yōu)化

上面列舉到的很多應(yīng)用其實(shí)就是通過(guò)局部性做一些優(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ù)查詢有問(wèn)題，因?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+解析字符串的過(guò)程了粥脚。
　　另外也發(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í)間的重要度越高收益越大州既∶涨ⅲ《The Effective Engineer》里直接用leverage(杠桿率)來(lái)衡量每個(gè)任務(wù)的重要性。這兩種方法差不多是類(lèi)似的吴叶，都是優(yōu)先做高收益率的事情阐虚，可以明顯提升你的工作效率。
　　這就是工作中收益率的局部性導(dǎo)致的蚌卤，只要少數(shù)事情有比較大的收益实束，才值得去做。還有一個(gè)很著名的法則82法則逊彭，在很多行業(yè)咸灿、很多領(lǐng)域都可以套用，80%的xxx來(lái)源于20%的xxx 侮叮，80%的工作收益來(lái)源于20%的工作任務(wù)避矢，局部性給我們的啟示“永遠(yuǎn)關(guān)注最重要的20%” 。

避免

上面我們一直在講如何通過(guò)局部性來(lái)提升性能囊榜，但有時(shí)候我們需要避免局部性的產(chǎn)生审胸。 比如在大數(shù)據(jù)運(yùn)算時(shí)，時(shí)常會(huì)遇到數(shù)據(jù)傾斜锦聊、數(shù)據(jù)熱點(diǎn)的問(wè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ù)切斜的方式都是提供過(guò)重新hash打亂整個(gè)數(shù)據(jù)讓數(shù)據(jù)達(dá)到均勻分布怎抛，當(dāng)然有些業(yè)務(wù)邏輯可能不會(huì)讓你隨意打亂數(shù)據(jù)卑吭，這時(shí)候就得具體問(wèn)題具體分析了。感覺(jué)在大數(shù)據(jù)領(lǐng)域马绝，局部性極力避免豆赏，當(dāng)然如果沒(méi)法避免你就得通過(guò)其他方式來(lái)解決了，比如HDFS中小文件單節(jié)點(diǎn)讀的熱點(diǎn)富稻，可以通過(guò)減少加副本緩解掷邦。其本質(zhì)上沒(méi)有避免局部性，只增加資源緩解熱點(diǎn)了椭赋，據(jù)說(shuō)微博為應(yīng)對(duì)明星出軌Redis集群也是采取這種加資源的方式抚岗。

參考資料

1. 維基百科局部性原理
2. 《計(jì)算機(jī)組成與設(shè)計(jì)》 David A.Patterson / John L.Hennessy
3. 《深入淺出計(jì)算機(jī)組成原理》 極客時(shí)間 徐文浩
4. 《深入理解計(jì)算機(jī)系統(tǒng)》 Randal E.Bryant / David O'Hallaron 龔奕利 / 雷迎春(譯)
5. Interactive latencies
6. Introduction to Graal 鄭雨迪