《Redis設計與實現》簡讀

NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...
目錄

一、資料結構與物件

簡單動態字串(SDS)

  • 相比C字串增加記錄字串長度的,獲取字串長度複雜度為O(1)
  • 相比C字串增加記錄已分配記憶體空間,可以避免緩衝區溢位
  • 空間預分配和空間惰性釋放
  • 二進位制安全,不是以空字元(0)來判斷字串是否結束
  • 遵循C字串以空字元結尾的慣例,可以相容部分C字串函式

關於空間預分配和空間惰性釋放

  • 字串增長操作時,如果修改後長度小於1M則分配該字串長度2倍的記憶體空間,如果修改後長度大於等於1M則分配該字串長度 1M的記憶體空間。(預分配,避免每次增長操作都需要進行記憶體重分配執行系統呼叫)
  • 字串縮短操作時,程式不會立即釋放縮短後多出來的位元組,而是在需要時再釋放。(惰性釋放,避免以後需要增長操作時重分配記憶體,會在較短的時間內造成記憶體浪費,文中未提及何時是“需要時”)

最佳實踐:因為對字串的增長或縮短操作都有可能需要執行記憶體重分配,所以修改相同鍵使用SDS型別儲存的值時保持修改前後長度一致。

連結串列

  • 雙端,獲取某節點前後置節點對複雜度為O(1)
  • 無環,表頭prev指標和表尾next指標都指向NULL
  • 記錄表頭尾節點,獲取表頭尾節點的複雜度為O(1)
  • 記錄連結串列長度,獲取連結串列長度複雜度為O(1)
  • 空指標儲存值,可以儲存各種不同型別的值

字典

  • 使用鏈地址法解決衝突,當多個鍵被分配到相同雜湊索引時將新鍵新增到節點連結串列表頭
  • 字典包含ht[0]和ht[1](ht[1]僅為rehash時使用)兩個雜湊表,當雜湊表儲存的鍵值對數量太多或太少時使用重新雜湊(rehash)維持雜湊表負載因子在合理範圍之內
  • rehash操作採用漸進式,分量將ht[0]中的鍵值對rehash到ht[1],新鍵值對統一儲存到ht[1]中

rehash步驟

  1. 擴充套件操作(沒有執行BGSAVE或BGREWRITEAOF且負載因子大於等於1;正在執行BGSAVE或BGREWRITEAOF且負載因子大於等於5),為ht[1]分配第一個大於等於當前包含鍵值對數量(ht[0].used)*2的<math><msubsup><mi>2</mi><mi></mi><mi>n</mi></msubsup></math>記憶體空間
  2. 收縮操作(負載因子小於0.1時),為ht[1]分配第一個大於等於當前包含鍵值對數量的<math><msubsup><mi>2</mi><mi></mi><mi>n</mi></msubsup></math>記憶體空間
  3. 將儲存在ht[0]中的所有鍵值對rehash到ht[1]
  4. 釋放ht[0],將ht[1]設定為ht[0],建立新的空白雜湊表ht[1]

負載因子=雜湊表已儲存節點數量/雜湊表大小

Redis使用MurmurHash2演算法來計算鍵的雜湊值

跳躍表

  • 有序集合的底層實現之一
  • 每個節點可以儲存一個位元組陣列或整數值
  • 連結串列中的節點按照分值大小排序,分值相同時按物件大小排序

整數集合

  • 可以儲存int16_t(-32768至32767)、int32_t(-2147483648至2147483647)、int64_t(-9223372036854775808至9223372036854775807)三種型別的整數集
  • 為節約記憶體,集合型別使用最小型別儲存整數,僅當新新增的整數大於當前所能容納的值範圍時進行升級操作
  • 因為每次新增新元素都有可能引起升級,所以新增新元素的時間複雜度為O(N)
  • 不支援降級操作

升級步驟

  1. 根據新元素的型別擴充套件底層陣列空間,併為新元素分配空間
  2. 轉換現有元素至新的型別,保持有序性放置元素
  3. 新增新元素,當新元素小於所有先有元素時放置在索引0,當新元素大於所有先有元素師放置在索引length-1

最佳實踐:為了避免新增新元素時產生升級操作,應向同一整數集合新增相同型別的整數

壓縮列表

  • 作為列表鍵和雜湊鍵的底層實現之一
  • 新增或刪除節點都可能造成連鎖更新,連鎖更新最壞時間複雜度為O(<math><msubsup><mi>N</mi><mi></mi><mi>2</mi></msubsup></math>)

物件

  • 字串物件(REDIS_STRING即string)
  • 列表物件(REDIS_LIST即list)
  • 雜湊物件(REDIS_HASH即hash)
  • 集合物件(REDIS_SET即set)
  • 有序集合物件(REDIS_ZSET即zset)

<div align=center>不同型別和編碼的物件</div>

型別編碼物件
REDIS_STRINGREDIS_ENCODING_INT(整數值)使用整數值實現的字串物件
REDIS_STRINGREDIS_ENCODING_EMBSTR(小於32位元組字串)使用embstr編碼的簡單動態字串實現的字串物件
REDIS_STRINGREDIS_ENCODING_RAW(大於32位元組字串)使用簡單字動態字串實現的字串物件
REDIS_LISTREDIS_ENCODING_ZIPLIST(預設配置下,所有元素長度小於64位元組且元素數量小於513,檢視命令:CONFIG GET list-max-ziplist*)使用壓縮列表實現的列表物件
REDIS_LISTREDIS_ENCODING_LINKEDLIST使用雙端連結串列實現的列表物件
REDIS_HASHREDIS_ENCODING_ZIPLIST (預設配置下,所有元素長度小於64位元組且元素數量小於513,檢視命令:CONFIG GET hash-max-ziplist*)使用壓縮列表實現的列表物件
REDIS_HASHREDIS_ENCODING_HT使用字典實現的雜湊物件
REDIS_SETREDIS_ENCODING_INTSET(預設配置下,所有元素都是整數值且元素數量小於513,檢視命令:CONFIG GET set-max-intset-entries)使用整數集合實現的集合物件
REDIS_SETREDIS_ENCODING_HT使用字典實現的集合物件
REDIS_ZSETREDIS_ENCODING_ZIPLIST(預設配置下,所有元素長度小於64位元組且元素數量小於128,檢視命令:CONFIG GET zset-max-ziplist*)使用壓縮列表實現的有序集合物件
REDIS_ZSETREDIS_ENCODING_SKIPLIST使用跳躍連結串列和字典實現的有序集合物件

備註

  1. TYPE KEY(獲取鍵的對應值物件型別)
  2. OBJECT ENCODING KEY(獲取鍵的對應值物件編碼)

記憶體回收、物件共享、空轉時長度

  • 每個物件都有引用計數器,當引用計數為0時物件所佔用的記憶體將被釋放
  • Redis初始化服務時自動建立0-9999的字串物件(包括資料結構中巢狀了字串物件的:linkedlist的列表物件、hashtable的雜湊物件、hashtable的集合物件、zset的有序集合物件),值在對應範圍內的字串物件將共享同一物件
  • 每個物件記錄有最後一次被命令程式訪問的時間,當maxmemory且回收記憶體演算法為volatile-lru或allkeys-lru時記憶體一旦超過maxmemory上限則優先釋放空轉時長較高的鍵值對

最佳實踐:為了最大程度的節省記憶體,應將簡單字元或重複率較高的字串對應成0-9999範圍內的數字。

二、單機資料庫的實現

資料庫

  • Redis有多個資料庫,預設值為16(檢視命令:CONFIG GET databases)
  • 過期鍵有惰性刪除和定期刪除兩種策略
  • 從伺服器不會自主刪除過期鍵

惰性刪除:當讀取的鍵是一個過期鍵時才會將該鍵刪除並返回空。

定期刪除:在規定的時間內分多次遍歷每個資料庫,從expires字典中隨機檢查一部分鍵的過期時間(也即每次執行定期刪除並不一定能把所有的過期鍵都刪除)。

最佳實踐:主從模式下從伺服器在讀取到過期鍵時不會主動刪除且會當成正常鍵返回資料,當資料中包含較多的過期鍵時主伺服器的定期刪除策略可能需要較長時間才能將該過期鍵刪除,因此Redis的主從模式不同於Mysql的主從模式(主寫從讀),如果使用類似Mysql主從的用法時需注意過期資料在一定時間內可能是髒資料。

RDB持久化

  • RDB檔案用於儲存和還原Redis伺服器所有資料庫中的資料
  • SAVE由伺服器程序執行,因此會阻塞伺服器
  • BGSAVE由子程序執行,因此不會阻塞伺服器
  • RDB是一個經過壓縮的二進位制檔案

AOF持久化

  • AOF檔案通過儲存所有修改資料庫的寫命令請求來記錄伺服器的資料庫狀態
  • AOF檔案中所有命令均以Redis命令請求協議儲存
  • 命令請求會先儲存到AOF緩衝區中,再定期儲存到AOF檔案
  • AOF重寫通過讀取資料庫中的鍵值對來重新產生一個AOF檔案,該檔案減少了很多不再需要的命令因此檔案體積更小

事件

  • Redis是由時間事件和檔案事件組成的事件驅動程式
  • 檔案事件處理器是基於Reactor模式實現的網路通訊程式,事件分為讀事件、寫事件
  • 時間事件分為定時事件、週期事件
  • serverCron是一個週期性事件,它是Redis週期性事件的主要函式
  • 因為事件處理在時間事件和檔案事件中輪訓,且不會搶佔,時間事件不一定在設定的時間立即執行

客戶端

  • 客戶端傳送的請求記錄在服務端的輸入緩衝區,該緩衝區大小為1G。
  • 服務端的輸出緩衝區分固定緩衝區(16KB)和可變緩衝區(檢視命令:CONFIG GET client-output-buffer-limit)。
  • Redis預設最大連線數為10000(檢視命令:CONFIG GET maxclients)
  • 網路連線關閉、傳送不合協議格式的命令請求、CLIENT KILL、空轉時間超時、輸入、輸出緩衝區大小超過限制時,客戶端將被關閉。
  • 客戶端的空轉時間超過timeout設定的值時將被關閉(檢視命令:CONFIG GET timeout)。
  • 可變輸出緩衝區分普通客戶端、pubsub(釋出/訂閱模式)、slave三種客戶端限制。預設情況下,普通客戶端無限制(阻塞式的訊息應答模式通常不會造成輸出緩衝區堆積),pubsub客戶端超過32m或持續60s超高8m,slave客戶端超高256m或持續60s超過64m,對於超過限制的客戶端Redis將關閉連線。
  • 最大連線數受系統當前檔案描述符數量限制,最大隻能取檔案描述符數量限制-32(Redis最多會佔用32個檔案描述符)。
  • 如果客戶端是主伺服器、從伺服器、被BLPOP等命令阻塞、正在執行SUBSCRIBE等訂閱命令,將不受timeout設定影響。

伺服器

  • serverCron函式預設每100毫秒執行一次,主要包括更新伺服器狀態資訊、處理服務接收的SIGTERM訊號、管理客戶端資源和資料庫狀態、檢查執行持久化等。

命令請求步驟

  1. 客戶端將命令請求傳送給伺服器
  2. 伺服器讀取命令請求並解析出命令引數
  3. 命令執行器根據引數查詢命令的實現函式,執行實現函式並得出命令回覆
  4. 伺服器將命令回覆返回給客戶端

伺服器啟動步驟

  1. 初始化伺服器狀態
  2. 載入伺服器配置
  3. 初始化伺服器資料結構
  4. 還原資料庫狀態
  5. 執行事件迴圈

三、多機資料庫的的實現

複製

  • Reids 2.8以前沒有部分重同步功能,命令丟失無法檢測,斷線後需要重新執行一次完整同步
  • 部分重同步通過複製偏移量、複製擠壓緩衝區、伺服器執行ID三部分實現
  • 從伺服器預設以1s一次的頻率向主伺服器傳送REPLCONF ACK <replication_offset>(從伺服器當前複製偏移量) 以完成心跳檢測、命令丟失檢測

Sentinel(哨兵)

  • Sentinel是執行在特殊模式下的Redis伺服器,使用不同的命令表
  • Sentinel向被監視的主伺服器以及其屬下的從伺服器建立命令連線和訂閱連線,命令連線用於向主伺服器傳送命令,訂閱連線用於接收__sentinel__:hello頻道的訂閱資訊(感知其他Sentinel的存在)
  • 監視同一主伺服器的Sentinel感知到其他Sentinel的存在後相互建立命令連線,用於主伺服器主觀下線後相互詢問是否同意主觀下線,當收集夠足夠多票數(大於1/2)後判斷為客觀下線並進行故障轉移

叢集

  • 叢集的整個資料庫(叢集模式下只能使用一個資料庫)被分為16384個槽,每個節點會記錄指派給自己的槽以及哪些槽指派給了其他哪個節點
  • 節點在收到命令請求時先檢查所需處理的鍵是否位於自己的槽中,不是則返回MOVED錯誤引導客戶端跳轉正確節點
  • 重新分片工作由redis-trib負責,用於將已指派的槽從源節點轉移到目標節點
  • 重新分片過程中如果客戶端請求一個已經轉移到新節點的鍵則返回ASK錯誤引導客戶端跳轉新節點
  • 叢集中的從節點用於複製主節點並在主節點下線後從中選舉出新的主節點

MOVED錯誤表示所請求的鍵負責權已經轉移到另一節點,ASK錯誤則只是槽正在轉移時的一種臨時性錯誤

四、獨立功能的實現

釋出與訂閱

  • 釋出訂閱分為頻道釋出訂閱和模式釋出訂閱兩種
  • 伺服器狀態在pubsub_channels字典儲存所有頻道訂閱關係,在pubsub_patterns連結串列儲存所有模式訂閱關係

事務

  • 事務是提供了一種將多個命令打包然後一次性按先進先出順序執行的機制,並不具備回滾功能
  • 事務執行過程中不會中斷,直到所有命令都被執行完之後才會結束事務
  • 帶有WATCH命令的事務可以監視某個鍵是否被修改,如果事務執行過程中被修改則客戶端的REDIS_DIRTY_CAS標誌將被開啟,事務將被伺服器拒絕提交

Lua指令碼

  • Redis內嵌Lua執行環境,並對環境中的函式進行一些修改以適應Redis,當需要執行Redis命令時使用偽客戶端
  • Redis使用指令碼字典來儲存所有執行或載入過的Lua指令碼,指令碼的SHA1校驗和作為鍵名
  • Lua指令碼在執行前伺服器會為其設定一個超時處理鉤子,指令碼執行超時時可以使用SCRIPT KILL來中止指令碼或SHUTDOWN nosave關閉整個伺服器

Redis建立Lua執行環境步驟

  1. 建立基礎Lua環境
  2. 載入函式庫到Lua環境中
  3. 建立包含對Redis進行操作的函式的全域性表格
  4. 使用自制隨機函式替代Lua原有帶副作用的隨機函式(自制隨機函式具有以下特徵:①對於相同seed,math.random總產生相同的隨機數序列;②除非顯示修改math.randomseed中的seed,否則均使用math.randomseed(0)初始化seed)
  5. 建立排序輔助函式,Lua環境使用該函式對一部分Redis命令的結果進行排序
  6. 建立可以提供更多詳細錯誤資訊的錯誤報告輔助函式redis.pcall
  7. 保護Lua環境的全域性變數,防止執行指令碼過程中修改全域性變數
  8. 將修改完成後的Lua環境儲存到伺服器狀態的Lua屬性中

排序

  • SORT命令由快速排序演算法實現
  • SORT命令通過將元素儲存在陣列中,再對陣列進行排序

慢查詢日誌

  • Redis預設記錄執行超過10000us的命令(檢視命令:CONFIG GET slowlog-log-slower-than)
  • Redis預設保留128條慢查詢日誌,超過後舊的日誌將被優先刪除(檢視命令:CONFIG GET slowlog-max-len)

源地址 By佐柱

轉載請註明出處,也歡迎偶爾逛逛我的小站,謝謝 :)

相關文章

資料庫 最新文章