introduction
Redis is a data structure storage system based on key-value pairs . Its features include memory-based operations, single-threaded command processing, IO multiplexing model for processing network requests, key-value pair storage, simple and rich data structures , etc.
This article mainly focuses on the objects and data structures in Redis to explain in detail the two major features of key-value pair storage and simple and rich data structures.
The data in Redis is stored in the form of Key, Value pairs in the dictionary , and the dictionary is implemented as a hash table.
Keys can only be represented by string objects, and values can be represented by any other objects.
Objects and Data Structures
There are many objects in Redis. Commonly used objects (data types) include string objects, list objects, hash objects, set objects, ordered set objects, etc.
There are other data types such as Bitmap, Hyperloglog, Geospatial, Bloom filter, etc., but this article only covers commonly used objects, and other data types will be explained in later articles.
The object RedisObject in redis consists of type, encoding, number of references, lru, and data structure object used by the pointer encoding.
Type identifies what type of object this is
Such as strings, lists, hashes, sets, ordered sets, etc.
The encoding indicates which data structure is used to construct the corresponding type of object
The reference count indicates how many times this object has been referenced.
Redis memory recycling uses reference counting method to recycle objects with reference count of 0. Redis only depends on string objects, and there is no circular dependency, so there is no circular reference, so reference counting method can be used.
lru records the time when this object was most recently called. When the space recovery algorithm uses lru, it will give priority to reclaiming objects that have not been used for a long time (subsequent deletion and recovery articles will introduce this)
Data Structure
sds simple dynamic string
sds is maintained using a byte array, len records the length of the string (the ‘\0’ at the end is not counted), and free indicates the free length in the byte array
Before adding an element, the system will determine whether the array length is sufficient. If not, it will be expanded. There is a space pre-allocation strategy for expansion, which will leave some free space.
If the string does not exceed the length of the array next time it is modified, it can be modified directly, saving the cost of expansion.
hashtable dictionary
Dictionaries are implemented using hash tables . The principles of hash tables will not be outlined in detail in this article.
Hash conflicts are resolved using the chain address method. When searching, first get the index through hash% array length – 1, then traverse the linked list nodes. If it is a new addition, directly use the head insertion method to insert it into the head of the linked list.
To prevent blocking when a large dictionary is expanded, the hash table in the dictionary is expanded gradually . When expansion occurs, there will be two hash tables.
Data may be stored in both the old and new hash tables. hgetWhen a request is received, the old hash table is searched first. If it is found, it is migrated to the new hash table. If it is not found in the old hash table, it is searched in the new hash table.
When the migration is complete, the new hash table replaces the old one
skiplist
The skip table maintains a multi-level ordered linked list. The high level can quickly reach the subsequent nodes . It is simple to implement and easy to maintain. The average time complexity of adding, deleting, modifying and checking is log n.
For example, to search for a node with a value of 2.0, the search order is the dashed line in the figure.
First find the virtual head node, and start searching from the highest layer currently maintained (L5). Go back and find that the o3 object has a value of 3.0, which means that it has been found too far, so go to the next layer to search; go to L4 and traverse successively, the o1 object has a value of 1.0, which is smaller than the target value of 2.0, which means that there is no target value behind the o1 object, so go to the o1 object L4 layer; continue to traverse backwards in the o1 object L4, and find that the o3 value is 3.0, which is larger than the target value, so go down to the o1 object L3 layer; the L3 layer is also behind o3, so continue to go down to the L2 layer, traverse the L2 layer backwards to the o2 object, and the value is 2.0. When compared with the o2 object, it is the same, which means it has been found.
Start querying from the highest layer maintained. If the query is empty or the query value is greater than the target value, the layer will be lowered. If the layer is still lowered at the last layer, it means that it cannot be found.
When the sorting values are the same, sort by object size. The objects here are all string objects.
The number of layers when adding nodes is randomly generated, and the higher the layer, the smaller the probability; other modification operations are also performed through queries, and other attributes such as the highest layer must also be maintained.
intset integer set
intset maintains an ordered, non-duplicate array
The implementation uses arrays, lengths (to record the number of elements), and encodings (the encodings can identify the element type, such as 16-, 32-, or 64-bit integers)
When the added element is a high-bit integer that does not exist in the current array (for example, the array is full of 32-bit integers, and a 64-bit integer is added at this time), an upgrade occurs: first apply for memory reallocation, then move the old element to the corresponding position, and then add the new element and modify the encoding at the same time. When the high-bit integer is deleted, no downgrade will occur.
The upgrade of intset effectively saves memory. When all set objects are integers and the amount of data is small, intset is used to save memory.
ziplist compressed list
The ziplist is composed of nodes in continuous space. The nodes are composed of the predecessor node offset (reverse traversal), encoding (byte array or integer encoding), and content (content can be byte array or integer)
Because the content of the ziplist is not fixed, for example, the offset of the predecessor node is variable, which will affect the length of the node. And because the ziplist is continuous in space, this will cause the subsequent node space to change, which is called a chain update (the probability of occurrence is small)
In order to save space, it is used to implement lists, hashes, and ordered sets in scenarios with small quantities.
quicklistQuick list
Quicklist can be used as a bidirectional linked list, except that the nodes use ziplist, which is often used to implement list objects in scenarios with large amounts of data.
Object
illustrate:
The amount of data in the following text represents the occupied bytes and the number of data elements.
This article does not introduce the command usage rules of each object. Students who need to learn the commands can go to the official website to check
String Object
The string object string is implemented by sds simple dynamic string
SDS has different encodings: int, embstr, row
int is used to store integer strings. Conversion between integers and strings may occur during calculations.
embstr is used to store short strings. It allocates memory only once. When allocating memory, it allocates both redisobject and sds.
row is used to store long strings. When allocating memory, it needs to be allocated twice: redisobject and sds
The string object is the most commonly used object in Redis and is the only object that other objects depend on.
Common usage scenarios of string objects: cache, counters, and distributed locks
List Object
The list object list is a queue that can operate the head and tail of the queue. It is implemented by ziplist or quicklist
Use ziplist when the data volume is small, and use quicklist (linkedlist+ziplist) when the data volume is large.
The usage scenario of the list is FIFO queue to ensure the order of element access
Hash Object
Hash object hash is an unordered data structure that maintains KV key-value pairs, implemented by ziplist or hashtable
Use ziplist for small amounts of data and hashtable for large amounts of data
The usage scenario of hash is partial access to cache (for example, a large gift package contains product A and product B, etc.)
Collection Objects
The characteristics of the set object are unordered and weightless, and are implemented by intset or hashtable
If the amount of data is small and the data is an integer, use intset; if the amount of data is large or the data is not an integer, use hashtable and the value is always null.
The usage scenario of the collection is unique elements or intersection and union (common attention, possible acquaintance), etc. (unordered, no duplication)
Ordered collection object
The ordered set object zset is an ordered, weightless data structure, implemented by ziplist or skiplist + hashtable
When the amount of data is small, use ziplist; when the amount of data is large, use skiplist + hashtable (to meet the function of indexing constants according to object queries, share objects, and not cause memory overhead)
The usage scenarios of ordered sets are rankings, popularity rankings, etc. (ordered, no duplication)
Summarize
This article introduces the objects and data structures in Redis in detail, focusing on the key-value pair storage and rich and diverse data structures of Redis.
Objects consist of types, codes, data structure pointers, etc.
To save space, each type of object has multiple encoding types of data structures that can be implemented
String objects are often used for caching, distributed locks, counters, etc., and are used by other objects.
SDS mainly uses three encodings, int, embstr, and row, to process different types of strings. embstr processes short strings and optimizes memory allocation.
sds is a dynamic string. By using the space pre-allocation strategy, if the modification does not exceed the length of the array, there is no need to expand the capacity, saving costs
List objects are often used to maintain the order of queue elements
When the amount of data is small, use the compressed list ziplist to implement it, and when the amount of data is large, use the quick list quicklist to implement it
The compressed list uses continuous space, and the nodes can store strings or integers.
The quick list can be used as a linked list, and the nodes are compressed lists.
Hash objects are often used to maintain partial access caches
When the amount of data is small, use the compressed list zpilist to implement it, and when the amount of data is large, use the hash table hashtable to implement it
To prevent blocking, the hash table uses two new and old hash tables to store elements when expanding capacity, and completes the migration while processing commands
Collection objects are unordered and weightless, and are often used for uniqueness, intersection (common friends), and union (possible acquaintances).
When the amount of data is small and all elements are integers, use the integer set intset to implement it. When the amount of data is large, use a hash table to implement it.
Integer collections have different encoding forms, which fully saves space; when using a hash table, the Value is empty
Ordered set objects are ordered and weightless, and are often used to make rankings.
When the amount of data is small, a compressed list is used; when the amount of data is large, a skiplist + hash table is used, and the hash table stores the comparison value of the K object V
The jump list is a multi-level ordered linked list with an average time complexity of log n. It is simple and easy to maintain.