preface

This chapter picks up where we left off with the Hash dictionary in Redis’ underlying data structure.

Basic introduction

Hash can also be used to store user information. Unlike String, which serializes all of the user’s fields, Hash can be stored individually. String retrieves the user as a whole String, whereas hash retrieves only part of the data to save network traffic. However, hash has a larger memory footprint than String, which is a disadvantage of hash.

> hset books java "Effective java"
(integer) 1
> hset books golang "concurrency in go"
(integer) 1
> hget books java
"Effective java"
> hset user age 17
(integer) 1
>hincrby user age 1	The incR command is used to count a single key
(integer18)Copy the code

Hash in Redis is more similar to Java HashMap, which is an array + linked list structure. Elements are appended to the list when a hash collision occurs. Note that value can only be a string in Redis Hash.

internals

After the basic introduction, let’s take a look at the internal structure of hash. The first dimension is an array, and the second dimension is a linked list. Form a Hashtable.

Partial source code:

struct dictht {
    dictEntry **table;	        / / array entry
    long size;			// Array length
    long used			// The number of elements in the array. }struct dictEntry{
    void *key;		        / / the hash key
    void *val;		    	/ / the hash value
    dictEntry *next;	        // The next dictEntry structure
}
Copy the code

In Java, HashMap expansion is a time-consuming operation that requires the application of new arrays. In order to pursue high performance,Redis adopts a progressive Rehash strategy. This is also the most important part of hash.

Progressive rehash

There are two hashtables inside the hash, usually just one. As shown in the figure:

Redis migrates the contents of the old hashtable into the new hashtable bit by bit, and when the migration is complete, the new hashtable will be used Hashtable replaces the previous one. When the last element of the HashTable is removed, the data structure is deleted. As shown in the figure:

The data move operation is placed in the subsequent instruction of the hash, which is the instruction operation from the client to the hash. Redis uses scheduled tasks to actively move data once the client has no subsequent instructions to operate on the hash.Redis.

Normally, when the number of elements in the Hashtable is equal to the length of the array, expansion begins, and the new array is twice the size of the original array. If Redis is doing BGSave (persistence), it probably won’t be expanded to reduce excessive Copy On Write of pages in memory. However, if the Hashtable is very full and the number of elements has reached 5 times the array length,Redis will force it to expand.

When the number of elements in a Hashtable becomes smaller,Redis shrinks to reduce the space footprint, and is not affected by BGSave, if the number of elements is less than 10% of the array length.