Redis (6) -- object and data structure

1, Preface

Redis In order to achieve better results . Such as ： Simple dynamic string 、 Double ended linked list 、 Dictionaries 、 Compressed list 、 Sets of integers and so on .

Redis There is no direct use of these data structures to implement key value pair databases , Instead, an object system is created based on these data structures . This system includes string objects 、 List objects 、 Hash object 、 There are five types of objects: collection objects and ordered collection objects . One of the benefits of using objects is that they can be used according to different scenarios , Choose the appropriate data structure to optimize the efficiency .

Redis Corresponding data structure in ：
Simple dynamic string
Linked list
Dictionaries
Set of integers
Compressed list

2, object

Redis Each object in is represented by a redisObject Structural representation , The three attributes related to data stored in this structure are ：type attribute 、encoding attribute 、ptr attribute

typedef struct redisObject{
    

	// type 
	unsigned type:4;
	
	// code 
	unsigned encoding:4;
	
	// Pointer to the underlying implementation data structure 
	void *ptr;
	
	//......

}

2.1, The type and encoding of objects

Redis Use objects to represent key value pairs in the database , Whenever a key value pair is created ,Redis Two objects are created , An object is used as the key of a key value pair （ Key object ）, Another value used as a key value pair （ The value object ）

#  For example, the following command creates two objects , A string object is used as a key , Another string object is used as a value 
redis> SET msg "hello wrold"
OK

2.1.1, type

Object's type Property records the type of object , The value of this attribute can be any one in the following table ：

Type constant	Object name
REDIS_STRING	String object
REDIS_LIST	List objects
REDIS_HASH	Hash object
REDIS_SET	A collection of objects
REDIS_ZSET	An orderly collection of objects

about Redis Come on , Key is always a string object , The value can be one of several objects , therefore ：

• When we call a database key ” String key “ when , We mean ： The value corresponding to this database key is a string object
• When we call a database key ” List key “ when , We mean ： The value corresponding to this database key is the list object

TYPE command

We can use TYPE Command view type , When executing on a database key TYPE On command , The result returned by the command is the type of value object corresponding to the database key , Instead of the type of key object .

#  The key is a string object   The value is a string object 
redis> SET msg "hello world"
OK
    
redis> TYPE msg
string

#  The key is a string object   The value is a string object 
redis> RPUSH numbers 1 3 5
(integer) 6
    
redis> TYPE numbers
list

#  The key is a string object   The value is a hash object 
redis> HMSET profile name Tom age 25 career Programmer
OK
    
redis> TYPE profile
hash

#  The key is a string object   Values are collection objects 
redis> SADD fruit apple banana cherry
(integer)3
    
redis> TYPE fruit
set

#  The key is a string object   Values are ordered collection objects 
redis> ZADD price 8.5 apple 5.0 banana 6.0 cherry
(integer)3
    
redis> TYPE price
zset

object	object type The value of the property	TYPE Output of command
String object	REDIS_STRING	”string“
List objects	REDIS_LIST	”list“
Hash object	REDS_HASH	”hash“
A collection of objects	REDIS_SET	”set“
An orderly collection of objects	REDIS_ZSET	”zset“

2.1.2, Coding and underlying implementation

Object's ptr Attributes point to the underlying implementation data structure of the object , And these data structures are made up of encoding Attribute decision .

encoding Property records the encoding used by the object , In other words, what data structure is used by this object as the underlying implementation of the object ：

Encoding constants	The underlying data structure corresponding to the encoding
REDIS_ENCODING_INT	long Type integer
REDIS_ENCODING_EMBSTR	embstr Encoded simple dynamic string
REDIS_ENCODING_RAW	Simple dynamic string
REDIS_ENCODING_HT	Dictionaries
REDIS_ENCODING_LINKEDLIST	Double ended linked list
REDIS_ENCODING_ZIPLIST	Compressed list
REDIS_ENCODING_INTSET	Set of integers
REDIS_ENCODING_SKIPLIST	Jump tables and dictionaries

Each type uses at least two different encodings , Such as ：

type	code	object
REDIS_STRING	REDIS_ENCODING_INT	String objects implemented with integer values
REDIS_STRING	REDIS_ENCODING_EMBSTR	Use embstr Encoded simple dynamic string implementation of string object
REDIS_STRING	REDIS_ENCODING_RAW	String objects implemented with simple dynamic strings
REDIS_LIST	REDIS_ENCODING_ZIPLIST	List objects implemented with compressed lists
REDIS_LIST	REDIS_ENCODING_LINKEDLIST	List objects implemented with double ended linked list
REDIS_HASH	REDIS_ENCODING__ZIPLIST	Hash objects implemented using compressed lists
REDIS_HASH	REDIS_ENCODING_HT	Hash object implemented using dictionary
REDIS_SET	REDIS_ENCODING_INTSET	Set objects implemented with integer sets
REDIS_SET	REDIS_ENCODING_HT	Collection objects implemented using dictionaries
REDIS_ZSET	REDIS_ENCODING_ZIPLIST	An ordered collection object implemented with a compressed list
REDIS_ZSET	REDIS_ENCODING_SKIPLIST	Ordered collection objects implemented using jump tables and dictionaries

Use OBJECT ENCODING Command to view the value object code of a database key

redis> SET msg "hello world"
OK

redis> OBJECT ENCODING msg
"embstr"

Redis Set different codes for an object according to different usage scenarios , So as to optimize the use efficiency of objects in the current scene .

For example, when the linked list object contains fewer elements ,Redis Compressed lists can be used as the underlying implementation of list objects .

• Compressed lists save more memory than double ended linked lists , And when the number of elements is small , Compressed lists stored in memory in consecutive blocks can be loaded into the cache faster than double ended linked lists
• When there are more and more elements ,Redis Will use more powerful 、 It is more suitable for double ended linked lists that store a large number of elements to save data

2.2, String object

The encoding of a string object can be int、raw perhaps embstr

int code

If a string holds an integer value , And this integer can be used long By type , Then the string object will store the integer value in the string object structure ptr Attributes inside （ take void* convert to long）, And set the encoding of the string object to REDIS_ENCODING_INT

for example ：

redis> SET number 10086
OK

redis> OBJECT ENCODING number
"int"

For some floating point numbers （ Such as 3.14） The preservation of the , The program will convert this floating-point number to a string value , Then save the converted String value

raw code

If a string holds a string value , And the length of this value is greater than 32 byte , Then the string object will use a simple dynamic string （SDS） To save the string value , And set the encoding to REDIS_ENCODING_RAW

for example ：

redis> SET story "Long,long ago there is lived a king......"
OK

redis> STRLEN story
(integer) 37

redis> OBJECT ENCODING story
“raw”

embstr code

If the string object holds a string value , And the length of this value is less than or equal to 32 byte , Then the string object will use embstr Save the string value by encoding

embstr And raw Codes need to be created redisObject And sdshdr Two structures , but embstr It is an optimized encoding method specially used to save short strings .embstr During memory reallocation, the two structures created are allocated to the same continuous memory space （ therefore embstr Only one memory reallocation is required when creating , It only needs to be released once ）.

Use embstr The advantages of ：

• The number of memory allocations required for creation is from raw The two times of coding is reduced to one , The same is true of release
• because embstr Both structures of are stored in a continuous memory space , So we can make better use of the advantages brought by cache

for example ：

redis> SET msg "hello"
OK

redis> OBJECT ENCODING msg
"embstr"

Code conversion

int Encoded string objects and embstr The encoded string object, when the condition is met , Will be converted to raw Encoded string object . for example ：

redis> SET number 10086
OK

redis> OBJECT ENCODING number
"int"

redis> APPEND number " is a good number"
(integer) 23

redis> GET number
"10086 is a good number"

redis> OBJECT ENCODING number
"raw"

It is worth mentioning that , because Redis Not for embstr Code string object, write any corresponding modification program （ Only int and raw Coded ）, So for embstr The encoded string object executes any modification instructions , The program converts the object encoding to raw Modify again . This also often leads to embstr Encoded string object after executing modification instruction , Always become a raw Encoded string object

2.3, List objects

The encoding of the list can be ziplist perhaps linkedlist code

When the list object satisfies both of the following conditions , List objects using ziplist code

• The length of all elements saved by the list object is less than 64 byte
• The list object holds fewer elements than 512 individual

Others that do not meet the conditions need to use linkedlist code （ The upper limit of these two conditions can be modified ）

Create a list object numbers

redis> RPUSH numbers 1 "three" 5
(integer)3

ziplist code

If numbers The key uses ziplist code , Then the value object will be like this ：

linkedlist code

If you use linkedlist Code words , Then the value object will be like this ：

It is worth noting that ： there StringObject Is the string object mentioned above , The reason for this painting , To simplify the representation . The string object is Redis The only one of the five types of objects will be nested by other types of objects

In the example three For example , Its complete expression should be ：

Encoding conversion

As long as it does not meet the use ziplist Any condition of coding , The code conversion operation of the object is performed . The originally saved elements will be transferred and saved to the double ended linked list .

redis> RPUSH blah "hello" "world" "again"
(integer)3

redis> OBJECT ENCODING blah
"ziplist"

# Put a greater than 64 Byte long elements are input into the list object 
redis> RPUSH blah "wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww"
(integer)4

redis>OBJECT ENCODING blah
"linkedlist"

2.4, Hash object

The encoding of the hash object can be ziplist perhaps hashtable

When the hash object can meet the following two conditions at the same time , Hash object using ziplist code ：

• The key and string length of all key value pairs saved by the hash object are less than 64 byte
• The key value pair saved by the hash object is less than 512 individual

Suppose a hash object uses ziplist As an underlying implementation , When pressing a new key value pair into this hash object , The program will push the compressed list node with saved keys into the compressed list , Then push the compressed list node with saved values into the compressed list . So the two nodes that hold the same key value pair are always next to each other , And press the key - Values are stored in order .

ziplist code

Create a list object profile

redis> HSET profile name "Tom"
(integer) 1

redis> HSET profile age 25
(integer) 1

redis> HSET profile career "Programmer"
(integer) 1

If the list object uses ziplist code , The schematic diagram of hash object is as follows ：

hashtable code

hashtable The hash object encoded uses the dictionary as the underlying implementation , Each key value pair in the hash object is saved with a dictionary key value pair （ The keys and values of the dictionary are string objects ）

If the top profile The code is hashtable, Then the schematic diagram should be ：

Encoding conversion

When the hash object is not satisfied ziplist When encoding conditions , The code conversion operation of the object is performed , All key value pairs originally saved in the compressed list will be transferred and saved to the dictionary , The code of the object will also change .

2.5, A collection of objects

The code of the collection object can be intset perhaps hashatble

When the following conditions are met at the same time , Use intset code

• The elements saved by the collection object are integer values
• The collection object holds no more elements than 512 individual

intset code

intset The coded set object uses the integer set as the underlying implementation , All elements contained in the set object are contained in the integer set .

redis> SADD numbers 1 3 5
(integer) 3

hashtable code

hashtable The coded collection object uses the dictionary as the underlying implementation , Each key in the dictionary is a string object , Each string object contains a collection element ; The values of the dictionary are all set to NULL

for example ：

redis> SADD Dfruits "appl" "banana" "cherry"
(integer) 3

Encoding conversion

When not satisfied with use intset When using conditions , Will trigger encoding conversion . All elements originally stored in the integer set will be transferred and saved to the dictionary , And change the code of the object to hashtable

2.6, An orderly collection of objects

The encoding of an ordered set can be ziplist perhaps skiplist

When the following two conditions are satisfied simultaneously , Object use ziplist code ：

• The ordered set holds less elements than 128 individual
• The length of all element members in an ordered set is less than 64 Bytes

ziplist code

ziplist Compressed lists are used at the bottom of the encoded ordered collection objects , Each collection element uses two packed list nodes next to each other to hold , The first node holds the members of the element （member）, The second element saves the score of the element

The set elements in the compressed list are sorted from small to large , Those with smaller scores are stored near the heading , Those with higher scores are stored near the end of the table .

for example ：

redis> ZADD price 8.5 apple 5.0 banana 6.0 cherry
(integer) 3

hypothesis price Use compressed list as the underlying implementation , Then the diagram should be ：

skiplist code

skiplist Use of coded ordered collection objects zset Structure as the underlying implementation , One zset Structure contains both a dictionary and a jump table

typedef struct zset{
    
    zskiplist *zsl;
    
    dict *dict;
}zset;

hypothesis price It uses skiplist code , Then the schematic diagram should be ：

Encoding conversion

When the ordered collection object is not satisfied ziplist The use condition of the code , Will trigger encoding conversion ; All elements originally saved in the compressed list will be transferred and saved to zset In structure , And change the code of the object to skiplist