Redis: SDS source code analysis

1. Preface

Hello, Welcome to 《 Redis Data structure source code analysis series 》, stay 《Redis Why so soon? ？》 In an article, I said Redis One reason for the speed is its simple and efficient data structure .

This series of articles is aimed at all stages of Coder People , Novices don't have to be afraid . In each article, Ao Bing will start with the introduction of actual combat , Then go deep into the source code analysis , Finally, the interview questions review these three directions and introduce them to you one by one .

2.SDS Order actual combat [ Newly arrived ]

SDS yes Redis The simplest data structure in .Redis All data structures in are unique key String as name , according to key obtain value, The only difference is value Different data structures .

SDS Widely used in production environments , such as , We use SDS Do distributed locks ; Turn an object into JSON String as cache, etc . stay Redis Once the relevant data structure is mentioned during the interview SDS It must be a topic that can't be bypassed , It is very simple （ Or after reading this article, it's very simple ）, The interviewer may not ask , But we have to understand .

First of all, let's start with the actual battle of command ~（ The old driver jumped directly ）

See the official website for more commands ：redis.io/commands#st…

2. 1 Set string

Format ：set <key> <value>. among value The value of can be a byte string (byte string)、 Integers and floating point numbers .

> set name aobing
OK
 Copy code

2.2 Get string

Format ：get <key>.

> get name
"aobing"
 Copy code

2.3 Get string length

Format ：strlen <key>

> strlen name
(integer) 6
 Copy code

2.4 Get substring

Format ：getrange <key> start end. Gets the substring of the string , stay Redis2.0 Previously, this command was substr, Current use getrange. The return displacement is start( from 0 Start ) and end Between ( It all includes , Not like the Baotou without the tail in other languages ) The string of . You can use a negative offset to provide an offset from the end of the string .

therefore -1 Represents the last character ,-2 It means the next to last , And so on . This function handles out of range requests by limiting the result range to the actual length of the string (end The setting is very large, and it ends at the end of the string ).

127.0.0.1:6379> set mykey "This is a string"
OK
127.0.0.1:6379> getrange mykey 0 3
"This"
127.0.0.1:6379> getrange mykey -3 -1
"ing"
127.0.0.1:6379> getrange mykey 0 -1
"This is a string"
127.0.0.1:6379> getrange mykey 10 10000
"string"
 Copy code

2.5 Set substring

Format ：setrange <key> offset substr. Return value ： Length of modified string .

from value Start with the whole length of , Overwrite... From the specified offset key Part of the string stored at . If the offset is greater than key The current length of the string at , The string will be filled with zero bytes to fit the offset .

Keys that do not exist are treated as empty strings , Therefore, this command will ensure that it contains a string large enough to set the value to offset.

Be careful ： The maximum offset you can set is 2^29 - 1（536870911）, because Redis String is limited to 512 MB. If you need to exceed this size , You can use multiple keys .

127.0.0.1:6379> set key1 "hello world"
OK
127.0.0.1:6379> setrange key1 6 redis
(integer) 11
127.0.0.1:6379> get key1
"hello redis"
127.0.0.1:6379> setrange key2 6 redis
(integer) 11
127.0.0.1:6379> get key2
"\x00\x00\x00\x00\x00\x00redis"
 Copy code

2.6 Append substring

Format ：append <key> substr If key Already exists and is a string , Then this command will value Append... To the end of the string . If key non-existent , It is created and set to an empty string , therefore APPEND In this special case Will be similar to SET.

127.0.0.1:6379> exists key4
(integer) 0
127.0.0.1:6379> append key4 hello
(integer) 5
127.0.0.1:6379> append key4 world
(integer) 10
127.0.0.1:6379> get key4
"helloworld"
 Copy code

2.7 Count

In the use of Redis In, we often use strings as counters , Use incr Command plus one . Format ：incr <key>. Return value ：key Incremented value . The stored number key Add 1.

If key non-existent , Set it to... Before performing the operation 0.

If key Contains a value of the wrong type or contains a string that cannot be represented as an integer , Returns an error . This operation is limited to 64 Bit signed integer . The count is determined by the range , It cannot exceed Long.Max, Not lower than Long.Min.

2.8 Expiration and deletion

Strings can be used del Command to delete , You can also use expire Command set expiration time , Automatically delete when due . We can use ttl Command to get the lifetime of the string （ How much time is left to expire ）.

Format ：del <key1> <key2> ... Return value ： Delete key The number of

127.0.0.1:6379> SET key1 "Hello"
"OK"
127.0.0.1:6379> SET key2 "World"
"OK"
127.0.0.1:6379> DEL key1 key2 key3
(integer) 2 
 Copy code

Format ：expire <key> time Return value ： If timeout is set, return 1. If key There is no return 0.

How to set the expired string to permanent ？

Time to live can be achieved by using DEL Command to delete the whole key To remove , Or be SET and GETSET Command override (overwrite), It means , If a command just modifies a with a lifetime key Instead of using a new key Instead of (replace) Its words , Then the survival time will not be changed .

for instance , To a key perform INCR command , Do... On a list LPUSH command , Or for a hash table HSET command , None of these operations will change key Time to live .

If you use RENAME To a key Change the name , So after the change of name key Life time is the same as before .

RENAME Another possibility of command is , Try to put a key Change the name to another one with a lifetime another_key , This is the old one another_key ( And its lifetime ) Will be deleted , And then the old key It will be renamed another_key , therefore , new another_key Life time is the same as the original key equally .

Use PERSIST The command can be deleted without key Under the circumstances , remove key Survival time , Give Way key To be a 『 lasting 』(persistent) key .

127.0.0.1:6379> expire age 100
(integer) 1
127.0.0.1:6379> ttl age
(integer) 97
127.0.0.1:6379> set age 20
OK
127.0.0.1:6379> ttl age
(integer) -1
127.0.0.1:6379> expire age 100
(integer) 1
127.0.0.1:6379> ttl age
(integer) 98
127.0.0.1:6379> rename age age2
OK
127.0.0.1:6379> ttl age2
(integer) 87
127.0.0.1:6379> expire age 100
(integer) 1
127.0.0.1:6379> ttl age
(integer) 96
127.0.0.1:6379> persist age
(integer) 1
127.0.0.1:6379> ttl age
(integer) -1
 Copy code

3.SDS Introduction and features [ eight-part essay ( a literary composition prescribed for the imperial civil service examinations, knows for it rigidity of form and poverty of ideas ) ]

Redis There is a high probability that the relevant data structure will be mentioned in the interview ,SDS Most people recite the eight part essay , But I haven't read the source code , Know what it is and don't know why it is , This can never be used ！！

4.SDS Structural model [ old hand ]

What Ao Bing read this time Redis The source code is the latest Redis6.2.6 and Redis3.0.0 edition

I'm sure you're hearing Redis The string in is not simple C Strings in languages , yes SDS（Simple Dynamic String, Simple dynamic string ） What new type did you think you had created , Regarding this , What Ao Bing wants to say is not to panic , Actually SDS The bottom layer of the source code of the content is typedef char *sds;.

4.1 data structure

Redis6.x Of SDS Data structure definition and Redis3.0.0 There's a big difference , But the core idea remains the same . Start with the simple version （Redis3.x） Let's get started ~

struct sdshdr {
    // Record buf The number of bytes used in an array 
    // be equal to SDS The length of the saved string 
    unsigned int len;

    // Record buf The number of unused bytes in an array 
    unsigned int free;

    //char Array , To hold strings 
    char buf[];
};
 Copy code

As shown in the figure below, it is a string "Aobing" stay Redis Storage form in ：

len by 6, Express this SDS A file with a length of 5 String ;
free by 0, Express this SDS There is no room left ;
buf It's a char An array of types , Notice that an empty character is saved at the end '\0'.

buf Automatically append one to the tail '\0' Characters are not counted in SDS Of len in , This is to follow C The convention of ending a string with an empty string , bring SDS You can use part of string.h Functions in the library , Such as strlen

#include <stdio.h>
#include <string.h>

int main() {
    char buf[] = {'A','o','b','i','n','g','\0'};
    printf("%s\n",buf);             // Aobing
    printf("%lu\n",strlen(buf));    // 6
    return 0;
}
 Copy code

4.2 Demanding data optimization

4.2.1 Data structure optimization

At present, we seem to have got a well structured SDS , But can we continue to optimize ？

stay Redis3.x In the version Strings of different lengths occupy the same header , If a string is short but the header takes up more space , It's a waste of time . So we're going to SDS There are three levels of strings ：

Short string ( The length is less than 32),len and free For the length of the 1 Bytes ;
Long string , use 2 Byte or 4 byte ;
Super long string , use 8 byte .

There are five types of SDS（ The length is less than 1 byte 、1 byte 、2 byte 、4 byte 、8 byte ）

We can do it in SDS One more in type Field to identify the type , But there's no need to use one 4 Bytes of int Type to do ！ have access to 1 Bytes of char type , Bit operation （3 Bit can identify 2^3 Types ） To get the type .

The following is a short string ( The length is less than 32) The optimized form of ：

Low three bit storage type , high 5 Bit storage length , The maximum length that can be identified is 32, So the length of the short string must be less than 32.
There is no need to free Field ,32-len That is to say free

Ao Bing took you to analyze a wave , So let's see Redis6.x How did you do it ！

//  Be careful ：sdshdr5 Never used ,Redis Just visit flags.
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /*  low 3 Bit storage type ,  high 5 Bit storage length  */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /*  Already used  */
    uint8_t alloc; /*  Total length , use 1 Byte storage  */
    unsigned char flags; /*  low 3 Bit storage type ,  high 5 Bit reservation  */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /*  Already used  */
    uint16_t alloc; /*  Total length , use 2 Byte storage  */
    unsigned char flags; /*  low 3 Bit storage type ,  high 5 Bit reservation  */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /*  Already used  */
    uint32_t alloc; /*  Total length , use 4 Byte storage  */
    unsigned char flags; /*  low 3 Bit storage type ,  high 5 Bit reservation  */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /*  Already used  */
    uint64_t alloc; /*  Total length , use 8 Byte storage  */
    unsigned char flags; /*  low 3 Bit storage type ,  high 5 Bit reservation  */
    char buf[];
};
 Copy code

The data structure is similar to what we analyzed ！ It's just adding an identification field , And not int type , It is 1 Bytes of char type , Use one of the 3 Bits represent specific types .

meanwhile ,Redis It is also stated in 5 Constants represent five types of SDS , It also coincides with our analysis .

#define SDS_TYPE_5 0
#define SDS_TYPE_8 1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4
 Copy code

4.2.2 uintX_t

Compare the two versions of code , It's not hard to find that Redis6.x in int There are also several types ：uint8_t / uint16_t / uint32_t /uint64_t. At first glance, I thought it was a new type , After all C There are no such types in language ！

Ao Bing was also full of fog at first sight , After all C The language is almost forgotten . But with my strong knowledge reserve ( Don't face ^_^) Guess it could be an alias ,C In language typedef ah ！ and _t Is its abbreviation . Check out the source code , Sure enough ~~

typedef unsigned char uint8_t;
typedef unsigned short uint16_t;
typedef unsigned int uint32_t;
typedef unsigned long long uint64_t;
 Copy code

4.2.3 Alignment filling

stay Redis6.x In the source code SDS Its structure is struct __attribute__ ((__packed__)) And struct There is a big difference , This is actually similar to what we know Alignment filling of .

(1) Take a chestnut

Consider the following structures ：

typedef struct{
     char  c1;
     short s; 
     char  c2; 
     int   i;
} s;
 Copy code

If the members in this structure are arranged in a compact way , hypothesis c1 The starting address of is 0, be s The address for 1,c2 The address for 3,i The address for 4. Let's demonstrate our hypothesis with code .

#include <stdio.h>

typedef struct {
    char c1;
    short s;
    char c2;
    int i;
} s;

int main() {
    s a;
    printf("c1 -> %d, s -> %d, c2 -> %d, i -> %d\n",
           (unsigned int)(void *)&a.c1 - (unsigned int)(void *)&a,
           (unsigned int)(void *)&a.s - (unsigned int)(void *)&a,
           (unsigned int)(void *)&a.c2 - (unsigned int)(void *)&a,
           (unsigned int)(void *)&a.i - (unsigned int)(void *)&a);
    return 0;
}
//  The result is ：c1 -> 0, s -> 2, c2 -> 4, i -> 8
 Copy code

Embarrassed , It's not a bit different from the assumption ！ This is the ghost of alignment filling , What is this ~

(2) What is byte alignment

In modern computers , Memory space is divided by bytes , Theoretically, any type of variable can be accessed from any starting address . But in practice, when accessing a specific type of variable, it is often accessed at a specific memory address , This is Various types of data need to be arranged in space according to certain rules , Instead of storing one by one , This is alignment .

(3) Alignment reason

The reason why alignment filling is needed is that the processing of storage space is very different in each hardware platform . Some platforms can only access certain types of data from certain addresses .

The most common is if the data storage is not aligned according to the requirements suitable for its platform , Loss of access efficiency .

For example, some platforms start reading from my address every time , If one int type （ Assuming that 32 position ） Store it at the beginning of my address , Then one reading cycle can read out , And if it's stored at the beginning of the odd address , You may need to 2 A reading cycle , And the high and low bytes of the result read twice can be pieced together to get the int data , This leads to a lot of reduction in reading efficiency .

(4) Change alignment

Be careful ： When we write programs , No need to think about alignment . The compiler will choose the alignment strategy that suits the target platform for us .

If we have to change the alignment manually , Generally, the default boundary condition can be changed by the following methods ：

Using pseudo instructions #pragma pack(n)：C The compiler will follow n Byte alignment ;
Using pseudo instructions #pragma pack()： Cancel custom byte alignment .
in addition , There's another way (GCC Special grammar )：
__attribute((aligned (n)))： Align the active members of the structure in n Byte on the natural boundary . If the length of any member in the structure is greater than n, Then align according to the length of the largest member .
__attribute__ ((packed))： Cancels the optimal alignment of the structure during compilation , Align according to the actual number of bytes occupied .

Change the structure of the above example code as follows ( Unalign ), Re execution , It can be found that after the alignment is cancelled, it is consistent with our hypothesis .

typedef struct __attribute__ ((__packed__)) {
    char c1;
    short s;
    char c2;
    int i;
} s;
//  Re execution ：c1 -> 0, s -> 1, c2 -> 3, i -> 4
 Copy code

(5) Redis Why not align ？

To sum up, we know that aligned filling can improve CPU Data reading efficiency , As IO Frequent Redis Why choose not to align ？

Let's go back to Redis6.x Medium SDS structure ：

There is one detail you need to know , namely SDS The pointer does not point to SDS Starting position （len Location ）, It's directed at buf[], bring SDS You can use it directly C Language string.h Some functions in the library , Compatible , very nice~.

If you do not align and fill , Then get the current SDS You only need to step back flagsPointer = ((unsigned char*)s)-1;

contrary , If aligned, fill , because Padding The existence of , We don't know how much to get in different systems flags, And we can't put sds Pointer to flags, This is not compatible with C The function of language , I don't know how much to advance to get buf[].

4.3 SDS advantage

4.3.1 O(1) Time complexity gets the length of the string

because C String does not record its own length , So in order to get the length of a string, the program must traverse the string , Until I met '0' until , The time complexity of the whole operation is O(N). And we use SDS The encapsulated string is obtained directly len Property value is enough , The time complexity is O(1).

4.3.2 Binary security

What is binary security ？
informally ,C In language , use '0' Represents the end of a string , If the string itself has '0' character , The string will be truncated , That is, non binary security ; If through some mechanism , Ensure that the contents of a string are not damaged when it is read or written , Binary security .

C The characters in the string are except that the last character is '\0' Other characters cannot be empty characters , Otherwise it's considered the end of the string ( Even if it's not actually ). This limits C Strings can only hold text data , Instead of saving binary data . and SDS Use len Property to determine whether the string ends , So I won't suffer from '\0' Influence .

4.3.3 Prevent buffer overflow

String splicing is very frequently used , stay C Used in language development char *strcat(char *dest,const char *src) Methods will src The contents of the string are spliced into dest End of string .

because C String does not record its own length , all strcat The method already considers that the user has been dest Enough memory allocated , Enough to hold src Everything in the string , Once this condition is not true, a buffer overflow will occur , Will overwrite other data ,Dangerous~.

// strcat  Source code 
char * __cdecl strcat (char * dst, const char * src) {
    char * cp = dst;
 
    while( *cp )
        cp++; /*  find  dst  Ending  */
 
    while( *cp++ = *src++ ) ; /*  Brainless general  src  Copied to the  dst  in  */
 
    return( dst ); /*  return  dst */
}    
 Copy code

As shown in the figure below, there is a buffer overflow ：

And C String is different ,SDS Of Automatic expansion mechanism Completely eliminate the possibility of buffer overflow ： When SDS API Need to be right SDS When making modifications ,API Will check SDS Whether the space meets the requirements for modification , If not satisfied ,API Will automatically SDS The space of is extended to the size required to perform the modification , The actual modification is then performed , So use SDS There is no need to manually modify SDS Space size of , There will be no buffer overflow .

SDS Of sds sdscat(sds s, const char *t) Method performs capacity expansion related operations during string splicing .

sds sdscatsds(sds s, const sds t) {
    return sdscatlen(s, t, sdslen(t));
}

/* s:  The source string  * t:  String to be spliced  * len:  The length of the string to be spliced  */
sds sdscatlen(sds s, const void *t, size_t len) {
    //  Gets the length of the source string 
    size_t curlen = sdslen(s);
		// SDS  Allocate space （ Automatic expansion mechanism ）
    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    //  Copy the destination string to the end of the source string 
    memcpy(s+curlen, t, len);
    //  to update  SDS  length 
    sdssetlen(s, curlen+len);
    //  Add closing 
    s[curlen+len] = '\0';
    return s;
}
 Copy code

Automatic expansion mechanism ——sdsMakeRoomFor Method

strcatlen Call in sdsMakeRoomFor Complete the capacity check and capacity expansion of the string , Focus on the analysis of this method ：

/* s:  The source string  * addlen:  New length  */
sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    // sdsavail: s->alloc - s->len,  obtain  SDS  The remaining length of 
    size_t avail = sdsavail(s);
    size_t len, newlen, reqlen;
    //  according to  flags  obtain  SDS  The type of  oldtype
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
    size_t usable;

    /* Return ASAP if there is enough space left. */
    //  The remaining space is greater than or equal to the new space , No need to expand , Directly return the source string 
    if (avail >= addlen) return s;
    //  Get the current length 
    len = sdslen(s);
    // 
    sh = (char*)s-sdsHdrSize(oldtype);
    //  New length 
    reqlen = newlen = (len+addlen);
    //  Assert that the new length is longer than the original length , Otherwise, terminate the execution 
    assert(newlen > len);   /*  Prevent data overflow  */
    // SDS_MAX_PREALLOC = 1024*1024,  namely 1MB
    if (newlen < SDS_MAX_PREALLOC)
        //  The length after adding is less than  1MB , Then expand the capacity by twice the new length 
        newlen *= 2;
    else
        //  The length after adding is greater than  1MB , Add... According to the new length  1MB  Capacity expansion 
        newlen += SDS_MAX_PREALLOC;
    //  Recalculate  SDS  The type of 
    type = sdsReqType(newlen);

    /* Don't use type 5: the user is appending to the string and type 5 is * not able to remember empty space, so sdsMakeRoomFor() must be called * at every appending operation. */
    //  Don't use  sdshdr5 
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;
    //  To obtain a new  header  size 
    hdrlen = sdsHdrSize(type);
    assert(hdrlen + newlen + 1 > reqlen);  /* Catch size_t overflow */
    if (oldtype==type) {
        //  The type hasn't changed 
        //  call  s_realloc_usable  Reallocate available memory , Return to new  SDS  Head pointer 
        // usable  Will be set to the currently allocated size 
        newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL; //  If the allocation fails, it will be returned directly NULL
        //  Get directions  buf  The pointer to 
        s = (char*)newsh+hdrlen;
    } else {
        //  Type change leads to  header  The size of the changes , Need to move the string forward , Out of commission  realloc
        newsh = s_malloc_usable(hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL;
        //  Put the original string copy Into the new space 
        memcpy((char*)newsh+hdrlen, s, len+1);
        //  Free the memory of the original string 
        s_free(sh);
        s = (char*)newsh+hdrlen;
        //  to update  SDS  type 
        s[-1] = type;
        //  Set length 
        sdssetlen(s, len);
    }
    //  obtain  buf  Total length ( undetermined )
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        //  If the available space is greater than the maximum length supported by the current type, it will be truncated 
        usable = sdsTypeMaxSize(type);
    //  Set up  buf  Total length 
    sdssetalloc(s, usable);
    return s;
}
 Copy code

Summary of automatic capacity expansion mechanism ：

Expansion stage ：

if SDS Free space left in avail Greater than the length of the new content addlen, There is no need to expand the capacity ;
if SDS Free space left in avail Less than or equal to the length of the new content addlen：
- If the total length after adding len+addlen < 1MB, Then expand the capacity by twice the new length ;
- If the total length after adding len+addlen > 1MB, Add... According to the new length 1MB Capacity expansion .

Memory allocation phase ：

Select the corresponding... According to the length after capacity expansion SDS type ：
- If the type remains the same , You just have to go through s_realloc_usable expand buf The array can be ;
- If the type changes , Then it needs to be for the whole SDS Reallocate memory , And put the original SDS Copy content to new location .

The flow chart of automatic capacity expansion is as follows ：

After expansion SDS Will not fit the newly added characters , Instead, more space was allocated ( Pre allocation strategy ), This reduces the number of memory reallocations caused by modifying strings

4.3.4 Memory reallocation times optimization

(1) Space pre allocation strategy

because SDS Space pre allocation strategy , SDS The string will not be allocated space frequently during the growth process . Through this allocation strategy ,SDS Will continue to grow N The number of memory reallocation times required by the secondary string must be N Down to the most N Time .

(2) Inert space release mechanism

Space pre allocation strategy is used to optimize SDS Frequent space allocation during growth , The inert space release mechanism is used to optimize SDS When a string is shortened, memory reallocation is not immediately used to reclaim the extra space after shortening , And just update SDS Of len attribute , Extra space for future use .

SDS Call in sdstrim Method to shorten the string ：

/* sdstrim  Method to delete the beginning and end of a string  cset  Characters that have appeared in  *  such as : * s = sdsnew("AA...AA.a.aa.aHelloWorld :::"); * s = sdstrim(s,"Aa. :"); * printf("%s\n", s); * * SDS  Turned into  "HelloWorld" */
sds sdstrim(sds s, const char *cset) {
    char *start, *end, *sp, *ep;
    size_t len;

    sp = start = s;
    ep = end = s+sdslen(s)-1;
    // strchr() Function to find a specific character in a given string 
    while(sp <= end && strchr(cset, *sp)) sp++;
    while(ep > sp && strchr(cset, *ep)) ep--;
    len = (sp > ep) ? 0 : ((ep-sp)+1);
    if (s != sp) memmove(s, sp, len);
    s[len] = '\0';
    //  Just updated len
    sdssetlen(s,len);
    return s;
}
 Copy code

Corrigendum

stay 《Redis Design and implementation 》 A book on sdstrim The explanation of the method is ： Delete... In string cset All characters that appear , Not from beginning to end .
such as ： call sdstrim("XYXaYYbcXyY","XY"), Move back except for all 'X' and 'Y'. This is wrong ~

SDS There is no release of the extra 5 Byte space , Will only len Set up a 7, The remaining space is 5. It can come in handy if the subsequent string grows （ There may be no need to reallocate memory ）.

Maybe you will have questions again , It doesn't really free up space , Will it lead to memory leakage ？ don 't worry ,SDS Provides us with a real release SDS Methods that do not use space sdsRemoveFreeSpace.

sds sdsRemoveFreeSpace(sds s) {
    void *sh, *newsh;
    //  Access to type 
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    //  obtain  header  size 
    int hdrlen, oldhdrlen = sdsHdrSize(oldtype);
    //  Get the length of the original string 
    size_t len = sdslen(s);
    //  Get the available length 
    size_t avail = sdsavail(s);
    //  Get the pointer to the head 
    sh = (char*)s-oldhdrlen;

    /* Return ASAP if there is no space left. */
    if (avail == 0) return s;

    //  Find the optimal length for this string  SDS  type 
    type = sdsReqType(len);
    hdrlen = sdsHdrSize(type);

    /*  If the type is the same , Or at least you still need a large enough type , We only need  realloc buf that will do ; *  otherwise , It means a lot of changes , Then manually reassign the string to use a different header file type . */
    if (oldtype==type || type > SDS_TYPE_8) {
        newsh = s_realloc(sh, oldhdrlen+len+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+oldhdrlen;
    } else {
        newsh = s_malloc(hdrlen+len+1);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        //  Free memory 
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }
    //  Reset the total length to len
    sdssetalloc(s, len);
    return s;
}
 Copy code

4.4 SDS What's the longest ？

Redis The official gave The maximum string size is 512MB. Why is that ？

stay Reids3.x In the version len It's using int Embellished , This will lead to buf The longest is 2147483647, It virtually limits the maximum length of the string .

Any details can be found in the source code , stay _sdsnewlen Method creation SDS Will call sdsTypeMaxSize Method to get the maximum value that each type can create buf length , It is not difficult to find that the maximum return value of this method is 2147483647, namely 512MB.

static inline size_t sdsTypeMaxSize(char type) {
    if (type == SDS_TYPE_5)
        return (1<<5) - 1;
    if (type == SDS_TYPE_8)
        return (1<<8) - 1;
    if (type == SDS_TYPE_16)
        return (1<<16) - 1;
#if (LONG_MAX == LLONG_MAX)
    if (type == SDS_TYPE_32)
        return (1ll<<32) - 1; //  Whatever the method means , Maximum return 2147483647.OVER~
#endif
    return -1; /* this is equivalent to the max SDS_TYPE_64 or SDS_TYPE_32 */
}
 Copy code

In this method Redis3.0.0 There is no such thing as

4.5 part API Source code interpretation

establish SDS

Redis adopt sdsnewlen Method creation SDS. In the method, the appropriate type will be selected according to the initialization length of the string .

sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
    void *sh;
    sds s;
    //  Judge according to the initialization length  SDS  The type of 
    char type = sdsReqType(initlen);
    // SDS_TYPE_5  Cast to  SDS_TYPE_8
    //  This side verifies  sdshdr5  Never used , Creating this step is GG 了  ੯ੁૂ‧̀͡u\ if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    //  Get head University 
    int hdrlen = sdsHdrSize(type);
    //  Point to  flags  The pointer to 
    unsigned char *fp; /* flags pointer. */
    //  Allocated space 
    size_t usable;
    //  Prevent overflow 
    assert(initlen + hdrlen + 1 > initlen); /* Catch size_t overflow */
    //  Allocate space 
    // s_trymalloc_usable:  Try to allocate memory , Failure returns NULL
    // s_malloc_usable:  Allocate memory or throw exceptions [ unfriendly ]
    sh = trymalloc?
        s_trymalloc_usable(hdrlen+initlen+1, &usable) :
        s_malloc_usable(hdrlen+initlen+1, &usable);
    if (sh == NULL) return NULL;
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    // s  Now point to buf
    s = (char*)sh+hdrlen;
    //  Point to flags
    fp = ((unsigned char*)s)-1;
    usable = usable-hdrlen-1;
    //  For different types of  SDS  Allocable space for truncation 
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    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 = usable;
            *fp = type;
            break;
        }
        // ...  Omit 
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    //  Add... At the end \0
    s[initlen] = '\0';
    return s;
}
 Copy code

adopt sdsnewlen Methods we can get the following information ：

SDS_TYPE_5 Will be forced to SDS_TYPE_8 type ;
When creating, by default, you will add... At the end '\0';
The return value points to SDS In structure buf The pointer to ;
The return value is char *sds type , Compatible parts C function .

Release SDS

In order to optimize performance ,SDS It does not release memory directly , But by resetting len Reach empty SDS The method of purpose ——sdsclear. Changing the method will only SDS Of len Zeroing , and buf And for really being emptied , New data can be copied , Instead of re applying for memory .

void sdsclear(sds s) {
    sdssetlen(s, 0);//  Set up len by 0
    s[0] = '\0';//“ Empty ”buf
}
 Copy code

If you really want to empty SDS You can call sdsfree Method , The bottom layer calls s_free Free memory .

void sdsfree(sds s) {
    if (s == NULL) return;
    s_free((char*)s-sdsHdrSize(s[-1]));
}
 Copy code

I'm aobing , The more you know , The more you don't know , Thank you for your ： give the thumbs-up 、 Collection and Comment on , See you next time ！