当前位置：网站首页>Redis 6.0 source code learning simple dynamic string

Redis 6.0 source code learning simple dynamic string

2022-07-24 02:03:00 【51CTO】

List of articles

Simple Dynamic String

data structure

C Strings in languages

Expand information

Once used data structure
data structure
About comments sdshdr5 Unused in doubt

Create string

Simple Dynamic String

Source code

data structure

Simple Dynamic String, abbreviation SDS, yes Redis The basic data structure used to store string and shaping data in .Redis Can only be used in C String as literal ; in the majority of cases ,Redis Use SDS As a string . Compared with C character string ,SDS Has the following advantages ：

Constant complexity gets string length .
Prevent buffer overflow .
Reduce the number of memory reallocations required to modify string length .
Binary security .
Compatible with the part C String function .

C Strings in languages

C The string in the language is Null-terminated String, It USES ’\0’ To represent the end of the string . And besides the end of the string , The string cannot contain empty characters , Otherwise, the first empty character read will be mistaken for the end sign .

This inconsistency between storing binary and reading is called Binary Unsafe. For binary security ,redis Medium SDS use len Property to record the length of the represented string .

Expand information

Binary security (binary safe) What does that mean? ？ - You know

Once used data structure

Redis 3.2 The previous data structure is relatively simple , Learning the historical version is more conducive to the understanding of the new data structure .

       
       struct 
       
       sdshdr {
       
       // buf  Length of occupied space in 
       
       int 
       
       len;
       
       // buf  Length of free space remaining in 
       
       int 
       
       free;
       
       //  Data space 
       
       char 
       
       buf[];
       
};
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.

len Recorded buf Number of bytes already used in , namely SDS The length of the string represented ;free Recorded buf Number of bytes not used in .buf It's an array of bytes , The array length is len+free+1, Because it needs to save one more ’\0’ As an end sign .

Through the understanding of data structure , You can calculate SDS Required memory size . With 64 For example, bit system , A byte string corresponds to SDS Need at least 10 Bytes .

SDS The pointer exposed to the upper layer does not point to SDS Pointer to structure , It's directed at buf The pointer to . because buf Will be redundant at the end of the string ’\0’ As an end sign , therefore SDS Compatible with C Language standard string handler .

data structure

Redis 3.2 After that SDS The structure becomes 5 Kind of :sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64.sdshdr yes Simple Dynamic String Header Abbreviation , The new structure consists of an indefinite header and an array of characters .

       
       struct 
       
       __attribute__ ((
       
       __packed__)) 
       
       sdshdr5 {
       
       unsigned 
       
       char 
       
       flags; 
       
       /* 3 lsb of type, and 5 msb of string length */
       
       char 
       
       buf[];
       
};
      
1.
2.
3.
4.

When the string length is less than 32 when , Will use sdshdr5 structure .sdshdr5 The structure only uses flags Indicates the structure type and length , low 3 Bits indicate the structure type , high 5 Bits indicate storage length .

       
       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[];
       
};
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.

sdshdr8、sdshdr16、sdshdr32 and sdshdr64 The structure is the same , take len and free Separate storage .

About comments sdshdr5 Unused in doubt

       
       /* Note: sdshdr5 is never used, we just access the flags byte directly.
       
 * However is here to document the layout of type 5 SDS strings. */
       
struct __attribute__ ((__packed__)) sdshdr5 {
       
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
       
    char buf[];
       
};
      
1.
2.
3.
4.
5.
6.

sdshdr5 There is a comment in “sdshdr5 is never used.”, When reading the source code of creating strings , Find out sdshdr5 It is actually used . Submit directly here “LNMPRG Source code research ” Conclusion .

Finally, we can confirm , The length is less than 32 The key/value pair , The bottom layer of the key is sdshdr5, And worthy robj The bottom is sdshdr8.
Q1: Why sdshdr5 save key Sure , save value no way ？
My guess is that the key will not update but the value will update , Therefore, the key is stored in as small a structure as possible ; Value update will cause capacity expansion , Simply store in a larger structure .
Q2: Why when parsing parameters ,Redis And abandoned the small sdshdr5？
My guess is for the convenience of coding . The number of parameters of different commands is different , At first, I couldn't tell which position was key Which position is value, Simply deal with it in a unified way , In specific scenarios , Then optimize it separately .

Create string

Redis adopt sdsnewlen Function creation SDS. In the function, the appropriate type will be selected according to the length of the string , After initializing the corresponding statistics , Returns a pointer to the contents of the specified string .

       
       sds 
       
       sdsnewlen(
       
       const 
       
       void 
       
       *
       
       init, 
       
       size_t 
       
       initlen) {
       
       void 
       
       *
       
       sh;
       
       sds 
       
       s;
       
       char 
       
       type 
       
       = 
       
       sdsReqType(
       
       initlen);
       
       //1.  Choose different types according to the string 
       
       /*  Usually, an empty string is created for appending , So use SDS8 type .*/
       
       if (
       
       type 
       
       == 
       
       SDS_TYPE_5 
       
       && 
       
       initlen 
       
       == 
       
       0) 
       
       type 
       
       = 
       
       SDS_TYPE_8;
       
       int 
       
       hdrlen 
       
       = 
       
       sdsHdrSize(
       
       type);
       
       //2.  Calculate the length required for different heads 
       
       unsigned 
       
       char 
       
       *
       
       fp; 
       
       /*  Point to flags The pointer to  */
       
       assert(
       
       initlen 
       
       + 
       
       hdrlen 
       
       + 
       
       1 
       
       > 
       
       initlen); 
       
       /* Catch size_t overflow */
       
       sh 
       
       = 
       
       s_malloc(
       
       hdrlen
       
       +
       
       initlen
       
       +
       
       1);
       
       if (
       
       sh 
       
       == 
       
       NULL) 
       
       return 
       
       NULL;
       
       if (
       
       init
       
       ==
       
       SDS_NOINIT)
       
       init 
       
       = 
       
       NULL;
       
       else 
       
       if (
       
       !
       
       init)
       
       memset(
       
       sh, 
       
       0, 
       
       hdrlen
       
       +
       
       initlen
       
       +
       
       1);
       
       s 
       
       = (
       
       char
       
       *)
       
       sh
       
       +
       
       hdrlen;
       
       fp 
       
       = ((
       
       unsigned 
       
       char
       
       *)
       
       s)
       
       -
       
       1;
       
       switch(
       
       type) {
       
       case 
       
       SDS_TYPE_5: {
       
       *
       
       fp 
       
       = 
       
       type 
       
       | (
       
       initlen 
       
       << 
       
       SDS_TYPE_BITS);
       
       break;
       
        }
       
       case 
       
       SDS_TYPE_8: {
       
       SDS_HDR_VAR(
       
       8,
       
       s);
       
       sh
       
       ->
       
       len 
       
       = 
       
       initlen;
       
       sh
       
       ->
       
       alloc 
       
       = 
       
       initlen;
       
       *
       
       fp 
       
       = 
       
       type;
       
       break;
       
        }
       
       case 
       
       SDS_TYPE_16: {
       
       SDS_HDR_VAR(
       
       16,
       
       s);
       
       sh
       
       ->
       
       len 
       
       = 
       
       initlen;
       
       sh
       
       ->
       
       alloc 
       
       = 
       
       initlen;
       
       *
       
       fp 
       
       = 
       
       type;
       
       break;
       
        }
       
       case 
       
       SDS_TYPE_32: {
       
       SDS_HDR_VAR(
       
       32,
       
       s);
       
       sh
       
       ->
       
       len 
       
       = 
       
       initlen;
       
       sh
       
       ->
       
       alloc 
       
       = 
       
       initlen;
       
       *
       
       fp 
       
       = 
       
       type;
       
       break;
       
        }
       
       case 
       
       SDS_TYPE_64: {
       
       SDS_HDR_VAR(
       
       64,
       
       s);
       
       sh
       
       ->
       
       len 
       
       = 
       
       initlen;
       
       sh
       
       ->
       
       alloc 
       
       = 
       
       initlen;
       
       *
       
       fp 
       
       = 
       
       type;
       
       break;
       
        }
       
    }
       
       if (
       
       initlen 
       
       && 
       
       init)
       
       memcpy(
       
       s, 
       
       init, 
       
       initlen);
       
       s[
       
       initlen] 
       
       = 
       
       '\0'; 
       
       //buf Finally add \0
       
       return 
       
       s;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.

Source details ：1 It's about

sdsReqType The function of the method is to return the corresponding... Based on the length of the string sds type .

       
       static 
       
       inline 
       
       char 
       
       sdsReqType(
       
       size_t 
       
       string_size) {
       
       if (
       
       string_size 
       
       < 
       
       1
       
       <<
       
       5)
       
       return 
       
       SDS_TYPE_5;
       
       if (
       
       string_size 
       
       < 
       
       1
       
       <<
       
       8)
       
       return 
       
       SDS_TYPE_8;
       
       if (
       
       string_size 
       
       < 
       
       1
       
       <<
       
       16)
       
       return 
       
       SDS_TYPE_16;
       
       #if (LONG_MAX == LLONG_MAX)
       
       if (
       
       string_size 
       
       < 
       
       1ll
       
       <<
       
       32)
       
       return 
       
       SDS_TYPE_32;
       
       return 
       
       SDS_TYPE_64;
       
       #else
       
       return 
       
       SDS_TYPE_32;
       
       #endif
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.