Redis base data type

Redis has five basic data type structures: string, list, hash, set, and zset.

All data structures of Redis use a unique key string as the name, and then obtain the corresponding value data through the unique key. Different types of data structures are different in the structure of value, that is to say, no matter what data type, their key is a string, representing the identification of the corresponding data.

String (string)

The string structure is used to store some fixed information, such as user information. The user information is serialized into a JSON string in the system, and then stored in Redis according to the user ID as the key and json string as the value.

In the subsequent process, user information can be obtained through ID in Redis to avoid frequent access to the database.

Internal implementation

Unlike strings in Java, strings are immutable. In Redis, strings are mutable. The implementation of the internal structure is similar to ArrayList in Java, which reduces the frequent allocation of memory by pre-allocating redundant space.

As shown in the following figure, the capacity allocated to the character string is larger than len. If the character string is smaller than 1MB, the capacity is doubled. If the character string is larger than 1MB, the capacity is increased by 1MB at most each time.

Assuming, for example, that value is Hello, the string might be 10 in length, with the first five for Hello and the last five for subsequent expansion.

PS: the maximum length of the string is 512MB.

Note: The Redis string can be expanded. If the size does not exceed 1MB, the capacity is doubled. If the size exceeds 1MB, only 1MB is added each time.

The list (list)

Redis lists are like LinkedLists in Java,

And since it’s a linked list, that means it’s very fast to insert and delete, O(1), but very slow to find, O(N),

Each element in the list has a bidirectional pointer that can point to the previous element and the next element, facilitating forward and backward traversal. When the last element in the list is displayed (that is, there is no data in the list), the list will be deleted automatically, and the memory occupied by the list will be reclaimed.

A quick list

The underlying Redis is not a simple LinkedList, but a QuickList structure,

This structure is ziplist, or compressed list. It compacts all the elements together and uses a contiguous memory space (array). When there is a large amount of data, it is changed to QuickList.

For example, if a linked list contains data of type int, two additional Pointers (prev and next) need to be added to the list.

Therefore, Redis combines linked list and Ziplist to form QuickList, which not only can meet the fast insert and delete performance, but also does not appear too large space redundancy, which makes a balance between performance and space.

The bottom line: The list in Redis is actually a linked list and ziplist combination (to save space) called a QuickList, rather than the imagined Java-like ArrayList, which has the advantage of being faster to add and delete and slower to find.

Hash (dictionary)

Redis dictionary is similar to Java HashMap, both of which are unordered dictionaries with key-value pairs stored internally. Meanwhile, the data structures of both sides are two-dimensional structures of array + linked list. When the array positions collide, the elements will be connected in series using the linked list under the array positions.

The difference is that the values of Redis dictionary can only be strings, and the way of Rehash is also different from that of Java. When Java HashMap is rehash, it needs to be completed all at one time. When the amount of data is large, the performance is poor and slow.

In order to pursue high performance, Redis adopts a progressive rehash strategy to ensure that services are not blocked during rehash.

Progressive rehash

Progressive rehash preserves both the old and new hash structures while rehashing, and queries both hash structures simultaneously.

Then, in subsequent scheduled tasks and hash operation instructions, the contents of the old hash are gradually migrated to the new hash structure.

When the migration is complete, the new hash will replace the old one, which will be automatically deleted after the last element is removed, and the memory will be reclaimed.

Set (set)

The collection in Redis is equivalent to the Java language HashSet. The key-value pairs are unordered but unique. The internal implementation is a dictionary in which all values are null values.

Zset (Ordered set)

Zset is similar to the combination of Java SortedSet and HashMap. On the one hand, a set can ensure uniqueness; on the other hand, each data in the set can be set with a score, which is used to sort data.

The internal data structure of a Zset is a tree structure called a jump list. Like a set, when the last element in the set is removed, the data structure is automatically deleted and memory is reclaimed.

Jump lists

Zset needs to support random insertion and deletion, so array is not appropriate, so storage needs to use linked list data structure, and the linked list also needs to use score value for sorting.

Ordered means that when you have something to insert, you have to locate the insertion point at a particular place, so that the linked list is in order, and usually binary search is used to locate the insertion point, but only arrays support binary search, linked lists can’t do that, so skip lists do that for you,

For example, if you’re in a company of hundreds of people, and the boss is assigning tasks, and there’s no organizational structure, and you have to assign tasks to each person individually, it’s going to be tiring,

However, the company can select the department manager, then the group leader, and then the group member. In this way, every time the boss assigns a task, he only needs to find the department manager, who then finds the group leader, who then finds the group member, which will be much easier.

Skip lists are similar to the hierarchy above, where all the elements are linked in a list at the bottom, and a group leader is selected every few elements, and then the department manager is selected between the group leaders.

Skip lists are called skip lists because an element can exist at different levels at the same time. For example, the element in the middle can exist at levels L0, 1, and 2.

To locate the insertion point, first locate the insertion point on the top layer, then dive down to the next layer, until you dive down to the bottom layer, and insert the new element. In this way, the effect similar to binary search can be achieved.