directory

preface

introduce

advantages

Memory allocation principles and lazy release

preface

From today we will learn the source of Redis, think about a little excited.

High energy warning ahead, non-combatants evacuate quickly.

But how can we lose it, withdraw what ah, said to do, dead knock source code, this code is also written by people, he can also whole out of what unearthly moxa.

Another but come, redis bottom is written in C language, if you know nothing about C language, that or forget it, the front is waiting for a mountain. Wall crack recommended to know about C. MMMM, fortunately I will C, ha ha ha, after all, he is open even code of the road of the little brother.

All right, enough bullshit. Let’s get down to business.

​

introduce

Instead of using C’s traditional string representation directly (an array of characters ending in an empty string), Redis constructed something called simple dynamic String SDS.

The String data structure we saw earlier is implemented with SDS at the bottom.

SDSHDR (SDS header structure is as follows) :

struct sdshdr { int len; // The length of space occupied in buf int free; Char buf[]; // Initialize the data space allocated by SDS, and be Flexible array member};Copy the code

Here’s an example:

We set a string named str1 with the value redis, and its structure in memory is roughly as follows:

​

Len is 5, which means that the SDS is 5 bytes long.

Free is 2, which means that the SDS has 2 bytes of unused space.

Buf allocates (len+1+free) bytes for an array of char[]. The first len bytes hold redis, the next byte holds ‘\0’, and the remaining free bytes are unused.

advantages

1. Binary security.

Because the traditional C language string conforms to the ASCII encoding, and its characteristic is zero, so when reading a string, as long as the ‘\0’, it is considered to have reached the end. The problem is that if you save binary files such as images or videos, they will be forcibly truncated and the data will be incomplete.

Now you can’t tell if the string is finished by stopping at zero, but you can now compare len with the length of buf[]. If len+1 is equal to the length of buf, the string is finished.

2. The time complexity of the operation to obtain the string length is O(1).

The traditional way to get the length of a C string is to iterate over the length of the string and return it if it hits zero. The time complexity is O(n).

The len member in the SDS header keeps the length of the string and its time complexity is O(1).

3. Prevent cache overflow.

Since the free member in the SDS header records the unused amount of buF character data, append should first determine whether free is sufficient. If so, add characters directly; if not, expand memory first and then add strings.

Memory allocation principles and lazy release

Memory will expand, but not arbitrarily. It’s like Ultraman wants a little monster, a flash of light, but if it’s the ultimate boss, you have to fight hard, pay attention to strategy, there’s a good chance you’ll call for help outside the venue.

If the SDS table header LEN member is less than 1MB (1024X1024), the same length of unused space is allocated.

If len member of SDS table header is greater than or equal to 1MB (1024X1024), 1MB of unused space is allocated.

No proof, Trey. Code it.

SDS sdsMakeRoomFor(SDS s, size_t addlen) { size_t free = sdsavail(s); Size_t len, newlen; // Free is long enough to return without extensionif (free >= addlen) returns; Len = sdslen(s); Sh = (void*) (s-(sizeof(struct SDSHDR))); Newlen = (len+addlen); // New length after expansion // space pre-allocation //#define SDS_MAX_PREALLOC (1024*1024) // The maximum length of pre-allocated memory is 1MBif(newlen < SDS_MAX_PREALLOC) // If the new length is less than the maximum prealloc length, multiply the extended length by 2 newlen *= 2;elsenewlen += SDS_MAX_PREALLOC; Newsh = zrealloc(sh, sizeof(struct SDSHDR)+newlen+1); // Get the address of the new extended spaceif (newsh == NULL) 
    returnNULL; newsh->free = newlen - len; // Update the unused space free for the new spacereturn newsh->buf;
}
Copy the code

If the new string is much shorter than the old one, does it have to be reclaimed?

Looking at the reset code, it’s clear that instead of reclaiming the extra length, the program uses free to store the strings for future use.

Void SDSHDR *sh = (void*) (s-(sizeof(struct SDSHDR))); sh->free += sh->len; Len = new free sh->len = 0; // The used space becomes 0 sh->buf[0] ='\ 0'; // string null}Copy the code

This is the source of SDS, if you want to see his specific steps for each operation, you will see the specific files SDS.c and SDS.H.

Emmmm, I can’t.

​

Long press the qr code below, immediate attention [learning Java little sister] receive more learning materials oh!