Embedding vs referencing in Redis - Performance Comparison

Time Complexity: Embedding vs referencing

O(1) for embedding, O(n) for referencing

Understanding Time Complexity

When storing a list of related items (like post IDs) in Redis, we can either embed the list as a string in a hash field or store it in a separate set.

We want to see how the time to get data changes as the data grows.

Scenario Under Consideration

Analyze the time complexity of these Redis commands for embedding and referencing.

# Embedding: post IDs as string in hash field
HSET user:1 name "Alice" posts "post1,post2,post3"
# Fetch: O(1)
HGET user:1 posts

# Referencing: post IDs in separate set
HSET user:1 name "Alice"
SADD user:1:posts post1 post2 post3
# Fetch: O(N)
SMEMBERS user:1:posts
    

This code shows two ways to store and fetch a user's post list: embedded string vs set.

Identify Repeating Operations

Look at what repeats when fetching data.

• Primary operation: HGET for the posts field (embedding) vs SMEMBERS for the posts set (referencing).
• Time growth: Embedding is O(1). Referencing is O(N) where N is the number of posts.

How Execution Grows With Input

As the number of posts grows, the work changes differently for each method.

Input Size (posts)	Embedding	Referencing
10	O(1)	O(10)
100	O(1)	O(100)
1000	O(1)	O(1000)

Embedding stays constant because all data is fetched at once. Referencing grows linearly with the number of posts.

Final Time Complexity

Time Complexity: O(1) for embedding, O(N) for referencing

Embedding fetches all data in one step, while referencing requires more steps as data grows.

Common Mistake

[X] Wrong: "All single Redis commands are O(1)."

[OK] Correct: SMEMBERS requires time proportional to the set size O(N), unlike HGET which is O(1).

Interview Connect

Understanding how data structure choices affect speed helps you design better Redis solutions and explain your reasoning clearly.

Self-Check

"What if we used a Redis pipeline to fetch all referenced posts at once? How would that affect time complexity?"

Practice

1. Which statement best describes embedding in Redis?

easy

A. Storing related data together in one key.

B. Storing data in separate keys linked by IDs.

C. Using multiple databases for related data.

D. Storing only references without actual data.

Solution

1. Step 1: Understand embedding concept

   Embedding means putting related data inside one Redis key, so all data is together.

2. Step 2: Compare with referencing

   Referencing stores data separately and links them by IDs, which is different from embedding.

3. Final Answer:

   Storing related data together in one key. -> Option A

4. Quick Check:

   Embedding = data together [OK]

Hint: Embedding means one key holds all related data [OK]

Common Mistakes:

• Confusing embedding with referencing
• Thinking embedding uses multiple keys
• Assuming embedding stores only IDs

2. Which Redis data structure is best suited for embedding small related data together?

easy

A. Sorted Set

B. String

C. List

D. Hash

Solution

1. Step 1: Identify data structure for embedding

   Hashes store multiple fields and values inside one key, ideal for embedding related small data.

2. Step 2: Compare other structures

   Strings hold single values, Lists and Sorted Sets are for ordered collections, less suited for embedding small related fields.

3. Final Answer:

   Hash -> Option D

4. Quick Check:

   Embedding small data = Hash [OK]

Hint: Use Hash for embedding small related fields [OK]

Common Mistakes:

• Choosing String for multiple fields
• Confusing List with Hash
• Using Sorted Set without score relevance

3. Given these Redis commands:

HSET user:100 name "Alice" age 30
HSET user:100:address city "NY" zip 10001

Which describes the data design?

medium

A. Referencing address data in a separate key

B. Embedding all user data in one key

C. Using a List to store user info

D. Storing user data as a String

Solution

1. Step 1: Analyze keys and data

   user:100 holds name and age, user:100:address holds address fields separately.

2. Step 2: Identify design pattern

   Address is stored in a separate key linked by user ID, which is referencing.

3. Final Answer:

   Referencing address data in a separate key -> Option A

4. Quick Check:

   Separate keys linked by ID = referencing [OK]

Hint: Separate keys with related IDs mean referencing [OK]

Common Mistakes:

• Thinking all data is embedded in one key
• Confusing List with Hash usage
• Assuming address is embedded inside user key

4. You want to store user profiles with embedded address data in Redis using hashes. Which command has an error?

medium

A. HSET user:200 name "Bob" age 25

B. HSET user:200:address city "LA" zip 90001

C. HSET user:200 name "Bob" city "LA" zip 90001

D. HSET user:200 name "Bob" age 25 city "LA" zip 90001

Solution

1. Step 1: Check embedding address in user hash

   Embedding means all fields in one key, so address fields city and zip should be in user:200 hash.

2. Step 2: Identify error in command C

   Command C uses a separate key user:200:address, storing address separately linked by ID. This is referencing, not embedding.

3. Final Answer:

   HSET user:200:address city "LA" zip 90001 -> Option B

4. Quick Check:

   Separate keys = referencing, not embedding [OK]

Hint: Embedding: all data in ONE key, no sub-keys [OK]

Common Mistakes:

• Missing value for a field
• Using separate keys when embedding
• Mixing field-value pairs incorrectly

5. You have a Redis database storing product info. You want to optimize for fast reads of product details including reviews. Which design is best?

hard

A. Embed product details and all reviews in one hash key per product.

B. Store all reviews in a single list key for all products.

C. Store product details in one hash and each review in separate keys linked by product ID.

D. Store product details as strings and reviews as sorted sets.

Solution

1. Step 1: Consider data size and access pattern

   Reviews can be many and large, embedding all in one key can cause large data and slow updates.

2. Step 2: Choose referencing for scalability

   Storing product details separately and reviews in linked keys allows efficient updates and reads without large keys.

3. Step 3: Evaluate other options

   Embedding all reviews in one hash risks large keys; storing all reviews in a single list key for all products mixes products; storing product details as strings and reviews as sorted sets don't fit review structure well.

4. Final Answer:

   Store product details in one hash and each review in separate keys linked by product ID. -> Option C

5. Quick Check:

   Large related data = referencing for performance [OK]

Hint: Large or many related items? Use referencing [OK]

Common Mistakes:

• Embedding large lists causing slow reads
• Mixing all reviews in one key
• Ignoring update frequency of reviews