學(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ō)的。

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

局部性分類

局部性有兩種基本的分類， 時(shí)間局部性 和 空間局部性 ，按Wikipedia的資料，可以分為以下五類，其實(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)用或類檢測(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í)候你寫出的java代碼執(zhí)行效率會(huì)比C++的高。

CopyOnWrite

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)程單獨(dú)拷貝一份。出于效率考慮，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來(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ù)的重要性。這兩種方法差不多是類似的，都是優(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 鄭雨迪