“This is my 35th day of participating in the First Challenge 2022. For more details: First Challenge 2022.”

The data structure

The source code is as follows:

typedef struct redisObject {
    / / type
    unsigned type:4;
    / / code
    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;
    // A pointer to the underlying data structure (mimicking polymorphism, which can store any type of object)
    void *ptr;
} robj;
Copy the code

Object type (Type)

Object types are defined as follows:

/* The actual Redis Object */
// String object
#define OBJ_STRING 0    /* String object. */
// List objects
#define OBJ_LIST 1      /* List object. */
// Set objects
#define OBJ_SET 2       /* Set object. */
// Ordered collection objects
#define OBJ_ZSET 3      /* Sorted set object. */
// Hash objects
#define OBJ_HASH 4      /* Hash object. */
​
/* The "module" object type is a special one that signals that the object * is one directly managed by a Redis module. In this case the value points * to a moduleValue struct, which contains the object value (which is only * handled by the module itself) and the RedisModuleType struct which lists * function pointers in order to serialize, deserialize, AOF-rewrite and * free the object. * * Inside the RDB file, module types are encoded as OBJ_MODULE followed * by a 64 bit module type ID, which has a 54 bits module-specific signature * in order to dispatch the loading to the right module, plus a 10 bits * encoding version. */
#define OBJ_MODULE 5    /* Module object. */
#define OBJ_STREAM 6    /* Stream object. */
Copy the code

The corresponding type command is mainly used to store the types of redis objects

For example, query key for redis datatype:

Object encoding

The object’s PTR pointer points to the object’s underlying data structures, which are determined by the object’s Encoding property.

The encoding property specifies the encoding used by the object, that is, what data structure the object uses as its implementation. The value of this property is one of the constants listed in the following table:

/* Objects encoding. Some kind of objects like Strings and Hashes can be * internally represented in multiple ways. The 'encoding' field of the object * is set to one of this fields for this object. */
// Simple dynamic string
#define OBJ_ENCODING_RAW 0     /* Raw representation */
// Integer of type long
#define OBJ_ENCODING_INT 1     /* Encoded as integer */
/ / a dictionary
#define OBJ_ENCODING_HT 2      /* Encoded as hash table */
/ / map
#define OBJ_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
// Double endian list
#define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */
// Compress the linked list
#define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
// Set of integers
#define OBJ_ENCODING_INTSET 6  /* Encoded as intset */
/ / jump table
#define OBJ_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
#define OBJ_ENCODING_EMBSTR 8  /* Embedded sds string encoding */
/ / table
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of listpacks */
#define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */
#define OBJ_ENCODING_LISTPACK 11 /* Encoded as a listpack */
Copy the code

Each type of object uses at least two different encodings, which are selected when the object is created

Object Encoding Prints the following code without encoding

char *strEncoding(int encoding) {
    switch(encoding) {
    case OBJ_ENCODING_RAW: return "raw";
    case OBJ_ENCODING_INT: return "int";
    case OBJ_ENCODING_HT: return "hashtable";
    case OBJ_ENCODING_QUICKLIST: return "quicklist";
    case OBJ_ENCODING_ZIPLIST: return "ziplist";
    case OBJ_ENCODING_LISTPACK: return "listpack";
    case OBJ_ENCODING_INTSET: return "intset";
    case OBJ_ENCODING_SKIPLIST: return "skiplist";
    case OBJ_ENCODING_EMBSTR: return "embstr";
    case OBJ_ENCODING_STREAM: return "stream";
    default: return "unknown"; }}Copy the code

LFU and LRU

Lru: The objectidleTime command compares the LRU time with the current time to calculate the idling time of an object without changing the LRU value of the object. In addition, it is related to Redis memory collection. If Redis has maxMemory enabled and the memory reclamation algorithm is volatile- LRU or Allkey-LRU. When Redis occupies more memory than maxMemory specified, Redis preferentially selects the object with the longest idling time to free.

robj *createObject(int type, void *ptr) {
    robj *o = zmalloc(sizeof(*o));
    o->type = type;
    o->encoding = OBJ_ENCODING_RAW;
    o->ptr = ptr;
    o->refcount = 1;
    /* Set the LRU to the current lruclock (minutes resolution), or * alternatively the LFU counter. */
    // Distinguish LRU from LFU
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
    } else {
        o->lru = LRU_CLOCK();
    }
    return o;
}
Copy the code

Lfu: use objectfreq to check the number of times the counter is used. For counters, Redis uses logarithmic counters based on probability. Eight bits is enough to record very high azimuth frequencies.

This time calculation is not the same as LRU — it takes a minute timestamp to modulo 2^16

/* Return the current time in minutes, just taking the least significant * 16 bits. The returned time is suitable to be stored as LDT (last decrement * time) for the LFU implementation. */
unsigned long LFUGetTimeInMinutes(void) {
    return (server.unixtime/60) & 65535;
}
​
/* Given an object last access time, compute the minimum number of minutes * that elapsed since the last access. Handle overflow (ldt greater than * the current 16 bits minutes time) considering the time as wrapping * exactly once. */
unsigned long LFUTimeElapsed(unsigned long ldt) {
    unsigned long now = LFUGetTimeInMinutes();
    if (now >= ldt) return now-ldt;
    return 65535-ldt+now;
}
Copy the code

refcount

For the object refcount command, the redis shared objects are placed in the sharedObjectsStruct. The createShareObjects function is used to create shared objects, such as the common string, and 10000 string objects, which are integer values [0-9999]. The 10000 character number can be changed by adjusting the value of the REDIS_SHARED_INTEGERS parameter.

However, the shared object pool conflicts with the maxMemory + LRU policy, because the shared object, lRU is also shared, only the integer object pool, because the integer object pool is more likely to be reused, and the string is equal. The time complexity becomes O(n), especially for long strings (floating point numbers are stored using strings inside Redis).

added

A domain

In the redisObject data structure, the bit field in C is used to save memory, and the bit field operation is very convenient.

It is important to note that it is portable. For example, in some embedded systems, 1 byte is not 8 bits, and if your type is 2 bytes across, this may result in undesirable results, so it is necessary to populate 0 appropriately.

Time to calculate

The function to obtain the time belongs to the system call, which consumes resources. Therefore, Redis adopts the way of caching and periodically updates the serverCorn function.

int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) {
    // ...
    /* Update the time cache. */
    updateCachedTime(1);
    // ...
}  
Copy the code

Ustime, estime in the redisServer object

Lrulock in the Redis object

Note that atomicGet is used in Lrulock because it may be used in other threads, such as cluster state.