Shulou(Shulou.com)05/31 Report--

Today, I will talk to you about the data structures in Redis, which may not be well understood by many people. in order to make you understand better, the editor has summarized the following contents for you. I hope you can get something according to this article.

Redis core object

There is a "core object" in Redis called redisObject, which is used to represent all key and value, using redisObject structures to represent five data types: String, Hash, List, Set, and ZSet.

The source code of redisObject is in redis.h, written in c language, and those who are interested can check it by themselves. I have drawn a picture of redisObject here, which shows that the structure of redisObject is as follows:

The colorful pictures of the blind.

In redisObject, "type indicates which data type it belongs to, and encoding represents how the data is stored", that is, the underlying implementation of the data type's data structure. Therefore, this article specifically introduces the corresponding part of encoding.

So what does the storage type in encoding mean? The meaning of the specific data type, as shown in the following figure:

Screenshot from "Redis Design and implementation second Edition"

Maybe after reading this picture, I still feel confused. Don't panic, there will be a detailed introduction of the five data structures. This diagram only allows you to find out which storage types are corresponding to each data structure, and you probably have an impression in mind.

To take a simple example, you set a string key 234 in Redis, and then look at the storage type of the string, you will see that the storage type of the string is int, and the non-integer one uses the embstr storage type, as shown in the figure below:

String Typ

String is the most basic data type of Redis, and it is also mentioned in the above introduction that Redis is developed in C language. But there is a clear difference between string types in Redis and string types in the c language.

There are three ways to store data structures of String type: int, raw, and embstr. So what's the difference between these three storage methods?

Int

Redis stipulates that if you store an "integer value", such as set num 123, it will be stored using the int storage method, and the value will be saved in the "ptr property" of redisObject.

SDS

If the stored string is a string value and the length is greater than 32 bytes, it will be stored using SDS (simple dynamic string), and if encoding is set to raw;, if the string length is less than or equal to 32 bytes, it will change encoding to embstr to save the string.

SDS is called a "simple dynamic string". For the three attributes defined in SDS in the source code of Redis, int len, int free, and char buf [].

Len holds the length of the string, free represents the number of unused bytes in the buf array, and the buf array holds each character element of the string.

So when you store a string Hello in Redsi, you can draw a redisObject structure diagram in the form of SDS according to the description of the source code of Redis, as shown in the following figure:

Comparison between SDS and c language strings

Redis certainly has its own advantages in using SDS as the type of string to store. Compared with the string in c language, SDS has made its own design and optimization to the string in c language. The specific advantages are as follows:

(1) the string in the c language does not record its own length, so "every time you get the length of the string will be traversed, and the time complexity is O (n)", while in Redis to get the string as long as you read the value of len, the time complexity becomes O (1).

(2) the concatenation of two strings in the "c language", if the memory space is not allocated long enough, "buffer overflow will occur"; while "SDS" will first determine whether the space meets the requirements according to the len attribute, and if there is not enough space, it will be expanded accordingly, so "there will be no buffer overflow".

(3) SDS also provides two strategies: "space pre-allocation" and "inert space release". When allocating space for a string, it allocates more space than it actually does, which "reduces the number of memory reallocations caused by continuous string growth."

When the string is shortened, SDS does not immediately reclaim the unused space, but records the unused space through the free property and releases it later when it is used.

The specific principle of space pre-allocation is: "when the length len of the modified string is less than 1MB, the space of the same length as len will be pre-allocated, that is, if the len of len=free; is greater than 1MB, the space allocated by free will be 1MB".

(4) SDS is binary security, in addition to storing strings, you can also store binary files (such as pictures, audio, video and other files of binary data); while the string in c language is an empty string as a Terminator, some pictures contain Terminators, so it is not binary safe.

To make it easy to understand, a table is made to compare the c-language string with SDS, as follows:

C language string SDS the time complexity of getting the length is O (n) the time complexity of getting the length is O (1) it's not binary secure, it's binary safe, it can only save strings, and it can save binary data, n times growing strings will inevitably lead to n times memory allocation, n times increasing string memory allocation times redisTemplate = new StringRedisTemplate (factory); return redisTemplate;}}

(3) the third step is to create Redis tool class RedisUtil, since learning object-oriented, like some common things into tool classes, like a part, when needed, assemble it.

@ Component public class RedisUtil {@ Autowired private RedisTemplate redisTemplate; / * store messages in the message queue * @ param key key * @ param value value * @ return * / public boolean lPushMessage (String key, Object value) {try {redisTemplate.opsForList (). LeftPush (key, value); return true;} catch (Exception e) {e.printStackTrace (); return false }} / * message pops up from the message queue * @ param key key * @ return * / public Object rPopMessage (String key) {try {return redisTemplate.opsForList (). RightPop (key);} catch (Exception e) {e.printStackTrace (); return null }} / * View message * @ param key key * @ param start start * @ param end ends 0 to-1 represents all values * @ return * / public List getMessage (String key, long start, long end) {try {return redisTemplate.opsForList (). Range (key, start, end);} catch (Exception e) {e.printStackTrace (); return null;}

This completes the creation of the Redis message queuing utility class, which can be used directly in later code.

Set collection

Both lists and collections in Redis can be used to store strings, but "Set is a non-repeatable collection, while List lists can store the same strings." Set collections are unordered as opposed to ZSet ordered collections discussed later.

The underlying implementation of Set is "ht and intset". Ht (hash table) has been studied in detail before. let's take a look at the storage structure of the inset type.

Inset, also known as a collection of integers, is used to hold the data structure type of integer values, which can hold the integer values of int16_t, int32_t, or int64_t.

In the set of integers, there are three attribute values encoding, length, and contents [], which represent the encoding, the length of the integer set, and the content of the element, respectively. Length is the size in the record contents.

When an element is added to the integer collection, if the length of the original collection is exceeded, the collection will be upgraded. The specific upgrade process is as follows:

Hongmeng official Strategic Cooperation to build HarmonyOS Technology Community

First expand the size of the underlying array, and the type of the array is the type of the new element.

Then convert the elements in the original array to the type of the new element and place them in the corresponding position of the expanded array.

The set of integers will not be degraded after the upgrade, and the coding will remain in the upgraded state.

Application scenario

The application scenarios of the Set collection can be used for business types such as "de-duplication, lucky draw, mutual friend, second-degree friend" and so on. Next, simulate a case of adding friends:

@ RequestMapping (value = "/ addFriend", method = RequestMethod.POST) public Long addFriend (User user, String friend) {String currentKey = null; / / determine whether it is a friend of the current user if (AppContext.getCurrentUser (). GetId (). Equals (user.getId)) {currentKey = user.getId.toString () } / / if 0 is returned, it means that it is not the user's friend return currentKey==null?0l:setOperations.add (currentKey, friend);}

If both users An and B use the above API to add a lot of their own friends, then one of the requirements is to obtain the common friends of An and B, so you can do the following:

Public Set intersectFriend (User userA, User userB) {return setOperations.intersect (userA.getId.toString (), userB.getId.toString ());}

For example, you can also achieve A users' own friends, or B users' own friends, etc., can be achieved.

ZSet collection

ZSet is an ordered collection. From the figure above, you can see that the underlying implementation of ZSet is implemented by ziplist and skiplist. Ziplist has been described in detail above. Here we will explain the structural implementation of skiplist.

Skiplist, also known as "jump table", is an ordered data structure that maintains multiple pointers to other nodes for fast access by each node.

Skiplist has the following characteristics:

Hongmeng official Strategic Cooperation to build HarmonyOS Technology Community

It is composed of many layers, the number of nodes from top to bottom is gradually dense, and the uppermost nodes are the most sparse and the span is the largest.

Each layer is an ordered linked list that contains at least two nodes, a header node and a tail node.

Each node in each layer contains a pointer to a node in the same layer and a node in the same location in the next layer.

If a node appears at a certain layer, then all the linked lists below will appear at the same location.

The structure diagram of the specific implementation is as follows:

In the structure of the jump table, head and tail represent the pointers to the head node and the tail node, which can quickly realize the positioning. Level represents the number of layers, len represents the length of the jump table, and BW represents the backward pointer, which is used when traversing from the tail to the front.

There are also two values under the BW that represent the score and the member object (the member object saved by each node).

In the implementation of the jump table, except that the bottom layer holds the complete data of the original linked list, the number of nodes in the upper layer will be less and less, and the span will be larger and larger.

The upper layer of the jump table is equivalent to the index layer, which serves to find the final data. the larger the amount of data, the higher the efficiency of the query reflected in the table, which is about the same as that of the balanced tree.

Application scenario

Because ZSet is an orderly collection, it is common for ZSet to implement sorting services, such as recommending the 10 most popular posts on the home page, that is, the implementation of rankings from high to low readings.

The following is a case study of the contestants who have obtained the top 10 in the rankings. The code for the implementation is as follows:

@ Autowired private RedisTemplate redisTemplate; / * get the top 10 rankings * @ return * / public static List getZset (String key, long baseNum, LevelService levelService) {ZSetOperations operations = redisTemplate.opsForZSet (); / / get the top 10 data Set set = operations.reverseRangeWithScores (key,0,9); List list= new ArrayList (); int iTunes 1 based on the score score For (ZSetOperations.TypedTuple o:set) {int uid = (int) o.getValue (); LevelCache levelCache = levelService.getLevelCache (uid); LevelVO levelVO = levelCache.getLevelVO (); long score = (o.getScore (). LongValue ()-baseNum + levelVO .getCtime ()) / CommonUtil.multiplier; levelVO .setScore (score); levelVO .setRank (I) List.add (levelVO); iTunes;} return list;} after reading the above, do you have any further understanding of the data structures in Redis? If you want to know more knowledge or related content, please follow the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.