本文試圖讓讀者對 Redis 有一個整體的認識。如果想深入學(xué)習(xí)，可以先閱讀掘金小冊上的 “老錢 Redis”，然后再找一本 Redis 實體書啃啃。
1. 是什么
Redis「Remote Dictionary Service」是基于內(nèi)存的存儲中間件，通常用于數(shù)據(jù)庫、緩存、消息隊列。
2. 基礎(chǔ) - 數(shù)據(jù)結(jié)構(gòu)
Redis 有 5 中數(shù)據(jù)結(jié)構(gòu)：string、list、hash、set 和 zset（有序集合），分別對應(yīng) Java 中的 String、LinkedList、HashMap、Set、SortedSet。
string 字符串
string 是 Redis 中最常見的數(shù)據(jù)結(jié)構(gòu)，也稱 SDS「Simple Dynamic String」，通常作為 key 或 value（最大長度 512 M）。圖中粉色部分為 Redis 對象的通用頭部，ptr 指向 SDS。string 按長短分以 embstr（len <= 44） 和 raw 的形式存儲。
字符串在長度小于 1 M 時采用加倍擴容；大于 1 M 時采用 +1 M 擴容。
list 列表
list 對應(yīng)的是鏈表而不是數(shù)組，插入刪除快而索引慢，可以用于消息隊列。list 的底層不是簡單的 LinkedList，而是 ziplist（壓縮列表）或 quicklist（快速列表）。
壓縮列表使用一塊連續(xù)的內(nèi)存，元素間緊挨著存儲沒有空隙。
每個元素中包括前一個元素的長度、當(dāng)前元素的編碼和內(nèi)容，在編碼中標(biāo)識當(dāng)前元素的長度。在沒有前后指針時，能夠快速的前后索引。
struct entry {
int<var> prevlen; // 前一個 entry 的字節(jié)長度
int<var> encoding; // 元素類型編碼
optional byte[] content; // 元素內(nèi)容
}
list 在增加元素時會根據(jù)內(nèi)存分配算法和當(dāng)前內(nèi)存大小，決定是在原有地址上擴展還是重新分配內(nèi)存
當(dāng)某個元素的長度超過 254 個字節(jié)時，后面元素的 prevlen 需要從 1 字節(jié)改成 5 字節(jié)用于表示上一元素的長度。這個操作可能會造成后面的元素雪崩式的更改 prevlen，即 聯(lián)級更新。因此，list 中存儲的元素不應(yīng)該太多、太大。
hash 字典
hash 是 Redis 中的字典結(jié)構(gòu)，內(nèi)部實現(xiàn)與 Java 中的 HashMap 一致（數(shù)組 + 鏈表）。字典內(nèi)部有兩個 HashTable，Rehash（擴容或縮容）時用于存儲新舊兩份數(shù)據(jù)。
擴容時機：元素個數(shù)等于數(shù)組長度（bgsave 時 5 倍數(shù)組長度時擴容）
擴容方式：2 倍數(shù)組長度
縮容時機：元素個數(shù)少于數(shù)組長度 10%
set 集合
set 是沒有排序的字符串集合，不允許出現(xiàn)重復(fù)元素，內(nèi)部結(jié)構(gòu)與 hash 字典一致，只是 value 為 null。
zset 有序集合
zset 是有序集合，內(nèi)部實現(xiàn)為跳躍鏈表，用于支持隨機地插入和刪除。
跳躍鏈表其實是基于 LinkedList + 多級索引 的實現(xiàn)。鏈表用于前后索引，多層級索引通過類似 2 分的思路幫助快速定位，復(fù)雜度 O(lgn)。跳躍鏈表相比二叉樹實現(xiàn)更加簡單，通過隨機層數(shù)來解決平衡的問題。
節(jié)點更新的過程是先刪除再添加。
3. 應(yīng)用
分布式鎖
Redis 底層是單線程、事件循環(huán)
// 先爭搶再設(shè)置過期時間，容易死鎖
setnx lock_abc true
expire lock_abc 5
// 原子命令
set lock_abc true ex 5 nx
延時隊列
// 阻塞讀 notify-queue 隊列
blpop notify-queue
// 使用 redis zset 來實現(xiàn)延時隊列，按 score 獲取需要執(zhí)行的任務(wù)
redis.zrangebyscore("delay-queue", 0, time.time(), start=0, num=1)
HypeLogLog
HypeLogLog 是 Redis 的高級數(shù)據(jù)結(jié)構(gòu)，用于獲取唯一元素總數(shù)?；跀?shù)學(xué)概率公式，通過計算某一事件連續(xù)發(fā)生的最大次數(shù)估算實驗的次數(shù)。Redis 通過對元素進行哈希，記錄從某位開始連續(xù)出現(xiàn) 0 的最大次數(shù)，來估算元素樣本的大小。
布隆過濾器
布隆過濾器是一個不精確的 set 結(jié)構(gòu)，用于判斷某個元素是否存在過，存在一定誤判。內(nèi)部實現(xiàn)是一個大型的位數(shù)組，通過多次哈希進行散落。效果與空間向量類似，同樣的元素散落結(jié)果一定相同。
GeoHash
在 Redis 中基于 zset 實現(xiàn)，score 是 GeoHash 的值。原理是將經(jīng)緯度經(jīng)過哈希算法映射到一條直線上的多個值，哈希值約接近表示兩個點約接近。
4. 原理
IO 模型
Redis 是單線程程序。
使用非阻塞 IO：能讀時讀，能寫時寫，無線程阻塞。
非阻塞 IO 基于操作系統(tǒng)底層的事件輪詢 API，注冊監(jiān)聽基于回調(diào)。
持久化
Redis 提供兩種持久化方式：
- RDB - 一段時間內(nèi)生成指定時間點生成數(shù)據(jù)集快照 (snapshot)
- AOF - 增量日志
Redis 提供了 SAVE 和 BGSAVE 兩個命令來生成 RDB 文件，前者是阻塞的，后者是后臺 fork 子進程。
AOF 持久化實現(xiàn)可以分為命令追加 (append)、文件寫入 (write)、文件同步 (fsync) 三個步驟。Append 追加命令到 AOF 緩沖區(qū)，Write 將緩沖區(qū)的內(nèi)容寫入到程序緩沖區(qū)，F(xiàn)sync 將程序緩沖區(qū)的內(nèi)容寫入到文件。
由于 AOF 比 RDB 文件更加完整，Server 啟動時優(yōu)先采用 AOF 文件進行恢復(fù)。
主從復(fù)制
主從復(fù)制是指一個 Server 復(fù)制另一個 Server 的數(shù)據(jù)。
主從復(fù)制的對象：mater 和 多 Slaver，和集群的概念區(qū)分開。
主從復(fù)制的三個階段：復(fù)制初始化（建立連接）、數(shù)據(jù)同步（同步現(xiàn)有數(shù)據(jù)）和命令傳播（同步增量數(shù)據(jù)）。
主從復(fù)制的策略：從未同步的 Slaver 全量同步，同步過的 Slaver 部分同步
5. 集群
大規(guī)模數(shù)據(jù)存儲系統(tǒng)都會面臨水平擴展的問題。水平擴展可以通過數(shù)據(jù)分片來解決，通過一致性哈希來避免大量的 rehash 數(shù)據(jù)遷移。但是數(shù)據(jù)分片如何屏蔽業(yè)務(wù)，在 Redis 3.0 支持集群以前，業(yè)界有兩種的解決方案。
一是使用中間代理層來屏蔽集群分布，優(yōu)點是數(shù)據(jù)遷移和運維方便，缺點是轉(zhuǎn)發(fā)有一定的性能損失，代表有 Twitter 的 Twemproxy 和豌豆莢的 Codis。
二是將數(shù)據(jù)路由和故障轉(zhuǎn)移封裝到 client，優(yōu)點是去中心化、可擴展性高，缺點是運維困難。
Redis 3.0 版本開始官方正式支持分集群，集群通過分片進行數(shù)據(jù)共享，分片內(nèi)采用一主多從的形式進行副本復(fù)制，并提供復(fù)制和故障恢復(fù)功能。
哈希槽
Redis Cluster 的數(shù)據(jù)分片依賴哈希槽（slot）實現(xiàn)，集群預(yù)先劃分 16384 個 slot，每個分片負責(zé)一部分 slot。請求時先通過 key 計算哈希值，然后映射到唯一的 slot，最后直連對應(yīng)的數(shù)據(jù)分片。
分片
Redis Cluster 的數(shù)據(jù)分片通常有多臺服務(wù)組成，一主多從（master and slavers）。master 負責(zé)寫（或讀），slaver 負責(zé)讀（或轉(zhuǎn)發(fā)寫請求）。主從服務(wù)使用 Raft 協(xié)議完成 Leader 選舉（故障轉(zhuǎn)移），使用 Epoch（紀(jì)元）的概念來給事件增加版本號。
