Redis 設(shè)計(jì)與實(shí)現(xiàn)（第一版）

Redis 設(shè)計(jì)與實(shí)現(xiàn)（第一版）

你正在閱讀的是《Redis 設(shè)計(jì)與實(shí)現(xiàn)》第一版（舊版），請?jiān)L問 RedisBook.com ，查看關(guān)注 Redis 3.0 、包含更多新內(nèi)容的新版《Redis 設(shè)計(jì)與實(shí)現(xiàn)》。

本書的目標(biāo)是以簡明易懂的方式講解 Redis 的內(nèi)部運(yùn)行機(jī)制，通過閱讀本書，你可以了解到 Redis 從數(shù)據(jù)結(jié)構(gòu)到服務(wù)器構(gòu)造在內(nèi)的幾乎所有知識。

為了保證內(nèi)容的簡潔性，本書會盡量以高抽象層次的角度來觀察 Redis ，并將代碼的細(xì)節(jié)留給讀者自己去考究。

如果讀者只是對 Redis 的內(nèi)部運(yùn)作機(jī)制感興趣，但并不想深入代碼，那么只閱讀本書就足夠了。

另一方面，對于需要深入研究 Redis 代碼的讀者，本書附帶了一份 帶有詳細(xì)注釋的 Redis 2.6 源代碼 ，可以配合本書一并使用。

第一部分：內(nèi)部數(shù)據(jù)結(jié)構(gòu)

Redis 和其他很多 key-value 數(shù)據(jù)庫的不同之處在于，Redis 不僅支持簡單的字符串鍵值對，它還提供了一系列數(shù)據(jù)結(jié)構(gòu)類型值，比如列表、哈希、集合和有序集，并在這些數(shù)據(jù)結(jié)構(gòu)類型上定義了一套強(qiáng)大的 API 。

通過對不同類型的值進(jìn)行操作，Redis 可以很輕易地完成其他只支持字符串鍵值對的 key-value 數(shù)據(jù)庫很難（或者無法）完成的任務(wù)。

在 Redis 的內(nèi)部，數(shù)據(jù)結(jié)構(gòu)類型值由高效的數(shù)據(jù)結(jié)構(gòu)和算法進(jìn)行支持，并且在 Redis 自身的構(gòu)建當(dāng)中，也大量用到了這些數(shù)據(jù)結(jié)構(gòu)。

這一部分將對 Redis 內(nèi)存所使用的數(shù)據(jù)結(jié)構(gòu)和算法進(jìn)行介紹。

• 簡單動態(tài)字符串

• sds 的用途
• Redis 中的字符串
• 優(yōu)化追加操作
• sds 模塊的 API

• 小結(jié)

• 雙端鏈表

• 雙端鏈表的應(yīng)用
• 雙端鏈表的實(shí)現(xiàn)
• 迭代器

• 小結(jié)

• 字典

• 字典的應(yīng)用
• 字典的實(shí)現(xiàn)
• 創(chuàng)建新字典
• 添加鍵值對到字典
• 添加新元素到空白字典
• 添加新鍵值對時發(fā)生碰撞處理
• 添加新鍵值對時觸發(fā)了 rehash 操作
• Rehash 執(zhí)行過程
• 漸進(jìn)式 rehash
• 字典的收縮
• 字典其他操作
• 字典的迭代

• 小結(jié)

• 跳躍表

• 跳躍表的實(shí)現(xiàn)
• 跳躍表的應(yīng)用
• 小結(jié)

第二部分：內(nèi)存映射數(shù)據(jù)結(jié)構(gòu)

雖然內(nèi)部數(shù)據(jù)結(jié)構(gòu)非常強(qiáng)大，但是創(chuàng)建一系列完整的數(shù)據(jù)結(jié)構(gòu)本身也是一件相當(dāng)耗費(fèi)內(nèi)存的工作，當(dāng)一個對象包含的元素?cái)?shù)量并不多，或者元素本身的體積并不大時，使用代價高昂的內(nèi)部數(shù)據(jù)結(jié)構(gòu)并不是最好的辦法。

為了解決這一問題，Redis 在條件允許的情況下，會使用內(nèi)存映射數(shù)據(jù)結(jié)構(gòu)來代替內(nèi)部數(shù)據(jù)結(jié)構(gòu)。

內(nèi)存映射數(shù)據(jù)結(jié)構(gòu)是一系列經(jīng)過特殊編碼的字節(jié)序列，創(chuàng)建它們所消耗的內(nèi)存通常比作用類似的內(nèi)部數(shù)據(jù)結(jié)構(gòu)要少得多，如果使用得當(dāng)，內(nèi)存映射數(shù)據(jù)結(jié)構(gòu)可以為用戶節(jié)省大量的內(nèi)存。

不過，因?yàn)閮?nèi)存映射數(shù)據(jù)結(jié)構(gòu)的編碼和操作方式要比內(nèi)部數(shù)據(jù)結(jié)構(gòu)要復(fù)雜得多，所以內(nèi)存映射數(shù)據(jù)結(jié)構(gòu)所占用的 CPU 時間會比作用類似的內(nèi)部數(shù)據(jù)結(jié)構(gòu)要多。

這一部分將對 Redis 目前正在使用的兩種內(nèi)存映射數(shù)據(jù)結(jié)構(gòu)進(jìn)行介紹。

• 整數(shù)集合

• 整數(shù)集合的應(yīng)用
• 數(shù)據(jù)結(jié)構(gòu)和主要操作
• intset 運(yùn)行實(shí)例
• 升級
• 關(guān)于升級
• 關(guān)于元素移動
• 其他操作

• 小結(jié)

• 壓縮列表

• ziplist 的構(gòu)成
• 節(jié)點(diǎn)的構(gòu)成
• 創(chuàng)建新 ziplist
• 將節(jié)點(diǎn)添加到末端
• 將節(jié)點(diǎn)添加到某個/某些節(jié)點(diǎn)的前面
• 刪除節(jié)點(diǎn)
• 遍歷
• 查找元素、根據(jù)值定位節(jié)點(diǎn)
• 小結(jié)

第三部分：Redis 數(shù)據(jù)類型

既然 Redis 的鍵值對可以保存不同類型的值，那么很自然就需要對鍵值的類型進(jìn)行檢查以及多態(tài)處理。

為了讓基于類型的操作更加方便地執(zhí)行，Redis 創(chuàng)建了自己的類型系統(tǒng)。

在這一部分，我們將對 Redis 所使用的對象系統(tǒng)進(jìn)行了解，并分別觀察字符串、哈希表、列表、集合和有序集類型的底層實(shí)現(xiàn)。

• 對象處理機(jī)制

• redisObject 數(shù)據(jù)結(jié)構(gòu)，以及 Redis 的數(shù)據(jù)類型
• 命令的類型檢查和多態(tài)
• 對象共享
• 引用計(jì)數(shù)以及對象的銷毀

• 小結(jié)

• 字符串

• 字符串編碼
• 編碼的選擇

• 字符串命令的實(shí)現(xiàn)

• 哈希表

• 字典編碼的哈希表
• 壓縮列表編碼的哈希表
• 編碼的選擇

• 哈希命令的實(shí)現(xiàn)

• 列表

• 編碼的選擇
• 列表命令的實(shí)現(xiàn)
• 阻塞的條件
• 阻塞
• 阻塞因 LPUSH 、 RPUSH 、 LINSERT 等添加命令而被取消
• 先阻塞先服務(wù)（FBFS）策略

• 阻塞因超過最大等待時間而被取消

• 集合

• 編碼的選擇
• 編碼的切換
• 字典編碼的集合
• 集合命令的實(shí)現(xiàn)
• 求交集算法
• 求并集算法

• 求差集算法

• 有序集

• 編碼的選擇
• 編碼的轉(zhuǎn)換
• ZIPLIST 編碼的有序集
• SKIPLIST 編碼的有序集

第四部分：功能的實(shí)現(xiàn)

除了針對單個鍵值對的操作外，Redis 還提供了一些同時對多個鍵值對進(jìn)行處理的功能，比如事務(wù)和 Lua 腳本。

另外，一些輔助性的功能，比如慢查詢，以及一些和數(shù)據(jù)庫無關(guān)的功能，比如訂閱與發(fā)布，我們也會經(jīng)常用到。

通過理解這些功能的底層實(shí)現(xiàn)，我們可以更有效地使用它們。

這一部分將對這些功能進(jìn)行介紹。

• 事務(wù)

• 事務(wù)
• 開始事務(wù)
• 命令入隊(duì)
• 執(zhí)行事務(wù)
• 在事務(wù)和非事務(wù)狀態(tài)下執(zhí)行命令
• 事務(wù)狀態(tài)下的 DISCARD 、 MULTI 和 WATCH 命令
• 帶 WATCH 的事務(wù)
• WATCH 命令的實(shí)現(xiàn)
• WATCH 的觸發(fā)
• 事務(wù)的 ACID 性質(zhì)

• 小結(jié)

• 訂閱與發(fā)布

• 頻道的訂閱與信息發(fā)送
• 訂閱頻道
• 發(fā)送信息到頻道
• 退訂頻道
• 模式的訂閱與信息發(fā)送
• 訂閱模式
• 發(fā)送信息到模式
• 退訂模式

• 小結(jié)

• Lua 腳本

• 初始化 Lua 環(huán)境
• 腳本的安全性
• 腳本的執(zhí)行
• EVAL 命令的實(shí)現(xiàn)
• EVALSHA 命令的實(shí)現(xiàn)

• 小結(jié)

• 慢查詢?nèi)罩?/a>

• 相關(guān)數(shù)據(jù)結(jié)構(gòu)
• 慢查詢?nèi)罩镜挠涗?/a>
• 慢查詢?nèi)罩镜牟僮?/a>
• 小結(jié)

第五部分：內(nèi)部運(yùn)作機(jī)制

以下章節(jié)將對 Redis 最底層也最隱蔽的模塊進(jìn)行探討：

• Redis 如何表示一個數(shù)據(jù)庫？數(shù)據(jù)庫操作是如何實(shí)現(xiàn)的？
• Redis 如何進(jìn)行持久化？ RDB 模式和 AOF 模式有什么區(qū)別？
• Redis 如何處理輸入命令？它又是如何將輸出返回給客戶端的？
• Redis 服務(wù)器如何初始化？傳入服務(wù)器的命令又是以什么方法執(zhí)行的？

以上的這些問題，都是這一部分要解答的。

• 數(shù)據(jù)庫

• 數(shù)據(jù)庫的結(jié)構(gòu)
• 數(shù)據(jù)庫的切換
• 數(shù)據(jù)庫鍵空間
• 鍵空間的操作
• 鍵的過期時間
• 過期時間的保存
• 設(shè)置生存時間
• 過期鍵的判定
• 過期鍵的清除
• 過期鍵的惰性刪除策略
• 過期鍵的定期刪除策略
• 過期鍵對 AOF 、RDB 和復(fù)制的影響
• 數(shù)據(jù)庫空間的收縮和擴(kuò)展

• 小結(jié)

• RDB

• 保存
• SAVE 、 BGSAVE 、 AOF 寫入和 BGREWRITEAOF
• 載入
• RDB 文件結(jié)構(gòu)

• 小結(jié)

• AOF

• AOF 命令同步
• 命令傳播
• 緩存追加
• 文件寫入和保存
• AOF 保存模式
• AOF 保存模式對性能和安全性的影響
• AOF 文件的讀取和數(shù)據(jù)還原
• AOF 重寫
• AOF 重寫的實(shí)現(xiàn)
• AOF 后臺重寫
• AOF 后臺重寫的觸發(fā)條件

• 小結(jié)

• 事件

• 文件事件
• 時間事件
• 時間事件應(yīng)用實(shí)例：服務(wù)器常規(guī)操作
• 事件的執(zhí)行與調(diào)度

• 小結(jié)

• 服務(wù)器與客戶端

• 初始化服務(wù)器
• 客戶端連接到服務(wù)器
• 命令的請求、處理和結(jié)果返回
• 命令請求實(shí)例： SET 的執(zhí)行過程
• 小結(jié)

關(guān)于

本書由 huangz 編寫。

我在研究 Redis 源碼并創(chuàng)作本書的過程中獲得了極大的快樂，希望你在閱讀本書時也能有同感。

評論、問題、意見或建議都可以發(fā)表在本書自帶的 disqus 論壇里，也可以通過 豆瓣 、 微博 或 Twitter 聯(lián)系我，我會盡可能地回復(fù)。

要獲得本書的最新動態(tài)，請關(guān)注 redisbook 項(xiàng)目。

要了解編寫本書時用到的工具（源碼管理、文檔的生成和托管、圖片生成，等等），請閱讀 這篇文章 。

下載本書離線版本： pdf 格式 或 html 格式 。

通過捐款支持本書

如果你喜歡這本《Redis 設(shè)計(jì)與實(shí)現(xiàn)》的話，可以通過捐款的方式，支持作者繼續(xù)更新本書：比如為本書修補(bǔ)漏洞、添加更多有趣的章節(jié)，或者發(fā)行有更多更棒內(nèi)容的下一版，等等。

你可以通過使用支付寶錢包 掃描以下二維碼來進(jìn)行捐款，或者通過向支付寶帳號 huangz1990@gmail.com 轉(zhuǎn)帳來進(jìn)行捐款。