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

In this issue, the editor will bring you about the role of the scan command in Redis. The article is rich in content and analyzes and narrates it from a professional point of view. I hope you can get something after reading this article.

SCAN command

The SCAN command is SCAN,SSCAN,HSCAN,ZSCAN.

SCAN means traversing all the keys.

The other SCAN commands are the collection selected by SCAN.

The SCAN command is an incremental loop that returns only a small portion of the elements per call. So there will be no KEYS commands.

The SCAN command returns a cursor that traverses from 0 to 0.

Today we mainly discuss how scan works from the perspective of underlying structure and source code.

The structure of Redis

Redis uses the Hash table as the underlying implementation, simply because it is efficient and easy to implement. When it comes to Hash tables, the first reaction of many Java programmers is HashMap. Yes, the storage structure of the underlying key of Redis is similar to the array + linked list structure of HashMap. Where the array size of the first dimension is 2n (n > = 0). The length of each expansion array is doubled.

The scan command traverses this one-dimensional array. The cursor value returned each time is also the index of this array. The limit parameter indicates how many array elements are traversed and returns all the eligible results attached to these elements. Because the size of the linked list attached under each element is different, the number of results returned each time is different.

Traversal order of SCAN

We can take a look at the traversal order of the scan command with a small chestnut.

127.0.0.1 keys * 1) "db_number" 2) "key1" 3) "myKey" 127.0.0.1 scan 0 MATCH * COUNT 11) "2" 2) 1) "db_number" 127.0.0.1scan 2 MATCH * COUNT 11) "1" 2) 1) "myKey" 127.0.0.1 1 MATCH * COUNT 11) "3" 2) 1) "key1" 127.0 .0.1 COUNT 6379 > scan 3 MATCH * COUNT 11) "0" 2) (empty list or set)

We have three key in our Redis, and we only iterate through the elements in an one-dimensional array at a time. As shown above, the traversal order of the SCAN command is

0-> 2-> 1-> 3

This order seems a little strange. It will be easier for us to understand if we convert it to binary.

00-> 10-> 01-> 11

We find that each time this sequence is high plus 1. Ordinary binary addition is the addition and carry from right to left. This sequence is added and carried from left to right. This point is also confirmed in the source code of redis.

The cursor is handled as follows in the dictScan function of the dict.c file

V = rev (v); v = rev (v)

It means that the cursor is inverted, added one, and then inverted, which is what we call "high plus 1" operation.

Here you may wonder why you should use this order for traversal instead of the normal 0, 1, 2. This order is due to the need to consider the expansion and reduction of dictionaries over time (we have to admire the comprehensiveness of developers' consideration of the problem).

Let's take a look at how traversal occurs during SCAN traversal when capacity expansion occurs. There are four elements in our original array, that is, the index has two digits, so we need to expand it to 3 digits and rehash it.

All elements that were originally attached under xx are assigned to 0xx and 1xx. In the figure above, when we are about to iterate through 10:00, dict does rehash, and the scan command will start traversing from 010, while 00000 and 100 (the elements attached under 00) will not be repeated.

Let's take a look at the downsizing. Suppose the dict is scaled down from 3 digits to 2 digits, and the dict will be scaled down immediately, and the scan will traverse 10. At this point, the elements attached under 010 will be traversed repeatedly, but none of the elements before 010 will be repeated. Therefore, there may be some repetitive elements when downsizing.

Rehash of Redis

Rehash is a complex process. In order not to block the process of Redis, it adopts a progressive rehash mechanism.

/ * dictionary * / typedef struct dict {/ / type-specific function dictType * type; / / private data void * privdata; / / hash table dictht ht [2]; / / rehash index / / when rehash is not in progress, the value is-1 int rehashidx; / * rehashing not in progress if rehashidx = =-1 * / the number of security iterators currently running int iterators; / * number of iterators currently running * /} dict

In the dictionary structure of Redis, there are two hash tables, a new table and an old table. In the process of rehash, redis gradually migrates the elements from the old table to the new table, so let's take a look at the source code of dict's rehash operation.

/ * Performs N steps of incremental rehashing. Returns 1 if there are still * keys to move from the old to the new hash table, otherwise 0 is returned. * * Note that a rehashing step consists in moving a bucket (that may have more * than one key as we use chaining) from the old to the new hash table, however * since part of the hash table may be composed of empty spaces, it is not * guaranteed that this function will rehash even a single bucket, since it * will visit at max Nissan 10 empty buckets in total, otherwise the amount of * work it does would be unbound and the function may block for a long time. * / int dictRehash (dict * d, int n) {int empty_visits = nasty 10; / * Max number of empty buckets to visit. * / if (! dictIsRehashing (d)) return 0; while (Nmura-& d-> ht [0] .used! = 0) {dictEntry * de, * nextde; / * Note that rehashidx can't overflow as we are sure there are more * elements because ht [0] .used! = 0 * / assert (d-> ht [0] .size > (unsigned long) d-> rehashidx); while (d-> ht [0] .table [d-> rehashidx] = NULL) {d-> rehashidx++ If (--empty_visits = = 0) return 1;} de = d-> ht [0] .table [d-> rehashidx]; / * Move all the keys in this bucket from the old to the new hash HT * / while (de) {uint64_t h; nextde = de- > next; / * Get the index in the new hash table * / h = dictHashKey (d, de- > key) & d-> ht [1] .sizemask; de- > next = d-> ht [1] .table [h] D-> ht [1] .table [h] = de; d-> ht [0] .used -; d-> ht [1] .used + +; de = nextde;} d-> ht [0] .table [d-> rehashidx] = NULL; d-> rehashidx++;} / * Check if we already rehashed the whole table... * / if (d-> ht [0] .used = 0) {zfree (d-> ht [0] .table); d-> ht [0] = d-> ht [1]; _ dictReset (& d-> ht [1]); d-> rehashidx =-1; return 0;} / * More to rehash... * / return 1;}

Through the comments, we can understand that the process of rehash is migrated on the basis of bucket. The so-called bucket is actually the element of the one-dimensional array we mentioned earlier. Migrate one list at a time. Let's explain this code.

First determine whether rehash is in progress, and if so, proceed; otherwise, return directly.

Then we start the progressive rehash in n steps. At the same time, it also determines whether there are any remaining elements to ensure security.

Before rehash, first determine whether the bucket to be migrated is out of bounds.

Then skip the empty bucket, where there is an empty_visits variable that represents the maximum number of empty bucket that can be accessed, mainly to ensure that there is not too much blocking Redis.

The next step is the element migration, rehash all the elements of the current bucket and update the number of elements in the two tables.

After migrating one bucket each time, you need to point the bucket in the old table to NULL.

Finally, determine whether the migration is complete, and if so, reclaim the space and reset the rehash index, otherwise tell the caller that there is still data that has not been migrated.

Because Redis uses a progressive rehash mechanism, the scan command returns the results to the client when it is necessary to scan both the new and old tables.

This is the role of the scan command in Redis shared by the editor. If you happen to have similar doubts, you might as well refer to the above analysis to understand. If you want to know more about it, you are welcome to 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.