2.3 Redis Data Structures

This is a historical learning note and may contain outdated or incomplete understanding.

1. Redis DB

redisDb is the data structure used by Redis to represent a DB, and it contains a dict type.
dict is the data structure used by Redis to represent K-V pairs, and it contains a dictht type.
dictht is an array, and each element in the array is a dictEntry. (That is, Redis uses a hash structure to implement K-V.)
The next pointer of dictEntry indicates that chaining is used to resolve hash collisions.
The val pointer of dictEntry points to a redisObject. (That is, the five Redis data structures.)
The type of redisObject indicates the five data structures, and encoding indicates the underlying encoding type of that data structure.

Redis DB

Redis keys are all string types. Values have five types, and each value type corresponds to multiple internal encodings.

2. string

String.
Up to 512 MB.

2.1. Use Cases

Cache: How to Design a Cache System
Distributed lock: Redis Distributed Locks
Counter.
Web-cluster session.
Global sequence number in a distributed system.

2.2. Underlying Implementation

The underlying implementation is a string. Redis strings do not end with \0 like C strings. Instead, Redis defines a data structure called sdshdr.
- len indicates the length of the string.
- free indicates how much free space remains.
- buf stores the string.
If the stored string is only one byte, much of the space is wasted on metadata (len and free), so multiple structures were introduced after Redis 3.2.
If the value is an int, the underlying implementation is an int.

127.0.0.1:6379> set k1 v1
OK
127.0.0.1:6379> object encoding k1
"embstr"
127.0.0.1:6379> set k2 1
OK
127.0.0.1:6379> object encoding k2
"int"
127.0.0.1:6379> set k3 some_value
OK
127.0.0.1:6379> object encoding k3
"embstr"
127.0.0.1:6379> set k5 ssssssssssssssssssssssssssssssssssssssssssssssss
OK
127.0.0.1:6379> object encoding k5
"raw"

3. list

An ordered collection that allows duplicates.

3.1. Use Cases

Asynchronous queue: Redis Asynchronous Queue
Weibo follower list.

3.2. Underlying Implementation

When the amount of data is relatively small, it is implemented with a ziplist: ziplist.md (the related note has not been published yet).
- Each item stored in the list (possibly a string) is smaller than 64 bytes.
- The list contains fewer than 512 items.
When the amount of data is relatively large, it is implemented with a doubly circular linked list: linkedlist.md (the related note has not been published yet).

4. set

An unordered collection with no duplicates.

4.1. Use Cases

Implement idempotency: prevent duplicate form submissions and implement message-queue idempotency.
Likes, favorites, tags.
Following relationships.
When sending email, if there are English users then send in English; store the English users’ email addresses in a set.

4.2. Underlying Implementation

When both of the following conditions are met, an ordered array is used: array.md (the related note has not been published yet).
- All stored data is integer data.
- The number of stored elements does not exceed 512.
Otherwise a hashmap is used: hashmap.md (the related note has not been published yet).

5. zset / sorted set

A set with sorting functionality.

5.1. Use Cases

Leaderboards.

5.2. Underlying Implementation

When the amount of data is relatively small, it is implemented with a ziplist: ziplist.md (the related note has not been published yet).
- Fewer than 128 elements.
- Each element is shorter than 64 bytes.
When the amount of data is relatively large, it is implemented with a skiplist: Skip List.md (the related note has not been published yet).
- Because of the skiplist, an element can be inserted in O(logN) time, and elements can be found quickly by score range.
Looking up a score by member (zscore) is implemented using a hash.

6. hash

K-V pairs.

6.1. Use Cases

hmset for fine-grained caching.
hmset + Lua script to implement a token-bucket rate-limiting algorithm: Redis RateLimiter

6.2. Underlying Implementation

When the amount of data is relatively small, it is implemented with a ziplist: ziplist.md (the related note has not been published yet).
- Both keys and values stored in the dictionary are smaller than 64 bytes.
- The dictionary contains fewer than 512 key-value pairs.
When the amount of data is relatively small, it is implemented with a hashmap: hashmap.md (the related note has not been published yet).