Redis Basic Series (4) – Hash objects

This is the 8th day of my participation in Gwen Challenge

1. Introduction to hash objects

In Redis, hash type refers to the key value itself is a key-value pair structure, such as value={{field1, value1},… {fieldN, valueN}} instead! In Redis, each hash key can store 223−12^{23}-1223−1 key-value pairs.

Common command used to hash objects

HDEL key field2 [field2] // Delete one or more hash table fields
HEXISTS key field // Check whether the specified field exists in the table key.
HGET key field // get the value of the specified field stored in the hash table /td>
HGETALL key // Get all fields and values of the specified key in the hash table
HINCRBY key field increment Increment increment increment increment increment increment increment increment increment increment increment increment increment
HINCRBYFLOAT key field increment Increment increment increment increment increment increment increment increment increment increment increment increment increment
HKEYS key // Get all the fields in the hash table
HLEN key // Get the number of fields in the hash table
HMGET key field1 [field2] // Get the values of all the given fields
HMSET key field1 value1 [field2 value2 ] // Set multiple field-value pairs to hash key at the same time.
HSET key field value // Set the hash table key field to value.
HSETNX key field value // Set the value of the hash table field only if field does not exist.
HVALS key // Get all the values in the hash table
HSCAN key cursor [MATCH pattern] [COUNT count] // Iterate over the key-value pairs in the hash table.
Copy the code

2. Hash object coding

There are two internal encodings of hash objects: Ziplist and Hashtable.

• ziplist(Compressed list) : when the hash object element number is less thanhash-max-ziplist-entriesThe default value is 512, and the length of all values is less than or equal tohash-max-ziplist-value When configured (64 bytes by default), it is used internally by RedisziplistEncoding stores hash objects. Each time a new key-value pair is added to the hash object, the program pushes the compressed list node holding the key to the end of the compressed column table, and then pushes the compressed list node holding the value to the end of the compressed column table.
  • Two nodes that store the same key-value pair are always next to each other, with the key-saving node coming first and the value-saving node coming second.
  • Key-value pairs added to the hash object first are placed at the head of the compressed list, while key-value pairs added to the hash object later are placed at the tail of the compressed list.
• hashtable(dictionary) : When the hash type cannot be satisfiedziplistCondition when Redis is usedhashtableAs an internal implementation of hashing, because ziplist’s read and write efficiency will be reduced, whilehashtableIs O (1).

3. Compress lists

Compressed list is a sequential data structure composed of a series of specially coded contiguous memory blocks developed by Redis to save memory.

3.1 Compressed list Composition

A compressed list can contain any number of entries, each of which can hold either a byte array or an integer value. The following shows the components of the compressed list.

3.2 Composition of compressed list nodes

Each compressed list node can hold either a byte array or an integer value

There are three types of byte array lengths

• Length less than or equal to63(
  $2 ^ {6} – 1$) byte array of bytes;
• Length less than or equal to16383 （
  $2 ^ {14} – 1$) byte array of bytes;
• Length less than or equal to4294967295 （
  $2 ^ {32} – 1$) byte array of bytes;

Integer values can have any of the following six lengths

• 4Bit length, between0 至 12An unsigned integer between;
• 1Signed integer long in bytes;
• 3Signed integer long in bytes;
• int16_tType integer;
• int32_tType integer;
• int64_tType integer.

Each compressed list node consists of previous_entry_LENGTH, Encoding, and Content.

3.2.1 previos_entry_lengthattribute

Previos_entry_length Records the length of the previous node in the compression list in bytes. The length of the previOS_entry_length property can be 1 or 5 bytes

• If the previous node is less than 254 bytes,previos_entry_lengthThe length is 1 byte
• If the previous node is 254 bytes or longer,previos_entry_lengthThe length is 5 bytes

The previOS_entry_length attribute enables ziplist traversal from the end of a table to the beginning of a table.

3.2.2 encodingattribute

The encoding property of the node records the type and length of the data held by the node’s Content property:

• The byte array encoding is one, two, or five bytes long, with the highest bit being 00, 01, or 10. This encoding means that the node’s Content property holds an array of bytes, and the length of the array is recorded by the encoding excluding the highest two bits.

• A byte long, with the highest bit of the value beginning with 11, is an integer encoding: this encoding means that the node’s Content property holds an integer value, whose type and length are recorded by encoding other bits after the highest two bits;

  coding	The length of the code	contentProperty to hold
  11000000	1byte	int16_tType is an integer.
  11010000	1byte	int32_tType is an integer.
  11100000	1byte	int64_tType is an integer.
  11110000	1byte	24Bit signed integer.
  11111110	1byte	8Bit signed integer.
  1111xxxx	1byte	Nodes that use this encoding have no correspondingcontentProperties,xxxxsavecontentvalue

3.2.3 contentattribute

The content property of a node holds the value of the node, which can be a byte array or an integer. The type and length of the value are determined by the encoding property of the node.

3.3 Cascading Updates

In a compressed list, there are multiple contiguous nodes e1 to eN between 250 and 253 bytes in length. Because all nodes e1 to eN are less than 254 bytes long, recording the length of these nodes requires only the 1-byte previous_entry_length attribute, in other words, The previous_entry_length attribute of all nodes from E1 to eN is 1 byte long.

If we set a new node new, 254 bytes or more long, as the head of the compressed list, then new will be the front node of E1, because e1’s previous_entry_length property is only 1 byte long, There is no way to store the length of the new node, so the program will redistribute the compressed list and expand the e1 node’s previous_entry_length property from 1 byte to 5 bytes.

Now, here’s the trouble — E1 was between 250 and 253 bytes long, but after adding four bytes of space to the previous_entry_length property, E1 was between 254 and 257 bytes long. This length cannot be saved using the 1-byte previous_entry_length attribute.

So, in order for e2’s previous_entry_length property to record E1’s length, the program needs to redistribute the compressed list again. The previous_entry_length attribute of e2 node is extended from 1 byte to 5 bytes.

Just as extending E1 caused an extension to E2, extending e2 caused an extension to E3, which in turn caused an extension to E4… In order for the previous_entry_length attribute of each node to meet the requirements of the compressed list for the node, the program needs to continuously perform space reallocation operations on the compressed list until eN.

This is called a chained update, where a single operation results in multiple consecutive space expansion operations. In addition to adding nodes can cause cascading updates, deleting nodes can also cause cascading updates. Because chained updates require N space reallocations of the compressed list in the worst case, and the worst complexity of each space reallocation is O(N), the worst complexity of chained updates is O(N^2).

Note that despite the complexity of chained updates, the chances of them actually causing performance problems are very low:

• First, the compressed list should have exactly multiple contiguous entries of length between250Bytes to253Cascading updates can only be triggered on nodes between bytes, which is rare in practice.
• Second, even if there are cascading updates, there is no impact on performance as long as the number of nodes being updated is small: for example, cascading updates to three or five nodes have absolutely no impact on performance;

4, the dictionary

Redis dictionary uses hash table as the underlying implementation, a hash table can have multiple hash table nodes, and each hash table node stores each key value in the dictionary.

/ / a hash table
typedef struct dictht{
  // Hash table array
  dictEntry **table;

  // Hash table size
  unsigned long size;

  // Hash table size mask, used to calculate the index value, always equal to size-1
  unsigned long sizemask;

  // The number of existing nodes in the hash table
  unsigned long used;
}dictht;

// hash node
typedef struct dictEntry{
  / / key
  void *key;

  / / value
  union{
    void *val;
    uint64_tu64;
    int64_ts64;
  }v;

  // points to the next hash table node
  struct dictEntry *next;
}dictEntry;

/ / a dictionary
typedef struct dict{
  // A type-specific function for creating polymorphic dictionaries
  dictType *type;

  // Private data
  void *privdata;

  // Hash table, save two hash table structure, when rehash, copy h[0] into h[1]; To end the rehash, point h[0] to h[1] and then empty h[1]
  dictht ht[2];

  // Rehash index. When rehash is no longer being performed, the value is -1
  int rehashidx;
}dict;

typedef struct dictType{
  // The function that calculates the hash value
  unsigned int (*hashFunction)(const void *key);

  // Copy the key function
  void *(*keyDup)(void *privdata, const void *key);

  // Copy the value of the function
  void *(*valDup)(void *privdata, const void *obj);

  // Compare key functions
  int (*keyCompare)(void *privdata, const void *key1, const void *key2);

  // The function that destroys the key
  void (*keyDestructor)(void *privdata, void *key);

  // A function that destroys values
  void (*valDestructor)(void *privdata, void *obj);
}dictType;
Copy the code

4.1 Hash algorithm

Redis calculates hash and index values as follows:

• Compute the hash value of the key using the dictionary set hash function
• hash = dict -> type -> hashFunction(key)
• Sizemask: sizemask: sizemask: sizemask: sizemask: sizemask: sizemask: sizemask: sizemask: sizemask: sizemask: sizemask: sizemask: sizemask: sizemask: sizemask
• Ht [x] can be HT [0] or HT [1], depending on the case.
• index = hash & dict -> ht[x].sizemask

4.2 Resolving key Conflicts

When two or more keys are assigned to the same index of the hash table array, we say they have a collision.

• Four ways to resolve hash conflicts
  • Open address method
    • Linear detection: add one unit of value to the conflicting value until there is no conflict.
    • Square detection method: add 1 square units to the value of the conflict, if the conflict is subtracted 1 square units; Then 2 squared, 3 squared, until there is no conflict.
    • Pseudorandom method: add a random number to the conflicting value until there is no conflict.
  • Chained address: Conflicting values are stored in a function linked list
    • Advantages: simple processing, no accumulation phenomenon, short average search length.
    • Linked list nodes can be expanded at will and are suitable for situations where length cannot be determined.
    • Compared with the open address method, the chain address method saves more space.
  • Establish a public overflow area: Establish a public overflow area to store all conflicting values.
  • Rehash: Hash the conflicting values again until no conflict occurs.

Each hash table node has a next pointer. Multiple hash table nodes can use the NEXT pointer to form a one-way linked list. Multiple nodes assigned to the same index can be connected by this one-way linked list, which solves the problem of key conflict. Because the list of dictEntry nodes has no Pointers to the end of the list, the program always adds new nodes to the head of the list for speed.

4.3 rehash

In order to keep the load factor of the hash table in a reasonable range, when the hash table stores too many or too few key pairs, it needs to expand or shrink the hash table.

• Rehash steps
  • Allocates space for the DICTIONARY’s HT [1] hash table
    • If an extension is performed, the length of HT [1] is greater than or equal to ht[0]. Used * 2 to the 2 power of n
    • If shrink is performed, the size of HT [1] is greater than or equal to ht[0]. Used to the power of 2 n.
  • Rehash the key pair for HT [0] onto HT [1].
  • When all key pairs of HT [0] are rehash to HT [1], release HT [0], set HT [1] to HT [0], and create an empty hash table for HT [1].

• Extension conditions for a hash table
  • The server is not currently executing BGSAVE or BGREWRITEAOF, and the hash table load factor is greater than or equal to 1
  • The server is running the BGSAVE or BGREWRITEAOF command and the hash table load factor is greater than or equal to 5

• The contraction condition of a hash table
  • When the load factor of the hash table is less than 0.1, the program automatically starts to shrink the hash table.

4.4 Progressive Rehash

When there are too many key-value pairs in a hash table, rehashing all of them at once can strain the server and even cause it to stop serving. To ensure that server performance is not affected, rehash is performed repeatedly and incrementally

• Allocate space for HT [1] so that the dictionary holds both HT [0] and HT [1] hash tables.
• If rehashidx is set to 0, rehash is started.
• During rehash, each time a dictionary is added, deleted, found, or updated, the manipulated key pair is rehash and the rehashidx is increments by one. When updating, deleting, and searching are performed on HT [0] and HT [1], adding key-value pairs only operates on HT [1] to ensure that HT [0] is only decreased.
• When ht[0] completes rehash for all key-value pairs, set rehashidx to -1 and rehash ends.