Redis underlying data structure analysis

As of now (2020-11-19), Redis has the following upper-layer data types:

  • Strings
  • Lists
  • Hashes
  • Sets
  • Sorted Sets
  • Bitmaps
  • HyperLogLogs
  • Streams
  • Geo

The top five are the most commonly used data structures, and each may be implemented by a variety of lower-level data structures.

Redis Strings

The value of a string cannot exceed the size of proto-max-bulk-len. The default value is 512M(512ll*1024*1024).

Redis strings are encoded in three formats:

  • OBJ_ENCODING_INT
  • OBJ_ENCODING_RAW
  • OBJ_ENCODING_EMBSTR

The latter two are both underlying structures called SDSHDRX definitions (x is the number of bytes), which are:

  • Sdshdr5 is a special one
  • sdshdr8
  • sdshdr16
  • sdshdr32
  • sdshdr64
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

For characters less than 32 bits long, use sdshdr5, flags lower memory type, higher memory size. Sdshdr5 is converted to sdshdr8 when null characters are created.

Take a look at the tryObjectEncoding method in Object. c

OBJ_ENCODING_INT

Let’s take a look at this code:

if (len <= 20 && string2l(s,len,&value)) {
    /* This object is encodable as a long. Try to use a shared object. * Note that we avoid using shared integers when maxmemory is used * because every object needs to have a private LRU field for the LRU * algorithm to work well. */
    if ((server.maxmemory == 0| |! (server.maxmemory_policy & MAXMEMORY_FLAG_NO_SHARED_INTEGERS)) && value >=0 &&
        value < OBJ_SHARED_INTEGERS) / / 10000
    {
        decrRefCount(o);
        incrRefCount(shared.integers[value]);
        return shared.integers[value];
    } else {
        if (o->encoding == OBJ_ENCODING_RAW) {
            sdsfree(o->ptr);
            o->encoding = OBJ_ENCODING_INT;
            o->ptr = (void*) value;
            return o;
        } else if (o->encoding == OBJ_ENCODING_EMBSTR) {
            decrRefCount(o);
            return createStringObjectFromLongLongForValue(value); }}}Copy the code

For numbers greater than 0 and less than 10000:

set str 9999
Copy the code

Redis pre-creates 10,000 RedisObjects between 0 and 99999 at startup, so if you set the value in this range, Redis doesn’t need to create any extra memory, just increment the reference by one.

For other integers, a redisObj is created, and a Redis object encoded as int is returned.

OBJ_ENCODING_EMBSTR

Redis encodes strings with embSTR when the string length is less than or equal to 44 bytes. In this case, the generated redisObj and SDSHDR are contiguous memory.

OBJ_ENCODING_RAW

In other cases, raw encoding is used. Note that memory is requested twice because SDSHDR and redisObj are not in contiguousmemory.

Redis Lists

The underlying data structure of the list is encoded in OBJ_ENCODING_QUICKLIST.

Quicklist is a data structure introduced in Redis3.2 that combines a List with Ziplist.

A doubly linked list of ziplists

The first comment in QuickList.c explains exactly what a QuickList is, as the name suggests: A QuickList is a bidirectional linked list, and each node in the list is a Ziplist structure.

Quicklist can be thought of as a data structure consisting of several small Ziplists linked together in a bidirectional list. When there are too many Ziplist nodes, the QuickList degrades to a bidirectional linked list. At one extreme, each Ziplist node contains only one entry, that is, only one element. When the number of Ziplist elements is too small, the Quicklist can degenerate into a Ziplist. An extreme case is that the Quicklist has only one Ziplist node.

Redis Hashes

The underlying hashtable data structure is either ziplist or ht.

If all key-values to be stored meet the following two conditions, use ziplist as the underlying storage. Otherwise, use HashTable storage. Note that the storage sequence of ziplist is the same as that of write to Hashtable.

  1. The string length of all key-value pairs in the key-value structure is smaller than hash-max-ziplist-value. The default value is 64, which can be changed in the configuration file
  2. Hash objects can hold fewer key-value pairs (one key-value pair is one) than hash-max-ziplist-entries. The default value is 512, which can be changed through the configuration file

When a data structure is converted from ziplist to a hash table, it will not be converted back if ziplist conditions are later met.

Redis Sets

Unordered set, unique set member.

The underlying set is based on either HT or INSET data structures.

An integer set (inset) is an ordered structure that stores integer data.

When the number of sets exceeds set-max-inset-entries(512 by default), the set converts the encoding to hashTable, even if you continue to put integer elements into the set.

Redis Sorted Sets

The underlying data structure of Zset is ziplist or Skiplist.

The redis configuration file has two configurations for ordered collections:

  • Zset-max-ziplist-entries 128: The maximum number of zset compressed list elements is 128
  • Zset-max-ziplist-value 64: The maximum length of an element cannot exceed 64 when zset uses a compressed list

In the zaddGenericCommand function of t_zset.c, if the element is added for the first time, the following two conditions are judged:

  • Zset-max-ziplist-entries Whether to equal 0
  • Whether the size of the inserted element is greater than zset-max-ziplist-value

if (zobj == NULL) {
    if (xx) goto reply_to_client; /* No key + XX option: nothing to do. */
    if (server.zset_max_ziplist_entries == 0 ||
        server.zset_max_ziplist_value < sdslen(c->argv[scoreidx+1]->ptr))
    {
        zobj = createZsetObject(a); }else {
        zobj = createZsetZiplistObject(a); }dbAdd(c->db,key,zobj);
}

Copy the code

If one of these is met, zset uses OBJ_ENCODING_SKIPLIST encoding, otherwise OBJ_ENCODING_ZIPLIST is used as the underlying data structure.

In general, zset-max-ziplist-entries are not configured to 0 and the string length of the elements is not too long, so the low-level implementation of compressed lists is used by default when creating ordered collections.

When zset inserts a new element, it determines the following two conditions:

  • Zset contains more than zset_max_ziplist_entries
  • The string length of the inserted element is greater than zset_MAX_ziplist_value

When any of these conditions are met, Redis changes the underlying implementation of ZSet from a compressed list to a skip list. The code is as follows:

if (zzlLength(zobj->ptr) > server.zset_max_ziplist_entries || sdslen(ele) > server.zset_max_ziplist_value)
    zsetConvert(zobj,OBJ_ENCODING_SKIPLIST);
Copy the code

After a zset is converted to a hop table, it does not revert to a compressed list, even if the elements are gradually removed.