---
# System prepended metadata

title: Ch6. Application components in Redis
tags: [Redis]

---

---
tags: Redis
---

# Ch6. Application components in Redis
── 使用 Redis 建構應用程式元件

- Overview
    - 建構兩個**自動補全函數**，分別應用在較短/長的聯絡人列表中，快速查找指定用戶。
    - 兩種不同類型的**鎖**，可以用於：減少數據衝突、提升效能、防止數據出錯，以及減少不必要工作。
    - 在指定時間執行任務的**延遲任務隊列**，並以此出發建構兩個不同的**消息系統**，分別提供點對點、廣播等消息服務。
    - 由 Redis 存儲及分發的數百萬條 **log entries** 上。

## 6.1 Autocomplete 
- **autocomplete：自動補全**
依據使用者已輸入的字母，來尋找所有以該字母為開頭的單詞，甚至是自動補充完整的句子。
![](https://i.imgur.com/pcFrZnw.png)

- **應用**

| |自動補全最近聯絡人|通訊錄自動補全|
| ---- | --- | --- |
| 情境 |《聯絡人清單短》<br>每個使用者都有其100位最近聯絡人的列表，當使用者發起聊天時，可依據輸入文字自動補全聯絡人名。|《聯絡人清單長》<br>郵件自動補全功能：玩家可以對同一公會(guild)的其他玩家發送信件，而一個公會可能包含成千上萬的玩家。|
| 說明 |LIST：儲存聯絡人清單 (memory 佔用少)|ZSET：將scores都設為0，用玩家名稱二進制排序<br>|
| 實作 |- 更新聯絡人 (LREM移除、LPUSH加入、LTRIM修剪)<br>![](https://i.imgur.com/2nwxmx6.png)<br> - 移除聯絡人<br>![](https://i.imgur.com/JIBl6xI.png)<br> - 獲取自動補全列表 & 尋找相符玩家<br>![](https://i.imgur.com/PPlScNR.png)|- 尋找前綴(prefix)範圍：利用ASCII的排序，如 abc: abb{~abc{ <br>![](https://i.imgur.com/ROY9N1U.png)<br>- 加入/退出公會<br>![](https://i.imgur.com/ywxNHIo.png)<br>- 獲取自動補全列表 & 尋找相符玩家<br>![](https://i.imgur.com/Lz57Bz4.png)|
| 備註 |實際自動補全由 python 完成，但是當LIST很長時，會浪費資源。|WATCH 是為了不同 process 間的衝突，但當負載增加重試次數會上升，需要 lock！|
        

## 6.2 & 6.3 Locks: Distributed locking & Counting semaphores
- 對數據加鎖 (lock data)
  1. 取得鎖 (acquire the lock)：以對數據進行排他性訪問
  2. 數據操作
  3. 釋放鎖 (release the lock)：給其他 process 使用

- 各種大類的鎖 (lock)

||WATCH|Distributed locking|Counting Semaphores|
|---|---|---|---|
|中文|(*回顧第四章 XD*)|分布式鎖|計數信號量|
|說明|一種樂觀鎖 (optimistic locking)：只做到通知但無法對數據進行排他性訪問。<br>不具備性能可擴展性，因為會一直重試。|有上面提到的三個步驟的鎖，用於不同機器上的不同 Redis 客戶端進行 acquire & release。<br>當客戶端取得鎖失敗時會等待。|可以讓用戶限制一項資源最多能被多少 process 使用。<br>當客戶端取得鎖失敗時直接回傳失敗。|
|情境|(*同右*)|【4.6 市場買賣】市場 (ZSET)、使用者 (HASH)、存貨 (SET)<br>![](https://i.imgur.com/CchFvnL.png)|承左測情境，若遊戲交易市場擴大，允許玩家在不登入遊戲的情況下進行商品買賣。限制 5 個 process 同時訪問市場。|
|實作|(*略*)<br>假設在買賣過程中，市場 (ZSET)  or 使用者 (HASH) 改變，會造成 WATCH 出錯就得重試。|【Simple Lock】限制任一時段只能上下一件商品！<br>- 取得鎖：設定的 timeout 期間不斷嘗試 SETNX 以取得鎖<br>![](https://i.imgur.com/gsNSIog.png)<br>- 釋放鎖：WATCH 鎖，確認和取得時候一樣再主動釋放<br>![](https://i.imgur.com/O3a3lYg.png)|【基本 semaphore】不介意系統時間、接受偶爾信號量超過限制<br>- 取得鎖：process 把自己 ZADD 計數信號量 (ZSET) 後 ZRANK 檢查排名，若排名大於等於限制數量，則取得失敗須 ZREM 自己<br>![](https://i.imgur.com/oxEABxw.png)![](https://i.imgur.com/d48cv3w.png)<br>- 釋放鎖：ZREM|
|衍伸||【Lock with timeouts】避免客戶端取得鎖之後 crash，導致鎖無法被正常釋放。<br>在取得鎖失敗的時候為該鎖設置超時時間 (EXPIRE)。<br>![](https://i.imgur.com/MejwBtn.png)|【Fair semaphore】信任差距1~2s的系統時間，接受偶爾信號量超過限制<br>- 取得鎖：先對 counter (STRING) 自增 INCR，再對原本的計數信號量 (ZSET) 和新的信號量擁有者 (ZSET) 執行 ZADD<br>![](https://i.imgur.com/VCeHX4R.png)![](https://i.imgur.com/67F2I7o.png)<br><br>【消除競爭條件 (race conditions)】永遠正確行為的信號量<br>+ lock with timeouts|
    


## 6.4 Task queues
- **Task queues：任務隊列**
    - 將待執行的任務放在 queue 中，並在之後對 queue 做處理，以延遲執行耗時的操作。
    - FIFO：先進先出
        - 透過 LIST 實作：RPUSH 塞到 LIST 尾巴、BLPOP 阻塞方式把第一個元素取出。
        - 當任務有優先級 (task priorities)，可以使用 BLPOP 將第一個非空 LIST 的第一個元素 pop 出來。→[[H1, H2], [M1, M2], [L1, L2]]
    - Delayed task：延遲任務
        - 透過 ZSET queue：儲存 {uuid, queue, callback, args pass to callback}，任務執行時間做為 score。

## 6.5 Pull messaging
- **Pull messaging：消息拉取**
    - 當兩個或多個客戶端互相發送和接受訊息時，會使用 push messaging 或 pull messaging 來傳遞訊息。
    - push messaging：發送者來確認，Redis內建 PUBLISH/SUBSCRIBE。
    - pull messaging：接收者自己確認。
- 應用


||單個接收者|多個接收者|
|---|---|---|
|情境|個人電子信箱的未讀訊息<br>![](https://i.imgur.com/AV06QI9.png)|群組聊天室每個人的未讀訊息<br>![](https://i.imgur.com/y2hsNGs.png)|
|實作|類似 FIFO queue，將要發送的訊息 RPUSH 進接收者的 LIST，接收者再 LTRIM 讀取訊息。|[Step1] 建立群組聊天室<br>- 使用 STRING 的 INCR 獲取新群組 ID<br>- 初始化 chat ZSET，ZADD 所有成員並將 score 設為 0<br>- 對各成員的 seen ZSET ZADD 該群組<br>- 發送初始化訊息<br><br>[Step2] 發送訊息<br>- 使用 lock 避免 race conditions<br><br>[Step3] 獲取訊息<br>- 對成員的 seen ZSET 操作 ZRANGE 取得群組ID和已讀消息ID<br>- 再以此對應 chat ZSET 操作 ZRANGEBYSCORE 來獲取群組內的未讀消息<br>- ZADD 更新已讀訊息、ZREMRANGEBYSCORE清除被所有人已讀的訊息<br><br>[Step4] 加入/離開群組<br>- ZADD/ZREM|


## 6.6 Distributing files with Redis
- **Distributing files with Redis：使用 Redis 進行文件分發**

- [情境] 遊戲用戶共 10 萬人，每天/人出現 10 個事件，累積兩年大約就有 73 億行 log 要分析。
    - 在本地進行資料聚合計算
分批讀入 memory 進行聚合統計，完成後再將結果寫入 Redis 中，可以有效減少程序與 Redis 服務的通信次數，縮短任務時間。

- [情境] 有一台機器的本地日誌需要交給多個日誌處理器進行不同的分析。
    - 使用 6.5 多個接收者的 pull messaging。
    - 本地機器：
將所有日誌發送至群組，最後再發送一條結束消息。
等待所有日誌處理器處理完（群組對應的完成標識 = 群組內的成員數 - 1）。
清理本次發送的所有日誌。
    - 日誌處理器：
不斷從群組中拉取消息，並進入相關處理，直至拉取到結束消息。
對羣組對應的完成標識進行 INCR ，表示當前日誌處理器已完成處理。

※ 參考筆記：https://www.gushiciku.cn/pl/gvkc/zh-hk