【Redis 系列】redis 學習十六,redis 字典(map) 及其核心編碼結構
- 2022 年 6 月 26 日
- 筆記
redis
是使用 C 語言編寫的,但是 C
語言是沒有字典這個數據結構的,因此 C
語言自己使用結構體來自定義一個字典結構
typedef struct redisDb
src\server.h 中的 redis 資料庫 數據結構
/* Redis database representation. There are multiple databases identified
* by integers from 0 (the default database) up to the max configured
* database. The database number is the 'id' field in the structure. */
typedef struct redisDb {
dict *dict; /* The keyspace for this DB */
dict *expires; /* Timeout of keys with a timeout set */
dict *blocking_keys; /* Keys with clients waiting for data (BLPOP)*/
dict *ready_keys; /* Blocked keys that received a PUSH */
dict *watched_keys; /* WATCHED keys for MULTI/EXEC CAS */
int id; /* Database ID */
long long avg_ttl; /* Average TTL, just for stats */
unsigned long expires_cursor; /* Cursor of the active expire cycle. */
list *defrag_later; /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;
redisDb 存放了 redis 資料庫底層的數據結構:
- dict
字典類型
- expires
過期時間
- blocking_keys
客戶端等待數據的鍵 (BLPOP)
- ready_keys
收到PUSH的鍵被阻塞
- watched_keys
監控 MULTI/EXEC CAS 的鍵,例如事務的時候就會使用到
- id
資料庫的 id, 0 – 15
- avg_ttl
統計平均的 ttl
- expires_cursor
記錄過期周期
- defrag_later
存放 key 的列表
typedef struct dict
src\dict.h 字典的數據結構
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;
dict
存放字典的數據結構
- type
字典的類型
- privdata
私有數據
- ht
hash 表, 一個舊錶,一個新表,是有當 hash 表擴容的時候,新表才會被使用到,也就是 ht[1]
typedef struct dictType
typedef struct dictType {
uint64_t (*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);
int (*expandAllowed)(size_t moreMem, double usedRatio);
} dictType;
dictType
定義了多個函數指針,便於後續進行方法的實現和調用
例如 keyCompare
函數指針,他是一個指針,指向的是一個函數,這個函數有 3 個參數,和 1 個返回值:
3 個參數
- privdata
具體的數據
- key1
key1 這個鍵具體的值
- key2
key2 這個鍵具體的值
這個指針 keyCompare 指向的函數作用是比較兩個 key 的大小
typedef struct dictht
/* This is our hash table structure. Every dictionary has two of this as we
* implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
dictht
存放的是 hash
表使用到的數據結構
- table
實際的 key-value 鍵值對
- size
hashtable 的容量
- sizemask
等於 size -1
- used
hashtable 元素的個數
typedef struct dictEntry
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;
dictEntry
為鍵值對的實際數據結構
- key
key 值,實際上是一個 sds
類型的
- v
value 值,是一個聯合體
- next
dictEntry
指針,指向下一個數據,主要是解決 hash 衝突的
例如上一篇我們介紹到的 hash
,如下圖中,key 就是 1,v 就是 (k3,v3) ,next 指向的就是 (k2,v2),一般默認情況 next 指向 NULL
上述聯合體 v ,裡面第 1 個元素是, void *val;
實際上這個元素才是指向真正的值,這個元素是一個指針,實際的數據結構是這個樣子的
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
* LFU data (least significant 8 bits frequency
* and most significant 16 bits access time). */
int refcount;
void *ptr;
} robj;
- type
類型,占 4 個 bit ,是用來約束客戶端 api 的,例如 string 類型,embstr,hash,zset 等等
- encoding
編碼類型,占 4 個bit ,使用到的數字有 0 – 10,分別表示不同的數據類型
- lru
lru 占 24 個bit ,3 個位元組 , 記憶體淘汰演算法
- refcount
引用計數 , int 類型,占 4 個位元組
- ptr
實際的數據指針 , 64 位作業系統中, ptr 占 8個位元組
bitmap 的小案例
設置一個 bitmap 的 key,作用為標記 11 號的在線用戶
127.0.0.1:6379> SETBIT login:9:11 25 1
(integer) 0
127.0.0.1:6379> SETBIT login:9:11 26 1
(integer) 0
127.0.0.1:6379> SETBIT login:9:11 27 1
(integer) 0
127.0.0.1:6379> BITCOUNT login:9:11
(integer) 3
127.0.0.1:6379> strlen login:9:11
(integer) 4
- BITCOUNT key [start end]
通過 BITCOUNT 可以看出 11 號在線人數 3 個人,login:9:11 佔用位元組數位 4 位元組
127.0.0.1:6379> SETBIT login:9:12 26 1
(integer) 0
127.0.0.1:6379> SETBIT login:9:12 25 0
(integer) 0
127.0.0.1:6379> SETBIT login:9:12 27 1
(integer) 0
127.0.0.1:6379> STRLEN login:9:12
(integer) 4
通過 BITCOUNT 可以看出 12 號在線人數 2 個人,login:9:12 佔用位元組數位 4 位元組
下面我們將取 login:9:11 和 login:9:12 的 與操作,來計算 11 號 和 12 號兩天來都在線的人數
127.0.0.1:6379> BITOP and login:and login:9:11 login:9:12
(integer) 4
127.0.0.1:6379> BITCOUNT login:and
(integer) 2
- BITOP operation destkey key [key …]
根據上述結果我們可以看出,11 號 和 12 號兩天來都在線的人數為 2 人,驗證 ok
我們再來看看11 號 和 12 號任意一天在線的人數
127.0.0.1:6379> BITOP or login:or login:9:11 login:9:12
(integer) 4
127.0.0.1:6379> BITCOUNT login:or
(integer) 3
根據上述結果我們可以看出,11 號 和 12 號任意一天在線的人數為 3 人,驗證 ok
127.0.0.1:6379> type login:or
string
127.0.0.1:6379> OBJECT encoding login:or
"raw"
127.0.0.1:6379> OBJECT encoding login:9:12
"raw"
127.0.0.1:6379> OBJECT encoding login:and
"raw"
咱們來看看上述用到的 key ,在 redis 裡面實際是什麼數據類型吧,
- OBJECT encoding [arguments [arguments …]]
可以看出上述都是 「raw」 類型, 也就是 redis 的 sds 類型
快取行
咱們再來看一個小例子,redis 中設置一個字元串 key
127.0.0.1:6379> set name xiaoming
OK
127.0.0.1:6379> OBJECT encoding name
"embstr"
我們可以看出 name 的類型是 「embstr」,那麼 「embstr」 底層是如何實現的呢?「embstr」 有能承載多少個位元組的數據呢?
上述我們有說到 redis 裡面存放鍵值對的地方在 dictEntry 結構體中,dictEntry 結構體中的val 指針指向的是一個 redisObject 結構體,是這樣的
我們在一個 64 位的機器中,CPU 在記憶體中讀取數據的是通過讀取快取行的方式來實現的
一個快取行有 64 位元組
一個 redisObject 結構體占 16 位元組
那麼就還剩 48 位元組 可以使用,那麼使用 redis 裡面 哪一個 sds 數據結構來存放數據數據呢?
使用 hisdshdr8 類型,hisdshdr8 類型 sds 的前 3 個元素佔用 3 個位元組,那麼剩下的 buf 存放數據就可以存放 45個位元組(64 – 16 – 3)的數據了
如果你這麼認為了,那麼就有點粗心哦,因為 redis 為了兼容 C 語言的標準,會在字元串的後面加上 1 個 『\0』 ,他是佔一個位元組的因此最終「embstr」
實際能存放的位元組數是:
44 位元組
來回顧上一篇文章,可以看出
當數據佔用空間在 0 – – 2^5-1 , 使用 hisdshdr5 數據類型
2^5 – 2^8-1 的佔用空間的時候,使用 hisdshdr8 數據類型
小小的實踐
我們在 redis 中設置一個 test 的值為一個 44位元組 的內容,查看這個 key 的類型,是 embstr
127.0.0.1:6379> set test 99999999991111111111222222222233333333334444
OK
127.0.0.1:6379> OBJECT encoding test
"embstr"
127.0.0.1:6379> STRLEN test
(integer) 44
再來設置 test2 為 大於 44 位元組的內容,再查看他的內容是 raw
127.0.0.1:6379> set test2 999999999911111111112222222222333333333344449
OK
127.0.0.1:6379> OBJECT encoding test2
"raw"
最後送上一張上述數據結構的關係圖
參考資料:
-
reids 源碼 reids-6.2.5 Redis 6.2.5 is the latest stable version.
歡-迎點贊,關注,收藏
朋友們,你的支援和鼓勵,是我堅持分享,提高品質的動力
好了,本次就到這裡
技術是開放的,我們的心態,更應是開放的。擁抱變化,向陽而生,努力向前行。
我是小魔童哪吒,歡迎點贊關注收藏,下次見~