This is the 24th day of my participation in the August Text Challenge.More challenges in August

Redis data structure and algorithm implementation

Overview of Redis

Redis is a simple key-value database, that is, the process of using keys to get values. Rather than complex data structures like a relational database

Redis operates in memory, so you need to consider the memory usage of the host when manipulating data

Common data types include string, List, set, zset, and dictionary hash objects.

In addition, there are similar geospatial(storage geographic latitude and longitude), Hyperloglog (number of sets), bitmap(bitmap), not to repeat, Baidu a lot of (in fact, there are also their own actual use scenarios, you can understand the interview and the interviewer to talk about it)

The List (List)

The list used in Redis consists of two parts

  • Compressed list (used when the amount of data stored in the list is small)
  • Bidirectional loop list ()

Two conditions need to be met for a compressed list

  1. A single data is smaller than 64 bytes
  2. The number of data in the list is less than 512

A contiguous piece of space is used to store data, and each node may be different in size (the only difference compared to an array is that each node of the array is the same size, which can cause memory waste because some data sizes are smaller than the node size. So this is where the concept of compression comes in.)

Features:

  1. Small memory footprint
  2. Supports multiple types of data stores

Bidirectional cyclic list

// The following is the C code, because Redis is implemented in C.
typedef struct listnode {
  struct listNode *prev;
  struct listNode *next;
  void *value;
} listNode;


typedef struct list {
  listNode *head;
  listNode *tail;
  unsigned long len;
  / /... Omit other definitions
} list;
Copy the code

There is also a list field to represent the head pointer, tail pointer, and length of the list

hash

Compressed list and hash table are two ways to achieve

Using a compressed list implementation is consistent with the above conditions

Hash table uses MurmurHash2 as the hash algorithm, which is characterized by fast operation and good randomness. Redis also supports dynamic expansion and shrinkage of hash tables

As data increases dynamically, the load factor of the hash table keeps growing. To prevent hash table performance degradation, when the load factor is greater than 1, Redis triggers expansion, expanding the hash table to about twice its original size. Redis triggers scaling when the load factor is less than 0.1

Capacity expansion or reduction involves data relocation and hash recalculation, consuming resources

set

Implementations include the following two types

  • Orderly array
  • Hash table

A set is primarily non-repeating data

The condition for an ordered array is

  • The data stored is all integers;
  • A maximum of 512 data elements are stored.

zset

An ordered set

implementation

  • List of compression
  • Jump table

The condition for the compressed list is

  • All data should be less than 64 bytes in size;
  • The number of elements must be less than 128.

So how does redis persist

The values of key-value pairs can support multiple data types. Do you still need to store the corresponding structure on disk

  1. Only data is stored, and the data structure is just an identifier, which can be restored to the corresponding data type when needed. In this case, restoration consumes resources to perform this operation
  2. Data structures and data are stored