14 Ordered Set Usage and Internal Implementation Principles #

Compared to set types, sorted set types have an additional sorting property called score. For a sorted set, each stored element is composed of two values: the element value and the sorting value. The element values in a sorted set are also unique, but the scores can be repeated.

When we store a student’s score in a sorted set, the storage structure is shown in the following figure:

Now let’s start with the usage of sorted sets.

1 Basic Usage #

1) Add one or more elements #

Syntax: zadd key [NX|XX] [CH] [INCR] score member [score member …] Example:

127.0.0.1:6379> zadd zset1 10 java
(integer) 1
127.0.0.1:6379> zadd zset1 3 golang 4 sql 1 redis
(integer) 3

As we can see, elements are added to the sorted set using the format zadd key score1 member1 score2 member2 .

2) Query the list of all elements #

Syntax: zrange key start stop [WITHSCORES] Example:

127.0.0.1:6379> zrange zset 0 -1
1) "redis"
2) "mysql"
3) "java"

Here, -1 represents the last element, and the query result includes the start and end elements.

3) Remove one or more elements (based on element value) #

Syntax: zrem key member [member …] Example:

127.0.0.1:6379> zrangebyscore zset1 0 -1 #Query all elements
1) "golang"
2) "redis"
3) "sql"
4) "java"
127.0.0.1:6379> zrem zset1 redis sql #Remove elements: redis, sql
(integer) 2
127.0.0.1:6379> zrange zset1 0 -1 #Query all elements
1) "golang"
2) "java"

If the delete command contains elements that do not exist, they will not affect the normal execution of the command, and the non-existent elements will be ignored.

4) Query the score value of a specific element #

Syntax: zscore key member Example:

127.0.0.1:6379> zscore zset1 redis
"1"

5) Query elements within a score range #

Syntax: zrangebyscore key min max [WITHSCORES] [LIMIT offset count] Example:

127.0.0.1:6379> zrangebyscore zset1 3 10
1) "golang"
2) "redis"
3) "sql"
4) "java"

6) Query the rank of a specific element #

Syntax: zrank key member Example:

127.0.0.1:6379> zadd zset 5 redis 10 java 8 mysql #Create a sorted set
(integer) 3
127.0.0.1:6379> zrank zset java #Query the ranking of the element
(integer) 2
127.0.0.1:6379> zrank zset redis
(integer) 0

As we can see, the ranking starts from 0, and the ranking can be understood as the indexed value of the element after sorting.

For more commands, please refer to the appendix.

2 Code Practice #

Now let’s look at the usage of sorted sets in Java. First, add the Jedis framework. The sample code is as follows:

import redis.clients.jedis.Jedis;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class ZSetExample {

public static void main(String[] args) {
    Jedis jedis = new Jedis("127.0.0.1", 6379);
    Map<String, Double> map = new HashMap<>();
    map.put("小明", 80.5d);
    map.put("小红", 75d);
    map.put("老王", 85d);
    // Add elements to the sorted set
    jedis.zadd("grade", map);
    // Query people with scores between 80 and 100 (including 80 and 100)
    Set<String> gradeSet = jedis.zrangeByScore("grade", 80, 100);
    System.out.println(gradeSet); // Output: [小明, 老王]
    // Query the ranking of 小红 (rank starts from 0)
    System.out.println(jedis.zrank("grade", "小明")); // Output: 1
    // Remove 老王 from the set
    jedis.zrem("grade", "老王");
    // Query all elements in the sorted set (ordered by rank from small to large)
    Set<String> range = jedis.zrange("grade", 0, -1);
    System.out.println(range); // Output: [小红, 小明]
    // Query all elements in the sorted set (ordered by score from small to large)
    Set<String> rangeByScore = jedis.zrangeByScore("grade", 0, 100);
    System.out.println(rangeByScore);
}
}

3 Implementation #

A sorted set is composed of ziplist or skiplist.

1) ziplist #

When the data is small, the sorted set is stored in the ziplist format, as shown in the following code:

127.0.0.1:6379> zadd myzset 1 db 2 redis 3 mysql
(integer) 3
127.0.0.1:6379> object encoding myzset
"ziplist"

From the results, we can see that the key-value pairs of the sorted set are stored in the ziplist structure. The sorted set using ziplist as storage must meet the following two conditions:

• The number of elements in the sorted set must be less than 128.
• The length of all the element values in the sorted set must be less than 64 bytes.

If either of the above conditions is not satisfied, the sorted set will be stored using skiplist. Next, let’s test what happens when an element in the sorted set has a length greater than 64 bytes. The code is as follows:

127.0.0.1:6379> zadd zmaxleng 1.0 redis
(integer) 1
127.0.0.1:6379> object encoding zmaxleng
"ziplist"
127.0.0.1:6379> zadd zmaxleng 2.0 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
(integer) 1
127.0.0.1:6379> object encoding zmaxleng
"skiplist"

From the above code, we can see that when the length of all the element values in the sorted set is greater than 64 bytes, the sorted set will be converted from ziplist to skiplist.

Note: You can set the threshold for using ziplist as storage for sorted sets by configuring the parameters “zset-max-ziplist-entries” (default: 128) and “zset-max-ziplist-value” (default: 64) in the configuration file.

2) skiplist #

The skiplist data structure is implemented based on the zset structure, which consists of a dictionary and a skiplist, as shown in the source code:

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

The source code implementation of the skip list will be detailed in later sections.

① Skip List Implementation Principle #

The structure of the skip list is shown in the following figure:

According to the above image, when we query the value 32 in the skip list, the execution flow is as follows:

• Start from the top level and compare: 1 is less than 32, move to the next node in the current level and compare;
• 7 is less than 32, move to the next node in the current level and compare. Because the next node points to Null, take 7 as the target and move to the next level to continue searching;
• 18 is less than 32, continue to move forward to search. Compared to 77, 18 is less than 32, move to the next level and continue searching;
• Compared to 32, 32 is equal to 32, and the value is successfully found.

From the above process, it can be seen that the skip list starts from the top level and searches from front to back. If the node at the current level is greater than the value being searched, or if the node at the current level is Null, move to the previous node as the target and continue to move down a level to search and loop this process, until the node is found and returned. If the last element is compared and the node is still not found, Null is returned.

② Why skip list instead of red-black tree? #

Because the performance of the skip list is similar to that of a red-black tree, but it is easier to implement compared to a red-black tree, Redis uses a skip list for the implementation of sorted sets.

4 Usage Scenarios #

The classic use cases of sorted sets are as follows:

• Ranking of student scores
• Fans list, sorted by follow time

5 Summary #

Through the study of this article, we have learned that sorted sets have the unique and sorting features. The sorting feature is achieved by the score field. The score field not only provides the sorting capability but also enables the filtering and selection of data. We also learned that sorted sets are stored in the ziplist or skiplist format. When the number of elements is less than 128 and the length of all element values is less than 64 bytes, the sorted set uses ziplist for storage. Otherwise, it uses skiplist. Skiplist searches elements from top to bottom and from front to back. Compared to a traditional plain list, it can be faster because the plain list can only search from front to back one by one.