1 HashMap/ConcurrentHashMap 配置緩存

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

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

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

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

每個 Broker 與 Name Server 集群中的所有節(jié)點建立長連接，定時每隔 30 秒注冊 主題的路由信息到所有 Name Server。

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

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

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

下面我們看下路由信息如何更新和讀取：

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

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

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

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

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

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

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

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

Broker 使用不同的 ConcurrentHashMap 分別用來存儲消費組、消費進度、消息過濾信息等。

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

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

2 LinkedHashMap 最近最少使用緩存

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

LinkedHashMap 支持兩種順序插入順序 、 訪問順序。

• 插入順序：先添加的在前面，后添加的在后面，修改操作并不影響順序
• 訪問順序：問指的是 get/put 操作，對一個鍵執(zhí)行 get/put 操作后，其對應(yīng)的鍵值對會移動到鏈表末尾，所以最末尾的是最近訪問的，最開始的是最久沒有被訪問的，這就是訪問順序。

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

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

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

LruCache 使用了裝飾器模式 ，使用 LinkedHashMap 默認保存 1024 個緩存 key ，當 key 最久未被訪問，并且 keyMap 的大小超過 1024 時 ，記錄最老的 key ，當下次添加緩存對象時，刪除最老的 key。

使用 LinkedHashMap 重點需要做到使用訪問順序模式和重寫 removeEldestEntry 方法。因為 LinkedHashMap 并不是線程安全的，Mybatis 二級緩存責任鏈中 SynchronizedCache 對象可以實現(xiàn)線程安全的對緩存讀寫。

3 TreeMap 排序?qū)ο缶彺?/span>

TreeMap 是一種基于紅黑樹的有序 Map，它可以按照鍵的順序進行遍歷。

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

下面重點介紹 TreeMap 在一致性哈希算法中的應(yīng)用。

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

一致性哈希的主要優(yōu)點是在節(jié)點增減時，只有少量的數(shù)據(jù)需要重新映射，因為只有那些直接或間接與新增或刪除節(jié)點相鄰的數(shù)據(jù)項需要遷移。這大大減少了系統(tǒng)的遷移開銷和影響，使得系統(tǒng)更具擴展性和可伸縮性。

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

1、我們定義一個 TreeMap 存儲節(jié)點/虛擬節(jié)點 。

2、初始化節(jié)點

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

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

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

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

當需要定位某個 key 屬于哪個節(jié)點時，先通過哈希函數(shù)計算 key 的哈希值，并在環(huán)上順時針方向找到第一個大于等于該哈希值的節(jié)點位置。該節(jié)點即為數(shù)據(jù)的歸屬節(jié)點 。

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

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

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

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

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

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

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

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

5 寫到最后

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

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

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

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

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