Redis-basic data structure

Share a great artificial intelligence tutorial. Zero-based! Easy to understand! Funny and humorous! Hope you join the artificial intelligence team too! Please click http://www.captainbed.net

Redis (Remote Dictionary Server), the remote dictionary service, is an open source log-based, Key-Value database written in ANSI  C language , supporting the network, memory-based or persistent , and providing APIs in multiple languages. From March 15, 2010, the development of Redis is hosted by VMware. Since May 2013, the development of Redis has been sponsored by Pivotal .

Redis provides richer data structures and commands, and it supports multiple data structures based on lists, sets, hash tables, etc. These structures are implemented in redis by six underlying data structures:

Simple Dynamic String (SDS)
Linked List
Dictionary
Jump List
Integer Set
Compressed List


SDS

Used to save the string in the redis database, it is a structure:


The three attributes in the structure are used to indicate the number of used bytes, the number of unused bytes, and the byte array. The reason why redis designs this structure instead of using the string in the C language is because the SDS structure is similar. Compared with the string in the C language, it has the following advantages:

The length of the string is recorded. When the strlen operation is performed, the complexity is O(1), while the ordinary string is O(n).
SDS adopts an optimization strategy of pre-allocation and lazy release to reduce the number of reallocations of space. The free field records the number of unused space bytes.
Binary security, in addition to storing characters, it can also store any binary.
The SDS operation function will automatically check whether the space is sufficient and automatically expand the space when the space is insufficient to prevent memory overflow.

Linked list

Used to store linked list structure data, it is used to implement collection commands such as SADD:


dictionary

Dictionaries are widely used in Redis. The Redis database itself uses dictionaries as the underlying implementation. For example, if we execute the command: SET msg "hello world", redis will create a key with msg value "hello world" in the database dictionary.

The dictionary contains two hash tables in implementation. Under normal conditions, only the first hash table stores data. When a rehash occurs, space is allocated to the second hash table and the data in the first hash table is copied to The second hash table. If the amount of data in the hash table is relatively large, progressive rehash will be used, and the rehash will be completed in multiple times. There is a rehashindex field in the dictionary to record the rehash progress (if the rehash value is -1), then query the data in the dictionary When it is time, you may find two hash tables, first check the first table, if you can’t find the second one, but the new data will be added to the second hash table, after the rehash occurs, the second hash The table is responsible for querying the data requested by the client. When the server is executing CPU-consuming commands such as BGSAVE and BGREWRITEAOF, it will try to avoid rehash operations.


Skip list

Redis implements a jump table structure, which is used to implement ordered collections in the cache such as ZADD and other commands.

Integer set

When the set contains only integers, and the number of elements in the set is small, redis will use the integer set as the underlying implementation.


The elements in the contents may be 16, 32, or 64 bytes. Redis will only allocate appropriate memory. For example, when a 16-bit integer is currently added, only 16 bytes will be allocated to the contents element, and then it will be added to the array again. When an integer of more than 16 bytes is added, 32 or 64 bytes of memory will be re-allocated for the upgrade of the array. The array can only be upgraded but not downgraded. It can be upgraded from 16 bytes to 32 or 64 bytes, but cannot be downgraded from 64 bytes. To 16 or 32 bytes.

Compressed list

When the number of elements in structures such as lists, collections, hash tables, and ordered collections is less than a certain threshold, redis will use compressed lists as the underlying implementation of these structures. The purpose is to save memory. The compressed list contains the following components :

zlbytes 4 bytes, records the number of bytes of memory occupied by the entire compressed list: used when reallocating memory in the compressed list or calculating zlend.
zltail 4 bytes, records the number of bytes between the end node of the compressed list table and the start address of the compressed list. Through this offset program, the address of the end node of the table can be determined without traversing the entire compressed list.
zllen 2 bytes, records the number of nodes contained in the compressed list. When the attribute value is equal to UINT16_MAX, the actual number of nodes can be calculated by traversing the entire compressed list.
entryX, the list node, the length is determined by the memory node in the node. There is a field in the node, previous_entry_length, which records the length of the previous point. When the length of the node is around 254, the modification of a node may be triggered. Chain update of all nodes.


The compressed list will save memory, but some performance will be lost when accessing or modifying the elements in the structure. Therefore, when the number of elements or the element size exceeds a certain threshold, the value object will be encoded and converted into a collection, hash table, and Ordered collection and other structures, and reallocate memory.

Object

Redis does not directly use the above data structures to implement the key-value pair database. Instead, it creates an object system based on these data interfaces. Each time a new key-value pair is created in the Redis database, at least two are created. Object, a key object, and a value object. Each object contains a specified type and code.

Object type

The type attribute of the object is set, and the type of the object can be output through the TYPE command. The object has the following types:

String object: The type constant is REDIS_STRING, and the output value is string.
List object: The type constant is REDIS_LIST, and the output value is list.
Hash object: The type constant is REDIS_HASH, and the output value is hash.
Collection object: The type constant is REDIS_SET, and the output value is hash.
Ordered set table object: The type constant is REDIS_ZSET, and the output value is zset.
Object coding

To set the encoding property of the object, you can view the encoding of the object through the OBJECT ENCODING command. The object has the following encodings:

Long type integer, REDIS_ENCODING_INT, output int
embstr coded SDS, REDIS_ENCODING_EMBSTR, output embstr. Embstr encoding is an optimized encoding method specially used to save short strings. Compared with normal character encoding, the character encoding will call the memory allocation function twice to create the redisObject and sdshdr structures respectively, while the embstr encoding will call the memory once. The allocation function allocates a continuous space. The space contains two structures
SDS, redisObject and sdshdr , REDIS_ENCODING_RAW, output raw
dictionary, REDIS_ENCODING_HT, output hashtable
double-ended linked list, REDIS_ENCODING_LINKEDLIST, output linkedlist
compressed list, REDIS_ENCODING_ZIPINI, output zipCOlist
integer set, REDIS_ENCODING_RAW, Output intset
skip list and dictionary, REDIS_ENCODING_SKIPLIST, output skiplist.
Each type of object uses at least two different encodings. Under different conditions, redis will encode and convert the object. For example, if the object is all integers, then he The encoding of is int, but when some commands are executed, not all the stored in the object are integers, then the encoding of the object will be changed from int to raw, the same is true for other types of objects.