NoSQL 與 Redis 快取

為何需要 NoSQL 與分類比較 基礎

關聯式資料庫擅長強一致的交易與彈性查詢，但在以下情境會吃力：

• 寫入量與資料量超過單機：RDBMS 的水平擴展（分庫分表）需要大量應用層工作；許多 NoSQL 從設計之初就是分散式、可自動分片。
• 極低延遲：記憶體型 KV（Redis）可做到次毫秒級讀寫，適合請求熱路徑。
• Schema 多變或半結構化：使用者屬性、事件 payload 欄位常變，document model 更自然。
• 特殊存取模式：全文檢索、時間序列、圖關係、超寬表、海量分析聚合。
• 可用性優先：跨機房、分區時仍要能寫（Cassandra、DynamoDB 的設計取向）。

NoSQL 的代價通常是：放棄或弱化跨列 / 跨分區交易、JOIN 能力弱、一致性模型較複雜（最終一致）、必須依查詢模式設計資料模型（query-driven modeling），事後新增查詢方式很痛苦。

分類與代表產品

主要產品比較

SQL vs NoSQL 選型決策

Redis 為何單執行緒仍然很快 高頻

Redis 處理命令的核心是單執行緒事件迴圈（event loop），但它在一般硬體上單實例仍可做到每秒約 10 萬等級的簡單命令（使用 pipeline 時更高，實際依硬體與命令而定）。原因：

1. 純記憶體操作：大部分命令只是記憶體中的雜湊查找與指標操作，耗時在微秒以下，瓶頸通常是網路與系統呼叫，不是 CPU。
2. I/O 多工（I/O multiplexing）：用 epoll（Linux）/ kqueue（BSD/macOS）同時監聽上萬個 socket，只處理就緒的連線，一個執行緒就能服務大量連線（Reactor 模式）。
3. 單執行緒避免鎖與 context switch：資料結構不需加鎖，沒有鎖競爭與執行緒切換開銷，每個命令天然原子。
4. 高效的資料結構與編碼：SDS、listpack、intset、skiplist，小資料用緊湊編碼省記憶體並提升 CPU cache 命中。
5. 簡單的協定：RESP 協定易於解析。

不是「完全」單執行緒：背景執行緒處理 AOF fsync、關閉檔案、UNLINK / FLUSHALL ASYNC 的惰性釋放（lazy free，4.0+）；RDB 與 AOF rewrite 用 fork 子行程。Redis 6.0 引入 I/O threads：多個執行緒負責 socket 讀寫與協定解析，命令執行仍是單執行緒，用來緩解大量連線時網路 I/O 成為瓶頸的問題（io-threads 預設為 1，即不開啟）。

Redis 資料結構、底層編碼與典型用例 高頻 深入

Redis 對外的型別（type）與內部的編碼（encoding）是分離的：同一型別在資料小的時候用緊湊編碼（省記憶體、CPU cache 友善），超過閾值自動轉換成適合大量資料的編碼。用 OBJECT ENCODING key 可查看。以下以 Redis 7.x 為準（7.0 起以 listpack 取代 ziplist）。

String 與 SDS

Redis 不直接用 C 字串，而是 SDS（Simple Dynamic String）：結構中記錄 len 與 alloc。好處：(1) O(1) 取長度；(2) 二進位安全（可存 \0，能放圖片、protobuf）；(3) 追加時預先多配置空間（小於 1MB 時加倍、超過則每次多 1MB），減少 realloc；(4) 防止緩衝區溢位。embstr 把 redisObject 與 SDS 放在同一塊連續記憶體，一次配置、cache 友善。

緊湊編碼：listpack / intset

listpack 是一塊連續記憶體，元素依序緊密排列，每個元素記錄自身長度（取代舊的 ziplist；ziplist 每個元素記錄「前一個元素長度」，插入時可能觸發連鎖更新（cascade update），listpack 解決了這個問題）。小資料時查找雖是 O(N)，但 N 很小且記憶體連續，實際比雜湊表快、且省下大量指標開銷。這也是為什麼把大量小物件組織成多個小 hash（例如把 user:1000～user:1099 放進同一個 hash bucket）可以大幅省記憶體。

ZSet 為何用 skiplist 而不是平衡樹

大 ZSet 同時使用兩種結構：hashtable（member → score，O(1) 取分數）與 skiplist（依 score 排序，支援範圍查詢與排名）。

跳躍表是多層有序鏈結串列，每個節點以機率（Redis 用 p = 1/4）晉升到上一層，查找從最高層開始往右走、走不動就往下，期望時間 O(log N)。選擇它而非紅黑樹 / AVL 的理由（作者 antirez 曾公開說明）：

• 範圍查詢簡單高效：ZRANGEBYSCORE 找到起點後沿最底層鏈結串列往後走即可；平衡樹需要中序走訪。
• 實作與除錯簡單：沒有旋轉、重新著色等複雜操作；插入刪除只影響局部指標。
• 記憶體可調：平均每節點的指標數由 p 決定，p = 1/4 時平均約 1.33 個，比平衡樹的 2 個指標少。
• 容易支援排名：每層前進指標記錄跨度（span），ZRANK 可在 O(log N) 算出排名。
• 單執行緒下不需要考慮併發；若要無鎖併發，跳躍表也比平衡樹容易實作（Java 的 ConcurrentSkipListMap）。

典型用例指令

# 排行榜：活動中各創意的點擊數
ZINCRBY leaderboard:camp:7 1 creative:42
ZREVRANGE leaderboard:camp:7 0 9 WITHSCORES       # Top 10
ZREVRANK leaderboard:camp:7 creative:42             # 某創意的名次（0 起算）

# UV 計數（近似）：每個活動今天的不重複使用者數，每個 key 最多約 12KB
PFADD uv:camp:7:20261103 user:a user:b user:c
PFCOUNT uv:camp:7:20261103
PFMERGE uv:camp:7:week uv:camp:7:20261101 uv:camp:7:20261102 uv:camp:7:20261103

# Bitmap：使用者每日活躍（user 有整數序號時），1 億使用者只需約 12MB
SETBIT active:20261103 1234567 1
BITCOUNT active:20261103                            # 當日活躍人數
BITOP AND active:both active:20261102 active:20261103   # 連續兩天都活躍

# 去重：同一曝光的點擊只算一次（SET NX + 過期）
SET dedup:click:imp_9f2c 1 NX EX 86400              # 回傳 OK 代表第一次，nil 代表重複

# Session
HSET session:abc123 user_id 42 role admin
EXPIRE session:abc123 1800

# Stream：輕量事件佇列 + consumer group
XADD events * type click campaign 7
XGROUP CREATE events billing $ MKSTREAM
XREADGROUP GROUP billing worker-1 COUNT 10 BLOCK 2000 STREAMS events >
XACK events billing 1730600000000-0

# Geo
GEOADD stores 121.5654 25.0330 taipei101
GEOSEARCH stores FROMLONLAT 121.56 25.03 BYRADIUS 2 km ASC

過期、淘汰與持久化 高頻

過期策略：惰性刪除 + 定期刪除

設了 TTL 的 key 存在一個 expires 字典中。Redis 不會為每個 key 設計時器（成本太高），而是兩種策略並用：

惰性刪除（lazy expiration）

存取 key 時才檢查是否過期，過期就刪除並回傳不存在。CPU 友善，但從不被存取的過期 key 會一直佔記憶體。

定期刪除（active expiration）

背景週期任務（頻率由 hz 決定，預設 10 次 / 秒）每次從設有 TTL 的 key 中隨機取樣一批（經典實作為 20 個），刪除其中過期者；若過期比例超過 25% 就繼續下一輪，並有時間上限避免阻塞。可用 active-expire-effort 調整積極程度。

兩者結合仍可能有過期 key 殘留，最後由記憶體淘汰兜底。從庫不主動刪除過期 key，而是等主庫刪除後傳來 DEL（從庫讀取時會依 TTL 判斷回傳不存在，3.2+）。

淘汰策略（maxmemory-policy）

記憶體用量達到 maxmemory 時依策略淘汰：

近似 LRU：精確 LRU 需要雙向鏈結串列，每次存取都移動節點，記憶體與 CPU 開銷大。Redis 在每個物件存 24-bit 的最後存取時間，淘汰時隨機取樣 maxmemory-samples（預設 5）個 key，放入一個淘汰候選池（eviction pool，大小 16），淘汰其中最久未使用的。取樣數調到 10 已非常接近真正的 LRU。LFU 則把同一個 24-bit 欄位拆成 16-bit 時間 + 8-bit 對數計數器（Morris counter，機率性遞增，最大 255），並隨時間衰減（lfu-decay-time），解決 LRU 被一次性批次掃描污染的問題。

持久化：RDB vs AOF vs 混合

• AOF rewrite：日誌會無限增長（對同一 key INCR 一萬次），BGREWRITEAOF fork 子行程依目前資料產生最精簡的命令集合。Redis 7.0 起採用 multi-part AOF（base 檔 + 增量檔 + manifest），避免舊版 rewrite 期間雙寫緩衝的記憶體與 I/O 開銷。
• 混合持久化（aof-use-rdb-preamble yes，5.0 起預設開啟）：AOF rewrite 時 base 部分以 RDB 格式寫入，之後的增量用 AOF 格式。兼顧恢復速度與資料完整性。
• 建議：純快取可只開 RDB 甚至都不開；當作重要資料存放時開 AOF everysec + RDB 定期備份到異地（S3）。

# redis.conf 常用設定（快取型實例）
maxmemory 12gb
maxmemory-policy allkeys-lfu
maxmemory-samples 10

save 3600 1 300 100 60 10000      # RDB：3600 秒內至少 1 次寫入、或 300 秒 100 次、或 60 秒 10000 次即快照
appendonly yes
appendfsync everysec
aof-use-rdb-preamble yes

lazyfree-lazy-eviction yes         # 淘汰、過期、DEL 時在背景執行緒釋放記憶體
lazyfree-lazy-expire yes
lazyfree-lazy-user-del yes
slowlog-log-slower-than 10000      # 微秒，超過 10ms 記入 slowlog
io-threads 4                       # 6.0+，網路 I/O 多執行緒（依 CPU 核心數調整）

複製、Sentinel 與 Redis Cluster 進階

主從複製

1. 從庫發送 PSYNC replid offset。第一次或無法續傳時，主庫執行 全量同步：BGSAVE 產生 RDB 傳給從庫（或 diskless 直接走 socket），期間的新寫入存在複製緩衝區，之後補傳。
2. 之後主庫把每個寫命令非同步串流給從庫（命令傳播）。
3. 斷線重連時，若從庫的 offset 仍在主庫的 replication backlog（環狀緩衝區，repl-backlog-size 預設 1MB）內，就只做部分同步；否則全量同步。寫入量大的系統要把 backlog 調大，避免頻繁全量同步打爆主庫。

Sentinel：自動故障轉移

Sentinel 是一組（至少 3 個、部署在不同機器）監控行程：

• 主觀下線（SDOWN）：單一 Sentinel 在 down-after-milliseconds 內沒收到主庫有效回應。
• 客觀下線（ODOWN）：達到 quorum 個 Sentinel 都認為主庫下線。
• Sentinel 之間以類 Raft 的方式選出 leader，由 leader 挑選最合適的從庫（優先順序、複製 offset 最大、run ID）提升為主庫，並通知其他從庫與客戶端。
• 客戶端向 Sentinel 詢問目前主庫位址（redis-py 有 Sentinel 類別）。

Sentinel 只解決高可用，不解決容量與寫入擴展——所有資料仍在單一主庫。

Redis Cluster

• key 空間分成 16384 個 hash slot，slot = CRC16(key) mod 16384，每個 master 負責一部分 slot，各有自己的 replica。無中心節點，節點間透過 cluster bus（資料埠 + 10000）以 gossip 協定交換狀態與故障偵測，master 故障時由其他 master 投票讓其 replica 接手。
• 為什麼是 16384：節點心跳封包要攜帶自己負責哪些 slot 的 bitmap，16384 bits = 2KB，若用 65536 則要 8KB，心跳開銷太大；而官方建議叢集不超過約 1000 個節點，16384 個 slot 已足夠細分。
• MOVED 重新導向：客戶端送到錯誤節點時，回 MOVED 3999 10.0.0.2:6379，表示該 slot 已永久屬於別的節點，客戶端應更新本地 slot 對照表。
• ASK 重新導向：slot 正在遷移中，該 key 已搬到目標節點，客戶端應「這一次」對目標節點先送 ASKING 再送命令，但不更新對照表。
• Hash tag：key 中 {...} 內的部分才參與雜湊，例如 user:{42}:profile 與 user:{42}:freq 會落在同一 slot。多 key 命令（MGET、SUNION）、交易與 Lua script 要求所有 key 在同一 slot，否則回 CROSSSLOT 錯誤。注意濫用 hash tag 會造成資料傾斜。
• 限制：只能用 db 0；跨 slot 的多 key 操作受限；擴縮容需要遷移 slot（redis-cli --cluster reshard）。

Pipeline、Transaction、Lua 與 Big key / Hot key 高頻

三者比較

MULTI/EXEC 為何不回滾：

• 排隊時就發現的錯誤（命令不存在、參數數量錯）→ EXEC 時整個交易被拒絕，全部不執行。
• 執行時才發生的錯誤（例如對 string 做 LPUSH，WRONGTYPE）→ 只有該命令失敗，其他命令照常執行，沒有回滾。
• 官方理由：這類錯誤是程式 bug，應在開發階段發現；不支援回滾讓 Redis 保持簡單快速。
• WATCH key：EXEC 前若被 watch 的 key 被其他客戶端修改，EXEC 回傳 nil（交易放棄），應用程式重試——這是 CAS 樂觀鎖。

# 執行時錯誤不會回滾
MULTI
SET a 1
LPUSH a x          # 排隊成功（QUEUED），但執行時 WRONGTYPE
SET b 2
EXEC
# 1) OK
# 2) (error) WRONGTYPE Operation against a key holding the wrong kind of value
# 3) OK             → a 與 b 都被設定了

Big key 問題

常見經驗值：String 超過 10KB 以上、或集合元素超過數千～上萬個就值得注意（各團隊標準不同）。危害：

• 讀寫大 key 佔用大量網路頻寬與主執行緒時間 → 其他請求延遲飆高。
• DEL 大 key 同步釋放記憶體可能阻塞數百毫秒以上。
• Cluster 中造成記憶體傾斜；遷移 slot 時大 key 遷移阻塞。

偵測：redis-cli --bigkeys / --memkeys（以 SCAN 取樣，對線上影響小）、MEMORY USAGE key、離線分析 RDB 檔（如 redis-rdb-tools）。解法：拆分（大 hash 依欄位雜湊拆成 N 個小 hash：profile:{uid}:0..N）、只取需要的欄位（HMGET 而非 HGETALL，大集合用 HSCAN / SSCAN 漸進讀）、壓縮 value、刪除用 UNLINK。

Hot key 問題

某個 key 的 QPS 遠高於其他（例如爆紅活動的設定、首頁推薦清單），所有請求集中打到同一個 slot 所在的節點，即使叢集總容量足夠也會單點過載。偵測：redis-cli --hotkeys（需 LFU 淘汰策略）、客戶端或 proxy 統計、MONITOR（成本高，只能短暫使用）。解法：

• 本地快取（L1）：在應用程式行程內快取熱 key 幾秒鐘，最有效。
• Key 複製分散：寫入 hot:key:0 ～ hot:key:9 十份副本（落在不同 slot），讀取時隨機挑一份。
• 讀寫分離：讀請求分散到 replica（需接受複製延遲）。
• 熱點寫入（例如全域計數器）：在應用程式端先聚合再批次寫入，或拆成多個子計數器。

Redis 分散式鎖 高頻 深入

多個服務實例需要互斥地執行某件事（例如同一廣告主的結算任務只能一個 worker 跑、快取重建只讓一個請求去查 DB），需要分散式鎖。正確的單實例 Redis 鎖有三個要點：

1. 原子地「不存在才設定 + 設過期」：SET lock:key <token> NX PX 30000。不能分開寫 SETNX 再 EXPIRE——中間當機會留下永不過期的死鎖。
2. value 是唯一值（token，例如 UUID）：用來辨識鎖的擁有者。
3. 釋放時用 Lua 比對 token 再刪除：避免誤刪別人的鎖。情境：A 拿到鎖但執行超過 30 秒，鎖過期，B 取得鎖；A 完成後直接 DEL 就會刪掉 B 的鎖。「GET 比對再 DEL」兩步驟不是原子的，必須用 Lua。

import time
import uuid
import redis

r = redis.Redis(host="localhost", port=6379, decode_responses=True)

RELEASE_LUA = """
if redis.call('GET', KEYS[1]) == ARGV[1] then
  return redis.call('DEL', KEYS[1])
end
return 0
"""
EXTEND_LUA = """
if redis.call('GET', KEYS[1]) == ARGV[1] then
  return redis.call('PEXPIRE', KEYS[1], ARGV[2])
end
return 0
"""
release_script = r.register_script(RELEASE_LUA)   # 內部用 EVALSHA，script 只傳一次
extend_script = r.register_script(EXTEND_LUA)

class RedisLock:
    def __init__(self, client: redis.Redis, name: str, ttl_ms: int = 30_000):
        self.r, self.key, self.ttl_ms = client, f"lock:{name}", ttl_ms
        self.token = uuid.uuid4().hex

    def acquire(self, wait_s: float = 5.0) -> bool:
        deadline = time.monotonic() + wait_s
        while time.monotonic() < deadline:
            if self.r.set(self.key, self.token, nx=True, px=self.ttl_ms):
                return True
            time.sleep(0.05)                   # 簡單輪詢；可加 jitter
        return False

    def extend(self) -> bool:                  # 看門狗（watchdog）定期延長，避免任務未完成鎖就過期
        return bool(extend_script(keys=[self.key], args=[self.token, self.ttl_ms]))

    def release(self) -> bool:
        return bool(release_script(keys=[self.key], args=[self.token]))

    def __enter__(self):
        if not self.acquire():
            raise TimeoutError(f"could not acquire {self.key}")
        return self

    def __exit__(self, *exc):
        self.release()

with RedisLock(r, "settle:advertiser:3"):
    pass  # 執行結算；長任務需在背景執行緒定期呼叫 extend()

# redis-py 也內建 r.lock("name", timeout=30, blocking_timeout=5)，原理相同（token + Lua 釋放）

Redlock 與其爭議

單實例鎖的問題：主庫取得鎖後，尚未複製到從庫就當機，從庫升為主庫後鎖不見了，另一個客戶端可以再拿到鎖。Redlock（antirez 提出）：使用 N 個（通常 5 個）彼此獨立的 Redis master，客戶端依序向所有節點請求鎖，在有效時間內取得多數（≥ N/2 + 1）才算成功，鎖的有效時間要扣除取鎖耗時。

Martin Kleppmann 的批評（《How to do distributed locking》）：

• 任何基於租約（lease / TTL）的鎖，都可能因為 GC 停頓、行程暫停、網路延遲，讓客戶端在鎖已過期後仍以為自己持有鎖。這不是 Redlock 特有，但 Redlock 無法解決。
• Redlock 依賴各節點的時鐘大致正確（時鐘跳躍會讓鎖提早過期）。
• 正確性要求高的場景需要 fencing token：鎖服務每次發放單調遞增的編號，受保護的資源（例如儲存系統）拒絕比已見過更舊的編號。Redlock 沒有提供單調遞增的 token。
• 結論：若鎖只是為了效率（避免重複工作，偶爾重複也無妨），單一 Redis 鎖就夠了；若是為了正確性，應使用基於共識的系統（ZooKeeper、etcd，提供 zxid / revision 可當 fencing token），並讓下游支援 fencing。

antirez 也發表了回應，認為在合理的系統模型假設下 Redlock 是安全的。面試時能把雙方論點與「效率 vs 正確性」的結論講清楚即可。

快取模式與一致性 高頻 深入

快取的本質是「用可能過時的資料換取速度」。設計時要先回答：能容忍多久的不一致？快取掛了系統還能撐嗎？

四種常見模式

為什麼是「刪除」快取，而不是「更新」快取？

• 併發寫入的順序問題：A 寫 DB = 1、B 寫 DB = 2、B 更新快取 = 2、A 更新快取 = 1 → 快取停在舊值 1，直到過期。刪除是冪等的，沒有順序問題。
• 懶計算：快取值可能需要 JOIN 多張表計算，若資料寫多讀少，每次寫都重算是浪費；刪除後等下次讀再算。

為什麼「先更新 DB，再刪快取」？

若先刪快取再更新 DB：A 刪快取 → B 讀取 miss、從 DB 讀到舊值並回填快取 → A 更新 DB。結果快取裡是舊值，而且會一直存在到 TTL 過期。因為「讀 DB + 寫快取」通常比「寫 DB」快，這個競爭很容易發生。

先更新 DB 再刪快取仍有一個極端情況：快取剛好過期 → A 讀 DB 拿到舊值 → B 更新 DB 並刪除快取 → A 把舊值寫入快取。這需要「A 的讀 DB + 寫快取」橫跨「B 的寫 DB + 刪快取」整段，而寫 DB 通常比讀慢得多，機率很低。這也是業界（Facebook 的 memcache 論文中也採用 delete-on-write）普遍選擇此順序的原因。

進一步強化一致性

一律設 TTL

最後一道防線：即使出現不一致，最多維持 TTL 時間。

延遲雙刪（delayed double delete）

先刪快取 → 更新 DB → 等待一小段時間（大於一次「讀 DB + 回填」的時間，例如數百毫秒）→ 再刪一次。第二次刪除清掉併發讀回填的舊值。缺點：延遲時間難以精確估計、增加寫入延遲（通常非同步執行第二次刪除）。

刪除失敗重試

「更新 DB 成功、刪快取失敗」也會不一致。把刪除失敗的 key 送進訊息佇列重試。

訂閱 binlog 失效（CDC）

應用程式只寫 DB；由 Canal / Debezium / Maxwell 訂閱 MySQL binlog，解析出變更的列後刪除對應快取 key，失敗可重試。優點：與業務程式碼解耦、不會漏刪（任何寫入 DB 的路徑都會被捕捉，包括手動修資料）；缺點：多一套基礎設施、有毫秒到秒級延遲。

版本號 / 時間戳

快取值帶版本，寫入快取時用 Lua 比較版本，只接受更新的版本。

需要強一致時

不要快取，或讀取關鍵資料時直接讀 DB 主庫；或用分散式鎖序列化同一 key 的讀寫（代價高）。

快取穿透、擊穿、雪崩與多級快取 高頻

import json
import random
import threading
import time
from typing import Any, Callable, Optional

import redis

r = redis.Redis(decode_responses=True)
NULL_SENTINEL = "__NULL__"

class SingleFlight:
    """同一行程內：相同 key 的併發載入只執行一次，其他執行緒等待並共享結果（Go 的 singleflight 概念）。"""
    def __init__(self):
        self._lock = threading.Lock()
        self._calls: dict[str, dict] = {}

    def do(self, key: str, fn: Callable[[], Any]) -> Any:
        with self._lock:
            call = self._calls.get(key)
            if call is None:
                call = {"event": threading.Event(), "result": None, "error": None}
                self._calls[key] = call
                leader = True
            else:
                leader = False
        if not leader:
            call["event"].wait()
            if call["error"]:
                raise call["error"]
            return call["result"]
        try:
            call["result"] = fn()
        except Exception as e:
            call["error"] = e
            raise
        finally:
            with self._lock:
                self._calls.pop(key, None)
            call["event"].set()
        return call["result"]

sf = SingleFlight()

def ttl_with_jitter(base: int) -> int:
    return base + random.randint(0, base // 10)          # 防雪崩：TTL 加 0～10% 隨機

def get_cached(key: str, loader: Callable[[], Optional[dict]], ttl: int = 300) -> Optional[dict]:
    raw = r.get(key)
    if raw is not None:
        return None if raw == NULL_SENTINEL else json.loads(raw)

    def load():
        # 跨行程的互斥：只有拿到 Redis 鎖的實例去查 DB（防擊穿）
        lock_key = f"rebuild:{key}"
        if r.set(lock_key, "1", nx=True, ex=10):
            try:
                value = loader()
                if value is None:                          # 防穿透：快取空值，短 TTL
                    r.set(key, NULL_SENTINEL, ex=60)
                else:
                    r.set(key, json.dumps(value), ex=ttl_with_jitter(ttl))
                return value
            finally:
                r.delete(lock_key)
        # 沒拿到鎖：短暫等待後重讀快取（也可直接回舊值 / 預設值）
        for _ in range(20):
            time.sleep(0.05)
            raw2 = r.get(key)
            if raw2 is not None:
                return None if raw2 == NULL_SENTINEL else json.loads(raw2)
        return loader()                                    # 最後手段：降級直接查

    return sf.do(key, load)                                # 行程內再合併一次

多級快取與 local cache vs distributed cache

多級快取：L1 本地快取（短 TTL，如 1～10 秒）→ L2 Redis（分鐘級）→ DB。L1 擋掉熱 key 與 Redis 故障時的部分流量（防雪崩），L2 提供共享與容量。L1 的失效可透過 Redis Pub/Sub 廣播「key X 已變更」，或只依賴短 TTL。Redis 6.0 的 client-side caching（CLIENT TRACKING）讓伺服器在 key 變更時主動通知客戶端失效本地副本。

from cachetools import TTLCache
import threading

_l1 = TTLCache(maxsize=10_000, ttl=5)      # 5 秒本地快取
_l1_lock = threading.Lock()                 # cachetools 本身非執行緒安全

def get_campaign_config(campaign_id: int) -> dict:
    key = f"camp:cfg:{campaign_id}"
    with _l1_lock:
        if key in _l1:
            return _l1[key]
    value = get_cached(key, lambda: load_campaign_from_db(campaign_id), ttl=600)  # L2 + DB
    with _l1_lock:
        _l1[key] = value
    return value

MongoDB：文件模型、索引、聚合與複製分片 進階

MongoDB 以 BSON 文件儲存資料（單一文件上限 16MB），集合（collection）中的文件不強制相同結構。預設儲存引擎 WiredTiger 使用 B-tree、文件層級併發控制與壓縮。4.0 起支援 replica set 上的多文件 ACID 交易，4.2 起支援分片叢集上的交易（但成本較高，設計上仍應以單文件原子性為主）。

嵌入（embedding）vs 引用（referencing）

經驗法則：依存取模式設計；避免無界陣列（unbounded array）——文件會越來越大，可能觸及 16MB 上限並讓每次更新成本變高。時間序列資料可用 bucket pattern（每小時一個文件，內含該小時的事件陣列）或 5.0+ 的 time series collection。

{
  "_id": {"$oid": "6727a1c2e4b0a1b2c3d4e5f6"},
  "advertiser_id": 3,
  "name": "Black Friday 2026",
  "status": "active",
  "daily_budget_micros": 500000000,
  "targeting": {
    "countries": ["TW", "JP"],
    "devices": ["ios", "android"],
    "segments": ["sports_fan", "high_value"]
  },
  "creatives": [
    {"id": 101, "format": "banner_320x50"},
    {"id": 102, "format": "video_15s"}
  ],
  "updated_at": {"$date": "2026-11-03T02:00:00Z"}
}

索引

• 種類：單欄位、複合索引、multikey（陣列欄位，每個元素一個索引項）、text、2dsphere（地理）、hashed（用於 hashed sharding）、TTL 索引（自動刪除過期文件，適合 session、暫存資料）、部分索引（partial）、wildcard。
• 複合索引順序遵循 ESR 規則：Equality（等值）→ Sort（排序）→ Range（範圍），與 MySQL 的「等值在前、範圍在後」概念一致。
• 用 .explain("executionStats") 看 IXSCAN vs COLLSCAN、totalKeysExamined、totalDocsExamined 與 nReturned 的比例。

Aggregation pipeline 範例

from datetime import datetime, timedelta, timezone
from pymongo import ASCENDING, DESCENDING, MongoClient, WriteConcern
from pymongo.read_concern import ReadConcern

client = MongoClient("mongodb://mongo-0,mongo-1,mongo-2/?replicaSet=rs0",
                     maxPoolSize=50, w="majority", readPreference="secondaryPreferred")
db = client.ads

# 索引：ESR → campaign_id（等值）、ts（排序 / 範圍）
db.events.create_index([("campaign_id", ASCENDING), ("ts", DESCENDING)])
db.sessions.create_index("expire_at", expireAfterSeconds=0)        # TTL 索引

# 每個活動昨天的曝光、點擊、CTR，取前 10
start = datetime.now(timezone.utc).replace(hour=0, minute=0, second=0, microsecond=0) - timedelta(days=1)
end = start + timedelta(days=1)
pipeline = [
    {"$match": {"ts": {"$gte": start, "$lt": end}}},              # 先過濾，盡量放最前面以利用索引
    {"$group": {
        "_id": "$campaign_id",
        "impressions": {"$sum": {"$cond": [{"$eq": ["$type", "imp"]}, 1, 0]}},
        "clicks": {"$sum": {"$cond": [{"$eq": ["$type", "click"]}, 1, 0]}},
    }},
    {"$addFields": {"ctr": {"$cond": [
        {"$gt": ["$impressions", 0]},
        {"$divide": ["$clicks", "$impressions"]},
        None]}}},
    {"$sort": {"ctr": -1}},
    {"$limit": 10},
    {"$lookup": {"from": "campaigns", "localField": "_id",           # 類似 LEFT JOIN
                 "foreignField": "_id", "as": "campaign"}},
    {"$unwind": "$campaign"},
    {"$project": {"_id": 0, "campaign_id": "$_id", "name": "$campaign.name",
                  "impressions": 1, "clicks": 1, "ctr": 1}},
]
for row in db.events.aggregate(pipeline, allowDiskUse=True):
    print(row)

# 單文件原子更新：頻次計數 +1，不存在就建立
db.freq.update_one({"_id": "u42:c7:20261103"},
                   {"$inc": {"count": 1}, "$setOnInsert": {"expire_at": end + timedelta(days=1)}},
                   upsert=True)

# 指定 write concern / read concern
orders = db.get_collection("billing",
                           write_concern=WriteConcern(w="majority", j=True, wtimeout=5000),
                           read_concern=ReadConcern("majority"))

Replica set 與 write / read concern

Replica set：一個 primary 接收寫入，secondaries 透過複製 oplog 同步；primary 失聯時，其餘成員以類 Raft 協定選出新 primary（需要多數票，所以建議奇數個成員，至少 3 個）。

想要 read-your-writes：用 causally consistent session，搭配 majority read / write concern。

分片（sharding）

架構：mongos（查詢路由）+ config servers（儲存 metadata，本身是 replica set）+ 多個 shard（各自是 replica set）。資料依 shard key 切成 chunk（範圍），由 balancer 在 shard 間搬移以平衡。

• Ranged sharding：範圍查詢有效率，但單調遞增的 key（時間戳、ObjectId）會讓所有寫入集中到最後一個 chunk（熱點）。
• Hashed sharding：寫入均勻，但範圍查詢要廣播到所有 shard。
• 查詢帶 shard key → targeted query（只打一個 shard）；不帶 → scatter-gather。
• 好的 shard key：高基數、分布均勻、不單調、符合主要查詢模式。常用複合 shard key 如 {advertiser_id: 1, _id: 1}。5.0+ 支援 reshard，但仍是重量級操作。

Cassandra、LSM tree 與 DynamoDB 深入

LSM tree vs B+ tree

LSM tree（Log-Structured Merge tree）是 Cassandra、ScyllaDB、HBase、RocksDB、LevelDB 的核心。想法：把所有寫入轉成順序寫。

1. 寫：先追加到 commit log（持久性），再寫入記憶體中的 memtable（例如 skiplist），就可以回應。沒有隨機寫、沒有讀取舊頁。
2. Flush：memtable 滿了就整個寫成磁碟上一個不可變（immutable）、按 key 排序的 SSTable 檔。
3. 讀：依序查 memtable → 由新到舊的 SSTable；每個 SSTable 有 bloom filter（快速排除不含此 key 的檔案）與稀疏索引。
4. 更新與刪除：不修改舊檔，而是寫入新版本或墓碑（tombstone），讀取時以最新時間戳為準。
5. Compaction：背景合併多個 SSTable，丟棄舊版本與已過寬限期的墓碑，減少讀取時要查的檔案數。

Compaction 策略取捨：Size-Tiered（STCS）寫放大低、讀與空間放大高；Leveled（LCS）讀放大低、寫放大高，適合讀多；Time-Window（TWCS）按時間視窗分組，整個視窗過期時可直接刪除整個檔案，最適合帶 TTL 的時間序列。

Cassandra 資料模型與 partition key 設計

Cassandra 是無主架構：所有節點對等，以一致性雜湊（含 vnodes）把 partition key 映射到環上，資料複製 RF 份。Primary key = partition key + clustering columns：partition key 決定資料在哪些節點，clustering columns 決定 partition 內的排序。

-- CQL：查詢「某使用者最近的廣告事件」→ 以查詢設計表（query-first）
CREATE TABLE user_events (
  user_id    text,
  day        date,             -- 加入日期作為 partition key 的一部分，避免單一 partition 無限增長
  ts         timeuuid,
  campaign_id bigint,
  event_type text,
  PRIMARY KEY ((user_id, day), ts)
) WITH CLUSTERING ORDER BY (ts DESC)
  AND default_time_to_live = 2592000          -- 30 天
  AND compaction = {'class': 'TimeWindowCompactionStrategy',
                    'compaction_window_unit': 'DAYS', 'compaction_window_size': 1};

SELECT * FROM user_events WHERE user_id = 'u42' AND day = '2026-11-03' LIMIT 50;
-- 不帶完整 partition key 的查詢需要 ALLOW FILTERING（全叢集掃描，線上禁用）

• Partition 不能太大（常見建議控制在約 100MB 以內）：大 partition 造成讀取慢、compaction 與修復壓力、節點熱點。用「時間分桶」（(user_id, day)）切小。
• 分布要均勻：避免以低基數欄位（國家、狀態）為 partition key。
• 反正規化、一個查詢一張表：同一份資料依不同查詢寫入多張表。
• 墓碑陷阱：大量刪除或把欄位設為 null 會產生墓碑，讀取時要掃過它們，過多會導致查詢逾時（tombstone_failure_threshold）。佇列型用法（寫入後馬上刪除）是 Cassandra 反模式。

可調一致性（tunable consistency）

每個請求可指定一致性等級：ONE、QUORUM（RF/2 向下取整 + 1）、LOCAL_QUORUM（只在本機房取多數，跨機房常用）、ALL 等。規則：R + W > RF 時，讀寫的副本集合必定重疊，能讀到最新寫入。例如 RF = 3，讀寫都用 QUORUM（2）→ 2 + 2 > 3。追求低延遲可用 W = ONE、R = ONE，換取最終一致。修復機制：hinted handoff（暫存給故障節點的寫入）、read repair、定期 anti-entropy repair（Merkle tree 比對）。衝突解決採 last-write-wins（以時間戳為準），所以時鐘同步很重要。

DynamoDB 單表設計概念

DynamoDB 是 AWS 全託管的 KV / document 資料庫。主鍵為 partition key（簡單主鍵）或 partition key + sort key（複合主鍵）。查詢只能高效地「依 partition key 取得，並依 sort key 範圍篩選」（Query），否則只能 Scan 全表。單一項目上限 400KB；單一實體 partition 有吞吐上限（官方文件為每秒 3000 RCU / 1000 WCU），所以 partition key 必須分散。

單表設計（single-table design）：因為沒有 JOIN，把多種實體放進同一張表，用通用的 PK / SK 欄位與前綴「預先 JOIN」，讓一次 Query 就拿回一個存取模式需要的所有資料：

其他存取模式用 GSI（Global Secondary Index），例如以 status + updated_at 建 GSI 找出所有 active 活動（GSI 是非同步更新，只支援最終一致讀）。缺點：模型很難理解與演進、新增存取模式可能需要回填資料。原則：先列出所有存取模式，再設計鍵。

Bloom filter 原理與 Python 實作 進階

Bloom filter 是一種空間效率極高的機率型資料結構，回答「這個元素可能存在」或「一定不存在」。沒有 false negative，只有 false positive。

• 結構：一個 m 位元的位元陣列 + k 個獨立雜湊函數。
• 加入：對元素算 k 個雜湊值，把對應的 k 個位元設為 1。
• 查詢：k 個位元全為 1 → 可能存在；任一為 0 → 一定不存在。
• 誤判率：p ≈ (1 − e^−kn/m)^k；給定 n 與目標 p，最佳 m = −n·ln p / (ln 2)²、k = (m/n)·ln 2。p = 1% 時每個元素約需 9.6 bits、k ≈ 7。一億個元素、1% 誤判率約需 120MB，比存原始 key 小得多。
• 不支援刪除（把位元清 0 可能影響其他元素）。需要刪除用 Counting Bloom filter（每格改為計數器）或 Cuckoo filter。元素數超過設計容量時誤判率急升，可用 Scalable Bloom filter。
• 應用：快取穿透防護、LSM tree 的 SSTable 過濾、爬蟲 URL 去重、推薦系統「已曝光過的內容」過濾、Chrome 舊版惡意網址檢查。

import hashlib
import math

class BloomFilter:
    def __init__(self, capacity: int, error_rate: float = 0.01):
        self.m = math.ceil(-capacity * math.log(error_rate) / (math.log(2) ** 2))  # 位元數
        self.k = max(1, round(self.m / capacity * math.log(2)))                  # 雜湊函數數
        self.bits = bytearray((self.m + 7) // 8)

    def _positions(self, item: str):
        # Kirsch–Mitzenmacher 技巧：用兩個雜湊值組合出 k 個：h_i = h1 + i * h2 (mod m)
        digest = hashlib.blake2b(item.encode(), digest_size=16).digest()
        h1 = int.from_bytes(digest[:8], "little")
        h2 = int.from_bytes(digest[8:], "little") | 1     # 確保為奇數，避免週期過短
        return ((h1 + i * h2) % self.m for i in range(self.k))

    def add(self, item: str) -> None:
        for pos in self._positions(item):
            self.bits[pos >> 3] |= 1 << (pos & 7)

    def __contains__(self, item: str) -> bool:
        return all(self.bits[pos >> 3] & (1 << (pos & 7)) for pos in self._positions(item))

if __name__ == "__main__":
    bf = BloomFilter(capacity=100_000, error_rate=0.01)
    print(f"m={bf.m} bits ({bf.m / 8 / 1024:.1f} KiB), k={bf.k}")   # 約 117 KiB, k=7
    for i in range(100_000):
        bf.add(f"campaign:{i}")
    assert all(f"campaign:{i}" in bf for i in range(100_000))      # 無 false negative
    fp = sum(f"other:{i}" in bf for i in range(100_000)) / 100_000
    print(f"observed false positive rate = {fp:.4f}")              # 約 0.01

# 線上通常直接用 Redis 模組（RedisBloom；Redis 8 起內建於 Redis Open Source）
BF.RESERVE bf:campaign_ids 0.01 10000000
BF.ADD bf:campaign_ids campaign:42
BF.EXISTS bf:campaign_ids campaign:99999999    # 0 → 一定不存在，直接回 404，不查 DB
# 沒有模組時也可用 SETBIT / GETBIT 在 Redis bitmap 上自行實作（上面 _positions 的位置即 offset）

Python redis-py 實戰：連線池、Pipeline、限流、頻次控制 高頻

連線池與 pipeline

import redis

# 一個行程共用一個連線池（redis.Redis 本身執行緒安全，內部從池中借連線）
pool = redis.ConnectionPool(
    host="redis.internal", port=6379, db=0,
    max_connections=50,
    socket_timeout=0.05,           # 50ms：熱路徑要設短逾時，寧可降級也不要卡住
    socket_connect_timeout=0.2,
    health_check_interval=30,
    decode_responses=True,
)
r = redis.Redis(connection_pool=pool)
# Redis Cluster：from redis.cluster import RedisCluster; rc = RedisCluster(host=..., port=...)
# asyncio：import redis.asyncio as aioredis

# 批次取多位使用者的特徵：N 次 RTT → 1 次
def get_features(user_ids: list[str]) -> dict[str, dict]:
    pipe = r.pipeline(transaction=False)          # 不需要 MULTI/EXEC 時關掉 transaction
    for uid in user_ids:
        pipe.hmget(f"feat:{uid}", "segments", "ctr_7d", "last_seen")
    results = pipe.execute()
    return {uid: dict(zip(("segments", "ctr_7d", "last_seen"), vals))
            for uid, vals in zip(user_ids, results)}

# WATCH + MULTI 樂觀鎖（CAS）：只有在餘額足夠時扣款
def deduct(key: str, amount: int) -> bool:
    with r.pipeline() as pipe:
        while True:
            try:
                pipe.watch(key)
                balance = int(pipe.get(key) or 0)
                if balance < amount:
                    pipe.unwatch()
                    return False
                pipe.multi()
                pipe.decrby(key, amount)
                pipe.execute()                    # key 被別人改過會拋 WatchError
                return True
            except redis.WatchError:
                continue                          # 重試（實務上應限制次數）

滑動視窗限流（ZSet + Lua）

固定視窗（INCR + EXPIRE）簡單但在視窗邊界可能放行 2 倍流量；滑動視窗日誌用 ZSet 記錄每次請求的時間戳，精確但記憶體與請求數成正比。整段邏輯用 Lua 保證原子性。

import time
import uuid

SLIDING_WINDOW_LUA = """
local key    = KEYS[1]
local now    = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local limit  = tonumber(ARGV[3])
local member = ARGV[4]
redis.call('ZREMRANGEBYSCORE', key, 0, now - window)   -- 移除視窗外的舊紀錄
local count = redis.call('ZCARD', key)
if count < limit then
  redis.call('ZADD', key, now, member)
  redis.call('PEXPIRE', key, window)
  return {1, limit - count - 1}
end
return {0, 0}
"""
sliding_window = r.register_script(SLIDING_WINDOW_LUA)

def allow(client_id: str, limit: int = 100, window_ms: int = 60_000) -> tuple[bool, int]:
    now_ms = int(time.time() * 1000)
    allowed, remaining = sliding_window(
        keys=[f"rl:{client_id}"],
        args=[now_ms, window_ms, limit, f"{now_ms}-{uuid.uuid4().hex[:8]}"],  # member 需唯一
    )
    return bool(allowed), int(remaining)

# 用法（例如 API middleware）：
# ok, remaining = allow(api_key)
# if not ok: return 429 Too Many Requests, header Retry-After / X-RateLimit-Remaining

Appier 情境：頻次控制（frequency capping）

廣告主常要求「同一使用者每天最多看到某活動 N 次」。出價前要檢查、曝光後要累加，而且是極高 QPS。

FREQ_CAP_LUA = """
-- KEYS[1] = fc:{uid}:20261103   ARGV[1] = campaign_id   ARGV[2] = cap   ARGV[3] = ttl 秒
local current = tonumber(redis.call('HGET', KEYS[1], ARGV[1]) or '0')
if current >= tonumber(ARGV[2]) then
  return -1
end
local n = redis.call('HINCRBY', KEYS[1], ARGV[1], 1)
if n == 1 then
  redis.call('EXPIRE', KEYS[1], tonumber(ARGV[3]))
end
return n
"""
freq_cap = r.register_script(FREQ_CAP_LUA)

def fc_key(uid: str, day: str) -> str:
    return f"fc:{{{uid}}}:{day}"       # hash tag {uid}：同一使用者的 key 落在同一 slot

def can_serve(uid: str, day: str, campaign_ids: list[int], caps: dict[int, int]) -> list[int]:
    """出價前：一次取回此使用者今天所有活動的次數，過濾掉已達上限者（只讀，不累加）。"""
    counts = r.hmget(fc_key(uid, day), [str(c) for c in campaign_ids])
    return [c for c, n in zip(campaign_ids, counts) if int(n or 0) < caps[c]]

def record_impression(uid: str, day: str, campaign_id: int, cap: int) -> bool:
    """實際曝光（收到 win notice / impression beacon）後才累加。"""
    n = freq_cap(keys=[fc_key(uid, day)], args=[campaign_id, cap, 2 * 86400])
    return n != -1

• Key 設計：每位使用者每天一個 hash（欄位 = campaign_id），比「每位使用者 × 每活動一個 string key」省下大量 key 物件開銷，小 hash 走 listpack 編碼更省記憶體。Redis 7.4+ 也支援 hash 欄位層級的過期（HEXPIRE）。
• 先檢查、後累加：出價時只讀（大部分競價不會贏，不該累加）；贏標並確認曝光後才 HINCRBY。兩者之間有時間差，高併發下可能少量超過上限，業務上通常可接受。
• 容量估算：例如 1 億使用者，每人每天平均 5 個活動欄位，每個小 hash 粗估一兩百 bytes → 數十 GB 等級，需要 Redis Cluster 分片；多區域部署時各區獨立計數再非同步合併，接受最終一致。
• 降級：Redis 逾時就當作「未達上限」或「直接不出價」，取決於廣告主合約的嚴格程度。

Appier 情境：使用者 profile / feature store 低延遲查詢

以廣告平台常見做法為例：離線（Spark）每日 / 每小時計算使用者特徵與分群，串流（Flink）更新近即時特徵（最近 1 小時點擊數），兩者寫入線上 KV，供出價與推薦模型在請求時讀取。

import json

def bulk_load_features(rows, version: str, batch: int = 1000) -> None:
    """批次寫入新版本特徵：寫到帶版本的 key，全部完成後再切換指標，避免讀到一半新一半舊。"""
    pipe = r.pipeline(transaction=False)
    for i, (uid, feats) in enumerate(rows, 1):
        key = f"feat:{version}:{uid}"
        pipe.hset(key, mapping={k: json.dumps(v) for k, v in feats.items()})
        pipe.expire(key, 3 * 86400)               # 舊版本自動過期
        if i % batch == 0:
            pipe.execute()
    pipe.execute()
    r.set("feat:current_version", version)        # 原子切換

def read_features(uid: str) -> dict:
    version = r.get("feat:current_version")       # 實務上放本地快取幾秒，避免成為 hot key
    raw = r.hgetall(f"feat:{version}:{uid}")
    return {k: json.loads(v) for k, v in raw.items()}

面試自測題