Step into Redis- In-depth understanding of SDS

At the bottom of Redis’s most common string type is its own implementation of a data structure ** (Simple Dynamic Strings) for storing string and integer data. And this is one of the most common interview questions:

Interviewer: Do you know the character base in Redis?

Zhang: Yes, SDS ~😎😎

Interviewer: Ok, then tell me his details. Why not use the characters in C language and design a set of SDS separately?

* * * * * * * * * * * * * * * *

Interviewer: HH, go home and wait for the announcement. On the contrary, we have no idea about

The data structure

In C, if you want to design an SDS, you must have a string pointer. In addition, you can add some basic statistics: the current string length, the remaining capacity, and so on.

This structure was used before Redis 3.2:

struct sds {
    int len;// Number of bytes used in buF
    int free;// The number of bytes left in buf
    char buf[];// Real data space
};
Copy the code

Doing this has several advantages over c strings:

• Can quickly obtain the length of buf[], the remaining space, etc., relative to the C string, time complexity is O(1).

• What is exposed to the upper layer is a pointer to buf[]. SDS encapsulates some methods for external use, and SDS is also compatible with various operations on C strings

• Resolved binary security issues

  What is binary security? Generally speaking, in C language, “\0” is used to indicate the end of the character string. If there is a “\0” character in the string itself, the string will be truncated, that is, not binary safe; A string is binary safe if it is read or written by a mechanism that does not damage its contents.

Image from Redis 5 design and source code analysis

In x64, len and free are 4 bytes each, and buf[] is a dynamic array that dynamically allocates memory via malloc.

Can SDS be optimized again? We take into account that each string actually uses different bytes, but the header of a short string is the same length as the header of a long string, which is a bit wasteful.

As a result, after Redis 5.0, the SDS can store the length of the classification: length: less than 1 byte, 1 byte, 2 byte, 4 byte, 8 byte, a total of 5, with the bit operation to save at least 3 bits (000), then its high order can be used to save the length of BUF [].

For example, for short strings of less than 32 bits (2^5), flags only takes 1 byte, which is a great storage optimization compared to the 4+4 we used earlier.

/* 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; /* Lower 3-bit storage type, higher 5-bit storage length */
    char buf[];/* Flexible array, store actual contents */
};
Copy the code

Schematic of SDSHDR5:

Here’s a detail:

The comment for sdshdr5 states that it is no longer used, but in fact if it stores data (its structure is less than 32 bits for keys and less than 32 bits for values), its keys will be stored in SDSHdr5 and its values will be stored in SDshdr8.

If we look at the Redis source code, we can see that there are some other types defined, and these are the ones we usually use

struct __attribute__(((packed__)) sdshdr8 {
    uint8_t len; /* Unsigned 8-bit int, record length */
    uint8_t alloc; /* Does not include headers and terminators */
    unsigned char flags; /* The lower digit is used to save the type, the higher fifth digit is not used, it is reserved */
    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[];
};
Copy the code

Len stores the number of bytes that buF has occupied

Alloc stores the number of bytes allocated to buF, but does not include headers and terminators

Flags is used to store the size type. The high five bits are reserved

Buf [] flexible array

Basic operation

So having said SDS data structure, we should also focus on the most basic add, delete, change and check

I’m going to give you some ideas ahead of time so you can check them out on your own

.

Here are just a few of the important ones

String creation

typedef char *sds;
/* Create a new SDS string * and 'initlen' with the contents specified by the 'init' pointer. * If NULL is used for 'init', the string is initialized with zero bytes. * If SDS_NOINIT is used, the buffer is not initialized; * * Strings always end with a null character (all SDS strings do, always) so * * Even if you create an SDS string with the following: * * myString = sDSNewlen (" ABC ",3); * * You can use printf() to print strings, because at the end of the * string. However, the string is binary safe and can contain the \0 character in the middle because the length is stored in the SDS header. * /
sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
    void *sh;
    sds s;
    char type = sdsReqType(initlen);
    /* Empty strings are usually created in order to append. Use type 8 * since type 5 is not good at this. */
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;  // An empty string will be strongly typed here if the condition is met
    int hdrlen = sdsHdrSize(type); // Length of the head
    unsigned char *fp; / / pointer to flags
    size_t usable;

    assert(initlen + hdrlen + 1 > initlen); // Initial string length + header length +1(where 1 represents \0 terminator)
    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 = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)- 1;
    usable = usable-hdrlen- 1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    switch(type) {  // Obtain different flags according to different SDS types
        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;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break; }}if (initlen && init)
        memcpy(s, init, initlen);
    s[initlen] = '\ 0';
    return s;
}
Copy the code

The general process is as follows:

Conclusion:

• When an empty string is created, SDS_TYPE_5 is cast to SDS_TYPE_8
• The “+1” operation is used to calculate the length, because the \0 terminator is added

The release of

SDS provides related methods sDSfree and SDSClear, the former is to directly release the memory, while the latter is to clear the length, reducing the memory overhead, so that the new data can be directly covered after coming in.

void sdsfree(sds s) {
    if (s == NULL) return;
    s_free((char*)s-sdsHdrSize(s[- 1]));// Free memory directly here
}

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

Joining together

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

/* Join t and s */
sds sdscatlen(sds s, const void *t, size_t len) {
    size_t curlen = sdslen(s);
    s = sdsMakeRoomFor(s,len); // There is a capacity expansion operation
    if (s == NULL) return NULL;
    memcpy(s+curlen, t, len);// Select * from '//'
    sdssetlen(s, curlen+len);
    s[curlen+len] = '\ 0';// Add the terminator
    return s;
}

Copy the code

Related capacity expansion operations

#define SDS_MAX_PREALLOC (1024*1024) //1MB
/* Enlarges the free space at the end of the SDS string so that the caller * is sure to overwrite the bytes after the end of the addlen string by calling this function, plus one byte as an empty item. * If there is already enough free space, this function returns no * action, if there is not enough free space, it allocates what is missing, and * there may be more: * When greedy is 1, zoom in beyond what is needed to avoid the need to reallocate in the future * about incremental growth. * When greedy is 0, zoom in enough to make space available for 'addlen'. * * Note: This does not change the *length* * of the SDS string returned by sdslen(), but only the buffer space we have available. * /
sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[- 1] & SDS_TYPE_MASK;
    int hdrlen;
    size_t usable;

    /* Return as soon as possible if there is enough space. * /
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);// The original length + the stitching length
    assert(newlen > len);   /* Catch size_t overflow */
    if (greedy == 1) {   // Space allocation policy
        if (newlen < SDS_MAX_PREALLOC)  // The new length is less than 1M
            newlen *= 2;
        else
            newlen += SDS_MAX_PREALLOC; // The new length is greater than or equal to 1M}... }Copy the code

We can see that Redis has different strategies for assigning strings of different sizes:

• ifsdsThe remaining length is enough to allocate, so just go ahead and use it
• ifsdsThere’s not enough room left
  • The new lengthnewlenLess than 1 MB,newlen* 2
  • newlenGreater than or equal to 1MB innewlenBased on +1MB

The purpose of this is:Minimize memory usage and reduce overhead

Finally, the expansion will judge whether the storage type is correct again, if it is correct, it will directly allocate space, if not, it will re-open the memory and transplant the original string, as shown in the following code

sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
	...
    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. */
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    assert(hdrlen + newlen + 1 > len);  /* Catch size_t overflow */
    if (oldtype==type) {
        newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /* Because the header size changes, the string needs to be moved forward, * and realloc */ cannot be used
        newsh = s_malloc_usable(hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[- 1] = type;
        sdssetlen(s, len);
    }
    usable = usable-hdrlen- 1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    sdssetalloc(s, usable);
    return s;
}
Copy the code

General process:

To summarize

Advantages of SDS compared with Strings:

• You can quickly get string statistics, O(1) time complexity
• Prevent buffer overflow through fields such as Len and free
• Ensure binary security by replacing the \0 terminator with len
• Reduce memory consumption
  • pre-allocated
  • Inert release

The resources

Redis 5 Design and Source Code Analysis by Chen Lei