聊聊緩存世界的掃地僧
這篇文章，筆者想聊聊那些在業(yè)務系統(tǒng)中較少被使用，但卻活躍于中間件或者框架里，強大卻又低調的緩存，筆者愿稱他們?yōu)榫彺媸澜绲膾叩厣?/p>
一、HashMap/ConcurrentHashMap 配置緩存
HashMap 是一種基于哈希表的集合類，它提供了快速的插入、查找和刪除操作。
HashMap 是很多程序員接觸的第一種緩存 , 因為現(xiàn)實業(yè)務場景里，我們可能需要給緩存添加緩存統(tǒng)計、過期失效、淘汰策略等功能，HashMap 的功能就顯得孱弱 ，所以 HashMap 在業(yè)務系統(tǒng)中使用得并不算多。
但 HashMap 在中間件中卻是香餑餑，我們消息中間件 RocketMQ 為例。
上圖是 RocketMQ 的集群模式 ，Broker 分為 Master 與 Slave，一個 Master 可以對應多個 Slave，但是一個 Slave 只能對應一個 Master。
每個 Broker 與 Name Server 集群中的所有節(jié)點建立長連接，定時每隔 30 秒注冊 主題的路由信息到所有 Name Server。
消息發(fā)送者、消息消費者，在同一時間只會連接 Name Server 集群中的一臺服務器，并且會每隔 30s 會定時更新 Topic 的路由信息。
我們可以理解 Name Server 集群的作用就是注冊中心，注冊中心會保存路由信息（主題的讀寫隊列數(shù)、操作權限等），路由信息就是保存在 HashMap 中 。
路由信息通過幾個 HashMap 來保存，當 Broker 向 Nameserver 發(fā)送心跳包（路由信息），Nameserver 需要對 HashMap 進行數(shù)據(jù)更新，但我們都知道 HashMap 并不是線程安全的，高并發(fā)場景下，容易出現(xiàn) CPU 100% 問題，所以更新 HashMap 時需要加鎖，RocketMQ 使用了 JDK 的讀寫鎖 ReentrantReadWriteLock 。
下面我們看下路由信息如何更新和讀取：
1、寫操作：更新路由信息，操作寫鎖
2、讀操作：查詢主題信息，操作讀鎖
同時，我們需要注意 Name Server 維護路由信息還需要定時任務的支撐。
- 每個 Broker 定時每隔 30 秒注冊 主題的路由信息到所有 Name Server
- Name Server 定時任務每隔10 秒清除已宕機的 Broker
我們做一個小小的總結，Name Server 維護路由的模式是：HashMap + 讀寫鎖 + 定時任務更新。
- HashMap 作為存儲容器
- 讀寫鎖控制鎖的顆粒度
- 定時任務定時更新緩存
寫到這里，我們不禁想到 ConcurrentHashMap 。
ConcurrentHashMap 可以保證線程安全，JDK1.7 之前使用分段鎖機制實現(xiàn)，JDK1.8 則使用數(shù)組+鏈表+紅黑樹數(shù)據(jù)結構和CAS原子操作實現(xiàn)。
Broker 使用不同的 ConcurrentHashMap 分別用來存儲消費組、消費進度、消息過濾信息等。
那么名字服務為什么不使用 ConcurrentHashMap 作為存儲容器呢 ？
最核心的原因在于：路由信息由多個 HashMap 組成，通過每次寫操作可能要操作多個對象 ，為了保證其一致性，所以才需要加讀寫鎖。
二、LinkedHashMap 最近最少使用緩存
LinkedHashMap 是 HashMap 的子類，但是內部還有一個雙向鏈表維護鍵值對的順序，每個鍵值對既位于哈希表中，也位于雙向鏈表中。
LinkedHashMap 支持兩種順序插入順序 、 訪問順序。
- 插入順序：先添加的在前面，后添加的在后面，修改操作并不影響順序
- 訪問順序：問指的是 get/put 操作，對一個鍵執(zhí)行 get/put 操作后，其對應的鍵值對會移動到鏈表末尾，所以最末尾的是最近訪問的，最開始的是最久沒有被訪問的，這就是訪問順序。
LinkedHashMap 經(jīng)典的用法是作為 LruCache (最近最少使用緩存) ，而 MyBatis 的二級緩存的淘汰機制就是使用的 LinkedHashMap 。
MyBatis 的二級緩存是使用責任鏈+ 裝飾器的設計模式實現(xiàn)的。
上圖中，裝飾器包目錄下 Cache 接口有不同的實現(xiàn)類，比如過期淘汰、日志記錄等。
LruCache 使用了裝飾器模式 ，使用 LinkedHashMap 默認保存 1024 個緩存 key ，當 key 最久未被訪問，并且 keyMap 的大小超過 1024 時 ，記錄最老的 key ，當下次添加緩存對象時，刪除最老的 key。
使用 LinkedHashMap 重點需要做到使用訪問順序模式和重寫 removeEldestEntry 方法。因為 LinkedHashMap 并不是線程安全的，Mybatis 二級緩存責任鏈中 SynchronizedCache 對象可以實現(xiàn)線程安全的對緩存讀寫。
三、TreeMap 排序對象緩存
TreeMap 是一種基于紅黑樹的有序 Map，它可以按照鍵的順序進行遍歷。
TreeMap 有兩種應用場景讓筆者印象極為深刻 ，他們分別是一致性哈希算法和 RocketMQ 消費快照 。
本文重點介紹 TreeMap 在一致性哈希算法中的應用。
一致性哈希（Consistent Hashing）算法被廣泛應用于緩存系統(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é)點在哈希環(huán)上的位置和鍵的有序性。
1、我們定義一個 TreeMap 存儲節(jié)點/虛擬節(jié)點 。
2、初始化節(jié)點
構造函數(shù)包含三個部分：物理節(jié)點集合、每個物理節(jié)點對應的虛擬節(jié)點個數(shù)、哈希函數(shù) 。
我們重點看下添加節(jié)點邏輯：
3、按照 key 查詢節(jié)點
添加完節(jié)點之后，節(jié)點分布類似下圖：
當需要定位某個 key 屬于哪個節(jié)點時，先通過哈希函數(shù)計算 key 的哈希值，并在環(huán)上順時針方向找到第一個大于等于該哈希值的節(jié)點位置。該節(jié)點即為數(shù)據(jù)的歸屬節(jié)點 。
我們添加一個新的節(jié)點 node5 , 從下圖中，我們可以看到，影響的范圍（深黃色）并不大 ，這也就是一致性哈希算法的優(yōu)勢。
四、ByteBuffer 網(wǎng)絡編程緩沖池
ByteBuffer 是字節(jié)緩沖區(qū)，主要用于用戶讀取和緩存字節(jié)數(shù)據(jù)，多用于網(wǎng)絡編程、文件 IO 處理等。
筆者第一次接觸 ByteBuffer 是在分庫分表中間件 Cobar 中 。在網(wǎng)絡編程里，經(jīng)常需要分配內存，在高并發(fā)場景下，性能壓力比較大。
Cobar 抽象了一個 NIOProcessor 類用來處理網(wǎng)絡請求，每個處理器初始化的時候都會創(chuàng)建一個緩沖池 BufferPool 。BufferPool 用于池化 ByteBuffer ，這和我們平常使用的數(shù)據(jù)庫連接池的思路是一致的。
下圖展示了緩沖池 BufferPool 的源碼：
緩沖池 BufferPool 的核心功能是分配緩存和回收緩存 ，通過將緩存池化，可以大大提升系統(tǒng)的性能。
如今 ，Netty 內置了更為強大的內存池化工具 ByteBuf ，我們會在后面的文章里詳聊。
五、寫到最后
這篇文章，筆者總結了四種強大且低調的緩存。
1、HashMap/ConcurrentHashMap 經(jīng)常用于配置緩存，對于 HashMap 來講，HashMap + 讀寫鎖 + 定時任務更新是常用的模式。而 ConcurrentHashMap 廣泛存在于各種中間件，線程安全且靈活易用。
2、LinkedHashMap 經(jīng)常被用于創(chuàng)建最近最少使用緩存 LruCache 。推薦學習 Mybatis 二級緩存的設計，它使用責任鏈+ 裝飾器的設計模式，內置 LruCache 的實現(xiàn)就是使用 LinkedHashMap 。
3、TreeMap 是一種基于紅黑樹的有序 Map 。TreeMap 在一致性哈希中可以用作節(jié)點/虛擬節(jié)點的存儲結構，用來維護節(jié)點在哈希環(huán)上的位置和鍵的有序性。
4、ByteBuffer 是字節(jié)緩沖區(qū)，主要用于用戶讀取和緩存字節(jié)數(shù)據(jù)，多用于網(wǎng)絡編程、文件 IO 處理等。分庫分表中間件 Cobar 在網(wǎng)絡請求處理中，創(chuàng)建了緩沖池 BufferPool 用于池化 ByteBuffer ，從而大大提升系統(tǒng)的性能。
