Watermarking for late data in Apache Spark - Time & Space Complexity

Time Complexity: Watermarking for late data

O(n)

Understanding Time Complexity

We want to understand how the time to process streaming data changes when we use watermarking for late data.

Specifically, how does handling late data affect the work Spark does as data grows?

Scenario Under Consideration

Analyze the time complexity of the following Apache Spark Structured Streaming code snippet.

streamingDF
  .withWatermark("eventTime", "10 minutes")
  .groupBy(window(col("eventTime"), "5 minutes"), col("category"))
  .count()

This code groups streaming data by time windows and category, using a watermark to handle late data up to 10 minutes late.

Identify Repeating Operations

Look at what repeats as new data arrives:

• Primary operation: Grouping data by time windows and categories repeatedly for each batch.
• How many times: Once per micro-batch, processing all new data plus any late data within watermark.

How Execution Grows With Input

As more data arrives, Spark processes more rows each batch, including late data within the watermark.

Input Size (n)	Approx. Operations
10	Processes about 10 rows per batch
100	Processes about 100 rows per batch
1000	Processes about 1000 rows per batch

Pattern observation: The work grows roughly linearly with the number of rows processed each batch, including late data within the watermark.

Final Time Complexity

Time Complexity: O(n)

This means the processing time grows roughly in direct proportion to the number of rows Spark processes each batch.

Common Mistake

[X] Wrong: "Watermarking makes processing time constant no matter how much data arrives."

[OK] Correct: Watermarking limits how long late data is kept, but Spark still processes all data within that window, so time grows with data size.

Interview Connect

Understanding how watermarking affects processing time helps you explain how streaming systems handle late data efficiently while scaling with input size.

Self-Check

What if we increased the watermark delay from 10 minutes to 1 hour? How would the time complexity change?

Practice

1. What is the main purpose of watermarking in Apache Spark streaming?

easy

A. To handle late data by setting a threshold time for event processing

B. To speed up the streaming job by skipping data

C. To permanently store all incoming data

D. To convert batch data into streaming data

Solution

1. Step 1: Understand watermarking concept

   Watermarking sets a time limit to wait for late data in streaming.

2. Step 2: Identify purpose in streaming

   It helps to ignore data that arrives too late to keep results timely.

3. Final Answer:

   To handle late data by setting a threshold time for event processing -> Option A

4. Quick Check:

   Watermarking = handle late data [OK]

Hint: Watermarking sets max wait time for late events [OK]

Common Mistakes:

• Thinking watermark speeds up jobs by skipping all data
• Confusing watermark with data storage
• Assuming watermark converts batch to streaming

2. Which of the following is the correct syntax to add a watermark on a streaming DataFrame df with event time column eventTime and delay threshold of 10 minutes?

easy

A. df.withWatermark(eventTime, 10)

B. df.withWatermark("eventTime", "10 minutes")

C. df.watermark("eventTime", 10)

D. df.withWatermark("eventTime", 10)

Solution

1. Step 1: Recall correct method signature

   The method is withWatermark with two string arguments: column name and delay duration.

2. Step 2: Match correct syntax

   df.withWatermark("eventTime", "10 minutes") uses correct method and string format for delay "10 minutes".

3. Final Answer:

   df.withWatermark("eventTime", "10 minutes") -> Option B

4. Quick Check:

   Correct syntax uses strings for both args [OK]

Hint: Use strings for column and delay in withWatermark() [OK]

Common Mistakes:

• Passing column name without quotes
• Using integer instead of string for delay
• Using wrong method name like watermark()

3. Given the following Spark Structured Streaming code snippet, what will be the output schema's watermark column after applying watermark?

val streamingDF = spark.readStream.format("csv")
  .option("header", "true")
  .load("/data/events")

val withWatermarkDF = streamingDF.withWatermark("eventTime", "5 minutes")
withWatermarkDF.printSchema()

medium

A. eventTime: timestamp (nullable = true) with watermark

B. eventTime: string (nullable = true) with watermark

C. eventTime: timestamp (nullable = false) without watermark

D. No watermark added to schema

Solution

1. Step 1: Understand watermark effect on schema

   Watermark adds metadata to the event time column, which must be timestamp type.

2. Step 2: Check expected schema output

   Schema shows eventTime as timestamp with watermark metadata.

3. Final Answer:

   eventTime: timestamp (nullable = true) with watermark -> Option A

4. Quick Check:

   Watermark adds metadata to timestamp column [OK]

Hint: Watermark adds metadata to timestamp event column [OK]

Common Mistakes:

• Assuming eventTime remains string type
• Thinking watermark changes nullability
• Believing watermark does not affect schema

4. Identify the error in the following Spark Structured Streaming code that uses watermarking:

val df = spark.readStream.format("json")
  .load("/stream/data")

val result = df.withWatermark("timestamp", "1 minute")
  .groupBy(window(col("timestamp"), "30 seconds"))
  .count()

medium

A. withWatermark must be called after groupBy

B. Column name "timestamp" should be "eventTime"

C. Window duration cannot be "30 seconds"

D. Watermark delay must be shorter than window duration

Solution

1. Step 1: Check watermark and window durations

   Watermark delay must be shorter than window duration to ensure the query emits results.

2. Step 2: Compare durations in code

   Watermark is 1 minute but window is 30 seconds, watermark delay longer than window duration and causes error.

3. Final Answer:

   Watermark delay must be shorter than window duration -> Option D

4. Quick Check:

   Watermark < window duration [OK]

Hint: Watermark delay must be < window duration [OK]

Common Mistakes:

• Assuming any column name works
• Thinking window duration cannot be "30 seconds"
• Calling withWatermark after groupBy

5. You have a streaming dataset with event times and want to aggregate counts per 10-minute window. Late data can arrive up to 15 minutes late. Which watermark delay should you set to ensure correct results without excessive delay?

hard

A. "25 minutes"

B. "10 minutes"

C. "15 minutes"

D. "5 minutes"

Solution

1. Step 1: Understand watermark delay role

   Watermark delay should cover the maximum expected lateness of data to include late events.

2. Step 2: Match delay to late data arrival

   Since late data can arrive up to 15 minutes late, watermark delay must be at least 15 minutes.

3. Step 3: Avoid setting delay too short or too long

   Setting delay less than 15 minutes risks dropping late data; too long delays output.

4. Final Answer:

   "15 minutes" -> Option C

5. Quick Check:

   Watermark delay = max late arrival [OK]

Hint: Set watermark delay to max expected late arrival [OK]

Common Mistakes:

• Setting delay equal to window size instead of late arrival
• Using shorter delay than late data time
• Using unnecessarily long delay causing latency