Out-of-Order Event Handling

In daily basis, huge amount of data is being processed regardless of field. Both batch and real time processing happens with huge amount data. Bank transactions, data from sensors, share market, live activities(online commentary, video streaming) everything includes data processing. Batch processing requires separate programs for input, process and output. (example is payroll and billing systems) while real time data processing involves a continual input, process and output of data. Data will be processed in a small time period — real time.

While all these processes, we may face some problems such as loss of events, duplication of events and out-of-order of events. Due to network failures, restarting of a node/ source in the middle of the process, these problems may occur.

What is Out-of-Order Events??

Events are generated from respective sources will be tagged with a time stamp at which they were created. When they are received by a Stream processor they may not be in the order which they have been created. This may happen due to several reasons — mainly latency. There are various reasons for the latency. Due to underlying hardware (e.g. slower CPU, RAM, NIC, or HDDs), system mandated middle-ware (Databases, messaging buses, networking protocols).

Scenario — 1

When you look at the example scenario mentioned above, Events A, B, C are emitted from an application in the order of A, B, C. But when they traveled through a transport, due network delays event A is delayed by 10 s and B delayed by 2 s and C delayed by 1 s. Since the time gap between A and B is only 5 s and A delayed by 10 s, A will be received after 3 s upon B received by the receiver. Here event disorder occurs.

In Distributed systems, we do some processes in parallel and then merge the output from them into one stream for further processing. In those instances, we face out-of-order of events.

Sample Distributed System

In the above figure, you can observe that, when we merge the output from all 4 filters to get the output Stream, then in the Output stream, events will be shuffled. Why? we can’t guarantee which filter will get which event and what time it will generate output.

Why Disorder handling is important??

If we are taking decisions based on the observations made on the pattern of event data occurrences, then order-of -events is very crucial.

Lets consider a practical example

In debit card/ credit card transaction, in order to find the fraud usage, systems observe the pattern in the transaction. When a small transaction taken place and within some time, if another large transaction takes place immediately, there is a major chance of having fraud usage. If events are received in out-of-order, there won’t be required pattern observed even if fraud transactions happened.

If we are using heat sensors to observe the changes in the temperature at a given place. If events are received by a central system and results are formed according to that. If events are not received in order, then we can’t get the correct results — how temperature changes(pattern).

So in most of the cases, the order of events are very important and they play a major role in taking decisions and react to it.

How to handle it??

You can refer this blog post regarding the out-of-order in single processing system. You can see that there are 4 main methods described. They are :

  1. Buffer based approach

2. Punctuation based approach

3. Speculation based approach

4. Approximation based approach

Check out Buffer based Approach here :

We will talk about the techniques that can be used for solving out-of-order event scenario in Distributed Systems in next blog