Redis basic data structures and data types

An overview of the

• Redis as a distributed cache implementation, compared with Memecache, in addition to supporting persistence, an important feature of Redis is that Redis supports rich data types, that is, Memecache only supports string types, all key-value pairs are string types, while Redis values support strings, lists, dictionaries, collections, There are five types of ordered collections, so they can provide richer operations.
• Each data type of Redis supports multiple underlying data structure implementations, that is, each data type is not bound to a single data structure, but can be multiple. The reason for this design is that Redis is an in-memory database, and all data is stored in memory. Therefore, in the design process, it is necessary to reduce memory consumption as much as possible on the premise of ensuring performance, and balance between memory and performance, so as to store more data. So before we get into data types, let’s take a look at the underlying data structures of Redis.

The data structure

Simple dynamic string

• Redis is written in C language, Redis does not directly use the string of C language, but based on the string of C language to achieve a simple dynamic string. The main reason is that the string of C is a low-level API, which has the following problems :(1) there is no record of the string length, so it requires O(n) complexity to obtain the string length; (2) Because the string length is not recorded, it is prone to buffer overflow; (3) System call is needed every time to expand the string capacity, there is no reserved space (4) C string can only save characters.

• Based on the above problems, the simple dynamic string of Redis provides :(1) the length of string is recorded by len to achieve O(1) complexity; (2) The internal string array is reserved to reduce the number of memory reallocation of strings, and at the same time to achieve automatic expansion to avoid buffer overflow problem; (3) The internal character array is byte based to store data, so it can save characters and binary data. Specific data structure design is as follows:

  Struct __attribute__ ((__packed__)) sdshdr64 {// /* uint64_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 LSB of type, 5 unused bits */ // char buf[]; };Copy the code

Two-way linked list

• C language does not provide the implementation of bidirectional linked list, so Redis itself implements a bidirectional linked list, which is mainly used to store list data. The specific data structure is as follows:

• List node definitions:

  Typedef struct listNode {// struct listNode *prev; Struct listNode *next; Void *value; void *value; void *value; } listNode;Copy the code

• Linked list definitions:

  Typedef struct list {// listNode *head; // listNode *tail; void *(*dup)(void *ptr); void (*free)(void *ptr); int (*match)(void *ptr, void *key); // List length unsigned long len; } list;Copy the code

Chain hash dictionary

• The hash table of Redis is implemented as a chained hash, that is, the conflicting nodes are maintained by a linked list. The specific data structure is as follows:

• Hash list nodes:

  // typef struct dictEntry {// key key void *key; Union {// value value void *val; uint64_t u64; int64_t s64; double d; } v; Struct dictEntry *next; } dictEntry;Copy the code

• Chained hash table implementation:

  // typepedef struct dictht {// dictEntry **table; // Number of hash elements unsigned long size; // Hash mask, used to calculate hash indexes based on ampersand, always siz-1 unsigned long sizemask; unsigned long used; } dictht;Copy the code

• Redis hash structure:

  typedef struct dict { dictType *type; void *privdata; // Two hash tables, one of which is empty and uses dictht ht[2] for rehash; long rehashidx; /* rehashing not in progress if rehashidx == -1 */ unsigned long iterators; /* number of iterators currently running */ } dict;Copy the code

Ziplist ziplist

• Compressed lists are designed to save memory and are sequential data structures composed of contiguous chunks of specially encoded memory.

• Compressed lists are used when the list has few elements and the element types are small integers or short strings. Because the data access of the compressed list is generally traversal, that is, linear O(n) time complexity, but with fewer elements, there is no performance problem, similar to the constant O(1) time complexity.

• The overall structure of the compressed list is as follows: it mainly includes the total number of bytes of the list zlbytes, the number of bytes between the end node of the list and the start address of the list zLTail, the total number of elements of the list zllen, and the list element data node entry (the picture is taken from The Design and Implementation of Redis by Huang Jianhong).

• Element nodes of the element list: each node contains the size of the previous node, so that the position of the previous node can be calculated based on the position of the current element to achieve traversal; Encoding Indicates the data type and length of the value stored by content, which is the specific value.

  /* We use this function to receive information about a ziplist entry.
   * Note that this is not how the data is actually encoded, is just what we
   * get filled by a function in order to operate more easily. */
  typedef struct zlentry {
      unsigned int prevrawlensize; /* Bytes used to encode the previos entry len*/
      unsigned int prevrawlen;     /* Previous entry len. */
      unsigned int lensize;        /* Bytes used to encode this entry type/len.
                                      For example strings have a 1, 2 or 5 bytes
                                      header. Integers always use a single byte.*/
      unsigned int len;            /* Bytes used to represent the actual entry.
                                      For strings this is just the string length
                                      while for integers it is 1, 2, 3, 4, 8 or
                                      0 (for 4 bit immediate) depending on the
                                      number range. */
      unsigned int headersize;     /* prevrawlensize + lensize. */
      unsigned char encoding;      /* Set to ZIP_STR_* or ZIP_INT_* depending on
                                      the entry encoding. However for 4 bits
                                      immediate integers this can assume a range
                                      of values and must be range-checked. */
      unsigned char *p;            /* Pointer to the very start of the entry, that
                                      is, this points to prev-entry-len field. */
  } zlentry;
  Copy the code

Integer set intset

• A set of integers is a data structure of a set. This data structure is used when there are only integer elements in the set and the number of elements in the set is small.

• The specific data structure is defined as follows:

  typedef struct intset { uint32_t encoding; uint32_t length; Int int8_t contents[]; } intset;Copy the code

Jump table skiplist

String string

• In Redis, the corresponding integer type is stored as long if it does not exceed the range of LONG in C language. If it does, embstr or RAW string is used to store it. The corresponding strings and floating point numbers are stored using embstr or RAW strings.
• Int: An integer that can be held using type long.
• Embstr: If the number of bytes in a string is less than or equal to 32, embstr is used to encode the string. Note that integers cannot be stored using the long type. Floating point numbers are stored using strings in Redis.
• Raw: The string that embstr cannot store, that is, the string with more than 32 bytes, is encoded using RAW.
• Embstr, like raw encoding, is used to store strings. Embstr is an optimization of RAW for storing short characters. Embstr is mainly used to store short strings. In terms of memory allocation, emBSTR uses a memory allocation to create redisObject, the corresponding object of data type String in Redis, and SDS, a simple dynamic string used to store data, while RAW needs to allocate large SDS. Therefore, two memory allocations are used to create the above two objects respectively.

List the list

The dictionary hash

• The dictionary is mainly used to store key-value pair data, and there are two data structures of compressed list and chained hash table in the underlying coding.
• Selection rule: If the string length of the key and value of the hash object is less than 64 bytes and the number of all hash objects is less than 512, use the compressed list, otherwise use the chained hash table.
• This is the default rule and can be changed using the hash-max-ziplist-value and hash-max-ziplist-entries parameters in redis.conf.

Set the set

Ordered set Zset

• The ordered set mainly realizes the function of sorting by score, in which score can be repeated, but member object member cannot be repeated, that is, the ordered set is oriented to score score, and the set is oriented to member object member.
• There are also two data structures, compressed list and skip list, in the underlying coding.
• Selection rule: If the ordered set has less than 128 elements and each element’s member object is less than 64 bytes long, use the compressed list, otherwise use the skip list.
• The preceding rules can be modified by using zset-max-ziplist-entires and zset-max-ziplist-value in redis.conf.

The statement

Ps: I mixed a child programmer, if there is an error in the article please inform us, in addition, this article is only used for learning, refer to the following article, if offended please inform me to delete: Redis data type and data structure analysis