Redis principle and implementation details (1)

Redis (Remote Dictionary Service) remote dictionary service, memory database, kv database, data structure database

http://redis.cn/commands.html

1. Application:

The number of likes, comments, and clicks in the circle of friends (hash)

Record the Moments of Friends Talk List (sort), quick display (list)

Record the title, abstract, author and cover of the article, and display on the list page (hash)

Moments like user ID, comment ID, display de-duplication count (zset)

Cache hot data to reduce database pressure (hash)

Moments of friends talk about id (counter string)

Set up and merge to record the friendship (set)

Game record (list)

2. Data structure & storage structure

string: Binary security string (length = std::string)

hash: hash table/dictionary (=unordered_map) [core]

list: end-to-end two-way queue

set: collection (unordered and unique)

zset: set (ordered and unique) [core-distributed timer, current limit]

3. Value encoding rules

The memory allocator thinks that less than 64byte = small character string, and greater than 64byte = large character string

4. Use

redis-server //Open Redis server

redis-cli -h 127.0.0.1 -a 123456 //Open the Redis client


string

  • Character array, dynamic string, when the length is less than 1M, double expansion; more than 1M each time expand 1M; the maximum length is 512M
  • Binary security string, can store pictures, binary protocol and other data
  • The string length is less than 20 and can be converted to an integer, and it is stored in int; the string length is less than or equal to 44, and it is stored in embstr; the string length is greater than 44, and it is stored in raw
SET GET INCR INCRBY DECR DECRBY DEL SETNX
Set Get Atom+1 Atom+num Atom-1 Atom-num Delete Set a key that does not exist
SETBIT key offset value GETBIT key offset BITCOUNT key
Set the bit value of the offset of value in the offset Return the bit value of the key corresponding to the string in the offset bit Count the number of bit1
Application: Object storage, accumulator (incr reads), distributed lock (setnx lock 1), bit operation

list

  • Implementation of doubly linked list, the time complexity of the first and last operations (delete and add) of the list is O(1); the time complexity of finding the middle element is O(n)
  • gzip compression: the element length is less than 48, no compression; the difference between the length of the element before and after compression does not exceed 8, no compression (storage: two-way list, compressed list)
LPUSH LPOP RPUSH RPOP LRANGE LREM BRPOP DEL
LRANGE key start end LREM key count value BRPOP key timeout Block when the queue is empty (timeout time s+delay queue)
Application: stack (LPUSH+LPOP) queue (LPUSH+RPOP) blocking queue (LPUSH+BRPOP/RPUSH+RLPOP)
Asynchronous message queue (using redis between web and server) to obtain fixed window records (LPUSH+LTRIM lists 0 4 fixed length is 5)

hash

  • Hash table, which contains this data structure in many high-level languages; c++ unordered_map quickly index value through key;
  • The number of nodes <=512 and the string length <=64 are stored in a compressed list, otherwise the dictionary is stored
HGET HSET HMSET HMGET HINCRBY HLEN HDEL
Application: storage objects, shopping carts

set

  • Set, used to store unique fields, does not require order; (Storage is ordered, but order is not required during use)
  • The element is an integer and the number of nodes <=512 is stored in an integer array, and if one of the elements is not an integer or the number is greater than 512, it is stored in a dictionary
SADD SCARD SMEMBERS SISMENBER SRANDMEMBER SPOP SDIFF SINTER SUNION
Key plus member Count the number Return members Determine whether they are members Randomly return members Remove and return Seek the difference of the members of the set Intersection Union
Application: lottery, follow together, recommend friends

zset

Ordered set; used to implement rankings; it is an ordered and unique (member only) structure [zset: set key score score member member]

Number>128 or a string length>64, skip table storage; number of child nodes <=128 and string length <=64 compressed list storage

When the number is small, the list is compressed, saving space O(n); when the number is large, the access performance is O(1) O(logn).

ZADD ZREM ZSCORE ZINCRBY ZCARD ZRANK ZRANGE ZREVRANGE
Add score-member to the set key Delete Return score score increment Number of elements Return ranking Return elements in range Return reverse order
Application: Baidu hot list, delay queue (the orderliness of zset, expiration time as score, in distributed system: distributed timer),
Time window current limit (limit the max_count of the userid's action in the period)

Delay queue: If an event A is handed over to B for processing, and B is not completed within the specified time , the task is forwarded to C or returned to (return, forwarding method), which can be achieved by using a delay queue. When A is assigned to task B, the current time record is put into the delay queue, and the timeout record is obtained, and the forwarding or backing delete operation is performed.

Generally, there are several ways to deal with lock failure:

1. Throw an exception directly and notify the user to try again later;

2. Retry after sleep for a while;

3. Transfer the request to the delay queue and try again later;

Use zset to implement the delay queue, use the order of zset, use the expiration time as the score, zrangebyscore finds out the due tasks, and executes zrem to delete them.

In order to avoid multi-threaded competition, you can use the Lua script to execute these two commands atomically to prevent multiple threads from acquiring tasks at the same time, but they cannot be deleted, and the operation is performed in vain.

Solution: funnel current limit


Time window current limit: The system limits a user's behavior can only occur N times in a specified time

Maintain a time window, clean up all the records outside the window, and only keep the records in the window;
Disadvantage: All data in the time window are recorded. If this amount is large, it is not suitable for such a current limit.