Redis source code and design analysis -- 9. String object

Redis String object

1. Structure of string object

The following figure shows the structure of the string object , The first is a redisObject Header , The header specifies the object type and the code used by the object ,ptr The pointer points to a sdshdr Header ,sdshdr The structure of the buf The array holds the actual string .

2. String object encoding

2.1 Coding rules

We said earlier ,Redis An object in has the implementation of many underlying data structures . and String There are three types of object encoding , See the table below ：

encoding	ptr
OBJ_ENCODING_INT	String object implemented by integer value
OBJ_ENCODING_EMBSTR	embstr Encoded simple dynamic string implementation of string object
OBJ_ENCODING_RAW	String object implemented by simple dynamic string

The rules for using various codes are as follows ：

• The value saved by the string is an integer , And the integer can be used long Type said , Use OBJ_ENCODING_INT code .
• The object saved by string is a string value , And the length of the string is less than 44 byte , Use OBJ_ENCODING_EMBSTR code . （redis Use jemalloc Memory allocator , And jemalloc Will be allocated 8,16,32,64 Equal byte memory , One embstr The fixed size is 16+3+1 = 20 Bytes , So one of the biggest embstr String is 64-20 = 44 byte .）
• The object saved by string is a string value , And the string is greater than 44 byte , Use OBJ_ENCODING_RAW code .

2.2 Encoding conversion

int and embstr The encoded string object meets certain conditions , Will be converted to raw Encoded string object .

• Yes int and embstr String objects use APPEND command , The object becomes raw code .
• int Encoded integer string exceeds long The range that can be expressed , perhaps embstr The encoded string exceeds 44 byte , Will become raw code .

It should be noted that ,embstr Encoding is an optimized way to save short strings , This kind of coding and raw The coding is the same , but raw The code calls the memory allocation function twice to create redisObject The structure and sdshdr structure , and embstr Encoding allocates a continuous space by calling a memory allocation function , This space directly contains the above two parts , As shown in the figure below ：

Use embstr Encoded string objects to save short strings have the following benefits ：

• embstr Encoding will create a string object from the number of memory allocations required by raw Two times of coding is reduced to one time .
• Release embstr The encoded string object only needs to call the memory release function once , And release raw The encoded string object needs to call the memory release function twice .
• because embstr All data of the encoded string object is stored in a continuous memory , So this kind of encoded string object is better than raw Encoded string objects take advantage of caching .

secondly ,Redis Not for embstr Write any corresponding modification program for the encoded string , therefore embstr The encoded string is actually readable , Any operation to modify it , Will turn it into raw code .

3. Introduction to string object commands

command	describe
SET key value	Set the specified key Value
GET key	Get specified key Value
GETRANGE key start end	return key The child character of the string value in
GETSET key value	Will be given key The value of the set value , And back to key The old value （old value）
GETBIT key offset	Yes key String value stored , Gets the bit on the specified offset （bit）
MGET key1 [key2…]	Get all （ One or more ） Given key Value
SETBIT key offset value	Yes key String value stored , Sets or clears the bit on the specified offset （bit）
SETEX key seconds value	Will value value Related to key , And will key The expiration time of is set to seconds （ In seconds ）
SETNX key value	Only in key Set when not present key Value
SETRANGE key offset value	use value Parameter override given key String value stored , From the offset offset Start
STRLEN key	return key The length of the stored string value
MSET key value [key value …]	Set one or more... At the same time key-value Yes
MSETNX key value [key value …]	Set one or more... At the same time key-value Yes , If and only if all given key It doesn't exist
PSETEX key milliseconds value	This command and SETEX Command similar , But it's set in milliseconds key Survival time , Not like it SETEX Order that , In seconds
INCR key	take key The value of the number stored in is increased by one
INCRBY key increment take key	The stored value plus the given increment value （increment）
INCRBYFLOAT key increment	take key The stored value plus the given floating-point delta value （increment）
DECR key	take key Subtract one from the number stored in
DECRBY key decrementkey	The stored value minus the given decrement value （decrement）
APPEND key value	If key Already exists and is a string , APPEND The order will value Append to key The end of the original value

4. Implementation of string object command

The implementation code of string object command is t_string.c In the source file .

4.1 SET command

#define OBJ_SET_NO_FLAGS 0
//  stay key Only when it does not exist 
#define OBJ_SET_NX (1<<0)
//  stay key Only when it exists 
#define OBJ_SET_XX (1<<1)
//  In seconds (s) Set the key for the unit key Expiration time 
#define OBJ_SET_EX (1<<2)
//  In milliseconds (ms) Set the key for the unit key Expiration time 
#define OBJ_SET_PX (1<<3)

// setGenericCommand()  The function is the following command : SET, SETEX, PSETEX, SETNX  The lowest level implementation of 
// flags  It can be NX or XX, Provided by the macro above 
// expire  Definition key The expiration time of , Format by unit Appoint 
// ok_reply and abort_reply Save the reply client The content of ,NX and XX Will also change the reply 
//  If ok_reply It's empty , Then use  "+OK"
//  If abort_reply It's empty , Then use  "$-1"
void setGenericCommand(client *c, int flags, robj *key, robj *val, robj *expire, int unit, robj *ok_reply, robj *abort_reply) {
    
	//  initialization , Avoid mistakes 
    long long milliseconds = 0;

    //  If you define key The expiration time of 
    if (expire) {
    
        //  from expire Object , Save in milliseconds in , If there is an error, send the default message to client
        if (getLongLongFromObjectOrReply(c, expire, &milliseconds, NULL) != C_OK)
            return;
        //  If the expiration time is less than or equal to 0, Then send an error message to client
        if (milliseconds <= 0) {
    
            addReplyErrorFormat(c,"invalid expire time in %s",c->cmd->name);
            return;
        }
        //  If unit In seconds , You need to convert it into milliseconds to save 
        if (unit == UNIT_SECONDS) milliseconds *= 1000;
    }

    // lookupKeyWrite Function is to extract for write operation key Value object of 
    //  If set NX( non-existent ), But in the database   Can find   The key
    //  Or set up XX( There is ), But in the database   Can't find   The key
    //  reply abort_reply to client
    if ((flags & OBJ_SET_NX && lookupKeyWrite(c->db,key) != NULL) ||
        (flags & OBJ_SET_XX && lookupKeyWrite(c->db,key) == NULL))
    {
    
        addReply(c, abort_reply ? abort_reply : shared.nullbulk);
        return;
    }
    // db.c Functions in the file , At present db Set the key to key The value of is val
    setKey(c->db,key,val);

    //  Set the database to dirty (dirty), The server modifies one at a time key after , Will be on the dirty key (dirty) increase 1
    server.dirty++;

    //  Set up key The expiration time of 
    // mstime() Returns Greenwich mean time in milliseconds 
    if (expire) setExpire(c->db,key,mstime()+milliseconds);

    //  send out "set" Notice of the incident , Used in publish subscribe mode , Notify the client to accept the event that occurred 
    notifyKeyspaceEvent(NOTIFY_STRING,"set",key,c->db->id);

    //  send out "expire" Event notification 
    if (expire) notifyKeyspaceEvent(NOTIFY_GENERIC,
        "expire",key,c->db->id);

    //  Set up the success , Send... To the client ok_reply
    addReply(c, ok_reply ? ok_reply : shared.ok);
}

4.2 GET command

// GET  The underlying implementation of the command 
int getGenericCommand(client *c) {
    
    robj *o;

    // lookupKeyReadOrReply The function is to return key Value object of , Find and return the object , Can't find the message that will be sent to client
    //  If key There is no direct , return 0 Express GET Command executed successfully 
    if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.nullbulk)) == NULL)
        return C_OK;

    //  If key The encoding type of the value of is not a string object 
    if (o->type != OBJ_STRING) {
    
        addReply(c,shared.wrongtypeerr);    // Return the wrong type of information to client, return -1 Express GET Command execution failed 
        return C_ERR;
    } else {
    
        addReplyBulk(c,o);  // Return the previously found object as a reply to client, return 0 Express GET Command executed successfully 
        return C_OK;
    }
}

4.3 DECR and INCR command

// DECR key  take  key  Subtract one from the number stored in 
// INCR key  take  key  The value of the number stored in is increased by one 
//INCR and DECR The underlying implementation of the command 
void incrDecrCommand(client *c, long long incr) {
    
    long long value, oldvalue;
    robj *o, *new;

    o = lookupKeyWrite(c->db,c->argv[1]);   // Get by writing key Of value object 

    //  eureka value Object but value Object is not of string type , Go straight back to 
    if (o != NULL && checkType(c,o,OBJ_STRING)) return;

    //  The string type of value Convert to long long The type is saved in value in 
    if (getLongLongFromObjectOrReply(c,o,&value,NULL) != C_OK) return;
    
	//  Back up old value
    oldvalue = value;

    //  If incr beyond long long The range that a type can represent , Send error message 
    if ((incr < 0 && oldvalue < 0 && incr < (LLONG_MIN-oldvalue)) ||
        (incr > 0 && oldvalue > 0 && incr > (LLONG_MAX-oldvalue))) {
    
        addReplyError(c,"increment or decrement would overflow");
        return;
    }
    value += incr;  // Calculate the new value value 

    // value Object is currently unshared , Encoded as integer type , And new value The value is not in the shared range , And value be in long Within the range represented by the type 
    if (o && o->refcount == 1 && o->encoding == OBJ_ENCODING_INT &&
        (value < 0 || value >= OBJ_SHARED_INTEGERS) &&
        value >= LONG_MIN && value <= LONG_MAX)
    {
    
        new = o;
        //  Set up vlaue The value of the object 
        o->ptr = (void*)((long)value);
    } else {
    
        //  When any of the above conditions are not met , Then create a new string object 
        new = createStringObjectFromLongLong(value);

        //  If the previous value The object is 
        if (o) {
    
        	//  use new Object to rewrite key Value 
            dbOverwrite(c->db,c->argv[1],new);
        } else {
    
        	//  If the previous value non-existent , take key and new Make up a new key-value Yes 
            dbAdd(c->db,c->argv[1],new);
        }
    }
    //  When the key of the database is changed , This function will be called to send signals 
    signalModifiedKey(c->db,c->argv[1]);
    //  send out "incrby" Event notification 
    notifyKeyspaceEvent(NOTIFY_STRING,"incrby",c->argv[1],c->db->id);
    //  Set dirty key 
    server.dirty++;

    //  Reply to client
    addReply(c,shared.colon);
    addReply(c,new);
    addReply(c,shared.crlf);
}

4.4 APPEND command

// APPEND key value  Append string 
// APPEND Implementation of commands 
void appendCommand(client *c) {
    
    size_t totlen;
    robj *o, *append;

	//  Get by writing key Of value object 
    o = lookupKeyWrite(c->db,c->argv[1]);

    //  If not vlaue, Then create a 
    if (o == NULL) {
    
		//  For parameters value Optimized coding 
        c->argv[2] = tryObjectEncoding(c->argv[2]);
        //  take key and value Make up a new key-value Yes 
        dbAdd(c->db,c->argv[1],c->argv[2]); 
        //  increase value Reference count of 
        incrRefCount(c->argv[2]);
        //  return vlaue The length of 
        totlen = stringObjectLen(c->argv[2]);
    } else {
        
		//  Get value
		//  If value Objects that are not string types return directly 
        if (checkType(c,o,OBJ_STRING))
            return;

        /* "append" is an argument, so always an sds */
        //  Get the appended value object 
        append = c->argv[2];
        //  Calculate the added length 
        totlen = stringObjectLen(o)+sdslen(append->ptr);
        //  If the appended length exceeds the range , Then return to 
        if (checkStringLength(c,totlen) != C_OK)
            return;

        //  Because according to value modify key Value , So if key The original value is shared , Need to unshare , Create a new value object and key Pairing 
        o = dbUnshareStringValue(c->db,c->argv[1],o);
        //  take vlaue The value of the object is appended with append Value 
        o->ptr = sdscatlen(o->ptr,append->ptr,sdslen(append->ptr));
        //  Calculate the length of the appended value 
        totlen = sdslen(o->ptr);
    }
    //  When the key of the database is changed , This function will be called to send signals 
    signalModifiedKey(c->db,c->argv[1]);
    //  send out "append" Event notification 
    notifyKeyspaceEvent(NOTIFY_STRING,"append",c->argv[1],c->db->id);
    //  Set dirty key 
    server.dirty++;
    //  After sending the append value What's your length client
    addReplyLongLong(c,totlen);
}

Reference material ：

《Redis Design and implementation 》

Redis Source code analysis and comments