One, foreword

Redis provides five data types: String, Hash, List, Set, and Zset. Understanding the characteristics of each data type is important for the development and operation of Redis.

The original resolution

Note: the implementation of skip lists involved in this section has been analyzed in detail in the last section “Idle Talk about Redis 10” structure implementation of Redis skip lists, which will be directly referenced in this paper and will not be repeated.

Two, command implementation

Because the value of an ordered set key is an ordered set object, all commands for ordered set keys are built for ordered set objects.

The command Ziplist code implementation method Implementation method of ZSET coding
ZADD Call the ziplistInsert function to insert the member and the score value as two separate nodes into the compressed list. The zslInsert function is called to add the new element to the skip list, and the dictAdd function is called to associate the new element with the dictionary.
ZCARD Call 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 skip table data structure, returning the number of collection elements directly.
ZCOUNT Iterate through the compressed list and count the number of nodes with scores in a given range. Iterate over the skip list to count the number of nodes with scores in a given range.
ZRANGE Iterates through the compressed list from the head to the end of the table, returning all elements in the given index range. Traverses the skip list from head to tail, returning all elements in a given index range.
ZREVRANGE Traverses the compressed list from the end of the table to the beginning of the table, returning all elements in the given index range. Traverses the skip list from the end of the table to the beginning of the table, returning all elements in a given index range.
ZRANK Traverse the compressed list from the table head to the table end to find a given member, and record the number of nodes along the way. When a given member is found, the number of nodes passing through is the ranking of the corresponding element of the member. The skip list is traversed from the head of the table to the end of the table to find a given member, and the number of nodes passing through is recorded along the way. When a given member is found, the number of nodes passing through is the ranking of the corresponding element of the member.
ZREVRANK Traverse the compressed list from the end of the table to the beginning of the table to find a given member, and record the number of nodes along the way. When a given member is found, the number of nodes passing through is the ranking of the corresponding element of the member. The skip list is traversed from the end of the table to the beginning of the table to search for a given member, and the number of nodes passing through is recorded along the way. When a given member is found, the number of nodes passing through is the ranking of the corresponding element of the member.
ZREM Iterate through the compressed list to remove all nodes that contain the given member, as well as the score node next to the deleted member node. Traverses the skip list and deletes all skip list nodes that contain a given member. Disassociate the deleted element’s member from its score in the dictionary.
ZSCORE Iterate through the compressed list to find the node that contains the given member, and then extract the element score held by the score node next to the member node. Retrieves the score of a given member directly from the dictionary.

Third, structure analysis

As can be seen from the above and the figure above, the encoding of ordered sets can be ziplist or skiplist. Ziplist-coded ordered collection objects use a compressed list as the underlying implementation. Each collection element is held next to each other by two compressed list nodes, the first node holding the element’s members (member) and the second element holding its score (score).

Compressed list mode

The collection elements in the compressed list are sorted from smallest to largest, with smaller elements placed closer to the table head and larger elements placed closer to the end.

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
Copy the code

If the value object for the price key is ziplist encoded, the value object will look like Figure 8-14, and the compression list used by the object will look like figure 8-15.


Skip lists and dictionaries

Skiplist-encoded ordered collections objects use the zset structure as the underlying implementation, a zset structure containing both a dictionary and a skiplist:

typedef struct zset {

    zskiplist *zsl;

    dict *dict;

} zset;
Copy the code

The ZSL skip list in the ZSET structure stores all the set elements from small to large, and each skip list node stores one set element: the object attribute of the skip list node stores the members of the element, while the score attribute of the skip list node stores the score value of the element. Through this skip list, programs can perform range operations on ordered collections, such as ZRANK, ZRANGE and other commands are based on the skip list API to achieve.

In addition, the dict dictionary in the Zset structure creates a mapping from members to points for ordered collections, with each key-value pair in the dictionary holding a set element: the dictionary’s keys hold the elements’ members, and the dictionary’s values hold the elements’ points. This dictionary allows a program to find the score of a given member with O(1) complexity. The ZSCORE command is based on this feature, and many other ordered collection commands use this feature inside implementations.

The member of each element of an ordered collection is a string object, and the score of each element is a floating-point number of type double. It is worth mentioning that although zset structure used at the same time jump table and a dictionary to store an ordered set elements, but these two kinds of data structure will be Shared by pointer members of the same elements and score, so at the same time use jumping table and dictionaries to save collection elements won’t produce any duplicate member or score, also won’t waste because of this additional memory

The ordered collection object encoded by Skiplist would look like Figure 8-16, and the zset structure used by the object would look like Figure 8-17.


Note: Figure 8-17 repeats the members and points of each element in the dictionary and skip list for ease of presentation, but in practice, the dictionary and skip list share elements’ members and points, so there is no duplication of data and no wasted memory.

Four, coding conversion

The ziplist encoding is used when ordered collection objects can satisfy both of the following conditions:

1. The number of elements stored in an ordered set is less than 128.

2. The length of all elements stored in an ordered set is less than 64 bytes;

Ordered collection objects that do not meet the above two criteria will be encoded using Skiplist.

Note: The upper limits of the above two conditions can be modified, as described in the configuration file for the zset-max-ziplist-entries and zset-max-ziplist-value options. For ziplist-encoded ordered collection objects, when either of the two conditions for ziplist encoding cannot be met, the program will perform a coding conversion operation, transferring all the collection elements originally stored in the compressed list to the zset structure. And change the encoding of the object from Ziplist to skiplist.

1. The following case shows an ordered collection object that causes an encoding shift because it contains too many elements:Copy the code
The # object contains128Element redis> EVAL"for i=1, 128 do redis.call('ZADD', KEYS[1], i, i) end" 1 numbers
(nil)

redis> ZCARD numbers
(integer)128 Redis > OBJECT ENCODING numbers "ziplist" # redis> ZADD numbers 3.14pi
(integer)The 1 # object contains 129 elements redis> ZCARDnumbers
(integer)Redis > OBJECT ENCODING numbers "skiplist"Copy the code
2. The following case shows an ordered collection object causing an encoding shift because the members of the element are too long:Copy the code
Add an element redis> ZADD BLAH to the ordered collection with members only three bytes long1.0 www
(integer) 1

redis> OBJECT ENCODING blah
"ziplist"Add a member to the ordered collection66The byte long element redis> ZADD blah2.0 oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
(integer) 1Redis > OBJECT ENCODING blah"skiplist"
Copy the code

Summary of key points

1) The encoding of ordered sets can be Ziplist or skiplist.

2) A zset structure contains both a dictionary and a skip list.

3) Zset structure skip lists and dictionaries use Pointers to share members and scores of the same element.

4) Ziplist or Skiplist coding of ordered set objects, coding conversion can occur when the conditions are met.

over