DEV Community: Dominik Tornow

Paper Summary: Sagas

Dominik Tornow — Sat, 18 Feb 2023 03:30:24 +0000

H. Garcia-Molina and K. Salem. 1987. Sagas. In Proceedings of the 1987 ACM SIGMOD international conference on management of data (SIGMOD ‘87). Association for Computing Machinery, New York, NY, USA, 249–259.

Keywords: Long Running Processes, Sagas, Transactions, Compensation, Failure Mitigation, Failure Tolerance, Failure Transparency

Although the original paper on Sagas was written 35 years ago, the problem is still just as relevant today. This post explores the origins of the concept of Sagas, long-running processes that span multiple database transactions.

Introduction

In their paper Sagas, Hector Garcia-Molina and Kenneth Salem introduce the concept of sagas to implement “long-running” operations.

Molina and Salem refer to processes that consist of a single step as “short-running” or “short-lived” processes and processes that consist of multiple steps as “long-running” or “long-lived”. Therefore, short-running or long-running is not a statement about physical time but a statement about logical time with each step being a clock tick (Figure 1).

The Problem

In an ecosystem that largely rejects the idea of distributed transactions or holding locks for an extended period of time, any long-running process cannot simply be mapped to a long-running, distributed transaction. Instead, we need a different mechanism to compose long-running processes from short-running, non-distributed transactions.

The paper defines a process P as a sequence of steps a, b, etc, where each step is a database transaction. To use more familiar terms, you can think of a process as a function and the sequence of steps as a sequence of API calls to the database.

We refer to the sequence of steps a, b, etc as a trace:

trace(P) = a • b • …

The authors identify that the trace, that is, the sequential composition of transactions is not closed under atomicity (Figure 2). Here, the term atomicity denotes that an operation happens entirely or not at all.

In other words: A sequence of two transactions is not a transaction!

Trivially, if a process consists of a single transaction, the process exhibits the atomicity guarantees of a transaction (Figure 3).

However, if a process consists of multiple transactions, the process does not exhibit the atomicity guarantees of a transaction: The process may execute partially (Figure 4).

However, unlike other transactions, a process’ transactions are related and should be executed as a unit, any partial executions of a process are undesirable.

The paper discusses a travel reservation application, where a trip consists of multiple flights potentially on different airlines. Here, booking a trip involves multiple transactions, one per trip leg. As travelers, we want all transactions to be executed as a unit: We either want to book all flights or no flights, booking some flights is unacceptable.

The Solution

The paper introduces Sagas, a protocol for implementing long-running processes. The Saga protocol ensures that a process is atomic, that is, a process executes observably equivalent to completely or not at all.

To mitigate partial execution, a process may implement either forward or backward recovery [2]:

Forward Recovery

Forward failure recovery refers to failure mitigation strategies that transition the system from the intermediary state to a state that is equivalent to the final state (moving the process forward).

Backward Recovery

Backward failure recovery refers to failure mitigation strategies that transition the system from the intermediary state to a state that is equivalent to the initial state (moving the process backward).

Backward Recovery & Compensation

To enable backward recovery, each process should register a compensating step for each step (Figure 6).

The compensating step undoes — from a semantic point of view — the step, but does not necessarily return the database to the state that existed when the step began. Compensation will restore the world to a state which is an acceptable approximation to the state that it had before the start of the transaction.

For example, coming back to the travel reservation application, if a trip consists of two flights and reserving the first flight succeeded yet reserving the second flight failed, the saga needs to cancel the first reservation to return the database to an acceptable approximation to the state it had before the start of booking the trip.

Execution

So in the absence of failure, a process P produces the desired trace

trace(P) = s₁ • s₂ • … sₙ • ✔️

while in the presence of failure after step sᵢ, the process P produces the less desirable yet correct trace

trace(P) = s₁ • s₂ • … sᵢ • × • cᵢ … • c₂ • c₁ • ✔️

Implementation Considerations

When a failure interrupts a Saga, a Saga must be able to recover its current state and either perform forward or backward recovery. Therefore, a Saga must be able to record the beginning of a Saga, the completion of a Saga, and record checkpoints and compensations.

If you own the database you may record checkpoints and compensations transactionally with each step. If you cannot record checkpoints and compensations transactionally with each step, you have to devise a mechanism to record checkpoints compensations reliably.

Discussion

Although the paper was written more than 35 years ago, the problem and Sagas as the proposed solution are still relevant today. However, attention has shifted from composing database transactions to composing service invocations.
Keep in mind that services do not exhibit transactional properties: Services may not be atomic, after a service invocation, and if the service crashes, you may not know if the service took effect or not.

Therefore, you should register a compensating action before invoking a service and design compensation logic to be correct whether the service took effect or not.

Conclusion

Sagas remain relevant, despite significant advances in theory and practice since the paper’s publication. The basic concept of a Saga as a protocol for implementing atomicity in a distributed environment across transactions or services the techniques described in the paper continue to be widely used today.

References

[1] A trace semantics for long-running transactions, M. Butler, C. A. R. Hoare & C. Ferreira, 2005
[2] Handling Failures From First Principles, Dominik Tornow, 2022

Introducing the Linear Developer Experience

Dominik Tornow — Wed, 11 Jan 2023 19:05:01 +0000

Many complex systems exhibit a phenomenon known as a tipping point. A tipping point is a non-linear event, when a small quantitative change triggers a significant qualitative change that is often irreversible. These moments of rapid and dramatic change play a prominent role in diverse fields of study, such as physics, sociology, economics, epidemiology, as well as software engineering. Knowing about tipping points, understanding where and when they occur, helps organizations and individuals anticipate and mitigate the significant consequences for teams and the applications they work on.

As history repeatedly demonstrates, the complexity of software continues to grow as software becomes more broadly and deeply integrated into every aspect of our lives. Companies are quickly recognizing the need to provide a good developer experience to manage that complexity in order to boost productivity and increase developer satisfaction. While the need for a good developer experience is widely recognized, there is no consensus on its definition.

However, a common sentiment among software developers is that a project’s developer experience starts out delightful but eventually and suddenly becomes dreadful.

Let’s take a Django web application as an example: After you set up a Django project and generate and configure the initial application, development follows a straight path. First, you create models, controllers, views, and unit tests. Django does the heavy lifting to create an admin interface as well as database migrations when your models change. As the application evolves, you add more models, more controllers, more views, and more unit tests. Django makes updates to the admin interface and performs the database migrations.

We could describe the Django developer experience as linear: While the application grows quantitatively (more models, controllers, views, etc.), it remains the same qualitatively (the architecture of the application is still expressed as models, controllers, views, etc.). In other words, even though your application gets bigger, your developer experience does not change. Hence, the application's developer experience grows linearly.

Until you hit the tipping point! Just one more requirement, just one more feature, a small quantitative change that triggers a significant qualitative change, the straw that breaks the camel’s back, the last drop that overflows the barrel.

There are many factors that push us over the tipping point, but some are consistently at play: Implementing a multi-step process that spans multiple database transactions or orchestrates multiple services, a process that outlives a single request-response lifecycle, or time-based actions.

For example, Django, like most web frameworks, supports only single-step processes well. Per request, the Django framework executes one request handler, which is a plain function. In turn, that request handler invokes one database transaction. However, how do we approach a task that does not solely execute one database transaction or one service call, or a task that outlives the duration of a single request? How do we implement a task that requires two, five, or ten transactions, that orchestrates two, five, or ten services, or that runs for minutes, hours, days, weeks, months, or years?

Every project I’ve worked on hits a tipping point. We’ve all had the meeting where the tipping point becomes apparent. Sometimes we were junior engineers, and quietly listened. Other times we acted as senior engineers, and hotly debated terms such as orchestration, choreography, commands, events, job queues, job scheduling, or outbox patterns. Our arguments flooded the room, but regardless of our role, the imminent turn for the worse quickly became apparent. We had arrived at the tipping point!

At this point, Django no longer feels like my ally. Django feels like my adversary. Instead of empowering me, Django holds me back. I find myself needing to work around restrictions and limitations. Databases, queues, and timers are the duct tape holding my application together. Sagas, commands, and events are the crutches on which I drag myself through the day.

I have two options: I can embrace the tipping point as inevitable, or I can reject the tipping point as inevitable.

By embracing the tipping point, I can either declare defeat now or later. If I am willing to declare defeat now, I begin building my application as if I’ve reached the tipping point already. From day one, I implement my application in terms of sagas, commands, and events, I orchestrate and choreograph, and I enqueue and dequeue in anticipation that eventually I will have to go down that path anyways. Well, if my developer experience is dreadful from day one, at least I can’t be missing what I once had. If I am willing to declare defeat later, I begin my application as if no tipping point looms on the horizon. I soothe myself with euphemisms, I tell myself that if I don’t have to re-architect and re-implement my applications later, I am making a mistake now. KISS—keep it simple, stupid. YAGNI—you ain’t gonna need it. I can find comfort in an ecosystem armed with acronyms assuring me all of this is fine.

However, it’s not. If I embrace the tipping point, whether I declare defeat now or later, eventually quality, productivity, and satisfaction will suffer. Engineers will be writing scores of code to “plug into” hunting and fixing heisenbugs in the edge cases of the application, barely able to predict or reason about the consequences of releasing that bug fix. Unexpectedly, I will “lose” the best engineers on the team, and they will no longer be doing creative work on the application; instead, the best engineers will now be doing creative work on libraries, frameworks, and platforms.

Nobody will be delighted.

Instead, I should reject the tipping point as inevitable. At this point in time, when most software runs in the cloud and on the edge, integrates with multiple and various third-party APIs, and executes processes that run from a few seconds to many days, I should demand libraries, frameworks, and platforms that offer a linear developer experience—one that I will not outgrow as my project scales.

One that starts delightful and stays delightful.

Tipping points can be a devastating event causing a sudden and consequential decline in the experience of your team, leading to a decline in quality, productivity, and satisfaction. By knowing about tipping points and understanding where and when they occur you are able to anticipate, mitigate and outright avoid their consequences.

Don’t let a tipping point derail your project. Be proactive and be aware of your developer experience. Adopt libraries, frameworks, and platforms that start delightful and stay delightful.

Look for a Linear Developer Experience.

Learn more in Temporal's on-demand webinar Introducing the Linear Developer Experience.

Introduction to Temporal Workflows

Dominik Tornow — Mon, 24 Jan 2022 20:20:43 +0000

For the past 45 years, the database community has enjoyed an unparalleled developer experience: transactions mitigate failure in totality on a platform level, guaranteeing correctness on an application level.

Despite many advancements in the past 20 years, the distributed systems community has not enjoyed an equivalent developer experience: There is no abstraction that mitigates failure in totality on a platform level, guaranteeing correctness on an application level.

However, Temporal changes that equation!

Introduction

Temporal’s core abstraction, its unit of execution, reliability, and scalability, is the Workflow. Therefore understanding the Workflow is key to understanding Temporal in general. In this blog post series we deep dive into the world of Temporal Workflows.

A Temporal Workflow is Temporal’s core abstraction. You may think of a Temporal Workflow Definition as a regular Function Definition—in fact, that is the developer experience that Temporal provides to its users—but a Workflow Execution provides stunning improvements over a regular Function Execution.

Let’s get to know Workflow Executions and contrast them to regular Function Executions with a straightforward example: sending reminder emails.

Our use case requires that our application sends a reminder email once a month to any user who signed up for a trial period to upgrade their plan. In pseudo code our use case can be expressed as:

  
function send monthly reminder (user) do
  while user has not signed up do
    send reminder to user
    sleep for 1 month
  end
end

Regular Functions

The pseudo code looks fairly straightforward; in fact, the pseudo code looks less like an implementation and more like a specification. Could we use the pseudo code as a blueprint for a regular Function Definition?

No, not at all:

In a typical environment we cannot just invoke a function and expect the resulting function execution to reliably execute to completion — or like in this case execute indefinitely until cancelation.

As a result, we have to “break up” the process of Send Reminder Email into many different pieces, scattered across the tech stack: A cron job here, a message in a queue there, maybe a row in some database table, you know, for good measure.

On top of that, now we need to worry about failures, retries, duplication, and idempotence.

An implementation on top of services like AWS Lambda Functions and like AWS Simple Queueing Service might look like:



// Lambda function is bound to
// a. input queue "Reminder"
// b. output queue "Reminder"

// We assume that
// - messages are never lost
// - messages may be duplicated
// - messages are retried on failure

function SendReminderEmail(event, context) : Message {

  // UserSignup, SendEmail, Get, Set will throw an
  // Exception on failure

  // event.user Current user
  // event.iter Current iteration to limit retries (here 2)

  if (!UserSignedUp(event.user)) {

    // Retrieve the k/v pair for this user and iteration
    let kv = Get(`$(event.user)-${event.iter}`, 0);

    // Try at most twice
    if(kv.val < 2) {
      // Conditionally set the key. If the tag does not 
      // match we are racing with another instance of
      // SendReminderEmail
      if (Set(kv.key, kv.val + 1, kv.tag)) {
        // This does not prevent us from calling SendEmail
        // twice. Do you see why?
        SendEmail(user);
      }
    }
    else {
      throw;
    }
  }

  return {
    message: { user: event.user, iter: event.iter + 1},
    after: "1month"
  }
}

// Start by queueing the message {user: "<User>", iter: 0} on
// the message queue "Reminder"

Listing 2 looks nothing like the pseudo code in Listing 1.

Listing 2 does not tell the story of our use case—while not overly long or verbose, it is obscure and hard to reason about.

Temporal Workflows

Obviously we cannot use the pseudo code as a blueprint for a regular Function Definition. However, could we use the pseudo code as a blueprint for a Temporal Workflow Definition?

Well, yes, yes we can!

import { proxyActivities, sleep } from '@temporalio/workflow';

const { sendReminderEmail, hasSignedUp } = proxyActivities({
  scheduleToCloseTimeout: '10 seconds',
  retry: { maximumAttempts: 2 }
});

async function SendReminderEmail(user: string) {
    while(!await hasSignedUp(user)) {
      try {
        await sendReminderEmail(user);
      } catch(e) {
        // Thanks to Temporal's retry policy, we already 
        // tried twice, better luck next month 🍀
      }
      await sleep("1 month");
    }
}

In Temporal we can just invoke a Workflow Definition, and the resulting Workflow Execution reliably executes to completion — or like in this case execute indefinitely until cancelation.

Temporal Workflow Executions are to distributed systems what transactions are to databases: A great developer experience and (or maybe because of) peace of mind.

Doubts? Disbelief? Check out Part II and Part III to explore how Temporal implements this game-changing execution model.

Photo by Simon Berger on Unsplash