Why does the String type have a large memory overhead?
We saved the information of 100 million pictures, using about 6.4GB of memory, and a record of picture ID and picture storage object ID used an average of 64 bytes.
But the problem is that the records of a set of picture IDs and their storage object IDs actually only need 16 bytes.
Let’s analyze it. Both the picture ID and the picture storage object ID have 10 digits, and we can use two 8-byte Long types to represent these two IDs. Because the 8-byte Long type can represent a maximum value of 2 to the 64th power, it must be able to represent 10 digits. But why does the String type use 64 bytes?
In fact, in addition to recording actual data, the String type also requires additional memory space to record information such as data length and space usage, which is also called metadata. When the actual saved data is small, the metadata space overhead will be relatively large, which is a bit “overwhelming”.
So, how exactly does the String type store data? Let me explain.
When you save a 64-bit signed integer, the String type will save it as an 8-byte Long type integer, which is usually called int encoding.
However, when the data you save contains characters, the String type will be saved with a Simple Dynamic String (SDS) structure, as shown in the following figure:
-
buf: byte array, save the actual data. In order to indicate the end of the byte array, Redis will automatically add a “\0” at the end of the array, which will take up an additional 1 byte of overhead.
-
len: 4 bytes, indicating the used length of buf.
-
alloc: It also occupies 4 bytes, indicating the actual allocation length of buf, which is generally greater than len.
It can be seen that in SDS, buf stores actual data, while len and alloc themselves are actually additional overhead of the SDS structure.
In addition, for the String type, in addition to the additional overhead of SDS, there is also an overhead from the RedisObject structure.
Because Redis has many data types, and different data types have the same metadata to record (such as the time of last access, the number of references, etc.), Redis will use a RedisObject structure to uniformly record these metadata data, while pointing to the actual data.
A RedisObject contains 8-byte metadata and an 8-byte pointer. This pointer further points to the actual data location of the specific data type, such as pointing to the memory address where the SDS structure of the String type is located. You can take a look at the schematic diagram below. Regarding the specific structural details of RedisObject, I will introduce them in detail in later courses. Now you only need to understand its basic structure and metadata overhead.
In order to save memory space, Redis has also specially designed the memory layout of Long type integers and SDS.
On the one hand, when the Long type integer is saved, the pointer in RedisObject is directly assigned to the integer data, so that there is no need for an additional pointer to point to the integer, which saves the space overhead of the pointer.
On the other hand, when the string data is saved and the string is less than or equal to 44 bytes, the metadata, pointers, and SDS in RedisObject are a continuous memory area, so that memory fragmentation can be avoided. This layout is also known as embstr encoding.
Of course, when the string is larger than 44 bytes, the amount of data in SDS begins to increase. Redis no longer arranges SDS and RedisObject together, but allocates independent space for SDS and uses pointers to point to the SDS structure. This layout is called raw encoding mode.
In order to help you understand the three encoding modes of int, embstr and raw, I drew a diagram as follows:
Ok, knowing the extra metadata overhead that RedisObject contains, we can now calculate the memory usage of the String type.
Because the 10-digit picture ID and picture storage object ID are Long type integers, they can be stored directly with int-encoded RedisObject. The metadata part of each int encoded RedisObject occupies 8 bytes, and the pointer part is directly assigned an 8-byte integer. At this point, each ID will use 16 bytes, adding up to a total of 32 bytes. But where did the other 32 bytes go?
As I said in Lecture 2, Redis will use a global hash table to save all key-value pairs, and each item in the hash table is a dictEntry structure, which is used to point to a key-value pair. There are three 8-byte pointers in the dictEntry structure, which point to the key, value and the next dictEntry respectively. The three pointers are 24 bytes in total, as shown in the figure below:
However, these three pointers are only 24 bytes, why do they occupy 32 bytes? This is about the memory allocation library jemalloc used by Redis.
When jemalloc allocates memory, it will find a power of 2 that is larger than N but closest to N as the allocated space according to the number of bytes N we apply for, which can reduce the number of frequent allocations.
for example. If you apply for 6 bytes of space, jemalloc will actually allocate 8 bytes of space; if you apply for 24 bytes of space, jemalloc will allocate 32 bytes. So, in the scenario we just mentioned, the dictEntry structure occupies 32 bytes.
Well, here, you should be able to understand why it takes 64 bytes to save the image ID and image storage object ID with the String type.
You see, the effective information is only 16 bytes, but when it is stored in String type, it needs 64 bytes of memory space, and 48 bytes are not used to save the actual data. Let’s convert it, if there are 100 million pictures to be saved, then 100 million picture ID records will require 6.4GB of memory space, of which 4.8GB of memory space is used to save metadata, and additional memory space overhead very big. So, is there a more memory-efficient way?
What data structure can save memory?
Redis has an underlying data structure called a compressed list (ziplist), which is a very memory-efficient structure.
Let’s first review the composition of the compressed list. There are three fields zlbytes, zltail and zllen in the table header, respectively indicating the length of the list, the offset of the end of the list, and the number of entries in the list. There is also a zlend at the end of the compressed list, indicating the end of the list.
The reason why the compressed list can save memory is that it uses a series of consecutive entries to save data. The metadata of each entry includes the following parts.
-
prev_len, indicating the length of the previous entry. prev_len has two values: 1 byte or 5 bytes. When the value is 1 byte, it means that the length of the previous entry is less than 254 bytes. Although the range of values that can be represented by a value of 1 byte is 0 to 255, the default value of zlend in the compression list is 255, therefore, 255 is used by default to represent the end of the entire compression list, and other places indicating the length can no longer be used 255 is the value. Therefore, when the length of the last entry is less than 254 bytes, the value of prev_len is 1 byte, otherwise, the value is 5 bytes.
-
en: Indicates its own length, 4 bytes
-
encoding: Indicates the encoding method, 1 byte
-
content: save the actual data.
These entries will be placed in memory one by one, and there is no need to use additional pointers for connection, which can save the space occupied by pointers.
Let’s take saving the image storage object ID as an example to analyze how the compressed list saves memory space.
Each entry saves an image storage object ID (8 bytes). At this time, the prev_len of each entry only needs 1 byte, because the length of the previous entry of each entry is only 8 bytes, which is less than 254 bytes. . In this way, the memory size occupied by the storage object ID of a picture is 14 bytes (1 + 4 + 1 + 8=14), and 16 bytes are actually allocated.
Redis implements collection types such as List, Hash, and Sorted Set based on compressed lists. The biggest advantage of this is that it saves the overhead of dictEntry. When you use the String type, there is a dictEntry for a key-value pair, which takes 32 bytes of space. But when the collection type is used, one key corresponds to one collection of data, which can save a lot more data, but only one dictEntry is used, which saves memory.
This scheme sounds good, but there is still a problem: when using the collection type to store key-value pairs, a key corresponds to the data of a collection, but in our scenario, a picture ID only corresponds to the storage object ID of a picture , how should we use collection types? In other words, in the case where a key corresponds to a value (that is, a single-value key-value pair), how should we use a collection type to store this single-value key-value pair?
How to save single-value key-value pairs with collection type?
When saving single-value key-value pairs, a secondary encoding method based on the Hash type can be used. The secondary encoding mentioned here is to split a single-valued data into two parts, the first part is used as the key of the Hash set, and the latter part is used as the value of the Hash set. In this way, we can save the single-valued data to the Hash It’s in the collection.
Taking the picture ID 1101000060 and the picture storage object ID 3302000080 as an example, we can use the first 7 digits of the picture ID (1101000) as the Hash type key, and use the last 3 digits of the picture ID (060) and the picture storage object ID as the Hash type respectively The key and value in the value.
According to this design method, I inserted a set of records of picture ID and its storage object ID in Redis, and checked the memory overhead with the info command. I found that after adding a record, the memory usage only increased by 16 bytes. As follows:
127.0.0.1:6379> info memory # Memory used_memory: 1039120 127.0.0.1:6379> hset 1101000 060 3302000080 (integer) 1 127.0.0.1:6379> info memory # Memory used_memory:1039136
When using the String type, each record needs to consume 64 bytes, but this method only uses 16 bytes, and the memory space used is 1/4 of the original, which meets our need to save memory space.
However, you may also have doubts: “Does the secondary encoding have to use the first 7 digits of the picture ID as the key of the Hash type, and the last 3 digits as the key in the Hash type value?” In fact, the secondary encoding method uses The length of the ID is particular.
So, when does the Hash type underlying structure use a compressed list and when does it use a hash table? In fact, the Hash type sets two thresholds for storing data in a compressed list. Once the threshold is exceeded, the Hash type will use a hash table to store data.
These two thresholds correspond to the following two configuration items:
-
hash-max-ziplist-entries: Indicates the maximum number of elements in the hash set when saved in a compressed list.
-
hash-max-ziplist-value: Indicates the maximum length of a single element in the hash collection when stored in a compressed list.
If the number of elements we write in the Hash collection exceeds hash-max-ziplist-entries, or the size of a single element written exceeds hash-max-ziplist-value, Redis will automatically change the implementation structure of the Hash type from Compressed list to hash table.
Once converted from a compressed list to a hash table, the Hash type will always be stored in the hash table and will not be converted back to the compressed list. In terms of saving memory space, hash tables are not as efficient as compressed lists.
In order to make full use of the compact memory layout of the compressed list, we generally need to control the number of elements stored in the Hash collection. Therefore, in the secondary encoding just now, we only use the last 3 digits of the picture ID as the key of the Hash set, which ensures that the number of elements in the Hash set does not exceed 1000. At the same time, we set hash-max-ziplist-entries is 1000, so that the Hash collection can always use the compressed list to save memory space.
Summary
In the past, we thought that String is a “panacea” that can be used in any occasion. However, when the stored key-value pair itself does not occupy much memory space (such as the picture ID and picture storage object ID mentioned in this lesson), The metadata overhead of the String type dominates, including the memory overhead of the RedisObject structure, SDS structure, and dictEntry structure.
In this case, we can use compressed lists to save data. Of course, when using a collection type like Hash to save the data of a single-value key-value pair, we need to split the single-value data into two parts, which are used as the key and value of the Hash collection, just like the two-level encoding in the case just now. Image ID, I hope you can use this method in your own scene.