Maxmemory setting in Redis - Time & Space Complexity

Time Complexity: Maxmemory setting

O(1)

Understanding Time Complexity

When Redis reaches its memory limit, it uses the maxmemory setting to decide what to do next.

We want to understand the time complexity of memory management as data size increases.

Scenario Under Consideration

Analyze the time complexity of Redis handling maxmemory eviction with the allkeys-lru policy.

CONFIG SET maxmemory 100mb
CONFIG SET maxmemory-policy allkeys-lru
SET key1 value1
SET key2 value2
...
SET keyN valueN
    

This code sets a memory limit and an eviction policy that removes least recently used keys when memory is full.

Identify Repeating Operations

Redis samples a small, fixed number of keys to approximate the least recently used key for eviction.

• Primary operation: Sampling and evaluating a fixed number of keys for LRU approximation.
• How many times: A constant number of samples (default 5), independent of total keys.

How Execution Grows With Input

As the number of keys grows, Redis still samples the same fixed number of keys, keeping eviction time constant.

Input Size (n)	Approx. Operations
10	Sample fixed # (e.g., 5) keys
100	Sample fixed # (e.g., 5) keys
1000	Sample fixed # (e.g., 5) keys

Pattern observation: The time to find a key to evict is constant regardless of the number of keys.

Final Time Complexity

Time Complexity: O(1)

This means the time to find a key to evict is constant, independent of the number of keys stored.

Common Mistake

[X] Wrong: "Redis scans all keys linearly to find the LRU key."

[OK] Correct: Redis uses sampling of a fixed small number of keys for approximation, keeping it O(1).

Interview Connect

Understanding how Redis manages memory helps you explain real-world system behavior and performance under load.

Self-Check

"What if we changed the eviction policy from allkeys-lru to noeviction? How would the time complexity change?"

Practice

1. What does the maxmemory setting in Redis control?

easy

A. The maximum amount of memory Redis can use

B. The maximum number of clients connected

C. The maximum size of a single key

D. The maximum number of commands per second

Solution

1. Step 1: Understand the purpose of maxmemory

   The maxmemory setting limits how much memory Redis can use to avoid overloading the server.

2. Step 2: Compare options with this purpose

   Only the maximum amount of memory Redis can use matches this description, others relate to clients, keys, or commands, which are unrelated.

3. Final Answer:

   The maximum amount of memory Redis can use -> Option A

4. Quick Check:

   maxmemory limits Redis memory use [OK]

Hint: maxmemory always limits Redis memory size [OK]

Common Mistakes:

• Confusing maxmemory with client limits
• Thinking maxmemory limits key size
• Assuming maxmemory limits command rate

2. Which of the following is the correct syntax to set maxmemory to 512 megabytes using CONFIG SET in Redis?

easy

A. CONFIG SET maxmemory 512mb

B. CONFIG SET maxmemory 512MB

C. CONFIG SET maxmemory 512m

D. CONFIG SET maxmemory 512

Solution

1. Step 1: Recall Redis size suffix format

   Redis accepts size suffixes like KB, MB, GB in uppercase for memory settings.

2. Step 2: Check each option's suffix

   CONFIG SET maxmemory 512MB uses 'MB' uppercase which is correct; CONFIG SET maxmemory 512mb uses lowercase 'mb' which is invalid; CONFIG SET maxmemory 512m uses 'm' which is not recognized; CONFIG SET maxmemory 512 has no suffix, so it's bytes, not megabytes.

3. Final Answer:

   CONFIG SET maxmemory 512MB -> Option B

4. Quick Check:

   Use uppercase suffixes like MB for megabytes [OK]

Hint: Use uppercase suffixes like MB, GB for sizes [OK]

Common Mistakes:

• Using lowercase suffixes like mb
• Using incomplete suffix like m
• Omitting suffix and expecting megabytes

3. Given the command CONFIG SET maxmemory 1GB executed on a Redis server, what will be the effect?

medium

A. Redis will limit its memory usage to 1 gigabyte

B. Redis will allow unlimited memory usage

C. Redis will limit memory to 1 byte

D. Redis will throw a syntax error

Solution

1. Step 1: Interpret the command meaning

   The command sets maxmemory to 1GB, meaning Redis should limit memory use to 1 gigabyte.

2. Step 2: Validate the command syntax and effect

   The syntax is correct and Redis supports 'GB' suffix, so it will enforce the memory limit.

3. Final Answer:

   Redis will limit its memory usage to 1 gigabyte -> Option A

4. Quick Check:

   CONFIG SET maxmemory 1GB limits memory to 1GB [OK]

Hint: CONFIG SET maxmemory with GB limits memory to gigabytes [OK]

Common Mistakes:

• Thinking it sets unlimited memory
• Confusing bytes with gigabytes
• Expecting syntax error from correct command

4. You run CONFIG SET maxmemory 100mb on Redis but it returns an error. What is the likely cause?

medium

A. Redis does not support changing maxmemory at runtime

B. maxmemory must be set in bytes only, no suffix allowed

C. The value 100mb is too large for Redis

D. The suffix 'mb' is lowercase and invalid

Solution

1. Step 1: Check Redis suffix case sensitivity

   Redis requires uppercase suffixes like MB, GB for memory sizes.

2. Step 2: Analyze the error cause

   Using lowercase 'mb' causes syntax error; changing to 'MB' fixes it.

3. Final Answer:

   The suffix 'mb' is lowercase and invalid -> Option D

4. Quick Check:

   Use uppercase suffixes for memory sizes [OK]

Hint: Always use uppercase suffixes like MB, GB [OK]

Common Mistakes:

• Assuming maxmemory can't be changed at runtime
• Using lowercase suffix causing errors
• Thinking maxmemory only accepts bytes

5. You want Redis to use at most 2 gigabytes of memory and automatically evict keys when the limit is reached. Which two commands should you run?

hard

A. CONFIG SET maxmemory 2gb and CONFIG SET maxmemory-policy allkeys-random

B. CONFIG SET maxmemory 2GB and CONFIG SET maxmemory-policy noeviction

C. CONFIG SET maxmemory 2GB and CONFIG SET maxmemory-policy allkeys-lru

D. CONFIG SET maxmemory 2048 and CONFIG SET maxmemory-policy volatile-lru

Solution

1. Step 1: Set maxmemory to 2 gigabytes correctly

   Use CONFIG SET maxmemory 2GB with uppercase suffix for 2 gigabytes.

2. Step 2: Choose eviction policy that evicts keys automatically

   allkeys-lru evicts least recently used keys from all keys, enabling automatic eviction.

3. Step 3: Verify other options

   Lowercase '2gb' with allkeys-random uses invalid suffix and random eviction; 2GB with noeviction disables eviction; 2048 (bytes, not GB) with volatile-lru limits to tiny memory and only evicts expiring keys.

4. Final Answer:

   CONFIG SET maxmemory 2GB and CONFIG SET maxmemory-policy allkeys-lru -> Option C

5. Quick Check:

   Set maxmemory + allkeys-lru for eviction [OK]

Hint: Use uppercase GB and allkeys-lru for eviction [OK]

Common Mistakes:

• Using lowercase suffix like '2gb'
• Choosing noeviction policy
• Setting maxmemory without suffix
• Using volatile-lru when all keys need eviction