Redis: SDS source code parsing

1. Introduction

Hello, welcome to Redis data structure source code parsing series, in Redis Why so Fast? I mentioned earlier that one of the reasons Redis is fast is because of its simple and efficient data structures.

This series of articles is aimed at coders of all stages. Each article aobin will start from the command combat entry, then in-depth source code analysis, the final interview questions review these three directions to you volume king one by one.

2.SDS Command Practice [fresh off the boat]

SDS is the simplest data structure in Redis. All data structures in Redis are named by a unique key string, and value is obtained according to the key. The only difference lies in the data structure of value.

SDS is widely used in the production environment. For example, WE use SDS to do distributed locks. Turn objects into JSON strings for caching, etc. SDS is a very easy topic to talk about in the Redis interview process. It is very simple (or after reading this article, it is very simple 😄), the interviewer can not ask, but we can not understand 😄.

First of all, let’s start with the actual command. (the old driver directly skipped over)

IO /commands#st commands#st

2. 1 Setting a character string

Format: set


. The value can be a byte string, an integer, or a floating point.

> set name aobing
OK
Copy the code

2.2 Obtaining a String

Format: get

.

> get name
"aobing"
Copy the code

2.3 Obtaining the String Length

Format: strlen

> strlen name
(integer) 6
Copy the code

2.4 Obtaining substrings

Format: getrange

start end. Gets a substring of the string. Before dis2.0 this command was substr, now getrange. Returns a substring whose displacement is between start(starting at 0) and end (both included, rather than wrapping the head without the tail, as in other languages). You can use a negative offset to provide an offset from the end of the string.

So -1 represents the last character, -2 represents the penultimate character, and so on. This function handles out-of-range requests by limiting the result range to the actual length of the string (the end setting is very large and terminates 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 the code

2.5 Setting substrings

Format: setrange

offset substr. Return value: The length of the modified string.

Overwrites a portion of the string stored at the key at the specified offset, starting with the entire length of the value. If the offset is greater than the current length of the string at key, the string is padded with zero bytes to make the offset fit.

A nonexistent key is treated as an empty string, so this command will ensure that it contains a large enough string to be able to set the value to offset.

Note: You can set the maximum offset to 2^ 29-1 (536870911) because Redis strings are limited to 512 MB. If you need to go beyond 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 the code

2.6 Append substrings

Format: append

substr If the key already exists and is a string, this command appends the value to the end of the string. If the key does not exist, it is created and SET to an empty string, so APPEND will resemble SET in this particular case.

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

2.7 count

In Redis we often use strings as counters, incrementing by one using the incr command. Format: incr

. Returned value: the value after key increment. Increments the stored numeric key by 1.

If the key does not exist, it is set to 0 before performing the operation.

An error is returned if the key contains a value of the wrong type or contains a string that cannot be represented as an integer. This operation is limited to 64 – bit signed integers. The count is based on the range, which cannot exceed long. Max and cannot be lower than long.min.

2.8 Expiration and Deletion

The string can be deleted using the del command or the expire command. The string will be deleted automatically when it expires. We can use the TTL command to get the life of the string (how much time is left to expire).

Format: del


… Returned value: Number of keys to be deleted

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

Format: EXPIRE

time Returned value: 1 if timeout is set. Returns 0 if key does not exist.

How do I make an expired string permanent?

The lifetime can be removed by using the DEL command to delete the entire key, or overwrite by the SET and GETSET commands, which means that if a command simply changes the value of a lifetime key instead of replacing it with a new key, So the survival time won’t change.

For example, executing INCR on a key, LPUSH on a list, or HSET on a hash table does not change the lifetime of the key itself.

If RENAME is used to RENAME a key, the renamed key has the same lifetime as before.

Another possibility of the RENAME command is to try to RENAME a key with a lifetime to another key with a lifetime, another_key. In this case, the old another_key (and its lifetime) is deleted, and the old key is renamed another_key. Therefore, the new another_key has the same lifetime as the original key.

The PERSIST command enables you to remove the lifetime of a key without deleting it, making it a “persistent” key again.

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

3. Introduction and Characteristics of SDS

Redis interview probability will refer to the relevant data structure, most of the SDS eight-part text back as flow, but did not read the source code, know why, this can be absolutely impossible!!

4.SDS structure model [old driver]

Redis source code for the latest Redis6.2.6 andRedis3.0.0 version

When you hear that the String in Redis is not a Simple C language String, but a Simple Dynamic String (SDS), you think that you have created something new. What I want to say is not to panic. In fact, the source code of SDS content is typedef char * SDS; .

4.1 Data Structure

The data structure definition of SDS in REdis6.x is quite different from that in Redis3.0.0, but the core idea remains the same. Let’s start with the easy version (redis3.x)

struct sdshdr {
    // Records the number of bytes used in the BUF array
    // is equal to the length of the string saved by SDS
    unsigned int len;

    // Records the number of unused bytes in the BUF array
    unsigned int free;

    //char array, used to hold strings
    char buf[];
};
Copy the code

Here’s how the string “Aobing” is stored in Redis:

• Len is 6, indicating that the SDS stores a string of length 5;
• If free is 0, this SDS has no remaining space.
• Buf is an array of type char. Note that a null character ‘\0’ is saved at the end.

Buf automatically appends a ‘\0’ character to len in SDS. This is to comply with the convention of C strings ending in an empty string, so that SDS can directly use a part of the String. h library functions such as strlen

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

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

4.2 Harsh data optimization

4.2.1 Data structure optimization

So far we seem to have a well-structured SDS, but can we continue to optimize it?

In the redis3. x version, strings of different lengths take up the same amount of header space, so if a string is short and the header takes up more space, it’s wasteful. So we divide SDS into three levels of strings:

• Short strings (less than 32 characters in length), len and free are 1 byte long.
• A long string, either 2 or 4 bytes;
• Super long string, 8 bytes.

There are five types of SDS (less than 1 byte, 1 byte, 2 byte, 4 byte, 8 byte)

We can add a type field to the SDS to identify the type, but there is no need to use a 4-byte int to do that! You can use a 1-byte char to get the type using a bit operation (3 bits can identify 2^3 types).

The following is the optimized form for a short string (length less than 32) :

The lower bit storage type and the higher bit storage length can contain a maximum of 32 bytes. Therefore, the length of a short string must be less than 32 bytes.

The free field is not required; 32-len is free

Take a look at how redis6.x does it!

// Note: sdshdr5 is never used, Redis only accesses flags.
struct __attribute__(((packed__)) sdshdr5 {
    unsigned char flags; /* Lower 3-bit storage type, higher 5-bit storage length */
    char buf[];
};
struct __attribute__(((packed__)) sdshdr8 {
    uint8_t len; /* Already used */
    uint8_t alloc; /* Total length, stored in 1 byte */
    unsigned char flags; /* Low 3 bit storage type, high 5 bit reserved */
    char buf[];
};
struct __attribute__(((packed__)) sdshdr16 {
    uint16_t len; /* Already used */
    uint16_t alloc; /* Total length, stored in 2 bytes */
    unsigned char flags; /* Low 3 bit storage type, high 5 bit reserved */
    char buf[];
};
struct __attribute__(((packed__)) sdshdr32 {
    uint32_t len; /* Already used */
    uint32_t alloc; /* Total length, stored in 4 bytes */
    unsigned char flags; /* Low 3 bit storage type, high 5 bit reserved */
    char buf[];
};
struct __attribute__(((packed__)) sdshdr64 {
    uint64_t len; /* Already used */
    uint64_t alloc; /* Total length, stored in 8 bytes */
    unsigned char flags; /* Low 3 bit storage type, high 5 bit reserved */
    char buf[];
};
Copy the code

The data structure is similar to what we analyzed. Instead of an int, it is a 1-byte char, with three bits to indicate the specific type.

At the same time, Redis also declared five constants representing five types of SDS respectively, which happened to agree 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 the code

4.2.2 uintX_t

Uint8_t/uint16_t/uint32_t /uint64_t At first glance, it looks like a new type, after all, C language does not have these types!

Ao third first see is also full of fog water, after all C language forgot almost. C has a typedef. And _t is short for that. Check the relevant 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 the code

4.2.3 Align padding

In the source code of redis6.x, the structure of SDS is struct __attribute__ ((__packed__)), which is quite different from struct. This is actually related to the alignment padding that we are familiar with.

(1) For example, 🌰

Consider the following structure:

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

If the members of this structure are compact, assuming that C1 starts at address 0, the address of S is 1, that of C2 is 3, and that of I is 4. Let’s demonstrate our hypothesis with some code.

#include <stdio.h>

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

int main(a)
{
    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;
}
C1 -> 0, S -> 2, C2 -> 4, I -> 8
Copy the code

Embarrassed 😓, with the assumption is not the slightest bit! That’s what alignment padding is all about, blah blah blah

(2) What is byte alignment

In modern computers, memory space is divided into bytes, and any type of variable can theoretically be accessed from any starting address. But in practice, when accessing a variable of a particular type, it is often accessed at a specific memory location, which requires that the data of various types be arranged in space according to certain rules, rather than being placed one after another in order, which is called alignment.

(3) Align the reasons

The reason for the need for aligned padding is that storage space is treated very differently by hardware platforms. Some platforms can only access certain types of data from certain locations.

The most common is the loss of access efficiency if data storage is not aligned to the requirements appropriate for its platform.

Some platforms such as every time I read from my address, if an int type (assuming 32-bit) stored in my address, they can read a read cycle, if stored in address starts, is likely to need 2 read cycle, and the results of two readout of high and low together to get the int data bytes, Resulting in a significant decrease in read efficiency.

(4) Change the alignment

Note: we don’t need to worry about alignment when we write programs. The compiler selects an alignment strategy for us that is appropriate for the target platform.

If we must manually change the alignment, we can generally change the default alignment conditions as follows:

• Using the pseudo-directive #pragma pack(n) : the C compiler will align by n bytes;

• Use the pseudo-directive #pragma pack() : Uncustomize byte alignment.

  Alternatively, there is the following option (GCC specific syntax) :

• __attribute((aligned (n))) : Causes structure members to be aligned on n-byte natural boundaries. If there are members in the structure whose length is greater than n, align them according to the length of the largest member.

• __attribute__ ((Packed)) : Disables the optimized alignment of structures during compilation and aligns them according to the actual number of bytes consumed.

Change the structure of the above sample code to the following (unaligned) and execute it again. You can see that the unaligned structure is consistent with our hypothesis.

typedef struct __attribute__(((packed__))
{
    char c1;
    short s;
    char c2;
    int i;
} s;
C1 -> 0, s -> 1, C2 -> 3, I -> 4
Copy the code

(5) Why is Redis not aligned?

To sum up, we know that aligned padding can improve the efficiency of CPU data reading. As I/O frequent Redis, why choose not aligned?

Let’s review the SDS structure in redis6.x again:

The pointer to SDS does not point to the SDS starting position (len position), but directly to buF []. This allows SDS to use some functions in the STRing. h library of C language.

FlagsPointer = (((unsigned char*)s)-1; flagsPointer = ((unsigned char*)s)-1;

On the contrary, if Padding is used for alignment filling, we do not know how far back to get flags in different systems due to the presence of Padding, and we cannot point the POINTER of SDS to flags, so it is not compatible with C language functions, and we do not know how far forward to get BUf [].

4.3 SDS advantage

4.3.1 O(1) Time Complexity The length of the character string is obtained

Since the C string does not record its length, to get the length of a string, the program must traverse the string until it hits ‘0’, in O(N) time. When SDS is used to encapsulate the string, len attribute value can be obtained directly, and the time complexity is O(1).

4.3.2 Binary Security

What is binary security?

Generally speaking, in C, ‘0’ is used to indicate the end of a string. If the string itself has a ‘0’ character, the string will be truncated, that is, it is not binary safe. A string is binary safe if it is read or written by a mechanism that does not damage its contents.

C characters in a string other than the last character ‘\0’ cannot be null, otherwise it will be considered the end of the string (even if it is not). This limits C strings to holding only textual data, not binary data. SDS, on the other hand, uses the value of the len attribute to determine whether the string ends, so it is not affected by ‘\0’.

4.3.3 Preventing buffer overflow

Char *strcat(char *dest,const char * SRC) is used to concatenate the contents of SRC string to the end of dest string.

Since the C string does not record its length, all strcat methods assume that the user has allocated enough memory for dest to contain all the contents of the SRC string when executing this function, and that a buffer overflow will occur if this condition is not true, overwriting other data. Dangerous~

/ / strcat source code
char * __cdecl strcat (char * dst, const char * src)
{
    char * cp = dst;
 
    while( *cp )
        cp++; /* Find the end of DST */
 
    while( *cp++ = *src++ ) ; /* Brainless copies SRC to DST */
 
    return( dst ); Return DST */
}    
Copy the code

The following figure shows a buffer overflow:

Unlike C strings, SDS’s automatic expansion mechanism completely eliminates the possibility of buffer overflows: When THE SDS API needs to modify the SDS, the API will check whether the SDS space meets the requirements for modification. If not, the API will automatically expand the SDS space to the required size before the actual modification operation is carried out. Therefore, it is not necessary to manually modify the SDS space with SDS. There will be no buffer overflow problems.

The SDS SDSCat (SDS S, const char * T) method of SDS performs capacity expansion during string concatenation.

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

/* s: source string * t: string to be spliced * len: length of string to be spliced */
sds sdscatlen(sds s, const void *t, size_t len) {
    // Get the source string length
    size_t curlen = sdslen(s);
		// SDS allocates space (automatic expansion mechanism)
    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    // Copy the target string to the end of the source string
    memcpy(s+curlen, t, len);
    // Update the SDS length
    sdssetlen(s, curlen+len);
    // Appends the terminator
    s[curlen+len] = '\ 0';
    return s;
}
Copy the code

Automatic capacity expansion mechanism — sdsMakeRoomFor method

Strcatlen call sdsMakeRoomFor to complete string capacity check and expansion operations, focusing on the analysis of this method:

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

    /* Return ASAP if there is enough space left. */
    // If the remaining space is greater than or equal to the newly added space, the source string is returned without expansion
    if (avail >= addlen) return s;
    // Get the current length
    len = sdslen(s);
    // 
    sh = (char*)s-sdsHdrSize(oldtype);
    / / the new length
    reqlen = newlen = (len+addlen);
    // Assert that the new length is longer than the original length, otherwise terminate execution
    assert(newlen > len);   /* Prevent data overflow */
    // SDS_MAX_PREALLOC = 1024*1024, that is, 1MB
    if (newlen < SDS_MAX_PREALLOC)
        // if the new length is less than 1MB, the new length is twice that of the new length
        newlen *= 2;
    else
        // if the new length is greater than 1MB, add 1MB to the new length
        newlen += SDS_MAX_PREALLOC;
    // Recalculate the type of SDS
    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. */
    // Do not use sdshdr5
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;
    // Get the new header size
    hdrlen = sdsHdrSize(type);
    assert(hdrlen + newlen + 1 > reqlen);  /* Catch size_t overflow */
    if (oldtype==type) {
        // The type is unchanged
        // call s_realloc_usable to reallocate the available memory and return the head pointer to the new SDS
        // usable is set to the currently allocated size
        newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL; // Return NULL on assignment failure
        // Get a pointer to buf
        s = (char*)newsh+hdrlen;
    } else {
        // The type change causes the header size to change, so the string needs to be moved forward. Realloc cannot be used
        newsh = s_malloc_usable(hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL;
        // Copy the original string into the new space
        memcpy((char*)newsh+hdrlen, s, len+1);
        // Free the original string memory
        s_free(sh);
        s = (char*)newsh+hdrlen;
        // Update the SDS type
        s[- 1] = type;
        // Set the length
        sdssetlen(s, len);
    }
    // Get the total length of buF (TBD)
    usable = usable-hdrlen- 1;
    if (usable > sdsTypeMaxSize(type))
        // Truncate if the available space is greater than the maximum length supported by the current type
        usable = sdsTypeMaxSize(type);
    // Set the buF length
    sdssetalloc(s, usable);
    return s;
}
Copy the code

Summary of automatic capacity expansion mechanism:

Expansion phase:

• If the remaining free space in SDS avail is greater than the length of the new content addlen, there is no need to expand;
• If the remaining free space in SDS avail is less than or equal to the length of the new content addlen:
  • If the total length of len+addlen is less than 1MB, the capacity expansion is twice that of the new length.
  • If len+addlen is greater than 1MB, add 1MB to the new length.

Memory allocation phase:

• Select the SDS type based on the expanded length:
  • If the type does not change, simply passs_realloc_usableExpand the buF array;
  • If the type changes, you need to reallocate memory for the entire SDS and copy the original SDS contents to the new location.

The flowchart for automatic capacity expansion is as follows:

The expanded SDS does not hold exactly the newly added characters, but allocates more space (preallocation strategy), which reduces the number of memory reallocations when changing strings

4.3.4 Optimized the number of Memory reallocation times

(1) Space pre-allocation strategy

Because of the SDS pre-allocation policy, SDS strings do not allocate space frequently during growth. With this allocation strategy, SDS reduces the number of memory reallocations required to grow a string N times in a row from a certain number of N to a maximum of N.

(2) Inert space release mechanism

The space preallocation strategy is used to optimize the frequent space allocation when SDS grows, while the lazy space release mechanism is used to optimize the SDS string shortening not to immediately use memory redistribution to reclaim the extra space, but only update the LEN attribute of SDS, the extra space for future use.

Call the sdSTRIm method in SDS to shorten the string:

* s = sdsnew("AA... AA.a.aa.aHelloWorld :::"); * s = sdstrim(s,"Aa. :"); * printf("%s\n", s); * * SDS becomes "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;
    The STRCHR () function is used to find a particular 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';
    // Only len is updated
    sdssetlen(s,len);
    return s;
}
Copy the code

errata

The sdSTRIm method is explained in the Design and Implementation of Redis as follows: Remove all cSET characters from the string, not the beginning and end.

For example, call sdstrim(“XYXaYYbcXyY”,”XY”) and remove all ‘X’ and ‘Y’. This is wrong ❌ ~

SDS does not free the extra 5 bytes, but simply sets len to 7 and the remaining space to 5. This is useful if the string grows later (perhaps without reallocating memory).

Maybe you will have a question, this does not really free up space, whether it will lead to memory leaks? Rest assured, SDS provides us with a real way to free up SDS unused space sdsRemoveFreeSpace.

sds sdsRemoveFreeSpace(sds s) {
    void *sh, *newsh;
    // Get the type
    char type, oldtype = s[- 1] & SDS_TYPE_MASK;
    // Get the 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 a pointer to the head
    sh = (char*)s-oldhdrlen;

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

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

    /* If the type is the same, or at least still needs a large enough type, we just need realloc buf; * Otherwise, if the specification changes significantly, manually reassign the string to use a different header 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 the code

4.4 What is the maximum SDS?

Redis officially gives a maximum string size of 512MB. Why is that?

In the reids3.x versionlenIs decorated with int, which causes buf to be the longest2147483647, virtually limits the maximum length of a string.

Any details can be found in the source code. In the SDS created by the _sdsnewlen method, the sdsTypeMaxSize method is called to get the maximum buF length that can be created for each type. It is not hard to see that the maximum return value of this method is 2147483647, or 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, the maximum return is 2147483647. OVER~
#endif
    return - 1; /* this is equivalent to the max SDS_TYPE_64 or SDS_TYPE_32 */
}
Copy the code

This method does not exist in Redis3.0.0

4.5 Interpretation of some API source code

Create the SDS

Redis creates SDS through the sdsNewlen method. The appropriate type is selected in the method based on the string initialization length.

sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
    void *sh;
    sds s;
    // Determine the type of SDS based on the initialization length
    char type = sdsReqType(initlen);
    // SDS_TYPE_5 is cast to SDS_TYPE_8
    ੯ੁૂ · awfully u\ if (type == sds_type_5&&initlen == 0) type = SDS_TYPE_8; // If (type == sds_type_5&&initlen == 0) type = SDS_TYPE_8;
    // Get the head university
    int hdrlen = sdsHdrSize(type);
    // A pointer to flags
    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: NULL is returned if memory allocation fails
    // s_malloc_usable: allocating memory or throwing exceptions
    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 points to buf
    s = (char*)sh+hdrlen;
    / / points to flags
    fp = ((unsigned char*)s)- 1;
    usable = usable-hdrlen- 1;
    // Truncate the space allocated by different types of SDS
    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 \0 to the end
    s[initlen] = '\ 0';
    return s;
}
Copy the code

With the sdsnewlen method we can get the following information:

• SDS_TYPE_5Will be cast toSDS_TYPE_8Type;
• It is added at the end by default'\ 0';
• The return value is a pointer to buF in the SDS structure;
• The return value ischar *sdsType that can be compatible with some C functions.

The release of SDS

To optimize performance, SDS provides a way to clean up SDS by resetting LEN instead of directly freeing memory. The new method only zeros SDS len, and buF space is not really empty, new data can be copied without reapplying memory.

void sdsclear(sds s) {
    sdssetlen(s, 0);// Set len to 0
    s[0] = '\ 0';/ / "empty" buf
}
Copy the code

If you really want to empty SDS, you can call the sDSfree method, and the underlying memory is freed by calling s_free.

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

I’m Aobing, the more you know, the more you don’t know, thank you for your talent: likes, favorites and comments, we’ll see you next time!

---

The article is constantly updated. You can search “Aobing” on wechat to read it for the first time.