redis It's using C language-written , however C Language has no data structure of dictionary , therefore C The language itself uses structs to customize a dictionary structure
typedef struct redisDb
src\server.h Medium redis database data structure
/* 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 Deposited redis The underlying data structure of the database ：
- dict
Dictionary type
- expires
Expiration time
- blocking_keys
The key that the client waits for data (BLPOP)
- ready_keys
received PUSH The key of is blocked
- watched_keys
monitor MULTI/EXEC CAS Key , For example, the transaction will use
- id
Database id, 0 – 15
- avg_ttl
Statistically average ttl
- expires_cursor
Record expiration period
- defrag_later
Deposit key A list of
typedef struct dict
src\dict.h The data structure of the dictionary
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 Data structure for storing Dictionaries
- type
Types of dictionaries
- privdata
Private data
- ht
hash surface , An old watch , A new watch , Yes, it is hash When the meter is expanded , The new table will be used until , That is to say 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 Multiple function pointers are defined , It is convenient for subsequent method implementation and invocation
for example keyCompare A function pointer , He is a pointer , It points to a function , This function has 3 Parameters , and 1 Return values ：
3 Parameters
- privdata
Specific data
- key1
key1 The specific value of this key
- key2
key2 The specific value of this key
This pointer keyCompare The point function compares two key Size
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 Deposit is hash The data structure used by the table
- table
Actually key-value Key value pair
- size
hashtable The capacity of
- sizemask
be equal to size -1
- used
hashtable Number of elements
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 The actual data structure for key value pairs
- key
key value , It's actually a sds Type of
- v
value value , It's a consortium
- next
dictEntry The pointer , Point to the next data , Mainly to solve hash Conflicting
For example, in the last article we introduced hash, As shown in the figure below ,key Namely 1,v Namely (k3,v3) ,next It points to (k2,v2), The general default is next Point to NULL
The above consortium v , Inside No 1 The element is , void *val;
In fact, this element points to the real value , This element is a pointer , The actual data structure looks like this
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
type , Occupy 4 individual bit , Is used to constrain the client api Of , for example string type ,embstr,hash,zset wait
- encoding
The encoding type , Occupy 4 individual bit , The numbers used are 0 - 10, They represent different data types
- lru
lru Occupy 24 individual bit ,3 Bytes , Memory elimination algorithm
- refcount
Reference count , int type , Occupy 4 Bytes
- ptr
Actual data pointer , 64 Bit operating system , ptr Occupy 8 Bytes
bitmap A little case of
Set up a bitmap Of key, The function is to mark 11 Online users of
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]
adopt BITCOUNT It can be seen that 11 Number of people online 3 personal ,login:9:11 Occupy byte digits 4 byte
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
adopt BITCOUNT It can be seen that 12 Number of people online 2 personal ,login:9:12 Occupy byte digits 4 byte
Next we will take login:9:11 and login:9:12 Of And operation , To calculate 11 Number and 12 The number of people who have been online for the past two days
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 ...]
According to the above results, we can see ,11 Number and 12 The number of people who have been online for the past two days is 2 people , verification ok
Let's see 11 Number and 12 The number of people who are online on any day
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
According to the above results, we can see ,11 Number and 12 The number of people who are online on any day is 3 people , verification 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"
Let's take a look at the above key , stay redis What data types are actually in it ,
- OBJECT encoding [arguments [arguments ...]]
It can be seen that the above are “raw” type , That is to say redis Of sds type
Cache line
Let's take another small example ,redis Set a string in key
127.0.0.1:6379> set name xiaoming
OK
127.0.0.1:6379> OBJECT encoding name
"embstr"
We can see that name The type is “embstr”, that “embstr” How is the bottom layer implemented ？“embstr” How many bytes of data can it carry ？
We have mentioned above redis The place where the key value pairs are stored is dictEntry In the structure ,dictEntry In structure val The pointer points to a redisObject Structure , That's true
We're in a 64 In a bit machine ,CPU Reading data in memory is realized by reading cache rows
A cache line has 64 byte
One redisObject Structure proportion 16 byte
Then there is... Left 48 byte have access to , So use redis Inside Which one sds Data structure to store data ？
Use hisdshdr8 type ,hisdshdr8 type sds Before 3 Elements occupy 3 Bytes , So the rest buf Data can be stored 45 Bytes （64 - 16 - 3） The data of the
If you think so , Then it's a little careless , because redis For compatibility C The standard of language , Will add... To the end of the string 1 individual ‘\0’ , It takes one byte, so eventually “embstr” The actual number of bytes that can be stored is ：
44 byte
Let's review the last article , It can be seen that
When data takes up space in 0 - - 2^5-1 , Use hisdshdr5 data type
2^5 – 2^8-1 When you take up space , Use hisdshdr8 data type
Little practice
We are redis Set a test The value of is a 44 byte The content of , Look at this. key The type of , yes 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
Then set up test2 by Greater than 44 byte The content of , Check out his content again raw
127.0.0.1:6379> set test2 999999999911111111112222222222333333333344449
OK
127.0.0.1:6379> OBJECT encoding test2
"raw"
Finally, a diagram of the above data structure is provided
Reference material ：
reids Source code reids-6.2.5Redis 6.2.5 is the latest stable version.
huan - Welcome to praise , Focus on , Collection
friends , Your support and encouragement , I insist on sharing , The drive to improve quality
Okay , That's it this time
Technology is open , Our mindset , It should be more open . Embrace change , Born in the sun , Try to move on .
I am a Little Devil boy Nezha , Welcome to like, pay attention to collection , See you next time ~
