Support out-of-order event processing

[taegeonum]

Current Design of MIST

• A query is partitioned to multiple partitioned queries
• Each partitioned query has a queue
• Each queue contains tasks of the partitioned query
  • E.g) A task consists of chained operators and an input
• A processing thread picks a partitioned query, polls a task from the queue and runs the task.
• When the thread is processing the task, other threads cannot poll next task from the queue until the thread finishes the processing task. We block the queue until the polled task is finished.
  • Why? Because we suppose that the data stream generates in-order events, so, in order to guarantee in-order events processing.
  • But, we need to do reordering when two streams are unioned, if we guarantee in-order processing
  • What if the data stream generates out-of-order events?
  • We need to do reordering the events in source with watermark

Problem

• If users do not need in-order processing or the operators are stateless, event reordering and blocking the queue is unnecessary.This just generates additional overhead.

Goal

• Support out-of-order event processing in addition to in-order event processing

New Design

• Do not block task processing from the queue if unnecessary. Reorder and block the queue only if the operators need in-order event processing (Default is out-of-order)
• We need to change API part and engine part
• API Design
  • Set the flag for in-order processing to operation
  • If the operation requires in-order processing, set the flag True (Default is false)
  • It is only applied to stateful operations ( such as applyStateful)
• Engine design
  • Same as the previous M:N queue-thread relationships
  • If the partitioned query which has an operator requiring in-order processing, reorder before processing the task of the partitioned query. After reordering, process the tasks of the partitioned query and block other threads to process another task until the previous task is finished.

[taegeonum]

16/07/25 Edited

Current Design of MIST

• A query is partitioned to multiple partitioned queries
• Each partitioned query has a queue
• Each queue contains tasks of the partitioned query
  • E.g) A task consists of chained operators and an input
• A processing thread picks a partitioned query, polls a task from the queue and runs the task.
• When the thread is processing the task, other threads cannot poll next task from the queue until the thread finishes the processing task. We block the queue until the polled task is finished => Process events of a stream in multiple threads but guarantee one event is processed at a time

Why one event is processed at a time in a stream?

Query \ Stream	in-order	out-of-order
in-order	O	sorting at src required
out-of-order	O	O

[Table 1: support in-order/out-of-order processing]

• Easily support in-order processing (See Table 1)
  • When the events of input stream is in-order and the query requires in-order processing, this design can easily support this requirement.
• It guarantees deterministic events processing.
• Even though the query does not require in-order processing, this design can also support the requirements.
  • However, blocking the queue can limit the parallelism of event processing in a stream. But, we don't think it really matters when there exists a lot of queries and queues. Because each partitioned query is processed in parallel, so there already exist lots of parallelism.
• We need to do sorting events by timestamp with watermark when two streams are unioned or joined, if the query requires in-order processing. Or when the stream generates out-of-order events and the query requires in-order processing.

[taegeonum]

We will suppose queries require only in-order processing and the stream can be in-order and out-of-order.