directory

First, meet Redis

Second, Redis 5 big data types

Third, Redis SDS underlying data structure analysis

4. Analysis of linked list data structure

5. List data structures

1. Compress lists

2. Quick lists

6. Redis Dictionary

Redis integer set

Redis skipper

9. Redis objects

X. Redis usage scenarios

First, meet Redis

Recent entry learning Redis database, learn from the simplest content, and then summarize the record in this, in order to forget, also share with you!

Windows installation as shown below:

Download address:

Windows:github.com/microsoftar…

Linux: download. Redis. IO/releases/re…

Server side:

The Client side:

As a high-performance, open source NoSQL database, Redis mainly uses the form of key-value pair storage data, developed in C language, using BSD protocol, powerful, support a variety of data types, belonging to a non-relational database.

Different from Mysql, SQLServer, Oracle and other relational databases. Therefore, Redis features a number of advantages:

Support multiple programming languages, Such as Java, C, C++, Python, PHP, Go, Lua, etc.

It contains rich data types, Such as String, List, Set, Hash, and Sorted Set.

Fast read/write speed and high performance. Official data: The read speed is 110000 times /s, and the write speed is 81000 times /s, meaning that data is stored in memory for reading and writing.

Persistence. The important feature of Redis is to realize persistence, which periodically saves the data in memory to disk and reloads it into memory when the server restarts. The persistence modes include AOF and RDB.

Simple and powerful. You can implement message subscription publishing, Lua scripts, database transactions, and more. Redis is single-threaded, all operations are atomic and simple to use.

Implement high availability primary/secondary replication.

Realize distributed Cluster and high availability, respectively Redis Cluster and Redis Sentinel.

Support for multiple data structures. Such as Hash, Set, and bitmap.

Here are the five data types of Redis.

Second, Redis 5 big data types

Redis 5 big data operation commands are as follows: www.redis.cn/commands.ht…

1. String String

Strings are the most basic data type in Redis and are binary safe. A String key stores a maximum of 512 MB of data.

The supported data includes binary data, serialized data, and jSONized objects.

2. Hash

The Hash type is a mapping table of fields and values of String type. It is used to store object information. Each hash table can store 2^32-1 key-value pairs, equivalent to 4 billion data.

3**, List**

Redis lists are similar to simple string lists, sorted by insertion order, and can be manipulated to insert an element into the top or bottom of the table. You can also store 2^32-1 elements.

The Set data type is an unordered collection of strings, each element unique. Set through hash table to achieve, add and delete high efficiency, complexity O(1). A collection can hold up to 2^32-1 elements.

5, Sorted set Sorted Sort

An ordered collection is a collection of strings where each element corresponds to a value of type double. Redis sorts elements according to the size of this value, which is also achieved by hash table, with high efficiency in addition and deletion and complexity O(1). A collection can hold up to 2^32-1 elements.

Third, Redis SDS underlying data structure analysis

Redis is written by C language, and the underlying implementation has the syntax and characteristics of C language. Instead of using the string type in C directly, WE built our own SDS (Simple dynamic String) type as the Redis default string.

SDS source code:

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
Copy the code

As you can see from the underlying code, multiple constructs are defined to accommodate different requirements.

C string and SDS difference:

C string API is binary insecure, may have buffer overflow, only store text data, can use all the library functions of String. h, change the length of memory once allocation, get string length time complexity O(n).
SDS API is binary safe, there is no buffer overflow, text/binary data can be saved, using partial string.h library functions, modify N length allocation memory times <=N, get length O(1).

4. Analysis of linked list data structure

/* Node, List, and Iterator are the only data structures used currently. */

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    PORT_ULONG len;
} list;
Copy the code

There is no built-in linked list structure in C language. Redis builds a linked list by itself, using a bidirectional linked list, which is composed of multiple discrete nodes connected by Pointers. Each node has a precursor node and a successor node, except for the head node (no precursor) and tail node (no successor).

5. List data structures

1. Compress lists

#ifndef _ZIPLIST_H
#define _ZIPLIST_H

#define ZIPLIST_HEAD 0
#define ZIPLIST_TAIL 1

unsigned char *ziplistNew(void);
unsigned char *ziplistMerge(unsigned char **first, unsigned char **second);
unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where);
unsigned char *ziplistIndex(unsigned char *zl, int index);
unsigned char *ziplistNext(unsigned char *zl, unsigned char *p);
unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p);
unsigned int ziplistGet(unsigned char *p, unsigned char **sval, unsigned int *slen, PORT_LONGLONG *lval);
unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen);
unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p);
unsigned char *ziplistDeleteRange(unsigned char *zl, int index, unsigned int num);
unsigned int ziplistCompare(unsigned char *p, unsigned char *s, unsigned int slen);
unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip);
unsigned int ziplistLen(unsigned char *zl);
size_t ziplistBlobLen(unsigned char *zl);

#ifdef REDIS_TEST
int ziplistTest(int argc, char *argv[]);
#endif

#endif /* _ZIPLIST_H */
Copy the code

Redis compressed lists are implemented by the list key and hash key base.

Redis uses compressed lists, which are sequential data structures, when the list contains few elements and the value is small.

2. Quick lists

A fast list is a bidirectional linked list consisting of a compressed list, and each node of the linked list stores data in the compressed list.

The list is defined as follows:

typedef struct quicklist { quicklistNode *head; quicklistNode *tail; PORT_ULONG count; /* total count of all entries in all ziplists */ unsigned int len; /* number of quicklistNodes */ int fill : 16; /* fill factor for individual nodes */ unsigned int compress : 16; /* depth of end nodes not to compress; 0=off */ } quicklist;Copy the code

Quick list nodes:

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;
Copy the code

6. Redis Dictionary

Redis dictionary is a data structure used to store Redis key value pairs. It is also built by Redis itself. The bottom layer of Redis database is also implemented by dictionaries, and CURD operations are built on the dictionary.

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

typedef struct dictType {
    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;

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    dictEntry **table;
    PORT_ULONG size;
    PORT_ULONG sizemask;
    PORT_ULONG used;
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    PORT_LONG rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;
Copy the code

Redis integer set

Redis uses this data structure to implement the bottom layer of the collection key when a collection contains only integer numeric elements and the number of elements is small.

#ifndef __INTSET_H
#define __INTSET_H
#include <stdint.h>

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

intset *intsetNew(void);
intset *intsetAdd(intset *is, int64_t value, uint8_t *success);
intset *intsetRemove(intset *is, int64_t value, int *success);
uint8_t intsetFind(intset *is, int64_t value);
int64_t intsetRandom(intset *is);
uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value);
uint32_t intsetLen(intset *is);
size_t intsetBlobLen(intset *is);

#ifdef REDIS_TEST
int intsetTest(int argc, char *argv[]);
#endif

#endif // __INTSET_H
Copy the code

Redis skipper

Skip table is an ordered data structure that supports fast node search and batch processing of nodes. If an ordered collection has a large number of elements with long string values, Redis uses a skip table as the underlying implementation of the ordered collection.

9. Redis objects

The above data structure of Redis, in fact, is not directly used, but to create a system of objects, including string objects, list objects, etc. The Red IS object system implements the memory reclamation mechanism based on the reference counting technology. When an object is not in use, the system automatically reclaims the memory space occupied by the object.

robj *dupStringObject(robj *o) {
    robj *d;

    serverAssert(o->type == OBJ_STRING);

    switch(o->encoding) {
    case OBJ_ENCODING_RAW:
        return createRawStringObject(o->ptr,sdslen(o->ptr));
    case OBJ_ENCODING_EMBSTR:
        return createEmbeddedStringObject(o->ptr,sdslen(o->ptr));
    case OBJ_ENCODING_INT:
        d = createObject(OBJ_STRING, NULL);
        d->encoding = OBJ_ENCODING_INT;
        d->ptr = o->ptr;
        return d;
    default:
        serverPanic("Wrong encoding.");
        break;
    }
}

robj *createQuicklistObject(void) {
    quicklist *l = quicklistCreate();
    robj *o = createObject(OBJ_LIST,l);
    o->encoding = OBJ_ENCODING_QUICKLIST;
    return o;
}

robj *createZiplistObject(void) {
    unsigned char *zl = ziplistNew();
    robj *o = createObject(OBJ_LIST,zl);
    o->encoding = OBJ_ENCODING_ZIPLIST;
    return o;
}

robj *createSetObject(void) {
    dict *d = dictCreate(&setDictType,NULL);
    robj *o = createObject(OBJ_SET,d);
    o->encoding = OBJ_ENCODING_HT;
    return o;
}

robj *createIntsetObject(void) {
    intset *is = intsetNew();
    robj *o = createObject(OBJ_SET,is);
    o->encoding = OBJ_ENCODING_INTSET;
    return o;
}

robj *createHashObject(void) {
    unsigned char *zl = ziplistNew();
    robj *o = createObject(OBJ_HASH, zl);
    o->encoding = OBJ_ENCODING_ZIPLIST;
    return o;
}

robj *createZsetObject(void) {
    zset *zs = zmalloc(sizeof(*zs));
    robj *o;

    zs->dict = dictCreate(&zsetDictType,NULL);
    zs->zsl = zslCreate();
    o = createObject(OBJ_ZSET,zs);
    o->encoding = OBJ_ENCODING_SKIPLIST;
    return o;
}

robj *createZsetZiplistObject(void) {
    unsigned char *zl = ziplistNew();
    robj *o = createObject(OBJ_ZSET,zl);
    o->encoding = OBJ_ENCODING_ZIPLIST;
    return o;
}
Copy the code

X. Redis usage scenarios

Speaking so many Redis theory knowledge points, why do you see the advantage?

In practical application, Redis can be introduced into every major website and system, and it is widely used to solve the problem that relational database cannot solve.

Redis usage scenarios:

Do the cache. The most common use scenario for Redis. It does not need to regenerate data every time and is fast in caching and querying. Cache news content, product information, or shopping cart, etc.

Make a counter. Redis operations are atomic. It can be used to record the number of forwards and comments.

Implement message queuing system. Support pattern matching, can realize message subscription publishing. The blocking queue command enables activities such as seckilling and buying.

Real-time system, messaging system. Redis set function can be used to view the user’s specific operation to achieve a real-time system.

Billions of ranks. It’s also a key Redis app that uses ordered collections to rank hundreds of millions of users in real time, thanks to Redis’s read and write speed.

Big social networks. For example, QQ, Weibo, etc., users need Redis support for browsing and chatting.

This article is xiaobai recent entry learning Redis database, from the most simple content learning record, also share with you! Redis, as a high-performance, open source NoSQL database, is different from Mysql, SQLServer, Oracle and other relational databases. Therefore, The characteristics of Redis give it many advantages. There are many important places are not recorded here, such as persistence specific implementation principle AOF, RDB, Redis cluster, etc., after learning free in the record!

If you feel good welcome “one key three even” oh, like collection attention, have a problem direct comment, exchange learning!

In this paper, starting my CSDN blog: blog.csdn.net/Charzous/ar…

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

What is the principle and data structure of Redis, a powerful NoSQL database?

First, meet Redis

Second, Redis 5 big data types

Third, Redis SDS underlying data structure analysis

4. Analysis of linked list data structure

5. List data structures

1. Compress lists

2. Quick lists

6. Redis Dictionary

Redis integer set

Redis skipper

9. Redis objects

X. Redis usage scenarios

What is the principle and data structure of Redis, a powerful NoSQL database?

First, meet Redis

Second, Redis 5 big data types

Third, Redis SDS underlying data structure analysis

4. Analysis of linked list data structure

5. List data structures

1. Compress lists

2. Quick lists

6. Redis Dictionary

Redis integer set

Redis skipper

9. Redis objects

X. Redis usage scenarios

Related Posts

Look along the Hubble to see MyBatis overall architecture

A useful Chrome extension: SAP UI5 Inspector

Install the JDK environment in Linux