redis源碼剖析（三）——基礎數據結構

文章目錄

    • SDS
    • 鏈表
    • 字典

這篇文章關于 Redis 的基礎數據:

SDS

SDS （Simple Dynamic String）是 Redis 最基礎的數據結構。直譯過來就是”簡單的動態字符串“。Redis 自己實現了一個動態的字符串，而不是直接使用了 C 語言中的字符串。

sds 的數據結構：

struct sdshdr {// buf 中已占用空間的長度int len;// buf 中剩余可用空間的長度int free;// 數據空間char buf[];
};

所以一個 SDS 的就如下圖：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-t2YCOSKC-1573627290412)(media/15663750838907/15663751675407.jpg)]
所以我們看到，sds 包含3個參數。buf 的長度 len，buf 的剩余長度，以及buf。

為什么這么設計呢？

  1. 可以直接獲取字符串長度。
    C 語言中，獲取字符串的長度需要用指針遍歷字符串，時間復雜度為 O(n)，而 SDS 的長度，直接從len 獲取復雜度為 O(1)。

  2. 杜絕緩沖區溢出。
    由于C 語言不記錄字符串長度，如果增加一個字符傳的長度，如果沒有注意就可能溢出，覆蓋了緊挨著這個字符的數據。對于SDS 而言增加字符串長度需要驗證 free的長度，如果free 不夠就會擴容整個 buf，防止溢出。

  3. 減少修改字符串長度時造成的內存再次分配。
    redis 作為高性能的內存數據庫，需要較高的相應速度。字符串也很大概率的頻繁修改。 SDS 通過未使用空間這個參數，將字符串的長度和底層buf的長度之間的額關系解除了。buf的長度也不是字符串的長度。基于這個分設計 SDS 實現了空間的預分配和惰性釋放。

    • 預分配
      如果對 SDS 修改后，如果 len 小于 1MB 那 len = 2 * len + 1byte。 這個 1 是用于保存空字節。
      如果 SDS 修改后 len 大于 1MB 那么 len = 1MB + len + 1byte。
    • 惰性釋放
      如果縮短 SDS 的字符串長度，redis并不是馬上減少 SDS 所占內存。只是增加 free 的長度。同時向外提供 API 。真正需要釋放的時候，才去重新縮小 SDS 所占的內存

  • 二進制安全。
    C 語言中的字符串是以 ”\0“ 作為字符串的結束標記。而 SDS 是使用 len 的長度來標記字符串的結束。所以SDS 可以存儲字符串之外的任意二進制流。因為有可能有的二進制流在流中就包含了”\0“造成字符串提前結束。也就是說 SDS 不依賴 “\0” 作為結束的依據。

  • 兼容C語言
    SDS 按照慣例使用 ”\0“ 作為結尾的管理。部分普通C 語言的字符串 API 也可以使用。

鏈表

C語言中并沒有鏈表這個數據結構所以 Redis 自己實現了一個。Redis 中的鏈表是：

typedef struct listNode {// 前置節點struct listNode *prev;// 后置節點struct listNode *next;// 節點的值void *value;} listNode;

非常典型的雙向鏈表的數據結構。

同時為雙向鏈表提供了如下操作的函數：

/** 雙端鏈表迭代器*/
typedef struct listIter {// 當前迭代到的節點listNode *next;// 迭代的方向int direction;} listIter;/** 雙端鏈表結構*/
typedef struct list {// 表頭節點listNode *head;// 表尾節點listNode *tail;// 節點值復制函數void *(*dup)(void *ptr);// 節點值釋放函數void (*free)(void *ptr);// 節點值對比函數int (*match)(void *ptr, void *key);// 鏈表所包含的節點數量unsigned long len;} list;

鏈表的結構比較簡單，數據結構如下：
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-pwkSNd6w-1573627290413)(media/15663750838907/15663752964435.jpg)]

總結一下性質：

  • 雙向鏈表，某個節點尋找上一個或者下一個節點時間復雜度 O(1)。
  • list 記錄了 head 和 tail，尋找 head 和 tail 的時間復雜度為 O(1)。
  • 獲取鏈表的長度 len 時間復雜度 O(1)。

字典

字典數據結構極其類似 java 中的 Hashmap。

Redis的字典由三個基礎的數據結構組成。最底層的單位是哈希表節點。結構如下：

typedef struct dictEntry {// 鍵void *key;// 值union {void *val;uint64_t u64;int64_t s64;} v;// 指向下個哈希表節點，形成鏈表struct dictEntry *next;} dictEntry;

實際上哈希表節點就是一個單項列表的節點。保存了一下下一個節點的指針。 key 就是節點的鍵，v是這個節點的值。這個 v 既可以是一個指針，也可以是一個 uint64_t或者 int64_t 整數。*next 指向下一個節點。

通過一個哈希表的數組把各個節點鏈接起來：

typedef struct dictht {// 哈希表數組dictEntry **table;// 哈希表大小unsigned long size;// 哈希表大小掩碼，用于計算索引值// 總是等于 size - 1unsigned long sizemask;// 該哈希表已有節點的數量unsigned long used;} dictht;

通過圖示我們觀察：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-FVEBYd5O-1573627290413)(media/15663750838907/15663753610286.jpg)]

實際上，如果對java 的基本數據結構了解的同學就會發現，這個數據結構和 java 中的 HashMap 是很類似的，就是數組加鏈表的結構。

字典的數據結構：

typedef struct dict {// 類型特定函數dictType *type;// 私有數據void *privdata;// 哈希表dictht ht[2];// rehash 索引// 當 rehash 不在進行時，值為 -1int rehashidx; /* rehashing not in progress if rehashidx == -1 */// 目前正在運行的安全迭代器的數量int iterators; /* number of iterators currently running */} dict;

其中的dictType 是一組方法，代碼如下：

/** 字典類型特定函數*/
typedef struct dictType {// 計算哈希值的函數unsigned int (*hashFunction)(const void *key);// 復制鍵的函數void *(*keyDup)(void *privdata, const void *key);// 復制值的函數void *(*valDup)(void *privdata, const void *obj);// 對比鍵的函數int (*keyCompare)(void *privdata, const void *key1, const void *key2);// 銷毀鍵的函數void (*keyDestructor)(void *privdata, void *key);// 銷毀值的函數void (*valDestructor)(void *privdata, void *obj);} dictType;

字典的數據結構如下圖：
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-PI20viEC-1573627290414)(media/15663750838907/15663754115428.jpg)]

這里我們可以看到一個dict 擁有兩個 dictht。一般來說只使用 ht[0],當擴容的時候發生了rehash的時候，ht[1]才會被使用。

當我們觀察或者研究一個hash結構的時候偶我們首先要考慮的這個 dict 如何插入一個數據？

我們梳理一下插入數據的邏輯。

  • 計算Key 的 hash 值。找到 hash 映射到 table 數組的位置。

  • 如果數據已經有一個 key 存在了。那就意味著發生了 hash 碰撞。新加入的節點，就會作為鏈表的一個節點接到之前節點的 next 指針上。

  • 如果 key 發生了多次碰撞，造成鏈表的長度越來越長。會使得字典的查詢速度下降。為了維持正常的負載。Redis 會對 字典進行 rehash 操作。來增加 table 數組的長度。所以我們要著重了解一下 Redis 的 rehash。步驟如下：

    • 根據ht[0] 的數據和操作的類型（擴大或縮小），分配 ht[1] 的大小。
    • 將 ht[0] 的數據 rehash 到 ht[1] 上。
    • rehash 完成以后，將ht[1] 設置為 ht[0]，生成一個新的ht[1]備用。

  • 漸進式的 rehash 。

其實如果字典的 key 數量很大，達到千萬級以上，rehash 就會是一個相對較長的時間。所以為了字典能夠在 rehash 的時候能夠繼續提供服務。Redis 提供了一個漸進式的 rehash 實現
rehash的步驟如下：

  1. 分配 ht[1] 的空間，讓字典同時持有 ht[1] 和 ht[0]。
  2. 在字典中維護一個 rehashidx，設置為 0 ，表示字典正在 rehash。
  3. 在rehash期間，每次對字典的操作除了進行指定的操作以外，都會根據 ht[0] 在 rehashidx 上對應的鍵值對 rehash 到 ht[1]上。
  4. 隨著操作進行， ht[0] 的數據就會全部 rehash 到 ht[1] 。設置ht[0] 的 rehashidx 為 -1，漸進的 rehash 結束。
    這樣保證數據能夠平滑的進行 rehash。防止 rehash 時間過久阻塞線程。
  • 在進行 rehash 的過程中，如果進行了 delete 和 update 等操作，會在兩個哈希表上進行。如果是 find 的話優先在ht[0] 上進行，如果沒有找到，再去 ht[1] 中查找。如果是 insert 的話那就只會在 ht[1]中插入數據。這樣就會保證了 ht[1] 的數據只增不減，ht[0]的數據只減不增。

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/382373.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/382373.shtml
英文地址，請注明出處：http://en.pswp.cn/news/382373.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

C++迭代器使用錯誤總結

C++迭代器使用錯誤總結

指針和迭代器的區別： 迭代器： （1）迭代器不是指針，是類模板，表現的像指針。他只是模擬了指針的一些功能，通過重載了指針的一些操作符，->,*, --等封裝了指針，是一…
閱讀更多...
redis源碼剖析（四）跳表

redis源碼剖析（四）跳表

文章目錄整數集合跳躍表壓縮列表總結整數集合 當一個集合只包含整數，且這個集合的元素不多的時候，Redis 就會使用整數集合 intset 。首先看 intset 的數據結構： typedef struct intset {// 編碼方式uint32_t encoding;// 集合包含的元素數量…
閱讀更多...
vivo C/C++工程師 HR視頻面試問題總結20180807

vivo C/C++工程師 HR視頻面試問題總結20180807

一開始沒想到這次視頻面是HR面試，還以為是技術面試，畢竟上次面試的時候技術問題問的相對比較少，所以面試準備方向有點兒錯了，不過還是總結一下具體問題。 1）自我介紹：吸取了上次自我介紹的經驗，…
閱讀更多...
在Redis客戶端設置連接密碼 并演示密碼登錄

在Redis客戶端設置連接密碼 并演示密碼登錄

我們先連接到Redis服務 然后 我們要輸入 CONFIG SET requirepass “新密碼” 例如 CONFIG SET requirepass "A15167"這樣 密碼就被設置成立 A15167 我們 輸入 AUTH 密碼 例如 AUTH A15167這里 返回OK說明成功了 然后 我們退出在登錄就真的需要 redis-cli -h IP地…
閱讀更多...
redis源碼剖析（五）—— 字符串，列表，哈希，集合，有序集合

redis源碼剖析（五）—— 字符串，列表，哈希，集合，有序集合

文章目錄對象REDIS_STRING （字符串）REDIS_LIST 列表REDIS_SET （集合）REDIS_ZSET （有序集合）REDIS_HASH (hash表)int refcount（引用計數器）unsigned lru:REDIS_LRU_BITS對象 對于 Re…
閱讀更多...
函數sscanf小結

函數sscanf小結

1.sscanf用于處理固定格式的字符串&#xff0c;包含在頭文件<cstdio>中&#xff0c;函數原型為&#xff1a; int sscanf(const char *buffer,const char*format,[]argument ]...); 其中:buffer代表著要存儲的數據&#xff0c;format 代表格式控制字符串&#xff0c;arg…
閱讀更多...
redis源碼剖析（六）—— Redis 數據庫、鍵過期的實現

redis源碼剖析（六）—— Redis 數據庫、鍵過期的實現

文章目錄數據庫的實現數據庫讀寫操作鍵的過期實現數據庫的實現 我們先看代碼 server.h/redisServer struct redisServer{...//保存 db 的數組redisDb *db;//db 的數量int dbnum;... }再看redisDb的代碼&#xff1a; typedef struct redisDb {dict *dict; /*…
閱讀更多...
多益網絡 視頻面試面試總結20180816

多益網絡 視頻面試面試總結20180816

1.首先是自我介紹&#xff1a;因為等了半個小時&#xff0c;所以有點兒緊張&#xff0c;只說了一下自己的學校&#xff0c;愛好和興趣&#xff1b; 2.介紹了一個自己的最成功的項目&#xff1a;我介紹了一個關于GPS導航的項目&#xff0c;介紹了項目的內容和項目的一些工作&am…
閱讀更多...
redis源碼剖析（七）—— Redis 數據結構dict.c

redis源碼剖析（七）—— Redis 數據結構dict.c

文章目錄dict.hdict.cdict.h //定義錯誤相關的碼 #define DICT_OK 0 #define DICT_ERR 1//實際存放數據的地方 typedef struct dictEntry {void *key;void *val;struct dictEntry *next; } dictEntry;//哈希表的定義 typedef struct dict {//指向實際的哈希表記錄(用數組開鏈的…
閱讀更多...
簡述linux中動態庫和靜態庫的制作調用流程

簡述linux中動態庫和靜態庫的制作調用流程

假設現在有這些文件&#xff1a;sub.c add.c div.c mul.c mainc head.h&#xff08;前4個.C文件的頭文件&#xff09; 1.靜態庫制作流程 gcc -c sub.c add.c div.c mul.c -->生成 .o目標文件文件 ar rcs libmycal.a *.o …
閱讀更多...
redis源碼剖析（八）—— 當你啟動Redis的時候，Redis做了什么

redis源碼剖析（八）—— 當你啟動Redis的時候，Redis做了什么

文章目錄啟動過程初始化server結構體main函數會調用initServer函數初始化服務器狀態載入持久化文件&#xff0c;還原數據庫開始監聽事件流程圖啟動過程 初始化server結構體從配置文件夾在加載參數初始化服務器載入持久化文件開始監聽事件 初始化server結構體 服務器的運行ID…
閱讀更多...
linux中錯誤總結歸納

linux中錯誤總結歸納

1.使用gcc編譯C文件&#xff0c;C文件在for循環語句中出現變量定義 編譯器提示錯誤&#xff1a;“for”loop initial declarations are only allowed in C99 mode. note:use option -stdc99or-stdgnu99 to compile; 原因&#xff1a;gcc的標準是基于c89的&#xff0c;c89不能在…
閱讀更多...
redis源碼剖析（十一）—— Redis字符串相關函數實現

redis源碼剖析（十一）—— Redis字符串相關函數實現

文章目錄初始化字符串字符串基本操作字符串拼接操作other獲取指定范圍里的字符串將字符串中的所有字符均轉為小寫的形式將字符串中所有字符均轉為大寫的形式字符串比較other#define SDS_ABORT_ON_OOM#include "sds.h" #include <stdio.h> #include <stdlib.…
閱讀更多...
makefile內容小結

makefile內容小結

makefile中每個功能主要分為三部分&#xff1a;目標&#xff0c;依賴條件和命令語句 1.支持對比更新的Makefile寫法&#xff08;只會編譯文件時.o文件和.c文件時間不一致的文件&#xff09; 2.使用makefile自動變量和自定義變量的makefile寫法 其中&#xff1a;這三個符號為ma…
閱讀更多...
事務隔離級別動圖演示

事務隔離級別動圖演示

事務的基本要素&#xff08;ACID&#xff09; 原子性&#xff08;Atomicity&#xff09; 事務開始后所有操作&#xff0c;要么全部做完&#xff0c;要么全部不做&#xff0c;不可能停滯在中間環節。事務執行過程中出錯&#xff0c;會回滾到事務開始前的狀態&#xff0c;所有的…
閱讀更多...
C/C++的優點和缺點

C/C++的優點和缺點

1.C/C語言的優點 C語言是面向過程的語言&#xff0c;常用來編寫操作系統。C語言是從C語言發展過來的&#xff0c;是一門面向對象的語言&#xff0c;它繼承了C語言的優勢&#xff0c;同時也添加了三個主要的內容&#xff1a;Oriented-Object class,Template,STL. 1)C/C可以潛入…
閱讀更多...
C/C++命令行參數那點事

C/C++命令行參數那點事

int main(int argc, char *argv[ ]); 1.命令行參數&#xff1a;在命令行中給定的參數&#xff1b; 2.命令行參數在對函數main的調用時&#xff0c;主要有兩個參數送到main,一個是argc(argument count),命令行參數的個數&#xff0c;另外一個是argv,命令行參數的數組,命令行參…
閱讀更多...
mysql row_id為什么是6字節？為什么是8字節

mysql row_id為什么是6字節？為什么是8字節

mysql row_id是幾個字節&#xff1f; row_id InnoDB表中在沒有默認主鍵的情況下會生成一個6字節空間的自動增長主鍵 row_id是整型還是字符型&#xff1f; 源代碼中 row_id 是 ib_uint64_t 這是 8字節 uint64_t 是整形 為什么是6個字節&#xff1f; P.S. Base64編碼說明 B…
閱讀更多...
linux中的man文檔結構

linux中的man文檔結構

使用命令 man chapter章節號查找的內容
閱讀更多...
偽隨機數和真隨機數

偽隨機數和真隨機數

偽隨機數小項目 猜數字游戲 //C語言 猜數字游戲 https://blog.csdn.net/csdn_kou/article/details/79785709 C語言之隨機數生成超詳解 https://blog.csdn.net/csdn_kou/article/details/79788815 在上面的文章中&#xff0c;使用固定函數就一直是生成固定的隨機結果&#…
閱讀更多...
最新文章

Copyright @ 2022~2023