“This is the third day of my participation in the First Challenge 2022, for more details: First Challenge 2022”.

preface

Zset is an ordered set that can be used for sorting. Each element has a floating-point score attribute, and it can be sorted from small to large according to score. If score is the same, it can be sorted according to the ASCII code of key.

Compare with other data structures

​

First, basic use

​

ZADD key [NX|XX] [CH] [INCR] score member [score member ...]
Copy the code

Zadd inserts elements into ordered sets

2, key ordered set name

3. The setting is successful only when the NX- element does not exist and XX- element exists

4, CH changes the return value = the sum of the new elements added and modified elements

5. INCR modifies the new score to the original score plus the newly specified score value

Score Specifies the score value of the new element

7. New element name

​

ZRANGE key start stop [WITHSCORES]
Copy the code

1. ZRANGE searches for elements in an ordered set by range, and supports the return of element scores

2. A key is an ordered collection to be found

Start: 0- represents the first element, and -1- represents the last element

WITHSCORES Specifies whether to return the score value

Two, storage type

Like the hash type, zset uses two encodings: ziplist and skiplist.

In redis.conf, use the following configuration criteria to switch the storage type

# Ziplistzset-max-ziplist-entries 128# Ziplistzset-max-ziplist-value 64 # Ziplistzset-max-ziplist-value 64Copy the code

In the source code, when adding an element, if no ordered collection exists, zsets of different storage types are created according to the configuration.

Zsetvoid zaddGenericCommand(client *c, int flags) {... /* Lookup the key and create the sorted set if does not exist. */ zobj = lookupKeyWrite(c->db,key); if (zobj == NULL) { if (xx) goto reply_to_client; /* No key + XX option: nothing to do. */ if (server.zset_max_ziplist_entries == 0 || server.zset_max_ziplist_value < Sdslen (c->argv[scoreidx+1]-> PTR)) {// If the ziplist threshold is met, zobj = createZsetObject(); } else {// use skiplist zobj = createZsetZiplistObject(); } dbAdd(c->db,key,zobj); } else { if (zobj->type ! = OBJ_ZSET) { addReply(c,shared.wrongtypeerr); goto cleanup; }}... }Copy the code

​

  • The Ziplist structure has been analyzed in the previous article and will not be analyzed in this article, which will focus on skiplist

Three, skip table analysis

  • Redis skip table features:

1. The probabilistic alternative algorithm of William Pugh’s balanced tree is implemented with C language translation.

2. Score members who support repetition

3, support score sort, also support data sort

4. There is a backward pointer, so it is a two-way linked list, and the backward pointer is only at “level 1”. This allows you to traverse the list from end to end, which is useful for ZREVRANGE

4. Definition of hop table structure

Typedef struct zskiplistNode {// Element contents string type SDS ele; // double score; Struct zskiplistNode *backward; Struct zskiplistNode *forward; struct zskiplistNode *forward; // Element span unsigned long span; } level[]; } zskiplistNode; typedef struct zskiplist { struct zskiplistNode *header, *tail; // Size unsigned long length; Int level; } zskiplist; Typedef struct zset {// dict *dict; ZSL * ZSL; } zset;Copy the code

Summary: A skip list is a linked list. Each node has a hierarchical array, and each node holds a pointer to the next node.

Skiplist new method source code analysis

// Insert a node
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) { 
/* Update saves the previous node */ at the insertion position of each layer    
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;    
unsigned int rank[ZSKIPLIST_MAXLEVEL];    
int i, level;​    
serverAssert(!isnan(score));    
/ / zset head node
x = zsl->header;    
// Start with the largest layer and find the node before each layer insertion position
for (i = zsl->level- 1; i >= 0; i--) {
// Calculate the insertion position of the maximum layer base is 0, the other layer is the next layer as the base
/* store rank that is crossed to reach the insert position */        
rank[i] = i == (zsl->level- 1)?0 : rank[i+1];        
// The score of the current node is less than the inserted element score, or the score is equal to the content of the inserted element content (need to insert data before this node)
while (x->level[i].forward && (x->level[i].forward->score < score 
||(x->level[i].forward->score == score 
&& sdscmp(x->level[i].forward->ele,ele) < 0))) {// Add up the number of nodes that the current node spans
 rank[i] += x->level[i].span;            
 // Record the node smaller than the current node
 x = x->level[i].forward;        
}        
update[i] = x; 
}    
/* we assume the element is not already inside, since we allow duplicated * scores, reinserting the same element should never happen since the * caller of zslInsert() should test in the hash table if the element is * already inside or not. */
// Calculate the level of the new element
level = zslRandomLevel(a);// The new element level is larger than the current hop table level
if (level > zsl->level) {        
 // Initialize the previous node data between the new level and the old level for each level insertion position
 for (i = zsl->level; i < level; i++) {            
  // The node before the initial insertion position is the first node
  rank[i] = 0;            
  // Initialize the insertion position where the preceding section is the head node
  update[i] = zsl->header;            
  // Initialize the number of nodes to span before the insertion position to be the length of the hop table
  update[i]->level[i].span = zsl->length;        
 }       
 zsl->level = level;    
}    
 Create a new node
 x = zslCreateNode(level,score,ele);    
// Insert a new node into the position of each layer based on the previous position calculated previously
for (i = 0; i < level; i++) {        
 // Update the new node next node
 x->level[i].forward = update[i]->level[i].forward;        
 // New node inserts link
 update[i]->level[i].forward = x;       
 // Update the span
 /* update span covered by update[i] as x is inserted here */        
 x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
 update[i]->level[i].span = (rank[0] - rank[i]) + 1;    
}
/* increment span for untouched levels */    
for (i = level; i < zsl->level; i++) {        
update[i]->level[i].span++;    
}    
// Modify the precursor node of the new node
x->backward = (update[0] == zsl->header) ? NULL : update[0];
if (x->level[0].forward)        
 x->level[0].forward->backward = x;
else        
 // The new node belongs to the tail node
 zsl->tail = x;    
 // The length increases
 zsl->length++;    
 return x;
}
// New level of random computation
int zslRandomLevel(void) {
int level = 1;    
// Random number < 65535*0.25 (25% probability to add 1 level) increment by 1
while ((random() &0xFFFF) < (ZSKIPLIST_P * 0xFFFF))        
 level += 1;    
 return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
Copy the code

The overall process is as follows:

​