What is the principle of Redis data structure?

RedisDb

The Redis server has 16 databases by default, and one database corresponds to one RedisDB data structure.

typedef struct redisDb {
    dict *dict;
    dict *expires;
    dict * blocking_keys;
    dict * ready_keys;
    dict * watched_keys;
    ......
}

• dict: key space hash table, used to store all key-value pairs

• expires: expiration time hash table, used to store the expiration of keys Time

• blocking_keys: keys in blocked state and corresponding client

• ready_keys: keys in unblocked state and corresponding client, and blocking_keys The attributes are relative

• watched_keys: watch key and corresponding client, mainly used for transactions

RedisObject

Redis key The values ​​are all redisObject objects. Every time we create a new key-value pair in the Redis database, a redisObject object for the key name and a redisObject object for the key value will be generated

trpedef struct RedisObject {
    int4 type;
    int4 encoding;
    void *ptr;
    int24 lru;
    int32 refcount;
}

Field	Description	Explanation
type	is used to represent the type corresponding to Redis	String, list, hash, set, zset, stream, etc. are represented by enumerations
encoding	Internal encoding	int , embstr, raw, hashtable, quicklist, ziplist, intset, skiplist, etc., represented by enumeration
lru	24 bits, optional LFU or LRU	When it is LRU, it represents the last access time; when it is LFU, the high 16 bits are used to represent the access time at the minute level, and the low 8 bits are used to represent the access frequency. The increase in frequency uses a probability algorithm, the base The larger it is, the harder it is to increase; when the access time is updated, there is a certain probability that the access frequency will be attenuated. (Common to both) Access time is a modulo of a number, and the current time is also modulo. If the current time is greater than the access time, it is the difference between the two numbers; if the current time is less than the access time, it is the current time plus the modulus and the access time. The difference
refcount	Reference count	The initial value is 1, which is of little reference significance in practical applications
ptr	Pointer, occupies 8 bytes, points to the address of the data	dict, expires, etc., the pointer points to the same address

object command is the related operation on RedisObject.

Modify the memory elimination strategy

object idletime key # Returns the idle time of the key, that is, the approximate description of the time since the last time the key was read and written. It is not available in lfu mode

config set maxmemory-policy volatile-lfu # 修改内存淘汰策略
set name zhangsan
object freq name # 获取计数值，仅lfu模式下可用，初始化为5

get name

object freq name # 再次访问，返回为6

int

When the string value is an integer and is less than or equal to the maximum value of long, the encoding is int type, and ptr directly points to the int type address

embstr and raw

Redis The string is called SDS (Simple Dynamic String, simple string), corresponding to the key, non-integer String value

trpedef struct SDS {
    int8 capacity; // 数组容量
    int8 len; // 实际长度
    int8 flags;
    byte[] content; // 数组内容
}

It can be seen that SDS is similar to Java's ArrayList structure, and it is also Allocate an initial length and expand it when the length exceeds. Redis stipulates that the length of the string cannot exceed 512M.

When the length is particularly short, use embstr form to store; when the length exceeds 44 bytes, use raw form to store.

It is known that the maximum allocation unit of the memory allocator is 64 bytes, RedisObject occupies 16 bytes, the SDS identifier occupies 3 bytes, and a string ending with NULL requires one byte, so when the string length When it is less than or equal to 44, memory only needs to be allocated once. RedisObject and SDS are in the same memory unit. We call this data structure embstr, while those that are not in the same memory unit are called raw.

dict

dict (encoding is hashtable type, dictionary) corresponds to hash, set, zset (used to store the mapping between value and score) collection.

dict is similar to Java's HashMap structure. The difference is that HashMap expansion requires an array, then traverses it, re-hashes the old data and hangs it under the array. As a single-threaded Redis, it is difficult To withstand such a time-consuming process, it uses two arrays, returns first, and then moves the data bit by bit when it is free. After the move is completed, the old data is cleared. We call this process progressive rehash .

typedef struct dict {
    dictht ht[2];
}

The above is the detailed content of What is the principle of Redis data structure?. For more information, please follow other related articles on the PHP Chinese website!