Five basic data types

Redis supports five basic data types: String, Hash, List, Set, and Zset/Sorted Set

First, the reader needs to understand that Redis data types are divided by Value, and keys are all strings by default. Therefore, the following articles are all about the Value in the Redis Key Value pair.

  • String: The most basic type of Redis, similar to String in high-level programming languages.

    Redis 127.0.0.1:6379 > SET the key"Ha ha ha."
OK
redis 127.0.0.1:6379> GET key
"Ha ha ha."
Copy the code

  • Hash: A set of key-value pairs. Similar to Java HashMap, each Key corresponds to a Value in a Map. Hash is especially suitable for storing objects

    Redis 127.0.0.1:6379> DEL key redis 127.0.0.1:6379> HMSET key field1"Hello" field2 "World"
"OK"Redis 127.0.0.1:6379> HGET key field1"Hello"Redis 127.0.0.1:6379> HGET key field2"World"
Copy the code

  • The List: A simple List of strings, that is, each element in the List is a String (String is not a String, objects can be serialized into strings, such as JSON serialization, Redis native serialization), Similar to Java LinkedList and sorted by insertion order, you can add an element to the top or bottom of the list

    Redis 127.0.0.1:6379> DEL runoob redis 127.0.0.1:6379> lpush runoob redis (integer1 redis 127.0.0.1:6379> lpush runoob mongodb (integer) 2
redis 127.0.0.1:6379> lpush runoob rabbitmq
(integer) 3
redis 127.0.0.1:6379> lrange runoob 0 10
1) "rabbitmq"
2) "mongodb"
3) "redis"
Copy the code

  • Set: Redis Set is an unordered Set of String type, similar to Java HashSet, that is, every element in the Set is also of String type, which is characterized by O(1) complexity of adding, deleting and searching.

    Redis 127.0.0.1:6379> DEL runoob redis 127.0.0.1:6379> sadd runoob redis (integer1 redis 127.0.0.1:6379> sadd runoob mongodb (integer) 1
redis 127.0.0.1:6379> sadd runoob rabbitmq
(integer) 1
redis 127.0.0.1:6379> sadd runoob rabbitmq
(integer) 0
redis 127.0.0.1:6379> smembers runoob

1) "redis"
2) "rabbitmq"
3) "mongodb"
Copy the code

  • ZSet: An ordered set is similar to TreeMap in Java, but the bottom layer is not implemented with a red-black tree. It is sorted by score and supports range queries. Socre is a double, and member is a String. However, it is usually used to store data such as ID in production. If the whole object is stored, BigKey problem may occur.

    • Adds elements to an ordered collection
    zadd key score member 
Copy the code

    • Different from TreeMap, ZSet can not only use Score to find the corresponding member, but also use member to find the corresponding value

    • Redis 127.0.0.1:6379> DEL runoob redis 127.0.0.1:6379> Zadd runoob 0 redis (integer1 redis 127.0.0.1:6379> zadd runoob 0 mongodb (integer) 1
redis 127.0.0.1:6379> zadd runoob 0 rabbitmq
(integer) 1
redis 127.0.0.1:6379> zadd runoob 0 rabbitmq
(integer) 0 redis 127.0.0.1:6379> ZRANGEBYSCORE runoob 0 1000 1"mongodb"
2) "rabbitmq"
3) "redis"
Copy the code

Composition of Redis objects

Now that Redis has these data types, how does Redis manage these data types for internal use?

Redis is C, so there must be a struct to manage these data types. Every object in Redis is represented by a redisObject structure (which is why the basic data types are called objects in this article). The properties of this structure hold information about the object. Only three important properties are described here: the Type attribute, the Encoding attribute, and the PTR attribute

typedef struct redisObject {
    / / type
    unsigned type:4;
    / / code
    unsigned encoding:4;
    // A pointer to the underlying implementation data structure
    void *ptr;
}
Copy the code

  • Type: Represents the basic data type of the object from which Redis can be used to determine which basic data type the object is

  • Encoding: The encoding property records the underlying encoding used by the object, that is, what data structure is used as the underlying implementation of the object. The value of this property can be one of the constants listed in the following table

    Code constants The underlying data structure corresponding to the encoding
    REDIS_ENCODING_INT longInteger of type
    REDIS_ENCODING_EMBSTR embstrEncoding a simple dynamic string
    REDIS_ENCODING_RAW Simple dynamic string
    REDIS_ENCODING_HT The dictionary
    REDIS_ENCODING_LINKEDLIST Double side chain table
    REDIS_ENCODING_ZIPLIST List of compression
    REDIS_ENCODING_INTSET The integer set
    REDIS_ENCODING_SKIPLIST Skip lists and dictionaries

    Possible encodings for each type

    type coding object
    REDIS_STRING REDIS_ENCODING_INT A string object implemented with an integer value.
    REDIS_STRING REDIS_ENCODING_EMBSTR useembstrA string object that encodes a simple dynamic string implementation.
    REDIS_STRING REDIS_ENCODING_RAW A string object implemented using a simple dynamic string.
    REDIS_LIST REDIS_ENCODING_ZIPLIST A list object implemented using a compressed list.
    REDIS_LIST REDIS_ENCODING_LINKEDLIST A list object implemented using a double-ended linked list.
    REDIS_HASH REDIS_ENCODING_ZIPLIST A hash object implemented using a compressed list.
    REDIS_HASH REDIS_ENCODING_HT Hash objects implemented using dictionaries.
    REDIS_SET REDIS_ENCODING_INTSET A collection object implemented using a collection of integers.
    REDIS_SET REDIS_ENCODING_HT A collection object implemented using a dictionary.
    REDIS_ZSET REDIS_ENCODING_ZIPLIST An ordered collection object implemented using a compressed list.
    REDIS_ZSET REDIS_ENCODING_SKIPLIST An ordered collection object implemented using skip lists and dictionaries.

    I will briefly explain the data structures mentioned in the above table below.

Meaning: Redis by encoding attribute to set object used by the code, rather than a fixed object associated for specific types of codes, greatly improved the flexibility and efficiency of Redis, because Redis can according to different usage scenarios to set different coding for an object, so as to optimize the efficiency of the object in a particular scenario.

The implementation of the various data types is described below.

String object

The encoding of a string object can be int, RAW, or embstr. A brief introduction to string objects

SDS

SDS: Simple Dynamic String, Redis is a unique String object, so why Redis does not directly use C language strings?

The reason is that the simple string representation in C language does not meet the requirements of Redis in terms of security, efficiency and function. Redis SDS has some special attributes and strategies, which make SDS more in line with Redis’s pursuit of extreme response speed, operational security and functional requirements than C language native strings.

Let’s look at the definition of String

struct sdshdr {
    // Records the number of bytes used in the BUF array
    int len;
    
    // Records the number of unused bytes in the BUF array
   	int free;
    
    // An array of bytes to hold strings
    char buf [];
}
Copy the code

C string and SDS

  • C String length needs to be traversed; SDS has a len attribute, which can be obtained directly with time complexity reduced from O(N) to O(1).

  • C string can not prevent buffer overflow problem, programmers need to manually determine the memory; The SDS STRING API will automatically determine whether the available space of the string is sufficient for the corresponding operation. If not, Redis will expand the SDS space before performing the corresponding operation, such as concatenating operation.

  • The C string must be changed once, while the SDS string will not be changed, which reduces the number of memory reallocation, mainly due to the following two strategies

    • Space pre-allocation: When SDS needs to expand, in addition to allocating the necessary space for modification, it will also allocate the unused space of the same size as the string, and record it with the free attribute of SDS string
    • Lazy space release: When SDS needs to be shortened, it is not necessary to actually reclaim the free space, but to record it using the free property for future use

  • C strings can only hold text data; SDS can hold arbitrary binary data because its underlying layer is an array of bytes.

Commonality between C strings and SDS

  1. Also null-terminated, so SDS strings can also use some of the C string library functions.

The difference between different codes

Int coding

When the string object value is an integer and the integer value can be represented as long, Redis directly uses the integer value to hold a string object.

Embstr and raw

The data structures corresponding to these two encodings are SDS strings, but they are stored differently in memory.

The RAW encoding calls the memory allocation function twice to create the redisObject structure and the SDS structure, respectively

Embstr encodings only call the memory allocation function once to allocate a contiguous space containing redisObject and SDSHDR

Advantages of EMBSTR encoding:

  • Reduces the number of memory allocations required to create string objects from two to one
  • To free memory, you only need to call the sequentially free memory function
  • Because data is continuous, the advantages brought by cache can be better utilized according to the principle of spatial continuity

Disadvantages of embSTR encoding:

  • Because the address space is contiguous, the encoded string is read-only and becomes raw if it is modified
  • Because of the need for contiguous space, it is only suitable for small strings
How does Redis choose encoding

  • Integer types are encoded using int

  • The length of the string is less than or equal to 39 bytes

  • The character string contains more than 39 bytes and is encoded in raw

A list of objects

List objects can be encoded as ziplist or LinkedList

Linkedlist coding

If it is linkedlist encoding, it is actually very similar to the underlying implementation of linkedlist in Java, which uses bidirectional linkedlist as the underlying implementation. Each bidirectional linkedlist node holds a string object with pre and next Pointers.

Ziplist coding

If it’s ziplist code, then the underlying data structure will be ziplist compressed list data structure, and I’ll talk about compressed list very briefly.

List of compression

Compressed lists, developed by Redis to save memory, do not require Pointers to nodes’ addresses, but instead use sequential data structures composed of contiguous chunks of memory. A compressed list can contain any number of nodes, and each node can hold either a byte array or an integer value.

The reader must be wondering why a compressed list can be used instead of a bidirectional list to implement list objects.

It is mainly related to the following three points:

  1. Memory for
  2. Unique composition of compressed lists
  3. Compressing list node composition

Here are the details

Memory for

This is the component of the compressed list in memory, and each part uses A contiguous memory space. Since the memory is contiguous, if you know the length of A segment, you can directly skip this segment and access the next segment, for example, A -> B. If you know that the length of A is 300 and the start address of A is P, So B’s starting address is P plus 300.

Compressing list composition

  • Zlend: Special value to mark the end of the compressed list
  • Zlbytes: Records the number of bytes of memory used for the entire compressed list, which can be used to access Zlend directly
  • Zltail: Records the number of bytes between the end of the compressed list and the start of the compressed list. It can be used to access the end of the table
  • Zllen: Records the number of nodes in the compressed list, which simplifies the operation time complexity of obtaining the number of lists to O(1). It is a typical space-for-time strategy
  • Entry: Indicates each node in the compressed list

With these attribute values, we can complete many list operations with O(1) time complexity, such as obtaining the number of nodes, using zllen; For example, to access the end of the table, use the start address + zltail attribute. At this point, we have completed the same operation as the bidirectional linked list to obtain the head and tail of the table, the operation of obtaining the number of nodes, so how to do the node traversal? Depends on the composition of the compressed list nodes.

Compressing list node composition

The compressed list node is divided into three parts:

  • Previous_entry_length: The length of the previous node. From the start address of the current node – the length of the previous node, you can access the start address of the previous node, similar to the pre pointer of a bidirectional linked list
  • Encoding: Records the type and length of the data stored in the node. Given the length of the current node, it is natural to access the next node in the same way as the previous node
  • Content: Holds the value of the node, which can be of types such as byte arrays and integers. The length is held by the encoding value

At this point, we can traverse the list before and after using the previous_entry_length and encoding attributes of the node, and basically achieve the same functionality as a bidirectional list.

The hash object

Hashtable encoding can be ziplist or hashtable

Ziplist coding

Instead of introducing ziplist as a data structure, let’s focus on how to implement a hash object using Ziplist

When a hash object is ziplist encoded, the two nodes that hold the same key-value pair are always next to each other, the node that holds the key comes first and the node that holds the value comes last.

In other words, when I want to get the value of a key, I just need two nodes and two nodes to go through the compressed list, and I can go through all the keys, and when I find the value.

Hashtable coding

Hash objects encoded using HashTable use the Redis dictionary as the underlying implementation

The dictionary

Let’s first look at the Hash table defined in Redis

typedef struct dictht {
    // Hash table array
    dictEntry ** table;
    
    // Hash table size
    unsigned long size;
    
    // Hash table mask, equal to size-1, used to calculate the index
    unsigned long sizemask;
    
    // Number of existing nodes
    unsigned long used;
}
Copy the code

From the structure of the Hash table, we can see that the implementation of the Java HashMap is very similar.

  1. Hash table with array + linked list
  2. The zip method resolves Hash conflicts, but does not treify
  3. The subscript of the key in the array is also obtained using the node hash value & sizemask (size-1)

Take a look at the data structure of the Redis dictionary

typedef struct dict {
    // Type specific functions
    dictType *type;
    // Private data
    void *private;
    // Hash table array
    dictht ht[2];
    
    // Rehash index, which indicates the rehash progress. A value of -1 indicates that rehash has not been started
    int trehashidx;
}
Copy the code

The Redis dictionary mainly contains an array of hash tables of size 2, and the Rehash index, which is a key difference from the Java HashMap, namely the different rehash mechanism.

Rehash

As is known to all, the Rehash of traditional Hash algorithms has been notorious. Since subscripts are obtained by mod operation, all nodes will be Rehash once the capacity is expanded. Such a large calculation will make the Hash table completely unavailable for a period of time, which is no less than a devastating blow to single-threaded Redis. So Redis uses progressive Rehash optimization.

Process:

  1. Each Rehash only rehashes part of the old data. The starting position of the next Rehash is determined by the Rehash index
  2. Each node rehashes from the first table to the second table
  3. When Rehash is not complete, Redis will operate on the two hash tables for the dictionary. Delete, modify, and find operations will be performed on the first table, while additions will be directly added to the second table
  4. When the Rehash is complete, replace the first hash table with a second hash table, and then empty the pointer to the second table for the next expansion

Conclusion:

  1. The two hash tables ensure that the dictionary is still available to the outside world during progressive Rehash
  2. The rehash index stores the position of the rehash to find the node the next time the rehash is performed

A collection of objects

The encoding of a collection object can be either intSet or Hashtable. Intset is a collection of integers. If the objects in a collection are all integers, then intset can be used as the underlying implementation. Collection objects are then implemented in a similar way to Java’s HashSet implementation.

Ordered set object

Ordered collections can be implemented using Ziplist or Skiplist

Ziplist implementation

Similar to the Hash object implementation, a collection element is stored through two Ziplist nodes, the first node holds member, and the second node holds score. When traversing, it is also a hop between two nodes to find the next set element.

In order to achieve the function of zset ordering, the set elements in Ziplist are sorted according to the smallest score value, and the inserted nodes are also guaranteed to be in the position of the corresponding score value during insertion.

Skiplist implementation

For skiplist coding, the obvious implementation is skip lists. In addition to skip lists, dictionaries are used. That is, the bottom layer is implemented using skip lists + dictionaries.

Why use a dictionary?

If we use the skip list, the skip list is sorted according to score, and its search logic is also searched by score, that is to say, we can find the corresponding member according to the corresponding score through the skip list. However, if the corresponding score is searched by member, we cannot use the skip list to search quickly, but can only use linear search, O(N) level traversal skip list. From the business level, such similar requirements are very common, such as obtaining the score of the current user in the leaderboard. So such an inefficient implementation is a disaster for Redis.

If we use the dictionary and use member as key and score as value, then we can quickly find the score corresponding to a member through the dictionary, which is a typical space-time strategy.

Note: Redis does not directly use score as a value, which would cause score to be stored repeatedly, so Redis only allows the dictionary value to hold the address of the skip list node.

skiplist

The implementation of skip list is more complex, the general idea is through some special implementation, so that the search algorithm can be similar to binary search on an ordered list, the search time complexity is O(logN) level. Skip table implementation is not covered here, but you can read these articles if you are interested.

A simple Java implementation of Redis Skip List

What are the reasons why Redis does not use red-black trees but instead uses hoptables to implement ordered collections

  • It is easy to implement range queries, which are common for data types like ZSet
  • Simple code implementation
  • It is more flexible and can balance execution efficiency and memory consumption by changing the index building strategy (random strategy)

summary

In addition to paying attention to Redis API calls, programmers should also understand some Redis low-level implementation, which can better help us deal with the complex business of Redis design, so that we can make reasonable and efficient use of cache, a high concurrency tool.

References:

  1. Redis Design and Implementation by Huang Jianhong
  2. Redis Development, Operation and Maintenance — Fu Lei/Zhang Yijun
  3. Rookie Tutorial – Redis basic tutorial