學過計算機底層原理、了解過很多架構設計或者是做過優化的同學，應該很熟悉局部性原理。即便是非計算機行業的人，在做各種調優、提效時也不得不考慮到局部性，隻不過他們不常用局部性一詞。如果抽象程度再高一些，甚至可以說地球、生命、萬事萬物都是局部性的産物，因為這些都是宇宙中熵分布布局、局部的熵低導緻的，如果宇宙中處處熵一緻，有的隻有一篇混沌。
是以什麼是 局部性 ？這是一個常用的計算機術語，是指處理器在通路某些資料時短時間記憶體在重複通路，某些資料或者位置通路的機率極大，大多數時間隻通路_局部_的資料。基于局部性原理，計算機處理器在設計時做了各種優化，比如現代CPU的多級Cache、分支預測…… 有良好局部性的程式比局部性差的程式運作得更快。雖然局部性一詞源于計算機設計，但在當今分布式系統、網際網路技術裡也不乏局部性，比如像用redis這種memcache來減輕後端的壓力，CDN做素材分發減少帶寬占用率……
局部性的本質是什麼？其實就是機率的不均等，這個宇宙中，很多東西都不是平均分布的，平均分布是機率論中幾何分布的一種特殊形式，非常簡單，但世界就是沒這麼簡單。我們更長聽到的釋出叫做高斯釋出，同時也被稱為正态分布，因為它就是正常狀态下的機率釋出，起機率圖如下，但這個也不是今天要說的。
局部性分類
局部性有兩種基本的分類， 時間局部性 和 空間局部性 ，按Wikipedia的資料，可以分為以下五類，其實有些就是時間局部性和空間局部性的特殊情況。
時間局部性(Temporal locality):
如果某個資訊這次被通路，那它有可能在不久的未來被多次通路。時間局部性是空間局部性通路位址一樣時的一種特殊情況。這種情況下，可以把常用的資料加cache來優化訪存。
空間局部性(Spatial locality):
如果某個位置的資訊被通路，那和它相鄰的資訊也很有可能被通路到。 這個也很好了解，我們大部分情況下代碼都是順序執行，資料也是順序通路的。
記憶體局部性(Memory locality):
通路記憶體時，大機率會通路連續的塊，而不是單一的記憶體位址，其實就是空間局部性在記憶體上的展現。目前計算機設計中，都是以塊/頁為機關管理排程存儲，其實就是在利用空間局部性來優化性能。
分支局部性(Branch locality)
這個又被稱為順序局部性，計算機中大部分指令是順序執行，順序執行和非順序執行的比例大緻是5:1，即便有if這種選擇分支，其實大多數情況下某個分支都是被大機率選中的，于是就有了CPU的分支預測優化。
等距局部性(Equidistant locality)
等距局部性是指如果某個位置被通路，那和它相鄰等距離的連續位址極有可能會被通路到，它位于空間局部性和分支局部性之間。 舉個例子，比如多個相同格式的資料數組，你隻取其中每個資料的一部分字段，那麼他們可能在記憶體中位址距離是等距的，這個可以通過簡單的線性預測就預測是未來通路的位置。
實際應用
計算機領域關于局部性非常多的利用，有很多你每天都會用到，但可能并沒有察覺，另外一些可能離你會稍微遠一些，接下來我們舉幾個例子來深入了解下局部性的應用。
計算機存儲層級結構
上圖來自極客時間徐文浩的《深入淺出計算機組成原理》，我們以目前常見的普通家用電腦為例 ，分别說下上圖各級存儲的大小和通路速度，資料來源于
https://people.eecs.berkeley.edu/~rcs/research/interactive_latency.html。
從最快的L1 Cache到最慢的HDD，其兩者的訪存時間差距達到了6個數量級，即便是和記憶體比較，也有幾百倍的差距。舉個例子，如果CPU在運算是直接從記憶體中讀取指令和資料，執行一條指令0.3ns，然後從記憶體讀下一條指令，等120ns，這樣CPU 99%計算時間都會被浪費掉。但就是因為有局部性的存在，每一層都隻有少部分資料會被頻繁通路，我們可以把這部分資料從底層存儲挪到高層存儲，可以降低大部分的資料讀取時間。
可能有些人好奇，為什麼不把L1 緩存做的大點，像記憶體那麼大，直接替代掉記憶體，不是性能更好嗎？雖然是這樣，但是L1 Cache機關價格要比記憶體機關的價格貴好多(大概差200倍)，有興趣可以了解下DRAM和SRAM。
我們可以通過編寫高速緩存友好的代碼邏輯來提升我們的代碼性能，有兩個基本方法 。
- 讓最常見的情況運作的快，程式大部分的運作實際都花在少了核心函數上，而這些函數把大部分時間都花在少量循環上，把注意力放在這些代碼上。
- 讓每個循環内緩存不命中率最小。比如盡量不要列周遊二維數組。
MemCache
MemCache在大型網站架構中經常看到。DB一般公司都會用mysql，即便是做了分庫分表，資料資料庫單機的壓力還是非常大的，這時候因為局部性的存在，可能很多資料會被頻繁通路，這些資料就可以被cache到像redis這種memcache中，當redis查不到資料，再去查db，并寫入redis。
因為redis的水準擴充能力和簡單查詢能力要比mysql強多了，查起來也快。是以這種架構設計有幾個好處：
- 加快了資料查詢的平均速度。
- 大幅度減少DB的壓力。
CDN
CDN的全稱是Content Delivery Network，即内容分發網絡(圖檔來自百度百科) 。CDN常用于大的素材下發，比如圖檔和視訊，你在淘寶上打開一個圖檔，這個圖檔其實會就近從CDN機房拉去資料，而不是到阿裡的機房拉資料，可以減少阿裡機房的出口帶寬占用，也可以減少使用者加載素材的等待時間。
CDN在網際網路中被大規模使用，像視訊、直播網站，電商網站，甚至是12306都在使用，這種設計對公司可以節省帶寬成本，對使用者可以減少素材加載時間，提升使用者體驗。看到這，有沒有發現，CDN的邏輯和Memcache的使用很類似，你可以直接當他是一個網際網路版的cache優化。
Java JIT
JIT全稱是Just-in-time Compiler，中文名為即時編譯器，是一種Java運作時的優化。Java的運作方式和C++不太一樣，因為為了實作write once, run anywhere的跨平台需求，Java實作了一套位元組碼機制，所有的平台都可以執行同樣的位元組碼，執行時有該平台的JVM将位元組碼實時翻譯成該平台的機器碼再執行。問題在于位元組碼每次執行都要翻譯一次，會很耗時。
圖檔來自鄭雨迪
Introduction to Graal，Java 7引入了tiered compilation的概念，綜合了C1的高啟動性能及C2的高峰值性能。這兩個JIT compiler以及interpreter将HotSpot的執行方式劃分為五個級别：
- level 0：interpreter解釋執行
- level 1：C1編譯，無profiling
- level 2：C1編譯，僅方法及循環back-edge執行次數的profiling
- level 3：C1編譯，除level 2中的profiling外還包括branch（針對分支跳轉位元組碼）及receiver type（針對成員方法調用或類檢測，如checkcast，instnaceof，aastore位元組碼）的profiling
- level 4：C2編譯
通常情況下，一個方法先被解釋執行（level 0），然後被C1編譯（level 3），再然後被得到profile資料的C2編譯（level 4）。如果編譯對象非常簡單，虛拟機認為通過C1編譯或通過C2編譯并無差別，便會直接由C1編譯且不插入profiling代碼（level 1）。在C1忙碌的情況下，interpreter會觸發profiling，而後方法會直接被C2編譯；在C2忙碌的情況下，方法則會先由C1編譯并保持較少的profiling（level 2），以擷取較高的執行效率（與3級相比高30%）。
這裡将少部分位元組碼實時編譯成機器碼的方式，可以提升java的運作效率。可能有人會問，為什麼不預先将所有的位元組碼編譯成機器碼，執行的時候不是更快更省事嗎？首先機器碼是和平台強相關的，linux和unix就可能有很大的不同，何況是windows，預編譯會讓java失去誇平台這種優勢。 其次，即時編譯可以讓jvm拿到更多的運作時資料，根據這些資料可以對位元組碼做更深層次的優化，這些是C++這種預編譯語言做不到的，是以有時候你寫出的java代碼執行效率會比C++的高。
CopyOnWrite
CopyOnWrite寫時複制，最早應該是源自linux系統，linux中在調用fork() 生成子程序時，子程序應該擁有和父程序一樣的指令和資料，可能子程序會修改一些資料，為了避免污染父程序的資料，是以要給子程序單獨拷貝一份。出于效率考慮，fork時并不會直接複制，而是等到子程序的各段資料需要寫入才會複制一份給子程序，故此得名 寫時複制 。
在計算機的世界裡，讀寫的分布也是有很大的局部性的，大多數情況下讀遠大于寫， 寫時複制 的方式，可以減少大量不必要的複制，提升性能。 另外這種方式也不僅僅是用在linux核心中，java的concurrent包中也提供了CopyOnWriteArrayList CopyOnWriteArraySet。像Spark中的RDD也是用CopyOnWrite來減少不必要的RDD生成。
處理
上面列舉了那麼多局部性的應用，其實還有很多很多，我隻是列舉出了幾個我所熟知的應用，雖然上面這些例子，我們都利用局部性得到了能效、成本上的提升。但有些時候它也會給我們帶來一些不好的體驗，更多的時候它其實就是一把雙刃劍，我們如何識别局部性，利用它好的一面，避免它壞的一面？
識别
文章開頭也說過，局部性其實就是一種機率的不均等性，是以隻要機率不均等就一定存在局部性，因為很多時候這種機率不均太明顯了，非常好識别出來，然後我們對大頭做相應的優化就行了。但可能有些時候這種機率不均需要做很詳細的計算才能發現，最後還得核對成本才能考慮是否值得去做，這種需要具體問題具體分析了。
如何識别局部性，很簡單，看機率分布曲線，隻要不是一條水準的直線，就一定存在局部性。
利用
發現局部性之後對我們而言是如何利用好這些局部性，用得好提升性能、節約資源，用不好局部性就會變成阻礙。而且不光是在計算機領域，局部性在非計算機領域也可以利用。
##### 性能優化
上面列舉到的很多應用其實就是通過局部性做一些優化，雖然這些都是别人已經做好的，但是我們也可以參考其設計思路。
恰巧最近我也在做我們一個java服務的性能優化，利用jstack、jmap這些java自帶的分析工具，找出其中最吃cpu的線程，找出最占記憶體的對象。我發現有個redis資料查詢有問題，因為每次需要将一個大字元串解析很多個鍵值對，中間會産生上千個臨時字元串，還需要将字元串parse成long和double。redis資料太多，不可能完全放的記憶體裡，但是這裡的key有明顯的局部性，大量的查詢隻會集中在頭部的一些key上，我用一個LRU Cache緩存頭部資料的解析結果，就可以減少大量的查redis+解析字元串的過程了。
另外也發現有個代碼邏輯，每次請求會被重複執行幾千次，耗費大量cpu，這種熱點代碼，簡單幾行改動減少了不必要的調用，最終減少了近50%的CPU使用。
##### 非計算機領域
《高能人士的七個習慣》裡提到了一種工作方式，将任務劃分為重要緊急、不重要但緊急、重要但不緊急、不重要不緊急四種，這種劃分方式其實就是按機關時間的重要度排序的，按機關時間的重要度越高收益越大。《The Effective Engineer》裡直接用leverage(杠杆率)來衡量每個任務的重要性。這兩種方法差不多是類似的，都是優先做高收益率的事情，可以明顯提升你的工作效率。
這就是工作中收益率的局部性導緻的，隻要少數事情有比較大的收益，才值得去做。還有一個很著名的法則__82法則__，在很多行業、很多領域都可以套用，_80%的xxx來源于20%的xxx_ ，80%的工作收益來源于20%的工作任務，局部性給我們的啟示“永遠關注最重要的20%” 。
避免
上面我們一直在講如何通過局部性來提升性能，但有時候我們需要避免局部性的産生。 比如在大資料運算時，時常會遇到資料傾斜、資料熱點的問題，這就是資料分布的局部性導緻的，資料傾斜往往會導緻我們的資料計算任務耗時非常長，資料熱點會導緻某些單節點成為整個叢集的性能瓶頸，但大部分節點卻很閑，這些都是我們需要極力避免的。
一般我們解決熱點和資料切斜的方式都是提供過重新hash打亂整個資料讓資料達到均勻分布，當然有些業務邏輯可能不會讓你随意打亂資料，這時候就得具體問題具體分析了。感覺在大資料領域，局部性極力避免，當然如果沒法避免你就得通過其他方式來解決了，比如HDFS中小檔案單節點讀的熱點，可以通過減少加副本緩解。其本質上沒有避免局部性，隻增加資源緩解熱點了，據說微網誌為應對明星出軌Redis叢集也是采取這種加資源的方式。
參考資料
- 維基百科局部性原理
- 《計算機組成與設計》 David A.Patterson / John L.Hennessy
- 《深入淺出計算機組成原理》 極客時間 徐文浩
- 《深入了解計算機系統》 Randal E.Bryant / David O'Hallaron 龔奕利 / 雷迎春(譯)
- interactive latencies
- 鄭雨迪