I once saw a case where a team needed to develop a picture storage system that could quickly record the ID of the image and the ID of the image storage object, and also needed to be able to quickly find the ID of the image storage object based on the ID of the image. Let’s assume that the image ID and image storage object ID are represented by 10 digits. For example, the ID of the image is 1101021043, and the ID of the corresponding image storage object is 2301010051. It can be seen that the image ID and the image storage ID are exactly in one-to-one mapping, which is a typical key-value form. So the first thing to think about is using the String type directly to hold data. Save the image ID and the image storage ID as the key and value of the key-value pair, respectively. However, with the increasing amount of data stored, the memory usage of Redis also increased rapidly. As a result, the response of large memory Redis instances was slow due to RDB generation. Obviously String is not a good choice,

Is there any way to reduce memory consumption?

A data structure of type String

First, we need to understand why strings use so much memory to store data. In our case, since the image ID and the image store object ID are both 10 bits, we can represent the ids as two 8-byte longs. So a record of a set of image ids and their stored object ids is actually only 16 bytes. However, the Redis memory analysis shows that a set of image ids and their storage object ids take up 64 bytes, so why does a String use 64 bytes? In addition to recording the actual data, strings require additional memory space to record the length of the data, space usage information, and so on. This information is also called metadata. When the actual data stored is small, the space cost of metadata is significantly larger. Let’s first look at how String holds data. When you save a 64-bit signed integer, the String will save it as an 8-byte Long, also known as the int encoding. However, when you save data that contains characters, the String type is stored as a simple dynamic String structure (SDS). As shown in the figure below:

  • Len: 4 bytes, indicating the used length of BUF.
  • Alloc: Four bytes, indicating the length of buF allocated. Generally, the length is larger than len.
  • Buf: Byte array that holds the actual data. To indicate the end of an array, Redis automatically adds a “\0” to the end of the array.

As you can see, in an SDS structure, in addition to the BUF that holds the actual data, there is the overhead of len and alloc for additional metadata. In addition to the SDS overhead for String, there is also the overhead of a structure called RedisObject. Since Redis has many data types, different data types have the same metadata to record (such as last access time), So Redis uses a structure called RedisObject to record these metadata. A RedisObject contains an 8-byte metadata and an 8-byte pointer to the memory address where the data is located, such as the SDS structure of String. As shown in the figure below:

In order to save memory space, Redis specially designed the memory layout of Long integer and SDS. On the one hand, when saving Long integers, the pointer in RedisObject is directly assigned to integer data, so there is no additional pointer to the integer, saving the pointer space overhead. On the other hand, when the string data is stored, and the string is 44 bytes or less, the metadata, Pointers, and SDS in the RedisObject are contiguated memory areas, thus avoiding memory fragmentation. This layout is also known as embSTR encoding. When the string is larger than 44 bytes, the amount of data in the SDS starts to increase. Redis no longer arranges the SDS and RedisObject together, but allocates a separate space for the SDS and points to the SDS structure. This layout is known as the RAW encoding mode. As shown in the figure below:

Now let’s calculate the memory usage of a pair of image ids and image storage object ids. Since the 10-bit image ID and image storage object ID are Long integers, they can be stored directly as an int encoded RedisObject. The corresponding RedisObject metadata part is 8 bytes, and the pointer part is directly assigned to an 8-byte integer. At this point, each ID will use 16 bytes for a total of 32 bytes. But where did the other 32 bytes go?

Since Redis uses a global hash table to hold all key-value pairs, each entry in the hash table is a structure called dictEntity that points to a key-value pair. DictEntity consists of three 8-byte Pointers to the key, value, and next dictEntity. See the figure below.

The memory allocation library used by Redis is Jemalloc. When allocating memory, Jemalloc will, according to the applied number of bytes N, find a power of 2 which is larger than N and closest to N as the allocated space. So if you apply for a 24-byte dictEntity, you actually allocate 32 bytes. By now, you can see why the String used to store the image ID and the image store object ID takes 64 bytes. A valid piece of information is only 16 bytes. When stored as a String, it takes up 64 bytes of memory. There are 48 bytes for metadata information, which is a huge waste of memory. So is there a way to save more memory?

Use compressed lists to save memory

Redis has a structure called a compressed list, which is very memory efficient. Let’s review the composition of the compressed list first. The table header has three fields, ZLBytes, zllEN, and zltAIL, which represent the length of the list, the offset at the end of the list, and the number of entries in the list, respectively. The compressed column table has a ZLend at the end of the table, indicating the end of the list. See the figure below.

Since the compressed list uses a series of entries to store data, these entries are placed in memory one by one, and no additional Pointers are needed to connect them, thus saving the space occupied by Pointers. Each entry consists of the following parts.

  • Pre_len: indicates the length of the previous entry. The prev_len value can be 1 byte or 5 bytes. If the length of the previous entry is less than 254 bytes, the prev_len value is 1 byte; otherwise, the prev_len value is 5 bytes.
  • Len: indicates the length, which is 4 bytes.
  • Encoding: Indicates the encoding mode, which is 1 byte.
  • Content: Saves the actual data.

Suppose we use the entry to store the image storage object ID(8 bytes). In this case, the prev_len of each entry should only take 1 byte, because the length of the previous entry is less than 264 bytes. Thus, the memory size of an image object ID is 14 (1+4+1+8) bytes, and 16 bytes are actually allocated.

Redis implements List, Hash, and Sorted Set collection types based on compressed lists. The greatest benefit of this is the memory overhead of dictEntity. For String, a key-value pair has a dictEntity, which can occupy 32 bytes. For collection types, a key that corresponds to a lot of data takes up only one dictEntity, which saves memory.

How to store single-valued key-value pairs of data using collection types

When storing data for single-valued key-value pairs, we can use secondary encoding based on the Hash type. Secondary encoding refers to splitting single-valued data into two parts. The first part is used as the Hash key and the second part is used as the Hash value. For example, the ID of the image is 1101021043 and the ID of the corresponding image storage object is 2301010051. The first seven bits (1101021) of the image ID are used as the Hash key. The last three bits (043) and the image storage object whose ID is 2301010051 are used as the Hash key and value. We use this design to insert a record into Redis, which takes only 16 bytes, so we save a lot of space compared to the 64 bytes we use with String. Finally, let’s consider why the first 7 bits of the image ID are used as the Hash key and the last 3 bits as the Hash key. In The Redis storage structure, we have introduced two underlying implementation structures of the Redis Hash type, namely compressed list and Hash table. The Hash type sets two thresholds for storing data in a compressed list. Once the thresholds are exceeded, the Hash type stores the data in a Hash table. The two thresholds correspond to the following two configuration items:

  • Hash-max-ziplist-entries: indicates the maximum number of elements in a hash set when stored as a compressed list.
  • Hash-max-ziplist-value: indicates the maximum length of a single element in the hash set when saved as a compressed list.

Hash tables are not as efficient as compressed lists in terms of memory savings. We use the last three bits as the Hash key so that the number of elements in the Hash set does not exceed 1000, and we set hash-max-ziplist-entries=1000 to ensure that the underlying Hash type is a compressed list.

Well, that’s all for today’s introduction. More core knowledge, please pay attention to the public number programmer senior.