Shulou(Shulou.com)06/01 Report--

2018-1-3 by Atlas1. SDS description

The bottom layer of redis is written in C language, while redis does not directly use the string representation of C language, but constructs an abstract type called simple dynamic string, namely SDS (simple dynamic string).

In redis database, key-value pairs containing string values are all implemented by SDS at the bottom, and SDS can be said to be the cornerstone.

The AOF buffer in the AOF module and the input buffer in the client state are implemented by SDS.

Define the number of bytes used in the struct sdshdr {/ / record buf array / equal to the length of the string saved by SDS int len; / / record the number of unused bytes in the buf array int free; / / byte array, which is used to hold the string char buf [];} structure

The value of the free property is 0, indicating that there is no unused space for this SDS. The value of the len attribute is 5, indicating that the SDS holds a 5-byte string. The buf attribute is an array of type char. The first five bytes of the array hold five characters of'R','e','d','i', and's characters, and the last byte holds the empty character'\ 0'. Buf length = len+free+1. The policy SDS follows the convention that the C string ends with the empty character'\ 0'. The advantage is that part of the C string function can be reused directly. Compared to the C string SDS, the length of the SDS itself is recorded in the len attribute, so the complexity of getting the SDS length is only O (1). It is safer to read characters than the C string SDS not by ending the empty character'\ 0' but by the len attribute, so that redis can save not only text data, but also binary data in any format. The space allocation strategy compared to the C string SDS completely eliminates the possibility of buffer overflow. Check whether the free property meets the modification requirements. If not, automatically expand the space and then perform the modification operation. If there is enough space, there is no need to perform memory redistribution. The space allocation strategy optimizes the strategy space pre-allocation and inert space release to reduce the number of memory reallocation. Space pre-allocation formula:

If the len of SDS is less than 1MB after modifying SDS, then allocate free space of the same size as the len attribute

If after modifying SDS, the len of SDS will be greater than or equal to 1MB, then allocate the free space of 1MB. The lazy space release strategy is the extra space reservation released by the SDS space modification operation to avoid shortening the memory reallocation of strings and providing possible string growth in the future. SDS provides API to free up SDS space, so you don't have to worry about memory waste caused by lazy space release. 2. LIST description

The linked list provides efficient node rearrangement ability and sequential node access, and the length of the linked list can be flexibly adjusted by adding and deleting nodes.

One of the underlying implementations of list keys is the linked list.

Publish and subscribe, slow query, monitor and other functions also use the linked list, the redis server itself also uses the linked list to store the status information of multiple clients, and uses the linked list to build the client output buffer.

Define the value of typeof struct listNode {/ / front node struct listNode * prev; / / post node struct listNode * next; / / void * value;} listNode;typeof struct list {/ / header node listNode * head; / / footer node listNode * tail / / number of nodes in the linked list unsigned long len; / / 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);} list; structure

strategy

Double-ended: the linked list node has prev and next pointers, and the complexity of getting the front and back nodes of a node is O (1).

Acyclic: both the prev pointer of the header node and the next pointer of the footer node point to NULL, and access to the linked list ends with NULL.

Length counter with linked list: the len attribute of the list structure makes the complexity of getting the number of linked list nodes O (1).

Polymorphism: linked list nodes use void * pointers to save node values, and you can set type-specific functions for nodes through the dup, free, and match properties of the list structure, so linked lists can hold different types of values.

3. HASH description

A dictionary is an abstract data structure used to hold key-value pairs.

The keys in the dictionary are unique.

The redis database is implemented using dictionaries as the underlying implementation.

The dictionary is also one of the underlying implementations of the hash key.

Define typeof struct dictEntry {/ / key void * key; / / value union {void * val; unit64_t u64; int64_t s64;} v; / / next node struct dictEntry * next;} dictEntry;typeof struct dictht {/ / hash table array dictEntry * * table / / Hash table size unsigned long size; / / Hash table size mask, which is used to calculate the index value / / always equal to the number of existing nodes in the hash table unsigned long used;} dictht;typeof struct dictType {/ / the function unsigned int (* hashFunction) (const void * key) that calculates the hash value / / copy key function void * (* keyDup) (void * privdata, const void * key); / / copy value function void * (* valDup) (void * privdata, const void * obj); / / compare key function int (* keyCompare) (void * privdata, const void * key1,const void * key2) / / function for destroying keys void (* keyDestructor) (void * privdata, void * key); / / functions for destroying values void (* valDestructor) (void * privdata, void * val);} dictType;typeof struct dict {/ / type-specific function dictType * type; / / private data void * privadata; / / hash table dictht ht [2] / / rehash index / / when rehash is not in progress, the value is-1 int trehashidx;} dict; structure

The policy ht attribute is an array of two items. In general, dictionaries only use ht [0], and ht [1] is only used when rehash. Hash algorithm:

Hash = dict- > type- > hashFuncton (key)

Index = hash&dict- > ht [x] .sizemash; the solution to hash conflicts is the link address method. Unlike the java data structure hashMap, which is a single linked list, the newly inserted node is more likely to be accessed next when the header position is inserted. Rehash operation:

If an extension operation is performed, the size of ht [1] is the first one greater than or equal to the nth power of 2 of ht [0] .used * 2.

If a shrink operation is performed, the size of ht [1] is the first greater than or equal to the n-power of 2 of ht [0]. Used. Hash table load factor formula:

Load factor = number of hash table saved nodes / hash table size

Load_factor = ht [0] .used / ht [0] .size program automatically performs hash table expansion operation conditions:

The server is not currently executing BGSAVE or BGREWRITEAOF commands, and the load factor is greater than or equal to 1.

The server is currently executing a BGSAVE or BGREWRITEAOF command with a load factor greater than or equal to 5. The conditions under which the program automatically performs a hash table contraction operation:

The load factor of the hash table is less than 0.1. Hash table divide-and-conquer progressive rehash steps:

1) allocate space for ht [1], and the dictionary holds both ht [0] and ht [1].

2) if rehashidx is set to 0, it means that rehash starts.

3) during rehash, each deletion, search, or update operation on the dictionary will be carried out on two hash tables. In addition to performing the specified operation, the program will also rehash the key value pair of ht [0] to ht [1]. Each time the dictionary is added, the newly added key value pair will be saved to ht [1] instead of adding to ht [0]. After rehash, the value of ht will be increased by one.

4) with the continuous progress of dictionary operation, at some point in time, all key-value pairs of ht [0] will be rehash to ht [1], and set rehashidx to-1, indicating that the rehash operation is complete.

5) release ht [0], set ht [1] to ht [0], and then assign a blank hash table to ht [1]. 4. SKIPLIST description

Jump table is an ordered data structure, which can quickly access nodes by maintaining multiple pointers to other nodes in each node.

The jump table supports node lookup with average O (logN) and worst O (N) complexity, and can also batch process nodes through sequency.

In most cases, the efficiency of the jump table is comparable to that of the balanced tree, and the implementation is relatively simple.

Redis uses jump tables one place as one of the underlying implementations of ordered collection keys and the other as internal data structures in cluster nodes.

Define typeof struct zskiplistNode {/ / backward pointer struct zskiplistNode * backward; / / score double score; / / member object robj * obj; / / layer struct zskiplistLevel {/ / forward pointer struct zskiplistNode * forward; / / Span unsigned int span } level [];} zskiplistNode;typeof struct zskiplist {/ / header node, footer node struct skiplistNode * header,*tail; / / number of nodes in the table unsigned long length; / / maximum number of layers in the table int level;} zskiplist; structure

strategy

Header points to the header node of the jump table.

Tail points to the footer node of the jump table.

Level records the number of layers of the node with the largest number of outer headers in the jump table.

Length records the number of nodes outside the header in the jump table.

Layer: the forward pointer is used to access the node at the end of the table, while the span records the distance between the forward pointer and the current node.

The back pointer points to the previous node at the current node, traversing from the end of the table to the header.

Each node is arranged from small to large according to its saved score.

5. INTSET description

The set of integers is one of the underlying implementations of the collection key. When a set contains only integer-valued elements and the number of elements in the set is small, redis will use the set of integers as the underlying implementation of the collection key.

You can save integer values of int16_t, int32_t, int64_t.

Defines the number of elements contained in the typeof struct intset {/ / Encoding unit32_t encoding; / / collection unit32_t lenght; / / Array int8_t contents of saved elements [];} intset; structure

INTSET_ENC_INT16 means that the underlying implementation of a collection of integers is an array of type int16_t, and the collection holds integer values of type int16_t.

A value of 5 for the length attribute indicates that it contains five elements.

The contents array holds the five elements of the collection in attributes from small to large.

The size of the contents array is equal to 16 * 5 = 80 bits.

INTSET_ENC_INT64 means that the underlying implementation of a collection of integers is an array of type int64_t, and the collection holds integer values of type int64_t.

A value of 4 for the length attribute indicates that it contains four elements.

The contents array holds the four elements of the collection in attributes from small to large.

The size of the contents array equals 64 * 4 = 256 bits.

strategy

Upgrading a set of integers to merge and adding new elements is a three-step process:

1) expand the space of the underlying array of the set of integers according to the new element type and allocate space for the new element.

2) to convert all the existing elements of the underlying array to the same type as the new elements, and put the converted elements into the correct bits, it is necessary to keep the ordered properties of the underlying array unchanged.

3) add the new element to the underlying array.

6. ZIPLIST description

A compressed list is one of the underlying implementations of list keys and hash keys.

When a list key contains only a small number of list items, and each list item is either a small integer value or a short string, redis uses a compressed list as the underlying implementation of the list key.

When a hash key contains only a small number of key-value pairs, and each key-value pair is either a small integer value or a short string, redis uses a compressed list as the underlying implementation of the hash key.

Define

A sequential data structure consisting of a series of specially coded continuous memory blocks. It can contain any number of nodes, each of which can hold an array of bytes or an integer value.

structure

Zlbytes records the number of bytes of memory consumed by the entire compressed list.

Zltail records the number of bytes between the tail node of the compressed list and the starting address of the compressed list. Through the entire offset, the program can determine the address of the tail node without traversing the entire compressed list.

Zllen records the number of nodes in the compressed list.

EntryX is the node of the compressed list.

Zlend is used to mark the end of the compressed list.

strategy

The compressed list traverses backwards from the footer node, first by pointing the pointer to the footer node through the zltail offset, and then by traversing the entire compressed list forward by pointing to the length of the previous node recorded by the node.

This is the underlying data structure of the redis basic data type.

Reference: "redis Design and implementation"

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.