Redis string is a dynamic string, a string that can be modified. The implementation of the internal structure is similar to Java's ArrayList, which uses pre-allocation of redundant space to reduce frequent memory allocation.

Preface

String is the simplest data structure in Redis, and its internal representation is an array of characters.

Redis strings are dynamic strings, which can be modified. The implementation of the internal structure is similar to Java's ArrayList, which uses pre-allocation of redundant space to reduce frequent memory allocation.

Internal implementation of redis string

Redis built a simple dynamic string to store internally, the data structure is:

struct SDS {  // 数组容量  T capacity;    // 数组长度  T len;  // 特殊标识位  byte flags;   // 数组内容  byte[] buf;}

In the data structure, the length type uses generics instead of int directly. This is because when the string is relatively short, it can be represented by byte and short.

Among them, Buf stores the real string content , capacity represents the length of the allocated array, and len represents the length of the string. When there is no redundant space in the array, a new array will be allocated when content is added, and the content in the old array will be copied Come out , and then append new content.
Redis stipulates that the maximum length of a string is 512MB. When creating a string, len is as long as capacity, and no new redundant space is allocated.

Schematic diagram of Redis string storage structure:

The last'\0' is an empty string and is not counted in the len length . This is done to follow the implementation rules of C language strings.

When the length of the Redis string becomes larger:

  1. Determine whether the capacity length is sufficient to store the newly added characters . If it is satisfied, there is no need to expand the capacity, otherwise, expand the capacity;
  2. If len<=1MB, double the capacity, that is capacity*2, and then continue to judge ;
  3. If len>1MB, only 1MB of free space will be added once, and then continue to judge;
  4. The maximum length of the string is expanded to 512MB

When the Redis string is reduced, the reduced part will not be reclaimed immediately , but will be allocated to the next program that needs memory.

Redis string expansion mechanism

There are two storage methods for redis strings. When the length is particularly short, it is stored in emb format, and when the length exceeds 44, it is stored in raw format. The two storage methods are structured as follows:

Redis object header structure

struct RedisObject {    int4 type; // 4bits    int4 encoding; // 4bits    int24 lru; // 24bits    int32 refcount; // 64bits    void *ptr; // 64bits} robj;

The entire RedisObject object header needs to occupy 16 bytes.

RedisObject = type(4bits)+encoding(4bits)+LRU(24bits)+refcount(32bits)+ptr(64bits)=128bits

128/8=16

SDS structure

The structure of SDS uses a paradigm. When the string is relatively short, len and capacity can be represented by byte and short.

So the smallest object header size is the length of content + 3, and the structure is as follows:

struct SDS {   // 1byte  int8 capacity;   // 1byte  int8 len;   // 1byte  int8 flags;   // 内联数组,长度为 capacity   byte[] buf; }

SDS = capacity(8bits)+len(8bits)+flags(8bits)+content;

In order to accommodate a complete embstr object, the memory allocator will allocate at least 32 bytes of space. If the string is a little longer, it will be 64 bytes.

If the total size exceeds 64 bytes , Redis considers it to be a large string and no longer uses the emdstr format for storage, but should use the raw format.

RedisObject = type(4bits)+encoding(4bits)+LRU(24bits)+refcount(32bits)+ptr(64bits)=16 bytes;
SDS = capacity(8bits)+len(8bits)+flags(8bits)+Buf= 3 bytes + Buf;

The remaining length of Buf is only 45 (64-19), and the string in Buf is \0-terminated, and the maximum string length of all embstr is 44.

Expansion strategy

When the length of the string is less than 1M, the expansion adopts a doubling strategy . When the length is greater than 1M, in order to avoid the doubled redundant space being too large and causing waste, each allocation will only add 1M redundant space .

Redis string command

commanddescription
SET key valueSet the value of the specified key
GET key  Get the value of the specified key
SETRANGE key offset valueRewrite the value of value starting from the offset offset. If the current key is hello, the value after SETRANGE key 2 x is hexlo
GETRANGE key start endReturns the substring of the subscript of the string value in key from start to end
GETSET key valueSet the value of the given key to value and return the old value of the key
SETBIT key offset valueFor the string value stored in the key, set or clear the bit at the specified offset. value can only be 0 or 1
GETBIT ket offsetGet the bit at the specified offset for the string value stored in the key.
MSET key1 value1 [key2 value2 ...]Set multiple key-value pairs at the same time
MGET key1 [key2...]Get all the values ​​of a given key
SETEX key seconds valueSet the value of the key, and set the effective time of the key to seconds
SETNX key valueOnly set the value of the key when the key does not exist
STRLEN keyReturns the length of the string value stored in the key
INCR keyAdd 1 to the number stored in the key, starting from 0 by default
INCRBY key incrementIncrease the value of key storage by the specified increment
INCRBYFLOAT key incrementIncrease the value stored in the key by the specified floating point increment increment
DECR keyDecrease the number stored in the key by 1, starting from 0 by default
DECRBY key incrementDecrease the value stored in the key by the specified increment
APPEND key valueIf the key exists and is a string, the value of value is appended to the original value of the key. If the key does not exist, it is equivalent to the set operation

Application scenario

counter

The commands of incr and decr are to add 1 and subtract 1 to the value of the number stored in the key. These two operations are atomic, so they can be used for calculation.

Such as: number of comments, number of likes, number of shares, etc.

Distributed lock

The function of setnx is to set the value and return 1 when the key does not exist. When the key already exists, do not set the value and return 0. This operation is also atomic, so it can be used for distributed locks.

Return 1 to indicate that the lock is obtained, and return 0 to indicate that the lock is not obtained; then use del to delete the key to release the lock.

You can set an expiration time for the key at the same time, so that when the del deletion fails, the lock can also be guaranteed to be released.

Cache

The set operation can store the value, and the data object can be serialized and stored as a cache.

User sign-in record

You can use a bitmap (byte array) to record the user's check-in record. The check-in record per day occupies only one bit, 365 days is 365 bits, and 46 bytes can be fully accommodated.