Write articles carefully and share with your heart.

Personal website: Yasinshaw.com

Public number: XY’s technical circle

In the past, we simply used the basic data types and interfaces provided by Redis without delving into its underlying data structures. Recently, I plan to relearn and comb the knowledge of Redis, so I plan to start with introducing the basic types of Redis and its data structure.

redisObject

The key of Redis is the top-level model, and its value is flat. In Redis, all values are an object, and its structure is as follows:

typedef struct redisObject {
    unsigned [type] 4;
    unsigned [encoding] 4;
    unsigned [lru] REDIS_LRU_BITS;
    int refcount;
    void *ptr;
} robj;
Copy the code

A brief introduction to these fields:

  • Type: data type, such as string, hash, list, etc.
  • Encoding: Internal encoding, which is the data structure covered in this article. It refers to the data structure underlying the current value. Because there are multiple implementations of data structures underlying the same data type, you need to specify the data structure here.
  • REDIS_LRU_BITS: the length of time the current object can be retained. We’ll talk about that later when we talk about expiration policies for keys.
  • Refcount: Object reference count for GC.
  • PTR: pointer to the actual address of the object implemented in encoding.

string

Inside Redis, the string type has two underlying storage structures. Redis will automatically select the appropriate structure according to the stored data and the user’s operation instructions:

  • Int: stores integer types.
  • SDS: stores floating point, string and byte types;

SDS: simple dynamic string simple dynamic string

SDS

Internal data structure of SDS:

typedef struct sdshdr {
    // The length of characters already occupied in buf
    unsigned int len;
    // The length of the remaining available characters in buf
    unsigned int free;
    // Data space
    char buf[];
}
Copy the code

As you can see, the underlying layer is a char array. Buf has a maximum capacity of 512 MEgabytes, which can hold strings, floating point numbers, and bytes. So you can even put a serialized image. Why doesn’t it just use arrays instead of wrapping data structures like this?

Because buF will have the need to dynamically expand and shrink. If you use arrays directly, each modification to the string will result in an inefficient reallocation of memory.

The expansion process of BUF is as follows:

  • If len is less than 1M, then the same size is assigned to Free. For example, if len is 10 bytes, then the same size is assigned to Free. The actual length of BUF becomes 10 + 10 + 1 = 21bytes
  • If len is greater than or equal to 1 MB, then 1 MB is allocated to Free. For example, if len is changed to 30 MB, 1 MB is allocated to Free. The actual buF length is 30 MB + 1 MB + 1 MB

Lazy space free refers to the fact that when the string is shortened, it does not actually shrink, but instead moves the pointer to free. This eliminates the need to reallocate memory in the future when the string length increases. But this can be a waste of memory, and Redis provides apis to actually free up memory.

list

There are two data structures underlying list: linkedList and ziplist. Use Ziplist when the list has a small number of elements and the element content is small, otherwise use LinkedList.

The list

The linked list Redis uses is a bidirectional linked list. For ease of operation, a list structure is used to hold the linked list. As shown in the figure:

typedef struct list{
    // Table header node
    listNode *head;
    // Table end node
    listNode *tail;
    // The number of nodes in the linked list
    unsigned long len;
    // Node value copy function
    void *(*dup)(void *ptr);
    // Node value release function
    void* (*free) (void *ptr);
    // Node value comparison function
    int (*match)(void *ptr,void *key);
}list;
Copy the code

Data is actually a pointer. The element inside the list is the string described above. Because it is a bidirectional list, you can easily use it as a stack or queue.

List of compression

A compressed list, in contrast to the linked list above, is a bit like an array, storing data in a contiguous memory space. However, it differs from arrays in that it allows different sizes of data to be stored. Add a length attribute to each node to record the length of the node, which is easier to get the location of the next node.

The meanings of the fields in the figure above are:

  • Zlbytes: indicates the total length of the list
  • Zltail: Points to the last element
  • Zllen: number of elements
  • Entry: The content of the element, which records the length of the previous entry and is used for two-way traversal
  • Zlend: constant 0xFF as the ziplist delimiter

Compressed lists are not just the underlying implementation of lists, but one of the underlying implementations of hash. When the hash element number is small and the content length is small, a compressed list is used.

hash

There are two underlying implementations of hash: compressed lists and dictionaries. Now that the compressed list has been introduced above, let’s focus on the dictionary data structure.

The dictionary

Dictionaries are similar to Maps in Java and dict in Python. Similar to HashMap in Java, Redis uses hash tables as dictionary implementations, and hash conflicts are resolved using linked list methods. Redis also uses a data structure to hold the hash table:

When keys are added or decreased, the system expands or shrinks the capacity and rehashes the index value based on the hash value. So what if the dictionary is too big?

To solve the problem that it takes too much time to perform capacity expansion at a time, you can perform capacity expansion in batches during the insertion process. When the load factor reaches the threshold, only new space is requested, but the old data is not moved to the new hash table. When there is new data to insert, the new data is inserted into the new hash table and a data from the old hash table is placed into the new hash table. Repeat the process each time you insert data into the hash table. After many inserts, the data in the old hash table is moved to the new hash table bit by bit. Without a single, centralized data move, insertions are fast. This process is also known as progressive rehash.

set

There are no duplicate sets in set. The implementation of set is relatively simple. If it is an integer type, use the integer set intset directly. It’s pretty fast to use binary lookup to help. But when you insert, because you’re moving elements, it’s order N.

If it is not an integer type, use the dictionary described above in the Hash section. Key is the value of set, and value is null.

zset

Zset is a sortable set. Similar to hash, if the number of elements is small and small, the ziplist is used to store them. However, because Zset contains the ranking information of score, it is stored in ziplist according to the increasing ranking of score. This means that every time you insert data, you move the data after it.

Jump table

Skiplist is another data structure that implements dict. Skip lists are an enhancement to linked lists. When we use a linked list, even if the elements are arranged in order, if we want to find an element, we need to search from the beginning, the time complexity is O(N). As the name suggests, the skip table is a jump of some elements, can be abstract layers.

As shown in the figure below, for example, if we want to find 8, we first search L2 at the top layer and find that it is between 1 and 9. Then go to L1 to search, found between 5 and 9; And then I go to L0, and I find it between 7 and 9, and I find 8.

When there are many elements, using a hop table can significantly reduce the number of lookups.

Like list, Redis uses a custom data structure to hold a hop table instead of a direct hop table. Skiplist is shown in blue on the left, and zSkiplistNodes are shown on the right. ZskiplistNode has many layers L1, L2, etc., and Pointers to the next node in this layer. BW is a back pointer (BACKWARD) used to back up when looking. And then the score and the object itself.

conclusion

Redis exposes objects (data types), and each object is held by a redisObject, mapped to a different data structure through a different encoding. As you can see from the first diagram, sometimes different objects may use the same underlying data structure, such as compressed lists and dictionaries.

Once we understand the data structure, we will have a better idea of what objects to choose and how to optimize when problems arise.

Refer to the article

This article mainly refers to the Redis series of articles written by blogger “Cliff Edge Xiao Sheng”. Blog links:

www.cnblogs.com/hunternet/t…

Concern public number: XY’s technical circle