How Redis achieves sub-millisecond latency - Performance & Efficiency

Time Complexity: How Redis achieves sub-millisecond latency

O(1)

Understanding Time Complexity

We want to understand how Redis keeps its response times very fast, often under a millisecond.

How does Redis handle commands so quickly even as data grows?

Scenario Under Consideration

Analyze the time complexity of a simple Redis GET command.

GET user:1000
    

This command fetches the value stored at the key "user:1000" from Redis.

Identify Repeating Operations

Redis uses a hash table to store keys and values.

• Primary operation: Hash table lookup for the key.
• How many times: Exactly once per GET command.

How Execution Grows With Input

The time to find a key depends on how many keys are stored, but Redis uses efficient hashing.

Input Size (n)	Approx. Operations
10	About 1 lookup
100	About 1 lookup
1000	About 1 lookup

Pattern observation: The lookup time stays almost the same even as more keys are added.

Final Time Complexity

Time Complexity: O(1)

This means Redis finds the key in constant time, no matter how many keys there are.

Common Mistake

[X] Wrong: "Redis slows down a lot as the database grows because it has to check every key."

[OK] Correct: Redis uses a hash table that lets it jump directly to the key without checking all others.

Interview Connect

Knowing how Redis achieves fast lookups shows you understand efficient data access, a key skill in many database and system design questions.

Self-Check

"What if Redis used a simple list instead of a hash table? How would the time complexity change?"