您好,登錄后才能下訂單哦!
本文轉自互聯(lián)網
本系列文章將整理到我在GitHub上的《Java面試指南》倉庫,更多精彩內容請到我的倉庫里查看
https://github.com/h3pl/Java-Tutorial
喜歡的話麻煩點下Star哈
文章首發(fā)于我的個人博客:
www.how2playlife.com
本文是微信公眾號【Java技術江湖】的《探索Redis設計與實現(xiàn)》其中一篇,本文部分內容來源于網絡,為了把本文主題講得清晰透徹,也整合了很多我認為不錯的技術博客內容,引用其中了一些比較好的博客文章,如有侵權,請聯(lián)系作者。
該系列博文會告訴你如何從入門到進階,Redis基本的使用方法,Redis的基本數(shù)據(jù)結構,以及一些進階的使用方法,同時也需要進一步了解Redis的底層數(shù)據(jù)結構,再接著,還會帶來Redis主從復制、集群、分布式鎖等方面的相關內容,以及作為緩存的一些使用方法和注意事項,以便讓你更完整地了解整個Redis相關的技術體系,形成自己的知識框架。
如果對本系列文章有什么建議,或者是有什么疑問的話,也可以關注公眾號【Java技術江湖】聯(lián)系作者,歡迎你參與本系列博文的創(chuàng)作和修訂。
這周開始學習 Redis,看看Redis是怎么實現(xiàn)的。所以會寫一系列關于 Redis的文章。這篇文章關于 Redis 的基礎數(shù)據(jù)。閱讀這篇文章你可以了解:
三個數(shù)據(jù)結構 Redis 是怎么實現(xiàn)的。
SDS (Simple Dynamic String)是 Redis 最基礎的數(shù)據(jù)結構。直譯過來就是”簡單的動態(tài)字符串“。Redis 自己實現(xiàn)了一個動態(tài)的字符串,而不是直接使用了 C 語言中的字符串。
sds 的數(shù)據(jù)結構:
struct sdshdr {
// buf 中已占用空間的長度 int len;
// buf 中剩余可用空間的長度 int free;
// 數(shù)據(jù)空間
char buf[];
}
所以一個 SDS 的就如下圖:
所以我們看到,sds 包含3個參數(shù)。buf 的長度 len,buf 的剩余長度,以及buf。
為什么這么設計呢?
可以直接獲取字符串長度。
C 語言中,獲取字符串的長度需要用指針遍歷字符串,時間復雜度為 O(n),而 SDS 的長度,直接從len 獲取復雜度為 O(1)。
杜絕緩沖區(qū)溢出。
由于C 語言不記錄字符串長度,如果增加一個字符傳的長度,如果沒有注意就可能溢出,覆蓋了緊挨著這個字符的數(shù)據(jù)。對于SDS 而言增加字符串長度需要驗證 free的長度,如果free 不夠就會擴容整個 buf,防止溢出。
減少修改字符串長度時造成的內存再次分配。
redis 作為高性能的內存數(shù)據(jù)庫,需要較高的相應速度。字符串也很大概率的頻繁修改。 SDS 通過未使用空間這個參數(shù),將字符串的長度和底層buf的長度之間的額關系解除了。buf的長度也不是字符串的長度?;谶@個分設計 SDS 實現(xiàn)了空間的預分配和惰性釋放。
二進制安全。
C 語言中的字符串是以 ”\0“ 作為字符串的結束標記。而 SDS 是使用 len 的長度來標記字符串的結束。所以SDS 可以存儲字符串之外的任意二進制流。因為有可能有的二進制流在流中就包含了”\0“造成字符串提前結束。也就是說 SDS 不依賴 “\0” 作為結束的依據(jù)。
兼容C語言
SDS 按照慣例使用 ”\0“ 作為結尾的管理。部分普通C 語言的字符串 API 也可以使用。
C語言中并沒有鏈表這個數(shù)據(jù)結構所以 Redis 自己實現(xiàn)了一個。Redis 中的鏈表是:
typedef struct listNode {
// 前置節(jié)點 struct listNode *prev;
// 后置節(jié)點 struct listNode *next;
// 節(jié)點的值 void *value;} listNode;
非常典型的雙向鏈表的數(shù)據(jù)結構。
同時為雙向鏈表提供了如下操作的函數(shù):
/* * 雙端鏈表迭代器 */typedef struct listIter {
// 當前迭代到的節(jié)點 listNode *next;
// 迭代的方向 int direction;} listIter;
/* * 雙端鏈表結構
*/typedef struct list {
// 表頭節(jié)點 listNode *head;
// 表尾節(jié)點 listNode *tail;
// 節(jié)點值復制函數(shù) void *(*dup)(void *ptr);
// 節(jié)點值釋放函數(shù) void (*free)(void *ptr);
// 節(jié)點值對比函數(shù) int (*match)(void *ptr, void *key);
// 鏈表所包含的節(jié)點數(shù)量 unsigned long len;} list;
鏈表的結構比較簡單,數(shù)據(jù)結構如下:
總結一下性質:
字典數(shù)據(jù)結構極其類似 java 中的 Hashmap。
Redis的字典由三個基礎的數(shù)據(jù)結構組成。最底層的單位是哈希表節(jié)點。結構如下:
typedef struct dictEntry {
// 鍵
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下個哈希表節(jié)點,形成鏈表
struct dictEntry *next;
} dictEntry;
實際上哈希表節(jié)點就是一個單項列表的節(jié)點。保存了一下下一個節(jié)點的指針。 key 就是節(jié)點的鍵,v是這個節(jié)點的值。這個 v 既可以是一個指針,也可以是一個
uint64_t
或者
int64_t
整數(shù)。*next 指向下一個節(jié)點。
通過一個哈希表的數(shù)組把各個節(jié)點鏈接起來:
typedef struct dictht {
// 哈希表數(shù)組
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩碼,用于計算索引值
// 總是等于 size - 1
unsigned long sizemask;
// 該哈希表已有節(jié)點的數(shù)量
unsigned long used;
} dictht;
dictht
通過圖示我們觀察:
實際上,如果對java 的基本數(shù)據(jù)結構了解的同學就會發(fā)現(xiàn),這個數(shù)據(jù)結構和 java 中的 HashMap 是很類似的,就是數(shù)組加鏈表的結構。
字典的數(shù)據(jù)結構:
typedef struct dict {
// 類型特定函數(shù)
dictType *type;
// 私有數(shù)據(jù)
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 當 rehash 不在進行時,值為 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
// 目前正在運行的安全迭代器的數(shù)量
int iterators; /* number of iterators currently running */
} dict;
其中的dictType 是一組方法,代碼如下:
免責聲明:本站發(fā)布的內容(圖片、視頻和文字)以原創(chuàng)、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據(jù),一經查實,將立刻刪除涉嫌侵權內容。