I hope everyone can really read the source code, to understand firsthand knowledge. Instead of just going to see each public number copy to copy a few articles, some or even wrong.
^_^
How come so many people say that the magic reading problem in mysql is solved by MVCC?
SDS string: The name is simple dynamic string, but it is anything but simple. If all you know is that he can dynamically expand, that’s far from it.
Dynamic object header
First, the SDS object header definition and implementation of the basic string functions are in the SDS.h header file. A total of 5 SDS header formats are defined as follows:
/* 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; /* 3 lsb of type, and 5 msb of string length */
char buf[];
};
struct __attribute__(((packed__)) sdshdr8 {
uint8_t len; /* used */
uint8_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
charbuf[]; }; .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 codeWhere sdshdr5 is not used according to the comments, we ignore it.
The only other structure types that differ are len, which represents length, and alloc, which records allocated memory.
Unalignment of bytes
Again, notice the __attribute__ ((__packed__)) modifier on the structure, which cancellations byte alignment.
To verify this, I wrote the following little code:
struct packed_test_a
{
char i;
uint32_t j;
};
struct __attribute__(((packed__)) packed_test_b
{
char i;
uint32_tj; }; .struct packed_test_a a;
struct packed_test_b b;
a.i = 'a';
b.i = 'b';
a.j = 1u;
b.j = 2u;
printf("%d \n".sizeof(a)); / / 5
printf("%d \n".sizeof(b)); / / 8
Copy the codeIt’s not enough to just look at sizeof, so let’s use GDB to debug:
1 Type the breakpoint at the location of the first printf and run the r command to the breakpoint (line 37).
Thread 2 hit Breakpoint 1, main (argc=1, argv=0x7ffeefbff7d8)
at packed_test.c:37
37 printf("%d \n".sizeof(a));
Copy the code2 Check the memory at variable A, using x/ 24xb&a
0x7ffeefbff798: 0x61 0x01 0x00 0x00 0x00 0x00 0x00 0x00.Copy the code3 Check the memory at variable b, using x/ 24xb&b
0x7ffeefbff790: 0x62 0x00 0x00 0x00 0x02 0x00 0x00 0x00.Copy the codeIn this way, it is obvious that on variable A with an __attribute__ ((__packed__)) modifier, the data a.i = 0x61 and a.j = 0x01 are stored consecutively.
In variable B, b.I = 0x62 and B.j = 0x02 are filled with 3 bytes of 0x00 data for alignment.
Select the appropriate object header based on the length
create
Take a look at the function that creates the SDS string: sdsnewlen.
The function signature is as follows:
sds sdsnewlen(const void *init, size_t initlen)
Copy the code- Step one, use
s_mallocAllocate enough memory. That is, the length of the object header + the initial length of the string + 1(C string terminator placeholder).
sh = s_malloc(hdrlen+initlen+1);
Copy the code-
The second step is to initialize the allocated memory and use memset to batch set zero values.
-
Third, set the variable Pointers s, FP.
s = (char*)sh+hdrlen;
fp = ((unsigned char*)s)- 1;
Copy the code
Here, a little plot twist: * FP points to *s-1. Where *s points to the start address of the data area, *s-1 is sdS.flags.
- Step 4 set the object header properties according to the type:
switch(type) {
...
case SDS_TYPE_8: {
SDS_HDR_VAR(8,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break; }... }Copy the code- Step 5: Set the initial value in the data area
memcpy(s, init, initlen);
Copy the code- Finally, wrap things up
s[initlen] = '\ 0';
return s;
Copy the codeNote: The actual pointer returned here is*s. This is the starting address of the SDS string data area.
capacity
Here we go straight to the sdsMakeRoomFor function.
If the capacity is smaller than 1MB, the capacity is directly multiplied by 2. Otherwise, the capacity is expanded by 1MB. Yeah, it comes from here.
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
Copy the codeThen, it will judge whether the original object header is consistent with the expanded object header to decide whether to expand directly or… Removable nipple?
hdrlen = sdsHdrSize(type);
if (oldtype==type) {
newsh = s_realloc(sh, hdrlen+newlen+1);
if (newsh == NULL) return NULL;
s = (char*)newsh+hdrlen;
} else {
/* Since the header size changes, need to move the string forward, * and can't use realloc */
newsh = s_malloc(hdrlen+newlen+1);
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);
}
Copy the codeThanks to Redis’s single-threaded model, the code is also extremely simple: allocate sufficient length, copy and free the original memory.
Shrinkage capacity
The function is the same as expansion, see sdsRemoveFreeSpace.
Note that the scaling function returns the unallocated space in the SDS. The value of the string itself does not change.
/* If the type is the same, or at least a large enough type is still * required, we just realloc(), letting the allocator to do the copy * only if really needed. Otherwise if the change is huge, we manually * reallocate the string to use the different header type. */
if (oldtype==type || type > SDS_TYPE_8) {
newsh = s_realloc(sh, oldhdrlen+len+1);
if (newsh == NULL) return NULL;
s = (char*)newsh+oldhdrlen;
} else {
newsh = s_malloc(hdrlen+len+1);
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);
}
Copy the codeWhen the original type is the same as the target type, or the original type is above sdSHdr8, the type is not replaced, but only reassigned to an exact capacity using s_realloc.
Notice the presence of an S [-1] in the code? Can an array index be negative? That’s weird, right? Hold on
Storage structure
By looking at the structure definition of the SDS string, we can draw its memory storage structure (we use sdSHdr8 as an example) :
Except for SDSHDR5, the storage structure of the other four is the same.
Note that len,alloc,flags,*buf must be tightly connected in memory because the __attribute__ ((__packed__)) modifier is added to the structure.
Those “dirty” operations in the code
Negative array subscripts
If you take a closer look at the code, you’ll notice that there are plenty of ways to write this:
unsigned char flags = s[- 1];
Copy the codeIn some languages, a negative index of an array indicates the number of elements to access. But C, the top of the contempt chain, is a different story
In C, an array is a pointer, and s[-1] has the same effect as *s-1.
So, we know that s[-1] calls the flags property in the structure.
So why use it this way?
Because you’ve seen the function that creates SDS. We know that after creation, the exposed pointer only points to the location of the data area, namely the *buf property.
So, let’s start with this question: why is only the address of the data area directly returned, and not the entire SDS header address
*bufIs a native C array on which all string-related functions provided in the STL can be used directly.sdsThe head is dynamic, just onesdsYou can’t access any properties because you don’t know how the data is currently distributed.
So, if we return a pointer to an address between flags and *buf.
Since we know that flags is fixed length, we can retrieve the entire flags data by moving one char forward. And once we have flags we can know the distribution of the data in the header of the object and access the other len alloc properties.
The compiler preprocesses macros
Now let’s look at how to fetch the other fields in the header now that we have the *s pointer and flags.
How about continuing to use negative subscripts: -(1+1), -(1+1+1) and so on, that’s really completely unreadable.
Let’s look at the len method:
static inline size_t sdslen(const sds s) {
unsigned char flags = s[- 1];
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5:
return SDS_TYPE_5_LEN(flags);
case SDS_TYPE_8:
return SDS_HDR(8,s)->len; .case SDS_TYPE_64:
return SDS_HDR(64,s)->len;
}
return 0;
}
Copy the codeAs you can see, the same SDS_HDR macro is used for different types (except SDS_TYPE_5), except that the first argument is different.
Take a look at his macro definition:
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
Copy the codeIt’s just one line of code, and there’s a symbol ## : another type of preprocessor macro. Two hacks, called connectives, join two tokens into one.
For example, SDS_HDR(8,s), after being preprocessed by the compiler, would look like this:
((struct sdshdr8 *)((s)-(sizeof(struct sdshdr8))))
Copy the codeIsn’t that amazing? Macro parameters also become part of the code itself.
So, let’s see what this code does:
Sizeof (struct sdshdr8), sizeof(struct sdshdr8), sizeof(struct sdshdr8), sizeof(struct sdshdr8
Then, the first half: is a cast, because we have the head pointer to the SDS, so we just need to cast, and then we can do whatever we want.
conclusion
Simple dynamic strings: As one of the most photographed data structures in Redis, it is anything but simple. Not only the length has been dynamically expanded, but the head has also been dynamically expanded in order to maximize the use of space.
Also, the header stores the length of the current string, which is obvious: even though *buf refers to a standard C string, using the strlen function to find the length would have to traverse the entire string.
If you store extra, it’s a whole different story.
And, thanks to Redis’s single-threaded system, complex operations become incredibly simple.