What is the data structure of redis SDS?

1 Preface

Redis's string data structure SDS (Simple Dynamic String), which means a simple dynamic string, the literal meaning is smiple, which means simple, easy to operate, and users can quickly Just understand it and get started, without worrying about the internal implementation of redis; Dynamic refers to dynamic expansion, and the table can automatically allocate memory space dynamically; String represents a string, which is not difficult to understand.

二 SDS structure

2.1 redis SDS data structure

The data structure before redis3.2 is as follows;

struct sdshdr {
    unsigned int len;   
    unsigned int free;  
    char buf[];         
};

• len represents buf The length of space that has been used in (buffer);

• free represents the unused length in buf;

• buf[] represents the buffer Array, storing characters;

2.12 redis buffer structure

A more vivid storage image is as follows. The actual size in buf is 11 (len free 1), where Used space len = 5, unused space free = 5; reserved space character \0 occupies one bit; when we store a string zxzxz in redis, the memory has been allocated to us space, and the memory space that can be used later; if it is C language, then to get a zxzxz character length, you need to traverse the entire character array and end after encountering \0 (C language uses \0 to distinguish strings in the memory space). Calculate the length of a string. However, redis only needs one sdslen (non-c language readers do not need to worry about this kind of API) to calculate the length of the string; from an algorithmic perspective, redis obtains characters at one time The string length is O(1), and the c language is O(N), so redis is much faster;

2.2 redis space allocation strategy

Secondly, through the above It can be found in the figure that a string zxzxz is stored, and its length is 5, so the space used is 5, and \0 occupies 1; the reason is that when the redis string storage size is less than 1MB, any string is stored , its free size is always the same as its own size; when the string size is greater than 1MB, it allocates a free size of 1MB, which is called space preallocation strategy; If it is C language, you need to calculate the current The length of the string in buf, then calculates the length of the string to be appended, and then allocates the space; therefore, the speed of redis is quite fast, compared to c operating memory space;

c language operates memory space When appending a string, you need to constantly calculate the size and allocate the space size when appending the string. If it is not allocated, the appended string may overwrite the string that has been stored in the memory space; such as memory space storagezzz \ 0kkk\0; When storing zzz, it occupies 3 bits, plus 1 bit of unallocated space. If a ggg is appended to the zzz string, the original data will be lost without calculating the allocated space. Becomes zzzggg\0k\0, it is very intuitive to find that the memory overflows, the first string covers part of the second string;

So the operation content space of redis It is to prevent memory overflow and can store binary data such as pictures and videos. If the storage is operated by C language, a \0 in the binary file may cause memory leaks, buffer overflows, etc., so C language generally only operates text files;

The above is the detailed content of What is the data structure of redis SDS?. For more information, please follow other related articles on the PHP Chinese website!