計算機的局部性原理該如何利用

服務(wù)端軟件開發(fā)時，通常會把數(shù)據(jù)存儲在DB。而服務(wù)端系統(tǒng)遇到的第一個性能瓶頸，往往發(fā)生在訪問DB時。

這時大部分開發(fā)會拿出“緩存”，通過使用Redis在DB前提供一層緩存數(shù)據(jù)，緩解DB壓力，提升服務(wù)端性能。

在數(shù)據(jù)庫前添加數(shù)據(jù)緩存是常見的性能優(yōu)化方式

這種添加緩存的策略一定有效嗎？這種策略在什么情況下是有效的呢？理論分析，添加緩存最佳策略么？

如果我們對訪問性能要求高，希望數(shù)據(jù)在1ms，乃至100微妙內(nèi)完成處理，我們還能用這個添加緩存的策略么？

理解局部性原理

Intel 8265U的CPU L1 Cache只有256K，L2 Cache有個1MB，L3 Cache有12MB。共13MB存儲空間，如按7美元/1MB的價格計算，就要91美元。

內(nèi)存8GB，容量是CPU Cache 600多倍，120美元。如按今天價格，恐怕不到40美元。128G的SSD和1T的HDD，現(xiàn)在的價格加起來也不會超過100美元。雖容量是內(nèi)存16倍乃至128倍，但訪問速度不到內(nèi)存1/1000。

性能和價格的巨大差異，給我們工程師帶來挑戰(zhàn)：能不能既享受CPU Cache速度，又享受內(nèi)存、硬盤巨大的容量和低廉的價格呢？

想要同時享受到這三點，答案就是存儲器中數(shù)據(jù)的局部性原理（Principle of Locality）。可利用這個原理制定管理和訪問數(shù)據(jù)的策略。這個局部性原理包括時間局部性（temporal locality）和空間局部性（spatial locality）這兩種策略。

時間局部性

如果一個數(shù)據(jù)被訪問了，那它在短時間內(nèi)還會被再次訪問。

如小說，今天讀了一會兒，沒讀完，明天還會繼續(xù)讀。同理電子商務(wù)系統(tǒng)，一個用戶打開App，看到首屏。推斷他應(yīng)該很快還會再次訪問網(wǎng)站的其他內(nèi)容或頁面，就將這個用戶的個人信息，從存儲在硬盤的數(shù)據(jù)庫讀取到內(nèi)存的緩存中來。這利用的就是時間局部性。

同一份數(shù)據(jù)在短時間內(nèi)會反復(fù)多次被訪問

空間局部性

如果一個數(shù)據(jù)被訪問了，那么和它相鄰的數(shù)據(jù)也很快會被訪問。

讀完了這本書之后，感覺這書不錯，所以就會借閱整套。程序訪問了數(shù)組首項后，多半會循環(huán)訪問下一項。因為，在存儲數(shù)據(jù)的時候，數(shù)組內(nèi)的多項數(shù)據(jù)會存儲在相鄰的位置。這就好比圖書館會把“哈利波特”系列放在一個書架上，擺放在一起，加載時，也會一并加載。我們?nèi)D書館借書，往往會一次性把7本都借回來。

相鄰的數(shù)據(jù)會被連續(xù)訪問

有了時間局部性和空間局部性，不用再把所有數(shù)據(jù)都放在內(nèi)存，也不用都放在HDD，而是把訪問次數(shù)多的數(shù)據(jù)，放在貴但快的存儲器，把訪問次數(shù)少的數(shù)據(jù)，放在慢但大點的存儲器。

這樣組合使用內(nèi)存、SSD硬盤以及HDD硬盤，最低成本提供實際所需的數(shù)據(jù)存儲、管理和訪問需求。

花最少的錢，裝下亞馬遜的所有商品？

通過局部性原理，利用不同層次存儲器的組合，究竟會有什么樣的好處。

提供一個亞馬遜電商網(wǎng)站。假設(shè)里面有6億件商品，如果每件商品需要4MB的存儲空間，需2400TB（ = 6億 × 4MB）數(shù)據(jù)存儲。

如把數(shù)據(jù)都放在內(nèi)存，就需3600萬美元（ = 2400TB/1MB × 0.015美元 = 3600萬美元）。但這6億件商品，不是每件商品都會被經(jīng)常訪問。如有Kindle，也一定有無人問津商品，如緬甸語詞典。

如只在內(nèi)存里放前1%熱門商品，即600萬件熱門商品，而把剩下商品，放在機械式HDD硬盤，則需存儲成本下降到45.6萬美元（ = 3600 萬美元 × 1% + 2400TB / 1MB × 0.00004 美元），是原來成本的1.3%左右。

這就是時間局部性。把有用戶訪問過數(shù)據(jù)，加載到內(nèi)存，一旦內(nèi)存放不下，就把最長時間沒在內(nèi)存被訪問過的數(shù)據(jù)，從內(nèi)存移走，這就是LRU（Least Recently Used）。

熱門商品被訪問得多，就會始終被保留在內(nèi)存，冷門商品被訪問得少，就只存放在HDD，數(shù)據(jù)讀取也都是直接訪問硬盤。即使加載到內(nèi)存中，也會很快被移除。越熱門，越容易在內(nèi)存中找到，也就更好地利用了內(nèi)存的隨機訪問性能。

只放600萬件商品真的可以滿足我們實際的線上服務(wù)請求嗎？

要看LRU緩存命中率（Hit Rate/Hit Ratio），即訪問的數(shù)據(jù)中，可在我們設(shè)置的內(nèi)存緩存中找到的占比。

內(nèi)存隨機訪問請求需要100ns。極限情況下，內(nèi)存可以支持1000萬次隨機訪問。我們用了24TB內(nèi)存，如果8G一條的話，意味著有3000條內(nèi)存，可以支持每秒300億次（ = 24TB/8GB × 1s/100ns）訪問。以亞馬遜2017年3億的用戶數(shù)來看，我們估算每天的活躍用戶為1億，這1億用戶每人平均會訪問100個商品，那么平均每秒訪問的商品數(shù)量，就是12萬次。

但如數(shù)據(jù)沒有命中內(nèi)存，那么對應(yīng)的數(shù)據(jù)請求就要訪問到HDD磁盤了。一塊HDD硬盤只能支撐每秒100次的隨機訪問，2400TB的數(shù)據(jù)，以4TB一塊磁盤來計算，有600塊磁盤，也就是能支撐每秒 6萬次（ = 2400TB/4TB × 1s/10ms ）的隨機訪問。

這意味所有商品訪問請求，都直接到了HDD磁盤，HDD磁盤支撐不了這樣的壓力。我們至少要50%的緩存命中率，HDD磁盤才能支撐對應(yīng)的訪問次數(shù)。不然的話，我們要么選擇添加更多數(shù)量的HDD硬盤，做到每秒12萬次的隨機訪問，或者將HDD替換成SSD硬盤，讓單個硬盤可以支持更多的隨機訪問請求。

這只是一個簡單估算。實際應(yīng)用程序中，查看一個商品數(shù)據(jù)意味著不止一次隨機內(nèi)存或隨機磁盤訪問。對應(yīng)數(shù)據(jù)存儲空間也不止要考慮數(shù)據(jù)，還需要考慮維護數(shù)據(jù)結(jié)構(gòu)的空間，而緩存的命中率和訪問請求也要考慮均值和峰值的問題。

估算過程要理解如何進行存儲器的硬件規(guī)劃。要考慮硬件的成本、訪問的數(shù)據(jù)量以及訪問的數(shù)據(jù)分布，然后根據(jù)這些數(shù)據(jù)的估算，來組合不同的存儲器，能用盡可能低的成本支撐所需要的服務(wù)器壓力。而當(dāng)你用上了數(shù)據(jù)訪問的局部性原理，組合起了多種存儲器，你也就理解了怎么基于存儲器層次結(jié)構(gòu)，來進行硬件規(guī)劃了。

總結(jié)

實際的計算機日常的開發(fā)和應(yīng)用中，對于數(shù)據(jù)的訪問總是會存在一定的局部性。有時候，這個局部性是時間局部性，就是我們最近訪問過的數(shù)據(jù)還會被反復(fù)訪問。有時候，這個局部性是空間局部性，就是我們最近訪問過數(shù)據(jù)附近的數(shù)據(jù)很快會被訪問到。

而局部性的存在，使得我們可以在應(yīng)用開發(fā)中使用緩存這個有利的武器。比如，通過將熱點數(shù)據(jù)加載并保留在速度更快的存儲設(shè)備里面，我們可以用更低的成本來支撐服務(wù)器。

通過亞馬遜這個例子，我們可以看到，我們可以通過快速估算的方式，來判斷這個添加緩存的策略是否能夠滿足我們的需求，以及在估算的服務(wù)器負(fù)載的情況下，需要規(guī)劃多少硬件設(shè)備。這個“估算+規(guī)劃”的能力，是每一個期望成長為架構(gòu)師的工程師，必須掌握的能力。

遇到性能問題，特別是訪問存儲器的性能問題的時候，是否可以簡單地添加一層數(shù)據(jù)緩存就能讓問題迎刃而解呢？

亞馬遜網(wǎng)站商品數(shù)據(jù)的例子，似乎給了我們一個“Yes”。那這個答案是否放之四海皆準(zhǔn)呢？下回分解

參考

《計算機組成與設(shè)計：硬件/軟件接口》的5.1～5.2小節(jié)

數(shù)據(jù)庫

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。