Preface

Redis Is a key value pair database , The key is stored by hash . Whole Redis It can be thought of as an outer hash , It is called outer hash , Because Redis A hash type is also provided internally , This can be called an internal hash . When we use hash objects for data storage , To the whole Redis for , It goes through two layers of hash storage .

Hash object

The hash object itself is also a key-value Storage structure , The underlying storage structure can also be divided into two types :ziplist( Compressed list ) and hashtable( Hashtable ). These two storage structures are also distinguished by coding :

Encoding properties describe object encoding Command return value
OBJ_ENCODING_ZIPLIST Hash objects using compressed lists ziplist
OBJ_ENCODING_HT Hash objects using dictionaries hashtable

hashtable

Redis Medium key-value It's through dictEntry Object wrapped , And the hash table is to put dictEntry The object is packaged again to get , This is the hash table object dictht

typedef struct dictht {
dictEntry **table;// Hash table array
unsigned long size;// Hash table size
unsigned long sizemask;// Mask size , Used to calculate index values , Always equal to size-1
unsigned long used;// The number of existing nodes in the hash table
} dictht;

Be careful : In the above structure definition table Is an array , Each of its elements is a dictEntry object .

Dictionaries

Dictionaries , Also known as the symbol table (symbol table), Associative array (associative array) Or map (map), A hash table is nested inside the dictionary dictht object , Here's a dictionary ht The definition of :

typedef struct dict {
dictType *type;// Some specific functions of dictionary type
void *privdata;// Private data ,type You may need to use
dictht ht[2];// Hashtable ( Notice that there is 2 Hash table )
long rehashidx; //rehash Indexes , be not in rehash when , The value is -1
unsigned long iterators; // Number of iterators in use
} dict;

among dictType Some common functions are defined internally , Its data structure is defined as follows :

typedef struct dictType {
uint64_t (*hashFunction)(const void *key);// Compute hash function
void *(*keyDup)(void *privdata, const void *key);// Copy key functions
void *(*valDup)(void *privdata, const void *obj);// Copy value function
int (*keyCompare)(void *privdata, const void *key1, const void *key2);// Contrast the bond function
void (*keyDestructor)(void *privdata, void *key);// Destroy key functions
void (*valDestructor)(void *privdata, void *obj);// Destroy the value function
} dictType;

When we create a hash object , You can get the following diagram ( Some attributes are omitted ):

rehash operation

dict An array is defined in ht[2],ht[2] Two hash tables are defined in :ht[0] and ht[1]. and Redis By default, only ht[0], It doesn't use ht[1], Not for ht[1] Initialize allocation space .

When setting a hash object , It's going to be a hash array ( In the picture above dictEntry[3]) Which subscript in , It's determined by calculating the hash value . If there is a hash collision ( The calculated hash values are consistent ), Then there will be more than one subscript dictEntry, So as to form a linked list ( The far right in the picture above points to NULL The location of ), However, it should be noted that the last element inserted is always at the top of the list ( When a hash conflict occurs , Always put the node at the head of the list ).

When reading data, we encounter a node with multiple elements , You need to traverse the linked list , So the longer the list , The worse performance . To ensure the performance of the hash table , When one of the following two conditions is satisfied , Do... On the hash table rehash( Re hash ) operation :

  • The load factor is greater than or equal to 1 And dict_can_resize by 1 when .
  • The load factor is greater than or equal to the security threshold (dict_force_resize_ratio=5) when .

PS: Load factor = Number of nodes used by hash table / Hash table size ( namely :h[0].used/h[0].size).

rehash step

Both extended hashes and contracted hashes are executed by rehash To complete , This involves the allocation and release of space , There are five steps :

  1. For the dictionary dict Of ht[1] Hash table allocation space , Its size depends on the number of saved nodes in the current hash table ( namely :ht[0].used):

    • If it is an extension operation, then ht[1] The size is 2 Of n The first of the powers is greater than or equal to ht[0].used * 2 The value of the property ( such as used=3, here ht[0].used * 2=6, so 2 Of 3 The second party is 8 The first one is greater than used * 2 Value (2 Of 2 Power < 6 And 2 Of 3 Power > 6)).
    • If it is a contraction operation, then ht[1] The size is 2 Of n The first of the powers is greater than or equal to ht[0].used Value .
  2. Put the attributes in the dictionary rehashix Is set to 0, It means that it is executing rehash operation .

  3. take ht[0] All key value pairs in the hash are recalculated in turn , And on the ht[1] Array corresponding position , Every time you complete a key value pair rehash after rehashix The value of needs to increase 1.

  4. When ht[0] All key value pairs in are migrated to ht[1] after , Release ht[0] , And will ht[1] It is amended as follows ht[0], Then create a new one ht[1] Array , For the next time rehash To prepare for .

  5. Put the attributes in the dictionary rehashix Set to -1, This time rehash End of operation , Wait for the next time rehash.

Progressive type rehash

Redis This rehashing operation in Because it's not all at once rehash, It's a lot of times, slowly ht[0] Key value pairs in rehash To ht[1], So this kind of operation is also called progressive rehash. Progressive type rehash You can avoid centralization rehash The huge amount of computation , It's the idea of divide and rule .

In a progressive way rehash In the process , Because there may be new key value pairs saved in , here ** Redis The new method is to put the newly added key value pairs into ht[1] in , This ensures that ht[0] The number of key value pairs will only decrease **.

When executing rehash In operation , If the server receives a command from the client requesting operation , be We'll check ht[0], I can't find the result, and then I go to ht[1] Query in .

ziplist

About ziplist Some characteristics of , Previous articles have analyzed it separately , Want to know more about , Sure Click here . But note that in the hash object ziplist And list objects ziplist The difference is that the hash object is a key-value form , So its ziplist It is also shown in key-value,key and value Close together :

ziplist and hashtable Code conversion of

When a hash object can satisfy either of the following two conditions , The hash object will choose to use ziplist Code to store :

  • The total length of all key value pairs in the hash object ( Including keys and values ) Less than or equal to 64 byte ( This threshold can be determined by the parameter hash-max-ziplist-value To control ).
  • The number of key value pairs in the hash object is less than or equal to 512 individual ( This threshold can be determined by the parameter hash-max-ziplist-entries To control ).

If either of these two conditions is not satisfied , The hash object will choose to use hashtable Code for storage .

Common commands for hash objects

  • hset key field value: Set individual field( Hash object key value ).
  • hmset key field1 value1 field2 value2 : Set up multiple field( Hash object key value ).
  • hsetnx key field value: Hash table key Mesosphere field Is set to value, If field Already exists , Do nothing .
  • hget key field: Get hash table key In the domain field Corresponding value.
  • hmget key field1 field2: Get hash table key Multiple domains in field Corresponding value.
  • hdel key field1 field2: Delete hash table key One or more of field.
  • hlen key: Return hash table key Number of domains .
  • hincrby key field increment: Hash table key In the domain field Plus the increment increment ,increment Can be negative , If field If it's not a number, it will report an error .
  • hincrbyfloat key field increment: Hash table key In the domain field Plus the increment increment,increment Can be negative , If field No float Type will report an error .
  • hkeys key: Get hash table key All domains in .
  • hvals key: Get the values of all fields in the hash table .

Learn about common commands for manipulating hash objects , We can verify the type and encoding of the hash object mentioned above , Before testing, in order to prevent other key The interference of values , Let's do it first flushall Command clear Redis database .

Then execute the following commands in turn :

hset address country china
type address
object encoding address

The results are as follows :

You can see that when there is only one key value pair in our hash object , The underlying code is ziplist.

Now we will hash-max-ziplist-entries Change the parameter to 2, And then restart Redis, Finally, enter the following command to test :

hmset key field1 value1 field2 value2 field3 value3
object encoding key

After output, we get the following result :

You can see , Coding has become hashtable.

summary

This paper mainly introduces Redis in 5 Hash type is one of the most commonly used data types, and the underlying storage structure hashtable Use , And when hash When the distribution is uneven Redis It's about how to rehash , Finally, we learned about some common commands of hash objects , Some examples are given to verify the conclusion .

Redis In the hash distribution is not uniform how to do more related articles

  1. Redis Hash in (Hash)

    Redis Hash (Hash) Redis hash It's a string Type of field and value Mapping table ,hash Ideal for storing objects . Redis Each of them hash Can be stored 232 - 1 Key value ...

  2. redis Medium key Set expiration time

    EXPIRE key seconds For a given   key   Set the lifetime , When   key   expires ( Survival time:   0  ), It will be automatically deleted . stay Redis in , With time to live   key   go by the name of 『 Volatile ...

  3. About Redis Data types in

    One . Redis Common data types Redis The most commonly used data types are as follows : String Hash List Set Sorted set A picture shows the nature of the problem Figure 1 : Figure 2 : Code : /* Object ...

  4. Fast sync mysql Data to redis in

    MYSQL Quickly synchronize data to Redis For example, the scene : Store player's mission data , When the game server starts, it will mysql The player's data is synchronized to redis in . from MySQL Import data into Redis Of Hash In structure . Of course , Most direct ...

  5. Large batch deletion redis It's useless key+ To configure

    At present, there is a single instance online redis It's useless key Too much , Decided to delete part of . 1. Delete the key, Use redis Of pipeline According to certain conditions, count out the users that need to be deleted , Put it in a table , The table is del_use ...

  6. Redis Data objects in

    redis object redis There are five common objects in Most of the object types we talk about are value types , Most of the key types are string objects , There are several types of value , But either is based on redisObject Realized redisObjec ...

  7. Redis The basic data structure in

    Redis Infrastructure Infrastructure sds Simple dynamic string data structure typedef struct sdstr{ int len // Bytes allocated by string int free // Number of unused bytes cha ...

  8. Redis Data types and basic operations in

    Redis The built-in data types are 5 Kind of : character string String. Hash Hash. list List. aggregate Set. Ordered set ZSet String type String yes Redis The most basic type in , One key Corresponding to a v ...

  9. redis-cli Through pipes --pipe Quickly import data into redis in

    There's a need recently , We need to write 50 million pieces of data in batches redis in , There are many ways ! The most efficient way is through redis-cl Write in a pipeline way One : First look at the order cat redis.txt | redis-cli -h 12 ...

  10. redis Summary of common operation methods of various data types in

    stay spring Use in jedisTemplate operation , See https://www.cnblogs.com/EasonJim/p/7803067.html One .Redis Five data types of 1.String( ...

Random recommendation

  1. 『SQL Inject 』 User-Agent Detection and utilization analysis of manual injection

    The principle is simple : The background is receiving UA There is no right time UA Filter it , either PDO Data interaction ( actual PDO It's very necessary ), Lead to UA There's malicious code in , Finally, it is executed in the database . Bug Code : It's a local environment ,Bug Code section : ...

  2. Android_Studio And SDK download

    Android Studio includes all the tools you need to build apps for Android. DOWNLOAD ANDROID STUDIO 2. ...

  3. haproxy Configure monitoring redis Active standby switching ( turn )

    Environment premise :     redis sentinel To configure , Three hosts , And the configuration runs well        Add... To the configuration file : frontend ft_redis  bind 0.0.0.0:6379 name re ...

  4. so far .Net The most powerful platform , The best performance JSON Serialization and deserialization Libraries .

    Swifter.Json This is so far .Net The most powerful platform , The best performance JSON Serialization and deserialization Libraries . Github : https://github.com/Dogwei/Swifter.Js ...

  5. Spring Cloud Turbine Real time monitoring of microservice cluster

    Code download address : https://gitlab.com/mySpringCloud/turbine SpringBoot edition :1.5.9.RELEASE ( Stable version ) SpringCloud edition :Ed ...

  6. MySQL database Simple operation command ( Part summary )

    1. View process view database ps - ajx|grep mysql 2. Sign in MySQL mysql -u user name -p password 3. Opening service sudo service mysql start 4. Out of Service ...

  7. Jmeter( Twenty-four )Jmeter-Question And “ Encryption request parameters ”

    There are many cases of parameter encryption in daily interface testing , Of course, the opposite is decryption . Record instances directly : Exclude the different encryption methods of each household , The most used is MD5 encryption (16,32).Jmeter3.2 Version already has a solution 1.${__ ...

  8. orm Exercises

    One : Multi table practice query 1. Create your own test data : 2. Check the total number of students : 3. Inquire about “ biological ” Courses and “ Physics ” Students who have passed the course id And name : 4. Query the number of classes in each grade , Take out the top three grades with the largest number of classes : 5. ...

  9. UVA.10474 Where is the Marble ( Sort Two points search )

    UVA.10474 Where is the Marble ( Sort Two points search ) Problem analysis A big water topic . Sort to find the position of the first target number , Return its subscript . Violence is more than , Forced to write a BS, There are lots of mistakes . Should be ...

  10. Use Mybatis Times wrong Invalid bound statement (not found):

    Generated when using reverse engineering .xml The file in conf Under the table of contents , When using the query method , Cannot be in dao Find... Under the bag xml file , So wrong reporting . The test code is as follows : @Test public void testSimple() thr ...