用 Caffeine 和 Redis 管理 Cache 案例分析
資料使用模式千百種，必須因事制宜地使用 Cache。網路上有許多不錯的整理，例如：
這篇就不多作類似的整理，而是備忘最近碰到有意思的實例。
以下是本篇名詞的意思：
- server：指 web server 或 API server。
- local cache：server 的 in-memory cache。
- external cache：多台 servers 共用的 cache server，可以是一台或一組。
- database：儲存原始資料的 database server，可以是一台或一組。
重啟 Server 後造成 Database 過載
重開 server 後需要一些時間才能填回 local cache，這段時間會增加 database 的負載。如果 servers 數量夠多，一台台慢慢地重開，不會造成 database 過載。但每次更新 server 的時間會拉很長。
解法是將 local cache 的資料寫入 external cache，重開後從 external cache 讀回來。細節實作有很多選擇，比方說原本的架構已將 local cache、external cache、database 作成一體的 inline cache。理論上重開前後的差異只是暫時增加 external cache 負載。
為降低 external cache 的負載，可以在 local cache 發出請求時多過一層 Caffeine 的 async load，用來統合同一個 key 多筆查詢成一筆對 external cache/database 的查詢。若有作 partition (後述)，等於來自同時間全部 servers 收到同一個 key 的查詢，總共只會發一次查詢到 external cache/database。
假設一次重開十台機器，十台機器每秒收到 100 筆同樣的查詢，等於將 1000 筆對 database 的查詢降為對 external cache 的 1 筆查詢。注意即使有作 partition，server 用 multi-threads 處理多個 client requests 時，仍有可能同時查 local cache 發現 cache miss，然後同時對 external cache 發出多個查詢，查詢同一個 key。使用 Caffeine 的 async load 可確保只查詢 external cache 一次。
資料一致性和 Scalability
如果每台 server 都用自己 local cache，N 台 server 的 cache pool size 和一台一樣，不具 scalability。並且需要處理資料一致性：server A 改了某個 key 的值，要通知其它 server 更新 local cache。
分散式系統的兩個核心模式是 partition (sharding) 和 replication。用 partition 可同時解決讀寫 scalability 問題，每個 key 只有唯一的 server 負責處理；用 replication 可解決 read scalability 並提供 high availability (HA)。
用 replication 的缺點是要處理 read consistency，我個人的偏好是即使用 partition + replication，也不要從 replicas 讀資料。換句話說，如果多作 replication，目的只是提高 HA，藉此避開 read consistency 的問題。
像這樣使用 partition 的 distributed cache 應該是常見解法？groupcache 是一個例子。更多的說明可見 Consistent Hash。
昂貴操作和 Cache Refresh
有些服務需要查詢大量 database 資料作複雜的計算後得出結果。自然會用 cache 減輕負擔。但是當資料過期的時候，第一筆請求仍需等一段時間。
解法是在資料快過期前先在背景更新資料。例如用 Caffeine 的 refresh，可設 10 分鐘後資料 stale，10 ~ 20 分鐘內有人存取，先回 stale data，同時在背景 refresh data。反之，若 10 ~ 20 分鐘內沒人存取，就刪除 stale data。
若想減低重開機第一次請求的等待時間 (還有降低 server 重開的負擔)，可以針對第一次請求用輕量化的實作，然後等一段隨機的時間後，在背景 refresh 執行原本的實作。例如 API 是提供最近一天內取樣的某種統計，輕量化實作可以只取 1/10 資料。
高頻率、高數量、不常更動的資料
由於讀取頻率很高，希望在 external cache 存愈多資料愈好，減輕 database 壓力。由於 key 的數量很高 (例如千萬筆或億筆)，若忽然有一批查詢的資料不在 external cache 內，可能會讓 database 過載。因此，必須有效率地在 external cache 內存資料。
直覺的作法是用 LRU 管理 external cache。以 Redis 來說，用 setex 設值和 TTL，然後每次 get 後順便用 expire 更新 TTL。
這作法有幾個小缺點：
- 每個 key 額外多占 90 bytes ，10M 筆會多占近 1G 記憶體。
- 常見操作變兩倍貴 （get + expire)。官方有個 issue 要求 getex 好多年了，還是沒結果。
- 不易掌握 keys 的數量。
前兩個效能問題不見得是必須解決的問題，最後一個可以用 scan 跑個數分鐘，也不嚴重。唯一要留意的是若同時有大量 keys 過期，會卡住 Redis 一段時間，因為 Redis 是固定時間隨機抽查 expired keys，不斷地清理直到數量降到 1/4。設 TTL 時，務必加上一段隨機值。
Generational LRU
若資料很少會更新，有個有趣的解法，可以解決上述三者問題：用類似 generational GC 的概念，將資料存在多個 hash。
概念是每個 hash 有個流水號，假設依序為 h0、h1、h2、…。查詢的作法如下：
- 先查 h0，有資料就返回。
- 查 h1，有資料就返回，順便「搬」到 h0 (
hset h0 key value+hdel h1 key)。 - 查 h2、h3 … 以此類推。
每個 hN 表示一段時間內的資料，N 愈大表示愈舊。所以若只想保留 N 筆，可以定期清掉 hN+1 和之後的 hash。用 unlink 清的話，不會占用 Redis main thread 的時間。
那要怎麼保持 h0、h1、… 有由新到舊的資料？可以用時間算出 hash 名稱，比方說 h20201114 存 2020/11/14 的資料，每天存到不同 hash。過了七天，就刪掉七天前的 hash。這樣不用像 garbage collector 在執行 garbage collection 後，要將剩下活著的資料搬到其它 region。
這作法常見情境只需呼叫一次 get，偶而會需要 2 ~ N 個 get + 1 個 set + 1 個 delete。比較貴的操作是 invalidate，需要 N 個 delete，所以比較適合用在不常更新的資料。
總結
要提供 scalable 和穩定的 cache 服務，架構上需要：
- server 用 shared local cache (partition / sharding) 確保每個 key 只有一個節點可寫入。
- local cache 使用 Caffeine async load 確保忽然有大量同筆 key 的查詢時，只會對後端發出一次請求。
- local cache 後面接一層 shared external cache server (Redis)，減少 database 的負擔以及處理重開 server 的負載。
- Redis 可用 generational hashes 節省記憶體空間。
- 針對可接受 stale data 且費時的操作，用 Caffeine refresh 省時。
