How to implement the five data structures of redis at the underlying level

Implementation method: 1. Each data structure has its own underlying internal encoding implementation, and there are multiple implementations, so that Redis will choose the appropriate internal encoding in the appropriate scenario; 2. Each data structure has There are more than two internal encoding implementations; 3. Internal encoding can be used as an internal implementation of a variety of external data structures.

The operating environment of this tutorial: Windows 7 system, Redis version 5.0.10, DELL G3 computer.

Redis has five basic data structures: string, hash, set, zset, and list. The following explains how the bottom layer implements them in downloading Redis 3.0.6 version.

To summarize

(1) Each data structure has its own underlying internal coding implementation, and there are multiple implementations, so that Redis will choose the appropriate scenario Appropriate internal encoding.

(2) You can see that each data structure has more than two internal encoding implementations. For example, the string data structure includes three internal encodings: raw, int and embstr.

(3) At the same time, some internal encodings can be used as internal implementations of various external data structures. For example, ziplist is an internal encoding common to hash, list, and zset.

Dynamic String SDS

SDS is the abbreviation of "simple dynamic string". The strings that appear in all scenarios in Redis are basically implemented by SDS:

• All non-numeric keys, such as: key msg

  in set msg "hello"

• Values ​​of string data type, such as: value "hello" in set msg "hello"

• " character in non-string data type String value", such as: rpush fruits "apple" "apple" in "banana" "banana"

##The SDS looks like this:

free: How much space is left

len: String length

buf: Stored character array

Space pre-allocation

In order to reduce the number of memory reallocations of the modified string agent, SDS adopts the "one-time management is enough" strategy:

• If the SDS length after modification is
• If the SDS length >= 1MB after modification, the expansion will not only meet the modified length, but also have an additional 1MB space.

Lazy space release

In order to avoid memory reallocation operations when shortening strings, SDS does not release space immediately when the data is reduced. .

int

is the various numbers stored in redis, including the

set game "111" intentionally added with "" ”

##Double linked listDouble linked list such as lpush, rpush, lpop, rpop

looks like this:

is divided into two parts:

"Coordination part": orange

• head: points to the head of a specific doubly linked list
  tail: Points to the tail of a specific doubly linked list
  len: The length of the doubly linked list

  "Specific implementation": blue
• There is a predecessor pre and a successor next

The doubly linked list consists of list and listNode. Data structure composition.

Recommended related tutorials:

Redis Tutorial

The above is the detailed content of How to implement the five data structures of redis at the underlying level. For more information, please follow other related articles on the PHP Chinese website!