這篇文章，筆者想聊聊那些在業(yè)務(wù)系統(tǒng)中較少被使用，但卻活躍于中間件或者框架里，強(qiáng)大卻又低調(diào)的緩存，筆者愿稱他們?yōu)榫彺媸澜绲膾叩厣?/p>

一、HashMap/ConcurrentHashMap 配置緩存

HashMap 是一種基于哈希表的集合類，它提供了快速的插入、查找和刪除操作。

HashMap 是很多程序員接觸的第一種緩存 , 因?yàn)楝F(xiàn)實(shí)業(yè)務(wù)場(chǎng)景里，我們可能需要給緩存添加緩存統(tǒng)計(jì)、過(guò)期失效、淘汰策略等功能，HashMap 的功能就顯得孱弱 ，所以 HashMap 在業(yè)務(wù)系統(tǒng)中使用得并不算多。

但 HashMap 在中間件中卻是香餑餑，我們消息中間件 RocketMQ 為例。

上圖是 RocketMQ 的集群模式 ，Broker 分為 Master 與 Slave，一個(gè) Master 可以對(duì)應(yīng)多個(gè) Slave，但是一個(gè) Slave 只能對(duì)應(yīng)一個(gè) Master。

每個(gè) Broker 與 Name Server 集群中的所有節(jié)點(diǎn)建立長(zhǎng)連接，定時(shí)每隔 30 秒注冊(cè) 主題的路由信息到所有 Name Server。

消息發(fā)送者、消息消費(fèi)者，在同一時(shí)間只會(huì)連接  Name Server 集群中的一臺(tái)服務(wù)器，并且會(huì)每隔 30s 會(huì)定時(shí)更新 Topic 的路由信息。

我們可以理解 Name Server 集群的作用就是注冊(cè)中心，注冊(cè)中心會(huì)保存路由信息（主題的讀寫隊(duì)列數(shù)、操作權(quán)限等），路由信息就是保存在 HashMap 中 。

路由信息通過(guò)幾個(gè) HashMap 來(lái)保存，當(dāng) Broker 向 Nameserver 發(fā)送心跳包（路由信息），Nameserver 需要對(duì) HashMap 進(jìn)行數(shù)據(jù)更新，但我們都知道 HashMap 并不是線程安全的，高并發(fā)場(chǎng)景下，容易出現(xiàn) CPU 100% 問(wèn)題，所以更新 HashMap 時(shí)需要加鎖，RocketMQ 使用了 JDK 的讀寫鎖 ReentrantReadWriteLock 。

下面我們看下路由信息如何更新和讀?。?/p>

1、寫操作：更新路由信息，操作寫鎖

2、讀操作：查詢主題信息，操作讀鎖

同時(shí)，我們需要注意 Name Server 維護(hù)路由信息還需要定時(shí)任務(wù)的支撐。

• 每個(gè) Broker 定時(shí)每隔 30 秒注冊(cè) 主題的路由信息到所有 Name Server
• Name Server 定時(shí)任務(wù)每隔10 秒清除已宕機(jī)的 Broker

我們做一個(gè)小小的總結(jié)，Name Server 維護(hù)路由的模式是：HashMap + 讀寫鎖 + 定時(shí)任務(wù)更新。

• HashMap 作為存儲(chǔ)容器
• 讀寫鎖控制鎖的顆粒度
• 定時(shí)任務(wù)定時(shí)更新緩存

寫到這里，我們不禁想到 ConcurrentHashMap  。

ConcurrentHashMap 可以保證線程安全，JDK1.7 之前使用分段鎖機(jī)制實(shí)現(xiàn)，JDK1.8 則使用數(shù)組+鏈表+紅黑樹(shù)數(shù)據(jù)結(jié)構(gòu)和CAS原子操作實(shí)現(xiàn)。

Broker 使用不同的 ConcurrentHashMap 分別用來(lái)存儲(chǔ)消費(fèi)組、消費(fèi)進(jìn)度、消息過(guò)濾信息等。

那么名字服務(wù)為什么不使用 ConcurrentHashMap 作為存儲(chǔ)容器呢 ？

最核心的原因在于：路由信息由多個(gè) HashMap 組成，通過(guò)每次寫操作可能要操作多個(gè)對(duì)象 ，為了保證其一致性，所以才需要加讀寫鎖。

二、LinkedHashMap 最近最少使用緩存

LinkedHashMap 是 HashMap 的子類，但是內(nèi)部還有一個(gè)雙向鏈表維護(hù)鍵值對(duì)的順序，每個(gè)鍵值對(duì)既位于哈希表中，也位于雙向鏈表中。

LinkedHashMap 支持兩種順序插入順序 、 訪問(wèn)順序。

• 插入順序：先添加的在前面，后添加的在后面，修改操作并不影響順序
• 訪問(wèn)順序：?jiǎn)栔傅氖?get/put 操作，對(duì)一個(gè)鍵執(zhí)行 get/put 操作后，其對(duì)應(yīng)的鍵值對(duì)會(huì)移動(dòng)到鏈表末尾，所以最末尾的是最近訪問(wèn)的，最開(kāi)始的是最久沒(méi)有被訪問(wèn)的，這就是訪問(wèn)順序。

LinkedHashMap 經(jīng)典的用法是作為 LruCache (最近最少使用緩存) ，而 MyBatis 的二級(jí)緩存的淘汰機(jī)制就是使用的 LinkedHashMap 。

MyBatis 的二級(jí)緩存是使用責(zé)任鏈+ 裝飾器的設(shè)計(jì)模式實(shí)現(xiàn)的。

上圖中，裝飾器包目錄下 Cache 接口有不同的實(shí)現(xiàn)類，比如過(guò)期淘汰、日志記錄等。

LruCache 使用了裝飾器模式 ，使用 LinkedHashMap 默認(rèn)保存 1024 個(gè)緩存 key ，當(dāng) key 最久未被訪問(wèn)，并且 keyMap 的大小超過(guò) 1024 時(shí) ，記錄最老的 key ，當(dāng)下次添加緩存對(duì)象時(shí)，刪除最老的 key。

使用 LinkedHashMap 重點(diǎn)需要做到使用訪問(wèn)順序模式和重寫 removeEldestEntry 方法。因?yàn)?LinkedHashMap 并不是線程安全的，Mybatis 二級(jí)緩存責(zé)任鏈中 SynchronizedCache 對(duì)象可以實(shí)現(xiàn)線程安全的對(duì)緩存讀寫。

三、TreeMap 排序?qū)ο缶彺?/h2>

TreeMap 是一種基于紅黑樹(shù)的有序 Map，它可以按照鍵的順序進(jìn)行遍歷。

TreeMap 有兩種應(yīng)用場(chǎng)景讓筆者印象極為深刻 ，他們分別是一致性哈希算法和 RocketMQ 消費(fèi)快照 。

本文重點(diǎn)介紹 TreeMap 在一致性哈希算法中的應(yīng)用。

一致性哈希（Consistent Hashing）算法被廣泛應(yīng)用于緩存系統(tǒng)、分布式數(shù)據(jù)庫(kù)、負(fù)載均衡器等分布式系統(tǒng)中，以實(shí)現(xiàn)高性能和高可用性。它解決了傳統(tǒng)哈希算法在動(dòng)態(tài)環(huán)境下擴(kuò)展性和負(fù)載均衡性能的問(wèn)題。

一致性哈希的主要優(yōu)點(diǎn)是在節(jié)點(diǎn)增減時(shí)，只有少量的數(shù)據(jù)需要重新映射，因?yàn)橹挥心切┲苯踊蜷g接與新增或刪除節(jié)點(diǎn)相鄰的數(shù)據(jù)項(xiàng)需要遷移。這大大減少了系統(tǒng)的遷移開(kāi)銷和影響，使得系統(tǒng)更具擴(kuò)展性和可伸縮性。

TreeMap 在一致性哈希中可以用作節(jié)點(diǎn)/虛擬節(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)，用來(lái)維護(hù)節(jié)點(diǎn)在哈希環(huán)上的位置和鍵的有序性。

1、我們定義一個(gè) TreeMap 存儲(chǔ)節(jié)點(diǎn)/虛擬節(jié)點(diǎn) 。

2、初始化節(jié)點(diǎn)

構(gòu)造函數(shù)包含三個(gè)部分：物理節(jié)點(diǎn)集合、每個(gè)物理節(jié)點(diǎn)對(duì)應(yīng)的虛擬節(jié)點(diǎn)個(gè)數(shù)、哈希函數(shù) 。

我們重點(diǎn)看下添加節(jié)點(diǎn)邏輯：

3、按照 key 查詢節(jié)點(diǎn)

添加完節(jié)點(diǎn)之后，節(jié)點(diǎn)分布類似下圖：

當(dāng)需要定位某個(gè) key 屬于哪個(gè)節(jié)點(diǎn)時(shí)，先通過(guò)哈希函數(shù)計(jì)算 key 的哈希值，并在環(huán)上順時(shí)針?lè)较蛘业降谝粋€(gè)大于等于該哈希值的節(jié)點(diǎn)位置。該節(jié)點(diǎn)即為數(shù)據(jù)的歸屬節(jié)點(diǎn) 。

我們添加一個(gè)新的節(jié)點(diǎn) node5 , 從下圖中，我們可以看到，影響的范圍（深黃色）并不大 ，這也就是一致性哈希算法的優(yōu)勢(shì)。

四、ByteBuffer 網(wǎng)絡(luò)編程緩沖池

ByteBuffer 是字節(jié)緩沖區(qū)，主要用于用戶讀取和緩存字節(jié)數(shù)據(jù)，多用于網(wǎng)絡(luò)編程、文件 IO 處理等。

筆者第一次接觸 ByteBuffer 是在分庫(kù)分表中間件 Cobar 中 。在網(wǎng)絡(luò)編程里，經(jīng)常需要分配內(nèi)存，在高并發(fā)場(chǎng)景下，性能壓力比較大。

Cobar 抽象了一個(gè) NIOProcessor 類用來(lái)處理網(wǎng)絡(luò)請(qǐng)求，每個(gè)處理器初始化的時(shí)候都會(huì)創(chuàng)建一個(gè)緩沖池 BufferPool 。BufferPool 用于池化 ByteBuffer ，這和我們平常使用的數(shù)據(jù)庫(kù)連接池的思路是一致的。

下圖展示了緩沖池 BufferPool 的源碼：

緩沖池 BufferPool 的核心功能是分配緩存和回收緩存 ，通過(guò)將緩存池化，可以大大提升系統(tǒng)的性能。

如今 ，Netty 內(nèi)置了更為強(qiáng)大的內(nèi)存池化工具 ByteBuf ，我們會(huì)在后面的文章里詳聊。

五、寫到最后

這篇文章，筆者總結(jié)了四種強(qiáng)大且低調(diào)的緩存。

1、HashMap/ConcurrentHashMap 經(jīng)常用于配置緩存，對(duì)于 HashMap 來(lái)講，HashMap + 讀寫鎖 + 定時(shí)任務(wù)更新是常用的模式。而 ConcurrentHashMap 廣泛存在于各種中間件，線程安全且靈活易用。

2、LinkedHashMap 經(jīng)常被用于創(chuàng)建最近最少使用緩存 LruCache 。推薦學(xué)習(xí) Mybatis 二級(jí)緩存的設(shè)計(jì)，它使用責(zé)任鏈+ 裝飾器的設(shè)計(jì)模式，內(nèi)置 LruCache 的實(shí)現(xiàn)就是使用 LinkedHashMap 。

3、TreeMap 是一種基于紅黑樹(shù)的有序 Map 。TreeMap 在一致性哈希中可以用作節(jié)點(diǎn)/虛擬節(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)，用來(lái)維護(hù)節(jié)點(diǎn)在哈希環(huán)上的位置和鍵的有序性。

4、ByteBuffer 是字節(jié)緩沖區(qū)，主要用于用戶讀取和緩存字節(jié)數(shù)據(jù)，多用于網(wǎng)絡(luò)編程、文件 IO 處理等。分庫(kù)分表中間件 Cobar 在網(wǎng)絡(luò)請(qǐng)求處理中，創(chuàng)建了緩沖池 BufferPool 用于池化 ByteBuffer ，從而大大提升系統(tǒng)的性能。