Solving the challenges of data deletion in Redis

Remote Dictionary Server (Redis) does not provide a direct command for deleting keys based on a pattern. Instead, the process involves iterating over the database using the SCAN command to identify matching keys, followed by the DEL command to remove them.

This approach is resource-intensive for several reasons:

• Iteration overhead: SCAN must traverse portions of the database to find matching keys, even for a single entry.
• Repeated scans for multiple patterns: Deleting keys for multiple patterns requires repeating the process for each pattern, significantly increasing overhead and latency.

Limitations of Lua scripts for deletion

Lua scripts may seem like a solution, as they allow combining SCAN and DEL into a single atomic operation. However, this approach has drawbacks:

• Blocking behavior: Lua scripts execute in a blocking manner, preventing Redis from processing other read or write operations during execution.
• High-traffic impact: In high-traffic environments, blocking operations can lead to timeouts and hinder other workflows.
• Performance risks with large datasets: As Lua scripts take longer to execute on large datasets or complex patterns, the risk of disruption to concurrent operations increases.

Importance of data deletion in Redis

Efficient data deletion in Redis is essential for:

• System performance: Removing unnecessary data ensures faster access to relevant information and optimizes Redis's responsiveness.

• Reliability: Proper data management helps maintain a clean dataset, reducing the risk of performance degradation or operational issues.

• Cost-efficiency: Redis operates in RAM, which is both expensive and limited. Effective memory management minimizes costs while maximizing resource utilization.

Challenges in deleting data by pattern in Redis

Consider a scenario with 1 million records in Redis, where we need to delete keys matching five different regex patterns:

1. Test*(T1)*
2. Test*(T2)*
3. Test*(T3)*
4. Test*(T4)*
5. Test*(T5)*

Issue with multiple patterns

To delete records matching these patterns:

• The database must be iterated five times, once for each regex pattern.
• Assuming:
  • Batch size: 1,000 records scanned per iteration.
  • Time per SCAN operation: 500 ms.

The total time required:

Time= 1M × 5× 500ms / 1000 = 42 minutes.

This time increases significantly with a larger number of records or regex patterns.

Generalized formula for time calculation

To calculate the total time required for deleting records matching multiple regex patterns:

Total Time (ms) = O((N × M × K) / Batch Size)

Where:

• N: Total number of records in the database.
• M: Number of regex patterns.
• K: Time (in ms) taken for a single SCAN operation.
• Batch Size: Number of records processed per SCAN batch.

The preceding approach, while functional, can be significantly optimized to reduce the time and resource overhead associated with pattern-based deletions.

Possible solutions for optimizing data deletion in Redis

1. Use SCAN with batch deletion

   • Approach: Leverage the non-blocking SCAN command to fetch keys matching a pattern in small batches, followed by the DEL command to remove those keys.
   • Benefits:
     • Prevents locking Redis and avoids blocking other operations.
     • Spreads the deletion process over time, reducing strain on the server.

2. Offload to an external script

   • Approach: Use an external application or worker process to fetch keys via SCAN and delete them iteratively.
   • Benefits:
     • Reduces the load on Redis by offloading the deletion task to a separate process.
     • Isolates the deletion operation from critical Redis workloads, ensuring better overall system performance.
   • Trade-off: Requires additional infrastructure and scripting for implementation.

3. Use key expiration (EXPIRE)

   • Approach: Set expiration times for keys at creation using EXPIRE or SETEX commands, ensuring automatic deletion once the data becomes irrelevant.
   • Benefits:
     • Eliminates the need for manual pattern-based deletions.
     • Reduces operational overhead by automating data removal.
   • Trade-off: Not applicable to data that lacks predefined expiration logic.

4. Lua scripts with time-slicing

   • Approach: Use Lua scripts to delete data in smaller chunks with deliberate pauses to avoid long blocking operations. This method combines SCAN and DEL within the script, limiting the number of keys processed per execution.
   • Benefits:
     • Maintains atomicity of deletion operations while reducing blocking impact.
     • Allows Redis to continue handling other requests during the process.
   • Trade-off: If not properly tuned, this approach may still negatively affect Redis performance, especially in high-traffic environments.

Our approach

We have combined Solution 2 (Offloading to an external script) with Solution 4 (Lua Scripts with time-slicing) to address our problem.

In our approach:

• Lua Script: We use a Lua script to efficiently scan the database while limiting the keys to be processed.
• Offloading to external script: The data retrieved by the Lua script (which is independent of regex patterns) is passed to an external script. This external script processes the keys against multiple regex patterns. If a match is found, the corresponding key is deleted from Redis using the DEL command.

This combined method enables us to process multiple regex patterns in a single iteration over the database. Additionally, time-slicing is implemented between consecutive scans, ensuring other queued requests are processed without delays, preventing any potential performance degradation.

Understanding the scenario with an Example

Let’s assume the Redis database contains the following 8 keys:

• ABC123
• ABC234
• BCD123
• BCD234
• CDF123
• DEF234
• HJK123
• LMN123

Now, suppose we need to delete keys that match the regex patterns *ABC* and *BCD*.

Using Approach 2 (Offloading to an external script) alone, we would need to iterate over the database twice:

1. Once to fetch keys matching *ABC*
2. A second time to fetch keys matching *BCD*

Similarly, Approach 4 (Lua Scripts with time-slicing) would also require two separate iterations for each regex pattern.

To overcome this inefficiency, we use a Lua script to scan the entire database and fetch keys in batches, without initially filtering by any regex patterns. The retrieved keys are then passed to an external script, which applies multiple regex patterns (e.g., *ABC* and *BCD*). If a match is found, the corresponding key is deleted using the DEL command.

This way, we efficiently process multiple patterns in a single database scan.

Analyzing time complexity

Assume Redis contains 1 million records, and a batch size of 1000 is used for each SCAN operation. Using the following formula:

Total Time (ms) = O((N × M × K) / Batch Size)

Where:

• N = Total number of records in the database (1 million)
• M = Number of regex patterns (1, as we’re not filtering by regex during the scan)
• K = Time per SCAN operation (500 ms)
• Batch Size = Number of records processed per SCAN (1000)

Substituting the values:

Total time = (1M * 1 * 500 ms ) / 1000 = 8 minutes

In this case, M is 1 because the data is fetched without applying any regex filtering. The external script applies the regex filtering later.

Time comparison

Conclusion

Efficient management of data deletion in Redis is crucial for maintaining optimal performance, cost-efficiency, and data integrity. Although Redis does not natively support deletion by pattern, combining strategies such as Lua scripting and external processing provides a powerful and effective solution.

Our approach integrates the strengths of Lua scripting for controlled, batch-wise scanning and external processing for complex regex-based deletions, addressing Redis's limitation with special characters in regex. This hybrid method minimizes Redis blocking, ensures high availability during the deletion process, and allows multiple patterns to be handled in a single iteration.

By adopting this strategy, Redis performance can be optimized, memory overhead reduced, and a clean, efficient dataset maintained—without disrupting other critical operations. With proper implementation and fine-tuning, this method strikes a balance between performance and operational efficiency, making it ideal for high-traffic environments with complex data deletion requirements.