Introduction to Stream
Computing
Module 2
Introduction to Stream Concepts
A data stream is: A continuous, unbounded sequence of data records generated over time.
streams are:
● Continuous
● Infinite (unbounded)
● Time-ordered
● Generated in real-time
Examples of Streaming Data:
● Sensor data (IoT devices)
● Stock market transactions
● Server logs
● Social media feeds
● GPS tracking data
● Online banking transactions
Stream Processing Architecture
Characteristics:
● Continuous
● High velocity
● Timestamped events
● Structured / Semi-structured /
Unstructured
Stream Processing Architecture
acts as a buffer, distributor, and traffic controller between: Data Producers → Stream Processing Engine
Data Ingestion is the process of: When implemented using a Message Broker, it ensures:
● Collecting data from multiple producers ● Reliability
● Receiving it continuously ● Scalability
● Temporarily storing it ● Fault tolerance
● Distributing it to consumers (processing engines) ● Decoupling of systems
Stream Processing Architecture
A Stream Processing Engine is a distributed system that:
Processes unbounded, continuous data streams in real time.
Unlike batch engines (MapReduce), it processes data as it arrives.
Stream Processing Engine Architecture
Stream Processing Engine Architecture
1. Input Receiver Responsibilities:
Purpose: ● Event parsing
● Schema validation
● Accepts incoming events. ● Timestamp assignment
● Deserialization
● Converts raw input into structured records.
Converted to:
Raw input: {
user_id: 101,
101,5000,10:05
amount: 5000,
timestamp: 10:05
}
Stream Processing Engine Architecture
2. Stream Buffer / Queue
Purpose:
● Temporarily stores incoming events.
● Ensures smooth processing. Suppose 10,000 transactions arrive in 1 second.
This helps in:
The buffer:
● Handling burst traffic
● Holds them in queue.
● Managing backpressure
● Sends them gradually to processing layer.
Stream Processing Engine Architecture
3. Processing Layer (Core Engine) Types of operations:
A) Filter
1 Transformation
● Map (modify data) Check transactions > ₹10,000
● Filter (remove unwanted records)
B) Transformation
2 Aggregation
Convert currency if needed.
● Count
● Sum C) Aggregation
● Average
● Min/Max
Count transactions per user.
3 Pattern Detection
Example:
● Sequence detection
● Complex event processing Transaction = ₹25,000
Rule: If amount > ₹10,000 → mark as "High Value"
4 Enrichment
● Join stream with reference data
Stream Processing Engine Architecture
4. Stateful Processing Unit User 101 made:
Stateless Processing: ● ₹25,000 at 10:05
Each event processed independently.
● ₹30,000 at 10:07
Stateful Processing:
● ₹40,000 at 10:09
System remembers previous data.
State can include: Rule:
● Counters
If 3 high-value transactions within 10 minutes → suspicious.
● Lists
To detect this, system must remember previous transactions.
● User sessions
That memory = State
● Partial aggregations
Stream Processing Engine Architecture
5. Window Manager
Since streams are infinite, we divide data into finite chunks called windows. Window size = 10 minutes
Types of Windows: It groups transactions between:
1 Tumbling Window 10:00 – 10:10
10:10 – 10:20
Fixed size, no overlap. 3 Session Window
Example: For user 101:
Based on inactivity gap.
Every 5 minutes. All 3 transactions fall into same
Example: 10-minute window → trigger alert.
2 Sliding Window If no activity for 30 minutes → session ends.
Fixed size, overlapping.
Example:
10-minute window sliding every 5 minutes.
Stream Processing Engine Architecture
6. Time Management Unit
There are three time concepts:
1 Event Time
When event actually occurred.
Transaction happened at 10:05
2 Processing Time But due to network delay, it arrives at 10:07.
When system processes it.
Engine must use Event Time, not arrival time.
3 Ingestion Time
When event entered system.
The engine must handle:
● Late arrivals
● Out-of-order events
Stream Processing Engine Architecture
7. State Management System
State must be stored reliably.
Functions:
● Store intermediate results
System saved:
● Recover after failure
User 101 → 2 high-value transactions so far
● Maintain consistency
If crash happens:
System reloads state and continues correctly.
Stream Processing Engine Architecture
8. Fault Tolerance Mechanism
Streaming systems must never lose data.
Techniques used: Power failure at 10:08 AM.
1 Checkpointing System restarts:
Save system state at intervals. ● Reloads last checkpoint
2 Replay Mechanism
● Reprocesses missing events
Reprocess data from last safe point.
● No transaction is lost
3 Replication
Multiple copies of state.
Stream Processing Engine Architecture
9. Parallelism and Scalability When users = 1 million:
To handle large data: One processor cannot handle all transactions.
● Stream divided into partitions.
Solution:
● Each partition processed independently.
● Divide users into partitions.
● Tasks run in parallel.
● Each partition processed independently.
This enables:
● Horizontal scaling Example:
● High throughput ● Processor 1 → Users 1–10000
● Low latency
● Processor 2 → Users 10001–20000
Stream Processing Engine Architecture
10. Output Emitter
After processing, results are: Alert message:
● Sent to storage ⚠ Suspicious Activity Detected
● Sent to dashboards
User: 101
3 high-value transactions in 10 minutes
● Used to trigger alerts
Sent to:
● Forwarded to another system
● Bank dashboard
● SMS alert system
● Risk management system
Stream Data Model
A stream is:
An unbounded, ordered sequence of immutable events generated over time.
S = { e1, e2, e3, e4, ... }
Where:
● S = Stream Event = <Key, Value, Timestamp>
● e = Event Key → user_id (used for partitioning)
Value → transaction details
● Infinite in nature {
Timestamp → when event occurred "user_id": 101,
● Ordered by time "amount": 25000,
"location": "Kochi",
"timestamp": "10:05:00"
}
Sampling in Stream Processing
Sampling means:
Selecting a small representative subset of the stream to approximate
results efficiently.
Instead of processing 1,000,000 events per second, we process maybe 10,000
and still get good insights.
Sampling Techniques in Stream Processing
Reservoir Sampling:
It allows to maintain a truly random sample of size k from a stream of data where the
total number of items (n) is unknown or infinite.
Let:
● k = size of sample
● i = current position in stream
Step 1: Store first k elements in reservoir.
Step 2: For each new element at position i (i > k):
1. Generate random number r between 1 and i.
2. If r ≤ k:
Replace r-th element in reservoir.
3. Else:
Ignore element.
Reservoir Sampling:
Stream:
10, 20, 30, 40, 50, 60
Let k = 3.
Initial reservoir:
[10, 20, 30]
Now element = 40 (i = 4)
Random r between 1–4.
Suppose r = 2.
Replace position 2:
[10, 40, 30]
Bernoulli Sampling
Each element is independently selected with probability p.
Algorithm
For each incoming element:
1. Generate random number between 0 and 1.
2. If random number < p → select. Let p = 0.2
3. Else → discard.
Stream: 1,2,3,4,5,6,7,8,9,10
Each element has 20% chance of being selected.
Possible sample: 2,7,9
Systematic Sampling
Select every k-th element.
If sampling interval = k:
Stream:
Select elements where:
1,2,3,4,5,6,7,8,9,10
i % k == 0 k=3
Selected:
3,6,9
Stratified Sampling
Ensure representation of different categories.
Used when stream has groups.
Transactions by city: Delhi, Delhi, Kochi, Mumbai, Kochi, Kochi
If simple random sampling used,
Delhi may dominate sample.
Steps
So: 1. Partition stream by key.
1. Divide into groups (strata). 2. Apply sampling within each partition.
2. Sample proportionally from each group.
Weighted Sampling
Give higher selection probability to important elements.
In fraud detection:
Transaction = ₹100 → low importance
Transaction = ₹1,00,000 → high importance
Assign weight proportional to amount.
Higher weight → higher chance of selection.
Priority Sampling
Each element assigned a random priority score.
Keep only top-k elements with highest priority.
Transaction amounts: 5000, 25000, 100000, 2000
Assign priority:
5000 → 0.32
25000 → 0.75
100000 → 0.91
2000 → 0.12
Keep highest k priorities.
Sliding Window Sampling
Instead of sampling entire stream,
Sample only recent window.
Last 5 minutes of transactions only.
Apply:
● Reservoir sampling within window.
Useful for:
● Real-time monitoring
● Trend analysis
Adaptive Sampling
Sampling rate changes dynamically based on system load.
Example:
If CPU > 80% → reduce sampling rate.
If CPU < 40% → increase sampling rate.
Used in:
● Large-scale monitoring systems
● Cloud environments
Filtering streams – Bloom filter
A space-efficient probabilistic data structure used to test whether an element is a
member of a set.
It answers:
“Element may be present”
“Element is definitely not present”
Filtering streams – Bloom filter
When inserting an element: Bit array size = 5
1. Pass element through k hash functions. Hash functions:
2. Each hash outputs an index in bit array.
● h₁(x) = x mod 5
3. Set those positions to 1.
Index: 0 1 2 3 4
● h₂(x) = (2x + 3) mod 5 Value: 0 0 0 0 0
When checking an element: ● h₃(x) = (3x + 1) mod 5
1. Hash it using same k functions.
2. Check those positions.
3. If any position = 0 → definitely NOT present.
4. If all positions = 1 → MAYBE present.
Filtering streams – Bloom filter
Insert x = 7 Check x = 4
Compute hashes: Compute hashes:
h₁(7) = 7 mod 5 = 2 h₁(4) = 4 mod 5 = 4
h₂(7) = (2×7 + 3) mod 5 = (14 + 3) mod 5 = 17 mod 5 = 2 h₂(4) = (2×4 + 3) mod 5 = (8 + 3) mod 5 = 11 mod 5 = 1
h₃(7) = (3×7 + 1) mod 5 = (21 + 1) mod 5 = 22 mod 5 = 2 h₃(4) = (3×4 + 1) mod 5 = (12 + 1) mod 5 = 13 mod 5 = 3
All hashes = 2 Check positions:
Set index 2 to 1: Index 4 → 0
Index 1 → 0
Index: 0 1 2 3 4 Index 3 → 0
Value: 0 0 1 0 0
Since at least one position is 0,
4 is definitely NOT present
Filtering streams – Bloom filter
Check x = 17
Compute hashes:
h₁(17) = 17 mod 5 = 2
h₂(17) = (2×17 + 3) mod 5 = (34 + 3) mod 5 = 37 mod 5 = 2
h₃(17) = (3×17 + 1) mod 5 = (51 + 1) mod 5 = 52 mod 5 = 2
Check position 2:
Index 2 → 1
All required positions are 1.
So Bloom filter says:
17 MAY BE present
But we never inserted 17.
This is a false positive.
Count distinct problem - Flajolet martin algorithm
Stream: A, B, A, C, B, D, E, D
Distinct elements = {A, B, C, D, E}
Answer = 5
Flajolet–Martin (FM) Algorithm - is a probabilistic algorithm used to estimate the number of distinct elements using very small
memory.
Step 1: Choose a Hash Function [ h(x) ]
Step 2: For Each Element in Stream
1. Compute hash value.
2. Convert to binary.
3. Count number of trailing zeros.
4. Keep track of maximum trailing zeros seen (R).
Step 3: Estimate Distinct Count
Estimated Count=2REstimated\ Count = 2^REstimated Count=2R
Count distinct problem - Flajolet martin algorithm
h(x)=(3x+1)mod5
Suppose the stream is: 1, 2, 3, 4, 2, 1, 5
x Hash Binary Trailing Zeros
Maximum trailing zeros: R=2
1 4 100 2
2 2 010 1 Flajolet–Martin estimate:
3 0 000 0 Estimated Count= 2^R
= 2^2 = 4
4 3 011 0
5 1 001 0
Counting oneness in a window – DGIM algorithm
DGIM stands for:
● Datar
● Gionis
● Indyk
● Motwani
It estimates:
Number of 1s in the last N bits of a binary stream.
Instead of storing every bit, DGIM groups the 1s into buckets. Each bucket tracks:
1. The timestamp of its most recent 1.
2. The size (the number of 1s it contains), which must be a power of 2 (1, 2, 4, 8, ).
Counting oneness in a window – DGIM algorithm
Rule 1: Only 1s Are Stored
Rule 2: Each Bucket Represents a Power of 2 - 1,2,4,8,16,…
Rule 3: Each Bucket Stores Two Things -
1 Size (number of 1s in it)
2 Timestamp of most recent 1 in that bucket
Rule 4: At Most Two Buckets of Same Size
Rule 5: If Three Buckets of Same Size Appear → Merge Oldest Two
Rule 6: Delete Buckets Outside the Window
Counting oneness in a window – DGIM algorithm
Case 1: When a 0 is Added
Rule:
Do nothing (except slide the window).
DGIM stores only 1s, so:
● No bucket is created.
● No merging happens.
● Only old buckets may expire if outside window.
Counting oneness in a window – DGIM algorithm
Case 2: When a 1 is Added
Step 1: Create New Bucket
Step 2: Check Rule of At Most Two Buckets