[redis series] redis learning 16. Redis Dictionary (map) and its core coding structure

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 ：

• redis_doc

• 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 ~