第二部分 單機數(shù)據(jù)庫的實現(xiàn)

數(shù)據(jù)庫

服務(wù)器中的數(shù)據(jù)庫

• Redis服務(wù)器的所有數(shù)據(jù)庫都保存在redisServer.db數(shù)組中，而數(shù)據(jù)庫的數(shù)量使用redisServer.dbnum屬性保存

切換數(shù)據(jù)庫

• 客戶端通過修改目標數(shù)據(jù)庫指針，讓它指向redisServer.db數(shù)組中的不同元素來切換不同的數(shù)據(jù)庫

數(shù)據(jù)庫鍵空間

• 數(shù)據(jù)庫主要由dict和expires兩個字典域構(gòu)成，其中dict字典負責保存鍵值對，而expires字典則負責鍵的過期時間
• 因為數(shù)據(jù)庫由字典構(gòu)成，因此對數(shù)據(jù)庫的操作都是建立在對字典操作之上
• 數(shù)據(jù)庫的鍵總是一個字符串對象，而值則可以是任意一種Redis對象類型，包括字符串對象、哈希表對象、集合對象、列表對象、有序集合對象。

image

設(shè)置鍵的過期時間

• expires字典的鍵指向數(shù)據(jù)庫中的某個鍵，而值則記錄了數(shù)據(jù)庫鍵的過期時間，過期時間以毫秒為單位的UNIX時間戳

過期鍵刪除策略

• 三種不同的刪除策略

  • 定時刪除
    • 在設(shè)置一個鍵的同時，創(chuàng)建一個定時器，讓定時器在鍵過期時間來臨時，立即執(zhí)行對鍵的刪除操作
    • 優(yōu)點： 對內(nèi)存友好，能盡快地將過期鍵占用的內(nèi)存釋放
    • 缺點： 對時間不友好，如果過期鍵很多，那么會占用大量CPU時間，影響服務(wù)器響應(yīng)時間和吞吐量
  • 惰性刪除
    • 放任過期鍵不管，但是每次從鍵空間中獲取鍵時，都檢查取得的鍵是否過期，如果過期，就刪除該鍵；如果沒有過期，就返回該鍵
    • 優(yōu)點：對時間友好，只有當取出過期鍵時，才將該鍵刪除
    • 缺點：對空間不友好，大量過期無用鍵占用內(nèi)存，由內(nèi)存泄露的風險
  • 定期刪除
    • 每個一段時間，程序就對數(shù)據(jù)庫進行一次檢查，刪除里面的過期鍵，至于要刪除多少過期鍵，以及要檢查多少個數(shù)據(jù)庫，由算法決定
    • 優(yōu)點： 對上面兩種策略的折衷。 對內(nèi)存友好，對空間友好
    • 關(guān)鍵是如何決定刪除操作執(zhí)行的時常和頻率

• Redis的過期鍵刪除策略

  • Redis使用的是 定期刪除+ 惰性刪除 保證過期鍵一定能被刪除。并合理利用CPU時間和避免內(nèi)存空間浪費

  • 惰性刪除 ： 在執(zhí)行命令之前，對輸入的鍵進行過期檢查

  • 定期刪除 ： 在規(guī)定時間內(nèi)，分多次遍歷服務(wù)器中多個數(shù)據(jù)庫，從數(shù)據(jù)庫中的expires字典隨機檢查一部分鍵的過期時間，并刪除其中的過期鍵。

AOF、RDB和復(fù)制功能對過期鍵的處理

• 執(zhí)行SAVE命令或者BGSAVE命令所產(chǎn)生的新RDB文件不會包含已過期的鍵
• 執(zhí)行BGREWRITEAOF命令所產(chǎn)生的重寫AOF文件不會包含已過期的鍵
  • 當一個過期鍵被刪除之后，服務(wù)器會追加一條DEL命令到現(xiàn)有的AOF文件末尾，顯示地刪除過期鍵
• 當載入RDB or AOF文件時，會對文件保存的鍵進行檢查，過期的鍵會被忽略。
• 從服務(wù)器即使發(fā)現(xiàn)過期鍵也不會主動刪除，而是等待主節(jié)點發(fā)來DEL命令，這種統(tǒng)一、中心化的過期鍵刪除策略可以保證主從服務(wù)器的數(shù)據(jù)一致性。

數(shù)據(jù)庫通知

• 當Redis命令對數(shù)據(jù)庫進行修改之后 ， 服務(wù)器會根據(jù)配置向客戶端發(fā)出數(shù)據(jù)庫通知 （PUB/SUB）
  • 鍵空間通知： 某個鍵執(zhí)行了什么命令（SET / EXPIRE / DEL）
• 鍵事件通知： 某個命令被哪些鍵執(zhí)行了 （KEY1 / KEY2 / KEY3）

RDB持久化

前置知識： 進程和子進程

image

可以看出，子進程和父進程的代碼區(qū)是共享的，而數(shù)據(jù)區(qū)和PCB塊是父進程的副本。

子PCB中的PID字段為新分配子進程PID，數(shù)據(jù)集字段為數(shù)據(jù)集地址。

父進程和子進程是可以并行執(zhí)行的?；ゲ桓蓴_。

RDB文件的創(chuàng)建與載入

• RDB持久化通過保存數(shù)據(jù)庫中的鍵值對來記錄數(shù)據(jù)庫的狀態(tài) ， 生成經(jīng)過壓縮的二進制文件。

• 創(chuàng)建過程

  • SAVE命令由服務(wù)器進程直接執(zhí)行保存操作，因此該命令會阻塞服務(wù)器
  • BGSAVE由子進程執(zhí)行保存操作，所以該命令不會阻塞服務(wù)器

• 載入過程

  • 如果服務(wù)器開啟了AOF持久化功能，那么服務(wù)器會優(yōu)先使用AOF文件還原數(shù)據(jù)庫狀態(tài)
  • 如果AOF處于關(guān)閉狀態(tài)，服務(wù)器才會使用RDB文件來還原數(shù)據(jù)庫狀態(tài)(前者丟失的數(shù)據(jù)更少)

自動間隔性保存

• 服務(wù)器狀態(tài)中會保存所有用save選項設(shè)置的保存條件，當任意一個保存條件被滿足時，服務(wù)器會自動執(zhí)行BGSAVE命令。

  #redis.conf
  格式： save 時間 修改次數(shù)
  save 900 1   （900s內(nèi)修改1次）
  save 300 10
  save 60 10000 （60s內(nèi)修改10000次）
  

  struct redisServer{
      struct saveparam *saveparams; //記錄保存條件的數(shù)據(jù)
      long long dirty;  //修改計數(shù)器
      time_t lastsave;  //上一次執(zhí)行保存的時間
  }
  

RDB文件的結(jié)構(gòu)

• 對于不同類型的鍵值對，RDB文件會使用不同的方式來保存他們

image

AOF持久化

AOF（Append Only File）持久化實現(xiàn)

• RDB持久化通過保存數(shù)據(jù)庫中的鍵值對來記錄數(shù)據(jù)庫狀態(tài)的不同

• AOF持久化是通過保存Redis服務(wù)器所執(zhí)行的寫命令來記錄數(shù)據(jù)庫狀態(tài)的

  image

• AOF文件中所有命令都是以Redis命令請求協(xié)議的格式（文本協(xié)議）保存的

• 命令請求會先保存到AOF緩沖區(qū)里面，之后再定期寫入并同步到AOF文件中

  • 由于內(nèi)存和磁盤的輸入/輸出速度不匹配，因此會將數(shù)據(jù)先寫入緩沖區(qū)。系統(tǒng)提供了fsync, fdatasync兩個同步函數(shù)（系統(tǒng)調(diào)用），讓操作系統(tǒng)立即將緩沖區(qū)的數(shù)據(jù)寫入硬盤中，減少緩沖區(qū)由于宕機而丟失數(shù)據(jù)的影響

• appendfsync選項的不通值對AOF持久化功能的安全性和Redis服務(wù)器的性能有很大的影響

  • always : 每個事件循環(huán)都將aof_buf緩沖區(qū)內(nèi)容寫入同步到AOF文件
  • everysec（默認） ： 每個事件循環(huán)后，判斷上一次AOF是否間隔1S，如果是，則將aof_buf緩沖區(qū)內(nèi)容寫入同步到AOF文件。 因此就算故障停機，緩存也只丟失1S的數(shù)據(jù)。
  • no ： 什么時候?qū)⒕彌_區(qū)內(nèi)容同步到AOF文件中，由操作系統(tǒng)決定

AOF文件的載入與數(shù)據(jù)還原

• 服務(wù)器只要載入并重新執(zhí)行保存在AOF文件中的命令（使用偽客戶端），就可以還原數(shù)據(jù)庫本來的狀態(tài)了。

AOF重寫

• 為了解決AOF體積膨脹的問題，提供了AOF重寫機制。AOF重寫可以產(chǎn)生一個新的AOF文件，這個新的AOF文件和原有的AOF文件保存的數(shù)據(jù)庫狀態(tài)是一樣的，但體積更小
• AOF重寫是一個由歧義的名字，程序無需對現(xiàn)有AOF文件進行任何裝入、分析和寫入操作。它是通過讀取數(shù)據(jù)庫中的鍵值對來實現(xiàn)的。
• AOF重寫程序放在子進程中執(zhí)行，此時服務(wù)器進程可以繼續(xù)處理命令請求
• 子進程帶有服務(wù)器進程數(shù)據(jù)的副本（數(shù)據(jù)一致性問題），那么如果在重寫過程中有新的寫請求更改數(shù)據(jù)庫狀態(tài)，就會產(chǎn)生當前數(shù)據(jù)庫狀態(tài)與重寫后的AOF文件狀態(tài)不一致問題。
• 在執(zhí)行BGREWRITEAOF命令時，Redis服務(wù)器會維護一個AOF重寫緩沖區(qū)，該緩沖區(qū)會在子進程創(chuàng)建新AOF文件期間，記錄服務(wù)器執(zhí)行的所有寫命令。當子進程完成創(chuàng)建新AOF文件的工作后，服務(wù)器會將重寫緩沖區(qū)中的所有內(nèi)容追加到新的AOF文件的末尾，使得新舊兩個AOF文件所保存的數(shù)據(jù)狀態(tài)一致。隨后，用新的AOF文件替換舊的AOF文件，以此來完成AOF文件重寫操作
• image
  • 在AOF重寫期間，服務(wù)器的執(zhí)行工作
    • 執(zhí)行客戶端的命令
    • 將執(zhí)行后的寫命令追加到AOF緩沖區(qū)（保證舊的AOF文件完整）
    • 將執(zhí)行后的寫命令追加到AOF重寫緩沖區(qū)（用于解決數(shù)據(jù)不一致問題）

事件

Redis服務(wù)器是一個事件驅(qū)動程序，服務(wù)器處理的事件分為文件事件和時間事件兩類

文件事件

• 文件事件處理器是基于Reactor模式實現(xiàn)的網(wǎng)絡(luò)通信程序
• 文件事件處理器使用IO多路復(fù)用程序來同時監(jiān)聽多個套接字。并根據(jù)套接字目前執(zhí)行的任務(wù)來為套接字關(guān)聯(lián)不同的事件處理器
• 當被監(jiān)聽的套接字準備好執(zhí)行連接應(yīng)答（accept）、讀取(read)、寫入(write)、關(guān)閉(close)時，與操作對應(yīng)的文件事件就會產(chǎn)生，這時文件事件處理器就會調(diào)用套接字之前關(guān)聯(lián)好的事件處理器來處理這些事件。
• 文件事件是對套接字操作的抽象，每次套接字變?yōu)榭蓱?yīng)答(acceptable)、可寫(writeable)或者可讀(reable)時，相應(yīng)的文件事件就會產(chǎn)生
• 文件事件分為AE_READABLE事件（讀事件）和AE_WRITEABLE事件（寫事件）兩類

image

• 一次完整的客戶端與服務(wù)端連接事件示例

  • Redis服務(wù)器運行時， 將連接應(yīng)答處理器與 AE_READABLE事件關(guān)聯(lián)起來

  • 當Redis客戶端發(fā)起連接時，那么監(jiān)聽套接字將產(chǎn)生AE_READABLE事件，觸發(fā)連接應(yīng)答處理器執(zhí)行。處理跟客戶端建立連接，并將客戶端套接字的AE_READABLE事件與命令請求處理器關(guān)聯(lián)起來

  • 當客戶端向redis發(fā)起請求的時候，那么客戶端套接字將產(chǎn)生AE_READABLE事件，然后由對應(yīng)的命令請求處理器來處理。讀取客戶端的命令內(nèi)容，并傳給相應(yīng)程序執(zhí)行。

  • 那么當redis準備好給客戶端響應(yīng)數(shù)據(jù)之后，服務(wù)端會將AE_WRITEABLE事件跟命令回復(fù)處理器關(guān)聯(lián)起來。當客戶端準備嘗試讀取響應(yīng)數(shù)據(jù)時，客戶端套接字就會產(chǎn)生AE_WRITEABLE事件，觸發(fā)命令回復(fù)處理器執(zhí)行處理，將準備好的數(shù)據(jù)返回給客戶端。 當回復(fù)寫完時，服務(wù)器就會解除客戶端套接字的AE_WRITABLE事件與命令回復(fù)處理器之間的關(guān)聯(lián)。

時間事件

• 時間事件分為定時事件和周期性事件；定時事件只在指定時間到達一次，而周期性事件則每隔一段事件到達一次。

• 服務(wù)器在一般情況下只執(zhí)行serverCorn函數(shù)一個時間事件，并且是周期性的(100ms一次)

  事件實現(xiàn)的三個屬性：
  id:時間事件全局ID   ，  when:事件到達時間    timeProc:事件處理函數(shù)
  與一個由事件節(jié)點構(gòu)成的無序鏈表
  

事件的調(diào)度與執(zhí)行

• 文件事件和時間事件之間是合作關(guān)系，服務(wù)器會輪流處理這兩種事件，并且處理事件過程中不會發(fā)生搶占。

• 時間事件的實際處理事件通常會比設(shè)定的到達晚一些(因為無法中斷文件事件)

• ServerCron是Redis周期性事件的主要函數(shù)。 它的工作主要包括

  • 更新服務(wù)器的各類統(tǒng)計信息，如時間，內(nèi)存占用
  • 清理數(shù)據(jù)庫過期鍵值對
  • 嘗試進行AOF和RDB操作等等

客戶端

• 服務(wù)器狀態(tài)結(jié)構(gòu)使用clients鏈表表示連接了多少個客戶端狀態(tài),新添加的客戶端狀態(tài)會被放到鏈尾

• 客戶端狀態(tài)flags屬性使用不同標志來表示客戶端的角色,以及客戶端當前所在狀態(tài)

• 輸入緩沖區(qū)記錄了客戶端發(fā)送的命令請求,這個緩沖區(qū)大小不超過1GB

• 客戶端使用argv , argc兩個屬性記錄命令的參數(shù)和個數(shù) , 而cmd屬性記錄了客戶端要執(zhí)行命令的實現(xiàn)函數(shù)

  image

• 客戶端有固定大小緩沖區(qū)和可變大小緩沖區(qū)兩種, 其中固定大小緩沖區(qū)最大大小為16KB , 而可變大小緩沖區(qū)(由多個緩沖區(qū)組成, 用鏈表鏈接)最大大小不能超過服務(wù)器設(shè)置的硬性限制值

• 輸出緩沖區(qū)限制值有兩種,如果輸出緩沖區(qū)的大小超過了服務(wù)器設(shè)置的硬性限制, 那么客戶端會被立即關(guān)閉 ; 除此之外 ; 如果客戶端在一定時間內(nèi),一直超過服務(wù)器設(shè)置的軟性限制,那么客戶端也會關(guān)閉.

  #設(shè)置硬性 , 軟性鏈接
  命令名  客戶端角色  硬性鏈接  軟性鏈接  軟性鏈接時長
  client-output-buffer-limit normal 0 0 0
  client-output-buffer-limit slave 256mb 64mb 60
  client-output-buffer-limit pubsub 32mb 8mb 60
  

• 客戶端關(guān)閉的原因 : 網(wǎng)絡(luò)連接關(guān)閉 ; 發(fā)送了不合格時的命令請求 ; 成為CLIENT KILL目標 ; 空轉(zhuǎn)時間超時 ; 輸出緩沖區(qū)的大小超出限制.

服務(wù)端

• 一個命令請求從發(fā)送到完成要經(jīng)歷的步驟:
  • 客戶端將命令請求發(fā)給服務(wù)器
  • 服務(wù)器讀取命令請求,并分析命令參數(shù)
  • 命令執(zhí)行器根據(jù)參數(shù)查找命令的實現(xiàn)函數(shù),然后執(zhí)行實現(xiàn)函數(shù)并得出命令回復(fù)
    • 執(zhí)行預(yù)備操作: 如檢驗命令的格式 ; 內(nèi)存是否足夠 ; 命令此時是否合法 ; 查看是否開啟事務(wù)
    • 調(diào)用命令實現(xiàn)函數(shù)
    • 執(zhí)行后續(xù)操作: 更改統(tǒng)計信息,如耗費時長 ; 如果開啟了AOF還要往緩沖區(qū)寫數(shù)據(jù) ; 如果它是master,那么還要將數(shù)據(jù)同步到從服務(wù)器
  • 服務(wù)器將命令回復(fù)返回給客戶端
• ServerCron函數(shù)(每隔100ms執(zhí)行一次,維護服務(wù)器相關(guān)資源,并做統(tǒng)計)
  • 更新服務(wù)器時間緩存
  • 更新LRU時鐘 (空轉(zhuǎn)時間 = LRU時鐘 - 某個鍵上次訪問時間 )
  • 更新服務(wù)器每秒執(zhí)行的命令數(shù) (統(tǒng)計吞吐量) ; 更新內(nèi)存峰值
  • 處理SIGTERM信號(中斷信號)
  • 管理數(shù)據(jù)庫資源(檢查過期鍵)
  • 將AOF緩沖區(qū)內(nèi)容寫入AOF (每次事件循環(huán)時都會做出檢查)
• 服務(wù)器從啟動到能夠處理客戶端請求經(jīng)過的步驟
  • 初始化服務(wù)器狀態(tài)
  • 載入服務(wù)器配置
  • 初始化服務(wù)器數(shù)據(jù)結(jié)構(gòu)
  • 還原數(shù)據(jù)庫狀態(tài)
  • 執(zhí)行事件循環(huán)