Implementing DEL, EXPIRE, and Auto-Cleanup in Redis Internals

This document explores the internal workings of Redis’s DEL and EXPIRE commands, along with its crucial auto-expiration and cleanup mechanisms. We’ll delve into how these features are implemented in a Go-based Redis clone, highlighting the design choices and trade-offs that enable Redis’s high performance and memory efficiency.

1. Implementing the DEL Command

The DEL command in Redis is used to remove one or more specified keys. Its behavior is straightforward: it deletes existing keys and returns the number of keys successfully deleted.

1.1. Redis CLI Behavior

• DEL key: Deletes key and returns 1 if the key existed and was deleted. If key did not exist, it returns 0.
• DEL key1 key2 key3: Can delete multiple keys. It returns the total count of keys that were actually removed, ignoring non-existent keys.

1.2. Golang Implementation Details

Our Go implementation of DEL resides in the eval.go file, which handles command evaluation.

// eval.go
func evalDelete(args []string, rw io.ReadWriter) {
    deletedCount := 0
    for _, key := range args {
        // store.Delete is an abstraction to remove key from the hash map
        if store.Delete(key) {
            deletedCount++
        }
    }
    // Encode and return the count of deleted keys
    encodeInteger(rw, deletedCount)
}

// store.go
func Delete(key string) bool {
    // Assuming 'store' is a global or accessible hash map (e.g., map[string]interface{})
    if _, exists := store.data[key]; exists {
        delete(store.data, key)
        return true
    }
    return false
}

Key Logic:

• The evalDelete function iterates through all provided arguments, treating each as a key to be deleted.
• For each key, it calls store.Delete(key), an abstracted function responsible for removing the key from the underlying hash map.
• store.Delete returns true if the key was found and deleted, and false otherwise.
• A deletedCount variable tracks the number of successful deletions.
• Finally, encodeInteger is used to send the deletedCount back to the client, adhering to Redis’s RESP (REdis Serialization Protocol) for integer responses.

2. Implementing the EXPIRE Command

The EXPIRE command sets a timeout on a key. After the timeout, the key will automatically be deleted. This is useful for temporary data or caching.

2.1. Redis CLI Behavior

• EXPIRE key seconds: Sets an expiration of seconds on key. Returns 1 if the timeout was set, 0 if key does not exist or the operation failed for other reasons.
• If key already has an expiration, EXPIRE will overwrite it.

2.2. Golang Implementation Details

The EXPIRE command’s logic is also implemented in eval.go.

// eval.go
func evalExpire(args []string, rw io.ReadWriter) {
    // 1. Argument validation
    if len(args) != 2 {
        encodeError(rw, "ERR wrong number of arguments for 'expire' command")
        return
    }

    key := args[0]
    durationStr := args[1]

    // 2. Parse duration
    durationSeconds, err := strconv.ParseInt(durationStr, 10, 64)
    if err != nil {
        encodeError(rw, "ERR value is not an integer or out of range")
        return
    }

    // 3. Get the object from the store
    obj := store.GetRaw(key) // Assuming GetRaw returns the internal object or nil
    if obj == nil {
        encodeInteger(rw, 0) // Key does not exist, cannot set expiration
        return
    }

    // 4. Calculate absolute expiration time in milliseconds
    expiresAt := time.Now().UnixMilli() + durationSeconds*1000
    obj.ExpiresAt = expiresAt // Assuming obj has an ExpiresAt field

    // 5. Update the store (if necessary, depending on store.GetRaw implementation)
    store.SetRaw(key, obj) // Ensure the updated object is stored

    encodeInteger(rw, 1) // Expiration set successfully
}

Key Logic:

• Argument Validation: Ensures exactly two arguments (key and duration) are provided.
• Duration Parsing: Converts the duration string to an int64 representing seconds. Handles parsing errors.
• Key Existence Check: Retrieves the key’s object from the store. If the key doesn’t exist, it returns 0, as expiration cannot be set on a non-existent key.
• expiresAt Calculation: Calculates the absolute Unix timestamp in milliseconds when the key should expire. This is current_time_in_millis + duration_in_seconds * 1000.
• Storing Expiration: The calculated expiresAt is stored within the key’s object (e.g., obj.ExpiresAt). A value of -1 can signify no expiration.
• Return Value: Returns 1 upon successful expiration setting.

3. Redis Key Auto-Deletion Mechanisms

While DEL and EXPIRE handle explicit deletions, Redis also needs to automatically clean up keys that have expired. This is crucial for memory management and preventing stale data.

3.1. Why Auto-Deletion?

• Memory Management: Prevents expired keys from indefinitely occupying memory.
• Data Freshness: Ensures clients only retrieve valid, unexpired data.
• Set-and-Forget: Allows users to set an expiration and rely on Redis for cleanup, reducing manual burden.

Redis employs two primary modes for key auto-deletion: Passive Deletion and Active Deletion.

3.2. Passive Deletion (Lazy Deletion)

Passive deletion occurs when a client attempts to access an expired key. Instead of immediately deleting keys as they expire, Redis performs a check only when the key is requested.

Mechanism:

1. A client sends a command (e.g., GET, TTL) for a specific key.
2. Before returning the key’s value, Redis checks its expiresAt timestamp.
3. If expiresAt is less than or equal to the current time, the key is considered expired.
4. The key is then explicitly deleted from the hash table, and the client is informed that the key does not exist (e.g., nil for GET).

Golang Implementation in store.go’s Get function:

// store.go
func Get(key string) (interface{}, bool) {
    obj, exists := store.data[key]
    if !exists {
        return nil, false // Key does not exist
    }

    // Assuming obj is a struct with Value and ExpiresAt fields
    if obj.ExpiresAt != -1 && obj.ExpiresAt <= time.Now().UnixMilli() {
        // Key is expired, perform passive deletion
        delete(store.data, key)
        return nil, false // Return not found after deletion
    }

    return obj.Value, true // Key exists and is not expired
}

Trade-offs:

• Pros: Very efficient as it only performs work when necessary. No background threads or constant scanning required.
• Cons: Expired keys that are never accessed will remain in memory indefinitely, leading to potential memory leaks if not addressed by active deletion.

3.3. Active Deletion

Active deletion addresses the limitation of passive deletion by periodically scanning for and removing expired keys that haven’t been accessed. This is where Redis’s single-threaded nature and statistical approach shine.

3.3.1. The Challenge: Single-Threaded Nature

Redis is single-threaded, meaning it processes commands one by one. This simplifies concurrency management but poses a challenge for background tasks like active deletion. A dedicated background thread is not an option. Iterating through all keys to find expired ones would be extremely costly and block the main event loop, leading to high latency.

3.3.2. The Statistical Algorithm

Redis employs a probabilistic, statistical algorithm to perform active deletion without blocking the server:

1. Periodic Execution: A