Implementing All Keys Random Eviction and INFO Command in Redis Internals

In this deep dive, we’ll explore two crucial aspects of building a Redis-compliant database: implementing the ‘All Keys Random’ eviction strategy and supporting the ‘INFO’ command for real-time database statistics. We’ll also see how these features can be visualized using industry-standard tools like Prometheus and Grafana, demonstrating the power of Redis compliance.

All Keys Random Eviction Strategy

Continuing our journey into Redis eviction strategies, we move beyond simple first-key eviction to a more sophisticated approach: ‘All Keys Random’.

Concept

The ‘All Keys Random’ eviction strategy is straightforward: when the database reaches its maximum key limit, it randomly selects and evicts a certain percentage of existing keys from the entire dataset. This differs from strategies that target specific subsets of keys (like LRU or LFU) by considering all keys equally for eviction.

Implementation in diceDB

Our diceDB implementation of ‘All Keys Random’ involves a few key components:

1. Eviction Strategy Configuration: We set the eviction strategy to AllKeysRandom.
2. Key Limit (keysLimit): A maximum number of keys the database can hold. For demonstration, we set this to 100.
3. Eviction Ratio (evictionRatio): This dictates the percentage of keys to evict when the limit is breached. For a clear demonstration of the algorithm, we use 0.4 (40%). In production, this ratio would typically be much smaller (e.g., 5-10%) to minimize performance impact.

The core logic resides in the evictAllKeysAtRandom function within eviction.go:

• Calculate Keys to Evict: number_of_keys_to_evict = keysLimit * evictionRatio.
• Iterate and Delete: The function iterates through the hash table (which stores our keys). For every count number of keys, it invokes a delete operation.

Relying on Hash Table Randomness

Crucially, our implementation leverages the inherent randomness of Go’s hash table iteration. When a key is inserted, it’s passed through a hash function, landing in a specific slot. Since we don’t know the exact output of the hash function, iterating through the hash table provides a fairly random distribution of keys. This allows us to achieve a ‘random’ eviction without implementing a separate random sampling mechanism, making the implementation simple and efficient.

// Pseudocode for evictAllKeysAtRandom
func evictAllKeysAtRandom(db *DB, keysLimit int, evictionRatio float64) {
    numKeysToEvict := int(float64(keysLimit) * evictionRatio)
    keysEvicted := 0

    // Iterate through the hash table (map in Go)
    for key := range db.data {
        if keysEvicted >= numKeysToEvict {
            break
        }
        db.Delete(key) // Invoke delete operation
        keysEvicted++
    }
}

Database Statistics with the INFO Command

Beyond eviction, understanding the internal state of our database is paramount. This is where statistics come into play, and Redis provides the INFO command for this purpose.

Importance of Statistics

Database statistics are vital for:

• Monitoring: Keeping an eye on key metrics like memory usage, connected clients, and, in our case, the number of keys.
• Alerting: Setting up alerts for abnormal behavior or resource exhaustion.
• Transparency and Confidence: Gaining insight into the database’s health and performance.

The Redis INFO Command

The INFO command in Redis returns a wealth of information about the server in a human-readable format. When you run redis-cli info, you get an output categorized into various sections.

Response Format

The INFO command’s response is structured into multiple sections, each starting with a section title prefixed by hash space (e.g., # Server, # Clients, # Memory, # Persistence, # KeySpace).

Within each section, information is presented as key:value pairs, followed by \r\n (carriage return, newline). For the KeySpace section, which is our primary interest, the format is slightly different:

# KeySpace
db0:keys=1,expires=0,avg_ttl=0
db1:keys=0,expires=0,avg_ttl=0
...

Here, db0 is the key, and keys=1,expires=0,avg_ttl=0 is its value. Redis supports up to 16 databases (db0 to db15), with db0 being the default.

Implementing INFO in diceDB

Our diceDB implementation focuses specifically on the KeySpace section to report the number of keys. We don’t implement expires or avg_ttl for this demonstration.

1. Command Definition: The INFO command is defined in eval.go.
2. Response Generation: We construct the response using a buffer, starting with # KeySpace\r\n.
3. Key Space Statistics Object (keySpaceStat): A global object (e.g., a map of maps or a slice of structs) is used to store key counts for different databases. For simplicity, diceDB supports 4 databases (db0-db3).

   // Example structure for keySpaceStat
   var keySpaceStat = []struct {
       keys int
   }{
       {keys: 0}, // db0
       {keys: 0}, // db1
       {keys: 0}, // db2
       {keys: 0}, // db3
   }

4. Updating Statistics: The updateDBStatus function is responsible for updating these global key counts. Crucially, every time a SET operation occurs, keySpaceStat[db_index].keys++ is called. Similarly, on a DELETE operation, keySpaceStat[db_index].keys-- is called. This ensures the global object always reflects the current number of keys.

When the INFO command is fired, it simply reads the current values from keySpaceStat and formats them into the Redis-compliant KeySpace section, sending it back as a bulk string response.

Visualizing Eviction and Statistics in Action

Point-in-time statistics are useful, but historical trends are essential for understanding database behavior over time. This is where visualization tools come into play.

The Visualization Stack: Prometheus and Grafana

• Prometheus: A powerful open-source monitoring system and time-series database. It pulls metrics from configured targets (like our diceDB via an exporter) and stores them.
• Grafana: A leading open-source platform for monitoring and observability. It connects to various data sources (like Prometheus) to create dynamic and interactive dashboards for visualizing metrics.
• Redis Exporter: A Prometheus exporter specifically designed to expose Redis metrics in a format Prometheus can understand. This is a crucial bridge.

diceDB’s Redis Compliance

The beauty of implementing the INFO command in diceDB in the exact same format as Redis is that we can reuse existing Redis tooling without any modifications:

1. The redis-cli can connect to diceDB (running on port 7379 in our demo) and issue INFO commands.
2. The standard redis-exporter can connect to diceDB, continuously fire INFO commands, collect the metrics, and expose them on an endpoint.
3. Prometheus can then scrape this endpoint, persist the time-series data.
4. Grafana can query Prometheus and render beautiful charts showing diceDB’s key count over time.

Demonstration Walkthrough

Let’s walk through a typical demonstration:

1. Initial State: Connect redis-cli to diceDB (e.g., dot/redis-cli -p 7379). An initial INFO command shows db0:keys=0.
2. Setting Keys: Execute SET K1 V1, SET K2 V1, etc. Each INFO command will now show db0:keys=1, db0:keys=2, and so on.
3. Grafana Setup: A Grafana dashboard is configured to plot the number_of_keys metric collected by Prometheus from diceDB.
4. Bombarding with Keys: A storm utility (a simple Go program) continuously fires SET requests with random keys and values to diceDB.

   go run storm/set/main.go

5. Observing the Sawtooth Pattern: As the storm utility bombards diceDB with keys, the Grafana chart will show a distinct