Redis is an open source (BSD-licensed), in-memory data structure storage system that can be used as a database, cache, and messaging middleware. It’s easy to use Redis for almost any online project, whether you’re caching or messaging middleware, but most people probably don’t get down to the nitty grittier of Redis policy implementation.
Just recently, I encountered some bugs related to Redis in the project development. As I was not familiar with some implementations of the bottom layer, IT was difficult to solve them, so I decided to open such a series to record some learning notes on the structure and strategy of the bottom layer of Redis.
In the first part, we are going to start with the implementation of Redis’s five data structures and object types. The main content is as follows. You can also download the corresponding mind map from GitHub repository at the end of the article.
This article intends to introduce two data structures, SDS simple dynamic string and double-entailed linked list.
SDS simple dynamic string
As we all know Redis is implemented by C language as the underlying programming language, and C language also has the data structure of string, which is a character array and a null-terminated character array. This structure is too simple for Redis. So Redis implements SDS, a simple dynamic string structure, which is actually very similar to the implementation of ArrayList in Java.
Redis source code sdS. h file, there are five types of SDSHDR, they are:
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 */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* used */
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; /* used */
uint32_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
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 codeThe comment for sdshdr5 indicates that sdshdr5 is never used. The sdSHdr5 data structure is generally used to store strings of less than 32 characters, but this structure is no longer used. Sdshdr8 is recommended to store strings of even smaller lengths, because sdSHdr5 lacks two key fields and therefore does not have dynamic expansion operation. Once the pre-allocated memory space is used up, the memory needs to be reallocated and the data needs to be copied and migrated. In the actual production environment, the performance is still greatly affected, so this is discarded. However, some small keys are still stored in this structure.
The len field represents the current total length of the string, and the alloc field represents the total memory allocated for the current string (not including len and the memory allocated for the flags field itself). Because each structure in the pre-allocation time will allocate a section of memory space, mainly for the convenience of later expansion. The lower three digits of flags indicate the current SDS type; the higher five digits are useless. The lower three digits are as follows:
#define SDS_TYPE_5 0
#define SDS_TYPE_8 1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4
Copy the codeIn fact, Redis disables memory alignment for SDSHDR memory allocation, meaning that the memory addresses allocated for each field are tightly aligned, so string arguments in Redis are passed directly using char* Pointers.
SDSHDR memory allocation prevents memory alignment, so SDS [-1] refers to the memory address of the FLAGS field. The flags field can be used to get the type of the current SDS, and then the header field can be read to determine the related attributes of SDS.
Let’s talk about SDSHDR’s performance improvements over traditional C strings, as well as its convenience points.
First, for a traditional C string, I want to get the length of the string by at least O(n) traversing the array, whereas SDS only needs O(1) to get the len field.
Second, is also a very important design, if our initial allocation a string object, so if I want to additional content at the back of the string, once confined to the length of the array is initialized can’t modify, we need to assign at least one large enough array, and then a copy of the original string.
Each time SDSHDR allocates memory for an SDS, it allocates an additional portion of memory that is not currently in use. Generally, the extra memory is equal to the size of the current string. If it exceeds 1MB, the extra memory is 1MB. When the sdSCat method is executed, the program alloc-len is used to compare whether there is enough free memory left to allocate the appended content. If there is not enough natural memory to trigger a reallocation, and if there is enough unused memory left to lay down, the allocation is made without reallocation.
With this preallocation strategy, SDS reduces the number of memory reallocations required to grow strings N times in a row from a certain N to a maximum of N.
Finally, for regular C strings, it determines the end of the string by determining whether the current character is a null character, so your string must not contain even a null character, otherwise nothing after a null character will be read as a valid character. And for some special format requirement, you need to use the null character separation effect, so the traditional C string cannot be stored, and our SDS is not judge by null character string at the end, but rather through the len field of value judgment at the end of the string, so, SDS has binary safe this feature, That is, it can safely store binary data with special format requirements.
SDS is an improved VERSION of C string, compatible with the existing FUNCTION API in C language, but also through some means to improve the performance of some operations, worthy of reference.
Second, the linked list
Chain table this data structure, I believe you also not strange, there are many types, such as a singly linked list, two-way linked list, circular linked list, the list relative to an array, it is does not require continuous blocks of memory address, 2 it is to delete, and insert the time complexity is O (1) level, very efficient, but not nearly as an array of random access query mode.
Again, there is no best data structure, only the right data structure, such as the higher-level data structure, dictionary, which relies on linked lists to avoid hash collisions, but we’ll talk more about that later.
Redis implements a bidirectional linked list structure with the help of C language:
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
Copy the codeThe pre pointer points to the previous node, the next pointer points to the next node, and value points to the data object corresponding to the current node. Let me steal a diagram of the entire chain structure:
Although I can traverse the list through the first head node, there is a layer of structure encapsulated above redis that represents a list structure:
typedef struct list {
listNode *head;
listNode *tail;
void *(*dup)(void *ptr);
void (*free)(void *ptr);
int (*match)(void *ptr, void *key);
unsigned long len;
} list;
Copy the codeHead refers to the head node of the linked list, tail refers to the tail node of the linked list. Dup is used to copy the value of the node when the linked list is transferred. Generally, the equal sign is sufficient, but in some special cases, the node transfer function may be used. By default, this function can be assigned NULL to indicate node transfer using an equal sign. The free function is used to free the memory used by a node. If the default value is NULL, the redis zfree function is used to free the memory.
void zfree(void *ptr) {
#ifndef HAVE_MALLOC_SIZE
void *realptr;
size_t oldsize;
#endif
if (ptr == NULL) return;
#ifdef HAVE_MALLOC_SIZE
update_zmalloc_stat_free(zmalloc_size(ptr));
free(ptr);
#else
realptr = (char*)ptr-PREFIX_SIZE;
oldsize = *((size_t*)realptr);
update_zmalloc_stat_free(oldsize+PREFIX_SIZE);
free(realptr);
#endif
}
Copy the codeThe concept of memory alignment is involved here. For example, in a 64-bit operating system, one IO will fetch eight bytes of memory data. If a variable is across two eight-byte segments, the CPU will need to perform two IO to fetch the entire variable, introducing memory alignment. In order to ensure that the memory allocation of any variable does not occur in this way, the operation is to fill the memory bits that are useless, of course, this will cause memory fragmentation, but this is also a space-for-time strategy, you can also disable it.
The first part of the function is to make some judgments. If the total memory occupied by the data structure to which the pointer points is determined, the free function is directly called to free the memory, otherwise a calculation is required. Zmalloc in Redis appends a PREFIX_SIZE header block every time a memory is allocated. The PREFIX_SIZE header block is equal to the maximum addressing space on the current system. For example, on 64 cpus, PREFIX_SIZE takes up 8 bytes. And these 8 bytes are internal storage of the actual amount of memory occupied by the current data.
So in this case, moving the PTR pointer down is pointing to the head of the PREFIX_SIZE field, and then fetching the value that’s in there, which is the actual amount of memory that the current data structure is using, Finally, it passes in its own update_zmalloc_stat_free function to change the value of the used_memory memory record pointer, and finally calls free to free the memory, including the header.
Actually, we’re going to digression, but let’s move on to data structures, and if this isn’t clear, it doesn’t matter, we’ll talk about it later.
The match function is still a polymorphic implementation, only defined, and the implementation is up to you, if you choose not to implement it, to compare the values of two linked list nodes. Return 0 for unequal and 1 for equal.
The last len field describes the number of nodes in the list. This is the basic definition of a linked list in Redis. Add the list to the list structure and the final abstract graph in Redis looks like this, still stolen graph:
To sum up, we introduced a basic implementation of the linked list in Redis. To sum up, it is a double-ended linked list, that is, the time complexity of the nodes before and after the search for a node is O(1), and it is also a loopless linked list with Pointers to the first and last nodes. Besides the first, it also has three polymorphic functions. Replication, comparison and memory release between nodes need to be implemented by users themselves.
Focus on the public not getting lost, a programmer who loves to share.
Public number reply “1024” add the author wechat together to discuss learning!
All the case code materials used in each article are uploaded to my personal Github
Github.com/SingleYam/o…
Welcome to step on it!