∎∎

11institutetext: ✉ Shuhao Zhang 22institutetext: Singapore University of
Technology and Design, Singapore
22email<EMAIL_ADDRESS>33institutetext: Juan Soto 44institutetext:
Technische Universität Berlin, Germany
44email<EMAIL_ADDRESS>55institutetext: Volker Markl 66institutetext:
Technische Universität Berlin, Germany
66email<EMAIL_ADDRESS>
# A Survey on Transactional Stream Processing

Shuhao Zhang  Juan Soto  Volker Markl

(Received: date / Accepted: date)

###### Abstract

Transactional stream processing (TSP) strives to create a cohesive model that
merges the advantages of both transactional and stream-oriented guarantees.
Over the past decade, numerous endeavors have contributed to the evolution of
TSP solutions, uncovering similarities and distinctions among them. Despite
these advances, a universally accepted standard approach for integrating
transactional functionality with stream processing remains to be established.
Existing TSP solutions predominantly concentrate on specific application
characteristics and involve complex design trade-offs. This survey intends to
introduce TSP and present our perspective on its future progression. Our
primary goals are twofold: to provide insights into the diverse TSP
requirements and methodologies, and to inspire the design and development of
groundbreaking TSP systems.

###### Keywords:

Transactions Stream Processing Survey

##  1 Introduction

Figure 1: Leaderboard Maintenance (LM) S-Store .

Stream processing has emerged as a powerful paradigm for real-time data
processing, with its roots dating back to the late 1990s and early 2000s when
publish-subscribe systems and data stream management systems (DSMS) were
introduced babcock2002models . Over time, various stream processing
frameworks, such as Apache Storm, Apache Flink, and Apache Kafka Streams, have
been developed, each with its own strengths and weaknesses.

The concept of combining relational queries with continuous stream processing
has been proposed since the inception of the first-generation stream
processing engine (SPE) golab1 . However, most modern SPEs either disallow the
maintenance of relational tables 10.1145/1007568.1007616  or permit (shared)
relational tables to be queried during continuous query processing, but
implicitly assume that relations remain unchanged throughout the lifespan of
††margin: a query Aurora ; madden2002fjording . Consequently, current SPEs
have some limitations. First, they do not offer transactional guarantees.
Second, they are unable to maintain a consistent state across distributed
systems, such as the management of transactional records during stream
processing S-Store . This has led to the emergence of TSP systems
conway2008cisc ; Transactions2018 ; AFFETTI202065 ;
Arasu:2006:CCQ:1146461.1146463 ; botan2012transactional ; meehan2017data ;
stream2003stream .

In ††margin: general, a TSP system is a computing system that processes
continuous streams of data while providing transactional guarantees, such as
atomicity, consistency, isolation, and durability (ACID) Tatbul2018 . To
qualify as a TSP system, a system should possess the following two fundamental
characteristics: 1) enable continuous data processing: the system should be
able to process incoming data streams in (near)real-time, without the need for
batch processing or storing the entire dataset in memory; 2) offer
transactional guarantees: the system should guarantee ACID properties are met,
to ensure that data operations are correct, reliable, and maintain data
integrity. These systems are designed to handle real-time data processing and
analytics, while ensuring the correctness and integrity of data operations.

###  1.1 Example Use Cases

To provide context, next, we discuss two ††margin: representative scenarios as
motivating examples, which is then followed by some remarks. A detailed list
of relevant application scenarios is presented in Section 5.

Leaderboard Maintenance. Meehan et al. S-Store  describe a leaderboard
maintenance application (depicted in Figure 1), which considers a TV show akin
to American Idol. In this use case, viewers vote for their favorite
contestants (via text message), and the system must continuously and
accurately update and display the top contestants ranked by the total number
of votes in real-time. Suppose a preferential voting scheme is employed, where
the contestant with the fewest votes is periodically eliminated. Additionally,
several leaderboards are maintained: one for the top-3 contestants, one for
the bottom-3 contestants, and a third one for the top-3 trending contestants
over the last 100 votes. With each incoming vote, these three leaderboards are
continuously updated. Here, there are two key requirements. First, incoming
votes need to be validated and recorded in a shared table called Votes, which
requires ACID guarantees. Second, to ensure fairness, early votes need to be
tallied before later votes, thereby necessitating an ordering guarantee.

Figure 2: Streaming Ledger (SL) Transactions2018 .

Streaming Ledger. Another simplified use case that benefits from TSP is the
Streaming Ledger (SL), proposed by dataArtisans Transactions2018 , as
illustrated in Figure 2. In this scenario, two types of requests access two
tables with shared mutable states: transfers, which exchange funds between
user accounts or assets, and deposits, which increase the balance on user
accounts or assets. The aim is to process a stream of these requests and
output the results. To handle a large volume of concurrent requests both ACID
guarantees and ordering guarantees are necessary. For instance, transfers may
be rolled back, if they violate data integrity, such as causing a negative
account balance. Additionally, the system may need to process requests in
temporal order by timestamp.

Remarks. Neither modern SPEs, nor databases adequately support the two
aforementioned use cases. On the one hand, modern SPEs restrict each execution
entity (e.g., each operator/thread), to maintain a disjoint subset of states
(or partitioned states) flink . However, this violates a transactional
consistency guarantee, when each input tuple involves multiple keys. On the
other hand, databases were not designed to handle workloads with high-velocity
input stream insertion. Contrastingly, TSP offers both ACID and stream
processing properties in a unified manner.

Integrating streaming and transactional features is a complex task. Over the
past decade, various research groups have developed their own definitions and
corresponding solutions for TSP golab2 ; Chen10 ; DSPCC ; TSDM ;
botan2012transactional ; tstream ; Affetti:2017:FIS:3093742.3093929 . This
diversity stems from the wide range of application scenarios proposed in the
literature, as well as the fact that each system concentrates on a specific
use case, which imposes implicit assumptions and objectives. Use cases that
benefit from TSP typically employ streaming capabilities to persist state or
provide (near real-time) views of shared tables, while simultaneously
leveraging transactional features, to ensure a consistent representation of
the state or a summary of the shared tables.

###  1.2 Scope

This survey provides ††margin: a comprehensive overview of TSP, encompassing
its background, properties, design aspects, technologies, systems, and
applications. We delve into the challenges and design trade-offs in
implementing TSP and provide insights into the current state of the field and
potential future directions. Our analysis focuses primarily on stateful stream
processing, which involves the general task of processing dynamic or streaming
data with algorithms that can continuously produce new results on-the-fly.
While we discuss various aspects of stream processing, including dataflow
engines and distributed systems, our analysis is not limited to these specific
design and implementation choices. The survey emphasizes the following six
aspects:

  * $\bullet$

Background: Discusses the history and motivation behind stream processing and
TSP, and outlines various transaction models over data streams.

  * $\bullet$

Properties: Explores the key properties of TSP, such as transactions, delivery
guarantees, and state management.

  * $\bullet$

Design Aspects: Examines the design aspects of TSP, including languages, APIs,
and system architectures.

  * $\bullet$

Technologies: Investigates the technologies used to implement TSP and how each
property is addressed with potential alternatives.

  * $\bullet$

Systems: Surveys representative TSP systems, focusing on their features,
strengths, and weaknesses.

  * $\bullet$

Applications: Presents real-world applications and scenarios where TSP is
leveraged to provide valuable insights and improved decision-making.

###  1.3 Outline of the Survey

The subsequent ††margin: sections are organized as follows. Section 2
introduces the background and overview of TSP, covering the conceptual
framework of TSP systems, transaction models over data streams, and providing
a high-level overview of the survey. Section 3 discusses the taxonomy of TSP
systems, delving into system properties, system architecture and design
aspects, and the technologies used to implement TSP. Section 4 presents a
survey of TSP systems, including early and recent TSP systems, and compares
them based on the taxonomy established in Section 3. Section 5 showcases
various applications and use cases of TSP, such as stream processing
optimization, concurrent stateful processing, and stream and DBMS integration.
Section 6 highlights open challenges and future directions for TSP research
and development, including novel applications and hardware platforms. Section
7 concludes with a summary of the key findings and insights gained throughout
the survey.

##  2 Background

In this section, we provide a brief overview of key terms and definitions
essential for understanding transactional stream processing systems, followed
by a conceptual framework of TSP, and lastly, discuss several transaction
models over data streams. The definitions of terms and explanations of
concepts are drawn from various sources, including Babcock et al.
babcock2002models .

###  2.1 Terms and Definitions

A data stream represents one or more underlying signals, such as a network
traffic stream indicating the type and volume of data transmitted among nodes
in a network. An event $e$ is a 2-tuple $e=<t,v>$, consisting of a timestamp
and payload. The timestamp specifies when an event occurred, while the payload
represents data values used during stream processing.

Stream queries are collections of operators that continuously process
streaming events. An operator can be ††margin: broadly defined as a
fundamental component or unit of computation within a stream processing
system. Traditional stream operators include join and aggregation, while
modern SPEs also support user-defined stream operators.

Windows define bounded subsets of streams to manage infinite streams, with
various window types such as tumbling, sliding, and session windows. The state
is a fundamental concept in stream processing, enabling the comparison of
current data with historical data.

A dataflow model is a powerful abstraction for stream processing systems,
††margin: that enables parallel and distributed processing by breaking tasks
into smaller units and orchestrates their execution across multiple nodes. In
this model stream processing tasks are represented as directed acyclic graphs
(DAGs) with nodes representing operators and edges representing the flow of
data between operators. Utilizing a dataflow model allows stream processing
systems to distribute workload efficiently, which in turn may increase the
demand for transactional correctness guarantees.

###  2.2 Conceptual Framework of TSP

This section provides ††margin: a comprehensive conceptual framework for
transactional stream processing (TSP) systems, discussing the relationships
between the key components and aspects. A TSP system is comprised of five
components: transactions, transaction models, operators, scheduler, and
storage. These components are closely related to the four key aspects of a TSP
system, which are language, programming model, execution model, and
architecture.

Transactions are critical components of TSP systems, ensuring that data is
processed and maintained consistently and reliably. Transactions combine the
real-time nature of stream processing with the reliability and consistency
guarantees of traditional transactional systems. ††margin: Transaction models
describe the granularity and scope of transactions within a TSP system. In
TSP, a transaction is considered committed when it has successfully completed
an operation (e.g., insertion, update, deletion) and the system has confirmed
that transactional changes are consistent with the desired transactional
guarantees (e.g., consistency, isolation, durability). Upon committing a
transaction, the system ensures that its effects are persistent and can be
recovered in the event of a failure. This concept of “commit” is essential in
TSP systems to maintain the integrity and consistency of the data during
processing.

Operators are responsible for processing incoming and outgoing data, and
performing operations, such as filtering, aggregation, transformation, or
joins. Operators may also have mutable state that needs to be managed in a
transactional manner. Scheduler manages the execution of operators and ensures
that transactions are executed in the correct order, according to the chosen
consistency and isolation models. Schedulers may need to handle out-of-order
events, coordinate distributed execution, and manage resource allocation. The
storage component manages the persistent state of the system, including the
mutable state of operators and any intermediate or final results produced
during processing. The storage component must also ensure durability and fault
tolerance, while providing efficient access to the data.

The conceptual framework of a TSP system covers the key aspects to consider
when designing and implementing a TSP system, including language, programming
model, execution model, and architecture.

_Language:_ The language aspect of a TSP system defines the syntax and
semantics for expressing streaming and on-demand queries, as well as the
transactional properties (e.g., consistency, isolation, durability). This
aspect is related to the transaction models and operators, as it provides the
means for developers to define and manipulate transactions and the operations
they perform.

_Programming Model:_ The programming model refers to the way developers
interact with the TSP system to define and manage stateful operations and
transactional guarantees. This aspect is related to transactions, transaction
models, and operators, as the programming model provides the framework for
working with these components in a structured and organized manner.

_Execution Model:_ The execution model focuses on how the TSP system processes
both streaming and on-demand queries while providing transactional guarantees.
This aspect is related to the scheduler and operators, as the execution model
determines how the scheduler manages the execution of operators and ensures
that transactions are executed in the correct order, according to their
consistency and isolation models.

_Architecture:_ The architecture aspect of a TSP system addresses how the
system is designed and structured to balance the requirements of stream
processing and data management. This aspect is related to all five of the key
components. The architecture facilitates interaction between these components,
such as sharing state between on-demand and streaming queries and providing
read and write access as needed.

###  2.3 Transaction Models over Data Streams

Next, we discuss some notable transaction models over data streams, along with
their implementation approaches, to provide a comprehensive understanding of
transactional guarantees in stream processing.

####  2.3.1 Abstract Models

Various transaction models have been explored for stream processing
applications to address consistency guarantees. These models serve as
processing paradigms in TSP systems.

Per-tuple Transactions: Each tuple in the data stream is treated as a separate
transaction, adhering to ACID properties. This approach is suitable for
scenarios requiring atomic and isolated processing of individual events.
However, it may introduce significant overhead due to frequent coordination
between processing nodes.

Micro-batch Transactions: Data streams are divided into small, bounded micro-
batches, with transactions executed over them. This approach reduces the
overhead associated with per-tuple transactions, allowing for parallelism and
optimization opportunities. However, it may introduce additional latency.

Window-based Transactions: Transactions are executed over windows based on a
unit of time, the number of events, or some other criterion. This approach
enables processing of related events within the same transaction, thereby,
providing stronger consistency guarantees. Yet this can be challenging to
manage, especially when dealing with out-of-order events or evolving window
types.

Group-based Transactions: Transactions are executed over groups of related
events in the data stream. Groups can be defined based on specific criteria,
providing fine-grained control over transaction boundaries, and stronger
consistency guarantees for complex processing tasks. However, managing group-
based transactions can be complex, requiring the identification of related
events and coordination across multiple processing nodes.

Adaptive Transactions: This flexible model allows the system to dynamically
adjust transaction boundaries based on workload, system state, or application
requirements. This can include switching between different transaction models
or adapting granularity to optimize performance or meet specific consistency
guarantees. Implementing adaptive transactions can be challenging, as it
requires real-time monitoring and the adaptation of transaction boundaries.

####  2.3.2 Implementation Approaches

Implementation approaches for the aforementioned transaction models can be
classified into three categories: unified transactions, embedded-transactions,
and state transactions. Depending on an application’s specific requirements,
an appropriate combination of implementation approach and particular
transaction model should be chosen to achieve the desired performance,
scalability, and fault tolerance capability.

Unified Transactions: This approach embeds stream processing operations into a
transaction, providing a single framework for handling both stream processing
and transactions. Unified transactions can potentially support various
transaction models, as it allows flexibility in defining the scope and
granularity of transactions. However, it might be more suitable for fine-
grained transaction models, such as per-tuple or micro-batch transactions.

Embedded Transactions: This approach embeds transaction processing into stream
processing, allowing for transactional semantics without the need for separate
transaction management. Embedded transactions can be more efficient for
certain transaction models, particularly when a lightweight transaction
mechanism is required. It might be better suited for per-tuple, micro-batch,
or adaptive transactions, where the overhead of separate transaction
management can be minimized.

State Transactions: This approach separates transaction processing and stream
processing, focusing on managing shared mutable state through transactions.
State transactions can also support different transaction models, but are more
suitable for scenarios where state management is a primary concern, such as
window-based, group-based, or adaptive transactions.

##  3 Taxonomy of TSP

††margin:

In this section, we examine a taxonomy of Transactional Stream Processing
(TSP) as illustrated in Figure 3. The taxonomy is structured into three key
categories: _Properties of TSP:_ Here we examine the characteristics and
requirements of TSP systems, including ordering, ACID properties, state
management, and reliability. Analyzing these properties enables us to better
understand the fundamental issues and challenges prevalent in TSP systems that
seek to ensure accurate and reliable data processing. _Design Aspects of TSP:_
Here we explore the design considerations in TSP systems, spanning transaction
implementation, boundaries, execution, delivery guarantees, and state
management. Investigating these design aspects aids us in evaluating the
suitability of TSP systems for specific applications and provides insights
into various design choices and trade-offs. _Implementation Details:_ Here we
address the practical aspects of TSP system implementation, such as
programming languages, APIs, system architectures, and component integration.
This section also discusses performance metrics and evaluation criteria for
TSP systems. By examining these implementation details, we gain a deeper
understanding of the practical challenges and proposed solutions in the
development of TSP systems. Ultimately, this enables us to be more informed
about the choices that must be made when designing or selecting which TSP
system to employ for a given use case.

Figure 3: Taxonomy of TSP.

###  3.1 Properties of TSP

A TSP model ††margin: is required to meet both the ordering properties of
streaming operators and events, and the ACID properties of transactions, while
also addressing state management, reliability, fault tolerance, and
durability. These elements along with the CAP theorem’s implications are
crucial to the design and functionality of TSP systems. Hence, we will delve
into these properties in the subsequent sections, starting with ordering
properties followed by ACID properties.

####  3.1.1 Ordering Properties

In TSP systems, there are two critical ordering properties: event ordering and
operation ordering.

##### Event Ordering:

Event ††margin: ordering requires that transactions be processed according to
the order of their triggering events, typically based on timestamps or some
other logical ordering mechanism. This property is crucial to ensure
transactions are executed in the correct sequence, so as to avoid
inconsistencies. It also helps prevent race conditions or out-of-order
processing, which can occur in distributed TSP systems with high levels of
parallelism. It is worth noting that the ordering schedule is determined
explicitly by the input event rather than the transaction execution order.

To maintain event order TSP systems may employ strategies such as locking,
versioning, or optimistic concurrency control. Golab et al.golab2  propose two
stronger serialization properties with ordering guarantees. The first is
called _window-serializable_ , which requires a read-only transaction to
perform a read either strictly before a window is updated or after all sub-
windows of the window are updated. The second is called _latest-window-
serializable_ , which only allows a read on the latest version of the window,
i.e., after the window has been completely updated. Instead of imposing an
event ordering, FlowDBAffetti:2017:FIS:3093742.3093929  enables developers to
optionally ensure that the effects of transactions are the same as if they
were executed sequentially (i.e., in the same order in which they started).

##### Operation Ordering:

In many TSP systems, applications can be represented using dataflow models,
such as directed acyclic graphs (DAGs), where operators are connected by data
streams tstream . However, it is essential to acknowledge that in the TSP
landscape, there may be other models that represent and process data streams
using a different approach. ††margin: Operation ordering refers to the
sequence in which operators are executed in a TSP system, which impacts the
correctness and efficiency of the system. Via operation ordering, the data
that flows through the pipeline will be processed correctly: thereby
contributing to the consistency and correctness prevalent in a TSP system.
When an application is represented using a DAG, the operation ordering is
determined by the directed edges between the operators. Although the operation
ordering may be expressed differently for alternative representations, the
ordering property guarantees the outcome will be the same. Consider a scenario
where a TSP system adopts a dataflow model for stream processing - the
ordering property is inherently upheld in such a setup. Nevertheless, if a
database system incorporates TSP, an added prerequisite for operation ordering
becomes necessary to guarantee consistency and accuracy, as detailed in the
work of S-Store S-Store .

####  3.1.2 ACID Properties

TSP can offer traditional ACID guarantees Bernstein:1996:PTP:261193  similar
to those in relational databases. ††margin: However, depending on the
requirements of the specific application, TSP systems may need to relax or
adapt these guarantees. First, although ACID properties are strictly required
in relational databases, they may be relaxed in stream processing scenarios
Affetti:2017:FIS:3093742.3093929 ; botan2012transactional ; tstream ; ACEP .
Second, some streaming applications, do not require the ACID properties ACEP .

##### Atomicity:

Atomicity ensures that transactions are either fully completed or aborted. In
TSP systems, all operations within a transaction are either successfully
processed together or not processed at all: thereby preventing partial updates
that could lead to an inconsistent state. Atomicity in TSP varies depending on
the transaction model. Traditional commit protocols, such as two-phase commit
(2PC), ensure atomicity ††margin: by coordinating commit or abort decisions
among distributed participants. In contrast, sagas sagas  allow the exposure
of intermediate (uncommitted) state and require developers to define
compensating actions for each operation, thereby offering a more flexible way
to handle atomicity at the cost of strong isolation guarantees. Some TSP
systems, like the one proposed by Wang et al. ACEP , relax atomicity in
certain contexts, which enables developers to choose the desired consistency
level. In such cases, alternative atomicity models, like sagas, can be adopted
to balance the trade-offs between consistency, performance, and availability.
Understanding these differences is crucial for designing TSP systems with
appropriate atomicity guarantees.

##### Consistency:

Consistency ensures that a transaction moves the system from one consistent
state to another consistent state Vossen2016 . In the context of TSP systems,
consistency guarantees that data is processed and updated according to the
specified consistency model. TSP systems can provide different levels of
consistency depending on the application requirements, such as eventual
consistency ACEP , strong consistency Affetti:2017:FIS:3093742.3093929 , or
causal consistency tstream . It is essential to understand the trade-offs
between various consistency levels, as stronger consistency guarantees may
lead to increased complexity and reduced performance.

##### Isolation:

Isolation prevents concurrent transactions from interfering with one another
Vossen2016 . In TSP systems, isolation is essential for ensuring that the
output data remains consistent despite the concurrent execution of
transactions. Different isolation levels can be provided by TSP systems, such
as serializability, snapshot isolation, or read committed
Affetti:2017:FIS:3093742.3093929 . The choice of isolation level depends on
the application requirements and the trade-off between consistency and
performance. Some TSP systems may offer configurable isolation levels,
allowing developers to adjust the isolation guarantees according to the
application’s specific needs.

##### Durability:

Durability ††margin: guarantees that once a transaction is committed, its
changes are permanently stored in the system Vossen2016 . In TSP systems,
durability can be ensured through techniques, such as replication, logging, or
checkpointing Affetti:2017:FIS:3093742.3093929 . Durability plays a pivotal
role in TSP systems, especially when recovery from failures and fault
tolerance are considered. A system’s durability influences the preservation of
its state and output and governs the perceived behaviour from an external
user’s standpoint during a failure event. The recovery mechanism of specific
TSP systems might entail replaying input streams to rebuild the state, which,
due to variability in order and isolation presumptions, may not always restore
an identical state. The extent of state preservation post-recovery can differ.
To ensure durability, a TSP system typically needs to satisfy various
properties, including input preservation, state maintenance, and output
persistence. This is often achieved through strategies like replication,
logging, or checkpointing, which assure fault tolerance and recoverability
post-failure.

####  3.1.3 State Management Properties

Effective state management is essential in TSP systems to ensure data
consistency, support the stateful processing of operations, and failure
recovery. Among the primary state management properties are state types,
access scope, state recovery, and the management of large states.

##### State Types:

States in TSP systems can be categorized into two types: a) read-only state:
This type of state involves applications that solely read data to obtain the
information needed to process input events. Managing read-only state is
relatively straightforward, as it does not involve updates or concurrency
control concerns. b) read-write state: This type of state is updated and
maintained as stream events are processed. Managing read-write state becomes
particularly challenging when processing different input events that rely on
reads or writes to the same state. Concurrency control issues can arise when
more than one entity (e.g., threads) shares a state (e.g., intra-operator) and
may concurrently modify it during execution.

##### Access Scope:

Access scope defines the visibility and accessibility of state information
within a TSP system. It dictates whether the state is shared globally,
partitioned across parallel processing instances, or limited to a specific
operator or group of operators. In the case of stream operators, they may need
to maintain multiple states. For example, shared states can be the index
structure of an input stream or some other user-defined data structure shared
among threads of the same operator, operators, and queries. Moreover, access
scope impacts performance, consistency, and fault tolerance.

##### State Recovery:

State recovery refers to the ability of a TSP system to restore its state
after a failure, thereby, ensuring that processing can resume without data
loss or inconsistencies. This property is essential for providing fault
tolerance and maintaining the overall reliability of a TSP system. State
recovery can be achieved using techniques, such as checkpointing, logging, or
state replication. Effective state recovery mechanisms must minimize the time
required to restore state and resume processing while ensuring that the
recovered state is consistent with the pre-failure state.

##### Management of Large States:

As the volume of data and the number of concurrent transactions grows, TSP
systems must be able to manage large states effectively to maintain low-
latency access and fault tolerance. To distribute shared mutable state across
multiple nodes, techniques, such as data sharding, partitioning, and
replication can be employed, to provide scalability. State partitioning
involves distributing state information across multiple storage locations,
improving scalability and parallelism. State compaction reduces the storage
footprint by merging redundant or outdated state information. State
checkpointing periodically saves snapshots of the state, enabling recovery
after failures and ensuring durability. Additionally, TSP systems can use
state eviction and expiration strategies, such as Least Recently Used (LRU) or
Time-to-Live (TTL), to manage memory and storage resources efficiently. This
ensures that the system can continue processing new transactions without
running out of resources.

####  3.1.4 Reliability and Delivery Guarantees

Fault tolerance, durability, and deliverability are essential properties of
TSP systems. These properties ensure that TSP systems can accurately process
data and maintain their state despite potential issues, such as failures,
duplicate messages, and out-of-order events. Fault tolerance and durability
are essential to achieve exactly-once delivery semantics. Fault tolerance
ensures a system can continue operating despite failures, while durability
guarantees that committed transactions are stored permanently. Together, these
properties enable the system to provide exactly-once semantics, thereby,
ensuring each event is processed correctly and without duplication or
omission, even when failures occur.

##### Delivery Guarantees:

Delivery guarantees in TSP systems dictate how input events are processed,
when failures, duplicate messages, or out-of-order events occur. Common
delivery guarantees in stream processing systems include at-most-once, at-
least-once, and exactly-once processing. Exactly-once processing is often the
most desirable for TSP systems, ensuring each event is processed exactly once,
regardless of failures or other issues during processing. Thus, even in the
presence of failures, the system can ensure no duplicates or missing events
occur.

##### Fault Tolerance:

Since streaming applications typically run indefinitely, the probability of
service disruptions due to unexpected system failures increases. A fault-
tolerant TSP system persists when processing events and adheres to delivery
guarantees, even in the face of failures. In case of a failure, a fault-
tolerant system must recover and resume processing without violating delivery
guarantees. To enable rapid recovery from failures and minimize data loss,
fault tolerance approaches, such as state replication, checkpointing, and log-
based recovery are employed.

##### Durability:

Durability involves persistent data storage, to ensure its availability for
retrieval. This property is crucial for upholding delivery guarantees, as it
enables the system to maintain desired processing semantics. For instance, in
an exactly-once processing scenario, the system must ensure that each input
event is processed and committed exactly once, necessitating durable storage
for both the input events and corresponding state changes.

##### CAP Theorem:

The CAP theorem, foundational in distributed systems, states a system can’t
simultaneously provide consistency, availability, and partition tolerance.
This is of importance to Transactional Stream Processing (TSP) systems, which
often must strike a balance among these properties due to distributed data
processing and storage. Consistency and durability both aim to maintain a
uniform view of the system’s state. For TSP systems, these are crucial for
preserving data integrity and providing reliable transactional guarantees.
Availability, ensuring every system request receives a response, is vital for
continuous, real-time processing in TSP systems. Partition tolerance, akin to
fault tolerance, allows a system to function even during communication
breakdowns between nodes, a key requirement in TSP systems for ensuring
uninterrupted processing. Given the CAP theorem’s constraints, TSP systems may
need to prioritize among these properties based on specific use cases. For
instance, a TSP system prioritizing consistency and partition tolerance might
compromise availability, leading to longer response times. Conversely, one
focusing on availability and partition tolerance may occasionally return stale
data but provides fast responses and continuous operation.

######  Remark 1 (Beyond Exactly-Once Guarantee)

TSP systems may face unique challenges requiring more stringent delivery
guarantees than the exactly-once guarantee typically found in many SPEs.
Specifically, TSP systems must replay failed tuples in the exact timestamp
sequence of their triggering input events and prevent duplicate message
processing. This is crucial because results depend on the local state of an
operator and the time ordering of input streams.

One approach to achieving this advanced level of delivery guarantee involves
checkpointing or archiving each input event before processing and sequentially
replaying them in case of failure Chandrasekaran2004RemembranceOS . While this
method provides the desired guarantee, it incurs significant overhead, making
it unsuitable for many TSP systems. Consequently, further research is required
to identify more efficient mechanisms that can satisfy the delivery guarantee
needs of TSP systems while minimizing performance overhead.

###  3.2 Design Aspects of TSP

The design aspects of TSP systems focus on the critical components required to
create a functional and efficient TSP system. These components include the
implementation of transactions, determining transaction boundaries, executing
transactions, delivering guarantees, and managing the state. Understanding
these design aspects is crucial for evaluating the suitability of different
TSP systems for specific application requirements and providing insights into
various design choices and trade-offs.

####  3.2.1 Implementing Transactions

To actualize a transaction model over data streams, three primary approaches
have been proposed: ††margin: embedding stream processing operations into
transactions (i.e., _unified transactions_), embedding transaction processing
into stream processing (i.e., _embedded transactions_), or combining
transaction processing and stream processing (i.e., _state transactions_). Let
us discuss each of these in turn.

##### Approach 1: Unified Transactions.

Unified transactions integrate stream processing and transaction processing by
transforming data streams into time-varying relations motwani2002query ;
stream2003stream ; Arasu:2006:CCQ:1146461.1146463 . By treating data streams
and relational data uniformly, TSP systems can leverage existing relational
data management techniques for transactional consistency and correctness. This
approach enables us to define a transaction that can handle both stream
processing and transactional aspects within a single framework, thereby,
allowing flexibility in defining the transaction scope and granularity.

######  Definition 1 (Unified Transaction)

Let $D={d_{1},d_{2},...,d_{n}}$ be a dataset containing both data streams and
relational data, and $O={o_{1},o_{2},...,o_{m}}$ be a set of processing
operations. A unified transaction $T_{i}$ is a tuple $(D_{i},O_{i})$, where
$D_{i}\subseteq D$ and $O_{i}\subseteq O$. In this approach, both stream
processing and transactional aspects are handled within a single framework,
allowing flexibility in defining the scope and granularity of transactions.

Several studies have explored the implementation of continuous queries as
sequences of one-time queries, which are executed as a result of data source
modifications or periodic execution botan2012transactional ; S-Store ;
oyamada2011efficient ; Oyamada13 . These studies illustrate the various
methods employed to unify stream processing and transaction processing, so as
to enable the use of a single execution engine for both types of operations.
The design space for unified transactions consists of several aspects,
including data modelling, query execution, and transaction management.

Data Modeling. In order to transform data streams into relational data, data
streams are represented as time-varying relations. To indicate the time-
varying nature of data, both input and output streams are treated as
continuous relations with a timestamp attribute. This uniform representation
enables the use of relational algebra and SQL-like queries to process data
streams and simplifies the integration of stream processing with existing
relational database systems.

Query Execution. Queries over data streams are often continuous: they are
evaluated over an unbounded sequence of input data. Unified transactions
represent continuous queries as a sequence of one-time queries triggered by
data source modifications or periodic execution. This approach allows for the
reuse of existing query processing techniques from relational databases while
ensuring the continuous nature of stream processing is maintained.

Transaction Management. To ensure transactional consistency and correctness,
the unified transactions approach relies on relational data management
techniques. In particular, concurrency control and recovery mechanisms, such
as two-phase locking and logging, to provide isolation, atomicity, and
durability guarantees.

The unified transactions approach simplifies system architecture and leverages
well-established relational data management techniques. However, this approach
may introduce additional overhead due to the transformation of data streams
into relational data and may not be suitable for all TSP systems, particularly
those with strict latency requirements or complex stream processing needs.
Developers must carefully evaluate the trade-offs and requirements of their
specific application to determine whether this approach is appropriate for
their TSP system.

##### Approach 2: Embedded Transactions.

The embedded transaction approach integrates transaction processing directly
into the stream processing pipeline. Instead of transforming data streams into
relational data, transactions are managed and processed within the context of
stream processing. This approach involves event-driven processing, state
management, and transactional guarantees.

######  Definition 2 (Embedded Transaction)

Let $S={s_{1},s_{2},...,s_{n}}$ be a data stream, and
$O={o_{1},o_{2},...,o_{m}}$ be a set of stream processing operations. An
embedded transaction $T_{i}$ is a tuple $(s_{i},O_{i})$, where $s_{i}\in S$
and $O_{i}\subseteq O$. Here, each incoming data item $s_{i}$ is treated as a
transaction, allowing real-time processing while maintaining consistency and
reliability guarantees.

††margin:

Several studies, including those exploring incremental continuous query
processing with isolation guarantees Shaikh16  have explored the embedded
transactions approach. For instance, Shaikh et al Shaikh16  propose a model
that treats each incoming data item as a transaction. This approach allows for
real-time processing of data streams while maintaining consistency and
reliability guarantees. However, potential issues include inconsistencies in
the output due to updates during join processing. To address this, they
propose a mechanism for maintaining consistency in the presence of concurrent
updates, using snapshot isolation and optimistic concurrency control.

Key aspects of embedded transactions involve processing events as they arrive,
managing state information between processing steps, and incorporating data
partitioning, replication, and checkpointing to achieve transactional
guarantees. Next, we examine each of these aspects in turn.

Event-Driven Processing. The embedded transaction approach employs event-
driven processing, where each event in the data stream triggers one or more
stream processing operations. This allows for low-latency processing and
maintains the temporal order of data streams.

State Management. State management is crucial in the embedded approach since
it enables the retention and manipulation of information between processing
steps. State management varies across systems, with some using distributed
storage systems or in-memory data structures for efficient state management.

Transactional Guarantees. The embedded transaction approach provides
transactional guarantees, such as consistency, isolation, and durability
within the stream processing pipeline. To achieve these guarantees, they
employ techniques, such as data partitioning, replication, and checkpointing.

The embedded transaction approach offers benefits, such as low-latency
processing and the native handling of complex stream processing tasks.
Nevertheless, implementing transactional guarantees within the stream
processing pipeline could necessitate substantial efforts. Furthermore, this
approach might not be optimal for applications necessitating integration with
established relational databases or traditional transaction processing
systems. Developers should carefully assess the requirements and constraints
of their specific application to determine whether this approach is
appropriate for their TSP system.

##### Approach 3: State Transactions.

The state transaction approach merges transaction processing and stream
processing within a single system and handles state access operations as
transactions. This enables TSP systems to provide transactional guarantees
while processing unbounded data streams and ensure correctness via
transactional semantics and the modelling of state accesses as _state
transactions_.

######  Definition 3 (State Transaction)

Let $S={s_{1},s_{2},...,s_{n}}$ be a data stream, $R={r_{1},r_{2},...,r_{p}}$
be a set of shared mutable states, and $O={o_{1},o_{2},...,o_{m}}$ be a set of
processing operations. A state transaction $T_{i}$ is a tuple
$(S_{i},R_{i},O_{i})$, where $S_{i}\subseteq S$, $R_{i}\subseteq R$, and
$O_{i}\subseteq O$. All operations within the same transaction have the same
timestamp, denoted as $ts$.

State transactions focus on managing shared mutable states through
transactions. Key aspects include managing state information between
processing steps and decoupling transaction processing from stream processing.
Design considerations include dataflow models, state access operations,
coordination mechanisms, and fault tolerance and recovery. Next, we examine
each of these design considerations in turn.

Dataflow Models. The state transaction approach typically uses dataflow models
to process data streams consisting of interconnected stateful operators. These
operators process events, update state, and produce output events, which is
amenable for parallel and distributed processing.

State Access Operations. State transactions treat state access operations as
transactions, where each operation is associated with a unique timestamp. This
enables complex processing tasks and transactional guarantees, like
consistency, isolation, and durability.

Coordination Mechanisms. The state transaction approach coordinates state
transactions across the dataflow pipeline using mechanisms, such as two-phase
commit protocols, timestamp-based ordering, or conflict resolution strategies,
to maintain consistency and isolation.

Fault Tolerance and Recovery. The state transaction approach provides fault
tolerance and recovery mechanisms, such as replication, checkpointing, and
logging, to ensure durability and resilience against failures.

The state transaction approach integrates transaction processing into the
stream processing pipeline, handles complex processing tasks, and provides
transactional guarantees. However, this approach may introduce additional
complexity due to the use of coordination and fault tolerance mechanisms.
Developers should carefully assess their application’s requirements and weigh
the benefits against the potential complexities introduced by this approach.

####  3.2.2 Determining Transaction Boundaries

Determining transaction boundaries is an essential aspect of TSP system
design, as it defines which operations are grouped into transactions for
atomicity. It turns out that establishing transaction boundaries over streams
can be quite flexible, particularly for state transaction implementation.
First, various conditions can initiate a transaction (i.e., _triggering
unit_), such as per input event or per batch of events with a common
timestamp. Second, different entities can generate a transaction (i.e.,
_generating unit_), such as per operator and per query. Additionally,
transactions can spawn other transactions (i.e., _transaction spawning_). Let
us examine each of these settings in turn.

##### Setting 1: Triggering Units.

TSP systems diverge from traditional databases in that they rely on incoming
streaming events rather than user requests to initiate transactions. The
granularity of transaction boundaries is defined by various types of
triggering units, including time-based, batch event-based, single event-based,
and user-defined triggers. Next, we describe each of these in turn.

Time-based Triggers. Time-based triggers ††margin: refer to transactional
models in which the transaction boundaries are determined by time intervals.
These intervals can be either fixed or dynamically adjusted based on the
application requirements or the characteristics of the data streams. It often
assumes that events with a common timestamp are executed atomically to ensure
progress correctness. This approach is employed in both academic projects,
such as STREAM stream2003stream ; Arasu:2006:CCQ:1146461.1146463  and
commercial products, like Coral8 Coral8 . Time-based triggers are suitable for
the concurrent aggregation of sliding windows, the association of transaction
boundaries with window boundaries, and the management of long-running queries
with specified re-execution frequencies golab2 ; DSPCC ; conway2008cisc .

Batch Event-based Triggers. These transactions are triggered when a batch of
events with a shared characteristic (e.g., common timestamp, originating from
the same stream) are processed. Batch event-based triggers are used in
DataCell Liarou2009DataCellBA ; liarou2009exploiting , S-Store S-Store , and
Chen et al.’s cycle-based transaction model Chen10 ; chen2011query .They can
handle large volumes of data and provide consistent processing across multiple
streams.

Single Event-based Triggers. In this type, a transaction is triggered for each
incoming event. Single event-based triggers ensure fine-grained control and
consistency on an event-by-event basis. They have been implemented in various
systems, such as Aurora and Borealis Aurora ; abadi2005design , ACEP ACEP ,
SPASS SPASS , and TStream tstream . This type of transaction is suitable for
applications requiring strict consistency guarantees and low-latency
processing.

User-defined Triggers. In this type, users can define custom triggering
conditions based on their specific application requirements, which offers
flexibility when establishing transaction boundaries and declaring processing
guarantees. Botan et al.botan2012transactional  and Chen et
al.chen2018streamdb  demonstrate the use of user-defined transactions in their
respective systems.

##### Setting 2: Generating Units.

While triggering units determine “when” a transaction is created, generating
units focus on “who” generates a transaction. Transactions can be generated by
user clients directly or through continuous queries on a per-query or per-
operator basis. The design space for generating units includes query-based,
operator-based, and user-defined generators. Next, we describe each unit type
in turn.

Query-based Generator. These transactions group operations involved in the
one-time execution of an entire query stream2003stream ;
Arasu:2006:CCQ:1146461.1146463 . Early Stream Processing Engines (SPEs)
employed query-based triggers for the interactive processing of both
relational and streaming data, such as the STREAM project stream2003stream ;
Arasu:2006:CCQ:1146461.1146463 . This type simplifies the transactional model,
making it easier to manage and understand. However, it may lack flexibility in
some cases, where individual operators within a query need to have separate
transactional boundaries or different isolation levels.

Operator-based Triggers. In this type, each operator in a query generates its
own transactions S-Store ; tstream . Examples of this design include S-Store
S-Store  and TStream tstream . Operator-based triggers provide a finer level
of granularity and flexibility compared to query-based triggers, which enables
more precise control over shared states in streaming dataflow graphs. This can
lead to better performance and resource utilization in certain scenarios.
However, this increased flexibility may also result in potential conflicts or
dilemmas, such as deadlocks and contention, which may require additional
mechanisms to resolve S-Store ; tstream .

User-defined Triggers. Some applications may require ad-hoc transactional
queries or user-driven transactions during stream processing AFFETTI202065 ;
Affetti:2017:FIS:3093742.3093929 ; chen2018streamdb . User-defined
transactions allow users to specify where consistency needs to be enforced and
which consistency constraints are required, as demonstrated in the work of
Affetti et al. AFFETTI202065 ; Affetti:2017:FIS:3093742.3093929 . This type
grants more control to the user, thereby, allowing them to tailor
transactional semantics to their specific needs. However, this flexibility can
make system-level optimizations more challenging, as the transaction types are
not known in advance. Additionally, users bear the responsibility of ensuring
that the system is free of any dilemmas or conflicts AFFETTI202065 ;
Affetti:2017:FIS:3093742.3093929 .

##### Setting 3: Transaction Spawning.

Transactions can also spawn, i.e., trigger and generate other transactions.
This is particularly useful in service-oriented architectures, where the basic
premise is to treat all functionalities as services and compose and execute
them, according to the user or application-specific requirements DEXA16 .
Treating each service execution as a transaction and requiring atomic
execution of those transactions have been found to be very helpful in this
process. The execution of service compositions yields composite transactions
TM16 , where a transaction is an execution of a service TIOT . Subsequently, a
transaction spawning consists of a nonempty set of services. Some of these
have executions that are continuous and others may spawn new transactions.

####  3.2.3 Executing Transactions

Executing transactions involves processing the operations within a transaction
according to the defined transaction boundaries and ensuring that the system
maintains the required properties including the ACID properties and also the
streaming properties.  Table 1 summarizes ††margin: the execution mechanisms
adopted by relevant systems. These can be classified into five approach types:
_single-version lock-based_ , _multi-version lock-based_ , _static partition-
based_ , _dynamic partition-based_ , and _optimistic_. Note that, “C” in ACID
refers to the preservation of integrity constraints, independent of how
transactions are integrated with stream processing.

Table 1: Execution mechanisms of TSP systems.

††margin:

Works |  Approach |  Key Notes
---|---|---
STREAM stream2003stream , Wang et al. ACEP , Oyamada et al. oyamada2011efficient , FlowDB/TSpoon Affetti:2017:FIS:3093742.3093929 ; AFFETTI202065  |  single-version lock-based |  Each state is maintained with a single copy; concurrent access is regulated by exclusive locks with an event ordering guarantee
Wang et al. ACEP  |  multi-version lock-based |  Each state is maintained with multiple copies; concurrent access is regulated by read-write locks with an event ordering guarantee
S-Store S-Store  |  state partition-based |  Pre-partition states into disjoint partitions, and regulate concurrent access to each partition, similar to the single-version lock-based approach
TStream tstream , MorphStream mao2023morphstream  |  transaction partition-based |  Dynamically partition and regroup state transactions to avoid conflicts
Golab et al. golab2 , FlowDB/TSpoon AFFETTI202065 ; Affetti:2017:FIS:3093742.3093929  |  optimistic |  Optimistically schedule concurrent state transactions and abort transactions if conflicts arise
Several prior works abadi2005design ; botan2012transactional ; Chen11 ; Chen10 ; Gtze2019SnapshotIF  |  snapshot isolation |  Implement the semantics of database transactions to defined segments of data streams, thereby assuring snapshot isolation during the processing of these segments

##### Lock-based Approaches:

Lock-based approaches ensure the correct execution of transactions by
controlling access to shared resources. Using locks to protect shared states,
these methods prevent concurrent access and maintain consistency. Lock-based
approaches can be classified into two main types:

_a) Single-version lock-based:_ These approaches utilize a single version of
the shared state and apply locks to ensure proper transaction execution. The
challenge lies in balancing synchronization and performance without causing
excessive contention or delays in transaction processing. We discuss three
notable examples of single-version lock-based approaches as follows.

In STREAM stream2003stream , synopses enable different operators to share
common states. To guarantee that operators view the correct version of a
state, the system must track the progress of each stub and present the
appropriate view (i.e., a subset of tuples) to each stub. This is achieved
through a local timestamp-based execution model with a global schedule that
coordinates the successive execution of individual operators via time slot
assignments. Batches of tuples with the same timestamp are executed atomically
to ensure progress correctness, with a simple lock-based transactional
processing mechanism implicitly involved.

An earlier study by Wang et al. ACEP  describes a strict two-phase locking
(S2PL)-based algorithm that allows multiple state transactions to run
concurrently while maintaining both ACID and streaming properties. Unlike the
original S2PL Bernstein:1996:PTP:261193  algorithm, Wang et al. ACEP  lock
each transaction ahead of all query and rule processing. In this process, each
transaction’s timestamp is compared against a monotonically increasing counter
to ensure that the transaction with the smallest timestamp always obtains a
lock first, thereby guaranteeing access to the proper state sequence. Once
lock insertion is complete, the system increases the counter and allows the
next transaction to proceed, regardless of whether the transaction was fully
processed. To fulfil event ordering constraints, read or write locks are
strictly invoked in their triggering event order. However, the locking
mechanism must synchronize the execution for every single input event, which
may negatively impact system performance.

Oyamada et al. oyamada2011efficient  propose three pessimistic transaction
execution algorithms: synchronous transaction sequence invocation (STSI),
asynchronous transaction sequence invocation (ATSI), and order-preserving
asynchronous transaction sequence invocation (OPATSI). STSI processes
transactions triggered by event streams one at a time, with execution results
naturally generated following the event arrival sequence. ATSI removes the
blocking behaviour of STSI by asynchronously spawning new threads that wait
for the transaction to complete. OPATSI extends ATSI through a priority queue
to further guarantee the order of the results.

_b) Multi-version lock-based:_ These approaches employ multiple versions of
shared states and use locks to control access to different state versions. The
main challenge is ensuring that the correct state version is accessed while
avoiding outdated writes.

A notable example is Wang et al. ACEP , who propose an algorithm called LWM
(Low-Water-Mark), which relies on the multi-versioning of shared states. LWM
leverages a global synchronization primitive to guard the transaction
processing sequence: write operations must be performed monotonically in event
order, but read operations are allowed to execute as long as they can read the
correct version of the data (i.e., its timestamp is earlier than the LWM). The
key differences between LWM and the traditional multi-version concurrency
control (MVCC) scheme are twofold. First, MVCC aborts and then restarts a
transaction when an outdated write occurs, while LWM ensures that writes are
permitted strictly in their timestamp sequence, preventing outdated writes.
Second, MVCC assumes that the timestamp of a transaction is system-generated
upon receipt, whereas LWM sets the timestamp of a transaction to the
triggering event. This distinction enables LWM to maintain a more event-driven
approach to transaction management, better aligning with the streaming nature
of TSP systems.

In summary, lock-based approaches to transaction execution in TSP systems
offer various methods for managing access to shared resources and maintaining
consistency. While single-version lock-based approaches focus on balancing
synchronization and performance within a single shared state, multi-version
lock-based approaches provide greater flexibility by managing multiple
versions of shared states. Both types of approaches present their own
challenges and trade-offs, and the choice of approach depends on the specific
requirements and characteristics of the TSP system being implemented.

##### Partition-based Approaches:

Partition-based approaches to transaction execution in TSP systems involve
dividing the internal states or transactions into smaller units, which can
then be executed in parallel or with reduced contention. These methods aim to
improve performance while maintaining consistency and adhering to event order
constraints. There are two primary types of partition-based approaches:

_a) Static partition-based:_ These approaches divide the internal states of
streaming applications into disjoint partitions and use partition-level locks
to synchronize access. This approach is suitable for transactions that can be
perfectly partitioned into disjoint groups.

For example, S-Store S-Store  splits the streaming application’s internal
states into multiple disjoint partitions. The computation on each sub-
partition is performed by a single thread. To guarantee state consistency,
S-Store uses partition-level locks to synchronize access. However, the state
partition-based approach only performs well on transactions that can be
perfectly partitioned into disjoint groups, given that acquiring partition-
level locks on cross-partition states significantly impacts performance due to
the overhead.

_b) Dynamic partition-based:_ These approaches involve decomposing
transactions into smaller steps and executing them in parallel to improve
performance while ensuring serializability and meeting event order constraints
(e.g., TStream tstream  and MorphStream mao2023morphstream ).

The _sagas_ model sagas  allows a transaction to be split into several smaller
steps, each of which executes as a transaction with an associated compensating
transaction. Either all steps are executed or in a partial execution
compensating transactions are executed for steps that are completed. Thus,
isolation is relaxed in the original transaction and delegated to the
individual steps. It exposes an intermediate (uncommitted) state and requires
developers to define compensating actions. A similar idea of splitting
transactions has been adopted in TSP systems such as TStream tstream  and
MorphStream mao2023morphstream  but does not expose uncommitted states and
hence does not require compensating actions.

In particular, TStream tstream  is a recently proposed TSP system that adopts
transaction decomposition to improve stream transaction processing performance
on modern multicore processors. Despite the relaxed isolation properties,
TStream ensures serializability, as all conflicting operations (being
decomposed from the original transactions) are executed sequentially as
determined by the event sequence. The successor of TStream tstream ,
MorphStream pushes the idea further and proposes cost-model guided dynamic
transaction decomposition and scheduling to further improve the system
performance.

##### Optimistic Approach:

Optimistic approaches avoid locking resources by employing timestamps and
conflict detection mechanisms to maintain transaction consistency at the
desired isolation level, aborting and rescheduling transactions when
necessary. These approaches handle transactions by predicting the order of
events or by performing speculative execution to improve system performance.
The challenge is to ensure that speculation is accurate and efficiently
manages rollback or recovery when needed.

Golab et al.golab2  present a scheduler targeting _window serializable_
properties, which optimistically executes window movements and utilizes
serialization graph testing (SGT) to abort any _read-only_ transactions
causing read-write conflicts. A conflict-serializable schedule is achieved if
the precedence graph remains acyclic. They also suggest reordering read
operations within transactions to minimize the number of aborted transactions,
thereby improving the schedule. FlowDB/TSpoonAFFETTI202065 ;
Affetti:2017:FIS:3093742.3093929  propose an optimistic timestamp-based
protocol that refrains from locking resources and instead uses timestamps to
ensure transactions consistently read or update versions aligned with the
desired isolation level. If this is not feasible, transactions are aborted and
rescheduled for execution. This approach aims to minimize contention and
improve performance by avoiding lock-based mechanisms while still maintaining
the necessary consistency and isolation requirements.

##### Snapshot Isolation Approach:

These approaches employ snapshot isolation to split a stream into a sequence
of bounded chunks and apply database transaction semantics to each chunk.
Processing a sequence of data chunks generates a sequence of state snapshots.
By storing multiple versions of values as commit and delete timestamps,
readers can access the latest version of a state, ensuring consistency and
isolation among concurrent transactions.

A number of TSP systems employ snapshot isolation abadi2005design ;
botan2012transactional ; Chen11 ; Chen10 ; Gtze2019SnapshotIF , aiming to
split a stream into a sequence of bounded chunks and apply the semantics of a
database transaction to each chunk. By putting the operation on a data chunk
within a transaction boundary, a state snapshot is produced. In this way,
processing a sequence of data chunks generates a sequence of state snapshots.
For example, Götze and Sattler Gtze2019SnapshotIF  present a snapshot
isolation approach for TSP. Each state has multiple versions of values, each
stored as a _commit timestamp_ , _delete timestamp_ , and _value_.
Consequently, readers can access the latest version of a state using the
commit and delete timestamps. This approach provides consistency and isolation
among concurrent transactions while avoiding the need for locking mechanisms,
which can improve system performance.

####  3.2.4 Ensuring Delivery Guarantees

In this subsection, we explore various design aspects of TSP systems that help
ensure reliability and delivery guarantees. We discuss strategies for
achieving ACID properties and streaming properties under failures and their
implications on TSP system design. For a comprehensive survey on fault
tolerance mechanisms in SPEs, refer to state_survey . While modern SPEs
usually offer fault-tolerance mechanisms while ensuring various delivery
guarantees, they may not always fulfil the requirements of TSP due to the
combined need to satisfy ACID and streaming properties.

##### Achieving ACID Properties:

In the event of a failure, TSP systems generally need to recover all states,
including input/output streams, operator states, and shared mutable states.
This ensures committed transactions remain stable, while uncommitted
transactions do not impact this state. Transactions that have started, but
have not yet been committed should be undone upon failure and reinvoked with
the correct input parameters once the system is stable again. This
necessitates an upstream backup and an undo/redo mechanism akin to an ACID-
compliant database.

For instance, TSP systems must guarantee _atomicity_ when updating shared
states, even under failures. An atomic transaction ensures a commit either
fully completes the entire operation or, in cases of failure (e.g., system
failures or transaction aborts), rolls back the database (or shared states in
TSP) to its pre-commit state. Journaling or logging in database systems mainly
accomplish atomicity, while distributed database systems require additional
atomic commit protocols to ensure atomicity. Regrettably, most prior works on
TSP either do not explicitly mention their mechanisms to ensure atomicity
under failure tstream ; Affetti:2017:FIS:3093742.3093929  or rely on
mechanisms provided by their storage systems (e.g., traditional database
systems S-Store ). Making this more transparent could help users better
understand which properties are not guaranteed when employing a TSP system in
practice.

##### Achieving Streaming Properties:

To satisfy streaming properties further, the recovered states in TSP systems
should be equivalent to the one under construction when no failure occurred.
Achieving this requires an order-aware recovery mechanism Clonos . However,
the commonly adopted recovery operation in modern SPEs, particularly the
parallel recovery operation, might result in different transactional states
due to the absence of guarantees on the event processing sequence during
recovery. To the best of our knowledge, there is still no in-depth study on
designing efficient fault tolerance mechanisms for TSP systems.

Additionally, ††margin: distributed SPEs often adopt a form of eventual
consistency 10.1145/2460276.2462076  to ensure high availability, as states
exposed to the external world are expressed as output streams, and instant
consistency of the global system state is hidden from users. Eventual
consistency informally guarantees that if no new updates are made to a given
data item, all accesses to that item will eventually return the last updated
value. However, it is unclear how such a relaxed model (i.e., eventual
consistency) can be applied to TSP to achieve fault tolerance and high
availability, given that shared mutable states (or their snapshot) need to be
immediately visible and queryable both internally and externally to the
system.

####  3.2.5 Implementing State Management

State ††margin: management is a crucial aspect of transactional stream
processing (TSP) systems, as it enables the coordination of concurrent
transactions, maintains consistency, and provides fault tolerance tstream ;
millwheel . The design space for state management in TSP systems can be
characterized by several dimensions, such as access scope, storage model, data
manipulation statements, and state management strategies. Next, we delve into
these dimensions and explore their implications for system design and
optimization.

##### Access Scope:

The access scope of state management ranges from intra-operator to inter-
systems. Depending on the application’s requirements, TSP systems may need to
manage state locally within a processing node or share state across multiple
nodes or even external systems Gtze2019SnapshotIF ; flink . It is worth noting
that when OLTP workloads are implemented in a TSP system, the access scope of
a shared state is within a transaction, which can be attributed to a single
operator or multiple operators. _a) Intra-operator state management_ focuses
on maintaining state among instances of a single operator, making it suitable
for applications with localized data access patterns and minimal coordination
requirements golab2 . _b) Inter-operator state management_ involves sharing
state across multiple operators within the same query/system tstream ;
Affetti:2017:FIS:3093742.3093929 . This approach is particularly relevant for
applications that require coordination among different operators. _c) Inter-
system/global state management_ extends the scope of state sharing even
further, enabling TSP systems to exchange state information with external
systems, such as other stream processors, databases, or distributed file
systems meehan2017data . This approach allows TSP systems to leverage the
capabilities of external systems, such as query processing or storage, and can
facilitate seamless integration with existing data processing pipelines.
However, managing state across system boundaries can introduce additional
complexity, latency, and potential consistency issues.

##### Storage Models:

There are two primary storage models for implementing state management in TSP
systems: relations and key-value pairs. Each has its trade-offs and
implications for system design and optimization.

_a) Relations:_ In this model, states are represented as time-varying
relations that map a time domain to a finite but unbounded bag of tuples
adhering to a relational schema stream2003stream ; S-Store . This approach
leverages well-developed techniques from relational databases, such as
persistence and recovery mechanisms. Storing states as relations can help
minimize system complexity, especially when a foreign key constraint is
required in TSP meehan2017data . However, incorporating time into the
relational model can add complexity to query processing and optimization
stream2003stream .

Representative examples include STREAM, S-Store, and TStream. STREAM
stream2003stream  represents the state as a time-varying relation, mapping a
time domain to a finite, but unbounded bag of tuples adhering to the
relational schema. To treat relational and streaming data uniformly, STREAM
introduces two operations: _To_Table_ to convert streaming data to relational
data, and _To_Stream_ to convert relational data to streaming data. S-Store
S-Store  does not implement its own state management component, but instead
relies on H-Store HStore  to ensure the transactional properties of shared
states represented as relations. TStream tstream  uses the Cavalia relational
database Wu:2017:EEI:3067421.3067427  to support the storage of shared states.

_b) Key-Value Pairs:_ In this model, states are represented as key-value
pairs, which simplifies the design of TSP systems millwheel ; flink . This
approach is suitable for scenarios that mainly require select and update
statements for manipulating shared states during stream processing
AFFETTI202065 ; mao2023morphstream . However, it may not be the best choice
for applications that require more complex data manipulation operations or
constraints, such as foreign key constraints meehan2017data .

Representative examples include MillWheel millwheel , Flink with RocksDB, AIM
(Analytics in Motion)AIM15 , FlowDBMS/TSpoonAFFETTI202065 ;
Affetti:2017:FIS:3093742.3093929 , and TStream/MorphStream tstream ;
mao2023morphstream . MillWheel millwheel  maintains state as an opaque byte
string on a per-key basis, with users implementing serialization and
deserialization methods. The persistent state is backed by a replicated and
highly available data store, such as Bigtable chang2008bigtable  or Spanner
corbett2013spanner , ensuring data integrity and transparency for the end
user. Flink flink  relies on an LSM-based key-value store engine called
RocksDB rocksdb  to support shared queryable state. G”otze and Sattler
Gtze2019SnapshotIF  also adopt a key-value store for transactional state
representation, using multi-version concurrency control, where each state
(i.e., key) has multiple _commit timestamps_ , _delete timestamps_ , or
_values_.

AIM AIM15  represents state in a distributed in-memory key-value store, where
nodes store system state as horizontally-partitioned data in a _ColumnMap_
layout. The _Analytics Matrix_ system state provides a materialized view of
numerous aggregates for each individual customer (subscriber). When an event
arrives in an SPE, the corresponding record in the _Analytics Matrix_ is
updated atomically. In FlowDBMS/TSpoon AFFETTI202065 ;
Affetti:2017:FIS:3093742.3093929 , a key-value store is employed, with the
state maintained by a special type of stateful stream operator called the
_state operator_. All state access requests must be routed to and subsequently
handled by state operators defined in the application.

##### Data Manipulation Statements:

TSP systems need to define and support different data manipulation statements
employed in applications that constrain both system design and potential
optimizations. These statements may include operations such as insert, update,
delete, and query, which must be executed efficiently and consistently in the
context of transactional stream processing.

Storing shared states as relations could be a reasonable choice of system
design when applications require _insert_ (I) or _delete_ (D) statements and
need to maintain foreign key constraints, such as in the case of streaming ETL
meehan2017data . However, when applications only need _select_ (S) and
_update_ (U) statements for manipulating shared states during stream
processing, storing shared states as vanilla key-value pairs is sufficient and
simplifies the design of TSP systems. Specific optimizations should be adopted
by the TSP systems according to application needs.

##### State Management Strategies:

The choice of state management strategy can significantly impact system
performance, fault tolerance, and scalability millwheel ; flink ; HStore .
There are three main strategies for managing state in TSP systems: _a) In-
memory state:_ This strategy maintains state within the processing nodes’
memory, enabling low-latency access. However, it can be limited by available
memory and may require replication and distributed transactions for fault
tolerance and consistency guarantees AIM15 ; tstream . _b) External state
stores:_ In this strategy, state is stored in external systems, such as
transactional databases or distributed key-value stores with transactional
support Gtze2019SnapshotIF ; rocksdb . This approach allows for improved fault
tolerance, consistency guarantees, and scalability but may introduce
additional latency chang2008bigtable ; corbett2013spanner . _c) Hybrid state
management:_ This approach combines the advantages of in-memory state and
external state stores, using in-memory caching to minimize latency and
external transactional storage for fault tolerance, consistency guarantees,
and scalability AFFETTI202065 ; Affetti:2017:FIS:3093742.3093929 .

######  Remark 2 (Failure of Concurrency Control Protocols)

Conventional concurrency control (CC) protocols, which are widely used in OLTP
database systems, fail to guarantee the properties of TSP Systems. To
illustrate why, we use a conventional timestamp-ordering concurrency control
(T/O CC) Bernstein:1981:CCD:356842.356846  as an example. Similar discussions
can be also found in a prior work ACEP . Let $txn_{1}=write(k1,v1)$ and
$txn_{2}=read(k1)$ be two distinct transactions. For simplicity, let us assume
that there are only these two transactions in the system. If
$txn_{2}.ts>txn_{1}.ts$, then both $txn$ will be successfully committed.

However, their serial order would be $txn_{2}\rightarrow txn_{1}$, which
violates the event order constraint (i.e., $txn_{2}$ will wrongly read the
original value of $k1$). On the other hand, if $txn_{2}.ts<txn_{1}.ts$, then
$txn_{2}$ will be successfully committed. However, $txn_{1}$ will be aborted
as the writes will come too late. Aborting a transaction that represents an
undo of an externally visible output or action may not be acceptable in TSP
applications.

Similarly, in other conventional CC protocols, either the results are in the
wrong serial order or one of the transactions has to be aborted, which
eventually will result in the wrong serial order upon a restart. In other
words, conventional CC protocols are not yet ready for such _event-driven_
transaction execution.

Figure 4: Example of timestamp assignment dilemma.

######  Remark 3 (Timestamp Assignment Dilemma)

In TSP systems, a transaction triggered by a corresponding input event should
ideally take effect with minimal latency after the event occurs ACEP . This
concept is related to external consistency or linearizability in distributed
systems theory. ††margin: In this setting, the timestamp of the transaction is
set to be the same as the timestamp of its corresponding triggering event.
When all transactions are generated by external events, the transaction
schedule is aligned with an external event sequence, satisfying the event
ordering constraint.

However, a dilemma arises when transactions can also be generated by internal
events (i.e., outputs generated by operators) with timestamps assigned
according to input events, as illustrated in Figure 4. In the DAG, each
operator can produce output streams and generate stream transactions. Suppose
operator A receives input event $e$ and generates two events $e_{a}$ and
$e_{a}^{\prime}$, passed to operators B and C, respectively. Further, suppose
operator C processes $e_{a}^{\prime}$, generates $e_{c}$ as an output, and
then passes $e_{c}$ to operator B. Now, let us assume operator B processes two
events $e_{a}$ and $e_{c}$ and generates two transactions $txn_{e_{a}}$ and
$txn_{e_{c}}$, respectively. In addition, operator C processes event
$e_{a}^{\prime}$ and generates transaction $txn_{e_{a}}^{\prime}$. On the one
hand, $txn_{e_{a}}$ must be committed jointly with $txn_{e_{c}}$, for
otherwise, the event ordering constraint would be violated. On the other hand,
$txn_{e_{c}}$ cannot be generated before $txn_{e_{a}}^{\prime}$ is committed,
for otherwise, this would violate the operator ordering constraint, which
means $txn_{e_{a}}$ is unable to be committed. The system then runs into a
deadlock situation, where $txn_{e_{a}}$ and $txn_{e_{a}}^{\prime}$ are
infinitely waiting for each other to be committed.

There are two approaches to prevent this dilemma: 1) an additional ordering
constraint can be enforced between operators B and C, or 2) different
timestamps could be assigned to the generated events: $e_{a}$,
$e_{a}^{\prime}$, and $e_{c}$. However, to date, we are not aware of any
generally efficient solution to address such a dilemma.

###  3.3 Technologies Employed in TSP Implementation

This section delves into the practical aspects of implementing TSP systems,
such as the choice of programming languages and APIs, system architectures,
and the integration of various components to achieve a well-rounded TSP
system. We also discuss performance metrics and evaluation criteria for TSP
systems.

####  3.3.1 Languages and APIs

TSP systems should provide user-friendly and expressive languages that can
easily define complex transactions, data manipulations, and processing logic
over data streams while addressing aspects such as ordering properties, state
management, and delivery guarantees. However, TSP systems do not yet have a
standard transaction model or language, which complicates the selection of
appropriate languages and APIs. Let us examine both declarative languages and
functional languages in turn.

##### Declarative Languages:

The STREAM system motwani2002query ; stream2003stream ;
Arasu:2006:CCQ:1146461.1146463  supports a declarative query language called
CQL (Continuous Query Language), which is designed to handle both relational
data and data streams. Coral8’s Coral8  continuous computation language (CCL)
has a SQL-like syntax and supports both data streams and event streams.
Franklin et al. Franklin2009ContinuousAR  introduced TruSQL, a relational
stream query language that fully integrates stream processing into SQL,
including persistence. These relational stream query ††margin: languages are
well-suited for TSP when handling a single query at a time. However, they may
not sufficiently address TSP-specific issues like isolation and concurrent
execution of queries. Declarative languages need to be extended to provide
proper isolation guarantees. Moreover, they need to facilitate the correct
interaction among queries by incorporating features that explicitly express
proper interactions or defining interaction constraints as separate rules.

##### Functional Languages:

Functional languages millwheel , influenced by MapReduce-like APIs are more
suitable for expressing state abstractions and complex application logic than
SQL-like declarative languages. Streaming systems, like Flink embed
functional/fluent APIs into general-purpose programming languages, which allow
users to define custom dataflows akin to the Aurora system Aurora . This
design is also present in TSP systems, such as FlowDBMS and TStream
AFFETTI202065 ; Affetti:2017:FIS:3093742.3093929 ; tstream . These languages
offer greater flexibility and expressiveness, enable developers to create
custom processing logic, and leverage existing functional programming
paradigms. However, they may introduce additional complexity and a steeper
learning curve for developers new to TSP systems. Further research is needed
to explore the trade-offs between the simplicity of declarative languages and
the flexibility of functional languages, as well as to develop new programming
constructs and abstractions that strike a balance between the two approaches,
considering the transactional requirements of TSP systems.

####  3.3.2 System Architectures

Given the properties and requirements discussed, TSP applications usually
necessitate the use of SPEs in conjunction with data storage and analysis
frameworks, such as database management systems (DBMSs), to create software
architectures that integrate data storage, retrieval, and mining. Three
approaches can be employed to construct a TSP system: 1) extending a DBMS, 2)
embedding a DBMS in an SPE, and 3) composing a DBMS and an SPE. The choice of
architectural approach for TSP systems depends on the specific requirements
and constraints of the stream processing application. Each approach offers a
unique set of trade-offs and considerations, making them more or less suitable
for different use cases. By understanding the strengths and weaknesses of each
approach, developers can make informed decisions when designing and
implementing TSP systems to meet the needs of their applications. Next, we
explore each approach in turn.

(a) Extending a DBMS

(b) Embedding a DBMS in a SPE

(c) Composing a DBMS and an SPE

Figure 5:  Illustrations of alternative system architectures of TSP systems.

##### Extending a DBMS:

Extending a DBMS for TSP involves incorporating stream processing
functionality into traditional database management systems. By doing so, these
systems aim to provide a unified platform for stream processing and
traditional database management tasks while maintaining the strong
consistency, isolation, and fault tolerance properties of traditional
databases. Since state is managed ††margin: directly within the DBMS, it can
be shared across queries and operators, and provide durability and
consistency. Since transactions are supported in the underlying DBMS, it
offers strong consistency guarantees. This setup is particularly advantageous
in applications, such as financial systems, where the integrity and
correctness of the data are paramount.

Notable examples of this approach include DataCell Liarou2009DataCellBA ,
MaxStream Botan09 , Truviso Continuous Analytics system (TruCQ) Sailesh10 ,
and S-Store S-Store . While extending a DBMS for TSP offers a unified
platform, it also has limitations, such as difficulty in efficiently
supporting native or hybrid stream processing applications and challenges in
handling real-time processing and stateful operations. Consequently,
alternative approaches might be more suitable for specific TSP applications.

Advantages of this approach include: a) leveraging the existing features and
infrastructure of a DBMS for transactional support, query processing, and data
management; b) simplifying the system architecture by integrating stream
processing functionality within the DBMS, reducing the need for additional
components or interfaces; and c) potentially providing strong consistency
guarantees by directly utilizing the transactional mechanisms of the
underlying DBMS. Disadvantages include: a) potentially being less flexible and
adaptable to the specific requirements of stream processing applications, as
it inherits the architectural constraints of the underlying DBMS; and b)
possibly having limited scalability and performance due to the constraints of
the underlying DBMS, which may not be designed for high-velocity, high-volume
data streams.

##### Embedding a DBMS in an SPE:

The embedding approach involves integrating an SPE with an embedded key-value
store or DBMS to manage state, provide transactional support, and handle
storage capabilities. This method enables stream processing systems to take
advantage of the features of the embedded DBMS while maintaining the
flexibility and efficiency of stream processing. In this approach, state
management occurs within the embedded DBMS, which can also be shared across
queries and operators. However, the sharing model depends on the specific
integration between the SPE and the embedded DBMS. Durability can be achieved
via the underlying DBMS.

Examples of this approach include Aurora Aurora  and its successor Borealis
abadi2005design , TStream tstream  and its successor MorphStream
mao2023morphstream . Embedding a DBMS within an SPE allows for various
transactional models over streams but also introduces challenges such as
integration complexity and potential performance bottlenecks or resource
contention issues. This approach is better suited for applications that
require a balance between the performance and scalability of stream processing
and the transactional support and data management capabilities of a DBMS. It
can be particularly useful when the stream processing workload is dynamic and
demands efficient state management and transactional support. Examples of such
applications include real-time analytics, social network analysis, and large-
scale data processing tasks like log analysis or clickstream processing.

Advantages of this approach include: a) enabling TSP systems to benefit from
the features of both the SPE and the embedded DBMS, combining their strengths
and providing a unified platform for stream processing; and b) offering
improved performance and scalability by facilitating concurrent data
processing and state management, as well as leveraging the distributed nature
of modern SPEs. Disadvantages of this approach include: a) necessitating
careful integration of the embedded DBMS with the SPE, which may increase
complexity and impact overall system latency; and b) the performance of the
embedded DBMS might be influenced by the stream processing workload,
potentially causing bottlenecks or resource contention issues. These problems
can be mitigated by carefully tuning the embedded DBMS for the specific use
case.

##### Composing a DBMS and an SPE:

The composing approach involves using both a DBMS and an SPE in conjunction
while keeping them as separate components. This method offers flexibility,
adaptability, and optimizability for various application requirements. The SPE
primarily focuses on processing streams, while the DBMS handles state
management, transactional support, and storage capabilities. In this approach,
state is managed within the DBMS, while the SPE processes the streams. Sharing
state across queries and operators depends on the communication and
synchronization between the SPE and DBMS. Durability can be achieved via the
underlying DBMS, but the communication latency between the components can
impact performance.

Examples of this approach include Storage Manager for Streams (SMS) SMS .
Although composing a DBMS and an SPE is more complex than other approaches and
introduces additional challenges, such as performance overhead and latency in
communication between the systems, it provides a flexible and scalable
solution for building TSP systems that can leverage the strengths of both
components. The composing approach is well-suited for applications requiring
high levels of flexibility, adaptability, and performance, as well as the
ability to separately optimize and customize the SPE and the DBMS components.
It is particularly useful for applications with diverse and evolving
requirements, as it enables the system to be easily adapted or extended to
accommodate new functionality or optimizations. Examples of such applications
include IoT systems, sensor networks, and other data-intensive applications
with varying processing and storage requirements.

Advantages of this approach include: a) offering the most flexibility and
adaptability by allowing separate optimization and customization of the SPE
and the DBMS, enabling tailored solutions for specific application
requirements; and b) providing better scalability and performance by
distributing workloads across multiple systems and enabling parallelization of
processing tasks. Disadvantages of this approach include: a) demanding
additional effort to ensure integration correctness, which may increase
development and maintenance complexity. This challenge can be mitigated by
using standardized interfaces and middleware for communication between the SPE
and the DBMS; and b) potentially exhibiting higher latency due to the need for
communication and synchronization between the SPE and the DBMS. However, this
can be mitigated by optimizing communication protocols and leveraging caching
techniques to minimize data exchange overhead.

####  3.3.3 Performance Metrics of TSP Systems

In this subsubsection, we discuss the key performance metrics and evaluation
criteria for transactional stream processing systems. These metrics help in
understanding the efficiency and effectiveness of various TSP architectures,
as well as in identifying the trade-offs associated with different system
designs.

##### Throughput:

Throughput is a measure of the number of transactions or events processed per
unit of time. High throughput is desirable in TSP systems, as it indicates the
system’s capability to handle large volumes of data efficiently. Throughput
can be affected by factors such as system architecture, resource allocation,
and workload characteristics. TSP systems should be designed to maximize
throughput while maintaining other performance guarantees, such as low latency
and correctness.

##### Latency:

Latency is the time taken for a transaction or event to be processed by the
TSP system, from the moment it enters the system until it is completely
processed. Low latency is crucial for TSP systems, as many real-time
applications require timely processing of data. Latency is influenced by
factors such as system architecture, data processing complexity, and resource
utilization. TSP systems should be designed to minimize latency, ensuring that
transactions are processed quickly without compromising other performance
aspects.

##### Scalability:

Scalability measures the ability of a TSP system to handle increasing amounts
of data and concurrent transactions without significant performance
degradation. As the volume of data and the number of concurrent transactions
grow, TSP systems must be able to scale effectively to maintain low-latency
access and fault tolerance. Techniques such as data sharding, partitioning,
and replication can be employed to distribute the shared mutable state across
multiple nodes, providing horizontal scalability.

##### Correctness Guarantee:

Correctness guarantee in TSP systems refers to the extent to which a system
can ensure data consistency and maintain the required transaction properties,
as discussed in subsection 3.1, in the presence of failures, network delays,
or other factors. This includes support for various isolation levels,
consistency models, and durability guarantees. TSP systems should be designed
to provide the appropriate level of correctness guarantees based on the
specific requirements of the stream processing application.

  * $\bullet$

Isolation Levels: TSP systems should maintain proper isolation levels (e.g.,
serializable, snapshot isolation, read committed) to ensure that concurrent
transactions do not interfere with each other and result in incorrect data
processing.

  * $\bullet$

Consistency Models: Different TSP systems may adopt different consistency
models (e.g., strong consistency, eventual consistency, or causal consistency)
to provide a balance between data correctness and system performance. The
choice of consistency model should be aligned with the application
requirements and the tolerance for temporary inconsistencies.

  * $\bullet$

Durability Guarantees: TSP systems should ensure that once a transaction is
committed, its effects are permanently recorded, even in the presence of
failures. This can be achieved through techniques such as logging,
checkpointing, and replication.

Balancing correctness guarantees with other performance metrics, such as
throughput and latency, is crucial for achieving optimal performance in TSP
systems. It is essential to recognize that the choice of the appropriate
correctness guarantee is highly dependent on the application’s requirements
and the nature of the data being processed. For some applications, strong
consistency and high isolation levels might be necessary, while for others,
relaxed consistency models and lower isolation levels might be sufficient.

##  4 Systems Offering Transactional Stream Processing

We summarize six notable transactional stream processing (TSP) systems in
Table 2. These TSP systems showcase the various approaches used to address the
challenges in transactional stream processing. Each system offers unique
features and each has made some design choices that cater to different
application requirements. Let us explore each of these systems in turn, to
gain some insight into the design and implementation of TSP systems. ††margin:

Table 2: Key characterization of Six Transactional Stream Processing Systems

System |  Unique Features |  Properties |  Design Aspects |  Implementation Details
---|---|---|---|---
STREAM |  first unified framework |  ACID, ordering, at-least-once |  unified transaction, lock-based approach |  embedding a DBMS in an SPE
Botan et al. |  pipelined architecture |  ACID, ordering |  unified transaction, per-tuple transactions |  embedding a DBMS in an SPE
S-Store |  static partitioning |  ACID, ordering, exactly-once, at-least-once |  state-transaction, per-store-procedure-invocation transaction |  extending a DBMS
Braun et al. |  in-database stream analytics |  ACID, ordering |  state transaction, per-tuple transactions |  extending a DBMS
FlowDB |  transactional state management on Flink |  ACID, ordering, exactly-once |  state transaction, user-defined transaction boundary |  embedding a DBMS in an SPE
TStream /MorphStream |  dual-mode scheduling |  ACID, ordering, exactly-once |  state transaction, per-tuple transactions |  embedding a DBMS in an SPE

##### STREAM:

STREAM stream2003stream  is an early TSP system that introduces a unified
framework for continuous query processing over data streams and relations. It
supports ACID properties and offers at-least-once delivery guarantees.
STREAM’s design approach is based on a combination of a sliding-window model
and a relational model for efficiently processing continuous queries. It
employs a language called CQL (Continuous Query Language) to express queries,
which can be translated into efficient query plans for execution. STREAM
supports ACID properties and at-least-once delivery guarantees. The system
focuses on ordering properties and state management properties by using
windows and panes for efficient state handling. The architecture of STREAM is
centered around a relational model, which simplifies the integration of stream
processing and transaction processing.

##### Botan et al.:

Botan et al. botan2012transactional  proposed a TSP system that focuses on a
pipelined architecture for efficient parallel execution. The system supports
ACID properties, but does not explicitly specify the delivery guarantees. Its
design approach is centered around per-tuple transactions, which ensures
strong consistency guarantees and high isolation. Botan et al. also address
the challenges of implementing transactional guarantees in a stream processing
environment, such as handling failures and maintaining consistency among
shared mutable state. They propose techniques for addressing these challenges,
including state replication, checkpointing, and recovery mechanisms. The
system adheres to ACID properties, while delivery guarantees are not
explicitly mentioned. The system addresses fault tolerance and durability by
employing state replication, checkpointing, and recovery mechanisms.

##### S-Store:

S-Store S-Store  is a state-transaction TSP system that builds upon H-Store, a
distributed, main-memory relational database system. It extends H-Store with
stream processing capabilities and supports ACID properties. S-Store offers
various delivery guarantees, such as exactly-once and at-least-once processing
semantics. The system employs a partitioning mechanism for efficient parallel
execution of stream processing tasks. In S-Store, each transaction is
represented as a stored procedure, which can be invoked by incoming data
streams. These stored procedures manipulate shared mutable states within the
context of ACID-compliant transactions, ensuring consistency and isolation
among concurrent tasks. S-Store supports ACID properties, exactly-once and at-
least-once delivery guarantees, and employs a partitioning mechanism for
distributed and parallelized execution. S-Store also focuses on fault
tolerance techniques, including state replication, checkpointing, and
recovery.

##### Braun et al.:

Braun et al. AIM15  presented a TSP system that focuses on in-database
analytics by combining event-processing and real-time analytics within the
same database. The system supports ACID properties. However, the delivery
guarantees are not explicitly specified. Its design approach is centered
around in-database stream processing, which allows the system to efficiently
handle complex event processing and real-time analytics tasks without
requiring external tools or components. The system supports ACID properties,
while delivery guarantees are not specified. The system also emphasizes
performance metrics and evaluation of TSP systems, showcasing its efficiency
in handling large volumes of data and complex analytics tasks.

##### FlowDB:

FlowDB Affetti:2017:FIS:3093742.3093929  is a TSP system that integrates
stream processing and consistent state management. It supports ACID properties
and provides exactly-once delivery guarantees. The system’s design approach is
based on a state-transaction model, which allows for efficient management of
shared mutable state. FlowDB features a language called FQL (Flow Query
Language) for expressing continuous queries and supports the integration of
custom stream processing operators and user-defined functions. FlowDB supports
ACID properties, exactly-once delivery guarantees, and efficient state
management. It also addresses fault tolerance and durability by employing
checkpointing and recovery mechanisms.

##### TStream/MorphStream:

TStream tstream  and its successor MorphStream mao2023morphstream  are TSP
systems that emphasize efficient concurrent state access on multicore
processors. These systems support ACID properties and offer exactly-once
delivery guarantees. TStream’s design approach includes a unique dual-mode
scheduling strategy that combines transactional and parallel modes, to enable
the system to maximize parallelism opportunities offered by modern multicore
architectures. TStream’s dynamic restructuring execution strategy further
improves concurrency by adapting the execution plan based on observed state
access patterns during runtime. Unlike other works, TStream focuses on
improving the performance of concurrent state access on multicores with
efficient execution mechanisms, and delivery guarantees.

##  5 Applications/Scenarios Leveraging TSP

TSP arises in varying domains, such as healthcare ACEP , the Internet of
Things (IoT) botan2012transactional , and e-commerce
Affetti:2017:FIS:3093742.3093929 ). Table 3 summarizes thirteen scenarios.
Each application encompasses diverse features, transactional models, and
implementations of TSP systems. We can categorise them into four scenarios:
_stream processing optimization_ , _concurrent stateful processing_ , _stream
& DBMS integration_, and _recoverable stream processing_.

| Scenario | Ordering | ACID | State Management | Reliability
---|---|---|---|---|---
Stream Processing Optimization
1 | Sharing Intermediate Results | event, operation | ACID | read-write, inter-operator | consistency
2 | Multi-Query Optimization | event | ACID | read-write, global | delivery guarantee
3 | Deterministic Stream Operations | event | ACID | read-write, intra & inter-operator | -
4 | Prioritizing Query Scheduling | event | ACID | read-write, inter-query | delivery guarantee
Concurrent Stateful Processing
5 | Ad-hoc Queryable States | event, operation | ACID | read-write, global | consistency, durability
6 | Concurrent State Access | event, operation | ACID | read-write, intra & inter-operator | consistency, durability
7 | Active CEP | event | ACID | read-write, inter-Query | delivery guarantee, durability
Stream and DBMS Integration
8 | Streaming Ingestion | event | ACID | read-write, global | delivery guarantee, durability
9 | Streaming OLTP | operation | ACID | read-write, per-transaction | consistency, durability
10 | Streaming OLAP | event (optional) | snapshot | read-write, global | delivery guarantee, fault tolerance
Robust Stream Processing
11 | Shared Persistent Storage | operation | ACID | read-write, global | consistency, durability
12 | Transaction Identifier | operation | ACID | read-write, global | consistency, durability
13 | Fault Tolerance Outsourcing | operation | ACID | read-write, global | fault tolerance, durability
Table 3: Summary of application scenarios and their demands of TSP properties.

###  5.1 Stream Processing Optimization

Several works have proposed the consistent management of shared mutable states
to optimize stream processing. Below we discuss these works in the context of
stream processing optimization across four use cases: _sharing intermediate
results_ , _multi-query optimization_ , _deterministic stream operations_ ,
and _prioritizing query scheduling_.

Sharing Intermediate Results. In the STREAM system stream2003stream , nearly
identical states, or synopses, within a query plan are kept in a single store
to reduce storage redundancy. Operators access their states exclusively via a
stub interface. As operators are scheduled independently, they require
slightly different data views, so STREAM employs a timestamp-based execution
mechanism for correctness. Ordering properties are crucial in this scenario.
Event ordering constraints maintain the data stream order, while operation
ordering constraints ensure transaction operations’ order. ACID properties
maintain the correctness and consistency of shared mutable states. State
management properties require read-write state types and inter-operator access
scope for managing shared states among different operators.

Multi-Query Optimization. Ray et al. SPASS  introduced the SPASS (Scalable
Pattern Sharing on Event Streams) framework, which optimizes time-based event
correlations among queries and shares processing effectively. The optimizer
identifies a shared pattern plan, maintaining an optimality bound. The runtime
then uses shared continuous sliding view technology for executing the shared
pattern plan. A sequence transaction model on shared views defines the
correctness of concurrent shared pattern execution. SPASS doesn’t modify
existing states but selects, inserts, and deletes shared states like sliding
views. Ordering properties are crucial for maintaining the correct order of
pattern queries. Event ordering constraint preserves data stream order, while
operation ordering constraint is less important as sharing is among queries.
ACID properties maintain consistency and correctness of shared states like
sliding views. State management properties need read-write state types and
global access scope for managing shared states among pattern queries. However,
some implementation details are not specified in the original paper (e.g.,
sliding views’ data layout, key used for searching shared sliding views).

Deterministic Stream Operations. Handling out-of-order streams is often a
performance bottleneck due to the conflict between data parallelism and order-
sensitive processing. While data parallelism improves throughput by processing
events concurrently, it can cause events to be handled out-of-order. Most
solutions use locks or non-lock algorithms like sorting survey_hwstream .
Brito et al. OOO_STM  proposed an interesting non-lock approach using software
transactional memory (STM) for stream processing. They model processing a
batch of input data at order-sensitive operators as a transaction and pre-
assign commit timestamps, effectively imposing order. Events received out-of-
order or conflicting are processed in parallel optimistically but aren’t
output until all preceding events are completed, ensuring consistent operator
states. Ordering Properties are crucial for managing out-of-order streams,
with event ordering constraint needed to maintain data stream order. Operation
ordering constraint is less relevant. ACID Properties maintain correctness and
consistency of shared mutable states, especially when handling out-of-order
and conflicting events. State Management Properties require read-write state
types and intra- and inter-operator access scope for managing shared states
within and among different operators.

Prioritizing Query Scheduling. Handling potentially infinite data streams
requires continuous queries with window constraints to limit tuple processing.
Most implementations execute sliding window queries and window updates
serially, implicitly assuming a window cannot be advanced while accessed by a
query. Golab et al.golab2  argue that concurrent processing of queries (reads)
and window-updates (writes) is necessary for prioritized query scheduling to
improve answer freshness. They model window updates and queries as
transactions with atomic sub-window reads and writes, which can lead to read-
write conflicts. Golab et al.golab2  prove traditional conflict
serializability is insufficient and define stronger isolation levels
restricting allowed serialization orders following event ordering. Ordering
Properties are crucial for prioritizing query scheduling, with event ordering
constraint ensuring correct data stream order. ACID Properties maintain
correctness and consistency of shared mutable states when handling concurrent
reads and writes. State Management Properties require read-write state types
and inter-query access scope for managing shared states among different
queries and window updates.

###  5.2 Concurrent Stateful Processing

In this scenario, application workloads consist of both ad-hoc and continuous
queries, which may access and modify common application states for future
reference flinkstate . We will discuss three representative applications in
the context of concurrent stateful processing: _ad-hoc queryable states_ ,
_concurrent state access_ , and _active complex event processing_ , focusing
on the properties of TSP required by each application.

Ad-hoc Queryable States. Ad-hoc queries, or snapshot queries, can be submitted
to an SPE anytime, executed once, and provide insights into the system’s
current state. They may be used to obtain further details in response to
continuous query result changes. In Botan et al.’s example
botan2012transactional , real-time sensors generate temperature measurements
to ensure temperature-sensitive devices operate within design specifications.
When a temperature reading falls out of the operating range, it triggers an
alert. The SPE must ensure table updates and stream temperature readings are
executed in the correct order, demanding event and operation ordering
constraints. To maintain the specifications table’s integrity and prevent data
corruption, ACID Properties are necessary. The state is read-write, as the
table needs updates, and the access scope is global, as all incoming
temperature readings need to probe the table. Delivery Guarantee and Fault
Tolerance are vital for ensuring accurate temperature reading processing and
system recovery from potential failures.

Concurrent State Access. In applications like Ververica Streaming Ledger
Transactions2018  (SL), operators like parser, deposit, transfer, and sink may
need to share access to states, such as account and asset data. To process
transactions correctly and maintain data consistency, event and operation
ordering constraints are crucial. ACID Properties are necessary to ensure
shared state accuracy and prevent data corruption during concurrent access.
The state is read-write, as the account and asset data need updates, and the
access scope includes intra and inter-operator, as multiple operators and
their replica instances access and modify the shared stat. Delivery Guarantee,
Fault Tolerance, and Durability are critical for maintaining accurate and
consistent transaction processing. CAP Theorem considerations must be taken
into account when designing the system to balance consistency, availability,
and partition tolerance.

Active Complex Event Processing. In the realm of stream processing, active
complex event processing is a method that continuously monitors and analyzes a
series of real-time events to detect certain patterns or sequences. Wang et
al. ACEP  have applied this concept to a hospital infection control
application. The system uses sensor devices to generate real-time data on
healthcare workers’ (HCWs) behaviors such as “exit”, “sanitize”, and “enter”.
These events are then analyzed by pattern queries that aim to detect any
violations of hospital hygiene rules. The status of all HCWs, whether static
or dynamic, is stored in tables. In this application, it is crucial to
maintain the correct order of events and handle concurrent accesses and
updates during stream execution. This requires event ordering constraint and
ACID Properties to ensure data consistency and prevent conflicts. The state
management in this scenario involves read-write states with inter-query access
scope, as multiple pattern queries may read or update the tables concurrently.
Reliability and delivery guarantee properties, such as delivery guarantee,
fault tolerance, and durability, are essential for accurately and consistently
detecting violations of hospital hygiene rules.

###  5.3 Stream and DBMS Integration

The integration of SPEs with DBMSs is becoming increasingly important Tatbul10
. Scenarios such as stream data ingestion (i.e., _Streaming Ingestion_),
implementing OLTP queries in alternative ways (_Streaming OLTP_), and mixed
stream and analytic queries (_Streaming OLAP_) can be well supported by TSP
systems. In the following sections, we discuss each of these scenarios and
their requirements concerning TSP properties.

Streaming Ingestion. Streaming ingestion is an essential process for
organizations handling large volumes of data, as it enables more timely access
to incremental results compared to traditional batch ingestion. This approach
processes smaller microbatches throughout the day, which requires proper
management of ordering and state properties. A notable example by Meehan et
al.meehan2017data  involves self-driving vehicles, where the value of sensor
data decreases over time. In this case, timely processing and storage of time
series data are critical for making valuable decisions. The authors adapt TPC-
DItpc_di , a standard benchmark for data ingestion, to assess streaming
ingestion effectiveness while considering new data dependencies introduced by
breaking large batches into smaller ones. In this scenario, maintaining the
correct order of time series data is crucial, necessitating event ordering
constraint. ACID properties are required to ensure the correctness and
consistency of ingested data, especially with high sample rates and large data
volumes. Read-write state types are needed for efficient management and
persistence of ingested data. Delivery guarantee is essential for processing
and persisting ingested data accurately and consistently in near real-time.
Additionally, durability is necessary to ensure data availability for analysis
and decision-making, even after a system failure or outage.

Streaming OLTP. Streaming OLTP addresses traditional OLTP workloads using
streaming queries. Chen and Migliavacca chen2018streamdb  propose _StreamDB_ ,
a TSP-based system. Streaming OLTP requires ACID Properties, State Management
Properties (e.g., database partitioning), and fault tolerance. _StreamDB_ uses
three operators in a streaming query: 1) _Source_ operator, receiving
transactions and sending them to downstream data operators; 2) _Data_
operator, managing a portion of a database, executing transactions, and
producing results; 3) _Sink_ operator, receiving transaction responses.
_StreamDB_ reduces lock contention by distributing the database among multiple
data operators. However, creating an optimal stream dataflow graph for diverse
OLTP workloads remains an open question. In this scenario, operation ordering
constraint is crucial for correct transaction processing and minimizing lock
contention. ACID properties ensure database correctness and consistency during
transaction processing. Read-write state types are required for managing the
database and transactions, while maintaining consistency. Consistency,
Durability, and Fault Tolerance are vital for accurate and consistent
transaction processing and for maintaining database consistency even after
system failures or outages.

Streaming OLAP. Organizations often need real-time analysis of data streams
for immediate decision-making, and several related applications have been
described in the literature AIM15 ; streamingcube ; Gtze2019SnapshotIF . The
Huawei-AIM workload AIM15  features a three-tier architecture with storage, an
SPE, and real-time analytics (RTA) nodes. RTA nodes push analytical queries to
storage nodes, merge partial results, and deliver final results to clients. To
meet the service level objective (SLO), a consistent state (or snapshot) must
not be older than a certain bound. In this scenario, event ordering constraint
ensures correct analytical query processing. ACID properties can be relaxed
(e.g., snapshot isolation) to maintain data correctness and consistency. Read-
write state types manage the database and ensure the consistent state meets
the SLO. Delivery Guarantee, Consistency, Durability, and Fault Tolerance
ensure accurate query processing, data persistence, and system recovery from
failures.

###  5.4 Robust Stream Processing

In addition to requirements such as _scalability_ and _low latency_ , many
critical streaming applications demand SPEs to recover quickly from failures
requirements . Consequently, considerable effort has been dedicated to
achieving fault tolerance in SPEs. We discuss previous attempts to employ
transaction-like concepts to ensure high availability and fault tolerance in
stream processing, focusing on their demands for properties of TSP discussed
in Section 3.1.

Shared Persistent Storage. MillWheel millwheel  uses an event-driven API for
stateful computations and stores input and output data persistently. It relies
on remote storage systems like BigTable bigtable  for managing state updates
and handling fault tolerance through data replication. This relates to
Durability in ACID properties and Reliability and Delivery Guarantee
properties. MillWheel ensures Atomicity by encapsulating all per-key updates
in a single atomic operation. While it enforces operation ordering
constraints, strict event ordering constraints are not provided. State
Management Properties are vital in MillWheel due to its dependence on shared
persistent storage.

Transaction Identifier. Trident’s “transactional topology” trident  processes
small batches of tuples as a single operation and assigns unique transaction
identifiers (_TXID_), relating to Ordering Properties. TXID, logged in
external storage along with operator state, addresses Atomicity and Durability
in ACID properties. If TXID mismatch occurs, a batch must be resubmitted,
requiring strict transaction processing ordering (operation ordering
constraint) and potentially limiting throughput. State Management Properties
are essential in this approach, as it depends on read-write states. Trident
provides strong Delivery Guarantee and Fault Tolerance, but may lose
intermediate results during failures due to disregarding buffered input
states.

Fault Tolerance Outsourcing. Ishikawa et al. BDA18  propose integrating fault
tolerance into an OLTP engine for data stream processing. This involves
backing up data streams in an in-memory database system instead of a file
system, addressing Durability in ACID properties and Reliability and Delivery
Guarantee properties. It enforces operation ordering constraints, similar to
H-Store’s state partitioning transaction processing. However, outsourcing
fault tolerance can strain the remote store during data spikes, potentially
impacting other applications sharing the store. This approach also requires
CAP Theorem considerations, as the choice of an in-memory database system
might involve trade-offs between consistency and availability.

######  Remark 4 (TSP is not just nice to have, but sometimes a must)

By employing modern SPEs, existing workarounds, such as using external
databases to store shared application states, can lead to significant
additional programming effort ACEP , poor performance S-Store , and even
incorrect results golab2 ; S-Store-demo . This problem is exacerbated if more
complex shared mutable state storage and retrieval queries, such as range
look-ups are further required. In contrast, TSP systematically manages
concurrent accesses to shared application states with transactional
correctness. This even leads TSP to have the potential to better support
traditional database workloads (i.e., OLTP and OLAP) as well.

######  Remark 5 (TSP-based applications have diverse requirements)

Some TSP-based applications do not require insertion and deletion operations
at all, while others do not need to update shared mutable states. Also
noteworthy is that transactional dependency is rare among applications, which
means that in most cases, the input parameters in a transaction are
predetermined from the triggering events. Targeting a narrowed application
domain, a TSP system can take advantage of these diverse requirements to
simplify its design and improve system performance. To date, there is no
standard benchmark for TSP systems Tatbul2018 , which must include
comprehensive performance metrics, diverse workload features, and meaningful
application scenarios. The applications that we list in Table 3 may serve as a
starting point for the construction of a standard benchmark. However, more
††margin: applications may need to be included, arranged according to their
particular application’s features.

##  6 Research Outlook

In this section, we offer a perspective on future research directions of TSP.

###  6.1 Novel Applications

The rise of IoT generates real-time data that needs immediate processing.
Traditional big data applications were designed for large static datasets, but
modern applications demand more. We foresee novel streaming applications
benefiting from TSP solutions as the range of applications served by SPEs
widens. Current research, like NebulaStream nebulastream , explores systems
meeting these requirements. We discuss various application areas, including
online machine learning/stream mining, mixed batch/stream transactional
workloads, streaming materialized views, and cloud applications.

Optimization for Stateful Stream Processing. Shahvarani and Jacobsen’s IBWJ
IBWJ  accelerates sliding window joins by using a shared index data structure,
reducing redundant memory access and improving performance. As new tuples
arrive, the index structure is updated, raising concurrency control issues.
Shahvarani et al.IBWJ  propose a low-cost concurrency control mechanism for
high-rate update queries. A TSP system could naturally handle this concurrency
problem, providing durability when required. Despite its potential, we are
unaware of any practical implementation of this approach.

Online Machine Learning/Stream Mining. The rising demand for data stream
analysis necessitates online learning and mining. Current efforts support
continuous queries (CQs) referencing non-streaming resources like databases
and ML models DSPCC . Model-based streaming systems, such as anomaly
detectors, require regular model updates without significantly increasing
operational costs millwheel . Due to the lack of transactional support in
traditional SPEs, implementing emerging streaming learning and mining
algorithms can be challenging 10.1007/978-3-030-19274-7_10 . Although existing
batch-based ML training (like TensorFlow) may not need to care for
inconsistencies in the state they handle, a streaming ML scenario may prohibit
such inconsistencies as each input data may be allowed to be used, up to a
limited threshold, and any inconsistency may lead to significantly lower
training quality. ††margin: It thus remains an interesting future work to
study how those novel training and mining use cases can be supported
efficiently in TSP systems, which bring features, such as elastic scaling,
fault tolerance guarantees, and shared state consistency to users, even at the
virtual space ooi2022sense .

Mixed Batch/Stream Transactional Workloads. Many enterprise applications,
particularly in finance and IoT, generate mixed workloads with continuous
stream processing, OLTP, and OLAP. DeltaLake 10.14778/3415478.3415560  allows
streaming jobs to write small objects into a table with low latency and
coalesce them into larger objects later. Fast “tailing” reads are also
supported for treating a Delta table as a message bus. Tatbul Tatbul10
outlines challenges in streaming data integration, including common semantic
models, optimization, and transactional issues. These challenges persist due
to diverse applications and systems focusing on limited feature sets.

Streaming Materialized Views. Traditional materialized views (MVs) are not
optimized for high-velocity data stream processing, leading to the need for
streaming materialized views (SMVs). SMVs must handle high-velocity inputs,
update states with random access patterns, and share updated states among
concurrent entities. Recent works, such as S-Query verheijde2022s  and Umbra’s
continuous view scheme winter13meet , have proposed solutions, but the former
lacks strict ACID guarantees, and the latter has yet to be compared with
state-of-the-art transactional stream processing systems like S-Store S-Store
, TStream tstream , and TSpoon AFFETTI202065 . The distinction in use cases
drives a clear separation of concerns and further investigation into
optimizing SMVs.

Cloud Applications. ††margin: Existing SPEs often lack transactional