---
title: "101: Cache and Redis"
---
###### tags: `jubo` `tutorials` `cache` `redis`

[TOC]

**雞肋小知識**

| | |
| -------- | -------- |
| | 
|

# Purposes of cache
- 主資料庫開始**不穩定**了，需要保護主資料庫
- 改善整體系統在資料**讀取路徑**的吞吐量

# General rules
## Pareto principle (aka. 80-20 rule)
- **假設 80% 的流量都來自 20% 的資料所貢獻**。故需要被快取的資料量可粗估就是 20% 的流量大小
- 可能合理假設加上快取的請求的流量 QPS (Query per second)
- 了解被快取的資料的 avg. byte size

**練習題**
- 假設
- 系統的 QPS 為 30
- 每筆資料的 avg. size=1024 bytes
- expire time 設為 1 天 (86400 seconds)
- 則快取系統的記憶體至少需要
- 30 (QPS) * 86400 * 1024 (bytes) * 20% ~= **0.5 GiB**

## TTL must be set
- 被快取的資料一定要給 TTL (expire time)
- 後續才有辦法估計真實用量 (會搭配可觀測性基礎建設)
- 若使用 Redis 時沒有給 TTL，預設使用 [Least Recently Used (LRU) cache](https://redis.io/topics/lru-cache) 來剔除 keys
- 這會導致在尖峰時刻，Redis 得同時忙著處理 client requests 以及 key eviction，**會傷害服務吞吐量**

# Common problems and solutions
## [Cache stampede](https://en.wikipedia.org/wiki/Cache_stampede) (踩踏)

問題來源：
- 商業情境有熱點資料 (hot key)，該資料快取過期
- 高並行流量同時存取該過期的資料，但 app tier 未正確實作 **Single Flight**
(source: https://www.cyningsun.com/01-11-2021/golang-concurrency-singleflight.html)

### Common implementation mistake

sequenceDiagram
    autonumber
    participant App    
    participant Cache
    participant DB
    App->>Cache: get cached data
    Cache-->>App: return cached data
    Note left of App: reply client (if cache hit)
    Note over App, DB: if cache miss...
    App->>DB: query data
    DB-->>App: return data
    App->>Cache: update cache
    Cache-->>App: return ack
    Note left of App: reply client

:::danger
在高並行請求下，同一瞬間會有大量的 cache miss，進而造成：
- :fire: 大量的 requests 衝進到 DB
- :fire: 大量的 cache recomputation

(source: https://www.cyningsun.com/01-11-2021/golang-concurrency-singleflight.html)
:::

### Distributed locks (for single flight)

那我們來調整一下實作邏輯：
1. 首先我們可以利用 cache server 做為 distributed lock manager
2. 在 cache miss 後、query data 前，嘗試取得 global lock
3. 拿到 lock 後，再進去 DB 拿資料
4. 並在 update cache 後歸還 lock

sequenceDiagram
    autonumber
    participant App    
    participant Cache
    participant DB    
    Note over App, DB: if cache miss...
    rect rgb(191, 223, 255)
    loop RETRY if needed*
        App->>Cache: acquire lock
        Cache-->>App: return lock
    end
    end
    App->>DB: query data
    DB-->>App: return data
    App->>Cache: update cache**
    Cache-->>App: return ack
    rect rgb(191, 223, 255)
    App->>Cache: release lock**
    Cache-->>App: return ack
    end
    Note left of App: reply client

:::info
:information_source: * **重試策略**

- 拿不到 lock 的重試策略，應考慮商業情境的需求
- 若商業情境可以接受不 retry，那就直接 reply (降低 application 複雜度)
- 直到有明確的商業情境需求作為規範再實作
- 若有需求，則應使用 [exponential backoff (with jitter) retry algorithm](https://cloud.google.com/iot/docs/how-tos/exponential-backoff) 來實作
:::

:::info
:information_source: ** **原子操作**
- 若使用 Redis，這兩個動作可考慮透過執行 [Lua script](https://redis.io/commands/eval) 將其包成 atomic operation，App 可以少實作一些錯誤處理情境
:::

:::danger
:fire: 若按照上述的循序圖實作，仍屬常見的錯誤實作。是什麼地方沒考慮到呢？
:::
:::spoiler Answer

多個 requests 遇到 cache miss 時，的確只有一筆 request 能成功拿到 lock，而**其他 requests 皆在嘗試 acquiring lock**。

當第一筆成功歸還 lock 後，**next request 拿到 lock 就又衝進 DB 了！** :fire: 造成無謂的流量繼續打在 DB 上。
:::

---

#### :bulb: 正確的實作

- 拿到 lock 之後，應**再檢查一次 cached data 是否已存在**
- 若有，直接 release lock 後回傳資料
- 若無，才進 DB 拿資料、recomputation

sequenceDiagram
    autonumber
    participant App    
    participant Cache
    participant DB    
    Note over App, DB: if cache miss...
    rect rgb(191, 223, 255)
    loop RETRY if needed
        App->>Cache: acquire lock
        Cache-->>App: return lock
    end
    end
    rect rgb(51, 204, 51)
        App->>Cache: get cached data
        Cache-->>App: return cached data
    end
    
    alt
        Note over App, DB: if cache hit...
        rect rgb(191, 223, 255)
            App->>Cache: release lock
            Cache-->>App: return ack
        end
        Note left of App: reply client
    else
        Note over App, DB: if cache miss...
        App->>DB: query data
        DB-->>App: return data
        App->>Cache: update cache
        Cache-->>App: return ack
        rect rgb(191, 223, 255)
            App->>Cache: release lock
            Cache-->>App: return ack
        end
        Note left of App: reply client
    end

## Cache penetration (穿透)

問題來源：
- 前述的 *cache stampede* 假設當 cache miss 時，database **一定有你要檢索的資料**；但 *cache penetration* 的情境是：**database 就是沒有該資料**，**所以造成大量的 cache miss** :fire:
- 另一種常見的原因是**惡意流量**，攻擊者製造許多隨機的 keys 來攻擊系統 :fire:

### Cache null
- 最簡單的想法就是把該 key 存下來，value 為 null
- :warning: **但 TTL 不能設太長**，以避免影響系統對正常用戶的可用性

### [Bloom filter](https://en.wikipedia.org/wiki/Bloom_filter)
(source: https://www.evanlin.com/BloomFilter/)

- Bloom filter 是一種[節省空間的機率型資料結構](https://en.wikipedia.org/wiki/Bloom_filter)
- 透過 bit array 以及多個 hash functions 的設計，此資料結構可提供非常輕巧的檢索功能，以降低 cache/DB 的負擔

#### 讀取路徑流程圖

flowchart LR
    S(Start) --request--> A
    A[App] --> B{Is key in bloomfilter?}
    B --> |No| A
    B --> |Yes| C{Is key in cache?}
    C --> |Yes, return cache| A
    C --> |No, check DB| D[(DB)]
    D --return query result--> A

- 我們先透過它來檢索一筆資料：
- 當它告訴我們不存在，則**一定不在**資料庫裡
- 當它告訴我們存在，則資料**可能在資料庫裡** (i.e. **有誤判率**)。此時該 request 就可以去 cache/DB 查資料
- 由於查詢結果可能會出現[誤判 (false positives)](https://en.wikipedia.org/wiki/Bloom_filter#Probability_of_false_positives)，故也需要透過調整 bit array 長度以及 hash function 數量的方式，來設計允許的誤判率

#### 但仍有問題需要考慮
- 是否有一個 **BloomFilter as a Service** 的應用實體提供給 distributed system 使用呢？
- 如何 delete 存進 Bloom Filter 的 key？

:::info
:information_source: 如何計算 BloomFilter 的 False Positive

每次檢驗某 key 的時候，會找出 k 個 bit position，當全部的 bits 皆為 1 時，該 key 很可能有在 set 裡。

問題在於：執行 k 個 hash function，每次都是 bit=1 的機率為何？

以下為推導思路：

符號定義：
- $k$ hash functions
- $n$ bits

則當我存入 1 個 key 進入 BloomFilter 時，其中一個 bit=0 的機率為：

$(1-\dfrac{1}{n})^k$

故當存入越來越多個 keys 時 (e.g. $m$ 個 keys)，可以期待其中一個 bit=0 的機率越來越低，故將上式做 $m$ 次方：

$((1-\dfrac{1}{n})^k)^m=(1-\dfrac{1}{n})^{km}$

我們有了一個 bit=0 的機率，就可以知道在存入了 $m$ 個 keys 之後，其中一個 bit=1 的機率了：

$1-(1-\dfrac{1}{n})^{km}$

故回到原本的問題：因為我有 $k$ 個 hash function，而每次都出現 bit=1 的機率就變成：

$(1-(1-\dfrac{1}{n})^{km})^k$

讓我搞懂怎計算的參考資料:
- [Bloom Filters](https://youtu.be/bEmBh1HtYrw?t=311)
- [布隆过滤器(Bloom Filter)原理及Golang实现](https://zhuanlan.zhihu.com/p/165130282)

:::

## Cache avalanche (雪崩)

問題來源：
- 快取過期時間 (expire time) 皆相同，導致大量快取接近同時過期
- Cache server 當機，導致大量快取失效

### TTL with jitter
- 過期時間設置加上一個偏差值。一個可行的策略是加上 5% 偏誤

#### 練習題
- 原本設計是 TTL=3600 sec.
- 則設置 expire time 時，使用 3600±5% = 3600±180
- 使得實際被設置的 TTL 被均勻分散在 3420~3780 之間

(source: [TalkGo: #112 go-zero 分布式缓存最佳实践](https://youtu.be/csKogMn4v0Q?t=759))

### Cluster deployment
- 使用叢集架構部署 cache server，避免[單點故障](https://en.wikipedia.org/wiki/Single_point_of_failure)引起的雪崩

:::info
:information_source: 參考資料：

- Simple self-hosting: [Deploying Redis Cluster on Kubernetes](https://www.containiq.com/post/deploy-redis-cluster-on-kubernetes)
- GCP Product: [High availability on Memorystore for Redis](https://cloud.google.com/memorystore/docs/redis/high-availability)
:::

# Redis basics

## Single threaded
- Redis 使用**單執行緒**處理用戶端請求
- 帶給 distributed system 的好處不會有 race condition

## Persistence
- 別預期它提供可靠的永久性儲存 (i.e. [Durability](https://en.wikipedia.org/wiki/Durability_(database_systems)))
- i.e. 若 Redis server 當機是會遺失資料的
- 因為預設儲存機制是一段時間才對 memory 做 snapshot，故有機率 loss data (see [Topic: Redis Persistence](https://redis.io/topics/persistence))
- 如不能接受，需要調整 Redis server configuration :tired_face:

## Database namespacing
- 仍然有 logical database space 的概念的
- 但預設只有 **16 個** ([stackoverflow.com](https://stackoverflow.com/questions/36735236/maximum-number-of-databases-in-redis))
- 平常登入使用的是 index 0 的 DB
- 可透過 [SELECT](https://redis.io/commands/select) 指令切換 DB

### Reminders
- Redis 官方建議
> *In practical terms, Redis databases should be used to separate different keys belonging to the same application (if needed), and not to use a single Redis instance for multiple unrelated applications.* - [SELECT](https://redis.io/commands/select)
- **一個 Redis instance** 應只服務**一個業務實體**
- 其中的 numbered databases 就只是提供該業務實體方便隔離 key space
- 不要讓一個 Redis 服務不同的業務實體
- 但此功能在 open source Redis Cluster 及 Redis Modules 上會**不能用**！另外，Redis 的作者也自省這是一個 Redis 的錯誤設計 (source: https://redis.com/blog/7-redis-worst-practices/#3.Numbered_databases/SELECT)

### Great practice (opinionated)
- 撰寫 **integration testing** 時，顯式地控制讓不同的 test cases 連向不同的 numbered databases，**避免測資污染**

## Data types
- 看一遍 [Redis data types intro](https://redis.io/topics/data-types-intro)，了解如何善用 Redis 來降低 app tier 複雜度、並做出更好的 system design
- 各種 date types 的 API 可再參考 [Redis 教程 - 菜鸟教程](https://www.runoob.com/redis/redis-tutorial.html)，很有用

# Redis practices

## Quick starting on local

- 使用 docker [Redis official image](https://hub.docker.com/_/redis) 快速運行一個免洗 Redis server
- `Makefile` code snippets:

        REDIS_PORT ?= 6379
        
        stop-redis:
            @echo "stop redis..."
            @docker stop redis-6 | true

        restart-redis: stop-redis
            @echo "start redis..."
            @docker run -d --rm \
                --name redis-6 \
                -p $(REDIS_PORT):6379 \
                redis:6.2-alpine

- 使用 `redis-cli` (*installed via [`brew install redis`](https://formulae.brew.sh/formula/redis)*) 連接 Redis server

## [Distributed locks](https://redis.io/topics/distlock)

### How to acquire lock
- 使用 [`SET`](https://redis.io/commands/set) 與 `NX` + `EX` options 來完成
- `NX`: Only set the key if it does not already exist.
- `EX`*`seconds`* : Set the specified expire time, in seconds.
- **加上 TTL 的目的是讓 Redis 自動幫你釋放 lock，避免 [deadlock](https://en.wikipedia.org/wiki/Deadlock)。** 因為：
- App 做太久了、不符原設計了，卡死該資源影響別的服務
- App 可能因故重啟、當機，故無法主動釋放該 lock

sequenceDiagram
    participant App1
    participant App2
    participant Redis
    App1->>Redis: acquire lock (SET foo token1 NX EX 30)
    Redis->>App1: return OK
    Note over App1: do things...
    App2->>Redis: acquire lock (SET foo token2 NX EX 30)
    Redis->>App2: return nil
    Note over App2: failed to SET

- command line demo:

    $ redis-cli
    127.0.0.1:6379> SET foo bar NX EX 30
    OK
    127.0.0.1:6379> SET foo hello NX EX 30
    (nil)
    127.0.0.1:6379> GET foo
    "bar"

### How to release lock

:::danger
:fire: 有潛在問題的做法

- 直覺：使用 `DEL` 指令刪除該 key
- 但是你怎知該 key 真的是你 `SET` 的？
- 要是不小心在 EX 的時間後才去 release 該 lock，很有可能 release 的是別人 `SET` 的 lock
:::

:::success
:bulb: 正確做法
- 在 **`SET` lock** 的時候，使用一組 non-guessable large random string (e.g. [UUID v4 string](https://en.wikipedia.org/wiki/Universally_unique_identifier#Version_4_(random))) 作為 value
- **release lock** 的時候使用 Lua script 來提供 [atomic operation](https://en.wikipedia.org/wiki/Linearizability) 的特性、檢查 value 真的是我 `SET` 的才 release lock
:::

- 以下為正確做法的循序圖：

sequenceDiagram
    participant App
    participant Redis
    Note over App: generate TOKEN_FOO
    App->>Redis: acquire lock (SET foo TOKEN_FOO NX EX 30)
    Redis->>App: return OK
    Note over App: do things...
    App->>Redis: rety to release lock (via sending a Lua script)
    Note over Redis: check the foo's value if is TOKEN_FOO
    alt
        Note over Redis: matched
        Redis->>App: return deleting result (1 or 0)
    else 
        Note over Redis: not matched
        Redis->>App: return 0
    end    

- 使用的 [Lua script](https://redis.io/commands/set#patterns) 範例

    if redis.call("get",KEYS[1]) == ARGV[1]
    then
        return redis.call("del",KEYS[1])
    else
        return 0
    end

## Bloom Filter Pattern
- 有遇到再深入了解 [Redis Best Practices - Bloom Filter Pattern](https://redis.com/redis-best-practices/bloom-filter-pattern/)

## Further reading
- [Redis Best Practices - official articles](https://redis.com/redis-best-practices/introduction/)
- [AmazingTalker 微服務化-快取服務](https://medium.com/amazingtalker-tech/amazingtalker-%E5%BE%AE%E6%9C%8D%E5%8B%99%E5%8C%96-%E5%BF%AB%E5%8F%96%E6%9C%8D%E5%8B%99-1f22f94b93ea)