Redis Internals: Understanding Objects, Encodings, and INCR Command Implementation

Redis, a powerful in-memory data store, often presents intriguing behaviors that hint at its sophisticated internal architecture. One such behavior is observed with the INCR command, which can increment a non-existent key, return an integer, yet store the value as a string. This article delves into the Redis object model, explaining how types and encodings make such flexibility possible, and walks through the implementation of the INCR command.

The Curious Case of Redis INCR

Consider the following sequence of Redis commands:

1. INCR mykey: Returns 1. Even though mykey didn’t exist, Redis initialized it and incremented its value.
2. SET mykey 10: Sets the value of mykey to 10.
3. INCR mykey: Returns 11 (an integer).
4. GET mykey: Returns "11" (a string).

This behavior raises a fundamental question: How does Redis manage to return an integer for INCR but a string for GET on the same key? The answer lies in Redis’s internal object representation, specifically its redisObject structure, and the concepts of types and encodings.

The Redis Object Model: redisObject

Redis is fundamentally a key-value store where keys are hashed, and values are encapsulated within a generic redisObject. This redisObject structure is designed to hold not just the actual data but also crucial metadata, making Redis highly flexible and memory-efficient.

The redisObject structure, as found in the Redis source code, typically includes:

• type: Stores the object’s abstract data type (e.g., string, list, set).
• encoding: Stores the concrete implementation or encoding of the type (e.g., raw string, integer-encoded string, ziplist).
• lru: Used for Least Recently Used (LRU) eviction strategies.
• refcount: A reference counter for garbage collection, indicating how many pointers refer to this object.
• ptr: A void* pointer to the actual data structure (e.g., a string, a linked list, a hash table).

Memory Optimization: Bit Fields

A key design decision in redisObject is the use of bit fields for type and encoding. Instead of allocating full bytes or integers for these fields, Redis assigns a limited number of bits:

• type: 4 bits
• encoding: 4 bits

This means type and encoding together occupy only 1 byte (8 bits). This is a significant memory saving, especially considering Redis’s in-memory nature. If Redis were to use full 4-byte integers for each, it would consume 8 bytes instead of 1 byte for these two fields alone.

Total Object Size

Combining all fields, a redisObject typically occupies 12 bytes:

• type (4 bits) + encoding (4 bits) = 1 byte
• lru (24 bits) = 3 bytes
• refcount (4 bytes) = 4 bytes
• ptr (4 bytes for a pointer on a 32-bit system, 8 bytes on 64-bit) = 4 bytes (assuming 32-bit for calculation in video)

Total: 1 + 3 + 4 + 4 = 12 bytes (on a 32-bit architecture, or 16 bytes on 64-bit if ptr is 8 bytes). This compact size is crucial for Redis’s performance.

Redis Types: What Redis Really Stores

Redis supports a limited set of abstract data types. These are the high-level categories of data it can store:

• OBJ_STRING
• OBJ_LIST
• OBJ_SET
• OBJ_ZSET (Sorted Set)
• OBJ_HASH
• OBJ_MODULE
• OBJ_STREAM

Crucially, notice that OBJ_INT (an integer type) is not listed here. This means Redis does not have a dedicated internal type for integers. This is where encodings come into play.

Redis Encodings: The Concrete Implementations

While type defines what kind of data an object represents, encoding defines how that data is concretely implemented or stored. Each type can have multiple encodings, allowing Redis to optimize memory and performance based on the specific characteristics of the data.

Encoding Examples:

• OBJ_STRING Type:

  • OBJ_ENCODING_RAW: A raw byte array, typically for larger strings (e.g., > 44 bytes).
  • OBJ_ENCODING_EMBSTR: An embedded string, optimized for smaller strings (e.g., <= 44 bytes), where the string data is stored directly within the redisObject allocation itself, avoiding a separate malloc call.
  • OBJ_ENCODING_INT: Used when a string value can be represented as an integer. The integer is stored as its string representation (e.g., “123”) but is internally flagged as an integer encoding for specific operations.

• OBJ_LIST Type:

  • OBJ_ENCODING_ZIPLIST: A compact, memory-efficient data structure for small lists.
  • OBJ_ENCODING_LINKEDLIST: A standard linked list, used when the list grows beyond a certain threshold, offering better performance for larger lists.

• OBJ_SET Type:

  • OBJ_ENCODING_INTSET: A specialized set for storing only integers, highly memory-efficient.
  • OBJ_ENCODING_HASHTABLE: A generic hash table for storing any type of set members.

Dynamic Encoding Changes

Redis can dynamically change an object’s encoding based on its content or size. For example, a ZIPLIST might be converted to a LINKEDLIST once it exceeds a certain number of elements or total size. This allows Redis to start with a memory-optimized encoding for small data sets and transition to a performance-optimized encoding as data grows.

The INT Encoding for Strings

This is key to understanding the INCR command. When Redis stores an integer like 10, it’s actually stored as a string ("10") with an OBJ_STRING type and OBJ_ENCODING_INT encoding. This encoding tells Redis that although the value is a string, it can be interpreted as an integer for arithmetic operations.

Design Philosophy and Trade-offs

Redis’s object model reflects several thoughtful design decisions:

1. Memory Efficiency: The use of bit fields for type and encoding, and specialized encodings like ZIPLIST and INTSET, significantly reduces memory footprint, especially for small data sets. The 40% memory saving on redisObject itself is a testament to this.
2. Extensibility: The void* ptr allows redisObject to point to any underlying data structure. Combined with the flexible encoding field, this makes Redis highly extensible. For instance, a Bloom filter could be implemented as an OBJ_STRING with a custom OBJ_ENCODING_BLOOMFILTER (or even OBJ_ENCODING_RAW), where the ptr points to the Bloom filter’s byte array.
3. User Experience vs. Raw Performance: The INCR operation, which involves converting a string to an integer, incrementing it, and converting it back to a string, might seem computationally expensive. However, this design simplifies the user experience by allowing INCR to work on string keys that represent numbers, without requiring a separate INT type. The creators prioritized this flexibility and simplicity, accepting a minor performance trade-off for this specific operation, as it’s often not the bottleneck.

Implementing Redis Internals in Go

Re-implementing Redis in Go requires careful consideration of how to mimic its C-based internal structures, especially the bit fields.

Simulating Bit Fields in Go

Go does not directly support bit fields like C. To achieve a similar effect for type and encoding, a single uint8 (8-bit unsigned integer) can be used to store both:

type RedisObject struct {
    Value       interface{}
    ExpiresAt   int64
    TypeEncoding uint8 // Combines type (first 4 bits) and encoding (last 4 bits)
}

// Object types (left-shifted by 4 bits to occupy the higher 4 bits of TypeEncoding)
const (
    ObjectTypeString = 0 << 4
    ObjectTypeSet    = 1 << 4
    // ... other types
)

// Object encodings (occupy the lower 4 bits of TypeEncoding)
const (
    ObjectEncodingRaw        = 0
    ObjectEncodingInt        = 1
    ObjectEncodingEmbeddedStr = 8
    // ... other encodings
)

// To combine:
// obj.TypeEncoding = ObjectTypeString | ObjectEncodingInt

// To extract type:
// obj.TypeEncoding & 0xF0 // Mask for higher 4 bits
// (obj.TypeEncoding >> 4) // Right shift to get actual type value

// To extract encoding:
// obj.TypeEncoding & 0x0F // Mask for lower 4 bits

This approach uses bitwise operations to pack and unpack the type and encoding values into a single byte.

The SET Command: Deduce Type and Encoding

When a SET command is executed, Redis needs to determine the appropriate type and encoding for the value. The deduceTypeEncoding function plays a crucial role:

1. Attempt Integer Conversion: It first tries to parse the value as an integer. If successful, the objectType is ObjectTypeString, and objectEncoding is ObjectEncodingInt.
2. Check for Embedded String: If not an integer, it checks if the string’s length is less than or equal to 44 bytes. If so, objectType is ObjectTypeString, and objectEncoding is ObjectEncodingEmbeddedStr.
3. Default to Raw String: Otherwise, objectType is ObjectTypeString, and objectEncoding is ObjectEncodingRaw.

This logic ensures that even numbers are stored as strings but with an INT encoding flag, allowing Redis to perform arithmetic operations efficiently when needed.

The INCR Command: Step-by-Step Logic

The implementation of the INCR command follows this logic:

1. Argument Validation: Ensure exactly one argument (the key) is provided.
2. Retrieve Object: Attempt to retrieve the redisObject associated with the key from the store.
3. Handle Non-Existent Key: If the object does not exist, a new redisObject is created with:
   • Value: "0" (string representation of zero)
   • TypeEncoding: ObjectTypeString | ObjectEncodingInt This new object is then stored.
4. Type and Encoding Assertion: The retrieved (or newly created) object’s TypeEncoding is checked:
   • It must be ObjectTypeString.
   • Its encoding must be ObjectEncodingInt. If these conditions are not met (e.g., trying to INCR a list), an error is returned.
5. Value Conversion and Increment: The object’s string Value is parsed into an integer, incremented, and then converted back into a string.
6. Update Object: The redisObject’s Value field is updated with the new string representation of the incremented integer.
7. Return Result: The incremented integer value is returned to the client.

This process perfectly mimics the observed behavior: INCR always returns an integer, but the underlying storage remains a string with an INT encoding.

Conclusion: Extensibility and Thoughtful Design

The Redis object model, with its distinct type and encoding fields, is a testament to thoughtful database design. It enables:

• Memory Efficiency: Through bit fields and specialized encodings.
• Extensibility: Allowing new data structures (like a Bloom filter) to be integrated by simply defining a new encoding for an existing type (e.g., OBJ_STRING).
• Flexibility: Adapting data representation dynamically based on content and usage patterns.

Understanding these internals reveals how Redis achieves its remarkable performance and versatility, making it a powerful and adaptable tool for various use cases.