前面說過, 每個節點的?`previous_entry_length`?屬性都記錄了前一個節點的長度:
* 如果前一節點的長度小于?`254`?字節, 那么?`previous_entry_length`?屬性需要用?`1`?字節長的空間來保存這個長度值。
* 如果前一節點的長度大于等于?`254`?字節, 那么?`previous_entry_length`?屬性需要用?`5`?字節長的空間來保存這個長度值。
現在, 考慮這樣一種情況: 在一個壓縮列表中, 有多個連續的、長度介于?`250`?字節到?`253`?字節之間的節點?`e1`?至?`eN`?, 如圖 7-11 所示。

因為?`e1`?至?`eN`?的所有節點的長度都小于?`254`?字節, 所以記錄這些節點的長度只需要?`1`?字節長的?`previous_entry_length`?屬性, 換句話說,`e1`?至?`eN`?的所有節點的?`previous_entry_length`?屬性都是?`1`?字節長的。
這時, 如果我們將一個長度大于等于?`254`?字節的新節點?`new`?設置為壓縮列表的表頭節點, 那么?`new`?將成為?`e1`?的前置節點, 如圖 7-12 所示。

因為?`e1`?的?`previous_entry_length`?屬性僅長?`1`?字節, 它沒辦法保存新節點?`new`?的長度, 所以程序將對壓縮列表執行空間重分配操作, 并將`e1`?節點的?`previous_entry_length`?屬性從原來的?`1`?字節長擴展為?`5`?字節長。
現在, 麻煩的事情來了 ——?`e1`?原本的長度介于?`250`?字節至?`253`?字節之間, 在為?`previous_entry_length`?屬性新增四個字節的空間之后,?`e1`的長度就變成了介于?`254`?字節至?`257`?字節之間, 而這種長度使用?`1`?字節長的?`previous_entry_length`?屬性是沒辦法保存的。
因此, 為了讓?`e2`?的?`previous_entry_length`?屬性可以記錄下?`e1`?的長度, 程序需要再次對壓縮列表執行空間重分配操作, 并將?`e2`?節點的`previous_entry_length`?屬性從原來的?`1`?字節長擴展為?`5`?字節長。
正如擴展?`e1`?引發了對?`e2`?的擴展一樣, 擴展?`e2`?也會引發對?`e3`?的擴展, 而擴展?`e3`?又會引發對?`e4`?的擴展……為了讓每個節點的`previous_entry_length`?屬性都符合壓縮列表對節點的要求, 程序需要不斷地對壓縮列表執行空間重分配操作, 直到?`eN`?為止。
Redis 將這種在特殊情況下產生的連續多次空間擴展操作稱之為“連鎖更新”(cascade update), 圖 7-13 展示了這一過程。





除了添加新節點可能會引發連鎖更新之外, 刪除節點也可能會引發連鎖更新。
考慮圖 7-14 所示的壓縮列表, 如果?`e1`?至?`eN`?都是大小介于?`250`?字節至?`253`?字節的節點,?`big`?節點的長度大于等于?`254`?字節(需要?`5`?字節的?`previous_entry_length`?來保存), 而?`small`?節點的長度小于?`254`?字節(只需要?`1`?字節的?`previous_entry_length`?來保存), 那么當我們將?`small`?節點從壓縮列表中刪除之后, 為了讓?`e1`?的?`previous_entry_length`?屬性可以記錄?`big`?節點的長度, 程序將擴展?`e1`?的空間, 并由此引發之后的連鎖更新。

因為連鎖更新在最壞情況下需要對壓縮列表執行?`N`?次空間重分配操作, 而每次空間重分配的最壞復雜度為??, 所以連鎖更新的最壞復雜度為??。
要注意的是, 盡管連鎖更新的復雜度較高, 但它真正造成性能問題的幾率是很低的:
* 首先, 壓縮列表里要恰好有多個連續的、長度介于?`250`?字節至?`253`?字節之間的節點, 連鎖更新才有可能被引發, 在實際中, 這種情況并不多見;
* 其次, 即使出現連鎖更新, 但只要被更新的節點數量不多, 就不會對性能造成任何影響: 比如說, 對三五個節點進行連鎖更新是絕對不會影響性能的;
因為以上原因,?`ziplistPush`?等命令的平均復雜度僅為??, 在實際中, 我們可以放心地使用這些函數, 而不必擔心連鎖更新會影響壓縮列表的性能。
- 介紹
- 前言
- 致謝
- 簡介
- 第一部分:數據結構與對象
- 簡單動態字符串
- SDS 的定義
- SDS 與 C 字符串的區別
- SDS API
- 重點回顧
- 參考資料
- 鏈表
- 鏈表和鏈表節點的實現
- 鏈表和鏈表節點的 API
- 重點回顧
- 字典
- 字典的實現
- 哈希算法
- 解決鍵沖突
- rehash
- 漸進式 rehash
- 字典 API
- 重點回顧
- 跳躍表
- 跳躍表的實現
- 跳躍表 API
- 重點回顧
- 整數集合
- 整數集合的實現
- 升級
- 升級的好處
- 降級
- 整數集合 API
- 重點回顧
- 壓縮列表
- 壓縮列表的構成
- 壓縮列表節點的構成
- 連鎖更新
- 壓縮列表 API
- 重點回顧
- 對象
- 對象的類型與編碼
- 字符串對象
- 列表對象
- 哈希對象
- 集合對象
- 有序集合對象
- 類型檢查與命令多態
- 內存回收
- 對象共享
- 對象的空轉時長
- 重點回顧
- 第二部分:單機數據庫的實現
- 數據庫
- 數據庫鍵空間
- 重點回顧
- RDB 持久化
- RDB 文件結構
- 重點回顧
- AOF 持久化
- AOF 持久化的實現
- 重點回顧
- 事件
- 文件事件
- 重點回顧
- 參考資料
- 客戶端
- 客戶端屬性
- 重點回顧
- 服務器
- 命令請求的執行過程
- 重點回顧
- 第三部分:多機數據庫的實現
- 復制
- 舊版復制功能的實現
- 重點回顧
- Sentinel
- 啟動并初始化 Sentinel
- 重點回顧
- 參考資料
- 集群
- 節點
- 重點回顧
- 第四部分:獨立功能的實現
- 發布與訂閱
- 頻道的訂閱與退訂
- 重點回顧
- 參考資料
- 事務
- 事務的實現
- 重點回顧
- Lua 腳本
- 創建并修改 Lua 環境
- 重點回顧
- 排序
- SORT <key> 命令的實現
- 重點回顧
- 二進制位數組
- GETBIT 命令的實現
- 重點回顧
- 慢查詢日志
- 慢查詢記錄的保存
- 慢查詢日志的閱覽和刪除
- 添加新日志
- 重點回顧
- 監視器
- 成為監視器
- 向監視器發送命令信息
- 重點回顧
- 源碼、相關資源和勘誤