Interviewer: what is the internal implementation of set data types in redis?

Although it is already March in spring , But riding a shared bike so far , And a little cold . I rubbed my frozen numb hands , Say to the lady at the front desk ：“ Hello! , I'm here for an interview .”

Miss asked ：“ Hello! , What's your name ？” I reply ：“ My name is wanmao society .” Miss, sister laughed , Speaking of ：“ That's a strange name , Who gave it to you .” I replied without expression ：“ My father .” The little sister put away her smile , Speaking of ：“ Come with me .” I was taken to the interview room to wait , A moment later, a young man with a clean and beautiful face came in , A faint fragrance of men's perfume comes to us. .

interviewer ：Redis What are the basic data types in ？

I ：Redis The basic data types of are ： character string （string）、 Hash （hash）、 list （list）、 aggregate （set）、 Ordered set （zset）.

interviewer ： What is the internal implementation of the collection data type ？

I was also immersed in the complacency of the last question , Suddenly, his expression solidified , The palms began to sweat .“ This .. Not much in-depth understanding ”, I hesitated .

interviewer ： Go back and wait for the news .

This sentence is clear , And then there's no then . Failure is the mother of success , I'm not discouraged , Decided to mend it right away .

Type and code

First , Understand what is type ？ What is? code ？ stay Redis Objects are used in to represent keys and values in memory . Each object consists of a redisObject The structure represents , There are three properties ： type （type）、 code （encoding）、 Pointer to specific data （ptr）.

We usually say string 、 Hash 、 list 、 aggregate 、 Ordered sets are redisObject Medium type , In fact, for each data structure Redis There are various internal coding implementations at the bottom of the system , This is to select the appropriate internal code in the appropriate scene , To achieve a balance between memory space and processing efficiency , This may be the golden mean .

In the interview , Often asked about the internal implementation 、 Internal construction 、 internals , Generally speaking, it means redisObject Medium code .

The encoding of the set

There are two kinds of codes for sets , Namely ： Set of integers （intset） Hash table （hashtable）.

When all elements in a set are integers , And the number of elements is less than set-max-intset-entries（ The default is 512 individual ） when , Use an integer set as the encoding of the set , All integers are stored in the set of elements . such as ：

Log in and copy

127.0.0.1:6379> sadd one-more-set 1 2 3 4 5
(integer) 5
127.0.0.1:6379> smembers one-more-set
1) "1"
2) "2"
3) "3"
4) "4"
5) "5"
127.0.0.1:6379> object encoding one-more-set
"intset"

     

      
1.
      
2.
      
3.
      
4.
      
5.
      
6.
      
7.
      
8.
      
9.
      
10.
     

When all elements in the set are not integers , Or the number of elements is greater than or equal to set-max-intset-entries（ The default is 512 individual ） when , Use the hash table as the encoding of the set , Each key in the hash table is a string object , Each string contains a collection of elements , The values of the hash table are all NULL.

such as , All elements in the collection are not integers ：

Log in and copy

127.0.0.1:6379> sadd one-more-set one more
(integer) 2
127.0.0.1:6379> smembers one-more-set
1) "more"
2) "one"
127.0.0.1:6379> object encoding one-more-set
"hashtable"

     

      
1.
      
2.
      
3.
      
4.
      
5.
      
6.
      
7.
     

Of course , I haven't fully understood the above details yet “ conquer ” interviewer , We need to go deeper :)

Encoding conversion of sets

When a set is encoded as an integer set , Then add non integer elements to this set , Or add integer elements to this set, so that the number of elements is too large , Will perform the encoding conversion of the set .

Transfer all elements originally saved in the integer set to the hash table , And the encoding of the set is changed from an integer set to a hash table . however , Remove non integer elements from the set , Or reduce the number of integer elements , A set encoded by a hash table will not be converted to an integer set .

for instance , Let's first create a set encoded by an integer set ：

Log in and copy

127.0.0.1:6379> sadd one-more-set 1 2 3 4 5
(integer) 5
127.0.0.1:6379> smembers one-more-set
1) "1"
2) "2"
3) "3"
4) "4"
5) "5"
127.0.0.1:6379> object encoding one-more-set
"intset"

     

      
1.
      
2.
      
3.
      
4.
      
5.
      
6.
      
7.
      
8.
      
9.
      
10.
     

then , Add two more string elements to it , It is converted to hash table encoding ：

Log in and copy

127.0.0.1:6379> sadd one-more-set one more
(integer) 2
127.0.0.16379> smembers one-more-set
1) "one"
2) "5"
3) "1"
4) "2"
5) "more"
6) "4"
7) "3"
127.0.0.1:6379> object encoding one-more-set
"hashtable"

     

      
1.
      
2.
      
3.
      
4.
      
5.
      
6.
      
7.
      
8.
      
9.
      
10.
      
11.
      
12.
     

then , Then remove the two string elements from the collection , The encoding of the set is still a hash table ：

Log in and copy

127.0.0.1:6379> srem one-more-set one more
(integer) 2
127.0.0.1:6379> smembers one-more-set
1) "5"
2) "1"
3) "2"
4) "4"
5) "3"
127.0.0.1:6379> object encoding one-more-set
"hashtable"

     

      
1.
      
2.
      
3.
      
4.
      
5.
      
6.
      
7.
      
8.
      
9.
      
10.
     

summary

stay Redis in , The internal implementation of the set has an integer set （intset） Hash table （hashtable） Two kinds of , When all elements in the set are integers and the number of elements is small , Use the integer set as the internal implementation , Otherwise, use the hash table as the internal implementation . When conditions are not met , An integer set can be converted to a hash table , But the hash table cannot be converted to an integer set .

---

I've seen it here , You and I must be predestined friends , Leave your give the thumbs-up and Focus on , It will become a great thing in the future .