MySQL & PostgreSQL 都有 In-Memory 快取 (Buffer Pool & Shared Buffer)，那為何實務上還要用 Redis 快取呢？

Redis 會比 MySQL & PostgreSQL 快取快嗎？

MySQL & PostgreSQL 的快取單位為 Page，因此即便是 id=1 的查詢，都要經過不同 Page 層層篩選才能找到資料，例如 B+Tree 的 Traversal。

而 Redis 是 key-value 快取資料庫，快取單位就是資料，只要 key 命中就能馬上找到資料，且 Redis 還針對不同業務情境提供不同資料結構 (String、List、Set、Hash、Sorted Set) 跟操作。

Redis 提供哪些資料結構？

首先 Redis 所有資料會儲存成 Robj (Redis Object)，由於 Redis 主結構為 Hash，Key 可用 String 儲存，但 Value 可能為不同的型別，因此 Redis 使用 Robj 將資料抽象化來儲存不同型別的資料。

String

最基礎的資料型別，透過 binary 形式儲存，且保證因為編碼 format 更改資料內容 (binary-safe)，因此 String 可儲存任何資料，例如一般字串，數字，檔案以及序列化後的物件等。

String 的常見操作：

• CRUD：GET， SET， DEL
• 多筆操作：MSET，MGET
• 數字操作：INCR， INCRBY，INCRBYFLOAT，DECR，DECRBY

底層資料結構：

Simple Dynamic String 是 String 類別的資料結構，會記錄當前 binary 資料的被佔用長度，以及還沒被佔用的長度。

struct sdshdr {  
    long len; // 被佔用的長度  
    long free; // 還沒被佔用的長度  
    char buf[]; // binary 資料  
};

List

由多個 redis 的 String 所組成，List 中成員會依照插入順序儲存，並提供由頭尾插入，以及頭尾拿出的功能，List 能實作很多功能，例如任務隊列，Message Queue。

List 的常見操作：

• 插入移除：LPUSH，RPUSH，LPOP， RPOP
• 資料查詢：LRANGE，LLEN，LPOS (找元素的 index)
• 阻塞操作：BLPOP，BRPOP，如果 List 中沒有資料 Redis 會 blocking 住。
• LTRIM：根據輸入 range 保留 List。
• LREM：根據元素出現次數移除多個元素。

底層結構；

為 雙向 linked-list，每個節點會紀錄 prev 以及 next 的節點，每個節點會有一個指向真實資料的指標。

Set
多個 String 以無序的方式所組成，其保證內部不會有重複的元素，此外 Redis 提供了多個 Set 之間交集，差集，聯集的操作。

Set 的常見操作：
CRUD：SADD，SREM，SMEMBERS，SCARD，SPOP
集合操作：SDIFF，SINTER，SUNION

底層結構；

Dict 為 Hash 以及 Set 的底層結構，也是 Redis 的主結構 (key 為 sds，value 為 robj)，一個 Dict 會有兩個 hash table 主要用於 rehashing，每個 hash table 會有多個儲存 key-value 資料的 bucket。

Hash

key-value 的資料類型，也是 Redis 的主結構，非常適合用於儲存物件型資料，例如 User 物件有姓名，年齡，信箱等。當物件很小時，Hash 會將資料壓縮後儲存，因此單台 Redis 可以儲存數百萬個小物件。

Hash 的常見操作：
CRUD：HSET，HGET，HDEL
多欄位讀：HGETALL，HKEYS，HMGET

底層結構；

同 Set。

Sorted Set

Sorted Set 是有序的 Set，其順序會依照給定的權重值排序，由於資料使排序好的，在查找資料時，可用 binary search 查找效率高。

由於 Sorted Set 的高查詢效能，Sorted Set可當作一組 Hash 資料的 index，將物件 id 以及 index field 儲存在 Sorted Set，單筆物件的完整資料儲存在 Hash。

Sorted Set 的常見操作：
CRUD：ZADD，ZRANGE，ZREM
Rank 操作：ZRANK 找元素位置，ZSCORE 設定元素權重值

底層結構：

Skip List 為 sorted set 的底層結構，其結構為多層的 sorted linked list，第一層的 linked list 節點的橫跨維度(span)是 0，隨著層級往上，節點的橫跨維度(span)會提升，而查找方式是從最上層開始往下查找，原理類似 binary search，透過橫跨維度過濾掉節點。

符合快速查詢的資料結構通常會使用平衡二元樹 (e.g AVL，紅黑樹)，而 Skip List 相較於平衡樹，實作更簡單，在橫跨維度設計良好的情況，平均查詢時間也能到 O(logN)。

(圖來源：https://www.geeksforgeeks.org/dsa/skip-list/)

Normal Lane 為第一層 linked list，span 為 0，只有第一層的情況，查詢需要 O(N)，為了提高查詢效率，Skip List 增加了第二層 linked list Express Lane，並將 span 提升到 4，當我們要在此 Skip List 查詢 45 時，首先會從最上層也就是 Express Lane 開始搜尋，從 10->30->57，我們發現 45 介於 30 到 57 之間，我們藉由 30 這個節點往下一層開始搜尋，30->43->45 匹配成功，透過此方法，我們可以過濾掉 30 以下的節點，提高搜尋時間。

但 Redis 不是單執行緒嗎？效能會比多執行緒好嗎？

MySQL & PostgreSQL 會同時讀寫相同 Page，因此要上鎖，但 Redis 是單執行緒，不須要上鎖，也沒有 Context Switch，全是記憶體操作，不需要等 I/O 非常快，因此沒有 context switch 的單執行緒會比多執行緒來得更高效。

但是網路 I/O 呢？如何管理多個 Client Connection？

MySQL 是用多個 Thread 管理不同 Client Connection，而 PostgreSQL 是用多個 Process，但 Redis 用單個 Thread 就能管理多個 Client Connection。

Redis 怎麼用單個 Thread 管理多個 Client Connection？

MySQL & PostgreSQL 使用 Blocking I/O，在執行 read() 時，若沒有資料可讀會卡住，直到有資料才 return，同樣執行 write() 時，如果前一個寫入資料還沒 ACK，下一個寫入就會卡住，直到前一個處理完，因此多個 Blocking I/O 不能共用同個 Thread，因為如果第一個連線一直沒有資料執行 read() 會卡住，導致後面連線都有資料也處理不到，所以一個連線要搭配一個 Thread。

Redis 則是用 Non-Blocking I/O ，執行 read() & write() 時，沒資料或不可寫會直接 return error，一個 Thread 可處理多個 Non-Blocking I/O，前面連線沒資料會 return error 並往下一個連線處理，不會卡住，不需要一個 I/O 搭配一個 Thread。

但 Non-Blocking I/O 的 read() 不卡住，就要一直執行 read() ，假設有 N 個 I/O，就要執行 N 次 read()，Thread 是減少了，但 CPU 使用率太差了，假設 100 個 I/O 裡面只有 2 個有資料，等於 98 read() 白執行了。

如何高效使用 Non-Blocking I/O？

Redis 使用 Epoll，是 kernel 設計來管理 Non-Blocking I/O 的資料結構，能解決無效 read() 問題，它採用 Event-Drive 的方式，將結構內 Non-Blocking I/O 針對事件掛上 callback，例如當 I/O 觸發可讀事件或可寫事件時，會執行對應 callback。

硬體對 Kernel 發送中斷訊號時會觸發 Event，例如 NIC (網卡) 收到網路封包後，向 CPU 發送中斷訊號，此時 CPU 會停下手邊工作，告訴 Kernel 有緊急事件並把封包資料讀到記憶體中，然後觸發可讀事件，執行對應 I/O 的 callback。

而 Epoll callback 內容就是把該 I/O 放進 Double Link-List 的 Queue 中，可執行 epoll_wait() system call 讀 Queue 中資料，如果 Queue 沒資料，Epoll 會卡住直到 Queue 中放入資料，因此只會拿到有資料的 I/O 不會執行無效 read()。

實務上 Redis 會有一個 Thread 不斷接收連線建立請求，建立後放到 Epoll 結構中，另一個 Thread 處理 Client 請求，處理過程為：

1. 先透過 epoll_wait() 找到可讀連線，然後執行 read() 讀請求
2. 處理完請求後，結果先放到 server 層 in-memory buffer 中，不馬上 write()，為避免該連線 kernel 中的 buffer cache 滿了，前一個送出資料也沒收到 ACK ，此時 write() 會失敗
3. 隨後執行 epoll_ctl() 監聽該連線的可寫事件，結束這一 round
4. 執行下一次的 epoll_wait()
5. 此時會回傳可寫連線，在將 in-memory buffer 中結果透過 write() 寫入到連線
6. 而 write() 指令會先把資料寫到 kernel 的 buffer cache 在 async 的方式寫入網卡，執行很快。

透過上面流程，可發現處理 Client 請求的 Thread 全程不會有任何 I/O 等待，而這就是 Redis 高效的秘訣。