We talked about Redis data types and application scenarios, and linked to this article is what Every Programmer should know about Redis. This article will cover the following contents:
- The underlying implementation of the Srting type in Redis
- By learning the underlying implementation principle of String, we can learn which low-level optimization methods
- Redis about the String command
We know that Redis is implemented by C language. Before introducing the implementation of Sring type, let’s review the string type of C language. A string in C is an array of null-terminated characters. For details, see the following figure:
Srting type in Redis
Instead of using C strings directly, Redis builds its own set of abstract types called Simple Dynamic Strings, or SDS.
If you look at the Redis source code, you’ll find a structure like this:
- Len records the number of bytes already used in the BUF array, which is the length of the string held by the SDS type.
- Free records the number of unused bytes in the BUF array
- Buf is an array of bytes used to hold strings
From the above structure we can see:
The String type of Redis is encapsulated into SDS structure, which reflects the algorithm idea of exchanging space for time. Some space is sacrificed for faster query efficiency. For example, len 5 in the structure indicates that the SDS holds a five-byte string, and the time complexity of O(1) can be used to query the result.
Redis is positioned as a caching layer on top of the database layer, so efficiency should be considered everywhere. In fact, cache itself is also the embodiment of the idea of using space for time.
Fixed C string buffer overflow problem. C strings do not record string lengths. Therefore, when C strcat is used to concatenate strings, the length of the concatenated string exceeds that of the string applied for by itself, resulting in buffer overflow. SDS doesn’t have that problem
Space preallocation: Allocating a certain amount of space in advance when applying for space. When the space is not enough, you can apply for a larger space through the API provided by SDS.
Lazy free space: when the requested space is no longer in use, instead of immediately freeing the space, the free property in SDS records the number of bytes for future use
Binary security: Packaged SDS addresses binary security issues, so various types of data can be cached in Redis String. The SDS API treats the data stored in the BUF array by SDS as binary, without limiting, filtering, or making assumptions about the data as it was written and as it was read.
To sum up what has been said above, there are two core ideas. The first is the realization of SDS; The second is the idea of space for time. There will also be articles devoted to the specific application of space for time and time for space.
Second, the underlying optimization method learning
What low-level optimization methods can we learn from this introduction? The idea of space for time was mentioned repeatedly above, and I think most developers have used it at some point or another in their actual projects. The design idea of Redis and Memcache is the concrete embodiment of this idea. In addition to Redis, MySQL also has a lot of use, such as index is one of them. This kind of design also exists in operating system and computer architecture design.
In addition to space swap time, memory pre-allocation and lazy release are also good optimization methods. For example, in the Dynamic mode of PHP-FPM process management, N Worker processes are generated in advance when it is started. When the number of visits increases, the number of Worker processes can be increased. When the number of visits decreases, these increased Worker processes can be destroyed or retained.
In addition to the above methods, there are many methods worth learning and reference, I will not list one by one here. If this article is helpful to you, please forward it to your friends so that you can learn and grow together. Feel free to point out any mistakes or ambiguations in the comments section. Everyone’s support is my motivation, I hope we can progress together!
