A Casual Discussion on Redis Knowledge

Redis Basic Principles

Redis has hand-crafted many data structures at the underlying level, making them more suitable for Redis application scenarios, improving high performance and reducing storage consumption.

String Data Structure

Redis's String design structure differs from other languages (JAVA, C++), and its unique design ensures high performance and low storage consumption.

As shown in the figure, the String data structure in Redis consists of len, alloc, flags, and buf. The key pointer points to the middle of flags and buf, ensuring fast read performance. When retrieving a key-String, you only need to move the pointer a few bits to the left to know the data's type, allocated space size, and used space size, and moving a few bits to the right gives you the specific content of the String directly.

QuickList

The common List is a singly linked list where each node can only store one element. Redis provides an upgraded version: QuickList, which is a doubly linked list where each node can store multiple elements.

As shown in the figure, an entry can store multiple elements, collectively packaged as a listpack, whose internal structure consists of:

• tot-bytes: The total byte size of the space occupied by the entire listpack
• num_elements: The number of stored elements
• element1~n: The n stored elements
• listpack end-byte: The end position of the listpack

Hash

Hash is the fundamental concept of Redis and is implemented in all programming languages, making it very common. Hash elements are stored in different slots. If different elements are assigned to the same slot, a linked list is formed. If the linked list becomes too long, it transforms into a red-black tree. This process needs no further explanation.

Redis needs to provide high-performance and highly reliable services. When facing situations where there are insufficient Hash slots and expansion is needed, Redis provides a progressive rehash solution.

If Hash slots are insufficient, we need to create a new Hash table, pause user responses, and migrate data from the original hash table to the new one, which inevitably causes long periods of congestion.

The idea behind progressive rehash is to spread the migration cost over each user access. Specifically, each user access migrates the accessed data to the new Hash table, but the new table is not enabled yet — the original Hash table is still used for access. After a sufficiently long time, all data from the original Hash table will be migrated to the new one, completing a seamless migration.

Zset

Zset is the sorted set provided by Redis. It implements element sorting by adding an associated score. Its main use cases are very broad, such as:

1. Dynamic leaderboards
2. Delayed queues: using score to store the timestamp for task execution

The underlying data structure of Zset is based on skip lists and Hash.

Linked lists have extremely high efficiency for modification operations, but the time complexity for queries is $O(N)$. Skip lists, on the other hand, accelerate queries through multiple different skip paths.

In Zset, each element's score is stored in the skip list, and the time complexity for add, delete, update, and query operations is very low. Additionally, to quickly locate each element's score, Zset maintains a mapping from elements to scores via a hash.

Redis Persistence Strategies

Redis is an in-memory database, which may lead to data loss. Therefore, persistence is needed to store data in the database.

AOF Incremental Files

AOF is an incremental persistence method. It achieves persistence by appending operations to a file. However, since it is stored in text form, it occupies more space.

To reduce the space usage of AOF files, Redis periodically uses the rewrite method to rewrite the backed-up operation commands.

RDB Full Snapshot Files

RDB is a full snapshot persistence method. RDB periodically saves data to disk, and it can use compression methods to significantly reduce backup file space.

Common Redis Considerations

Big Keys and Hot Keys

Definition of Big Keys:

Data Type	Big Key Standard
String type	A value with byte size greater than 10KB is a Big Key
Complex data structures like Hash/Set/Zset/List	More than 5000 elements or total value byte size greater than 10MB is a Big Key

Therefore, Big Keys can cause the following problems:

1. High read cost
2. Easy to cause slow queries (expiration deletion)
3. Master-slave replication anomalies, service blocking, inability to respond to requests normally, request timeouts and errors

To solve the Big Key problem, there are two implementation approaches:

1. Big Key compression: Use compression methods (gzip)
2. Split Big Keys into smaller keys: If the Big Key's value cannot be compressed, try to split the Big Key's value into multiple smaller values;
   1. For collection-type structures like hash, list, set, and zset, split Big Keys into smaller keys. You can use hash modulo to determine which key to place data in.
      1. There is also a unique method called hot-cold separation. For example, with leaderboard lists or bank account historical statements, users are unlikely to view all data — they only query recent data. In this case, Redis only caches recent data, and all data goes through the DB, thus avoiding the Big Key problem.

Definition of Hot Keys:

The QPS for user access to a certain Key is very high, causing a sudden CPU spike on the Server instance, making it difficult to handle all requests.

Slow Queries

Cache Penetration and Cache Avalanche

• Cache penetration: Hot data queries bypass the cache and hit the DB directly
  • Cache empty values: If querying a non-existent data, cache an empty value
  • Bloom filter: Use the bloom filter algorithm to store valid keys. Thanks to the algorithm's extremely high compression rate, only a very small amount of space is needed to store a large number of keys
• Cache avalanche: A large number of caches expire simultaneously
  • Scatter expiration times

Cache Consistency in Write Scenarios for Redis

Common Redis Use Cases

Consecutive Check-ins

Daily check-ins are a common way for many apps to increase daily active users. Users can receive certain rewards for consecutive check-ins, but if they miss a day in between, the check-in streak resets to 0.

We can store the user's check-in days by setting a user-check-in days key-value pair in Redis, and use Redis's expiration time capability to implement consecutive check-ins. For example, setting a 24-hour expiration means that after 24 hours, the key-value pair will be cleared, causing the check-in count to reset to 0.

Message Notifications

Uses QuickList. Another solution is pub-sub, but this is introduced using list.

Counting

Uses Hash, and pipe pipelines to reduce the number of operations.

Leaderboards

Zset

Rate Limiting

For a single user, excessive requests to an interface should not be allowed. Limit requests to fewer than 10 per second. Set the key as req_limit_timestamp.

Distributed Locks

Due to Redis's excellent single-threaded characteristics, implementing distributed locks is very easy. Use the setnx command.

The distributed lock capability provided by Redis's setnx also has many drawbacks:

1. Business timeout unlocking causes concurrency issues. The business execution time exceeds the lock release time.
2. The critical point issue during Redis master-slave failover. After failover, if the lock held by A has not been synchronized to the new master node, B can acquire the lock on the new master node.
3. Redis cluster brain-split, resulting in multiple master nodes.