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

This article mainly introduces "how to find the location of key in memory in redis database". In daily operation, I believe many people have doubts about how to find the location of key in memory in redis database. Xiaobian consulted all kinds of information and sorted out simple and easy-to-use methods of operation. I hope it will be helpful for you to answer the doubt of "how to find the location of key in memory in redis database". Next, please follow the editor to study!

First, the knowledge that needs to be known in advance

1. Each database in redis is stored in a redisDb structure. Where redisDb.id stores numbers represented by integers in the redis database. RedisDb.dict stores all the key-value pair data in the library. RedisDb.expires holds the expiration time of each key.

2. When the redis server is initialized, 16 databases are pre-allocated (this number can be configured through the configuration file), and all databases are saved to a member redisServer.db array of the structure redisServer. When we select the database select number, the program switches the database directly through redisServer.db [number]. Sometimes when a program needs to know which database it is in, it can just read redisDb.id.

3. Since we know that all the keys and values of a database are stored in redisDb.dict, we need to know that if we find the location of key, it is necessary to understand the structure of dict:

The copy code is as follows:

Typedef struct dict {

/ / Type-specific handlers

DictType * type

/ / Private data of type handling functions

Void * privdata

/ / Hash table (2)

Dictht ht [2]

/ / A flag that records the progress of rehash. A value of-1 indicates that rehash is not in progress.

Int rehashidx

/ / the number of security iterators currently in operation

Int iterators

} dict

As can be seen from the above structure, redis's dictionary uses a hash table as its underlying implementation. The dict type uses two pointers to the hash table, of which the hash table No. 0 (ht [0]) is mainly used to store all the key values of the database, while the hash table No. 1 is mainly used for the program to rehash the hash table No. 0. Rehash is usually triggered when a new value is added, which will not be overstated here. So finding a key in redis is actually a lookup operation for ht [0] in the dict structure.

4. Since it is a hash, then we know that there will be a hash collision, so what should we do when multiple keys hash for the same value? Redis uses a linked list to store multiple hash collided keys. That is, when the list is found based on the hash value of key, if the length of the list is greater than 1, then we need to traverse the linked list to find the key we are looking for. Of course, the length of the linked list is generally 1, so the time complexity can be regarded as o (1).

Second, when redis gets a key, if you find the location of the key.

With the above knowledge, we can analyze redis if we find a key in memory.

1. After getting a key, redis first determines whether the hash table No. 0 of the current database is empty, that is, if (dict- > ht [0] .size = = 0). Return NULL directly for true.

2. Determine whether the hash table 0 needs rehash, because if rehash is in progress, it is possible for either of the two tables to store the key. If rehash is in progress, the _ dictRehashStep method is called once, and _ dictRehashStep is used to passively rehash the database dictionary, as well as the dictionary of the hash key, which is not discussed here.

3. Calculate the hash table and calculate the hash value according to the current dictionary and key.

4. The index value of the hash table is calculated according to the hash value and the current dictionary.

5. Take out the linked list in the hash table according to the index value, and traverse the linked list to find the location of key. In general, the linked list is 1 in length.

6. When the ht [0] has been searched, the rehash judgment is made again. If it is not in the rehashing, it ends directly, otherwise, the 345 steps are repeated for the ht [1].

At this point, we have found the location of key in memory.

At this point, the study on "how to find the location of key in memory in the redis database" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

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.