Click “Party Friends” above and select “Top or star mark”

Your attention means a lot!

Author: My name is Liu Banxian

Source: my.oschina.net/liughDevelop/blog/2236771

Organized by the Java technology stack

The content of the mind map is as follows:

1

Introduction and Application

Redis is a high-performance, network-enabled, persistent K-K in-memory database written in ANSI C and provides multiple language apis. The commonly used types are String, List, Hash, Set, and ZSet.

 

Redis generally has the following applications in Internet companies:

  • String: cache, traffic limiting, counter, distributed lock, distributed Session

  • Hash: Stores user information, home page access volume, and combined query

  • List: timeline List and simple queue of followers on Weibo

  • Set: likes, clicks, tags, friends

  • Zset: Leaderboards

Another example is that e-commerce will use some special designs to ensure the stability of the system during big promotions. The following designs can be considered for inventory reduction:

In the figure above, the inventory is directly deducted in Redis, and then the log is recorded and synchronized to the database through the Worker. The problems of concurrent processing and repeated processing need to be considered when designing the synchronization Worker.

It can be seen from the above application scenarios that Redis is very efficient and stable. How is the bottom layer of Redis realized?

2

Redis object redisObject

When we execute the set Hello world command, we have the following data model:

                          

  • DictEntry: Redis assigns a dictEntry to each key-value pair, in which there are Pointers to key and val, and next points to the next dictEntry to form a linked list. This pointer can link together multiple key-value pairs with the same hash value to solve the hash conflict problem (chained address method).

  • SDS: Key “Hello” is stored in SDS (simple dynamic string), as described later.

  • RedisObject: The value val “world” is stored in redisObject. In fact, redis usually stores all 5 types as redisObject; The Type field in redisObject specifies the type of the Value object, and the PTR field points to the address of the object.

RedisObject is very important. The types, internal encoding, memory reclamation, shared objects and other functions of Redis objects need to be supported by redisObject. The advantage of this design is that different data structure implementations can be set for different usage scenarios of the five common types, so as to optimize the use efficiency of objects in different scenarios.

Both dictEntry objects, redisobjects and SDS require a memory allocator (such as Jemalloc) to allocate memory for storage. Jemalloc, the default memory allocator for Redis, does a relatively good job of reducing memory fragmentation.

For example, jemalloc divides the memory space into three ranges: small, large and huge in 64-bit system. Each range is divided into many small memory block units; When Redis stores data, it selects the most appropriate memory block for storage.

As mentioned earlier, each Redis object is represented by a redisObject structure whose PTR pointer points to the underlying implementation’s data structure, which is determined by the Encoding property. For example, we get the encoding to store “hello” by executing the following command:

All redis data structures are of the following type (important, used later) :

3

String

The underlying implementations of string objects can be int, RAW, or embstr (the table above should be named). Embstr encoding allocates a contiguous block of space by calling the memory allocation function once, whereas RAW requires two calls.

Int encoding string objects and EMbstr encoding string objects are converted to raw encoding string objects under certain conditions. Embstr: a string of <=39 bytes. Int: a long integer of 8 bytes. Raw: The string contains more than 39 bytes.

Simple dynamic strings (SDS), which are more like C++ strings or Java ArrayList<Character>, are dynamically variable in length:

Struct SDSHDR {// buf length int len; // The length of the free space in buf int free; // Data space char buf[]; // '\0' null-terminated};Copy the code

     

  • The get: sdsrange – O (n)

  • Set: sdscpy – O (n)

  • Create: sdsnew – O (1)

  • Len: sdslen – O (1)

Constant complexity to get string length: Because SDS records the length in the len attribute, the time complexity to get an SDS length is only O(1).

Prespace allocation: If an SDS is modified, there are two cases:

  • If the SDS length (len) is less than 1MB, the program allocates the same amount of unused space as len, in which case free and len have the same value. For example, if len of SDS becomes 15 bytes, the program allocates 15 bytes of unused space, and the actual length of the BUF array of SDS becomes 15+15+1=31 bytes (an extra byte for the user-saved null character).

  • SDS length (len value) is greater than or equal to 1MB, the program allocates 1MB of unused space. For example, after modification, len of SDS is 30MB, then its actual length is 30MB+1MB+1byte.

Lazy free space: When SDSTRIm is executed, SDS does not immediately free the extra space. The next time the string is concatenated and the concatenated space is not as large as the free space, the unused space will be used. Memory reallocation operations that operate on strings in certain cases are avoided by lazy free space.

Avoid buffer overflow: When using C string operation, if the string length increases (such as strcat operation) and forget to reallocate memory, it is easy to cause buffer overflow; SDS, on the other hand, because it records the length, automatically reallocates the memory when the corresponding operation may cause buffer overflow, eliminating buffer overflow.

4

List

The underlying implementation of List objects is quicklist (a quicklist, a combination of ziplist compressed lists and linkedlist double-ended lists). Lists in Redis support both insertion and pop-up, and can obtain elements in a specified position (or range), which can act as arrays, queues, stacks, and so on.

Typedef struct listNode {// struct listNode *prev; Struct listNode *next; Void *value; } listNode; Typedef struct list {// listNode *head; // listNode *tail; Void *(*dup)(void * PTR); Void (*free)(void * PTR); Int (*match)(void * PTR, void *key); Unsigned long len; } list;Copy the code

　   

  • rpush: listAddNodeHead —O(1)

  • lpush: listAddNodeTail —O(1)

  • push:listInsertNode —O(1)

  • index : listIndex —O(N)

  • pop:ListFirst/listLast —O(1)

  • llen:listLength —O(N)

4.1 LinkedList

This structure is more like a Java LinkedList, you can read the source code if you are interested.

     

As can be seen from the figure, Redis’ linkedList has the following features: The nodes have prev, next, head and tail Pointers, and the complexity of acquiring the front node, the back node, the head node and the tail node is O (1). The len attribute also gets the number of nodes is O (1).

Compared with double-entailed lists, compressed lists can save memory space, but have higher complexity when modifying or adding or deleting. Therefore, when the number of nodes is small, the compressed list can be used. However, with a large number of nodes, it is still cost-effective to use a double-entailed list. For more information, please reply at the background of Java Technology Stack wechat official account: Redis.

4.2 Ziplist (Compressed List)

Redis uses ziplist (compressed list) for the underlying implementation of a list key when it contains only a small number of list items and is a small integer value or short string length.

Ziplist was developed by Redis to save memory. It is a sequential data structure composed of a series of contiguous chunks of memory specially coded (rather than each node being a pointer like a double-endian linked list). The specific structure is relatively complex, interested readers can see Redis hash structure memory model analysis. Quicklist replaces Ziplist and LinkedList in the new version:

QuickList is a hybrid of zipList and linkedList. It splits the linkedList into segments, each of which is stored compactly using a zipList, and connects multiple Ziplists using a bidirectional pointer. Because the attached space of the linked list is relatively high, the prev and next Pointers take up 16 bytes (compared to 8 bytes in 64-bit systems). In addition, the memory of each node is allocated separately, which will increase the fragmentation of memory and affect the efficiency of memory management. Recommended reading: 50 Redis Interview Questions.

Quicklist’s default compression depth is 0, meaning no compression. To support fast push/pop operations, the first and last ziplists of the QuickList are uncompressed, and the depth is 1. To further save space, Redis will compress ziplist and store it using LZF algorithm. For more information, please reply at the background of Java Technology Stack wechat official account: Redis.

5

Hash

The underlying implementation of Hash objects can be ziplist (compressed list) or Hashtable (dictionary or Hash table).

Ziplist (compressed list) is used only if the Hash object meets both of the following conditions: 1. The number of elements in the hash is less than 512. 2. The key and value strings of all key-value pairs in the hash are shorter than 64 bytes.

Hashtable Hash tables are efficient because they can perform O(1) complexity read and write operations. The source code is as follows:

Typedef struct dict {// type specific function dictType *type; // Private data void * privData; // Dictht ht[2]; // Rehash index // If rehash is not in progress, the value is -1 int rehashidx; /* Rehashing not in progress if rehashidx == -1 */ / /* number of iterators currently running */} dict; Typedef struct dictht {// dictEntry **table; // Hash table size unsigned long size; // Always equal to size-1 unsigned long sizemask; // The number of existing nodes in the hash table unsigned long used; } dictht; typedef struct dictEntry { void *key; union {void *val; uint64_t u64; int64_t s64; } v; Struct dictEntry *next; struct dictEntry *next; } dictEntry; Typedef struct dictType {// calculate the hashFunction unsigned int (*hashFunction)(const void *key); Void *(*keyDup)(void * privData, const void *key); Void *(*valDup)(void * privData, const void *obj); Int (*keyCompare)(void * privData, const void *key1, const void *key2); Void (*keyDestructor)(void * privData, void *key); Void (*valDestructor)(void * privData, void *obj); } dictType;Copy the code

The above source code can be simplified into the following structure:

                   

This structure is similar to JDK7’s old HashMap<String,Object>, which causes hash collisions when two or more keys are assigned to the same index of the hash array.

Redis also uses the chained address method to resolve key collisions. That is, each hash table node has a next pointer, and multiple hash table nodes use the next pointer to form a single necklace list. Linked address method is to organize objects with the same hash value into a linked list and place them in the slot corresponding to the hash value.

If the dictionary in Redis uses HashTable as the underlying implementation, each dictionary will have two hash tables, one for normal use and one for rehash only. As you operate on the hash table, the number of keys increases or decreases. Recommended reading: This is probably the most comprehensive Redis high availability solution ever.

To keep the load factor of the hash table within a reasonable range, Redis rehashes the size of the hash table, that is, rehashes all key/value pairs in HT [0] into HT [1] incrementally.

6

Set

The underlying implementation of a Set object can be an intset (a Set of integers) or a hashtable (a dictionary or hashtable).

An intSet is used as the underlying implementation of Set objects when a Set contains only integers and has few elements.

// uint32_t encoding; // Uint32_t length; Int8_t contents[]; } intset;
Copy the code

  • sadd:intsetAdd—O(1)

  • smembers:intsetGetO(1)—O(N)

  • srem:intsetRemove—O(N)

  • slen:intsetlen —O(1)

Intset’s underlying implementation is an ordered, non-repeating array that holds collection elements. Intset The int array can be 16 -, 32 -, or 64 – bit. If all the integers in the array are 16 bits long and a new 32 bit integer is added, the entire array of 16 will be upgraded to a 32 bit array. The upgrade improves intSet flexibility and saves memory, but is not reversible.

7

ZSet

The underlying implementation of ZSet ordered collections objects can be ziplist (compressed list) or skiplist (skiplist).

When an ordered set has a large number of elements or long strings of members, Redis uses skiplist as the underlying implementation of ZSet objects.

Typedef struct zskiplist {// struct zskiplistNode *header, *tail; // The number of nodes in the table unsigned long length; Int level; int level; } zskiplist; Typedef struct zskiplistNode {// robj *obj; // double score; Struct zskiplistNode *backward; Struct zskiplistNode *forward; struct zskiplistNode *forward; // span -- the distance between the forward pointer and the current node unsigned int span; } level[]; } zskiplistNode;
Copy the code

Zadd –zslinsert– average O(logN), worst O(N)

Zrem –zsldelete– average O(logN), worst O(N)

Zrank –zslGetRank– Average O(logN), worst O(N)

    

Skiplist’s search time complexity is LogN, which is comparable to balanced binary trees, but simpler to implement. A skiplist is an ordered data structure that maintains multiple Pointers to other nodes in a node for fast access to nodes.

– More articles –

Build a distributed & NBSP for yourself; IM(instant messaging)& NBSP; system

Big data employment prospects, analysis is too in place!

What is the CPU doing when it is soaring

Ali distributed transaction framework GTS open source!

SpringCloud essay: Document a giant crater encountered while using OAuth2

– Focus on me

When you’re done, order a “good-looking” duck

Points duck duck

Left left left left down down down