Redis - SDS simple dynamic string

Definition explanation

Redis No direct use C The traditional string representation of the language ( With empty characters \0 Array of characters at the end , hereinafter referred to as C character string ), Instead, I built a simple dynamic string (simple dynamic string,SDS) Abstract type of , And will SDS As the default string representation .

Redis The protocol content from the client to the server 、 aof cache 、 The reply returned to the client and so on , These important contents are made up of sds Type to save . Only when the string does not need to be modified C character string , For the rest of the cases SDS.

Don't use C There are several reasons for strings ：

1）C Language strings do not record their own length , If you want to know the length of a string, you must traverse the string , The complexity is O(N), and Redis The same command is used for string STRLEN When , The complexity is O(1).

2） Binary security , Can store non text data , Including video , Audio , Pictures, etc .SDS Not like the traditional C character string ( A character array ) equally , and SDS It is often called a byte array , Store data in bytes , And the last \0 It's also a byte , How to store such data , When you take it out, it's still like , So it's binary safe . Because... Is defined in the structure len attribute , So it appears in the middle of the string in time \0 It can also be stored completely without being truncated .

3） You can perform append operations efficiently （append）, Speed up the append operation , And reduce the number of memory allocation , The cost is a bit more memory , And that memory is not actively released .

Source code interpretation

about SDS ,Redis There are five ways to implement SDS_TYPE_5、SDS_TYPE_8、SDS_TYPE_16、SDS_TYPE_32、SDS_TYPE_64. Which type to use depends on the length of the initialization , Thus reducing the use of memory .

data structure

be located sds.h The header file

struct __attribute__ ((__packed__)) sdshdr8 {

    uint8_t len;         //  Bytes used 
    uint8_t alloc;       //  Total available character space size , It should be practical buf Reduce the size of 1 ( because c The end of the string must be  \0,  Don't count in ).
    unsigned char flags; //  Sign a , Mainly to identify that this is sdshdr A few , At present, only 3 position , also 5 Bit spare 
    char buf[];          //  Where the string is actually stored   In fact, that is  C  Native string + Some free space 

};

But when initialized to null and SDS_TYPE_5 More special , In the source code, it will be cast to SDS_TYPE_8. Understanding is because in this case , It is very likely that additional data will be added later . So give a more appropriate grade .

be located sds.c

sds sdsnewlen(const void *init, size_t initlen) {

...

    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    
...

}

What's interesting is that for Key and Value Very small , Only Value Will be forced to turn , I understand that Key Not very often . So give the minimum value .


sds sdsnewlen(const void *init, size_t initlen) {
    
...
    s[initlen] = '\0';
    return s;
}

sdsnewlen() Back to SDS The pointer does not directly point to sdshdr The address of , It points directly to sdshdr in buf The address of . Because it's compatible with c Native string , buf In fact, that is C Native string + Some free space , In the middle is a special symbol ’\0’ separate ,‘\0’ It's a logo. C The symbol at the end of the string , In this way, and C Compatibility of native strings , part C A string of API It can also directly make .

Scale operation

If the newly applied memory plus the used memory does not exceed SDS_MAX_PREALLOC(1024*1024) Then press * 2 Multiple applications . On the contrary, press SDS_MAX_PREALLOC Increasing .


//  expand sds Actual free space , So that more strings can be spliced later .
//  It doesn't really change here sds The length of , It just adds more available space (buf)
sds sdsMakeRoomFor(sds s, size_t addlen) {
...

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);

    //  Within SDS_MAX_PREALLOC front , Capacity expansion is based on 2 Double the way to expand , After exceeding, it can only be incremented 
    if (newlen < SDS_MAX_PREALLOC)  // SDS_MAX_PREALLOC = 1024*1024
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
...
    sdssetalloc(s, newlen);
    return s;
}

String Type implementation

above-mentioned String Types can only store string type data , So when assigning different data types ,string Yes, they will be treated differently .

1） When the stored data is of integer type ,String Type will use int Code to store . Specifically, use a 8 Bytes of Long Type to implement .

2） When the stored data contains strings ,String Type will use SDS Structure to store .

The structure is as follows

struct {
 
 flags;     //  Occupy  8  Bytes , Sign a , Mainly to identify that this is sdshdr A few , At present, only 3 position , also 5 Bit spare    
 len  ;     //  Occupy  4  Bytes , Express  buf  Used length of .    
 alloc;     //  Occupy  4  Bytes , Express  buf  Actual allocated length of , Generally greater than  len.
 buf ;      //  Byte array , Save actual data . To represent the end of a byte array ,Redis  It will automatically add one at the end of the array “\0”, This will take up extra  1  The cost of one byte .

}

In addition to recording the actual data ,String Type also requires extra memory space to record data length 、 Space use 、 My last visit 、 Metadata such as the number of references , therefore ,Redis Will use one RedisObject Structure to record the metadata , At the same time point to the actual data .

One RedisObject Contains 8 Byte metadata and a 8 Byte pointer , This pointer further points to the actual data of the specific data type or the real value .

edit

To save memory use , Yes Long and SDS Did different treatments ：

1） When the preservation is Long Type integer ,RedisObject The pointer in is directly assigned to integer data , So you don't have to have extra pointers to integers , Saves pointer space overhead .

2） When you save string data , And the string is less than or equal to 44 Byte time ,RedisObject The metadata in 、 Pointers and SDS It's a continuous memory area , This avoids memory fragmentation . This layout is also called embstr Encoding mode .

3） When you save string data , And the string is greater than 44 Byte time ,SDS The amount of data started to increase ,Redis I don't want to put SDS and RedisObject It's all laid out together , It will give SDS Allocate independent space , And point at SDS structure . This layout is called raw Coding mode .