preface

<< Redis design and implementation >>, read a book to learn knowledge, take notes, deepen the understanding of knowledge.

The dictionary

A dictionary is a data structure in Redis. In the dictionary, a key corresponds to a value, which is called a key-value pair (the dictionary has multiple key-value pairs). The bottom layer of Redis is developed by C language, and there is no dictionary itself, so Redis encapsulates the data structure of a dictionary.

implementation

The bottom layer of the dictionary is implemented by the hash table, so the overall order should be introduced in descending order.

Hash table

Dictionary data structure:

  1. Type Type specific function
  2. Private Private data
  3. Ht [2] a hash table
  4. Rehashidx is -1 if the rehash is not in progress

The structure of a hash table includes:

  1. Table Hash table array
  2. Size Size of the hash table
  3. Sizemask Specifies the sizemask of the hash table, used to calculate index values. Sizemask = size-1
  4. Used Indicates the used node of the hash table

Hash table node data structure:

  1. The key key
  2. V value
  3. Next Indicates the address of the next node

As shown below:

When we add a key-value pair to the dictionary, we pass in the key and hash it according to the algorithm (MurmurHash2), and then perform the ampersand operation with Sizemask to calculate the added index.

As the operation continues, the number of keys stored in the hash table increases or decreases. In order to keep the load factor within a reasonable range, rehash is performed. Any condition is automatically rehash:

  1. The server does not run the BGSAVE or BGREWRITEAOF command and the load factor is greater than or equal to 1.
  2. The server runs the BGSAVE or BGREWRITEAOF command when the load factor is greater than or equal to 5.
  3. Rehash is performed when the load factor is less than 0.1.

Load factor: the number of nodes the hash table holds/the size of the hash table.

Rehash it is progressive because if ht[0] has too much data, direct transfer to HT [1] will result in a period of service interruption.

A progressive process:

  1. If ht[1] is allocated and rehashidx is set to 0, hash is being performed
  2. During rehash, dictionaries are added, deleted, and modified, and h[1] is also modified once, rehashidx + 1 is modified once
  3. As the dictionary continues to operate, eventually the key-value pair of H [0] is migrated to H [1], and rehashidx is changed to -1 to end the rehash.

Leave a summary of the book at the end

Refueling efforts to point out any problems and timely correction.