We all know that Redis defaults to 16 dB, but what is the underlying design structure of these dB’s? Let’s take a quick look at the source code. Important fields are commented

typedef struct redisDb { dict *dict; /* The keyspace for this DB dictionary data structure, very important */ dict *expires; /* Timeout of keys with a Timeout set expiration time */ dict *blocking_keys; /* Keys with clients waiting for data (BLPOP) list */ dict *ready_keys; /* Blocked keys that received a PUSH */ dict *watched_keys; /* WATCHED keys for MULTI/EXEC CAS transaction */ int id; /* Database ID */ long long avg_ttl; /* Average TTL, just for stats */ unsigned long expires_cursor; /* Cursor of the active expire cycle. */ list *defrag_later; /* List of key names to attempt to defrag one by one, gradually. */ } redisDb;Copy the code

All KVS in Redis are stored in dict, which is very important in Redis.

The dictionary DISC data structure is as follows

typedef struct dict { dictType *type; // void *privdata; dictht ht[2]; //hashtable, each dict has two such data structures, mainly used to hash long rehashidx; /* rehashing not in progress if rehashidx == -1; /* Number of iterators currently running through some fields of the record */} dict;Copy the code

When hash conflicts occur in Redis, we will use the header method (linked list) to solve them. However, if the linked list increases indefinitely, hashTable will degenerate into a linked list, affecting the query efficiency. In this case, we need to expand the previous array and move the old data to the new array. This process is called rehash

Then let’s look at the dictType

typedef struct dictType { uint64_t (*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
typedef struct dictht { dictEntry **table; // The first address pointing to the array is the core structure of the key pair unsigned long size; Unsigned long sizemask; // identical to size-1 unsigned long used; } dictht;Copy the code
typedef struct { void *key; // Union = value; void *val = void *val; // redisObject Uint64_t u64; int64_t s64; double d; } v; struct dictEntry *next; } dictEntry;Copy the code

Let’s look at the corresponding graph of memory relationships

typedef struct redisObject { unsigned type:4; // The current object type list String hash set zset unsigned Encoding :4; Unsigned lRU :LRU_BITS; /* LRU time (relative to global lru_clock) or * LFU data (least significant 8 bits frequency * and most significant 16 bits access time). */ int refcount; void *ptr; } robj;Copy the code

Finally we have a total diagram of redis memory relationship

#####1: Handling of integer encoding Let’s start with an example

127.0.0.1:6379> set type-int 12345 OK 127.0.0.1:6379> object encoding type-int "int" // Return encoding type is int 127.0.0.1:6379> Set type-int-long 12345678901234567890 OK 127.0.0.1:6379> object encoding type-int-long "embstr" // The encoding type returned is embstrCopy the code

If the length is less than 20, it is automatically converted to int. This is done in Redis

if (len <= 20 && string2l(s, len, &value))
Copy the code

In a redisObject, you can use PTR to store integer values directly without having to respace a SDS

#####2: Redis object string storage related optimization

127.0.0.1:6379> set type-str-short XXX OK 127.0.0.1:6379> object encoding type-str-short "embstr" 127.0.0.1:6379> set Type-str-long xxxxxxxxXXXX-xxxxxxxxxxxx-xxxxxxxxXXXX-x // The string length is 45 127.0.0.1:6379> object encoding type-str-long "Raw" 127.0.0.1:6379> set type-str-long2 XXXXxxxxXXXX-xxxxXXXXxxxx-xxxxXXXXXXXX-xxxxXXXXXXXXXXXX - // The string length is 44 127.0.0.1:6379> object encoding type-str-long2 "embstr"Copy the code

A redisobject is stored in memory. When the CPU completes an I/O, it reads the data in a buffer line. In Linux, a buffer line is 64 bytes. Actually, we can make a big estimate.

typedef struct redisObject {
    unsigned type:4;  //4bit
    unsigned encoding:4; //4bit
    unsigned lru:LRU_BITS; //24bit
    int refcount;   //4byte
    void *ptr;   //8byte
} robj;
Copy the code

A Redis object itself needs to be (4bit+4bit+24bit = 4byte) + 4byte + 8byte = 16byte

According to SDS allocation strategy, 48 bytes should be in the sdSHDR8 interval, and SDSHdr8 itself needs to be 3 bytes. SDS requires c language compatible function library, which always adds \0 at the end. So sdSHdr8 itself takes up 4 bytes, so there are 44 bytes left in a buffer line to store the rest of the data, so in redis string objects, when the length is less than 44, the encoding is of type embstr, and no new SDS space is opened

Follow my technical official account: Programmer_grow. There are excellent technical articles sent every week.