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

This article will explain in detail how to use the SCAN command in Redis to achieve limited guarantee. The content of the article is of high quality, so the editor shares it for you as a reference. I hope you will have a certain understanding of the relevant knowledge after reading this article.

The SCAN command ensures that all elements that exist in the dataset will be fully traversed from the beginning of the full traversal to the end of the full traversal, but the same element may be returned multiple times. If an element is added to the dataset or removed from the dataset during the iteration, the element may or may not be returned.

How does this work? start with the dictionary dict in Redis. Redis's database is implemented using dict as the underlying implementation.

Dictionary data type

Dictionaries in Redis are represented by the dict.h/dict structure:

Typedef struct dict {dictType * type; void * privdata; dictht ht [2]; long rehashidx; / * rehashing not in progress if rehashidx = =-1 * / unsigned long iterators; / * number of iterators currently running * /} dict;typedef struct dictht {dictEntry * * table; unsigned long size; unsigned long sizemask; unsigned long used;} dictht

The dictionary consists of two hash tables, dictht, which are mainly used as rehash, and usually mainly use the ht [0] hash table.

The hash table consists of an array of members dictEntry, the size attribute records the size of the array, the used attribute records the number of existing nodes, and the value of the sizemask attribute equals size-1. The array size is generally 2n, so the sizemask binary is 0b11111. It is mainly used as a mask, together with the hash value, to determine where the key should be placed in the array.

The index of key in the array is calculated as follows:

Index = hash & d-> ht [table] .sizemask

That is, the low value is calculated according to the mask.

The problem with rehash

The dictionary rehash uses two hash tables, first allocating space for ht [1]. If it is an expansion operation, the size of ht [1] is the first 2n greater than or equal to 2 times ht [0] .used, and if it is a contraction operation, the size of ht [1] is the first 2n greater than or equal to ht [0] .used. Then rehash all the key-value pairs of ht [0] into ht [1], finally release ht [0], set ht [1] to ht [0], and create a new blank hash table as ht [1]. Rehash is not done at once, but several times, gradually.

For example, now rehash a hash table ht [0] (sizemask is 11, index = hash & 0b11) to a hash table ht [1] (sizemask = hash & 0b111) with size 8.

The hash value of key in bucket0 position in ht [0] is 00, so the hash value of index from rehash to ht [1] may be 000 (0) and 100 (4). That is, the element rehash in bucket0 in ht [0] is followed by bucket0 and bucket4 scattered in ht [1], and so on, the corresponding relationship is:

Ht [0]-> ht [1]-0-> 0meme 4 1-> 1 recital 5 2-> 2 meme 6 3-> 3 meme 7

If the SCAN command traverses in the order of 0-> 1-> 2-> 3, the following problems occur:

In the expansion operation, if you return cursor 1, part of the data in the bucket0 in rehash,ht [0] may have been rehash to bucket [0] or bucket [4] in ht [1]. When traversing from bucket1 to bucket4 in ht [1], the elements in it have already been traversed in bucket0 in ht [0], which leads to the problem of repetition.

In the zoom-out operation, when cursor 5 is returned, but the size of the reduced hash table is only 4, how to reset the cursor?

Traversal order of SCAN

The traversal order of SCAN commands can be taken as an example:

127.0.0.1) keys * 1) "bar" 2) "qux" 3) "baz" 4) "foo" 127.0.0.1 foo > scan 0 count 11) "2" 2) 1) "bar" 127.0.0.16379 [3] > scan 2 count 11) "1" 2) 1) "foo" 127.0.0.1 scan 1 count 11) "3" "2) 1)" qux "2)" baz "127.0.0.1 scan [3] > scan 3 count 11)" 0 "2) (empty list or set)

You can see that the order is 0-> 2-> 1-> 3. It's hard to see the pattern. Convert it to binary and take a look at it:

00-> 10-> 01-> 11

The binary system is very clear, and the order of traversal is also addition, but each time it is high plus 1, that is, from left to right, from high to low carry.

SCAN source code

The source code of the SCAN traversal dictionary is dict.c/dictScan, which can be divided into two cases: the dictionary is not rehash or rehash is in progress.

When not doing rehash, the cursor is calculated as follows:

M0 = t0-> sizemask;// sets the bit of the umask bit of the cursor to 1v | = ~ m0scarp / reverse cursor v = rev (v); / / + 1 after reversal to achieve the effect of high plus 1 / reverse reset v = rev (v)

When size is 4, sizemask is 3 (00000011). Cursor calculation process:

V | = ~ m0v = rev (v) vault + v = rev (v) 00000000 (0)-> 11111100-> 00111111-> 01000000-> 00000010 (2) 00000010 (2)-> 111111111-> 10000000-> 00000001 (1) 00000001 (1)-> 11111101-> 10111111-> 11000000-> 00000011 (3)-> 11111111-> 00000000-> 00000000 (0)

When traversing size is 4, the cursor state transitions are 0-> 2-> 1-> 3.

Similarly, the cursor state transition when size is 8 is 0-> 4-> 2-> 6-> 1-> 5-> 3-> 7, that is, 000-> 100-> 010-> 110-> 001-> 101-> 011-> 111.

Combined with the previous rehash:

Ht [0]-> ht [1]-0-> 0meme 4 1-> 1 recital 5 2-> 2 meme 6 3-> 3 meme 7

As you can see, when the size changes from small to large, all the original cursors can find the corresponding position in the large hash table, and the order is consistent, will not be read repeatedly and will not be omitted.

When the size changes from large to small, suppose the size has changed from 8 to 4, which is divided into two cases. One is that the cursor is 0, 2, and 1, which is one of the three. At this time, continue to read, and will not be omitted and repeated.

However, if the cursor does not return these four, for example, it becomes 3 after returning 7d7. 11, so it will continue traversing from the bucket3 of the hash table with size 4, while bucket3 contains the bucket3 and bucket7 in the hash table with size 8, so it will cause repeated reading of bucket3 in the hash table with size 8.

Therefore, when the rehash in redis grows up, the SCAN command will not be repeated or omitted. And from big to small, it may cause repetition but not omission.

When rehash is in progress, the cursor calculation process:

/ * Make sure t0 is the smaller and T1 is the bigger table * / if (t0-> size > T1-> size) {t0 = & d-> ht [1]; T1 = & d-> ht [0];} M0 = t0-> sizemask; M1 = T1-> sizemask; / * Emit entries at cursor * / if (bucketfn) bucketfn (privdata, & t0-> table [v & M0]); de = t0-> table [v & M0] While (de) {next = de- > next; fn (privdata, de); de = next;} / * Iterate over indices in larger table that are the expansion * of the index pointed to by the cursor in the smaller table * / do {/ * Emit entries at cursor * / if (bucketfn) bucketfn (privdata, & T1-> table [v & M1]); de = T1-> table [v & M1] While (de) {next = de- > next; fn (privdata, de); de = next;} / * Increment the reverse cursor not covered by the smaller mask.*/ v | = ~ M1; v = rev (v); v = rev (v); / * Continue while bits covered by mask difference is non-zero * /} while (v & (M0 ^ M1))

The algorithm ensures that t0 is a small hash table. If not, t0 and T1 are interchanged, first traversing the bucket where the cursor is located in t0, and then traversing the larger T1.

The process of finding the next cursor is basically the same, except that the m0 is changed to the M1 of the hash table after rehash, and a judgment condition is added:

V & (M0 ^ M1)

The m0 of size4 is 00000011, the M1 of Magne8 is 00000111, and the value of m0 ^ M1 is 00000100, that is, take the different bits of the two mask to see if the cursor is 1 in these flag bits.

Suppose the cursor returns 2 and rehash is in progress, and the size changes from 4 to 8, and the difference between the two mask bits is the lower third bit.

First iterate through bucket2 in T1, then iterate through bucket2 in T1, the next cursor calculated by the formula is 6 (00000110), the lower third bit is 1, continue the loop, traverse the bucket6 in T1, and then calculate the cursor as 1, ending the loop.

So when you are in rehash, both hashes are traversed to avoid omission.

On how to use the SCAN command in Redis to achieve limited guarantee to share here, I hope that the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.

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.