Redis Storage Structure

Value Encoding Types

Redis automatically selects the most efficient encoding format based on the characteristics of stored data:

• String
  • int: String length ≤ 20 and convertible to integer
  • raw: String length > 44
  • embstr: String length ≤ 44
• List
  • quicklist: Optimized linked list structure
  • ziplist: Compressed list for small datasets
• Hash
  • dict: Dictionary implementation when entries > 512 or value length > 64 bytes
  • ziplist: Compressed list when entries ≤ 512 and value length ≤ 64 bytes
• Set
  • intset: Integer array when all elements are integers and count ≤ 512
  • dict: Dictionary when any element is non-integer or count > 512
• Sorted Set
  • skiplist: When count > 128 or any member length > 64 bytes
  • ziplist: When count ≤ 128 and all member lengths ≤ 64 bytes

Dictionary Implementation

Redis uses dictionary structures to organize key-value pairs internally. When hash structures exceed 512 entries or individual string values exceed 64 bytes, Redis switches to dictionary implementation.

Data Structures

The dictionary implementation uses several interconnected structures to manage key-value storage efficiently:

typedef struct hashNode {
    void *recordKey;
    union {
        void *dataValue;
        uint64_t unsignedValue;
        int64_t signedValue;
        double floatingValue;
    } payload;
    struct hashNode *nextEntry;
} hashNode;

typedef struct hashTable {
    hashNode **bucketArray;
    unsigned long tableCapacity;
    unsigned long indexMask;
    unsigned long itemCount;
} hashTable;

typedef struct redisDict {
    hashTable buckets[2];
    long migrationIndex;
    int16_t pauseMigrations;
} redisDict;

Key Concepts:

• A string key is processed through a hash function to produce a 64-bit integer
• Identical keys consistently produce the same hash value
• Modulo operations on powers of 2 can be optimized to bitwise operations
• Due to the pigeonhole principle, collisions are inevitable: with a table size of 4, keys 1, 5, 9, and 1+4n all map to bucket index 1

Collision Handling

Redis manages collisions through chaining. The load factor is calculated as itemCount / tableCapacity. Lower load factors indicate fewer collisions but higher memory usage, while higher values mean more collisions but better memory efficiency. Redis targets a load factor of approximately 1.

Expansion

When the load factor exceeds 1, Redis doubles the hash table capacity. However, expansion is deferred during fork operations (RDB save, AOF rewrite, or combined RDB-AOF). If the load factor exceeds 5 during forking, immediate expansion occurs despite the fork to prevent severe performance degradation. This mechanism relies on copy-on-write semantics.

Shrinking

When the load factor drops below 0.1, Redis shrinks the hash table. The new capacity is the smallest power of 2 that accommodates all existing entries. For example, with 9 entries, the next power of 2 (16) becomes the new capacity.

Progressive Rehash

When hash tables contain many elements, complete rehashing cannot happen atomically as it would block Redis responsiveness. Instead, Redis employs progressive rehashing.

Rehash Process

Each element from the old hash table is rehashed to generate a new 64-bit integer, then mapped to the new table based on its capacity.

Progressive Strategy

1. Uses divide-and-conquer: rehash operations are distributed across subsequent read/write operations
2. A background timer executes up to 1 millisecond of rehashing per call, processing 100 bucket slots per iteration
3. During rehash, expansion and shrinking operations are suspended

SCAN Command

The SCAN command provides non-blocking iteration over keys:

scan cursor [MATCH pattern] [COUNT count] [TYPE type]

Design rationale:

• Uses increment-on高位进位 addition ordering, ensuring rehash-affected buckets remain adjacent in iteration
• Guarantees no duplicates or missed keys during iteration
• Edge case: Multiple shrink operations during scanning can occasionally produce duplicate key returns

Expiration Mechanism

Redis provides multiple commands for key expiration:

expire key seconds
pexpire key milliseconds
ttl key
pttl key

Lazy Expiration

Keys are checked for expiration only when accessed. If expired, the key is deleted before the operation proceeds. This approach minimizes CPU overhead but may retain expired keys in memory if never accessed.

Periodic Deletion

A background timer periodically samples keys from each database:

#define SAMPLE_SIZE_PER_CYCLE 25

/* Configurable effort multiplier affects sampling rate */
/* Minimum effort is 1, maximum is 10 */

effectiveSamples = BASE_SAMPLE_COUNT + (BASE_SAMPLE_COUNT / 4) * effort;

int processExpiredKeys(redisDb *database, hashNode *entry, long long currentTime);

Large Keys

Large keys (massive hashes or sorted sets) cause significant operational issues. During expansion, Redis attempts to allocate a contiguous memory block large enough to hold the entire structure, causing noticeable latency. Similarly, memory reclamation after deletion creates pause events.

Diagnostic indicator: If Redis memory usage fluctuates dramatically, large keys are likely the cause.

Detection approach:

# Scan Redis instance with 0.1 second intervals, examining 100 keys per iteration
redis-cli -h 127.0.0.1 --bigkeys -i 0.1