天天看點

redis的五種基本資料類型及其内部實作詳解

小夥伴們大家好呀,好久不見啦(十天沒寫部落格呢。hh),最近沒有偷懶哦,而是在學習Redis。 好了廢話不多說,上幹貨吧!

一、redis的五種資料類型

redis作為目前最流行的Key-Value類型的記憶體資料庫,對于資料庫的操作都在記憶體中進行,并可定期的将資料異步的持久化到磁盤之上。由于是純記憶體的操作,是以它的性能比普通的關系型資料庫高出很多,同時由于是單線程串行的執行指令,是以也避免了加鎖和釋放鎖的開銷。相比于memcache,redis的每個value值最大可存儲1GB,而memcache隻有10MB,同時redis在速度上也快于memcache,還可以持久化。redis最大的特點則是,它可以支援五種基本資料類型,分别是字元串(string),清單(list),集合(set),有序集合(zset)以及哈希(hash),下面具體介紹下它們的特點以及内部實作。

二、redisObject

在redis中每個value都是以一個redisObject結構來表示,如下:

typedef struct redisObject{
//類型
unsigned type:4;
//編碼
unsigned encoding:4;
//指向底層資料結構的指針
void *ptr;
//引用計數器
int refCount;
//最後一次的通路時間
unsigned lru:
}
           

type:

type就是指這個對象的資料類型,即我們平常所認知的redis的五種資料類型,可以通過TYPE指令檢視一個對象的資料類型:

127.0.0.1:6379> set a 123
OK
127.0.0.1:6379> type a
string
127.0.0.1:6379> hmset b name jack age 12
OK
127.0.0.1:6379> type b
hash
127.0.0.1:6379> lpush c 1 2 3
(integer) 3
127.0.0.1:6379> type c
list
127.0.0.1:6379> sadd d 1 2 3
(integer) 3
127.0.0.1:6379> type d
set
127.0.0.1:6379> zadd e 2 a 3 b
(integer) 2
127.0.0.1:6379> type e
zset
127.0.0.1:6379> 

           

encoding:

表示redisObject對象的底層編碼實作,主要有簡單動态字元串,連結清單,字典,跳躍表,整數集合以及壓縮清單,每一個value都是由兩種及以上的上述編碼所構成,後面詳細展出

*ptr

用于指向底層實作資料結構的指針

lru:

最後一次通路該對象的時間,可以通過Object idletime檢視目前時間距離該鍵的lru的時間,即空轉時間如下:

127.0.0.1:6379> set cbd 123
OK
127.0.0.1:6379> object idletime cbd
(integer) 90
127.0.0.1:6379> object idletime cbd
(integer) 95
127.0.0.1:6379> object idletime cbd
(integer) 98
127.0.0.1:6379> get cbd //通路了該鍵,是以lru重置
"123"
127.0.0.1:6379> object idletime cbd
(integer) 3
127.0.0.1:6379> 
           

refCount

引用計數器,當建立一個對象的時間便将它的值初始化為1,當它被其它程式引用之時則加1,不再被引用則減1,當它的引用計數值變為0時,對象所占用的記憶體就會被釋放。是以它主要有兩個用途,記憶體回收的标志以及用于對象共享。

對象共享:當建立的兩個或多個鍵都是整數值并且相同時,則它們的鍵會共享這一個值對象,這樣可以減少記憶體的配置設定和回收,可以用OBJECT REFCOUNT檢視引用情況,如下:

127.0.0.1:6379> set first 123
OK
127.0.0.1:6379> OBJECT refcount first
(integer) 1
127.0.0.1:6379> set second 123
OK
127.0.0.1:6379> OBJECT refcount second
(integer) 2
127.0.0.1:6379> OBJECT refcount first
(integer) 2
127.0.0.1:6379> 

           

redis在初始化伺服器之時,會預設建立包含了值為0-9999的對象,當建立的鍵的值處于這個範圍之時,則直接添加引用即可。

struct sdshdr{
//記錄buf數組中已使用位元組的長度
int len;
//記錄buf數組中剩餘空間的長度
int free;
//位元組數組,用于存儲字元串
char buf[];
};
           

一個SDS示例如下:

redis的五種基本資料類型及其内部實作詳解

當free為0時表示沒有任何未使用的空間,len表示字元串的長度,buf中存儲每一個位元組以及空字元,由于SDS遵循了C字元串以為’\0’結尾的特點,是以它也可以直接重用部分C函數庫裡的函數。

相比于C字元串,SDS具有以下特點:擷取長度的時間複雜度為O(1),因為len直接儲存了目前字元串的長度;避免緩存區溢出,當C字元串進行拼接之時,如果未事先對目前字元串的空間進行調整,則可能會導緻目前字元串的資料溢出,導緻拼接過來的字元串内容被意外的修改,而SDS在拼接之前會進行自動的調整和擴充;減少記憶體配置設定次數,在SDS拼接發生以後,如果此時的len小于1MB則它會多配置設定和len大小相同的未使用空間,用free表示,如果大于1MB,則會配置設定1MB的為使用空間;惰性空間釋放,當字元串進行縮短的時候,程式并不會立即回收空間(也可以調用API立即釋放),而是記錄到free之中,以便于後序拼接的使用。

編碼:

字元串對象的編碼可以是int、raw或者embstr。其中int表示整型的值,embstr表示小于等于39位元組的字元串值,剩餘的均用raw表示,并且int和embstr都是隻讀的,一旦發生了append操作,即會轉換為raw。如下:

127.0.0.1:6379> set age 12
OK
127.0.0.1:6379> Object encoding age
"int"
127.0.0.1:6379> APPEND age 3
(integer) 3
127.0.0.1:6379> Object encoding age
"raw"
127.0.0.1:6379> set name jack
OK
127.0.0.1:6379> Object encoding name
"embstr"
127.0.0.1:6379> APPEND name ja
(integer) 6
127.0.0.1:6379> Object encoding name
"raw"

           

四、清單對象

連結清單提供了節點重排以及節點順序通路的能力,redis中的清單對象主要是由壓縮清單和雙端連結清單實作。

雙端連結清單(linkedlist)結構如下:

type struct list{
//表頭節點
listNode *head;
//表尾節點
listNode *tail;
//包含的節點總數
unsigned long len;
//一些操作函數 dup free match...
};
           

一個連結清單示例:

redis的五種基本資料類型及其内部實作詳解

其中每個節點都有一個prev指針和一個next指針,而節點中的value則是清單對象具體的值。

壓縮清單(ziplist)結構如下:

type struct ziplist{
//整個壓縮清單的位元組數
uint32_t zlbytes;
//記錄壓縮清單尾節點到頭結點的位元組數,直接可以求節點的位址
uint32_t zltail_offset;
//記錄了節點數,有多種類型,預設如下
uint16_t zllength;
//節點
清單節點 entryX;
           

一個壓縮清單示例:

redis的五種基本資料類型及其内部實作詳解

而每個清單節點中主要包括以下幾項:previous_entry_length,記錄了壓縮清單中前一節點的位元組長度,當小于254位元組時,它的長度為1位元組,當大于254位元組時,長度為5位元組且後4位元組儲存真正的長度,用于表尾向表頭周遊;content,節點所存儲的内容,可以是一個位元組數組或者整數;encoding,記錄content屬性中所儲存的資料類型以及長度。

編碼:

當清單對象所存儲的字元串元素長度小于64位元組并且元素數量小于512個時,使用ziplist編碼,否則使用linkedlist編碼,如下:

127.0.0.1:6379> rpush zip "hello" "world"
(integer) 2
127.0.0.1:6379> OBJECT encoding zip
"ziplist"
127.0.0.1:6379> rpush zip "fffffffffffffffffffffzzzzzzzzzzzzzzzzzzzzzzzzzzzzzkkkkkkkkkkkkkkkkkkkkkkkkkcccccccccc"
(integer) 3
127.0.0.1:6379> OBJECT encoding zip
"linkedlist"
127.0.0.1:6379> 

           

五、集合對象

整數集合與字典:

集合對象的編碼可以是整數集合(intset)或者字典(hashtable)。

整數集合結構如下:

typedef struct intset{
//編碼方式
uint32_t encoding;
//元素數量
uint32_t length;
//存儲元素的數組
int8_t contents[];
}
           

整數集合的每個元素都是contents數組的一個數組項,各個項在數組中按值得大小從小到大有序排列,并且不包含重複的項。contents數組中元素的類型由encoding決定,當新加入元素之時,如果元素的編碼大于contents是數組的編碼,則會将所有元素的編碼更新為新加入元素的編碼,然後再插入。編碼不會發生降級。

字典的結構如下:

typedef struct dict{
//類型特定函數
dictType *type;
//哈希表 兩個,一個用于實時存儲,一個用于rehash
dictht ht[2];
//rehash索引 資料遷移時使用
unsigned rehashidx;
}
           

而哈希表的結構如下:

typedef struct dictht{
//哈希表數組
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表掩碼,總是等于size-1,存儲時計算索引值
unsigned long sizemask;
//已有元素數量
unsigned long used;
}
           

一個字典示例如下:

redis的五種基本資料類型及其内部實作詳解

其中鍵值對都儲存在節點dictEntry之中,并且通過拉鍊法解決哈希沖突,存儲時通過MurmurHash算法來計算鍵的哈希值,能夠更好的提供随機分布性且速度也快。擴容時時采用漸進式的rehash,采用分而治之的方法,通過改變rehashidx的值,來一個個将元素移動到ht[1]中,完成以後将ht[1]變為ht[0],原先的ht[0]變為ht[1],同時将redhashidx置為-1。

編碼:

當集合對象所儲存的元素都是整數值且元素數量不超過512個時,使用intset編碼,否則使用hashtable編碼,如下:

127.0.0.1:6379> sadd cloud 1 2 3 4 5
(integer) 5
127.0.0.1:6379> object encoding cloud
"intset"
127.0.0.1:6379> sadd cloud a b c
(integer) 3
127.0.0.1:6379> object encoding cloud
"hashtable"
           

六、有序集合

跳躍表

有序集合的編碼可以是壓縮清單(ziplist)或者跳躍表(skiplist)。

跳躍表的結構如下:

typedef struct zskiplist{
//跳躍表的頭結點
zskiplistNode header;
//尾節點
zskiplistNode tail;
//跳躍表中層數最大的節點的層數(不包括頭結點)
unsigned long level;
//跳躍表長度(不包括頭節點)
unsigned int length;
           

其中的跳躍表節點結構如下:

typedef struct zskiplistNode{
//後退指針
struct zskiplistNode *backward;
//分值
double score;
//成員對象
robj *obj;
//層
struct zskiplistLevel{
//前進指針
struct zskiplistNode *forward;
//跨度
unsigned int span;
}level[];
};
           

每個level數組可以包含多個元素,裡面存儲有指向其他節點(不是下一個)的指針,可以加快通路速度;跨度用于表示兩個節點之間的距離,排位時使用;後退指針依次的從後向前通路;分值用于排序;成員是一個指向字元串對象的指針。

編碼:

當元素數量小于128個并且所有元素成員的長度都小于64位元組之時使用ziplist編碼,否則使用skiplist編碼,如下:

127.0.0.1:6379> zadd test 2 a 3 b
(integer) 2
127.0.0.1:6379> OBJECT encoding test
"ziplist"
127.0.0.1:6379> zadd test 4 ffffffffffffffffffffffffffffffffffffffffffffffffffffffffqwqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq
(integer) 1
127.0.0.1:6379> OBJECT encoding test
"skiplist"
           

七、哈希

哈希對象的編碼可以是壓縮清單(ziplist)或者字典(hashtable),當哈希對象儲存的所有鍵值對的鍵和值得長度都小于64位元組并且元素數量小于512個時使用ziplist,否則使用hashtable。使用ziplist時,是依次将鍵和值壓傳入連結表之中,兩者相鄰。使用hashtable是是将鍵值對存于dictEntry之中。

ok,今天簡單介紹了Redis中五種底層的資料結構,在Redis中每個對象幾乎底層都是使用這些資料結構之一,是以了解并掌握這些底層知識還是很有必要的。希望能幫助到你。

如果有想學Redis的夥伴們的強烈建議看《Redis的設計與實作》一書,該書語言精煉,清晰明了,是入門Redis的一大利器。當然,書中一些案例需要一定的c語言知識。我的方法是先大體看一遍網課,了解Redis是什麼? 怎麼用? 然後再來看實體書。了解底層實作。這裡我推薦網課看尚矽谷的Redis課程,還不錯。我相信讀寫結合,一定會事半功倍。一起加油吧!