Shulou(Shulou.com)06/01 Report--

This article is to share with you about the underlying implementation of Redis ordered collection objects, the editor thinks it is very practical, so I share it with you to learn. I hope you can get something after reading this article.

I. Preface

Redis provides five data types: String (string), Hash (hash), List (list), Set (set), and Zset (ordered set). Understanding the characteristics of each data type is very important for the development and operation of redis.

Original text analysis

Second, command realization

  because the values of ordered collection keys are ordered collection objects, all commands for ordered collection keys are built against ordered collection objects.

The command ziplist-encoded implementation method zset-encoded implementation method ZADD calls the ziplistInsert function, inserting members and scores into the compressed list as two nodes, respectively. First call the zslInsert function to add the new element to the jump table, and then call the dictAdd function to associate the new element to the dictionary. ZCARD calls the ziplistLen function to get the number of nodes in the compressed list, and divide this number by 2 to get the number of collection elements. Access the length property of the jump table data structure and directly return the number of collection elements. ZCOUNT traverses the compressed list to count the number of nodes whose scores are within a given range. Traverse the jump table to count the number of nodes with a score within a given range. ZRANGE traverses the compressed list from header to footer, returning all elements within a given index range. Traverses the jump table from header to footer, returning all elements within the given index range. ZREVRANGE traverses the compressed list from the footer to the header, returning all elements within a given index range. Traverses the jump table from the footer to the header, returning all elements within the given index range. ZRANK traverses the compressed list from header to footer to find a given member, and records the number of nodes along the way. When a given member is found, the number of passing nodes is the ranking of the corresponding elements of the member. Traverse the jump table from header to footer to find a given member, record the number of nodes along the way, and when a given member is found, the number of passing nodes is the ranking of the corresponding elements of the member. ZREVRANK traverses the compressed list from the footer to the header to find a given member, and records the number of nodes along the way. When a given member is found, the number of passing nodes is the ranking of the corresponding elements of the member. Traverse the jump table from the tail to the header to find a given member, record the number of nodes along the way, and when a given member is found, the number of passing nodes is the ranking of the corresponding elements of the member. ZREM iterates through the compressed list, deleting all nodes that contain a given member, and the score node next to the deleted member node. Traverses the jump table, deleting all jump table nodes that contain a given member. And disassociate the members and scores of the deleted element in the dictionary. ZSCORE iterates through the compressed list, finds the node that contains the given member, and then fetches the element score saved by the score node next to the member node. Fetch the score of a given member directly from the dictionary. III. Structural analysis

  from the previous article and the above figure shows that the encoding of ordered sets can be ziplist or skiplist. The ziplist-encoded ordered collection object uses a compressed list as the underlying implementation, and each collection element is saved by two compressed list nodes next to each other, with the first node holding the members of the element (member) and the second element holding the element's score.

Compressed list mode

The collection elements in the compressed list are sorted from small to large, the elements with lower scores are placed near the header, and the elements with higher scores are placed near the end of the table.

For example, if we execute the following ZADD command, the server will create an ordered collection object as the value of the price key:

Redis > ZADD price 8.5 apple 5.0 banana 6.0 cherry (integer) 3

If the value object of the price key uses ziplist encoding, the value object will be shown in figure 8-14, and the compressed list used by the object will be shown in figure 8-15.

Jump table and dictionary mode

The ordered collection object encoded by   skiplist uses the zset structure as the underlying implementation, and a zset structure contains both a dictionary and a jump table:

Typedef struct zset {zskiplist * zsl; dict * dict;} zset

The zsl jump table in the zset structure saves all the collection elements from small to large, and each jump table node stores a collection element: the object attribute of the jump table node stores the members of the element, while the score attribute of the jump table node stores the score of the element. Through this jump table, the program can perform scope operations on ordered sets, such as ZRANK, ZRANGE and other commands are based on the jump table API.

In addition, the dict dictionary in the zset structure creates a mapping from members to scores for ordered collections, and each key-value pair in the dictionary holds a collection element: the key of the dictionary holds the members of the element, while the value of the dictionary holds the score of the element. Through this dictionary, the program can find the score of a given member with O (1) complexity, and the ZSCORE command is implemented based on this feature, while many other ordered set commands use this feature inside the implementation.

Ordered collection the member of each element is a string object, and the score of each element is a floating-point number of type double. It is worth mentioning that although the zset structure uses both jump tables and dictionaries to hold ordered collection elements, both data structures share members and scores of the same element through pointers, so using both jump tables and dictionaries to save collection elements does not result in any duplicate members or scores, nor does it waste extra memory.

Skiplist-encoded ordered collection object, then the ordered collection object will be shown in figure 8-16, and the zset structure used by the object will be shown in figure 8-17.

Note:    for ease of presentation, figures 8-17 repeatedly show the members and scores of each element in dictionaries and jump tables, but in practice, dictionaries and jump tables share element members and scores, so they do not cause any data duplication or waste any memory.

IV. Code conversion

When an ordered collection object can meet both of the following conditions, the object uses ziplist encoding:

1. The number of elements saved in an ordered collection is less than 128

two。 The length of all element members saved in an ordered set is less than 64 bytes

Ordered collection objects that do not meet the above two conditions will use skiplist encoding.

Note: the upper limit of the above two conditions of    can be modified. For more information, please see the description of the zset-max-ziplist-entries option and the zset-max-ziplist-value option in the configuration file. For ordered collection objects using ziplist encoding, when either of the two conditions required for using ziplist encoding cannot be met, the program will perform a transcoding operation, transfer all collection elements originally stored in the compressed list to the zset structure, and change the object's encoding from ziplist to skiplist.

1. The following shows the transcoding of an ordered collection object because it contains too many elements: # object contains 128elements redis > EVAL "for iTunes 1,128 do redis.call ('ZADD', KEYS [1], I) I) end "1 numbers (nil) redis > ZCARD numbers (integer) 128redis > OBJECT ENCODING numbers" ziplist "# add a new element redis > ZADD numbers 3.14 pi (integer) the number of elements contained in the object has changed to 129redis > ZCARD numbers (integer) 12 codes has been changed redis > OBJECT ENCODING numbers" skiplist "2. The following shows that an ordered collection object causes transcoding because its members are too long: # add an element with a member of only three bytes to the ordered collection redis > ZADD blah 1.0 www (integer) 1redis > OBJECT ENCODING blah "ziplist" # add an element with a member of 66 bytes redis > ZADD blah 2.0 oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo (integer) encoding has been changed redis > OBJECT ENCODING blah "skiplist" 5.

1) the encoding of ordered sets can be ziplist or skiplist.

2) an zset structure contains both a dictionary and a jump table.

3) the zset structure jump table and dictionary share the members and scores of the same element through pointers.

4) ordered collection objects are encoded by ziplist or skiplist, and transcoding can occur if the conditions are met.

The above is what the underlying implementation of Redis ordered collection objects is, and the editor believes that there are some knowledge points that we may see or use in our daily work. I hope you can learn more from this article. For more details, please follow the industry information channel.

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.