Redis SDS principle

Reprinted from Redis SDS principle _m0_57015193 The blog of -CSDN Blog

---

redis Use c Language development , But it does not reuse c Native string implementation , I have built a new string implementation ：SDS（simple dynamic String）,SDS yes redis The default string implementation

SDS principle ：

struct sdshdr {
    //  Record buf The number of bytes used in an array , That is, the length of the used string 
    int len;
    //  Record buf The number of unused bytes in an array 
    int free;
    //  A character array , To hold strings 
    char buf[];
};

SDS and Character array comparison ：

C A character array	SDS
To get the length of the string, you need to traverse	Go straight back to
API unsafe , May cause buffer overflow	API Security , Will not cause buffer overflow
Memory reallocation must be called every time the length is modified	Not every time
Only text data can be saved	Can save binary
You can use all c Library function	Only a part can be reused

SDS adopt len Property record string length , Therefore, there is no need to traverse the entire character array

out of buffer ： The data on the physical address is overwritten

The main reason for buffer overflow is that its length is not recorded ： For two consecutive strings on the physical address , The current call strcat When the function links a new string , Later, the string data may be overwritten , Cause buffer overflow .SDS On each modification , First of all, according to the free Property to determine whether there is enough memory , Capacity will be expanded if not enough , Therefore, buffer overflow can be avoided .

For character arrays , Each expansion or contraction depends on memory reallocation , Otherwise, it may cause buffer overflow or memory leak . Due to memory reallocation, system calls need to be executed , Every time the efficiency is very low , In order to avoid expansion becoming redis Performance bottlenecks ,redis Space for time strategy is adopted to reduce the number of memory reallocation ：

Space preallocation ：SDS At each expansion , Allocate more memory . The length after expansion is less than 1M, Redistribute your own length , Greater than 1M, redistribution 1M
Inert space release ： Do not release memory immediately when shrinking , Record first and then free In the attribute , Convenient for subsequent use
SDS The corresponding function is provided to reclaim memory , No memory leakage due to the release of inert space

C Due to various specifications and restrictions, character arrays cannot store binary data , and SDS There are no restrictions on character data , Read and write completely , It won't stop because of an empty string , Therefore, binary data can be saved

SDS Still follow c The property that a character array ends with an empty string , The advantage of doing so is SDS You can reuse a part directly C String function .

It should be noted that ,redis Not all strings in use SDS, For the return value , Log type data still adopts character array