Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

Redis Dictionary (MAP) and its core coding structure

Redis is written in C language, but C language does not have the dictionary data structure, so C language uses the structure to define a dictionary structure

typedef struct redisDb

Redis database data structure in SRC \server.h

/* 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;
Copy the code

RedisDb stores the underlying data structure of the Redis database:

dict

A dictionary type

expires

Expiration time

blocking_keys

The client waits for the data key (BLPOP)

ready_keys

The key that receives the PUSH is blocked

watched_keys

Keys for monitoring MULTI/EXEC CAS, for example, are used for transactions

The database ID is 0-15

avg_ttl

Statistics the average TTL

expires_cursor

Record expiration period

defrag_later

A list of keys

typedef struct dict

SRC \dict.h dictionary data structure

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;
Copy the code

Dict holds the dictionary’s data structure

type

Types of dictionaries

privdata

Private data

Hash table, an old table, a new table, is used when the hash table is expanded, i.e. 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;
Copy the code

DictType defines multiple function Pointers to facilitate the subsequent implementation and invocation of the method

For example, the keyCompare function pointer is a pointer to a function that takes three arguments and returns one value:

Three parameters

privdata

Specific data

key1

The value of the key key1

key2

The value of the key key2

This pointer keyCompare points to a function that compares the size of two keys

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;
Copy the code

Dictht stores the data structure used by the hash table

table

The actual key-value key value pair

size

The capacity of the hashtable

sizemask

Is equal to the size of 1

used

Number of hashtable 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;
Copy the code

DictEntry is the actual data structure of the key-value pair

The key value is actually an SDS type

Value is a union

DictEntry pointer to the next data, mainly for resolving hash collisions

For example, in hash, key is 1,v is (k3,v3), next points to (k2,v2), and next points to NULL by default

V, the first element is void *val;

In fact, this element is pointing to the actual value, this element is a pointer, and 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;
Copy the code

type

The type, which has four bits, is used to constrain the client API, such as string, embstr, hash, zset, etc

encoding

Encoding type, accounting for 4 bits, the numbers used are 0-10, respectively representing different data types

Lru accounts for 24 bits, 3 bytes, memory elimination algorithm

refcount

Reference count, int, 4 bytes

The actual data pointer. On 64-bit operating systems, PTR takes up 8 bytes

A small example of bitmaps

Set a bitmap key to mark the online user at number 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
Copy the code

BITCOUNT key [start end]

It can be seen from the BITCOUNT that there are 3 people online on number 11, and login:9:11 occupies 4 bytes

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
Copy the code

From the BITCOUNT, it can be seen that the number of people online on number 12 is 2, and login:9:12 occupies 4 bytes

Now we’ll take the and operations login:9:11 and login:9:12 to count the number of people who were online on both 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
Copy the code

BITOP operation destkey key [key …]

According to the above results, we can see that the number of online users on 11th and 12th is 2, and the verification is OK

Let’s look at the number of people online on any given day on the 11th and 12th

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
Copy the code

According to the above results, we can see that the number of online people on any day of 11th and 12th is 3, and the verification is 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"Copy the code

Let’s take a look at the key used above, and what the actual data type is in Redis.

OBJECT encoding [arguments [arguments …]]

It can be seen that the above are “RAW” types, that is, redis SDS type

Cache line

Let’s look at a small example of setting a string key in redis

127.0.0.1:6379> set name xiaoming
OK
127.0.0.1:6379> OBJECT encoding name
"embstr"
Copy the code

We can see that the name type is “embstr”. How many bytes of data can “embstr” hold?

So we talked about where redis holds key-value pairs and in the dictEntry structure, the val pointer in the dictEntry structure points to a redisObject structure, and that’s what it looks like

In a 64-bit machine, the CPU reads data in memory by reading rows from the cache

A cache line has 64 bytes

A redisObject structure is 16 bytes

So there are 48 bytes left to use, so which SDS data structure in Redis is used to store data?

Using HISdSHDR8, the first 3 elements of hisdSHdr8 SDS occupy 3 bytes, so the remaining BUF storage data can hold 45 bytes (64-16-3) of data

If you think so, you are a bit careless, because Redis, in order to comply with the C standard, adds a ‘\0’ to the end of the string, which takes up one byte, so the actual number of bytes “embstr” can hold is:

44 byte

Let’s go back to the last article

Hisdshdr5 data type is used when data takes up space between 0 – -2 ^5-1

The hisdSHDR8 data type is used when 2^5-2^8-1 occupies space

Little practice

We set the value of test to 44 bytes in Redis. Check the type of the key, which is 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) 44Copy the code

Set test2 to content greater than 44 bytes and check that its content is RAW

127.0.0.1:6379 > set test2 999999999911111111112222222222333333333344449 OK 127.0.0.1:6379 > OBJECT encoding test2 "raw"Copy the code

Finally, a diagram of the above data structure is presented

References:

redis_doc
Reids source reids-6.2.5 Redis 6.2.5 is the latest stable version.

Huan – Welcome likes, attention, favorites

Friends, your support and encouragement, I insist on sharing, improve the quality of the power

All right, that’s it for this time

Technology is open, our mentality, should be more open. Embrace change, live in the sun, and strive to move forward.

I am Nezha, welcome to like, see you next time ~

Redis Dictionary (MAP) and its core coding structure

Redis Dictionary (MAP) and its core coding structure

typedef struct redisDb

typedef struct dict

typedef struct dictType

typedef struct dictht

typedef struct dictEntry

A small example of bitmaps

Cache line

Little practice

Huan – Welcome likes, attention, favorites

Related Posts

Leetcode 1 of the Day series – Effective Sudoku – “Three Levels of Cyclic Violence”

PHP proxy mode details

STM32F103 single chip microcomputer outputs phase-adjustable PWM wave