How Redis Implements the String Type

The Redis String type is one of the most fundamental and frequently used data types. Before analyzing its implementation, let’s look at the core requirements of the String type:

  • Store string data, binary-safe
  • Dynamic resizing
  • Provide function interfaces for related String operations
  • Minimize memory usage as much as possible

We will analyze its implementation around these core requirements.

Binary safety: In C, \0 marks the end of a string. If the string itself contains a \0 character, the string would be truncated — that is, it is not binary-safe. Being binary-safe means being able to handle this special case.

Underlying Structure

The String object (OBJ_STRING) in Redis is implemented in three main ways at the bottom level:

  • SDS (Simple Dynamic String): Most strings are implemented with SDS, which supports binary safety, dynamic resizing, space pre-allocation, and similar features.
  • Integer encoding: If the string content can be represented as a long long integer, Redis stores it directly as an integer to save space and improve efficiency.
  • embstr encoding: Short strings (≤ 44 bytes) use embstr encoding, which allocates the redisObject and the SDS together in one contiguous block of memory, reducing memory fragmentation and the number of allocations.

Simple Dynamic String (SDS)

Let’s look at the underlying structure of SDS. The source defines several structures:

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; // length currently used
    uint8_t alloc; /* total allocated capacity (excluding header and null terminator) */
    unsigned char flags; /* lower 3 bits identify the type */
    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[];
};

SDS chooses a different struct based on the string length, in order to save memory.

static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5)
        return SDS_TYPE_5;
    if (string_size < 1<<8)
        return SDS_TYPE_8;
    if (string_size < 1<<16)
        return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
    if (string_size < 1ll<<32)
        return SDS_TYPE_32;
    return SDS_TYPE_64;
#else
    return SDS_TYPE_32;
#endif
}

Let’s look at the flow of creating an SDS object:

sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
    sds s;
    char type = sdsReqType(initlen);   // choose type based on string length

    int hdrlen = sdsHdrSize(type);   // compute header length
    unsigned char *fp; /* flags pointer. */
    size_t usable;
    // allocate memory
    void *sh = trymalloc?
        s_trymalloc_usable(hdrlen+initlen+1, &usable) :
        s_malloc_usable(hdrlen+initlen+1, &usable);
    if (sh == NULL) return NULL;
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    s = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)-1;
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    switch(type) {
        case SDS_TYPE_5: {
            // ...
        }
        case SDS_TYPE_8: {
            // ...
        }
        case SDS_TYPE_16: {
            // ...
        }
        case SDS_TYPE_32: {
            // ...
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;   // assign used length
            sh->alloc = usable;  // assign total allocated capacity
            *fp = type;
            break;
        }
    }
    if (initlen && init)
        memcpy(s, init, initlen);  // copy initial value
    s[initlen] = '\0';
    return s;
}

So how is appending one SDS object to another implemented?

sds sdscatsds(sds s, const sds t) {
    return sdscatlen(s, t, sdslen(t));
}

sds sdscatlen(sds s, const void *t, size_t len) {
    size_t curlen = sdslen(s);

    s = sdsMakeRoomFor(s,len);  // ensure there is enough space
    if (s == NULL) return NULL;
    memcpy(s+curlen, t, len);
    sdssetlen(s, curlen+len);
    s[curlen+len] = '\0';
    return s;
}

The sdsMakeRoomFor function ensures the SDS object has enough usable space; if not, it grows the buffer via realloc.

embstr Encoding

embstr encoding is a way to store short strings. It allocates the redisObject and the SDS together in one contiguous block of memory | redisObject | sdshdr | string content |, avoiding memory fragmentation and extra allocations.

When creating a string object, if the string length is ≤ 44 bytes, embstr encoding is used.

#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44
robj *createStringObject(const char *ptr, size_t len) {
    if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT)
        return createEmbeddedStringObject(ptr,len);
    else
        return createRawStringObject(ptr,len);
}

robj *createEmbeddedStringObject(const char *ptr, size_t len) {
    // allocate memory: redisObject, sdshdr8 and the string storage space together
    robj *o = zmalloc(sizeof(robj)+sizeof(struct sdshdr8)+len+1);   
    struct sdshdr8 *sh = (void*)(o+1);

    o->type = OBJ_STRING;
    o->encoding = OBJ_ENCODING_EMBSTR;
    o->ptr = sh+1;
    o->refcount = 1;
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
    } else {
        o->lru = LRU_CLOCK();
    }

    sh->len = len;
    sh->alloc = len;
    sh->flags = SDS_TYPE_8;
    if (ptr == SDS_NOINIT)
        sh->buf[len] = '\0';
    else if (ptr) {
        memcpy(sh->buf,ptr,len);
        sh->buf[len] = '\0';
    } else {
        memset(sh->buf,0,len+1);
    }
    return o;
}

Memory Management and Optimization

Memory is a precious resource in any database, especially so for an in-memory database. Redis has many memory-optimization designs, and the String type is no exception:

  • Space pre-allocation: SDS reserves extra space for the string, reducing frequent realloc calls.
  • Lazy space freeing: SDS supports lazy reclamation of space, avoiding frequent memory shrinking.
  • Object sharing: For commonly used small integers, Redis uses an object sharing pool to reduce allocations.

Transactions and Event Notifications

Every time a string is modified (e.g. set, append, incr), Redis calls signalModifiedKey and notifyKeyspaceEvent — the former serves the transactional WATCH mechanism, and the latter serves the keyspace event notification mechanism.

Typical Code Flow

Let’s take the SET command as an example.

void setCommand(client *c) {
    robj *expire = NULL;
    int unit = UNIT_SECONDS;
    int flags = OBJ_NO_FLAGS;

    // parse extended command arguments such as NX, EX, etc.
    if (parseExtendedStringArgumentsOrReply(c,&flags,&unit,&expire,COMMAND_SET) != C_OK) {
        return;
    }

    // choose the appropriate encoding based on string length and content
    c->argv[2] = tryObjectEncoding(c->argv[2]); 
    
    // perform the write
    setGenericCommand(c,flags,c->argv[1],c->argv[2],expire,unit,NULL,NULL);
}

Eventually setGenericCommand calls genericSetKey to complete the write operation.

void genericSetKey(client *c, redisDb *db, robj *key, robj *val, int keepttl, int signal) {
    if (lookupKeyWrite(db,key) == NULL) {  // does the key exist?
        dbAdd(db,key,val);   // add the key-value pair
    } else {
        dbOverwrite(db,key,val);  // overwrite the key-value pair
    }
    incrRefCount(val);   // increment the reference count
    if (!keepttl) removeExpire(db,key);   // remove the expiration time
    if (signal) signalModifiedKey(c,db,key);   // whether to notify that the key was modified
}

The String type is implemented on top of the dict dictionary at the bottom level; both its key and value are robj objects, and the value object stores the string content. Since we analyzed the implementation of the Hash type earlier, the specific implementations of other String commands will not be repeated here.