Source code based on Redis-3.0

1. Simple dynamic strings

Introduction to the

Simple Dynamic String, namely Simple Dynamic String (SDS), is the basis of Redis to realize the underlying string-related data structure. It is constructed abstractly on the basis of C language String.

The data structure

In the source code,sds.h/sdshdrRepresents the composition of a most basic SDS as follows

struct sdshdr {
    // Records the number of bytes used in the BUF array
    // is equal to the length of the string saved by SDS
    int len;
    // Records the number of unused bytes in the BUF array
    int free;
    // An array of bytes to hold strings
    char buf[];
};
Copy the code

Char buf[] uses a flexible array with the following benefits:

If a pointer is usedchar *bufAllocate memory requirements in two steps: allocate the structure once and allocate it oncechar *buf, the memory needs to be freed twice: oncechar *buf, once is the internal storage of the structure. Using a character array of length 0 simplifies memory management by reducing the number of times memory is allocated and freed to one
An array of length zero ischar buf[]Does not occupy memory, saving memory space

// char buf[
struct sdshdr s;
printf("%d".sizeof(s));
/ / 8
// char *buf
struct sdshdr s;
printf("%d".sizeof(s));
/ / 12
Copy the code

For SDS statistics len and SIZE, time complexity is O(1)

/ / return SDSHDR. Len
static inline size_t sdslen(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->len;
}
/ / return SDSHDR. Free
static inline size_t sdsavail(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->free;
}
Copy the code

The characteristics of

SDS is compatible with some C language functions

SDS follow the conventions of C string null terminated save null character 1 byte space does not calculate in SDS len attribute, and allocate an additional 1 byte to null character space, and operations such as add null character to the end of the string is a function of SDS automatically, so the null character is completely transparent for users of SDS. The advantage of following the null-terminating convention is that SDS can directly reuse some of the functions in the C string library.

The role of SDS len

C language does not record the information of character length itself, string length needs to be traversed from beginning to end, and the time complexity is O(n). Len attribute is added in Redis to record string length, and the time complexity is reduced to O(1). SDS provides internal implementation of recording operation.
Because the string length is recorded, memory overflow problems are also avoided during some string operations

SDS reduces memory space reallocation when string changes

The change of the string will frequently call the underlying method of the system to change the memory space. SDS realizes two optimization strategies of space pre-allocation and lazy release through unused space, avoiding the performance consumption caused by frequent change of memory space.

Preempted the space

If len is less than 1MB, the preoccupied space is the same size as the used space. If len is greater than or equal to 1MB, the pre-occupied space is always 1MB. With this preallocation strategy, SDS reduces the number of memory reallocations required to grow strings N times in a row from a certain N to a maximum of N.

Used space	Distributive judgment condition	Allocate unused space	Total space occupied
5B	Whether the value is greater than or equal to 1MB	5B	5B(Len) + 5B(free) + 1B
2MB	Whether the value is greater than or equal to 1MB	1MB	2MB(Len) + 1MB(Free) + 1B
#### Lazy release

Lazy space free is used to optimize SDS string shortening operations: When the SDS API needs to shorten the string saved by SDS, the program does not immediately use memory reallocation to reclaim the shortened extra bytes, but instead uses attributes`free`The number of these bytes is recorded and held for future use.

In conclusion, either pre-allocation of space in advance or lazy release of space will inevitably take up more extra space, which can be understood as the idea of space for time.

SDS guarantees text binary security

The so-calledBinary securityA computer programming term used primarily in relation to string manipulation functions. A binary security feature (function) that essentially treats the operational input as a raw data stream without any special formatting significance. Every character is treated fairly, and no character is treated in particular. In plain English, the program does not restrict, filter, or make assumptions about the data in it as it was written and as it was read.

Redis stores characters through a BUF array, and reads the array length through the len attribute rather than the ‘\0’ character as in C, so special character parsing is not a problem and is binary safe.

2. List

Introduction to the

The linked list provides efficient node rearrangement and sequential node access, and the length of the linked list can be flexibly adjusted by adding and deleting nodes. C language does not have this built-in data structure, Redis provides the implementation of a double-endian linked list.

The data structure

In the source code,adlist.h/listNodeRepresents the composition of a basic linked list, as follows

/* * Double-ended list node */
typedef struct listNode {
    // The front node
    struct listNode *prev;
    // back node
    struct listNode *next;
    // Node value
    void *value;
} listNode;

/* * Double-endian list */
typedef struct list {
    // Table header node
    listNode *head;
    // Table end node
    listNode *tail;
    // Node value copy function
    void *(*dup)(void *ptr);
    // Node value release function
    void (*free) (void *ptr);
    // Node value comparison function
    int (*match)(void *ptr, void *key);
    // The number of nodes in the linked list
    unsigned long len;
} list;
Copy the code

The characteristics of

Double-ended linked list nodes have prev and next Pointers, and the time complexity of obtaining the pre-node and post-node of a node is O(1).
The prev pointer on the head node of a acyclic table and the next pointer on the tail node point to NULL, and access to the linked list ends at NULL
The head and tail Pointers of the list are used to obtain the head and tail nodes of the list. The time complexity is O(1).
The list length counter uses the len property of the list structure to count the list nodes held by the list. The time complexity of obtaining the list length is O(1).
Polymorphism supports saving different types of values

Usage scenarios

List List key, publish & subscribe, monitor, slow query

3. The dictionary

Introduction to the

A dictionary is an abstract data structure used to hold kev-value data. C language does not have built-in on-line data structure, Redis provides implementation support. Each Key in the dictionary is unique, and a program can look up the value associated with it by Key, update the value by Key, delete entire key-value pairs by Key, and so on

The data structure

The hash table used by Redis dictionaries is defined bydict.h/dicthtStructure definition

/* * dictionary */
typedef struct dict {
    // Type specific functions
    dictType *type;
    // Private data
    void *privdata;
    / / a hash table
    dictht ht[2];
    // rehash index; When rehash is not in progress, the value is -1
    in rehashidx; 
} dict;
Copy the code

typeSupport polymorphic storage of specific data types
privdataSave the optional arguments that need to be passed to those type-specific functions
htThe dictionary holds two hash tablesdictht, HT [0] is used to store data, ht[1] is used for rehash
rehashindxFlags whether rehash is currently in progress, and is not rehash when the value is -1

/* * Hash table * * Each dictionary uses two hash tables to implement progressive rehash. * /
typedef struct dictht {
    // Hash table array
    dictEntry **table;
    // Hash table size
    unsigned long size;
    // Hash table size mask, used to calculate index values
    // always equal to size-1
    unsigned long sizemask;
    // The number of existing nodes in the hash table
    unsigned long used;
} dictht;
Copy the code

tableHolds an array of **dictEntry **, which stores the node data of dictionary data, namely key-value data
sizeThe array size
sizemaskIndex value, always size-1
used**dictEntry ** number of nodes used

/* * hash table node */
typedef struct dictEntry {
    / / key
    void *key;
    / / value
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // Point to the next hash table node to form a linked list
    struct dictEntry *next;
} dictEntry;
Copy the code

key 键
vValue, which can be a pointer, uint64_t integer, or int64_t integer
nextPointer to the next node

The underlying principle

Hash calculation

Compute the hash value of the key using the dictionary set hash function used by RedisMurmurHash2The advantage of this algorithm is that even if the input keys are regular, the algorithm can still give a very good random distribution, and the algorithm is very fast

hash = dict->type->hashFunction(key);

Hash tablesizemaskAttribute and hash value for modulus calculation, calculate the index value to determine the hash slot position. Ht [x] can be HT [0] or HT [1], depending on the case.

index = hash & dict->ht[x].sizemask;

Hash collision

当Hash table node dictEntryWhen a collision occurs, next is used in series to point to the next node, throughChain address methodResolve hash node collision for storage, the colliding node will be usedThe first interpolationInsert to the head of the single list before the other nodes, because this operation does not need to traverse the list in O(1) time

rehash

The procedure for rehashing is as follows. Capacity expansion is used as an example

Before the expansion

Open the space

For a dictionaryht[1]The hash table allocates space, the size of the hash table depends on the operation to be performed, andht[0]The number of key-value pairs currently contained (i.eht[0].usedProperty value). As shown above, the capacity expansion operation,sizeIs greater than or equal toht[0].used2The first 2 to the NTH power of PI is 42 is 8, which is exactly 2 to the third power, soht[1]Set size to 8

operation	Ht [1]
capacity	The first one is greater than or equal to`Ht [0]. Used * 2 of 2ⁿ`
Shrinkage capacity	The first one is greater than or equal to`Ht [0]. 2 of 2ⁿ`
#### Copy object

Will be stored in the`ht[0]`Rehash to all key value pairs in`ht[1]`Above: Rehash means to recalculate the hash and index value of the key and then place the key-value pair into`ht[1]`Hash table at the specified location
#### Change pointer

When all key-value pairs contained in HT [0] are migrated to`ht[1]`After (`ht[0]`Empty table), release`ht[0]`That will be`ht[1]`Set to`ht[0]`And, in`ht[1]`Create a new blank hash table in preparation for the next rehash
#### Rehash trigger condition
The following is the source code of the expansion method:
“`c
// Indicates whether the dictionary is rehash enabled
static int dict_can_resize = 1;
// Enforce the ratio of rehash
static unsigned int dict_force_resize_ratio = 5;

/* Expand the hash table if needed / /

Initialize the dictionary, or extend the dictionary, as needed
T = O(N)

*/ static int _dictExpandIfNeeded(dict D) {/ Incremental rehashing already in progress.return. */ // Incremental rehash If (dictIsRehashing(d)) return DICT_OK;

/* If the hash table is empty expand it to the initial size. T = O(1) if (d->ht[0]. Size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE); /* If we reached the 1:1 ratio, and we are allowed to resize the hash * table (global setting) or we should avoid it but the ratio between * */ / If one of the following conditions is true, the number of their doubling * is doubling. */ / // 1) The ratio between the number of nodes in use and the size of the dictionary is close to 1: 1 // and dict_can_resize is true // 2) The ratio between the number of used nodes and the dictionary size exceeds dict_force_resize_ratio if (d-> HT [0]. Used >= d-> HT [0].size && (dict_can_resize | | d - > ht [0]. 2 / d - > ht [0]. Size > dict_force_resize_ratio)) {/ / new the size of the hash table is now at least use twice the number of nodes / / T = O (N) return dictExpand(d, d->ht[0].used*2); } return DICT_OK;Copy the code

}

Meet one of the following conditions and then trigger a rehash server environment | load factor (< code > ht [0]. 2 / ht [0] size < / code >) | controllable - | -- - | -- -- -- -- -- No in < code > BGSAVE < / code > or < code > command BGREWRITEAOF < / code > command | | > = 1 load factor meet will trigger a rehash Are performing < code > BGSAVE < / code > or < code > command BGREWRITEAOF < / code > command | > = 5 | < code > dict_can_resize < / code > > controlled switch To execute the <code>BGSAVE</code> command or the <code>BGREWRITEAOF</code> command, Redis needs to create a child of the current server process, Most operating systems use copy-on-write </code> to optimize the use efficiency of the child process, so the server increases the load factor required to perform the extension operation during the existence of the child process, thus avoiding the hash table extension operation during the existence of the child process as much as possible. This avoids unnecessary memory writes and maximizes memory savings. Dict_can_resize </code> Redis will adjust <code>dict_can_resize</code> to determine whether to enable rehash #### progressive rehash The following are the incremental rehash steps for capacity expansion: 1. Allocate space for <code> HT [1]</code> so that the dictionary holds both <code> HT [0]</code> and <code> HT [1]</code>. 2. Maintain an index counter variable <code>rehashidx</code> in the dictionary and set its value to 0 to indicate that rehash work has begun. 3. Each time a dictionary is added, deleted, found, or updated during rehash, the program performs, in addition to the specified operation, The <code> HT [0]</code> hash into <code> HT [1]</code> when the rehash is complete, The program increments the <code>rehashidx</code> property by one. Add data will only be added to <code> HT [1]</code>, and will not be repeatedly added to the old container. The query logic will first look up the data in <code> HT [0]</code> and then look up the data in <code> HT [1]</code>. 5. As the dictionary operation continues, at some point in time all key-value pairs of <code> HT [0]</code> will be rehashed to <code> HT [1]</code>, at which point the <code>rehashidx</code> property is set to -1. Indicates that the rehash operation is complete. > ** The benefit of progressive Rehash ** is that it takes a <code> dial-and-conquer </code> approach, spreading the computation required for rehash key and value pairs over every add, delete, find, and update operation to the dictionary, thereby avoiding the massive computation that comes with centralized Rehash. Skiplist ** is an ordered data structure that enables fast access to nodes by maintaining multiple Pointers to other nodes in each node. Search for nodes with average <code>O (logN) </code> and worst <code>O (N) </code> complexity, and batch process nodes through sequential operations. Skip lists are as efficient as balanced trees, and because they are much easier to implement than balanced trees, many programs use skip lists instead of balanced trees. ## Data structure! [insert picture description here] (HTTP: / / https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/de561d6b00914c38bc27c6322d3d77cd~tplv-k3u1fbpfcp-zoom-1.im H /zskiplistNode</code> and <code> Redis. H /zskiplist</code> Where <code>zskiplistNode</code> structure is used to represent the skiplist node, C /* ZSETs use a specialized version of Skiplists */ /* * a specialized version of Skiplists */ typedef Struct zskiplistNode {// member object robj *obj; // double score; Struct zskiplistNode *backward; Struct zskiplistNode *forward; struct zskiplistNode *forward; // span unsigned int span; } level[]; } zskiplistNode;Copy the code

objMember object. The member objects of each node areThe only.
scoreScore. All nodes in the skip list are gradedSince the childhoodTo sort by member objects with the same scoreobjTo sort by size in lexicographical order, nodes with smaller member objects are placed first
backwardBack pointer, point tozskiplistNodenode
levelLayer, byzskiplistLevelIs an array. Programs can use these layers to speed up access to other nodes, and in general, the more layers there are, the faster access to other nodes will be. The height of each skip list node is1 ~ 32Random number between
- forwardPoint to thezskiplistNodeA forward pointer to a node that provides the ability to traverse a skip list
- spanSpan. Rank the current node in the skip list by span. The greater the span between two nodes, the farther apart they are. All forward Pointers to NULL have a span of 0 because they are not connected to any node.

/* * skip list */
typedef struct zskiplist {
    // Table header and table tail nodes
    struct zskiplistNode *header, *tail;
    // The number of nodes in the table
    unsigned long length;
    // The number of layers of the node with the largest middle level in the table
    int level;
} zskiplist;
Copy the code

headerRepresents the head of the skip listzskiplistNodeThe head of the node
tailRepresents the end of the skip listzskiplistNodeThe tail of the node
lengthTotal number of nodes in a skip list (excluding table header nodes)
levelTotal number of levels in the skip table (not including levels in the head node)

The underlying principle

The RedisJump tableIn short, it is added on the basis of linked listsMulti-level indexSpeed up data lookup, plusbackwardProvides reverse lookup, yesSpace for timeThoughts.

As shown in the figure above, the dotted red line is the node traversal pathspanSpan onelevelThe layer carries out node sidewalks byforwardRoute to the next node until encounteredforwardIf the value is null, the node is the last node.

Usage scenarios

Ordered set key

5. Integer sets

Introduction to the

When a collection contains only integer numeric elements and the number of elements in the collection is small, Redis uses the collection of integers as the underlying implementation of the collection key, which stores an ordered, non-repeating set of integers.

The data structure

In Redis,intset.h/intsetStructure represents a collection of integers

typedef struct intset {
    // Encoding mode
    uint32_t encoding;
    // The number of elements the collection contains
    uint32_t length;
    // Hold an array of elements
    int8_t contents[];
} intset;
Copy the code

encodingEncoding mode. Encoding mode Based on the data type The encoding mode supports the minimum format storage
lengthNumber of arrays
contentsAn array that holds elements.contentsThe array does not hold anyint8_tThe value of type,contentsThe true type of the array dependsencodingProperty value. The element will followSince the childhoodIs stored in sequence

Encoding encoding	The minimum value	The maximum
INTSET_ENC_INT16	– 32768.	32767
INTSET_ENC_INT32	– 2147483648.	2147483647
INTSET_ENC_INT64	– 9223372036854775808.	9223372036854775807

Code upgrade

Use the encoding method that can meet the minimum length of element data type, and upgrade the encoding format when it cannot meet the requirement; The degrade operation is not supported.

Upgrade process:

Expands the size of the underlying array of integers based on the type of the new element and allocates space for the new element.
All the existing elements of the underlying array are converted to the same type as the new element, and the converted elements are placed in the correct bit, and in the process of placing the elements, the ordered nature of the underlying array remains unchanged.
Adds a new element to the underlying array.

Advantages of coding upgrade:

Uniform encoding storage to avoid type errors
Save memory

Usage scenarios

A collection of key

6. Compress lists

Introduction to the

Developed by Redis to save memory, ziplist is a sequential double-endian linked list data structure composed of a series of specially encoded contiguous memory blocks. A compressed list can contain any number of entries, each of which can hold either a byte array or an integer value.

The data structure

List of compression

Redis’s compressed list is made byziplist.cStructural composition

zlbytesIt’s an unsigned4byteAn integer that holds the amount of memory used by ziplist.

Using ZLBytes, the program can adjust the ziplist memory size directly without traversing the entire list to calculate the ziplist memory size.

zltailIndicates the offset from the start address of the last entry in the compressed list4byte.

This offset makes it possible to pop the tail of the table without traversing the entire list.

zllenCompress the nodes of the listentryThe number,2byte.

When the number of elements in the compressed list exceeds 2^ 16-2, zllen sets the value to 2^16-1. When the value is 2^16-1, zllen traverses the compressed list to obtain the number of elements. So Zllen is not a replacement for Zltail.

entryThe compressed list stores data on the nodeAn array of bytesorThe integer.
zlendCompress the end of the list, occupy1byteConstant for0xFF, i.e.,255.

Data structure features:

The internal representation is a contiguous memory array with data compactly arranged.

Can simulate the bidirectional linked list structure toThe O (1)Time complexity In and out of teams

A new deletion operation involves memory reallocation or release, which increases the complexity of the operation

Read and write operations involve complex pointer movement, and the worst time complexity isO (n2)

Suitable for storing small objects and data of limited length

Node information

/* * Save ziplist node information structure */
typedef struct zlentry {
    Prevrawlen: Length of the front node
    Prevrawlensize: Size of bytes required to encode prevrawlen
    unsigned int prevrawlensize, prevrawlen;
    Len: the length of the current node value
    // lensize: the size of the bytes required to encode len
    unsigned int lensize, len;
    // The size of the current node header
    // prevrawlenSize + lenSize
    unsigned int headersize;
    // The encoding type used for the current node value
    unsigned char encoding;
    // Pointer to the current node
    unsigned char *p;
} zlentry;
Copy the code

prevrawlensizeThe length of the front node
prevrawlenThe size in bytes required to encode the front node
len The length of the current node value
lensize The size of bytes required to encode the current node
headersizeThe size of the current node header is equal toprevrawlensize + lensize
encodingThe encoding type used for the current node value. Supports 3 types of byte arrays and 6 types of integers

The data type	The length of the
An array of bytes	Length <= 63 (2^6–1)
An array of bytes	Length <= 16383 (2^14–1)
An array of bytes	Length <= 4294967295 (2^32–1)
The integer	An unsigned 4-bit integer between 0 and 12
The integer	1 – byte long signed integer
The integer	A 3 – byte long signed integer
The integer	Int16_t Integer
The integer	Int32_t An integer
The integer	Int64_t Integer

*pPointer to the current node. Cooperate withzltailCan be used to quickly locate the tail node position

Here is an example to illustrate:

zlbytesIt is 210, meaning that the entire compressed list takes up 210 bytes
zltailThe tailentryThe node offset is 179, through the pointerpAdd the offset 179 to find the endpoints
zllenIs 5, which means there are currently 5entrynode
entryCurrently there are fiveentrynode
zlendConstant for the0xFF, i.e.,255.

Chain update

Because eachentryBoth maintain the byte size of the front node, and the change of the byte size of the current node will cause the change of the current node attribute. Redis calls this continuous multi-space expansion operation under special circumstancesCascade Update

Front node length	Maintaining front node attributes takes up space
<254byte	1byte

=254byte | 5byte

impact

In the worst case, chained update requires N space reallocation operations on the compressed list, and the worst complexity of each space reallocation is O(N), so the worst complexity of chained update is O(N^2).

The trigger condition

Cascading updates can be initiated only if there are exactly multiple consecutive nodes between 250 and 253 bytes in the compressed list.

To sum up, the probability of triggering chained update is very low, and the performance will not be greatly affected even if the number of nodes meeting the triggering conditions is small

Usage scenarios

List keys (small, small integer value, short string), hash keys (Small, small integer value, short string)

When a list of key contains only a small amount of the list items, and each list item or small integer value, or the length of the shorter string or as a hash key contains only a small amount of key-value pairs, than and each key/value pair of keys and values or small integer values, or the length of the string is shorter, the Redis will use compressed list to the underlying implementation to do it

Object of 7.

Introduction to the

Redis uses objects to represent keys and values in the database. Each time we create a new key-value pair in Redis’s database, we create at least two objects, one for the key (key object) of the key-value pair and one for the value (value object) of the key-value pair.

The data structure

Each object in Redis consists of oneredisObjectStructures,

typedef struct redisObject {
    / / type
    unsigned type:4;
    / / code
    unsigned encoding:4;
    // The last time the object was accessed
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
    // Reference count
    int refcount;
    // A pointer to the actual value
    void *ptr;
} robj;
Copy the code

typeType. There is always one key for key-value pairs stored in Redis databasesString object, and the value can beString object, list object, hash object, collection object, ordered collection objectOne of them

Type constants	Object name	TYPE Output of the TYPE command
REDIS_STRING	String object	“string”
REDIS_LIST	A list of objects	“list”
REDIS_HASH	The hash object	“hash”
REDIS_SET	A collection of objects	“set”
REDIS_ZSET	Ordered set object	“zset”

encodingType. The encoding used by the object, that is, what data structure does the object use as the underlying implementation of the object

Code constants	The underlying data structure corresponding to the encoding
REDIS_ENCODING_INT	An integer of type long
REDIS_ENCODING_EMBSTR	A simple dynamic string encoded by embstr
REDIS_ENCODING_RAW	Simple dynamic string
REDIS_ENCODING_HT	The dictionary
REDIS_ENCODING_LINKEDLIST	Double side chain table
REDIS_ENCODING_ZIPLIST	List of compression
REDIS_ENCODING_INTSET	The integer set
REDIS_ENCODING_SKIPLIST	Skip lists and dictionaries

Different types of objects have different underlying data structures. Redis can set different codes for an object according to different usage scenarios, so as to optimize the efficiency of the object in a certain scenario, as follows

type	coding	object	OBJECT ENCODING Command output
REDIS_STRING	REDIS_ENCODING_INT	A string object implemented with an integer value	“int”
REDIS_STRING	REDIS_ENCODING_EMBSTR	A string object implemented using a simple dynamic string encoded by EMbstr	“embstr”
REDIS_STRING	REDIS_ENCODING_RAW	A string object implemented using a simple dynamic string	“raw”
REDIS_LIST	REDIS_ENCODING_ZIPLIST	A list object implemented using a compressed list	“ziplist”
REDIS_LIST	REDIS_ENCODING_LINKEDLIST	A list object implemented using a double-ended linked list	“linkedlist”
REDIS_HASH	REDIS_ENCODING_ZIPLIST	A hash object implemented using a compressed list	“ziplist”
REDIS_HASH	REDIS_ENCODING_HT	Hash objects implemented using dictionaries	“hashtable”
REDIS_SET	REDIS_ENCODING_INTSET	A collection object implemented using a collection of integers	“intset”
REDIS_SET	REDIS_ENCODING_HT	A collection object implemented using a dictionary	“hashtable”
REDIS_ZSET	REDIS_ENCODING_ZIPLIST	An ordered collection object implemented using a compressed list	“ziplist”
REDIS_ZSET	REDIS_ENCODING_SKIPLIST	An ordered collection object implemented using skip lists and dictionaries	“skiplist”

refcountReference counting. Because C does not have an automatic memory reclamation mechanism, Redis passesReference Counting (Reference Counting)The memory reclamation mechanism is implemented. whenReference countingWhen the value is 0, the memory occupied by the object is reclaimed.

Object usage state	Reference counting
When a new object is initialized	+ 1
When newly quoted	+ 1
When no longer cited	– 1

As shown above,`refcount`If the reference count is 5, the object is referenced by five Pointers, which greatly reduces the memory usage

Redis only provides a shared object pool of integers from 0 to 9999, and no other data types

lruThe time when the object was last accessed. throughOBJECT IDLETIME [KEY]Command to view the object’s idle time when usedThe GET and SETEtc will activate the object,lruIt’s going to reset to 0. The property will be displayed in the memory reclamation algorithmvolatile-lruorallkeys-lruCome into play
*ptrA pointer to the underlying implementation data structure

Object type

String object

Value types	qualification	encoding	Underlying data structure
The integer	–	int	int
A string or floating point number	> 32	raw	sds
A string or floating point number	< = 32	embstr	sds
`raw`with`embstr`The difference between:

embstrCreating a string object requires only one memory allocation, whilerawRequires two
embstrFree object memory only once, whilerawRequires two
embstrUse a contiguous memory space, thanrawBetter leverage the advantages of caching

Floating point value will be converted to a string object to save and use code conversion When the stored value changes, code format and change the underlying data structure Nested object string objects is the most basic object types, can be stored value can also be stored strings, so it is also constitute the foundation of other complex object types, It is the only one of the five data objects that can be nested, that is, other complex data objects such as hash objects, list objects, etc., use string objects as one of the components to construct their own complex object types

In order toembstrEncoding format,stringA string object of type,ptrPoints to thesdsData structure, as follows:

A list of objects

Value types	qualification	encoding	Underlying data structure

| Simultaneously satisfy:

Length of all string elements (list-max-ziplist-valueControl) < 64 bytes

Number of elements (list-max-ziplist-entriesControl) < 512 | linkedlist | linkedlist
| | does not meet the above any conditions ziplist | ziplist

Double – ended linked list implementation

In the two-end listlistNodeA nodevalueUsing theString objectI built it

Compressed list implementation

The hash object

Value types	qualification	encoding	Underlying data structure

| Simultaneously satisfy:

Key and Value lengths for all key-value pairs (hash-max-ziplist-valueControl) < 64 bytes

Number of elements (hash-max-ziplist-entriesControl) < 512 | ziplist | ziplist
| | does not meet the above any conditions hashtable | hashtable

Compressed list implementation

Hash object implementation using compressed lists, both key-value pairsThey're stored in pairs
Always fromThe tail nodeInsert,KeyIn the former,ValueIn the latter

Hash table implementation

A collection of objects

Value types	qualification	encoding	Underlying data structure
An integer value	Simultaneously satisfy: All elements are integral values Number of elements (`set-max-intset-entries`Control) < 512	intset	intset

| | does not meet the above any conditions hashtable | hashtable

Integer set implementation

Hash table implementation

When using hash tables as the underlying data structure, passdictEntryIn thekeyThere are values to store,valueIs empty

An ordered set

Value types	qualification	encoding	Underlying data structure

| Simultaneously satisfy:

All element lengths (zset-max-ziplist-valueControl) < 64

Number of elements (zset-max-ziplist-entriesControl) < 128 | ziplist | ziplist
| | does not meet the above any conditions skiplist | skiplist

Compressed list implementation

Implementation of ordered collection objects using compressed lists,The elementandscoreAre allThey're stored in pairs
Always fromThe tail nodeInsert,The elementIn the former,scoreIn the latter

Skip list implementation

Skip list implementation passedzsetStructure for implementation, including oneA dictionary (dict)And aJump table (skiplist)

/* * ordered set */
typedef struct zset {
    // dictionary, keys are members, values are points
    // This is used to support O(1) complexity
    dict *dict;
    // Skip list, sort members by point value
    // Used to support the O(log N) average complexity of locating members by point value operations
    // And scope operations
    zskiplist *zsl;
} zset;
Copy the code

dictIn the dictionary. Keys are members and values are points. Used to supportO(1)Complexity of the point by member operation
zslJump table. Sort members by point value. Used to supportO(log N)Locate member operations and range operations by point value

Why are ordered collections implemented using both dictionaries and skip lists?

useThe dictionaryWill retainO(1)Complexity lookup, but the score is unordered storage, cannot support sorting and range operations

useJump tablePoints order is preserved, sorting and range operations are supported, butO(log N)Complexity search

To sum up, in order to give full play to their respective advantages, the two data structures are redundant for storage. In addition, dictionaries and skip tables share element members and score values, thus avoiding object repetition and reducing memory space occupation

reference

Redis Design and Implementation

www.cnblogs.com/meituantech… Meituan’s exploration and practice of Redis Rehash mechanism

www.voidcn.com/article/p-p…

Blog.csdn.net/luoyanjiewa…

www.cnblogs.com/hunternet/p… Jump table

www.bilibili.com/read/cv9019… List of compression

redisbook.com/

Github.com/huangz1990/…

[Redis] Data structures and objects

1. Simple dynamic strings

Introduction to the

The data structure

The characteristics of

SDS is compatible with some C language functions

The role of SDS len

SDS reduces memory space reallocation when string changes

Preempted the space

SDS guarantees text binary security

2. List

Introduction to the

The data structure

The characteristics of

Usage scenarios

3. The dictionary

Introduction to the

The data structure

The underlying principle

Hash calculation

Hash collision

rehash

Before the expansion

Open the space

The underlying principle

Usage scenarios

5. Integer sets

Introduction to the

The data structure

Code upgrade

Usage scenarios

6. Compress lists

Introduction to the

The data structure

List of compression

Node information

Chain update

impact

The trigger condition

Usage scenarios

Object of 7.

Introduction to the

The data structure

Object type

String object

A list of objects

Double – ended linked list implementation

Compressed list implementation

The hash object

Compressed list implementation

Hash table implementation

A collection of objects

Integer set implementation

Hash table implementation

An ordered set

Compressed list implementation

Skip list implementation

reference

Related Posts

SAP CRM WebClient UI Report transaction data request and response

How the Thread class, the cornerstone of concurrent programming, works

Computer Network Interview Questions Ii (2021 Latest edition)