Data lake design patterns in Hadoop - Time & Space Complexity

Time Complexity: Data lake design patterns

O(n)

Understanding Time Complexity

When working with data lakes, it is important to understand how the time to process data grows as the data size increases.

We want to know how the design pattern affects the speed of data processing in Hadoop.

Scenario Under Consideration

Analyze the time complexity of the following Hadoop MapReduce job using a data lake design pattern.

// Mapper reads data from raw zone
map(key, value) {
  // parse and filter records
  if (record is valid) {
    emit(key, value);
  }
}

// Reducer aggregates filtered data
reduce(key, values) {
  sum = 0;
  for each v in values {
    sum += v;
  }
  emit(key, sum);
}
    

This code reads raw data, filters it, and then aggregates results in the reduce step.

Identify Repeating Operations

Look at the loops and repeated steps in the code.

• Primary operation: The reducer loops over all values for each key to sum them.
• How many times: The reducer runs once per unique key, processing all associated values.

How Execution Grows With Input

As the input data grows, the number of records to process grows too.

Input Size (n)	Approx. Operations
10	About 10 map operations and sums over small groups
100	About 100 map operations and sums over larger groups
1000	About 1000 map operations and sums over even larger groups

Pattern observation: The total work grows roughly in direct proportion to the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to process data grows linearly as the data size increases.

Common Mistake

[X] Wrong: "The reducer runs a fixed number of times regardless of data size."

[OK] Correct: The reducer runs once per unique key, so if data grows with more keys or values, the reducer work grows too.

Interview Connect

Understanding how data lake design patterns affect processing time helps you explain how to handle big data efficiently in Hadoop.

Self-Check

"What if we added a combiner step before the reducer? How would the time complexity change?"

Practice

1. What is the main purpose of organizing data into zones like raw, processed, and curated in a data lake?

easy

A. To increase the size of the data lake

B. To keep data clean, easy to find, and ready for analysis

C. To make data harder to access

D. To reduce the number of users accessing data

Solution

1. Step 1: Understand the role of data zones

   Raw, processed, and curated zones help organize data by its state and quality.

2. Step 2: Identify the benefit of this organization

   This organization keeps data clean, easy to find, and ready for analysis.

3. Final Answer:

   To keep data clean, easy to find, and ready for analysis -> Option B

4. Quick Check:

   Data zones improve data usability = A [OK]

Hint: Think about why clean data helps analysis fast [OK]

Common Mistakes:

• Confusing size increase with organization benefits
• Assuming data zones restrict access
• Thinking zones reduce user numbers

2. Which of the following is the correct way to represent the 'raw' data zone in Hadoop folder structure?

easy

A. /data/curated/

B. /data/processed/

C. /data/raw/

D. /data/analytics/

Solution

1. Step 1: Recall standard folder naming for data zones

   The raw data zone is usually stored in a folder named 'raw' to indicate unprocessed data.

2. Step 2: Match folder names to zones

   /data/raw/ matches the raw data zone, while others represent different zones or purposes.

3. Final Answer:

   /data/raw/ -> Option C

4. Quick Check:

   Raw data folder = /data/raw/ [OK]

Hint: Raw data folder always named 'raw' [OK]

Common Mistakes:

• Choosing processed or curated folder names for raw data
• Using unrelated folder names like analytics
• Confusing folder names with data types

3. Given the following Hadoop folder structure:

/data/raw/sales.csv
/data/processed/sales_clean.csv
/data/curated/sales_summary.csv

Which file would most likely contain cleaned and transformed sales data ready for analysis?

medium

A. /data/processed/sales_clean.csv

B. /data/raw/sales_summary.csv

C. /data/curated/sales_summary.csv

D. /data/raw/sales.csv

Solution

1. Step 1: Understand the meaning of each zone

   Raw zone has original data, processed zone has cleaned/transformed data, curated zone has aggregated or summarized data.

2. Step 2: Identify the file with cleaned and transformed data

   /data/processed/sales_clean.csv indicates cleaned sales data ready for further use.

3. Final Answer:

   /data/processed/sales_clean.csv -> Option A

4. Quick Check:

   Processed zone = cleaned data = D [OK]

Hint: Processed folder means cleaned and transformed data [OK]

Common Mistakes:

• Choosing raw data file as cleaned data
• Confusing curated summary with cleaned data
• Selecting non-existent file paths

4. You have a data lake with folders: /data/raw/, /data/processed/, and /data/curated/. You accidentally saved uncleaned data in /data/curated/. What is the best fix?

medium

A. Move the uncleaned data to /data/raw/ and reprocess it

B. Leave the data as is in /data/curated/

C. Delete the /data/raw/ folder

D. Rename /data/curated/ to /data/raw/

Solution

1. Step 1: Identify the problem with data placement

   Uncleaned data should not be in the curated zone, which is for clean, ready data.

2. Step 2: Choose the correct fix

   Moving uncleaned data back to raw zone and reprocessing it ensures proper data flow and quality.

3. Final Answer:

   Move the uncleaned data to /data/raw/ and reprocess it -> Option A

4. Quick Check:

   Raw zone = uncleaned data fix = B [OK]

Hint: Unclean data belongs in raw zone, not curated [OK]

Common Mistakes:

• Ignoring data quality rules
• Deleting unrelated folders
• Renaming folders without moving data

5. You want to design a data lake in Hadoop that supports fast analytics and easy data governance. Which design pattern should you follow?

hard

A. Store all data in a single folder without zones

B. Keep only raw data and process it on-demand

C. Use random folder names for each data type

D. Organize data into raw, processed, and curated zones with clear folder structures

Solution

1. Step 1: Understand the goal of fast analytics and governance

   Fast analytics needs clean, organized data; governance needs clear structure and control.

2. Step 2: Identify the best design pattern

   Organizing data into raw, processed, and curated zones with clear folders supports both goals effectively.

3. Final Answer:

   Organize data into raw, processed, and curated zones with clear folder structures -> Option D

4. Quick Check:

   Zones + clear folders = fast analytics + governance = C [OK]

Hint: Zones and clear folders improve analytics and governance [OK]

Common Mistakes:

• Storing all data together causing confusion
• Processing data only on-demand slowing queries
• Using unclear folder names causing management issues