欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Redis的數(shù)據(jù)存儲及String類型的實現(xiàn)

 更新時間:2022年10月25日 14:22:50   作者:京東云開發(fā)者  
這篇文章主要介紹了Redis的數(shù)據(jù)存儲及String類型的實現(xiàn),redis作為k-v數(shù)據(jù)存儲,因查找和操作的時間復(fù)雜度都是O(1)和豐富的數(shù)據(jù)類型及數(shù)據(jù)結(jié)構(gòu)的優(yōu)化,了解了這些數(shù)據(jù)類型和結(jié)構(gòu)更有利于我們平時對于redis的使用,需要的朋友可以參考下

Redis作為基于內(nèi)存的非關(guān)系型的K-V數(shù)據(jù)庫。因讀寫響應(yīng)快速、原子操作、提供了多種數(shù)據(jù)類型String、List、Hash、Set、Sorted Set、在項目中有著廣泛的使用,今天我們來探討下下Redis的數(shù)據(jù)結(jié)構(gòu)是如何實現(xiàn)的。

1 引言

Redis作為基于內(nèi)存的非關(guān)系型的K-V數(shù)據(jù)庫。因讀寫響應(yīng)快速、原子操作、提供了多種數(shù)據(jù)類型String、List、Hash、Set、Sorted Set、在項目中有著廣泛的使用,今天我們來探討下下Redis的數(shù)據(jù)結(jié)構(gòu)是如何實現(xiàn)的。

2 數(shù)據(jù)存儲

2.1 RedisDB

Redis將數(shù)據(jù)存儲在redisDb中,默認(rèn)0~15共16個db。每個庫都是獨立的空間,不必擔(dān)心key沖突問題,可通過select命令切換db。集群模式使用db0

typedef struct redisDb {
dict *dict; /* The keyspace for this DB */
dict *expires; /* Timeout of keys with a timeout set */
...
} redisDb;
  • dict:數(shù)據(jù)庫鍵空間,保存著數(shù)據(jù)庫中的所有鍵值對
  • expires:鍵的過期時間,字典的鍵為鍵,字典的值為過期事件UNIX時間戳

2.2 Redis哈希表實現(xiàn)

2.2.1 哈希字典dict

K-V存儲我們最先想到的就是map,在Redis中通過dict實現(xiàn),數(shù)據(jù)結(jié)構(gòu)如下:

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;
  • type:類型特定函數(shù)是一個指向dictType結(jié)構(gòu)的指針,每個dictType結(jié)構(gòu)保存了一簇用于操作特定類型鍵值對的函數(shù),Redis會為用途不同的字典設(shè)置不同的類型特定函數(shù)。
  • privdata:私有數(shù)據(jù)保存了需要傳給那些類型特定函數(shù)的可選參數(shù)
  • ht[2]:哈希表一個包含兩個項的數(shù)組,數(shù)組中的每個項都是一個dictht哈希表,一般情況下,字典只使用ht[0] 哈希表,ht[1]哈希表只會在對ht[0]哈希表進行rehash時使用
  • rehashidx:rehash 索引,當(dāng)rehash不在進行時,值為 -1

hash數(shù)據(jù)存在兩個特點:

  • 任意相同的輸入一定能得到相同的數(shù)據(jù)
  • 不同的輸入,有可能得到相同的輸出

針對hash數(shù)據(jù)的特點,存在hash碰撞的問題,dict通過dictType中的函數(shù)能夠解決這個問題

typedef struct dictType {
uint64_t (*hashFunction)(const void *key);
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
...
} dictType;
  • hashFunction:用于計算key的hash值的方法
  • keyCompare:key的值比較方法

2.2.2 哈希表 dictht

dict.h/dictht表示一個哈希表,具體結(jié)構(gòu)如下:

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;
  • table:數(shù)組指針,數(shù)組中的每個元素都是一個指向dict.h/dictEntry結(jié)構(gòu)的指針,每個dictEntry結(jié)構(gòu)保存著一個鍵值對。
  • size:記錄了哈希表的大小,也就是table數(shù)組的大小,大小總是2^n
  • sizemask:總是等于size - 1,這個屬性和哈希值一起決定一個鍵應(yīng)該被放到table數(shù)組的哪個索引上面。
  • used:記錄了哈希表目前已有節(jié)點(鍵值對)的數(shù)量。

鍵值對dict.h/dictEntry

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;
  • key:保存著鍵值對中的鍵(SDS類型對象)
  • val:保存著鍵值對中的值,可以是一個uint64_t整數(shù),或者是一個int64_t整數(shù),又或者是一個指針指向一個被redisObject包裝的值
  • next:指向下個哈希表節(jié)點,形成鏈表指向另一個哈希表節(jié)點的指針,這個指針可以將多個哈希值相同的鍵值對連接在一次,以此來解決鍵沖突(collision)的問題

使用hash表就一定會存在hash碰撞的問題,hash碰撞后在當(dāng)前數(shù)組節(jié)點形成一個鏈表,在數(shù)據(jù)量超過hash表長度的情況下,就會存在大量節(jié)點稱為鏈表,極端情況下時間復(fù)雜度會從O(1)變?yōu)镺(n);如果hash表的數(shù)據(jù)再不斷減少,會造成空間浪費的情況。Redis會針對這兩種情況根據(jù)負載因子做擴展與收縮操作:

  • 負載因子:哈希表已保存節(jié)點數(shù)量/哈希表大小,load_factor = ht[0].used/ht[0].size
  • 擴展操作:
  • 服務(wù)器目前沒有在執(zhí)行BGSAVE命令或者BGREWRITEAOF命令,并且哈希表的負載因子大于等于 1;
  • 服務(wù)器目前正在執(zhí)行BGSAVE命令或者BGREWRITEAOF命令,并且哈希表的負載因子大于等于5;

收縮操作:

  • 當(dāng)哈希表的負載因子小于 0.1 時, 程序自動開始對哈希表執(zhí)行收縮操作。

Redis在擴容時如果全量擴容會因為數(shù)據(jù)量問題導(dǎo)致客戶端操作短時間內(nèi)無法處理,所以采用漸進式 rehash進行擴容,步驟如下:

  • 同時持有2個哈希表
  • 將rehashidx的值設(shè)置為0,表示rehash工作正式開始
  • 在rehash進行期間, 每次對字典執(zhí)行添加、刪除、查找或者更新操作時,程序除了執(zhí)行指定的操作以外,還會順帶將ht[0]哈希表在rehashidx索引上的所有鍵值對rehash到ht[1] ,當(dāng)rehash工作完成之后,程序?qū)ehashidx屬性的值增一
  • 某個時間點上,ht[0]的所有鍵值對都會被rehash至ht[1] ,這時程序?qū)ehashidx屬性的值設(shè)為-1, 表示rehash操作已完成

在漸進式 rehash 進行期間,字典的刪除(delete)、查找(find)、更新(update)等操作會在兩個哈希表上進行;在字典里面查找一個鍵的話, 程序會先在 ht[0] 里面進行查找,如果沒找到的話,就會繼續(xù)到ht[1]里面進行查找;新添加到字典的鍵值對一律會被保存到 ht[1] 里面,而ht[0]則不再進行任何添加操作:這一措施保證了ht[0]包含的鍵值對數(shù)量會只減不增(如果長時間不進行操作時,事件輪詢進行這種操作),并隨著rehash操作的執(zhí)行而最終變成空表。

dict.h/redisObject

Typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS;
int refcount;
void *ptr;
}
  • type:4:約束客戶端操作時存儲的數(shù)據(jù)類型,已存在的數(shù)據(jù)無法修改類型,4bit
  • encoding:4:值在redis底層的編碼模式,4bit
  • lru:LRU_BITS:內(nèi)存淘汰策略
  • refcount:通過引用計數(shù)法管理內(nèi)存,4byte
  • ptr:指向真實存儲值的地址,8byte

完整結(jié)構(gòu)圖如下:

3 String類型

3.1 String類型使用場景

String 字符串存在有三種類型:字符串,整數(shù),浮點。主要有以下使用場景

1)頁面動態(tài)緩存
比如生成一個動態(tài)頁面,首次可以將后臺數(shù)據(jù)生成頁面,并且存儲到redis字符串中。再次訪問,不再進行數(shù)據(jù)庫請求,直接從redis中讀取該頁面。特點是:首次訪問比較慢,后續(xù)訪問快速。

2)數(shù)據(jù)緩存
在前后分離式開發(fā)中,有些數(shù)據(jù)雖然存儲在數(shù)據(jù)庫,但是更改特別少。比如有個全國地區(qū)表。當(dāng)前端發(fā)起請求后,后臺如果每次都從關(guān)系型數(shù)據(jù)庫讀取,會影響網(wǎng)站整體性能。
我們可以在第一次訪問的時候,將所有地區(qū)信息存儲到redis字符串中,再次請求,直接從數(shù)據(jù)庫中讀取地區(qū)的json字符串,返回給前端。

3)數(shù)據(jù)統(tǒng)計
redis整型可以用來記錄網(wǎng)站訪問量,某個文件的下載量。(原子自增自減)

4)時間內(nèi)限制請求次數(shù)
比如已登錄用戶請求短信驗證碼,驗證碼在5分鐘內(nèi)有效的場景。當(dāng)用戶首次請求了短信接口,將用戶id存儲到redis 已經(jīng)發(fā)送短信的字符串中,并且設(shè)置過期時間為5分鐘。當(dāng)該用戶再次請求短信接口,發(fā)現(xiàn)已經(jīng)存在該用戶發(fā)送短信記錄,則不再發(fā)送短信。

5)分布式session
當(dāng)我們用nginx做負載均衡的時候,如果我們每個從服務(wù)器上都各自存儲自己的session,那么當(dāng)切換了服務(wù)器后,session信息會由于不共享而會丟失,我們不得不考慮第三應(yīng)用來存儲session。通過我們用關(guān)系型數(shù)據(jù)庫或者redis等非關(guān)系型數(shù)據(jù)庫。關(guān)系型數(shù)據(jù)庫存儲和讀取性能遠遠無法跟redis等非關(guān)系型數(shù)據(jù)庫。

3.2 String類型的實現(xiàn)——SDS結(jié)構(gòu)

Redis并沒有直接使用C字符串實現(xiàn)String類型,在Redis3.2版本之前通過SDS實現(xiàn)

Typedef struct sdshdr {
int len;
int free;
char buf[];
};
  • len:分配內(nèi)存空間
  • free:剩余可用分配空間
  • char[]:value值實際數(shù)據(jù)

3.3 SDS與C字符串之間的區(qū)別

3.3.1 查詢時間復(fù)雜度

C獲取字符串長度的復(fù)雜度為O(N)。而SDS通過len記錄長度,從C的O(n)變?yōu)镺(1)。

3.3.2 緩沖區(qū)溢出

C字符串不記錄自身長度容易造成緩沖區(qū)溢出(buffer overflow)。SDS的空間分配策略完全杜絕了發(fā)生緩沖區(qū)溢出的可能性,當(dāng)需要對SDS進行修改時,會先檢查SDS的空間是否滿足修改所需的要求,如果不滿足的話SDS的空間擴展至執(zhí)行修改所需的大小,然后才執(zhí)行實際的修改操作,所以使用SDS既不需要手動修改SDS的空間大小,也不會出現(xiàn)緩沖區(qū)溢出問題。

在SDS中,buf數(shù)組的長度不一定就是字符數(shù)量加一,數(shù)組里面可以包含未使用的字節(jié),而這些字節(jié)的數(shù)量就由SDS的free屬性記錄。通過未使用空間,SDS實現(xiàn)了空間預(yù)分配和惰性空間釋放兩種優(yōu)化策略:

  • 空間預(yù)分配:當(dāng)對一個SDS進行修改,并且需要對SDS進行空間擴展的時候,程序不僅會為SDS分配修改所必須要的空間,還會為SDS分配額外的未使用空間。擴展SDS 空間之前,會先檢查未使用空間是否足夠, 如果足夠的話,就會直接使用未使用空間,而無須執(zhí)行內(nèi)存重分配。如果不夠根據(jù)(len + addlen(新增字節(jié))) * 2的方式進行擴容,大于1M時,每次只會增加1M大小。通過這種預(yù)分配策略,SDS將連續(xù)增長N次字符串所需的內(nèi)存重分配次數(shù)從必定N次降低為最多N次。
  • 惰性空間釋放:惰性空間釋放用于優(yōu)化SDS的字符串縮短操作:當(dāng)需要縮短SDS保存的字符串時,程序并不立即使用內(nèi)存重分配來回收縮短后多出來的字節(jié),而是使用free屬性將這些字節(jié)的數(shù)量記錄起來,并等待將來使用。

3.3.3 二進制安全

C字符串中的字符必須符合某種編碼(比如 ASCII,并且除了字符串的末尾之外,字符串里面不能包含空字符, 否則最先被程序讀入的空字符將被誤認(rèn)為是字符串結(jié)尾。

SDS的API都是二進制安全的(binary-safe):都會以處理二進制的方式來處理SDS存放在buf數(shù)組里的數(shù)據(jù),程序不會對其中的數(shù)據(jù)做任何限制、過濾、或者假設(shè) —— 數(shù)據(jù)在寫入時是什么樣的,它被讀取時就是什么樣。redis不是用這個數(shù)組來保存字符,而是用它來保存一系列二進制數(shù)據(jù)。

3.4 SDS結(jié)構(gòu)優(yōu)化

String類型所存儲的數(shù)據(jù)可能會幾byte存在大量這種類型數(shù)據(jù),但len、free屬性的int類型會占用4byte共8byte存儲,3.2之后會根據(jù)字符串大小使用sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64數(shù)據(jù)結(jié)構(gòu)存儲,具體結(jié)構(gòu)如下:

struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* used */
uint8_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* used */
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; /* used */
uint32_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /* used */
uint64_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
  • unsign char flags:3bit表示類型,5bit表示未使用長度
  • len:表示已使用長度
  • alloc:表示分配空間大小,剩余空間大小可以使用alloc - len獲得

3.5 字符集編碼

redisObject包裝存儲的value值,通過字符集編碼對數(shù)據(jù)存儲進行優(yōu)化,string類型的編碼方式有如下三種:

  • embstr:

CPU每次按Cache Line 64byte讀取數(shù)據(jù),一個redisObject對象為16byte,為填充64byte大小,會向后再讀取48 byte數(shù)據(jù)。但獲取實際數(shù)據(jù)時還需要再通過*ptr指針讀取對應(yīng)內(nèi)存地址的數(shù)據(jù)。而一個sdshdr8屬性的信息占用4byte,其余44byte可以用來存儲數(shù)據(jù)。如果value值小于44,byte可以通過一次讀取緩存行獲取數(shù)據(jù)。

  • int:

如果SDS小于20位,并且能夠轉(zhuǎn)換成整型數(shù)字,redisObject的*ptr指針會直接進行存儲。

  • raw:

SDS

4 總結(jié)

redis作為k-v數(shù)據(jù)存儲,因查找和操作的時間復(fù)雜度都是O(1)和豐富的數(shù)據(jù)類型及數(shù)據(jù)結(jié)構(gòu)的優(yōu)化,了解了這些數(shù)據(jù)類型和結(jié)構(gòu)更有利于我們平時對于redis的使用。下一期將對其它常用數(shù)據(jù)類型List、Hash、Set、Sorted Set所使用的ZipList、QuickList、SkipList做進一步介紹,對于文章中不清晰不準(zhǔn)確的地方歡迎大家一起討論交流。

到此這篇關(guān)于Redis的數(shù)據(jù)存儲及String類型的實現(xiàn)的文章就介紹到這了,更多相關(guān)Redis數(shù)據(jù)存儲內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • 詳解centos7 yum安裝redis及常用命令

    詳解centos7 yum安裝redis及常用命令

    這篇文章主要介紹了centos7 yum安裝redis及常用命令,本文給大家介紹的非常詳細,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2020-09-09
  • Redis緩存穿透出現(xiàn)原因及解決方案

    Redis緩存穿透出現(xiàn)原因及解決方案

    這篇文章主要介紹了Redis緩存穿透出現(xiàn)原因及解決方案,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2020-08-08
  • 解析redis hash應(yīng)用場景和常用命令

    解析redis hash應(yīng)用場景和常用命令

    這篇文章主要介紹了redis hash應(yīng)用場景和常用命令,本文給大家介紹的非常詳細,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2021-08-08
  • 使用Ruby腳本部署Redis Cluster集群步驟講解

    使用Ruby腳本部署Redis Cluster集群步驟講解

    今天小編就為大家分享一篇關(guān)于使用Ruby腳本部署Redis Cluster集群步驟講解,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧
    2019-01-01
  • Linux系統(tǒng)下安裝Redis數(shù)據(jù)庫過程

    Linux系統(tǒng)下安裝Redis數(shù)據(jù)庫過程

    大家好,本篇文章主要講的是Linux系統(tǒng)下安裝Redis數(shù)據(jù)庫過程,感興趣的同學(xué)趕快來看一看吧,對你有幫助的話記得收藏一下,方便下次瀏覽
    2021-12-12
  • 淺談redis的過期時間設(shè)置和過期刪除機制

    淺談redis的過期時間設(shè)置和過期刪除機制

    本文主要介紹了redis的過期時間設(shè)置和過期刪除機制,文中通過示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-03-03
  • redis中hash表內(nèi)容刪除的方法代碼

    redis中hash表內(nèi)容刪除的方法代碼

    在本篇文章里小編給各位整理了關(guān)于redis中hash表內(nèi)容怎么刪除的方法以及技巧代碼,需要的朋友們分享下。
    2019-07-07
  • 使用Redis解決高并發(fā)方案及思路解讀

    使用Redis解決高并發(fā)方案及思路解讀

    這篇文章主要介紹了使用Redis解決高并發(fā)方案及思路,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2023-03-03
  • Redis在Ubuntu系統(tǒng)上無法啟動的問題排查

    Redis在Ubuntu系統(tǒng)上無法啟動的問題排查

    這篇文章主要介紹了Redis在Ubuntu系統(tǒng)上無法啟動的問題排查,文中通過代碼示例給大家介紹的非常詳細,對大家的學(xué)習(xí)或工作有一定的幫助,需要的朋友可以參考下
    2024-08-08
  • 分布式利器redis及redisson的延遲隊列實踐

    分布式利器redis及redisson的延遲隊列實踐

    這篇文章為大家主要介紹了分布式利器redis及redisson的延遲隊列實踐,搜遍全網(wǎng)好像還沒有使用redisson的延遲隊列的,redisson作為一個分布式利器,這么好用的工具沒人用有點可惜
    2022-03-03

最新評論