[[278602]]

目錄

• 一、緩存特征
• 二、LRU
• 三、緩存類型
• 四、CDN
• 五、緩存問題
• 六、數(shù)據(jù)分布
• 七、一致性哈希

一、緩存特征

命中率

當(dāng)某個(gè)請求能夠通過訪問緩存而得到響應(yīng)時(shí)，稱為緩存命中。

緩存命中率越高，緩存的利用率也就越高。

最大空間

緩存通常位于內(nèi)存中，內(nèi)存的空間通常比磁盤空間小的多，因此緩存的最大空間不可能非常大。

當(dāng)緩存存放的數(shù)據(jù)量超過最大空間時(shí)，就需要淘汰部分?jǐn)?shù)據(jù)來存放新到達(dá)的數(shù)據(jù)。

淘汰策略

• FIFO(First In First Out)：先進(jìn)先出策略，在實(shí)時(shí)性的場景下，需要經(jīng)常訪問最新的數(shù)據(jù)，那么就可以使用 FIFO，使得最先進(jìn)入的數(shù)據(jù)(最晚的數(shù)據(jù))被淘汰。
• LRU(Least Recently Used)：最近最久未使用策略，優(yōu)先淘汰最久未使用的數(shù)據(jù)，也就是上次被訪問時(shí)間距離現(xiàn)在最久的數(shù)據(jù)。該策略可以保證內(nèi)存中的數(shù)據(jù)都是熱點(diǎn)數(shù)據(jù)，也就是經(jīng)常被訪問的數(shù)據(jù)，從而保證緩存命中率。
• LFU(Least Frequently Used)：最不經(jīng)常使用策略，優(yōu)先淘汰一段時(shí)間內(nèi)使用次數(shù)最少的數(shù)據(jù)。

二、LRU

以下是基于 雙向鏈表 + HashMap 的 LRU 算法實(shí)現(xiàn)，對算法的解釋如下：

• 訪問某個(gè)節(jié)點(diǎn)時(shí)，將其從原來的位置刪除，并重新插入到鏈表頭部。這樣就能保證鏈表尾部存儲(chǔ)的就是最近最久未使用的節(jié)點(diǎn)，當(dāng)節(jié)點(diǎn)數(shù)量大于緩存最大空間時(shí)就淘汰鏈表尾部的節(jié)點(diǎn)。
• 為了使刪除操作時(shí)間復(fù)雜度為 O(1)，就不能采用遍歷的方式找到某個(gè)節(jié)點(diǎn)。HashMap 存儲(chǔ)著 Key 到節(jié)點(diǎn)的映射，通過 Key 就能以 O(1) 的時(shí)間得到節(jié)點(diǎn)，然后再以 O(1) 的時(shí)間將其從雙向隊(duì)列中刪除。

三、緩存類型

瀏覽器

當(dāng) HTTP 響應(yīng)允許進(jìn)行緩存時(shí)，瀏覽器會(huì)將 HTML、CSS、JavaScript、圖片等靜態(tài)資源進(jìn)行緩存。

ISP

網(wǎng)絡(luò)服務(wù)提供商(ISP)是網(wǎng)絡(luò)訪問的第一跳，通過將數(shù)據(jù)緩存在 ISP 中能夠大大提高用戶的訪問速度。

反向代理

反向代理位于服務(wù)器之前，請求與響應(yīng)都需要經(jīng)過反向代理。通過將數(shù)據(jù)緩存在反向代理，在用戶請求反向代理時(shí)就可以直接使用緩存進(jìn)行響應(yīng)。

本地緩存

使用 Guava Cache 將數(shù)據(jù)緩存在服務(wù)器本地內(nèi)存中，服務(wù)器代碼可以直接讀取本地內(nèi)存中的緩存，速度非常快。

分布式緩存

使用 Redis、Memcache 等分布式緩存將數(shù)據(jù)緩存在分布式緩存系統(tǒng)中。

相對于本地緩存來說，分布式緩存單獨(dú)部署，可以根據(jù)需求分配硬件資源。不僅如此，服務(wù)器集群都可以訪問分布式緩存，而本地緩存需要在服務(wù)器集群之間進(jìn)行同步，實(shí)現(xiàn)難度和性能開銷上都非常大。

數(shù)據(jù)庫緩存

MySQL 等數(shù)據(jù)庫管理系統(tǒng)具有自己的查詢緩存機(jī)制來提高查詢效率。

Java 內(nèi)部的緩存

Java 為了優(yōu)化空間，提高字符串、基本數(shù)據(jù)類型包裝類的創(chuàng)建效率，設(shè)計(jì)了字符串常量池及 Byte、Short、Character、Integer、Long、Boolean 這六種包裝類緩沖池。

CPU 多級緩存

CPU 為了解決運(yùn)算速度與主存 IO 速度不匹配的問題，引入了多級緩存結(jié)構(gòu)，同時(shí)使用 MESI 等緩存一致性協(xié)議來解決多核 CPU 緩存數(shù)據(jù)一致性的問題。

四、CDN

內(nèi)容分發(fā)網(wǎng)絡(luò)(Content distribution network，CDN)是一種互連的網(wǎng)絡(luò)系統(tǒng)，它利用更靠近用戶的服務(wù)器從而更快更可靠地將 HTML、CSS、JavaScript、音樂、圖片、視頻等靜態(tài)資源分發(fā)給用戶。

CDN 主要有以下優(yōu)點(diǎn)：

• 更快地將數(shù)據(jù)分發(fā)給用戶;
• 通過部署多臺(tái)服務(wù)器，從而提高系統(tǒng)整體的帶寬性能;
• 多臺(tái)服務(wù)器可以看成是一種冗余機(jī)制，從而具有高可用性。

五、緩存問題

緩存穿透

指的是對某個(gè)一定不存在的數(shù)據(jù)進(jìn)行請求，該請求將會(huì)穿透緩存到達(dá)數(shù)據(jù)庫。

解決方案：

• 對這些不存在的數(shù)據(jù)緩存一個(gè)空數(shù)據(jù);
• 對這類請求進(jìn)行過濾。

緩存雪崩

指的是由于數(shù)據(jù)沒有被加載到緩存中，或者緩存數(shù)據(jù)在同一時(shí)間大面積失效(過期)，又或者緩存服務(wù)器宕機(jī)，導(dǎo)致大量的請求都到達(dá)數(shù)據(jù)庫。

在有緩存的系統(tǒng)中，系統(tǒng)非常依賴于緩存，緩存分擔(dān)了很大一部分的數(shù)據(jù)請求。當(dāng)發(fā)生緩存雪崩時(shí)，數(shù)據(jù)庫無法處理這么大的請求，導(dǎo)致數(shù)據(jù)庫崩潰。

解決方案：

• 為了防止緩存在同一時(shí)間大面積過期導(dǎo)致的緩存雪崩，可以通過觀察用戶行為，合理設(shè)置緩存過期時(shí)間來實(shí)現(xiàn);
• 為了防止緩存服務(wù)器宕機(jī)出現(xiàn)的緩存雪崩，可以使用分布式緩存，分布式緩存中每一個(gè)節(jié)點(diǎn)只緩存部分的數(shù)據(jù)，當(dāng)某個(gè)節(jié)點(diǎn)宕機(jī)時(shí)可以保證其它節(jié)點(diǎn)的緩存仍然可用。
• 也可以進(jìn)行緩存預(yù)熱，避免在系統(tǒng)剛啟動(dòng)不久由于還未將大量數(shù)據(jù)進(jìn)行緩存而導(dǎo)致緩存雪崩。

緩存一致性

緩存一致性要求數(shù)據(jù)更新的同時(shí)緩存數(shù)據(jù)也能夠?qū)崟r(shí)更新。

解決方案：

• 在數(shù)據(jù)更新的同時(shí)立即去更新緩存;
• 在讀緩存之前先判斷緩存是否是最新的，如果不是最新的先進(jìn)行更新。

要保證緩存一致性需要付出很大的代價(jià)，緩存數(shù)據(jù)最好是那些對一致性要求不高的數(shù)據(jù)，允許緩存數(shù)據(jù)存在一些臟數(shù)據(jù)。

緩存 “無底洞” 現(xiàn)象

指的是為了滿足業(yè)務(wù)要求添加了大量緩存節(jié)點(diǎn)，但是性能不但沒有好轉(zhuǎn)反而下降了的現(xiàn)象。

產(chǎn)生原因：緩存系統(tǒng)通常采用 hash 函數(shù)將 key 映射到對應(yīng)的緩存節(jié)點(diǎn)，隨著緩存節(jié)點(diǎn)數(shù)目的增加，鍵值分布到更多的節(jié)點(diǎn)上，導(dǎo)致客戶端一次批量操作會(huì)涉及多次網(wǎng)絡(luò)操作，這意味著批量操作的耗時(shí)會(huì)隨著節(jié)點(diǎn)數(shù)目的增加而不斷增大。此外，網(wǎng)絡(luò)連接數(shù)變多，對節(jié)點(diǎn)的性能也有一定影響。

解決方案：

• 優(yōu)化批量數(shù)據(jù)操作命令;
• 減少網(wǎng)絡(luò)通信次數(shù);
• 降低接入成本，使用長連接 / 連接池，NIO 等。

六、數(shù)據(jù)分布

哈希分布

哈希分布就是將數(shù)據(jù)計(jì)算哈希值之后，按照哈希值分配到不同的節(jié)點(diǎn)上。例如有 N 個(gè)節(jié)點(diǎn)，數(shù)據(jù)的主鍵為 key，則將該數(shù)據(jù)分配的節(jié)點(diǎn)序號為：hash(key)%N。

傳統(tǒng)的哈希分布算法存在一個(gè)問題：當(dāng)節(jié)點(diǎn)數(shù)量變化時(shí)，也就是 N 值變化，那么幾乎所有的數(shù)據(jù)都需要重新分布，將導(dǎo)致大量的數(shù)據(jù)遷移。

順序分布

將數(shù)據(jù)劃分為多個(gè)連續(xù)的部分，按數(shù)據(jù)的 ID 或者時(shí)間分布到不同節(jié)點(diǎn)上。例如 User 表的 ID 范圍為 1 ~ 7000，使用順序分布可以將其劃分成多個(gè)子表，對應(yīng)的主鍵范圍為 1 ~ 1000，1001 ~ 2000，...，6001 ~ 7000。

順序分布相比于哈希分布的主要優(yōu)點(diǎn)如下：

能保持?jǐn)?shù)據(jù)原有的順序;

并且能夠準(zhǔn)確控制每臺(tái)服務(wù)器存儲(chǔ)的數(shù)據(jù)量，從而使得存儲(chǔ)空間的利用率最大。

七、一致性哈希

Distributed Hash Table(DHT) 是一種哈希分布方式，其目的是為了克服傳統(tǒng)哈希分布在服務(wù)器節(jié)點(diǎn)數(shù)量變化時(shí)大量數(shù)據(jù)遷移的問題。

基本原理

將哈希空間 [0, 2n-1] 看成一個(gè)哈希環(huán)，每個(gè)服務(wù)器節(jié)點(diǎn)都配置到哈希環(huán)上。每個(gè)數(shù)據(jù)對象通過哈希取模得到哈希值之后，存放到哈希環(huán)中順時(shí)針方向第一個(gè)大于等于該哈希值的節(jié)點(diǎn)上。

一致性哈希在增加或者刪除節(jié)點(diǎn)時(shí)只會(huì)影響到哈希環(huán)中相鄰的節(jié)點(diǎn)，例如下圖中新增節(jié)點(diǎn) X，只需要將它前一個(gè)節(jié)點(diǎn) C 上的數(shù)據(jù)重新進(jìn)行分布即可，對于節(jié)點(diǎn) A、B、D 都沒有影響。

虛擬節(jié)點(diǎn)

上面描述的一致性哈希存在數(shù)據(jù)分布不均勻的問題，節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)量有可能會(huì)存在很大的不同。

數(shù)據(jù)不均勻主要是因?yàn)楣?jié)點(diǎn)在哈希環(huán)上分布的不均勻，這種情況在節(jié)點(diǎn)數(shù)量很少的情況下尤其明顯。

解決方式是通過增加虛擬節(jié)點(diǎn)，然后將虛擬節(jié)點(diǎn)映射到真實(shí)節(jié)點(diǎn)上。虛擬節(jié)點(diǎn)的數(shù)量比真實(shí)節(jié)點(diǎn)來得多，那么虛擬節(jié)點(diǎn)在哈希環(huán)上分布的均勻性就會(huì)比原來的真實(shí)節(jié)點(diǎn)好，從而使得數(shù)據(jù)分布也更加均勻。