<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Farooq Qaiser on Medium]]></title>
        <description><![CDATA[Stories by Farooq Qaiser on Medium]]></description>
        <link>https://medium.com/@fqaiser94?source=rss-ac4d9cb6496a------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/proxy/1*TGH72Nnw24QL3iV9IOm4VA.png</url>
            <title>Stories by Farooq Qaiser on Medium</title>
            <link>https://medium.com/@fqaiser94?source=rss-ac4d9cb6496a------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 00:47:49 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@fqaiser94/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Modelling Exactly-Once Delivery Using TLA+]]></title>
            <link>https://medium.com/@fqaiser94/modelling-exactly-once-using-tla-2d7035e1379e?source=rss-ac4d9cb6496a------2</link>
            <guid isPermaLink="false">https://medium.com/p/2d7035e1379e</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[tla-plus]]></category>
            <category><![CDATA[formal-verification]]></category>
            <category><![CDATA[exactly-once-processing]]></category>
            <dc:creator><![CDATA[Farooq Qaiser]]></dc:creator>
            <pubDate>Tue, 29 Oct 2024 12:08:19 GMT</pubDate>
            <atom:updated>2025-08-18T01:34:01.337Z</atom:updated>
            <content:encoded><![CDATA[<h3>Modelling Exactly-Once Delivery Using TLA+ Part 4: Modelling Zombies and Fencing</h3><p><em>TLA+</em> is a language for writing system specifications and discovering fundamental design errors quickly. In this series of blogposts, we’ll introduce <em>TLA+</em> by iteratively modelling and refining our design for a simple application that can read and write messages from/to Kafka in an exactly-once fashion. This will be a four-part series consisting of:</p><ol><li><a href="https://medium.com/@fqaiser94/exactly-once-modelling-using-tla-3c792655be44">Writing a Specification</a></li><li><a href="https://medium.com/@fqaiser94/modelling-exactly-once-using-tla-f3eb15303b27">Checking a Specification</a></li><li><a href="https://medium.com/@fqaiser94/modelling-exactly-once-using-tla-9512e1eb8ca5">Modelling Failures and Transactions</a></li><li><a href="https://medium.com/@fqaiser94/modelling-exactly-once-using-tla-2d7035e1379e"><strong>Modelling Zombies and Fencing</strong></a></li></ol><p>You can find all of the code for this series in this <a href="https://github.com/fqaiser94/tla-exactly-once">GitHub repo</a>.</p><p><em>Also, if you have interesting systems engineering problems and are looking for a strong Software Engineer, feel free to reach out via </em><a href="https://www.linkedin.com/in/fqaiser94/"><em>LinkedIn</em></a><em>.</em></p><h3>Introduction</h3><p>So far in this series, we’ve managed to design a system that can read/write messages from/to Kafka without losing data or generating duplicates even in the presence of random failures. Some so-called “exactly-once” implementations will stop here but this is usually not enough. To be truly exactly-once, distributed systems must also be able to handle the possibility of <strong>zombies</strong>.</p><p>In this article, we’ll start by first trying to understand what are zombies and how they can appear. We’ll then introduce a zombie process into our spec and see how that can lead to duplicates. Afterwards, we’ll design a solution to prevent these duplicates using the <strong>fencing</strong> technique. Finally, we’ll conclude with some reflections about <em>TLA+ </em>in general. Buckle up, we’re ending the series with the longest (and most interesting!) post.</p><h3>Zombies</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/485/0*tYOl_jHscoFXbQ6Q" /><figcaption>vastateparksstaff, CC BY 2.0 &lt;<a href="https://creativecommons.org/licenses/by/2.0">https://creativecommons.org/licenses/by/2.0</a>&gt;, via Wikimedia Commons</figcaption></figure><p>In distributed systems, we use the term “zombie” to refer to a process that is running unbeknownst to our system. For example, imagine a distributed system consisting of worker processes managed by a central coordinator process similar to Spark, Flink, Kafka Connect etc. Each worker is assigned some unit of work by the coordinator and it’s the coordinator’s job to reassign work when it detects that a worker has died.</p><p>Detecting when a worker has died <strong>reliably </strong>however is a challenging task in a distributed setting. The usual mechanism is to have workers emit a “heartbeat” signal continuously to the coordinator to indicate that they are still alive and doing work. If the coordinator stops receiving heartbeats from a certain worker, it must assume that the worker is dead and redistribute it’s work to another worker. The problem is that the worker might still be alive and yet the coordinator might stop receiving heartbeats for other reasons.</p><p>The classic example of this is a <strong>network partition</strong> where a network failure causes the members of a system to split into two or more groups such that a member of one group cannot communicate with members in other groups. During the time that the network is degraded, the coordinator will not receive heartbeat signals from workers in other groups. As a result, the coordinator may incorrectly assume those workers are dead and reassign the work that was previously allocated to the “dead” workers to the remaining live workers. We refer to these “dead” workers as <strong>zombies</strong> because they’re not really dead, they’re just dead from the coordinator’s flawed perspective. The end result though is you now have two workers doing the same work at the same time. This can lead to all sorts of problems including duplicates, inconsistency, split-brain scenarios etc.</p><p>Another way you can end up with zombies is through long <strong>garbage collection</strong> (<em>GC</em>) cycles. In the <em>JVM</em> world, garbage collection tends to be a stop-the-world style event which means a worker will stop doing all work during that time, including emitting heartbeats. Normally this is fine because garbage collection tends to be a quick process (&lt;1 second) and most systems are designed to tolerate a few missed heartbeat signals. However if, for whatever reason, garbage collection suddenly starts taking a long enough time, our coordinator will eventually be forced to assume that a worker is dead and then reassign it’s work to another worker. Later, when the garbage collection cycle completes and the original worker recovers, it will resume emitting heartbeat signals and continue doing the work it was previously assigned. Usually a coordinator will detect that there are now two workers doing the same work and fix this but in the time that it takes to do this, you may end up with duplicated work.</p><blockquote>Pro tip: If someone is claiming to have an exactly-once implementation of something, a good way to check they know what they’re talking about is by asking them about how their system handles zombies. If they don’t understand what you mean by zombies, then there’s a good chance their implementation is not truly exactly-once (and you can then point them to this blogpost <em>😎).</em></blockquote><p>The system we’re designing will likely be implemented as a Kafka <strong>Consumer</strong> based application. These type of applications are typically deployed in a distributed fashion (to take advantage of Kafka’s natural partitioning scheme) using Kafka’s <strong>consumer group management</strong> APIs. The way this works is users will launch multiple instances of an application with the same <strong>consumer-group-id</strong>. These instances will form what’s known as a <strong>consumer group</strong> and they will play the role of workers. A Kafka broker will play the role of the coordinator and handle the distribution of topic-partitions to each of the members of the consumer group. If an instance dies, the Kafka broker will initiate the <strong>rebalancing</strong> process and redistribute topic-partitions between the remaining instances. As a result, our proposed system is potentially suspect to all of the aforementioned zombie issues.</p><h3>Modelling a Zombie</h3><p>It’s probably easy to see how zombies could result in duplicates but let’s turn off our brains for a moment and let <em>TLA+</em>/<em>TLC</em> do the work for us! 😄</p><p>Our <em>TLA</em>+ spec currently models a single process reading from an input topic-partition and writing to another output topic-partition. In order to simulate a zombie, we’ll need to modify our spec to reflect a scenario where we have two processes reading from the same input topic-partition and writing to the same output topic-partition. We’ll consider one of these processes to be a zombie and the other to be live from the perspective of the coordinator.</p><p>There are many ways we could model this. For example, we could duplicate each of our steps, once for each process, like so:</p><pre><strong>Next ==<br></strong>  /* Process 1 (live) steps<strong><br>  \/ Consume1<br>  \/ ProduceCommit1<br>  \/ Done1<br>  \/ Restart1<br></strong>  /* Process 2 (zombie) steps<strong><br>  \/ Consume2<br>  \/ ProduceCommit2<br>  \/ Done2<br>  \/ Restart2</strong></pre><p>Whilst this is a valid approach, this will involve significant duplication of “code” (not shown here) and even more so if we were to model more than two processes. Let’s see how we can achieve essentially the same result but in a more <em>DRY</em> fashion.</p><pre><strong>Processes == {1, 2}                                </strong>\* 1<strong><br><br>Init ==<br>  /\ InputTopic = &lt;&lt;1&gt;&gt;<br>  /\ Buffer = [ process \in Processes |-&gt; NULL ]   </strong>\* 2<strong><br>  /\ OutputTopic = &lt;&lt;&gt;&gt;<br>  /\ CommittedConsumerOffset = 1<br>  /\ PC = [ process \in Processes |-&gt; &quot;Consume&quot; ]  </strong>\* 3</pre><ol><li>First, we need to introduce the concept of <strong>Processes</strong> into our spec. We define this as a simple <strong>set</strong> of two integers; <strong>1</strong> and <strong>2</strong>. We’ll be using these integers to kind-of represent two different processes.</li><li>The next step is to update our initial state predicate to setup multiple processes. <br> <br>In our spec, a process has two pieces of local state; <strong>Buffer</strong> and <strong>PC</strong>. In order to model multiple processes, we’ll need to represent the <strong>Buffer</strong> and <strong>PC</strong> states for each process in our spec. One way to do this generically is to use a <em>TLA+</em> <strong>function</strong>. Despite the similarity in naming, a function in <em>TLA+ </em>is not like a function in regular programming languages. The programming equivalent of a <em>TLA</em>+ function would be a <strong>Map</strong> in <em>Java (</em>or a <strong>Dict</strong> in <em>Python</em>). <br> <br>In reality, it’s more accurate to think of <em>TLA+</em> functions as similar to mathematical functions. In math, a function maps each element of a set <strong>X</strong> to exactly one value from a set <strong>Y</strong>. We say the set <strong>X</strong> forms the <strong>domain</strong> of the function while the set <strong>Y</strong> is referred to as the <strong>codomain</strong> of the function. <br><br>Here the expression <strong>[ process \in Processes |-&gt; NULL ]</strong> is defining a new <em>TLA+</em> function. The part to the left of <strong>|-&gt;</strong> (i.e. <strong>process \in Processes</strong>) is defining the domain of our function, namely the set of numbers <strong>1</strong> and <strong>2</strong>. The codomain of this function is defined by the part to the right of <strong>|-&gt;</strong>. Here, the codomain is just a set consisting of a single value <strong>NULL</strong>. So this function maps both <strong>1</strong> and <strong>2</strong> to <strong>NULL</strong>. Our function is not defined for any other values. <br> <br>The idea here is that we’ve defined <strong>Buffer</strong> as a function that maps a process to the state of it&#39;s buffer at any given point in time. We can retrieve the state of the buffer for the first process by applying this function to the value <strong>1</strong>. Similarly, we can retrieve the state of the buffer for the second process by applying this function to the value <strong>2</strong>. We’ll see shortly exactly how we can “apply” functions to values in <em>TLA+</em>.</li><li>We need to do something similar with our <strong>PC</strong> variable. Recall that previously <strong>PC</strong> represented the <strong>program control</strong> state for a process. However, since we now have multiple processes and each process executes independently, the program control state could be different between processes, hence we now need to model <strong>PC</strong> as a function mapping each process to it’s program control state. However, in the initial state, we’ll have our <strong>PC</strong> function map both processes to <strong>&quot;Consume&quot;</strong>.</li></ol><blockquote>Functions aren’t actually something new, you’ve already been using functions throughout this series without noticing it! A TLA+ sequence (defined using <strong>&lt;&lt;&gt;&gt;</strong>) is actually just a function! It’s a specific type of function that maps integers (representing indexes) to values. Since this is such a common use case, TLA+ has dedicated, convenience syntax for it.</blockquote><p>Now that we’ve changed the types of <strong>Buffer</strong> and <strong>PC</strong> from simple integers and strings to functions returning integers and strings respectively, we need to update our usages of them starting with the <strong>Consume</strong> operator:</p><pre><strong>Update(function, x, y) == [ function EXCEPT ![x] = y ]                                 \* 1<br><br>Consume(process) ==                                                                    \* 2<br>  /\ PC[process] = &quot;Consume&quot;                                                         \* 3<br>  /\ IF MessagesAvailable<br>     THEN /\ Buffer&#39; = Update(Buffer, process, InputTopic[CommittedConsumerOffset])  \* 4<br>          /\ PC&#39; = Update(PC, process, &quot;ProduceCommit&quot;)                              \* 5<br>     ELSE /\ Buffer&#39; = Update(Buffer, process, NULL)                                 \* 4<br>          /\ PC&#39; = Update(PC, process, &quot;Done&quot;)                                       \* 5<br>  /\ UNCHANGED &lt;&lt;InputTopic, OutputTopic, CommittedConsumerOffset&gt;&gt;</strong></pre><ol><li>Here we’re introducing a new <strong>Update</strong> helper operator that we’ll be using in a bunch of places in our spec to update the values inside of our <strong>Buffer</strong> and <strong>PC</strong> functions for a given process as our system progresses through the various steps. <br> <br>We can use the <strong>[ function EXCEPT ![x] = y ]</strong> syntax to define a new function that is basically a copy of an existing <strong>function</strong> except that it reassigns the value associated with <strong>x</strong> to <strong>y</strong>. If you prefer to think of <em>TLA+</em> functions as similar to a <strong>Map</strong>, you can think of this operator as allowing you to create a new <strong>Map</strong> that is identical to an existing <strong>Map</strong> except that it has an updated <em>value</em> (<strong>y</strong>) for a given <em>key </em>(<strong>x</strong>).<br> <br>The only reason we’re adding this helper operator is to make our spec more readable since the syntax for updating <em>TLA+</em> functions can be a little intimidating. This operator isn’t adding any value beyond that.</li><li>Each of our processes will be able to consume messages independently of each other. In order to be able to model this without duplication of code, the first thing we need to change about our <strong>Consume</strong> operator is to have it take a <strong>process</strong> argument. In the context of our spec, this <strong>process</strong> argument will always be either a <strong>1</strong> or <strong>2 </strong>originating from our <strong>Processes</strong> set.</li><li>Next, we need to specify that we can only take this step for a given <strong>process</strong> as long as the program control state of that process is equal to <strong>&quot;Consume&quot;</strong>. Previously we did this by just specifying <strong>PC = &quot;Consume&quot;</strong>. However, our <strong>PC</strong> variable is now a function! We need to “apply” our function to the <strong>process</strong> argument and check if the result is equal to <strong>&quot;Consume&quot;</strong>. We can do that using square brackets to “index” a function in much the same way you would a <strong>Dict</strong> in <em>Python</em> i.e. <strong>PC[process] = &quot;Consume&quot;</strong>.</li><li>We also need to update the <strong>Buffer</strong> variable. Previously this was as simple as <strong>Buffer&#39; = NULL</strong> in the case where there were no more <strong>MessagesAvailable</strong>. However, now that our <strong>Buffer</strong> variable is a function, we want to update only the value corresponding to <strong>process</strong> inside our function for this step. We can use our helper <strong>Update</strong> operator here to do this: <strong>Buffer&#39; = Update(Buffer, process, NULL)</strong>. <br> <br>We can make a similar change for the case where there are still <strong>MessagesAvailable</strong>.</li><li>Finally, we can also update our <strong>PC</strong> variable references in a similar manner.</li></ol><p>We can make similar changes to the rest of the steps in our spec as follows:</p><pre><strong>ProduceCommit(process) ==<br>  /\ PC[process] = &quot;ProduceCommit&quot;<br>  /\ OutputTopic&#39; = Append(OutputTopic, Buffer[process])<br>  /\ CommittedConsumerOffset&#39; = Buffer[process] + 1<br>  /\ PC&#39; = Update(PC, process, &quot;Consume&quot;)<br>  /\ UNCHANGED &lt;&lt;InputTopic, Buffer&gt;&gt;<br><br>Done(process) ==<br>  /\ PC[process] = &quot;Done&quot;<br>  /\ UNCHANGED vars<br><br>Restart(process) ==<br>  /\ PC[process] /= &quot;Done&quot;<br>  /\ Buffer&#39; = Update(Buffer, process, NULL)<br>  /\ PC&#39; = Update(PC, process, &quot;Consume&quot;)<br>  /\ UNCHANGED &lt;&lt;InputTopic, OutputTopic, CommittedConsumerOffset&gt;&gt;</strong></pre><p>These changes should be self-explanatory at this point.</p><p>We’re not done yet though. Since we’ve updated our <strong>Consume</strong>, <strong>ProduceCommit</strong>, <strong>Restart</strong>, and <strong>Done</strong> steps so that they each now take a <strong>process</strong> argument, we also now need to update our usages of them.</p><pre><strong>Next ==                                                 </strong>\*1 <strong><br>  \E process \in Processes:<br>    \/ Consume(process)<br>    \/ ProduceCommit(process)<br>    \/ Restart(process)<br>    \/ Done(process)<br><br>Fairness ==                                             </strong>\*2 <strong><br>  \E process \in Processes:<br>    /\ WF_vars(Next)<br>    /\ SF_vars(ProduceCommit(process))<br>  <br>Termination == <br>  &lt;&gt;[](\A process \in Processes: PC[process] = &quot;Done&quot;)  </strong>\*3</pre><ol><li>Previously, when we had just one process, we defined our next state relation as either a <strong>Consume</strong> <strong>or</strong> <strong>ProduceCommit</strong> <strong>or</strong> <strong>Restart</strong> <strong>or</strong> <strong>Done</strong> step. Now that we have multiple processes, our system can potentially take any one of those steps for any one of our processes at any moment in time. Expanding our definition of <strong>Next</strong> to accommodate this change is as simple as adding a <strong>there-exists</strong> (<strong>\E</strong>) clause, as shown above. We can read our next state relation formally as <strong>there exists</strong> a <strong>process</strong> in our set of <strong>Processes</strong> for which we can take either a <strong>Consume</strong> <strong>or</strong> a <strong>ProduceCommit</strong> <strong>or</strong> a <strong>Restart</strong> <strong>or</strong> a <strong>Done</strong> step. <br> <br>It’s important to understand some of the implications of this definition. For example, this definition allows for the possibility that one process (P1) could go through all of <strong>Consume</strong>, <strong>ProduceCommit</strong>, <strong>Restart</strong>, and <strong>Done</strong> steps before another process (P2) ever takes a single step. And that’s perfectly fine; there’s no reason to assume two independent processes will move in lockstep with each other. In fact, the sequence of events we just described is exactly how our system would behave in the real world if process P2 encountered a long garbage collection pause.</li><li>We can also update our <strong>Fairness</strong> constraint in a similar fashion by adding a <strong>there-exists</strong> (<strong>\E</strong>) clause to its definition.</li><li>Following the pattern we’ve seen so far, it might be tempting add a <strong>there-exists </strong>(<strong>\E</strong>)<strong> </strong>clause to our <strong>Termination</strong> property. However, this would be incorrect. Consider the following scenario; we have two processes and the program control state for one process is <strong>&quot;Done&quot;</strong> while the other is <strong>&quot;Consume&quot;</strong>. Would you say our system is terminated in this case? Of course not! The program control state for both processes needs to be <strong>&quot;Done&quot;</strong> for our system to be considered fully terminated. <br> <br>Instead of <strong>there-exists</strong> (<strong>\E</strong>), we need to add a <strong>for-all</strong> (<strong>\A</strong>) clause here, as shown above. This formally defines <strong>Termination</strong> as any behaviour in which <strong>all</strong> <strong>Processes</strong> <strong>eventually always</strong> end up in a <strong>PC[process] = &quot;Done&quot; </strong>state.</li></ol><p>And those are all the changes we need to make to model two processes trying to replicate the same messages at the same time.</p><p>Even though we say <em>TLA</em>+ is not a programming language, elements of it are clearly inspired by modern programming languages, allowing us to modularize and reuse “code” instead of repeating ourselves. If we wanted to, we could easily simulate scenarios where we have more than just one zombie process. All we’d need to do is add more (unique) integers to our <strong>Processes</strong> set to represent more processes. That said, there’s little benefit to doing so as this doesn’t generate any interesting new behaviours.</p><h3>Duplicates</h3><p>At this point, our spec is ready to be checked by <em>TLC</em>. Doing so reveals the following sequence of steps which lead to a state that violates our <strong>NoDuplicates</strong> invariant:</p><pre><strong>State 1: &lt;Initial predicate&gt;<br>/\ CommittedConsumerOffset = 1<br>/\ OutputTopic = &lt;&lt;&gt;&gt;<br>/\ Buffer = &lt;&lt;NULL, NULL&gt;&gt;<br>/\ PC = &lt;&lt;&quot;Consume&quot;, &quot;Consume&quot;&gt;&gt;<br>/\ InputTopic = &lt;&lt;1&gt;&gt;<br><br>State 2: &lt;Consume line 25, col 5 to line 31, col 69 of module ExactlyOnce&gt;<br>/\ CommittedConsumerOffset = 1<br>/\ OutputTopic = &lt;&lt;&gt;&gt;<br>/\ Buffer = &lt;&lt;1, NULL&gt;&gt;<br>/\ PC = &lt;&lt;&quot;ProduceCommit&quot;, &quot;Consume&quot;&gt;&gt;<br>/\ InputTopic = &lt;&lt;1&gt;&gt;<br><br>State 3: &lt;Consume line 25, col 5 to line 31, col 69 of module ExactlyOnce&gt;<br>/\ CommittedConsumerOffset = 1<br>/\ OutputTopic = &lt;&lt;&gt;&gt;<br>/\ Buffer = &lt;&lt;1, 1&gt;&gt;<br>/\ PC = &lt;&lt;&quot;ProduceCommit&quot;, &quot;ProduceCommit&quot;&gt;&gt;<br>/\ InputTopic = &lt;&lt;1&gt;&gt;<br><br>State 4: &lt;ProduceCommit line 34, col 5 to line 38, col 39 of module ExactlyOnce&gt;<br>/\ CommittedConsumerOffset = 2<br>/\ OutputTopic = &lt;&lt;1&gt;&gt;<br>/\ Buffer = &lt;&lt;1, 1&gt;&gt;<br>/\ PC = &lt;&lt;&quot;Consume&quot;, &quot;ProduceCommit&quot;&gt;&gt;<br>/\ InputTopic = &lt;&lt;1&gt;&gt;<br><br>State 5: &lt;ProduceCommit line 34, col 5 to line 38, col 39 of module ExactlyOnce&gt;<br>/\ CommittedConsumerOffset = 2<br>/\ OutputTopic = &lt;&lt;1, 1&gt;&gt;<br>/\ Buffer = &lt;&lt;1, 1&gt;&gt;<br>/\ PC = &lt;&lt;&quot;Consume&quot;, &quot;Consume&quot;&gt;&gt;<br>/\ InputTopic = &lt;&lt;1&gt;&gt;</strong></pre><p>We can generate a state graph to see things more clearly (note that this does not show the full state space defined by our spec, only the state space that was explored before we found a violation):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*JzWq3Tf8iPc1AIzqYsiS1A.png" /><figcaption>Figure 1</figcaption></figure><p>We can see we end up with duplicates because there is nothing preventing both processes from consuming the same message at the same time and then producing it to the output topic. We can see this problem highlighted even more clearly in the following diagram generated by temporarily removing the <strong>Restart</strong> step from our <strong>Next</strong> disjunction:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*V8p_St_13dBeimq73Wo5fA.png" /><figcaption>Figure 2</figcaption></figure><p>This diagram also proves that zombie duplicates are still possible even in a world without random failures.</p><p>Once again, we see how easy it is to express and experiment with complex ideas in our <em>TLA+</em> specifications. Just imagine trying to setup the same experiment in <em>Java </em>or <em>Python</em>. You would have to set up a local Kafka cluster, seed it with some data, setup a couple of processes, write assertions to check for duplicates, etc. This will probably take a couple of hours + a few hundred lines of code and even then, you would still have to get relatively lucky to actually generate duplicates!</p><p>At the same time, it’s important to note that prior to us modelling this scenario, there was really no indication from <em>TLA+</em>/<em>TLC</em> that we could end up with duplicates if there were multiple processes running. It was only after we incorporated this detail into our spec did we discover this edge case. This is an important reminder that while <em>TLA+</em> and <em>TLC</em> are great assistants, they’re still not a replacement for critical thinking skills.</p><p>So, we’ve discovered a critical flaw in the exactly-once-ness of our design. It’s now time to turn our brains back on and come up with a solution!</p><h3>Zombie fencing</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3PDaUGObmCHr_0XqObhWvA.jpeg" /><figcaption>Image generated using Microsoft Designer with the prompt “Fencer versus a zombie caroon style”</figcaption></figure><p>Maintaining exactly-once behaviours in the presence of zombies is a challenging problem. Under these circumstances, you’ll often see developers rush towards lock based solutions. However, these types of solutions are rarely effective (often making duplicates improbable but not impossible) and even when they are effective, they tend to be too inefficient to be practically useful.</p><blockquote>You don’t have to take our word for it though, feel free to try modelling a lock based solution yourself!</blockquote><p>Instead, our best bet is a little-known technique commonly referred to as <strong>fencing</strong>. Although it makes for a good visual, the term fencing here isn’t a reference to the <a href="https://en.wikipedia.org/wiki/Fencing">combat sport</a> 🤺. Fencing in this context refers to the process of <em>fencing out</em> zombie processes from a system.</p><p>This is usually achieved through the use of <strong>fencing tokens</strong>. On startup, processes will acquire a token from a server (e.g. a Kafka broker). Later, when the process needs to make a request to the server (e.g. a request to a Kafka broker to write messages to a topic), it will include the token as part of the request. If the token is <strong>stale</strong>, the server will reject the request, effectively fencing out the process. Otherwise, if the token is valid, the server will complete the request and the system will continue to operate normally.</p><p>Fencing tokens are usually structured as a monotonically increasing value. Every time a new process registers with the server, the fencing token is incremented. This effectively fences out zombie processes as they will be holding smaller values than the current, valid token value.</p><p>Let’s see if we can use this technique to solve our zombie-duplicates issue.</p><h3>Modelling Zombie Fencing</h3><p>The main changes we need to make are as follows:</p><pre><strong>VARIABLES InputTopic, Buffer, OutputTopic, CommittedConsumerOffset, PC, CurrentToken, Token<br><br>vars == &lt;&lt;InputTopic, Buffer, OutputTopic, CommittedConsumerOffset, PC, CurrentToken, Token&gt;&gt;<br><br>Init ==<br>  /\ InputTopic = &lt;&lt;1&gt;&gt;<br>  /\ Buffer = [ process \in Processes |-&gt; NULL ]<br>  /\ OutputTopic = &lt;&lt;&gt;&gt;<br>  /\ CommittedConsumerOffset = 1<br>  /\ CurrentToken = 0<br>  /\ Token = [ process \in Processes |-&gt; NULL ]<br>  /\ PC = [ process \in Processes |-&gt; &quot;AcquireToken&quot; ]<br><br>AcquireToken(process) ==<br>  /\ PC[process] = &quot;AcquireToken&quot;<br>  /\ CurrentToken&#39; = CurrentToken + 1<br>  /\ Token&#39; = Update(Token, process, CurrentToken&#39;)<br>  /\ PC&#39; = Update(PC, process, &quot;Consume&quot;)<br>  /\ UNCHANGED &lt;&lt;InputTopic, Buffer, OutputTopic, CommittedConsumerOffset&gt;&gt;<br><br>ProduceCommit(process) ==<br>  /\ PC[process] = &quot;ProduceCommit&quot;<br>  /\ IF Token[process] = CurrentToken<br>     THEN /\ OutputTopic&#39; = Append(OutputTopic, Buffer[process])<br>          /\ CommittedConsumerOffset&#39; = Buffer[process] + 1<br>          /\ PC&#39; = Update(PC, process, &quot;Consume&quot;)<br>          /\ UNCHANGED &lt;&lt;InputTopic, Buffer, CurrentToken, Token&gt;&gt;<br>     ELSE /\ PC&#39; = Update(PC, process, &quot;Fenced&quot;)<br>          /\ UNCHANGED &lt;&lt;InputTopic, Buffer, OutputTopic, CommittedConsumerOffset, CurrentToken, Token&gt;&gt;<br>  <br>Fenced(process) ==<br>  /\ PC[process] = &quot;Fenced&quot;<br>  /\ UNCHANGED vars</strong></pre><ol><li>First, we introduce a couple of new variables into our spec; <strong>CurrentToken</strong> and <strong>Token</strong>.</li><li>Next, we need to give these new variables initial values, starting with <strong>CurrentToken</strong>. As is implied in the name, <strong>CurrentToken</strong> will represent the current, valid value of the fencing token issued by the server i.e. if a process tries to write to Kafka using a fencing token that matches the value of <strong>CurrentToken</strong>, then that should be allowed. Conversely, if a process tries to write to Kafka using a fencing token that does <strong>not</strong> match the value of <strong>CurrentToken</strong> (i.e. using a stale token) then this request should be rejected. We’ll give <strong>CurrentToken</strong> a initial value of <strong>0</strong>.<br> <br>This variable does not represent state that is tied to a specific process. Similar to <strong>InputTopic</strong> and <strong>OutputTopic</strong>, <strong>CurrentToken</strong> represents state that in the real world would live in our Kafka cluster.</li><li><strong>Token</strong> on the other hand is state that is tied to a process, and as a result we’ll setup <strong>Token</strong> as a function (similarly to <strong>Buffer</strong> and <strong>PC</strong>). This will initially be <strong>NULL</strong> for each process.</li><li>The idea is that processes will need to acquire a fresh token on startup to populate this <strong>Token</strong> variable. As a result, we need to update our <strong>PC</strong> variable so that the first step for each process will be <strong>AcquireToken</strong> (which we’ll be defining next), rather than <strong>Consume</strong>.</li><li>Here, we’re starting to define our new <strong>AcquireToken</strong> step. We first specify that we can only take this step for a process if the program control state for that process equals <strong>&quot;AcquireToken&quot;</strong>.</li><li>Next we increment the <strong>CurrentToken</strong>. This is important; this is what will fence out zombie processes holding older tokens. This updated token is what the server returns to our process.</li><li>We update the <strong>Token</strong> state for this process so it holds the new <strong>fencing token</strong>. We’ll need to include in this our requests later when this process attempts to produce messages to Kafka.</li><li>We specify the value of <strong>PC</strong> in the next state for this process is equal to <strong>&quot;Consume&quot;</strong>.</li><li>As usual, we specify that all other variables remain unchanged when we take this step.</li><li>In <strong>ProduceCommit</strong>, we now introduce some branching. If the token matches the current valid token, we go through the regular produce + commit process. Otherwise, if the token is invalid/stale, we move the process into a <strong>Fenced</strong> state.</li><li>Finally, we introduce a new <strong>Fenced</strong> step, as a complement to <strong>Done</strong>, in order to be able to distinguish between a clean shutdown (<strong>Done</strong>) and fencing of a zombie process (<strong>Fenced</strong>) of a process.</li></ol><p>The rest of the changes are fairly mechanical:</p><pre><strong>Restart(process) ==<br>  /\ PC[process] \notin {&quot;Fenced&quot;, &quot;Done&quot;}<br>  /\ Buffer&#39; = Update(Buffer, process, NULL)<br>  /\ PC&#39; = Update(PC, process, &quot;AcquireToken&quot;)<br>  /\ UNCHANGED &lt;&lt;InputTopic, OutputTopic, CommittedConsumerOffset, CurrentToken, Token&gt;&gt;<br>  <br>Consume(process) ==<br>  /\ PC[process] = &quot;Consume&quot;<br>  /\ IF MessagesAvailable<br>     THEN /\ Buffer&#39; = Update(Buffer, process, InputTopic[CommittedConsumerOffset])<br>          /\ PC&#39; = Update(PC, process, &quot;ProduceCommit&quot;)<br>     ELSE /\ Buffer&#39; = Update(Buffer, process, NULL)<br>          /\ PC&#39; = Update(PC, process, &quot;Done&quot;)<br>  /\ UNCHANGED &lt;&lt;InputTopic, OutputTopic, CommittedConsumerOffset, CurrentToken, Token&gt;&gt;<br><br>Next ==<br>  \E process \in Processes:<br>    \/ Register(process)<br>    \/ Consume(process)<br>    \/ ProduceCommit(process)<br>    \/ Restart(process)<br>    \/ Fenced(process)<br>    \/ Done(process)<br><br>Termination == <br>  &lt;&gt;[](\A process \in Processes: PC[process] \in {&quot;Fenced&quot;, &quot;Done&quot;})</strong></pre><ol><li>We need to update our <strong>Restart</strong> step so that we don’t restart fenced processes. Once a process is fenced, we consider it to be dead similar to how once a process is <strong>Done</strong> we consider it to be terminated.</li><li>In addition, we specify that <strong>PC</strong> should now point to the <strong>AcquireToken</strong> step as the first step in our program logic after a restart.</li><li>We need to add <strong>CurrentToken</strong> and <strong>Token </strong>to the <strong>UNCHANGED</strong> clauses of our <strong>Restart</strong> and <strong>Consume</strong> steps.</li><li>We need to add the new <strong>Register</strong> and <strong>Fenced</strong> steps to our <strong>Next</strong> action.</li><li>And lastly, we need to update our <strong>Termination</strong> property as we now have two possible terminal program control states for each process in our system (<strong>&quot;Done&quot;</strong> and <strong>&quot;Fenced&quot;).</strong></li></ol><p>Unfortunately, if you try to running this updated spec through <em>TLC, </em>it will never finish checking!</p><h3>Debugging TLA+</h3><p>Although <em>TLA+ </em>is not a programming language, we still have access to tools that allow for debugging:</p><ol><li>If you <strong>EXTENDS TLC</strong>, you can use statements like <strong>PrintT(&quot;hello world&quot;) </strong>to do printf-style debugging.</li><li>We can add invariants and check that they hold using <em>TLC</em> in a similar way to how we might write <strong>assert</strong> statements in our <em>Python</em> code.</li><li>Lastly, there’s also the recently released <a href="https://will62794.github.io/tla-web/"><em>TLA+</em> Web Explorer</a>. This nifty little tool allows you to step through the state machine defined by your “code” much like you would programs with a professional debugger.</li></ol><p>Try out some or all of these methods and see if you can spot the problem in our spec. Otherwise read on for the answer.</p><h3>State Space Explosion</h3><p>The “problem” is that our state space is infinite. Every time a process restarts, it has to start all over again from the <strong>AcquireToken</strong> step. Acquiring a fresh token ends up incrementing the <strong>CurrentToken</strong> value which results in a distinct, new state space. As a result, as long as our spec allows infinite restarts, there is always a new state space to be explored, and hence <em>TLC</em> never finishes exploring.</p><p>We need to somehow express in <em>TLA+</em> the idea that eventually our system must stop restarting. Having encountered similar problems throughout this series where the solution was to always fiddle with our fairness constraint, you might be tempted to look for a solution there first. Unfortunately, this is not really a fairness concern so this line of thought is a dead end.</p><p>Instead, we have to get a little clever here. To limit the size of the state space, we can introduce an arbitrary condition to our <strong>Restart</strong> step that effectively restricts the number of times a process can restart, like so:</p><pre><strong>VARIABLES InputTopic, Buffer, OutputTopic, CommittedConsumerOffset, PC, CurrentToken, Token, RemainingRestarts<br><br>vars == &lt;&lt;InputTopic, Buffer, OutputTopic, CommittedConsumerOffset, PC, CurrentToken, Token, RemainingRestarts&gt;&gt;<br><br>Init ==<br>    /\ InputTopic = &lt;&lt;1&gt;&gt;<br>    /\ Buffer = [ process \in Processes |-&gt; NULL ]<br>    /\ OutputTopic = &lt;&lt;&gt;&gt;<br>    /\ CommittedConsumerOffset = 1<br>    /\ PC = [ process \in Processes |-&gt; &quot;AcquireToken&quot; ]<br>    /\ CurrentToken = 0<br>    /\ Token = [ process \in Processes |-&gt; NULL ]<br>    /\ RemainingRestarts = [ process \in Processes |-&gt; 1 ]<br><br>Restart(process) ==<br>    /\ PC[process] \notin {&quot;Fenced&quot;, &quot;Done&quot;}<br>    /\ RemainingRestarts[process] &gt; 0<br>    /\ Buffer&#39; = Update(Buffer, process, NULL)<br>    /\ PC&#39; = Update(PC, process, &quot;AcquireToken&quot;)<br>    /\ RemainingRestarts&#39; = Update(RemainingRestarts, process, RemainingRestarts[process] - 1)<br>    /\ UNCHANGED &lt;&lt;InputTopic, OutputTopic, CommittedConsumerOffset, CurrentToken, Token&gt;&gt;</strong></pre><ol><li>First, we introduce a new variable <strong>RestartsRemaining </strong>into our spec. As is implied in the name, this will represent the number of restarts remaining.</li><li>Similar to <strong>PC</strong>, <strong>Buffer</strong>, and <strong>Token</strong>, we’ll set this up as a function so that each process can restart an independent number of times. We’ve chosen to to allow only <strong>1</strong> restart per process to minimize the size of the state space but we could just as easily set this to a higher value to explore scenarios where processes can restart multiple times. You could even make this a configurable <strong>CONSTANT</strong> in your spec to easily experiment with different values. Our justification for allowing only one restart per process is that going beyond this number does not yield any interesting behaviours that aren’t visible with just one restart.</li><li>The only step that can change the value of <strong>RestartsRemaining</strong> will be our <strong>Restart</strong> step.</li><li>Finally, we need to make two changes to our <strong>Restart</strong> step. The first is to specify we can only take this step as long as the number of restarts remaining for a given process is greater than <strong>0</strong>.</li><li>The second change is to decrement the number of restarts remaining for this process whenever we take this <strong>Restart</strong> step using our handy <strong>Update</strong> function.</li></ol><p>The only other changes we need to make are to specify this new variable as <strong>UNCHANGED</strong> in all our other steps:</p><pre><strong>AcquireToken(process) ==<br>    ...<br>    /\ UNCHANGED &lt;&lt;InputTopic, Buffer, OutputTopic, CommittedConsumerOffset, RemainingRestarts&gt;&gt;<br><br>Consume(process) ==<br>    ...<br>    /\ UNCHANGED &lt;&lt;InputTopic, OutputTopic, CommittedConsumerOffset, CurrentToken, Token, RemainingRestarts&gt;&gt;<br><br>ProduceCommit(process) ==<br>    ...<br>    IF ...<br>       THEN ...<br>            /\ UNCHANGED &lt;&lt;InputTopic, Buffer, CurrentToken, Token, RemainingRestarts&gt;&gt;<br>       ELSE ...<br>            /\ UNCHANGED &lt;&lt;InputTopic, Buffer, OutputTopic, CommittedConsumerOffset, CurrentToken, Token, RemainingRestarts&gt;&gt;</strong></pre><p>Running this now, you should see <em>TLC</em> does eventually finish checking our spec! We still end up with 556 distinct states but that’s better than infinite. More importantly though, our spec is passing all our desired invariants and properties again 🎉🎉🎉</p><h3>Zombie Fencing in Kafka</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/0*5gTp-V18-XjEo9tP.png" /></figure><p>Kafka actually offers zombie fencing capabilities that work in a similar fashion to what we’ve just modelled here. Central to Kafka’s implementation of zombie fencing is the rebalancing protocol. As we discussed briefly already, rebalancing is the process of redistributing topic-partitions between members of a consumer group. Kafka brokers will initiate a <strong>rebalancing </strong>of a consumer group whenever:</p><ol><li>A new instance attempts to join a consumer group or</li><li>An existing member of a consumer group attempts to leave or</li><li>When a Kafka broker stops receiving heartbeat signals from an existing member of the consumer group i.e. a potential zombie</li></ol><p>In any case, the Kafka broker will ask any current members of the consumer group to leave and rejoin the group within a certain timeframe. Eventually, once the Kafka broker has received all the <strong>JoinGroup</strong> requests or enough time has elapsed, the Kafka broker will respond with a <strong>JoinGroupResponse</strong>. Included in this response is a <strong>generation-id</strong>. This is a <strong>monotonically increasing</strong> value that Kafka tracks for each consumer group. Each time a consumer group rebalances, Kafka will increment this <strong>generation-id</strong>. As a result, only the application instances that have successfully participated in the most recent rebalancing round will have the latest <strong>generation-id</strong>. Any instances that failed to respond to the leave-and-rejoin request will still have the older <strong>generation-id</strong>.</p><p>Later, when an application instance attempts to consume or produce or commit a message to Kafka, it will include the <strong>generation-id</strong> as part of the request to the Kafka broker. The broker will check if this value matches the latest <strong>generation-id</strong> in it’s records and if it does it will allow the request. Otherwise, it will reject the request which will cause the application instance to throw an error and die, thereby removing any potential zombies from the system.</p><p>Hopefully you can see the striking similarities between what we’ve just modelled and how Kafka implements zombie fencing. In particular, you should have noted the role of <strong>generation-id</strong> which acts as the fencing token, the Kafka broker which acts as the coordinator, and the application instances which act like workers.</p><p>If you want to learn even more about how exactly-once semantics are implemented in Kafka, check out <a href="https://cwiki.apache.org/confluence/display/KAFKA/KIP-447%3A+Producer+scalability+for+exactly+once+semantics">KIP-447: Producer Scalability for Exactly Once Semantics</a>.</p><blockquote>Kafka actually offers two ways to fence zombies; one is “consumer-side” zombie fencing (which we described above) and the other is “producer-side” zombie fencing which you can learn more about from <a href="https://cwiki.apache.org/confluence/display/KAFKA/KIP-98+-+Exactly+Once+Delivery+and+Transactional+Messaging">KIP-98: Exactly Once Delivery and Transactional Messaging</a>.</blockquote><h3>Exactly-Once is a Hard Problem</h3><iframe src="https://cdn.embedly.com/widgets/media.html?type=text%2Fhtml&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;schema=twitter&amp;url=https%3A//x.com/mathiasverraes/status/632260618599403520%3Flang%3Den&amp;image=" width="500" height="281" frameborder="0" scrolling="no"><a href="https://medium.com/media/a974aff985ac03874a461f3bc64b9c01/href">https://medium.com/media/a974aff985ac03874a461f3bc64b9c01/href</a></iframe><p>Although we’ve gotten closer to an exactly-once design, it’s important to note that to be truly, truly exactly-once, our system must handle not just the possibility of <strong>worker</strong> zombies but also <strong>coordinator</strong> zombies as well. Alas, this problem is well out of the scope our simple spec (not to mention a beginner friendly intro-to-<em>TLA+</em> blogpost series) and is left as a learning exercise for keen readers to implement.</p><h3>Spec</h3><p>After all of our changes, this is what our final <em>TLA</em>+ spec looks like:</p><pre><strong>---- MODULE ExactlyOnce ----<br><br>EXTENDS Sequences, Integers<br><br>CONSTANT NULL<br><br>VARIABLES InputTopic, Buffer, OutputTopic, CommittedConsumerOffset, PC, CurrentToken, Token, RemainingRestarts<br><br>vars == &lt;&lt;InputTopic, Buffer, OutputTopic, CommittedConsumerOffset, PC, CurrentToken, Token, RemainingRestarts&gt;&gt;<br><br>Processes == {1, 2}<br><br>Init ==<br>    /\ InputTopic = &lt;&lt;1&gt;&gt;<br>    /\ Buffer = [ process \in Processes |-&gt; NULL ]<br>    /\ OutputTopic = &lt;&lt;&gt;&gt;<br>    /\ CommittedConsumerOffset = 1<br>    /\ PC = [ process \in Processes |-&gt; &quot;AcquireToken&quot; ]<br>    /\ CurrentToken = 0<br>    /\ Token = [ process \in Processes |-&gt; NULL ]<br>    /\ RemainingRestarts = [ process \in Processes |-&gt; 1 ]<br><br>MessagesAvailable == CommittedConsumerOffset &lt; Len(InputTopic) + 1<br><br>Update(function, x, y) == [ function EXCEPT ![x] = y ]<br><br>AcquireToken(process) ==<br>    /\ PC[process] = &quot;AcquireToken&quot;<br>    /\ CurrentToken&#39; = CurrentToken + 1<br>    /\ Token&#39; = Update(Token, process, CurrentToken&#39;)<br>    /\ PC&#39; = Update(PC, process, &quot;Consume&quot;)<br>    /\ UNCHANGED &lt;&lt;InputTopic, Buffer, OutputTopic, CommittedConsumerOffset, RemainingRestarts&gt;&gt;<br><br>Consume(process) ==<br>    /\ PC[process] = &quot;Consume&quot;<br>    /\ IF MessagesAvailable<br>       THEN /\ Buffer&#39; = Update(Buffer, process, InputTopic[CommittedConsumerOffset])<br>            /\ PC&#39; = Update(PC, process, &quot;ProduceCommit&quot;)<br>       ELSE /\ Buffer&#39; = Update(Buffer, process, NULL)<br>            /\ PC&#39; = Update(PC, process, &quot;Done&quot;)<br>    /\ UNCHANGED &lt;&lt;InputTopic, OutputTopic, CommittedConsumerOffset, CurrentToken, Token, RemainingRestarts&gt;&gt;<br><br>ProduceCommit(process) ==<br>    /\ PC[process] = &quot;ProduceCommit&quot;<br>    /\ IF Token[process] = CurrentToken<br>       THEN /\ OutputTopic&#39; = Append(OutputTopic, Buffer[process])<br>            /\ CommittedConsumerOffset&#39; = Buffer[process] + 1<br>            /\ PC&#39; = Update(PC, process, &quot;Consume&quot;)<br>            /\ UNCHANGED &lt;&lt;InputTopic, Buffer, CurrentToken, Token, RemainingRestarts&gt;&gt;<br>       ELSE /\ PC&#39; = Update(PC, process, &quot;Fenced&quot;)<br>            /\ UNCHANGED &lt;&lt;InputTopic, Buffer, OutputTopic, CommittedConsumerOffset, CurrentToken, Token, RemainingRestarts&gt;&gt;<br><br>Fenced(process) ==<br>    /\ PC[process] = &quot;Fenced&quot;<br>    /\ UNCHANGED vars<br><br>Done(process) ==<br>    /\ PC[process] = &quot;Done&quot;<br>    /\ UNCHANGED vars<br><br>Restart(process) ==<br>    /\ PC[process] \notin {&quot;Fenced&quot;, &quot;Done&quot;}<br>    /\ RemainingRestarts[process] &gt; 0<br>    /\ Buffer&#39; = Update(Buffer, process, NULL)<br>    /\ PC&#39; = Update(PC, process, &quot;AcquireToken&quot;)<br>    /\ RemainingRestarts&#39; = Update(RemainingRestarts, process, RemainingRestarts[process] - 1)<br>    /\ UNCHANGED &lt;&lt;InputTopic, OutputTopic, CommittedConsumerOffset, CurrentToken, Token&gt;&gt;<br><br>Next ==<br>    \E process \in Processes:<br>        \/ AcquireToken(process)<br>        \/ Consume(process)<br>        \/ ProduceCommit(process)<br>        \/ Restart(process)<br>        \/ Fenced(process)<br>        \/ Done(process)<br><br>Fairness ==<br>    \E process \in Processes:<br>        /\ WF_vars(Next)<br>        /\ SF_vars(ProduceCommit(process))<br><br>Spec ==<br>    /\ Init<br>    /\ [][Next]_vars<br>    /\ Fairness<br><br>Termination == &lt;&gt;[](\A process \in Processes: PC[process] \in {&quot;Fenced&quot;, &quot;Done&quot;})<br><br>NoDuplicatesIn(seq) ==<br>    \A i, j \in 1..Len(seq):<br>        i /= j =&gt; seq[i] /= seq[j]<br><br>NoDuplicates == NoDuplicatesIn(OutputTopic)<br><br>SeqContains(seq, value) ==<br>    \E x \in 1..Len(seq):<br>        seq[x] = value<br><br>SeqContainsAll(seq, values) ==<br>    \A i \in 1..Len(values):<br>        SeqContains(seq, values[i])<br><br>NoMissingData == &lt;&gt;[](SeqContainsAll(OutputTopic, InputTopic))<br><br>====</strong></pre><p>And the corresponding <em>TLC</em> file:</p><pre><strong>SPECIFICATION Spec<br>CONSTANT NULL = NULL<br>INVARIANT NoDuplicates<br>PROPERTY Termination NoMissingData</strong></pre><p>Even after including all the empty lines, our entire spec is still only 110 lines.</p><h3>Reflections</h3><h4>When is TLA+ useful?</h4><p><em>TLA</em>+ tends to be most useful in <strong>non-deterministic</strong> situations e.g. distributed systems, highly concurrent systems, etc. In our case, the non-determinism came from the random possibility of failures and zombies. As humans, it can be hard for us to spot non-deterministic bugs. For example, our spec defines 556 distinct states. Imagine trying to enumerate all of these possibilities by hand, let alone checking them. This is where writing out a formal spec and checking it with <em>TLC</em> is invaluable.</p><p>This is not to say that a system has to be non-deterministic for it to be worth modelling in <em>TLA+</em>. <em>TLA+</em> still gives you a common and precise language for communicating system designs with other developers. That alone is extremely valuable.</p><h4>What are some of the downsides of TLA+?</h4><p>As awesome as <em>TLA+</em> is, it does not give you a functioning system, only a design for one. Even worse, there’s currently no way to test if any implementations are faithful to the design. To be fair though, I don’t personally know of any popular tool in this space that can do both well.</p><h4>Learn more</h4><p>This was by no means intended to be a comprehensive introduction to <em>TLA+</em>. If you’re interested in diving deeper, I recommend the free <a href="https://lamport.azurewebsites.net/tla/book.html#download">Specifying Systems</a> book by Leslie Lamport (the creator of <em>TLA+</em>).</p><h4>Lastly …</h4><p>If you’ve gotten this far, congratulations, you’ve read more than 20,000 words! Hopefully you enjoyed the series and if you did, please give this article some 👏 on Medium. See you next time!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2d7035e1379e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Modelling Exactly-Once Delivery Using TLA+]]></title>
            <link>https://medium.com/@fqaiser94/modelling-exactly-once-using-tla-9512e1eb8ca5?source=rss-ac4d9cb6496a------2</link>
            <guid isPermaLink="false">https://medium.com/p/9512e1eb8ca5</guid>
            <category><![CDATA[exactly-once-processing]]></category>
            <category><![CDATA[formal-verification]]></category>
            <category><![CDATA[tla-plus]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Farooq Qaiser]]></dc:creator>
            <pubDate>Tue, 10 Sep 2024 13:32:35 GMT</pubDate>
            <atom:updated>2025-08-18T01:33:40.563Z</atom:updated>
            <content:encoded><![CDATA[<h3>Modelling Exactly-Once Delivery Using TLA+ Part 3: Modelling Failures and Transactions</h3><p><em>TLA+</em> is a language for writing system specifications and discovering fundamental design errors quickly. In this series of blogposts, we’ll introduce <em>TLA+</em> by iteratively modelling and refining our design for a simple application that can read and write messages from/to Kafka in an exactly-once fashion. This will be a four-part series consisting of:</p><ol><li><a href="https://medium.com/@fqaiser94/exactly-once-modelling-using-tla-3c792655be44">Writing a Specification</a></li><li><a href="https://medium.com/@fqaiser94/modelling-exactly-once-using-tla-f3eb15303b27">Checking a Specification</a></li><li><a href="https://medium.com/@fqaiser94/modelling-exactly-once-using-tla-9512e1eb8ca5"><strong>Modelling Failures and Transactions</strong></a></li><li><a href="https://medium.com/@fqaiser94/modelling-exactly-once-using-tla-2d7035e1379e">Modelling Zombies and Fencing</a></li></ol><p>You can find all of the code for this series in this <a href="https://github.com/fqaiser94/tla-exactly-once">GitHub repo</a>.</p><p><em>Also, if you have interesting systems engineering problems and are looking for a strong Software Engineer, feel free to reach out via </em><a href="https://www.linkedin.com/in/fqaiser94/"><em>LinkedIn</em></a><em>.</em></p><h3>Introduction</h3><p>We ended the last post on a bit of a cliffhanger suggesting our specification is not useful because it makes some unrealistic assumptions. In this post, we’ll start by trying to uncover these assumptions using state graphs. After that, we’ll refactor our spec to remove these assumptions and make it more realistic. However, once we do that, we’ll discover problems in the exactly-once-ness of our design. And so, we’ll finish off by updating our design to make it robust to duplicates. Buckle up, all of our hard work from <a href="https://medium.com/@fqaiser94/exactly-once-modelling-using-tla-3c792655be44">Part 1</a> and <a href="https://medium.com/@fqaiser94/modelling-exactly-once-using-tla-f3eb15303b27">Part 2</a> is about to start paying off!</p><h3>State graph</h3><p>As already mentioned, our specification currently has some unrealistic assumptions embedded within it. Unfortunately, as <em>TLA</em>+ newbies, it might be hard to see these assumptions from just reading the spec. To get a slightly different perspective, let’s try to visualize our spec as a <strong>state graph</strong>.</p><p>State graphs are a fairly intuitive way of visualizing the behaviours of a system, where <strong>nodes</strong> (boxes) are used to represent distinct states and <strong>edges</strong> (arrows) are used to represent possible state transitions. Since <em>TLA</em>+ specs are already a formal description of the behaviours of a system, it should come as no surprise that we can generate a state graph directly from our spec using <em>TLC</em> and <em>Graphviz </em>(installation instructions <a href="https://graphviz.org/download/#mac">here</a>).</p><p>The first step is to translate our spec into a <em>DOT</em> file using <em>TLC</em>:</p><pre>java -cp tla2tools.jar tlc2.TLC -dump dot,colorize,actionLabels ExactlyOnce.dot ExactlyOnce.tla</pre><p>We can then generate a visualization from the <em>DOT</em> file using <em>Graphviz</em>:</p><pre>dot -Tpng ExactlyOnce.dot -o ExactlyOnce.png</pre><p>Which should generate an image similar to this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/473/1*phCE4d2p6VMwLgNwNUQ7ug.png" /><figcaption>Figure 1</figcaption></figure><p>This graph shows all the states and state transitions that are possible in our system as we’ve specified it. We have two boxes indicating the two possible states our system can be in at any moment in time. We also have arrows showing all the possible steps our system can take. The solid arrow indicates the only possible way to go from our initial state to our terminal state is via the <strong>ConsumeProduceCommit</strong> step. We also have a pair of dashed arrows to indicate steps where no variables change i.e. stuttering steps and/or <strong>Done</strong> steps.</p><p>As far as systems go, this is an incredibly simple one. In fact, if our system was truly this simple, it would not be worth our time modelling it in <em>TLA</em>+. However before we prematurely conclude this series has been a waste of time, let’s consider what assumptions are embedded inside our <strong>ConsumeProduceCommit</strong> step.</p><h3>Atomicity</h3><p>If we compare the state of our system before and after the <strong>ConsumeProduceCommit</strong> step, we can see we’re assuming that our system will during this single step:</p><ol><li><strong>Successfully</strong> consume a message</li><li><strong>And</strong> <strong>successfully</strong> produce a message</li><li><strong>And</strong> <strong>successfully</strong> commit our consumer offset</li></ol><p>In other words, we’re assuming that we can build a system that can consume, produce, and commit messages from/to Kafka as a single<strong> atomic </strong>operation i.e. either the operation as a whole is executed completely or it is not executed at all but it is never executed partially.</p><p>Unfortunately, it’s impossible to consume, produce, and commit messages from/to Kafka as a single atomic operation in the real world. Each of consume, produce, and commit are independent operations that can potentially fail and as a result, there is no way to guarantee we won’t fail partway through the process e.g. we could fail after consuming and end up not producing or committing the consumed message.</p><blockquote>This is a gentle reminder that just because we can express something in TLA+ is no guarantee that we can actually build such a thing in real life. In fact, given how flexible the TLA+ language is, there are far more things we can express in TLA+ than we can actually build.</blockquote><p>As practical engineers, it’s not particularly useful to write specifications for systems we know we can’t build. Over the next couple of sections, we’ll gradually refactor our specification so it better reflects the realities of programming.</p><h3>Small Steps</h3><p>In <em>TLA</em>+, a step is atomic. <em>TLC</em> will not execute a step partially. Either all of the variable changes defined by a step will happen or none at all. As we already noted, we cannot consume, produce, and commit as a single atomic operation in the real world so it doesn’t make sense to model these as a single step in our <em>TLA</em>+ spec. We need to break up our “big” <strong>ConsumeProduceCommit</strong> step into smaller steps that better reflect the atomicity guarantees we have in the real world i.e. we need to model <strong>Consume</strong>, <strong>Produce</strong>, and <strong>Commit</strong> as separate steps in our spec. A naive first attempt at modelling this might look like the following:</p><pre><strong>Consume ==<br>    /\ MessagesAvailable<br>    /\ Buffer&#39; = InputTopic[CommittedConsumerOffset]<br>    /\ UNCHANGED &lt;&lt;InputTopic, OutputTopic, CommittedConsumerOffset&gt;&gt;<br><br>Produce ==<br>    /\ OutputTopic&#39; = Append(OutputTopic, Buffer)<br>    /\ UNCHANGED &lt;&lt;InputTopic, Buffer, CommittedConsumerOffset&gt;&gt;<br><br>Commit ==<br>    /\ CommittedConsumerOffset&#39; = Buffer + 1<br>    /\ UNCHANGED &lt;&lt;InputTopic, Buffer, OutputTopic&gt;&gt;<br><br>Next ==<br>    \/ Consume<br>    \/ Produce<br>    \/ Commit<br>    \/ Done</strong></pre><p>While this is certainly a step in the right direction, it still isn’t quite correct. Before you continue reading, take a moment to see if you can spot the problem.</p><h3>Modelling Sequential Logic</h3><p>We can find the problem relatively easily by running <em>TLC </em>which should throw the following <strong>RuntimeException</strong>:</p><pre><strong>Error: TLC threw an unexpected exception.<br>This was probably caused by an error in the spec or model.<br>See the User Output or TLC Console for clues to what happened.<br>The exception was a java.lang.RuntimeException: Attempted to apply the operator overridden by the Java method<br>public static tlc2.value.impl.IntValue tlc2.module.Integers.Plus(tlc2.value.impl.IntValue,tlc2.value.impl.IntValue),<br>but it produced the following error:<br>Cannot cast tlc2.value.impl.ModelValue to tlc2.value.impl.IntValue<br><br>Error: The behavior up to this point is:<br>State 1: &lt;Initial predicate&gt;<br>/\ CommittedConsumerOffset = 1<br>/\ OutputTopic = &lt;&lt;&gt;&gt;<br>/\ Buffer = NULL<br>/\ InputTopic = &lt;&lt;1&gt;&gt;<br><br>Error: The error occurred when TLC was evaluating the nested<br>expressions at the following positions:<br>0. Line 29, column 5 to line 30, column 52 in ExactlyOnce<br>1. Line 29, column 8 to line 29, column 44 in ExactlyOnce<br>2. Line 29, column 35 to line 29, column 44 in ExactlyOnce</strong></pre><p>From the error message, we can see the <strong>RuntimeException</strong> is thrown inside our <strong>Commit</strong> step (line 29 refers to our <strong>Commit</strong> definition) when <em>TLC </em>attempts to apply the <strong>+</strong> operator while trying to compute the next <strong>CommittedConsumerOffset</strong> value based on the current <strong>Buffer</strong> value. Unfortunately, <strong>Buffer</strong> is equal to <strong>NULL</strong> and since we’ve modelled <strong>NULL</strong> as a model value and model values don’t support any operation other than equality, we get a <strong>RuntimeException</strong>.</p><p>That’s the problem at the code level. From a modelling perspective though, the real question we need to ask ourselves is why is <strong>Buffer</strong> equal to <strong>NULL</strong> when we reach the <strong>Commit</strong> step? Or rather, why does <strong>Buffer</strong> not contain a message like it’s supposed to do by the time we reach the <strong>Commit</strong> step? The answer to that can also be found in our error message. <em>TLC</em> shows us the sequence of states it explored before hitting this error. There is only one state; the initial state. This means that <em>TLC</em> attempted to take <strong>Commit</strong> as the very first step in our system! This is obviously wrong; we can’t commit a message before we’ve even consumed it.</p><p>So now we need to understand why <em>TLC</em> is taking <strong>Commit</strong> as the first step. If you look closely at our <strong>Commit</strong> definition, you will note that our spec doesn’t specify any conditions for when it is appropriate to take a<strong>Commit</strong> step. In other words, our spec says we can take a <strong>Commit</strong> step at any time. In fact, our <strong>Produce</strong> step also suffers from the same problem; it can also be taken at any moment in time!</p><p>What we need is a way to say that <strong>Consume</strong>, <strong>Produce</strong>, and <strong>Commit</strong> steps need to happen sequentially. This is easy to do in regular programming languages where we have explicit <strong>control flow</strong> and is probably something you normally take for granted. However, as we’ve said before, <em>TLA</em>+ is not a programming language. If anything, <em>TLA+</em> is a language for defining <strong>state machines</strong> and if we want to allow only certain <strong>state transitions</strong>, we have to specify them explicitly. In order to do that, we’ll need to introduce the concept of control flow into our specification:</p><pre><strong>VARIABLES InputTopic, Buffer, OutputTopic, CommittedConsumerOffset, PC    </strong>\* 1<strong><br><br>vars == &lt;&lt;InputTopic, Buffer, OutputTopic, CommittedConsumerOffset, PC&gt;&gt;  </strong>\* 2<strong><br><br>Init ==<br>    /\ InputTopic = &lt;&lt;1&gt;&gt;<br>    /\ Buffer = NULL<br>    /\ OutputTopic = &lt;&lt;&gt;&gt;<br>    /\ CommittedConsumerOffset = 1<br>    /\ PC = &quot;Consume&quot;                                                     </strong>\* 3<strong><br><br>Consume ==<br>    /\ PC = &quot;Consume&quot;                                                     </strong>\* 4<strong><br>    /\ IF MessagesAvailable<br>       THEN /\ Buffer&#39; = InputTopic[CommittedConsumerOffset]<br>            /\ PC&#39; = &quot;Produce&quot;                                            </strong>\* 5<strong><br>       ELSE /\ Buffer&#39; = NULL<br>            /\ PC&#39; = &quot;Done&quot;                                               </strong>\* 6<strong><br>    /\ UNCHANGED &lt;&lt;InputTopic, OutputTopic, CommittedConsumerOffset&gt;&gt;<br><br>Produce ==<br>    /\ PC = &quot;Produce&quot;                                                     </strong>\* 7<strong><br>    /\ OutputTopic&#39; = Append(OutputTopic, Buffer)<br>    /\ PC&#39; = &quot;Commit&quot;                                                     </strong>\* 8<strong><br>    /\ UNCHANGED &lt;&lt;InputTopic, Buffer, CommittedConsumerOffset&gt;&gt;<br><br>Commit ==<br>    /\ PC = &quot;Commit&quot;                                                      </strong>\* 9<strong><br>    /\ CommittedConsumerOffset&#39; = Buffer + 1<br>    /\ PC&#39; = &quot;Consume&quot;                                                    </strong>\* 10<strong><br>    /\ UNCHANGED &lt;&lt;InputTopic, Buffer, OutputTopic&gt;&gt;<br><br>Done ==<br>    /\ PC = &quot;Done&quot;                                                        </strong>\* 11<strong><br>    /\ UNCHANGED vars<br><br>Termination == &lt;&gt;[](PC = &quot;Done&quot;)</strong>                                          \* 12</pre><ol><li>We’ll use the same technique <em>PlusCal</em> (a language that compiles down to <em>TLA</em>+) does for modelling control flow and introduce a new variable <strong>PC</strong> to explicitly represent the <strong>program counter </strong>state in our spec. The term “program counter” is usually used to refer to a special register in a computer’s processor that contains the memory address for the next instruction to be executed. For the purposes of our specification though, we can model this more simply as a string value indicating the next step to be executed.</li><li>Just like every other variable in our system, we need to make sure to add <strong>PC</strong> to our <strong>vars</strong> sequence.</li><li>Our initial state predicate just needs to specify the initial value of the <strong>PC</strong> variable, which we’ll say should be <strong>&quot;Consume&quot;</strong>.</li><li>In our <strong>Consume</strong> step, we add a new condition that specifies that we can only take this step as long as <strong>PC = &quot;Consume&quot;</strong>. This change and the change to our initial state predicate are what ensure the first step our system can take is only ever the<strong>Consume</strong> step.</li><li>In addition, each step now needs to specify what the next value of <strong>PC</strong> should be. So in our <strong>Consume</strong> step, in the case where there are still messages available, we specify the value of <strong>PC</strong> in the next state should be <strong>&quot;Produce&quot;</strong>.</li><li>In the case where there are no more messages available, we specify the value of <strong>PC</strong> in the next state should be <strong>&quot;Done&quot;</strong>.</li><li>Similarly to what we did in our <strong>Consume</strong> step, in our <strong>Produce</strong> step we add a new condition that specifies that we can only take this step as long as <strong>PC = &quot;Produce&quot;</strong>.</li><li>We also specify the value of <strong>PC</strong> in the next state should be <strong>&quot;Commit&quot;</strong>.</li><li>In our <strong>Commit</strong> step, we add a new condition that specifies that we can only take this step as long as <strong>PC = &quot;Commit&quot;</strong>.</li><li>We also specify the value of <strong>PC</strong> in the next state should be <strong>&quot;Consume&quot;</strong>.</li><li>The only change we need to make to our <strong>Done</strong> step is to specify that we can only take this step as long as <strong>PC = &quot;Done&quot;</strong>.</li><li>Lastly, we can refine our <strong>Termination</strong> property a little bit. Previously, we defined termination as eventually always there are no more messages available to consume. While this is still true, it’s a relatively indirect way of specifying our system’s behaviour in a terminated state. We can be more direct about this now; we can define <strong>Termination</strong> as simply the behaviour in which our program control state is <strong>eventually always</strong> equal to <strong>&quot;Done&quot;</strong>.</li></ol><p>We can verify visually if we’ve defined our state machine correctly by generating another state graph:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/473/1*V_wb6pEyQMD9jY1IcICvzA.png" /><figcaption>Figure 2</figcaption></figure><p>That’s looking more like how we expect our program to flow.</p><p>However, having 3 small steps that always succeed is not that much different from having 1 big step that always succeeds. Indeed, if we run <em>TLC</em>, we should see our spec still satisfies all of our desired properties and invariants. In reality though, there is no guarantee that our process won’t fail in between steps. This could be because of a random power surge, a network blip, nuclear fallout, an alien wielding a laser gun etc.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*whwEE9FhU7z1rzonaqG0yQ.jpeg" /><figcaption>Image generated using Microsoft Designer with the prompt “cartoon alien wielding laser gun”</figcaption></figure><p>In order to make our model more realistic, we need to introduce the possibility of random failures in between steps.</p><h3>Modelling Random Failures</h3><p>As distributed systems engineers will happily remind you, things can fail anywhere and at any time. Our process could fail immediately. Our process could fail after consuming a message. Our process could fail after producing a message. Our process could fail after committing offsets. Each time our process fails, it must start all over again from the <strong>Consume</strong> step. We can define this behaviour as yet another step in our spec:</p><pre><strong>Restart ==                                                             </strong>\* 1<strong><br>    /\ PC /= &quot;Done&quot;                                                    </strong>\* 2<strong><br>    /\ Buffer&#39; = NULL                                                  </strong>\* 3<strong><br>    /\ PC&#39; = &quot;Consume&quot;                                                 </strong>\* 4<strong><br>    /\ UNCHANGED &lt;&lt;InputTopic, OutputTopic, CommittedConsumerOffset&gt;&gt;  </strong>\* 5<strong><br><br>Next ==<br>    \/ Consume<br>    \/ Produce<br>    \/ Commit<br>    \/ Done<br>    \/ Restart                                                         </strong>\* 6</pre><ol><li>We’ll call the operator defining this step <strong>Restart</strong>. The idea here is that this step always restarts our process from the <strong>Consume</strong> step.</li><li>We’ll specify that we can only take this step as long as <strong>PC</strong> does not equal to <strong>&quot;Done&quot;</strong>. The reason for this is that our <strong>Done</strong> step really represents a system that has terminated so it doesn’t make a whole lot of sense for our our application to be able to restart if it’s already terminated. <br> <br>If you’re wondering why we don’t have a <strong>PC = &quot;Restart&quot;</strong> expression in our <strong>Restart</strong> step like we do for other steps, it’s important to remember that <strong>PC</strong> represents our program counter state and failures/restarts aren’t really a program counter state.</li><li>Here, we’re simulating the loss of any in-memory state when we restart by specifying the next value of <strong>Buffer</strong> as <strong>NULL</strong>.</li><li>We specify that our process has to start from the <strong>Consume</strong> step all over again by specifying the value of <strong>PC</strong> in the next state as <strong>&quot;Consume&quot;</strong>.</li><li>As usual, we have to specify all the other variables that are left unchanged by this step.</li><li>Finally, we add <strong>Restart</strong> as yet another option to our <strong>Next</strong> disjunction.</li></ol><p>That’s pretty much all we need to do to simulate random failures. At this point, we can try running our spec through <em>TLC</em> to see if we’re still able to maintain our desired properties and invariants in the presence of random failures. Unfortunately, you should see our <strong>NoDuplicates</strong> invariant is now being violated in at least one sequence of steps:</p><pre><strong>Error: Invariant NoDuplicates is violated.<br><br>Error: The behavior up to this point is:<br><br>State 1: &lt;Initial predicate&gt;<br>/\ CommittedConsumerOffset = 1<br>/\ OutputTopic = &lt;&lt;&gt;&gt;<br>/\ Buffer = NULL<br>/\ InputTopic = &lt;&lt;1&gt;&gt;<br>/\ PC = &quot;Consume&quot;<br><br>State 2: &lt;Consume line 21, col 5 to line 27, col 69 of module ExactlyOnce&gt;<br>/\ CommittedConsumerOffset = 1<br>/\ OutputTopic = &lt;&lt;&gt;&gt;<br>/\ Buffer = 1<br>/\ InputTopic = &lt;&lt;1&gt;&gt;<br>/\ PC = &quot;Produce&quot;<br><br>State 3: &lt;Produce line 30, col 5 to line 33, col 64 of module ExactlyOnce&gt;<br>/\ CommittedConsumerOffset = 1<br>/\ OutputTopic = &lt;&lt;1&gt;&gt;<br>/\ Buffer = 1<br>/\ InputTopic = &lt;&lt;1&gt;&gt;<br>/\ PC = &quot;Commit&quot;<br><br>State 4: &lt;Restart line 46, col 5 to line 49, col 69 of module ExactlyOnce&gt;<br>/\ CommittedConsumerOffset = 1<br>/\ OutputTopic = &lt;&lt;1&gt;&gt;<br>/\ Buffer = NULL<br>/\ InputTopic = &lt;&lt;1&gt;&gt;<br>/\ PC = &quot;Consume&quot;<br><br>State 5: &lt;Consume line 21, col 5 to line 27, col 69 of module ExactlyOnce&gt;<br>/\ CommittedConsumerOffset = 1<br>/\ OutputTopic = &lt;&lt;1&gt;&gt;<br>/\ Buffer = 1<br>/\ InputTopic = &lt;&lt;1&gt;&gt;<br>/\ PC = &quot;Produce&quot;<br><br>State 6: &lt;Produce line 30, col 5 to line 33, col 64 of module ExactlyOnce&gt;<br>/\ CommittedConsumerOffset = 1<br>/\ OutputTopic = &lt;&lt;1, 1&gt;&gt;<br>/\ Buffer = 1<br>/\ InputTopic = &lt;&lt;1&gt;&gt;<br>/\ PC = &quot;Commit&quot;</strong></pre><p>Notice how <strong>OutputTopic</strong> is equal to <strong>&lt;&lt;1, 1&gt;&gt;</strong> in the final state; these are the duplicates that are violating our <strong>NoDuplicates</strong> invariant. We can also generate a state graph to see the problem more visually:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7wIkRfkAGkErsNHYgNaZQA.png" /><figcaption>Figure 3</figcaption></figure><p>Note that this visualization doesn’t show the full state space, just the state space that was explored before <em>TLC</em> discovered a state where our <strong>NoDuplicates</strong> property was violated, which you can see in the bottom-right corner.</p><blockquote>You could try to explore the whole state space by removing the <strong>NoDuplicates</strong> invariant temporarily from your TLC configuration file. However, in that case, you would find that TLC never finishes exploring as there are an infinite number of states that TLC will explore without the <strong>NoDuplicates</strong> invariant. You could have 1 duplicate, 2 duplicates, 3 duplicates, etc.</blockquote><p>Discovering problems like this can be difficult in regular programming because it’s usually hard to simulate failures at exactly the right point in our code. With <em>TLA+</em> however it’s easy as <em>TLC</em> will always attempt to fully explore the state space.</p><p>So, we made our model more realistic and subsequently discovered a flaw in our design. Now we need to fix it. In the next section, we’ll discuss how we can adapt our design so that we can continue to maintain our <strong>NoDuplicates</strong> invariant even in a world with random failures.</p><blockquote>Random failures might seem like a edge case scenario but this in only true in the small. Past a certain point of scale, problems that were previously only rare occurrences start to become likely if not common events (and don’t forget about correlated/compounding failures!). What this means is that, if you plan to scale, failures are a reality that you need to account for in your design. Also, if you’re going to call something exactly-once, it had better be exactly-once not just in the happy paths but also when things are going wrong.</blockquote><h3>Transactions</h3><p>Before we jump into solution-ing, let’s try to understand the problem a little better. If we take a closer look at our state graph (<em>Figure 4</em>), we can see that not all <strong>Restart</strong> steps result in duplicates. For example, following the sequence of steps highlighted in green below does not result in duplicates in our <strong>OutputTopic</strong> despite the fact that this sequence allows for restarts in 4 different places.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*TjnUgsmZN_8uPn9aDyTKoA.png" /><figcaption>Figure 4</figcaption></figure><p>On the other hand, if our system follows the sequence of steps highlighted in red below, we do end up with duplicates in our <strong>OutputTopic</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xoPj5zNAP9wtMuCJCmZE9A.png" /><figcaption>Figure 5</figcaption></figure><p>Based on this, we can make a few specific observations:</p><ul><li>If we fail after our process launches, this does <strong>not</strong> result in duplicates</li><li>If we fail after our <strong>Consume</strong> step, this does <strong>not</strong> result in duplicates</li><li>If we fail after our <strong>Produce </strong>step, this <em>does</em> result in duplicates</li><li>If we fail after our <strong>Commit</strong> step, this does <strong>not</strong> result in duplicates</li></ul><p>This should make intuitive sense! Once we’ve produced a message, it’s gone. If we fail to commit our consumer offset, we’ll restart from the last committed consumer offsets and end up consuming and producing the same message all over again. Failing at any other point in our code has no impact on duplicates.</p><p>Therefore, we could argue that our fundamental problem is that our system does not guarantee that we will always commit our offsets after we’ve produced a message. This is the “critical phase” in our program logic. If we could somehow eliminate the possibility of failure between producing and committing a message, we should be able to close this source of duplicates. Luckily, we don’t have to think about this too hard in our heads; we can just test out our theory quickly using <em>TLA+</em>!</p><pre><strong>Consume ==<br>    /\ PC = &quot;Consume&quot;<br>    /\ IF MessagesAvailable<br>       THEN /\ Buffer&#39; = InputTopic[CommittedConsumerOffset]<br>            /\ PC&#39; = &quot;ProduceCommit&quot;                                   </strong>\* 3<strong><br>       ELSE /\ Buffer&#39; = NULL<br>            /\ PC&#39; = &quot;Done&quot;<br>    /\ UNCHANGED &lt;&lt;InputTopic, OutputTopic, CommittedConsumerOffset&gt;&gt;  <br><br>ProduceCommit ==                                                       </strong>\* 1<strong><br>    /\ PC = &quot;ProduceCommit&quot;<br>    /\ OutputTopic&#39; = Append(OutputTopic, Buffer)<br>    /\ CommittedConsumerOffset&#39; = Buffer + 1<br>    /\ PC&#39; = &quot;Consume&quot;<br>    /\ UNCHANGED &lt;&lt;InputTopic, Buffer&gt;&gt;<br><br>Next ==<br>    \/ Consume<br>    \/ ProduceCommit                                                   </strong>\* 2<strong><br>    \/ Done<br>    \/ Restart</strong></pre><ol><li>Here we’re just combining our <strong>Produce</strong> and <strong>Commit</strong> steps back together. Since a step is atomic in <em>TLA</em>+, there’s no way we can fail between producing and committing now.</li><li>Now that we’ve removed our <strong>Produce</strong> and <strong>Commit</strong> steps, we need to update any references to them, starting with our <strong>Next</strong> step where we can replace the <strong>Produce</strong> and <strong>Commit</strong> references with just <strong>ProduceCommit</strong>.</li><li>Last but not least, we need to update the reference to <strong>&quot;Produce&quot;</strong> with <strong>&quot;ProduceCommit&quot;</strong> in our <strong>Consume</strong> step in the case where there are <strong>MessagesAvailable</strong>.</li></ol><p>This probably feels like we’re taking a step backwards. Didn’t we just split <strong>Consume</strong>, <strong>Produce</strong>, and <strong>Commit</strong> into separate steps because it was impossible to build a system that could execute all three actions as a single atomic operation? The difference here is that it <em>is</em> possible to build a system where we can <strong>Produce </strong>and<strong> </strong><strong>Commit</strong> messages to Kafka as a single atomic operation using the <a href="https://cwiki.apache.org/confluence/display/KAFKA/KIP-98+-+Exactly+Once+Delivery+and+Transactional+Messaging">Kafka Transactions API</a> that was added in version 0.11.</p><blockquote>In reality, even if you’re using the Kafka Transactions API, you will still in most cases still end up producing messages to your topic before you commit the transaction. However, your consumers will not be able to read those messages until the transaction is committed (assuming you’ve correctly configured your consumers with <strong>isolation.level = &quot;read_committed&quot;</strong>). So the overall, observable effect is that of an all-or-nothing operation from the consumer’s perspective. For this reason, it’s correct to model this API as a single atomic step. To learn more about how transactions are implemented in Kafka, see <a href="https://cwiki.apache.org/confluence/display/KAFKA/KIP-98+-+Exactly+Once+Delivery+and+Transactional+Messaging">KIP-98</a>.</blockquote><p>So we might have a solution that we can actually implement in reality! We just need to make sure this new design actually satisfies our desired properties. Running <em>TLC</em> should reveal that we’re no longer violating our <strong>NoDuplicates</strong> invariant, hooray! Unfortunately, we’re violating a different property now; <strong>Termination</strong>.</p><h3>Strong Fairness</h3><p><em>TLC</em> is reporting that our <strong>Termination </strong>property is being violated in the following sequence of events:</p><pre><strong>Error: Temporal properties were violated.<br><br>Error: The following behavior constitutes a counter-example:<br><br>State 1: &lt;Initial predicate&gt;<br>/\ CommittedConsumerOffset = 1<br>/\ OutputTopic = &lt;&lt;&gt;&gt;<br>/\ Buffer = NULL<br>/\ InputTopic = &lt;&lt;1&gt;&gt;<br>/\ PC = &quot;Consume&quot;<br><br>State 2: &lt;Consume line 21, col 5 to line 27, col 69 of module ExactlyOnce&gt;<br>/\ CommittedConsumerOffset = 1<br>/\ OutputTopic = &lt;&lt;&gt;&gt;<br>/\ Buffer = 1<br>/\ InputTopic = &lt;&lt;1&gt;&gt;<br>/\ PC = &quot;ProduceCommit&quot;<br><br>Back to state 1: &lt;Restart line 41, col 5 to line 45, col 69 of module ExactlyOnce&gt;</strong></pre><p>Looking carefully, we can see that our <strong>ProduceCommit</strong> step is never taken in this sequence of steps. Our system always restarts before it can take this step, returning the system back to the initial state in a never-ending loop. As a result, our consumer offset never advances and we therefore never satisfy our definition of <strong>Termination</strong>.</p><p>While it’s nice to confirm that our system will never terminate if we always restart before committing our offsets, it’s much more useful to assume that even if the system restarts a few times, eventually the system will take a <strong>ProduceCommit</strong> step. If this is sounding familiar, that’s because we faced a similar problem in Part 2 with infinite stuttering steps. We fixed the problem there by introducing a <strong>weak fairness</strong> constraint. We can do something similar here as well:</p><pre><strong>Fairness ==<br>    /\ WF_vars(Next)<br>    /\ SF_vars(ProduceCommit)</strong>  \* 1</pre><ol><li>Previously, we defined <strong>Fairness</strong> as simply <strong>WF_vars(Next)</strong> i.e. weak fairness of the <strong>Next</strong> action. Weak fairness says that if an action is always enabled, it eventually happens. Our problem is that the <strong>ProduceCommit</strong> step isn’t <strong>always</strong> enabled. It is only <strong>intermittently</strong> enabled. Weak fairness does not guarantee that intermittently enabled actions will eventually happen. For those kind of semantics, we need to specify our action as <strong>strongly fair</strong>. We say an action is strongly fair if, given that said action isn’t permanently disabled, it will eventually happen. <br> <br>Similar to how we declare a step as weakly fair, we can mark a step as strongly fair using the <strong>SF_v(A)</strong> syntax, where <strong>A</strong> is the name of the action/step that changes variable <strong>v</strong>.</li></ol><p>If we rerun <em>TLC</em> now<em>, </em>we should see it report that our spec satisfies all of our declared properties and invariants now. We can confirm the same visually as well by generating a state graph from our spec:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*PitW7h5Y8-issFiglCJ2rQ.png" /><figcaption>Figure 6</figcaption></figure><p>That’s looking much “cleaner” now.</p><blockquote>Alternatively, instead of making our <strong><em>ProduceCommit</em></strong> step strongly fair, we could remove <strong><em>Termination</em></strong> and <strong><em>NoMissingData</em></strong> as desired properties. That’s a rational design decision to make in a world where avoiding duplicates is an invariant we want to uphold at all costs, even if that means our process stops making progress.</blockquote><h3>Spec</h3><p>After all of our changes, this is what our <em>TLA</em>+ spec looks like now:</p><pre><strong>---- MODULE ExactlyOnce ----<br><br>EXTENDS Sequences, Integers<br><br>CONSTANT NULL<br><br>VARIABLES InputTopic, Buffer, OutputTopic, CommittedConsumerOffset, PC<br><br>vars == &lt;&lt;InputTopic, Buffer, OutputTopic, CommittedConsumerOffset, PC&gt;&gt;<br><br>Init ==<br>    /\ InputTopic = &lt;&lt;1&gt;&gt;<br>    /\ Buffer = NULL<br>    /\ OutputTopic = &lt;&lt;&gt;&gt;<br>    /\ CommittedConsumerOffset = 1<br>    /\ PC = &quot;Consume&quot;<br><br>MessagesAvailable == CommittedConsumerOffset &lt; Len(InputTopic) + 1<br><br>Consume ==<br>    /\ PC = &quot;Consume&quot;<br>    /\ IF MessagesAvailable<br>       THEN /\ Buffer&#39; = InputTopic[CommittedConsumerOffset]<br>            /\ PC&#39; = &quot;ProduceCommit&quot;<br>       ELSE /\ Buffer&#39; = NULL<br>            /\ PC&#39; = &quot;Done&quot;<br>    /\ UNCHANGED &lt;&lt;InputTopic, OutputTopic, CommittedConsumerOffset&gt;&gt;<br><br>ProduceCommit ==<br>    /\ PC = &quot;ProduceCommit&quot;<br>    /\ OutputTopic&#39; = Append(OutputTopic, Buffer)<br>    /\ CommittedConsumerOffset&#39; = Buffer + 1<br>    /\ PC&#39; = &quot;Consume&quot;<br>    /\ UNCHANGED &lt;&lt;InputTopic, Buffer&gt;&gt;<br><br>Done ==<br>    /\ PC = &quot;Done&quot;<br>    /\ UNCHANGED vars<br><br>Restart ==<br>    /\ PC /= &quot;Done&quot;<br>    /\ Buffer&#39; = NULL<br>    /\ PC&#39; = &quot;Consume&quot;<br>    /\ UNCHANGED &lt;&lt;InputTopic, OutputTopic, CommittedConsumerOffset&gt;&gt;<br><br>Next ==<br>    \/ Consume<br>    \/ ProduceCommit<br>    \/ Done<br>    \/ Restart<br><br>Fairness ==<br>    /\ WF_vars(Next)<br>    /\ SF_vars(ProduceCommit)<br><br>Spec ==<br>    /\ Init<br>    /\ [][Next]_vars<br>    /\ Fairness<br><br>Termination == &lt;&gt;[](PC = &quot;Done&quot;)<br><br>NoDuplicatesIn(seq) ==<br>    \A i, j \in 1..Len(seq):<br>        i /= j =&gt; seq[i] /= seq[j]<br><br>NoDuplicates == NoDuplicatesIn(OutputTopic)<br><br>SeqContains(seq, value) ==<br>    \E x \in 1..Len(seq):<br>        seq[x] = value<br><br>SeqContainsAll(seq, values) ==<br>    \A i \in 1..Len(values):<br>        SeqContains(seq, values[i])<br><br>NoMissingData == &lt;&gt;[](SeqContainsAll(OutputTopic, InputTopic))<br><br>====</strong></pre><p>We didn’t make any changes to our <em>TLC</em> file but for completeness’ sake, here it is:</p><pre><strong>SPECIFICATION Spec<br>CONSTANT NULL = NULL<br>INVARIANT NoDuplicates<br>PROPERTY Termination NoMissingData</strong></pre><h3>Reflections</h3><p>A good chunk of the work we do when writing <em>TLA</em>+ is just abstraction. The challenge here is finding the right level of abstraction. We don’t want to abstract too much or we risk losing important details/nuances of our problem/domain. This was arguably part of the problem we had at the beginning of this post; we’d abstracted away too much of our program logic when we had a single <strong>ConsumeProduceCommit</strong> step and consequently missed important duplicate-generating edge cases.</p><p>At the same time, we don’t want to abstract too little either. For example, we chose to model <strong>Consume</strong>, <strong>Produce</strong>, and <strong>Commit</strong> as fairly high level steps. We could have gone much further and modelled all 488 pages of the <a href="https://kafka.apache.org/protocol">Kafka protocol</a> however this would require considerable effort for very little gain.</p><p>Finding a good balance is more of an art than a science and will depend heavily on your use case. That said, <strong>correct abstraction requires a solid understanding of your domain</strong>. There’s no getting around that. For example, it would be dangerous to assume that we can model Kafka transactions as single <strong>ProduceCommit</strong> step without a good understanding of the relevant APIs. In addition, it’s always a good idea to critically review the “grain of atomicity” at which you’re modelling operations in <em>TLA+ </em>to make sure they’re realistic. Lastly, while it’s probably more common for users to abstract too much rather than too little, it’s helpful to know that <em>TLA+</em> specifications are “<a href="https://lamport.azurewebsites.net/tla/future.pdf">seldom more than about 2000 lines</a>.” So if your specifications are starting to reach that range, you might just be abstracting too little.</p><p>However, once we got our model to the right level of abstraction (by modelling separate steps for <strong>Consume</strong>, <strong>Produce</strong>, and <strong>Commit</strong>, and modelling the possibility of arbitrary failures), <em>TLC</em> was easily able to surface issues in the exactly-once-ness of our design and we were able to quickly iterate from there with <em>TLC</em> acting almost like our copilot.</p><p>So are we done now? Surely after nearly 15,000 words across 3 blogposts, we must have a design that is truly exactly-once by now? 🙃 So far we’ve assumed that there is only ever one process that is consuming from the input topic and writing to the output topic. What happens when we have multiple processes running? Is it possible to generate duplicates in such a scenario? Tune into <a href="https://medium.com/@fqaiser94/modelling-exactly-once-using-tla-2d7035e1379e">Part 4</a> for an epic finale involving zombies and the noble art of fencing.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3PDaUGObmCHr_0XqObhWvA.jpeg" /><figcaption>Image generated using Microsoft Designer with the prompt “Fencer versus a zombie caroon style”</figcaption></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9512e1eb8ca5" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Modelling Exactly-Once Delivery Using TLA+]]></title>
            <link>https://medium.com/@fqaiser94/modelling-exactly-once-using-tla-f3eb15303b27?source=rss-ac4d9cb6496a------2</link>
            <guid isPermaLink="false">https://medium.com/p/f3eb15303b27</guid>
            <category><![CDATA[formal-verification]]></category>
            <category><![CDATA[tla-plus]]></category>
            <category><![CDATA[exactly-once-processing]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Farooq Qaiser]]></dc:creator>
            <pubDate>Wed, 07 Aug 2024 17:32:40 GMT</pubDate>
            <atom:updated>2025-08-18T01:33:16.368Z</atom:updated>
            <content:encoded><![CDATA[<h3>Modelling Exactly-Once Delivery Using TLA+ Part 2: Checking a Specification</h3><p><em>TLA+</em> is a language for writing system specifications and discovering fundamental design errors quickly. In this series of blogposts, we’ll introduce <em>TLA+</em> by iteratively modelling and refining our design for a simple application that can read and write messages from/to Kafka in an exactly-once fashion. This will be a four-part series consisting of:</p><ol><li><a href="https://medium.com/@fqaiser94/exactly-once-modelling-using-tla-3c792655be44">Writing a Specification</a></li><li><a href="https://medium.com/@fqaiser94/modelling-exactly-once-using-tla-f3eb15303b27"><strong>Checking a Specification</strong></a></li><li><a href="https://medium.com/@fqaiser94/modelling-exactly-once-using-tla-9512e1eb8ca5">Modelling Failures and Transactions</a></li><li><a href="https://medium.com/@fqaiser94/modelling-exactly-once-using-tla-2d7035e1379e">Modelling Zombies and Fencing</a></li></ol><p>You can find all of the code for this series in this <a href="https://github.com/fqaiser94/tla-exactly-once">GitHub repo</a>.</p><p><em>Also, if you have interesting systems engineering problems and are looking for a strong Software Engineer, feel free to reach out via </em><a href="https://www.linkedin.com/in/fqaiser94/"><em>LinkedIn</em></a><em>.</em></p><h3>Introduction</h3><p>We left off in Part 1 with a question; how do we know our spec is correct? <em>TLA+</em> provides only a grammar for specifying systems. Nothing about the way <em>TLA+</em> is written guarantees correctness. In fact, there are several things that are wrong about our specification the way it’s written currently. We need another tool to verify our designs. This is where <em>TLC</em> comes in.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*hli5FjUsdB99cvWJ" /><figcaption><a href="https://github.com/tlaplus/tlaplus">https://github.com/tlaplus/tlaplus</a></figcaption></figure><p>As noted on the official GitHub project page, <em>TLC</em> is a model checker for specifications written in <em>TLA+</em>. In short, it works by generating all the possible system behaviours permitted by the spec and then checking they don’t violate any of the desired properties. In this blogpost, we’ll see how we can use <em>TLC</em> to check the specification we wrote in part 1.</p><p>Heads-up; this post has a lot of words and very few visuals to go along with them. That said, the payoff will be worth it as in this post, we will lay the foundations we need to be able to refactor our spec confidently in <a href="https://medium.com/@fqaiser94/modelling-exactly-once-using-tla-9512e1eb8ca5">Part 3</a> and <a href="https://medium.com/@fqaiser94/modelling-exactly-once-using-tla-2d7035e1379e">Part 4</a> as we discover problems with the exactly-once-ness of our design.</p><h3>Running TLC</h3><p>The first thing we need to do is define a new file with the same name as our <em>TLA+</em> module; <strong>ExactlyOnce.cfg</strong>. Inside this file, we need to at a minimum declare our system’s specification formula like so:</p><pre><strong>SPECIFICATION Spec</strong>  \* 1</pre><ol><li><em>TLC </em>will use to use the declared <strong>SPECIFICATION</strong> formula <strong>Spec</strong> to generate all the possible system behaviours.</li></ol><p>Next, you’ll need to get a copy of the latest version of <strong>tla2tools.jar</strong> which is available for download from the official <a href="https://github.com/tlaplus/tlaplus/releases/tag/v1.7.3"><em>TLA</em>+ GitHub project’s releases</a> page. Once you have that in your working directory, we can run <em>TLC</em> just like any other regular Java program using:</p><pre><strong>java -cp tla2tools.jar tlc2.TLC ExactlyOnce.tla</strong></pre><p>The only required argument is the name of the <em>TLA</em>+ file we want to check. We don’t need to supply the <strong>ExactlyOnce.cfg</strong> file explicitly as <em>TLC</em> will automatically look for a <strong>.cfg</strong> file with the same name as our module in the current directory (this is why it’s important to name your modules and config files consistently).</p><p>Unfortunately though, when you run this command, you’ll see <em>TLC</em> throws the following error:</p><pre><strong>Error: The constant parameter NULL is not assigned a value by the configuration file.</strong></pre><p>Let’s try to understand what’s going on here.</p><h3>Specifying Constants</h3><p>Recall that in Part 1 of this series, we declared a <strong>CONSTANT NULL</strong> parameter in our <em>TLA</em>+ spec without actually specifying it’s value. While that’s totally valid in <em>TLA</em>+, <em>TLC</em> needs us to actually assign values to constants in order to be able to check a spec.</p><p>The question is, what value should we assign to our <strong>NULL</strong> parameter? This might seem a little paradoxical given that <strong>NULL</strong> is supposed to represent a missing value 😖 The trick here is to assign <strong>NULL</strong> a (<strong>sentinel)</strong> value that our system otherwise never expects to encounter for “real” data.</p><p>If we look closely at our spec, we can see that <strong>Buffer</strong> is the only variable that can equal <strong>NULL</strong> in our spec. Furthermore we can observe that, aside from <strong>NULL</strong>, <strong>Buffer</strong> is only ever equal an integer greater than 1 because of our decision to represent messages by their position inside the <strong>InputTopic</strong> sequence and the fact that sequences are 1-indexed in <em>TLA</em>+. As a result, we can assign the value 0 to our <strong>NULL</strong> parameter, since that is a value our system otherwise never expects. We can declare this in our <strong>ExactlyOnce.cfg</strong> file like so:</p><pre><strong>CONSTANT NULL = 0  </strong>\* 1</pre><ol><li>Declaring a value for a constant is pretty easy. We can just use the <strong>CONSTANT</strong> keyword followed by the name of the constant (as defined in our <em>TLA</em>+ spec) followed by an equals sign and then the actual value.</li></ol><p>If you try running <em>TLC</em> again, you should no longer see the error about an unassigned constant parameter.</p><h3>Checking for Deadlock</h3><p>Unfortunately, you’ll see a different<em>, </em>possibly more alarming error:</p><pre><strong>Error: Deadlock reached.</strong></pre><p>It’s not quite as bad as it sounds. We’ve actually made some progress as this time <em>TLC</em> has actually run and checked <em>some</em> system behaviours. Unfortunately, <em>TLC</em> discovered that, in at least one sequence of steps, our system becomes <strong>deadlocked</strong>, which is another way of saying that after a certain number of steps, our system has no more steps it can take and effectively becomes stuck. <em>TLC</em> will even tell us in which state our system got stuck:</p><pre><strong>Error: The behavior up to this point is:<br><br>State 1: &lt;Initial predicate&gt;<br>/\ CommittedConsumerOffset = 1<br>/\ OutputTopic = &lt;&lt;&gt;&gt;<br>/\ InputTopic = &lt;&lt;1&gt;&gt;<br>/\ Buffer = NULL<br><br>State 2: &lt;ConsumeProduceCommit line 20, col 5 to line 24, col 27 of module ExactlyOnce&gt;<br>/\ CommittedConsumerOffset = 2<br>/\ OutputTopic = &lt;&lt;1&gt;&gt;<br>/\ InputTopic = &lt;&lt;1&gt;&gt;<br>/\ Buffer = 1</strong></pre><p>The question is why do we get stuck? If we look carefully at our spec, we’ll see that we’ve really only defined one possible step that our system can take; <strong>ConsumeProduceCommit</strong>. And recall that our definition of <strong>ConsumeProduceCommit</strong> states that our system can only take this step if <strong>MessagesAvailable</strong> is true, as shown here:</p><pre><strong>ConsumeProduceCommit ==<br>    /\ MessagesAvailable<br>    /\ Buffer&#39; = InputTopic[CommittedConsumerOffset]<br>    /\ OutputTopic&#39; = Append(OutputTopic, Buffer&#39;)<br>    /\ CommittedConsumerOffset&#39; = Buffer&#39; + 1<br>    /\ UNCHANGED InputTopic</strong></pre><p>If we look at <strong>State 2</strong> in the error message above, the state in which our system becomes deadlocked, we can see that <strong>MessagesAvailable</strong> must be false as our <strong>CommittedConsumerOffset</strong> (2) is greater than the length of the <strong>InputTopic</strong> sequence (1). Thus we reach the same conclusion as <em>TLC</em>, that there are indeed no further steps our system can take from this state given how we’ve specified our system.</p><p>Now, you might be tempted to argue that nothing is really wrong. Our application has successfully processed all the messages that were available and there are no more messages available to consume. Effectively, you could say our system has finished it’s work and so there shouldn’t be any further steps/states after that. Whilst this is a valid line of reasoning, in general in <em>TLA+ </em>we prefer to model systems as an <strong>infinite</strong> sequence of states.</p><p>This leads us to what may seem like another paradox; how do you model systems that can terminate as an infinite sequence of states? 🤔 The trick here is to model termination as a step, in which nothing changes, and that we can take infinitely and exclusively after we’ve taken it once. Yet again, this is just a matter of defining another operator in our <em>TLA</em>+ spec:</p><pre><strong>Done ==                    </strong>/* 1<strong><br>    /\ ~MessagesAvailable  </strong>/* 2<strong><br>    /\ UNCHANGED vars      </strong>/* 3</pre><ol><li>Here we’re defining a new step as an operator <strong>Done</strong>.</li><li>We specify that we can only take this step once we’ve consumed all the available messages.</li><li>Lastly, we specify that none of the variables in our system can change their values during this step as nothing be should happening if our system is terminated.</li></ol><p>We’re not done yet though (pun intended). Our new <strong>Done</strong> operator isn’t being referred to anywhere in our spec so let’s fix that:</p><pre><strong>Next == <br>  \/ ConsumeProduceCommit  </strong>/* 1<strong><br>  \/ Done                  </strong>/* 2</pre><ol><li>Previously our <strong>Next</strong> operator was defined as equal to <strong>ConsumeProduceCommit</strong>. Our system could always take this step if there were messages available to be consumed.</li><li>Now, we’ve expanded our definition of <strong>Next</strong> so that it is a <strong>disjunction</strong> (note the use of <strong>\/</strong> rather than <strong>/\</strong>) of two potential next steps; either our system can take a <strong>ConsumeProduceCommit</strong> step <strong>OR</strong> it can take a <strong>Done</strong> step, depending on the state of our system.</li></ol><p>Looking at our definition of <strong>Next</strong> now, it should be obvious that we’ve covered all possible scenarios and deadlock should be impossible as there is always a step our system can take, even if it’s the same one as before. We can verify this by re-running TLC:</p><pre><strong>java -cp tla2tools.jar tlc2.TLC ExactlyOnce.tla</strong></pre><p>You should see the command runs successfully this time without raising any further errors.</p><p>The absence of deadlock is a such a commonly desired property that <em>TLC</em> will check for this automatically by default. However to discover other problems in our spec, we need to define our own checks.</p><h3>Checking for Termination</h3><p>The next thing you typically want to check for in your system is termination i.e. does our system always eventually terminate? From our previous discussion whilst checking for deadlock, you might be confident that’s already the case but it’s always worth double-checking your assumptions explicitly.</p><p>In order to check for termination, we first need to decide what constitutes a terminal state in our system. In our case, we already figured this out when we were writing our <strong>Done</strong> operator; it’s when there are no longer any messages available to consume. We can therefore define termination in our <em>TLA</em>+ spec as follows:</p><pre><strong>Termination == &lt;&gt;[](~MessagesAvailable)</strong>  \* 1</pre><ol><li>We have a new symbol here: <strong>&lt;&gt;</strong>. Although it might look similar to <strong>&lt;&lt;&gt;&gt;</strong> which we used previously to declare sequences, the two operators are entirely unrelated. <strong>&lt;&gt;</strong> is another temporal-logic<strong> </strong>operator used to express the idea of <strong>eventually</strong> i.e. we can read an expression of the form <strong>&lt;&gt;F</strong> as “eventually F is true.”<br> <br>We’ve already previously discussed the meaning of <strong>[]</strong> which can be summarized as <strong>always</strong>. We can compose these two operators into a temporal formula of the form <strong>&lt;&gt;[]F</strong> which is generally read as “eventually F is always true.” To avoid ambiguity, we can also read it as “eventually, F becomes true and remains true always thereafter.” <br> <br>Thus we can read our definition of <strong>Termination</strong> as “eventually no messages are available always.”</li></ol><p>In order to check that <strong>Termination</strong> holds, we need to declare this property in our <strong>ExactlyOnce.cfg</strong> file like so:</p><pre><strong>PROPERTY Termination</strong>  \* 1</pre><ol><li>We can use the <strong>PROPERTY</strong> keyword to declare any properties we want <em>TLC</em> to check are eventually true in every behaviour exhibited by our system.</li></ol><p>If we try running <em>TLC</em> now, you might be surprised to discover that our system doesn’t actually always terminate:</p><pre><strong>Error: Temporal properties were violated.<br><br>Error: The following behavior constitutes a counter-example:<br><br>State 1: &lt;Initial predicate&gt;<br>/\ CommittedConsumerOffset = 1<br>/\ OutputTopic = &lt;&lt;&gt;&gt;<br>/\ InputTopic = &lt;&lt;1&gt;&gt;<br>/\ Buffer = NULL<br><br>State 2: Stuttering</strong></pre><p>And that’s because we forgot to account for <strong>stuttering</strong> in our spec. Previously, we mentioned that all (valid) <em>TLA</em>+ specs are <strong>stutter-invariant</strong> meaning they can always stutter between any two “real” actions. In fact, in <em>TLA</em>+ it’s perfectly valid behaviour for a system to stutter forever! That’s what’s happening in this case. After the initial state, the next step and every step after that is that a stutter step. Obviously, if our system never takes a <strong>ConsumeProduceCommit</strong> step, we’ll never consume any messages and thus our system will never satisfy our definition of <strong>Termination</strong>.</p><p>Another, perhaps more intuitive, way to think about this kind of behaviour is to imagine if our system crashed immediately and thereafter never recovered. In this worst case scenario, other events will continue to happen in the wider universe which are represented by stutter steps. This is the type of situation that <em>TLC</em> is effectively simulating for us with this stuttering-forever behaviour.</p><p>While it’s nice that we can simulate this, it’s not usually super useful to assume that a system can crash permanently. To get around this issue, we need to somehow express in <em>TLA</em>+ the idea that that if our <strong>Next</strong> step is <strong>enabled </strong>(i.e. it is possible to take a <strong>Next</strong> step), our system must eventually take that step (rather than stuttering forever). We can do exactly this by adding a <strong>fairness</strong> <strong>constraint </strong>to our spec. Before we introduce the syntax for doing this, let’s discuss quickly what exactly we mean by <strong>fairness</strong>.</p><p>By default, <em>TLA</em>+ considers all actions to be <strong>unfair</strong>, which is to say that there is no guarantee that a given action <strong>A</strong> will eventually be taken regardless of whether it can happen or not. In contrast, we say an action <strong>A</strong> is <strong>weakly fair </strong>if, given that an <strong>A</strong> step <em>can</em> always happen, then it eventually <em>does</em> happen. These are exactly the semantics we want for our <strong>Next</strong> step. Let’s see how we can specify our <strong>Next</strong> step as weakly fair in our spec:</p><pre><strong>Fairness == WF_vars(Next)  </strong>\* 1<strong><br><br>Spec ==<br>    /\ Init<br>    /\ [][Next]_vars<br>    /\ Fairness            </strong>\* 2</pre><ol><li>In <em>TLA</em>+, we can specify an action <strong>A</strong> that changes variable <strong>v</strong> as <strong>weakly fair</strong> by writing an expression of the form <strong>WF_v(A)</strong>. Thus, <strong>WF_vars(Next) </strong>is declaring that the <strong>Next</strong> action (which changes <strong>vars</strong>) is weakly fair<strong>.</strong></li><li>Here, we’re just adding our fairness constraint to our spec as another conjunction. In formal jargon, we say “our <strong>Spec</strong> is now defined to be our system’s specification with the added condition of weak fairness of the next-state relation which asserts that execution does not stop as long as one of the <strong>Next</strong> actions is enabled.”</li></ol><p>If we check this updated specification formula, <em>TLC</em> should no longer report any temporal property violations 👏👏👏</p><blockquote>For a more in-depth treatment of the concept of fairness, I highly recommend reading Hillel Wayne’s excellent <a href="https://www.hillelwayne.com/post/fairness/">Weak and Strong Fairness</a> blogpost. In fact, while you’re at it, just read all of his blogposts about TLA+.</blockquote><p>Hopefully, you’re starting to see a pattern by now. Every time we discover a problem in our spec, it’s usually because we’ve made some assumption in our heads but failed to write it down explicitly. <em>TLA</em>+ is not a language that takes anything for granted and it forces us to explicitly write down all of our assumptions.</p><h3>Checking for Duplicates</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*SPoxHtEy82zz9c3K.jpg" /></figure><p>So far we’ve checked for some of the usual properties you would expect of most systems; absence of deadlock and eventual termination. One of the key goals of this series however was to model a system that was exactly-once. An important property of <strong>exactly-once</strong> behaviour is to avoid generating duplicates (as compared to <strong>at-least-once</strong> behaviour). In our context, this means our <strong>OutputTopic</strong> should never contain any duplicated elements. We can express this property in <em>TLA</em>+ as follows:</p><pre><strong>NoDuplicatesIn(seq) ==                                 </strong>\* 1<strong><br>    \A i \in 1..Len(seq):                              </strong>\* 2<strong><br>        \A j \in 1..Len(seq):                          </strong>\* 3<strong><br>            IF i /= j THEN seq[i] /= seq[j] ELSE TRUE  </strong>\* 4 <strong>  <br><br>NoDuplicates == NoDuplicatesIn(OutputTopic)            </strong>\* 5</pre><ol><li>Here we’re declaring a new “helper” operator <strong>NoDuplicatesIn</strong>. As the name implies, the idea here is that we can use this operator to check that any given sequence doesn’t contain any duplicated elements. <br> <br>As you’ve probably noticed, the syntax defining for operators that can “accept arguments” is very similar to what you might see when you define a function in regular programming languages like Python (except there’s even less syntax/ceremony involved!).</li><li>In order to check that each element of a sequence of arbitrary length is distinct, we need to compare each element with each other. We’ll need to use a new operator to do this: <strong>\A</strong> which is the “for all” operator. In general, an expression of the form <strong>\A x \in S : F</strong> can be read as “formula <strong>F</strong> is true for all elements <strong>x</strong> in the set <strong>S</strong>.” For example, <strong>\A i \in {1, 2}: i ≤ 2</strong> is the same as writing <strong>(1 ≤ 2) /\ (2 ≤ 2)</strong>.</li><li>Because we want to compare each element with every other element, we have to “iterate” over the sequence once for each element in the sequence (i.e. this is an <strong>O(N²) </strong>operation for those more comfortable with Big O notation).</li><li>We have a couple of new operators here. First, we have <strong>/=</strong> which is the <strong>not-equals</strong> operator i.e. opposite of <strong>=</strong>. Secondly we have <strong>IF … THEN … ELSE …</strong> which should be self-explanatory as it operates just like it’s counterparts in any other programming language. <br> <br>Thus, we can read the whole expression as “for all elements <strong>i</strong> and <strong>j</strong> in the set of numbers from <strong>1</strong> (inclusive) to <strong>Len(seq)</strong> (inclusive), where <strong>i</strong> is not equal to <strong>j</strong>, the element at index <strong>i</strong> of sequence <strong>seq</strong> is not equal to the element at index <strong>j</strong> of sequence <strong>seq</strong>.”</li><li>We can then use our <strong>NoDuplicatesIn</strong> helper operator to write the definition of our <strong>NoDuplicates</strong> property which asserts that there should be no duplicates in our <strong>OutputTopic</strong> sequence.</li></ol><p>We can check that this property holds by adding it to our config file:</p><pre><strong>INVARIANT NoDuplicates </strong> \* 1</pre><ol><li>We use the <strong>INVARIANT</strong> keyword to declare any properties that we want to check are true in <em>every</em> state of our system. These types of properties are known as <strong>safety</strong> properties. In contrast, the <strong>PROPERTIES</strong> keyword is used to declare any properties that we want to check are true <em>eventually</em>. These are known as <strong>liveness</strong> properties. <br> <br>The question of whether to write our duplicates check as a safety property versus a liveness property is a design decision. Are we writing a system that never contains duplicates ever or a system that eventually doesn’t contain any duplicates? For our purposes, let’s assume we’re designing a system that never contains any duplicates ever. Hence our decision to use the <strong>INVARIANT</strong> keyword rather than <strong>PROPERTIES.</strong></li></ol><p>If we run <em>TLC</em> with this updated configuration, you should see <em>TLC</em> passes the spec without issues i.e. our system design is robust against duplicates.</p><h3>Checking for Missing Data</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/858/1*tvMJCdMoOyLMd2qs9HYHhA.png" /></figure><p>We’ve covered the first half of exactly-once by checking for a lack of duplicates. The other half of exactly-once is making sure no data is missing (otherwise our system would be considered <strong>at-most-once</strong>). In our context, this means checking that each element in <strong>InputTopic</strong> is present in our <strong>OutputTopic</strong>. We can express this property in <em>TLA</em>+ as follows:</p><pre><strong>SeqContains(seq, value) ==                                      </strong>\* 1<strong><br>    \E x \in 1..Len(seq): <br>        seq[x] = value                                          </strong>\* 2<strong><br><br>SeqContainsAll(seq, values) ==<br>    \A i \in 1..Len(values):<br>        SeqContains(seq, values[i])                             </strong>\* 3<strong><br><br>NoMissingData == &lt;&gt;[](SeqContainsAll(OutputTopic, InputTopic))  </strong>\* 4</pre><ol><li>Here we’re starting the process of defining a new “helper” operator <strong>SeqContains</strong>. As the name implies, the idea here is that we can use this operator to check if a given sequence contains a given value.</li><li>In order to “check” that at least one element of a sequence satisfies a condition, we need to use a new operator; <strong>\E</strong> formally referred to as <strong>existential quantification</strong> and generally read as “there exists.” In general, an expression of the form <strong>\E x \in S : F</strong> can be read as “there exists an element <strong>x</strong> in set <strong>S</strong> for which formula <strong>F</strong> is true.” <br> <br>Thus, we can read our expression <strong>\E x \in 1..Len(seq): seq[x] = value</strong> as “there exists an element <strong>x</strong> in the set of numbers from <strong>1</strong> (inclusive) to <strong>Len(seq)</strong> (inclusive) where the element at index <strong>x</strong> of sequence <strong>seq</strong> is equal to <strong>value</strong>.” More informally, this expression is true as along as one of the elements in the given sequence is equal to the given value.</li><li>Using our <strong>SeqContains</strong> operator, we can define another helper operator <strong>SeqContainsAll </strong>that asserts that all elements of <strong>values</strong> are present in <strong>seq</strong> using the “for all” operator <strong>\A</strong>.</li><li>Last but not least, we can define our property <strong>NoMissingData </strong>as <strong>&lt;&gt;[](SeqContainsAll(OutputTopic, InputTopic))</strong> or in other words “eventually our output topic will contain all elements of input topic always.”</li></ol><p>We can declare this property in our config file like so:</p><pre><strong>PROPERTY NoMissingData</strong>  \* 1</pre><ol><li>Notice that we have declared this a <strong>Property</strong> rather than an <strong>Invariant</strong> because <strong>NoMissingData</strong> is only guaranteed to be true eventually. It is not guaranteed to be true in every state e.g. it definitely doesn’t hold in our initial state when the output topic is empty! However, if our system behaves correctly, the output topic should eventually contain all the elements of our input topic.</li></ol><p>If we run <em>TLC</em> with this updated configuration, you should see <em>TLC</em> passes the spec without issues i.e. our system design is robust to missing data issues.</p><h3>Refactoring</h3><p>Before we conclude this post, let’s take a brief moment to “clean” up some parts of our spec.</p><h4>Model Values</h4><p>Our solution for assigning a value to <strong>NULL</strong> was to make it equal to 0, a value that our messages/offsets can never be equal to in our <em>TLA</em>+ spec. This is a rather brittle solution. If we were to reuse our definition of <strong>NULL</strong> in a different numerical context, there is no guarantee that 0 will be an appropriate value to represent missing data. Indeed, 0 might even be a legitimate value in that context!</p><p>To avoid this issue, it’s common for <strong>NULL</strong> to be defined using another data type that better fits the use case; <strong>model values</strong>. Model values are a special type of value that you cannot do anything with other than to check for equality (<strong>=</strong>) with another value. Furthermore, a model value is only ever equal to itself. Despite these restrictions, model values can still be quite useful and it’s common to use them for modelling the concept of null.</p><p>In <em>TLC</em>, we can assign a model value like so:</p><pre><strong>CONSTANT NULL = NULL</strong>  \* 1</pre><ol><li>Here we’re declaring that the <strong>CONSTANT NULL</strong> in our spec is equal to a unique model value<strong> </strong><strong>NULL</strong>. Note that we could name the model value anything really e.g. <strong>CONSTANT NULL = abc</strong>.</li></ol><p>If you try running our spec through <em>TLC</em> after this change, it should continue to pass without issues.</p><blockquote>It’s worth noting that model values are a construct available exclusively in TLC. TLA<em>+</em> itself has no concept of model values. The only way to “define” a model value is to declare a <strong>CONSTANT</strong> parameter in your TLA+ spec and then assign a model value to that parameter in your TLC config, as we did above.</blockquote><h4>For-All and Implication Operators</h4><p>Our definition of <strong>NoDuplicatesIn</strong> currently looks like this:</p><pre><strong>NoDuplicatesIn(seq) ==                               <br>    \A i \in 1..Len(seq):                            <br>        \A j \in 1..Len(seq):                        <br>            IF i /= j THEN seq[i] /= seq[j] ELSE TRUE</strong></pre><p>We can simplify our definition of <strong>NoDuplicatesIn</strong> in two ways:</p><pre><strong>NoDuplicatesIn(seq) ==</strong><br><strong>    \A i, j \in 1..Len(seq):</strong>        /* 1<br><strong>        i /= j =&gt; seq[i] /= seq[j]</strong>  /* 2</pre><ol><li>First, we can switch to using a slightly specialized form of the “for all” operator which allows us to assert that formula <strong>F</strong> is true for all possible pairs of elements in the set <strong>S</strong> using the <strong>\A i, j \in S: F</strong> syntax. <br> <br>For example, <strong>\A i, j \in {1, 2}: i + j ≤ 4</strong> is the same as saying <strong>(1 + 1 ≤ 4) /\ (1 + 2 ≤ 4) /\ (2 + 1) ≤ 4 /\ (2 + 2 ≤ 4)</strong>.</li><li>The second simplification we can make to our definition of <strong>NoDuplicatesIn</strong> is to use the <strong>implication</strong> operator <strong>=&gt;</strong> to replace <strong>IF i /= j THEN seq[i] /= seq[j] ELSE TRUE</strong> with the shorter but otherwise completely equivalent <strong>i /= j =&gt; seq[i] /= seq[j] </strong>expression. In general, we read an expression of the form <strong>F =&gt; G</strong> as “<strong>F</strong> implies <strong>G</strong>.” <strong>F =&gt; G</strong> is true if either:<br>- <strong>F</strong> is true and <strong>G</strong> is true or <br>- <strong>F</strong> is false</li></ol><p>If you try running our spec through <em>TLC</em> after these changes, it should continue to pass without issues.</p><h4>Final Spec</h4><p>After our refactor (plus a little rearrangement to organize everything a little more sanely) we end up with the following <em>TLA+</em> spec:</p><pre><strong>---- MODULE ExactlyOnce ----<br><br>EXTENDS Sequences, Integers<br><br>CONSTANT NULL<br><br>VARIABLES InputTopic, Buffer, OutputTopic, CommittedConsumerOffset<br><br>vars == &lt;&lt;InputTopic, Buffer, OutputTopic, CommittedConsumerOffset&gt;&gt;<br><br>Init ==<br>    /\ InputTopic = &lt;&lt;1&gt;&gt;<br>    /\ Buffer = NULL<br>    /\ OutputTopic = &lt;&lt;&gt;&gt;<br>    /\ CommittedConsumerOffset = 1<br><br>MessagesAvailable == CommittedConsumerOffset &lt; Len(InputTopic) + 1<br><br>ConsumeProduceCommit ==<br>    /\ MessagesAvailable<br>    /\ Buffer&#39; = InputTopic[CommittedConsumerOffset]<br>    /\ OutputTopic&#39; = Append(OutputTopic, Buffer&#39;)<br>    /\ CommittedConsumerOffset&#39; = Buffer&#39; + 1<br>    /\ UNCHANGED InputTopic<br><br>Done ==<br>    /\ ~MessagesAvailable<br>    /\ UNCHANGED vars<br><br>Next ==<br>    \/ ConsumeProduceCommit<br>    \/ Done<br><br>Fairness == WF_vars(Next)<br><br>Spec ==<br>    /\ Init<br>    /\ [][Next]_vars<br>    /\ Fairness<br><br>Termination == &lt;&gt;[](~MessagesAvailable)<br><br>NoDuplicatesIn(seq) ==<br>    \A i, j \in 1..Len(seq):<br>        i /= j =&gt; seq[i] /= seq[j]<br><br>NoDuplicates == NoDuplicatesIn(OutputTopic)<br><br>SeqContains(seq, value) ==<br>    \E x \in 1..Len(seq):<br>        seq[x] = value<br><br>SeqContainsAll(seq, values) ==<br>    \A i \in 1..Len(values):<br>        SeqContains(seq, values[i])<br><br>NoMissingData == &lt;&gt;[](SeqContainsAll(OutputTopic, InputTopic))<br><br>====</strong></pre><p>And the following <em>TLC</em> config file:</p><pre><strong>SPECIFICATION Spec<br>CONSTANT NULL = NULL<br>INVARIANT NoDuplicates<br>PROPERTY Termination NoMissingData</strong></pre><p>Running this through <em>TLC</em>, our spec should come back all clear.</p><h3>Reflections</h3><p>We wrote an initial spec. We added some checks. We found bugs in our spec. We corrected our spec. More checks. More bugs. More corrections. And so on in a feedback loop not unlike your regular programming experience with unit testing, except here we’re getting feedback on our designs.</p><p>Moreover, in less than 50 lines we’ve expressed a model of our system and checked that it is exactly-once. But is it really this easy to write an exactly-once replicator? Are we sure our model is an accurate representation of reality? Cue:</p><blockquote>All models are wrong, but some models are useful.</blockquote><p>In <a href="https://medium.com/@fqaiser94/modelling-exactly-once-using-tla-9512e1eb8ca5">Part 3 Modelling Failures and Transactions</a>, we’ll take a critical look at our specification and question some of the (unrealistic) assumptions we’ve accidentally embedded in our design.</p><p>In the meantime, if you want to learn more on your own, try the following exercises:</p><ol><li>Currently our <em>TLA</em>+ spec just declares a constant <strong>NULL</strong> without any further constraints or information. It says nothing about what are valid values for <strong>NULL</strong>. How can you prevent users from assigning incorrect values for <strong>NULL</strong>? <a href="https://learntla.com/core/constants.html#preventing-nonsense-constants">Hint</a></li><li>How would you change the spec if we decided that our system needs to be a streaming/always-on system rather than a system that terminates once all messages have been processed? What needs to change, if anything?</li><li>Take a look at the spec. How many states does our system have? Do they reflect all the possible, relevant states and state transitions for our system?</li><li>What happens as you (slowly!) increase the number of messages in the input topic? How long does <em>TLC</em> take to verify the spec as the number of messages increase?</li><li>Imagine if our spec permitted multiple messages in the input topic. In that case, what other properties might you want to check? How would you write a property that asserts that messages are produced to the output topic in the same order as the input topic?</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f3eb15303b27" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Modelling Exactly-Once Delivery Using TLA+]]></title>
            <link>https://medium.com/@fqaiser94/exactly-once-modelling-using-tla-3c792655be44?source=rss-ac4d9cb6496a------2</link>
            <guid isPermaLink="false">https://medium.com/p/3c792655be44</guid>
            <category><![CDATA[exactly-once-processing]]></category>
            <category><![CDATA[formal-verification]]></category>
            <category><![CDATA[tla-plus]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[advanced-programming]]></category>
            <dc:creator><![CDATA[Farooq Qaiser]]></dc:creator>
            <pubDate>Wed, 31 Jul 2024 20:11:06 GMT</pubDate>
            <atom:updated>2025-08-18T01:32:50.400Z</atom:updated>
            <content:encoded><![CDATA[<h3>Modelling Exactly-Once Delivery Using TLA+ Part 1: Writing a Specification</h3><p><em>TLA+</em> is a language for writing system specifications and discovering fundamental design errors quickly. In this series of blogposts, we’ll introduce <em>TLA+</em> by iteratively modelling and refining our design for a simple application that can read and write messages from/to Kafka in an exactly-once fashion. This will be a four-part series consisting of:</p><ol><li><a href="https://medium.com/@fqaiser94/exactly-once-modelling-using-tla-3c792655be44"><strong>Writing a Specification</strong></a></li><li><a href="https://medium.com/@fqaiser94/modelling-exactly-once-using-tla-f3eb15303b27">Checking a Specification</a></li><li><a href="https://medium.com/@fqaiser94/modelling-exactly-once-using-tla-9512e1eb8ca5">Modelling Failures and Transactions</a></li><li><a href="https://medium.com/@fqaiser94/modelling-exactly-once-using-tla-2d7035e1379e">Modelling Zombies and Fencing</a></li></ol><p>You can find all of the code for this series in this <a href="https://github.com/fqaiser94/tla-exactly-once">GitHub repo</a>.</p><p><em>Also, if you have interesting systems engineering problems and are looking for a strong Software Engineer, feel free to reach out via </em><a href="https://www.linkedin.com/in/fqaiser94/"><em>LinkedIn</em></a><em>.</em></p><h3>Introduction</h3><p>Before we can start writing <em>TLA+</em>, we need to first understand the system we’re trying to model. For the purposes of this series, we’ll be modelling a simple process that continuously executes the following steps in a loop:</p><ol><li>Consume the next available message from an input topic based on the last committed consumer offset</li><li>Produce the consumed message to an output topic</li><li>Commit the consumer offset for the next message to be consumed in case of failure</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*iDWvnpSfSiSh3f7FV5o2Ag.png" /><figcaption>Figure 1: Consume-produce-commit loop</figcaption></figure><p>Essentially, our system is just replicating messages from one topic to another. Where things get interesting is we want to make sure we replicate each message from our input topic to our output topic exactly once. If you’ve ever written a similar application using the Java <strong>KafkaConsumer</strong> and <strong>KafkaProducer</strong> APIs, you’ll know it’s easy to produce duplicates. Even worse, if you’re really not being careful, you could accidentally lose data!</p><p>We’ll talk more about exactly-once in parts 3 and 4. To avoid disappointment though, advanced readers should note that we will <em>not</em> be modelling some consensus algorithm like <em>Paxos</em> or <em>Raft</em> in this series. We’ll still encounter the same problems but our solution/algorithm for exactly-once will be fairly high level. This should still be an interesting exercise whilst remaining a beginner friendly introduction to <em>TLA+</em> for most readers.</p><p>For part 1 however, we’re going to simply focus on getting familiar with <em>TLA</em>+ syntax by writing a simple specification of our system as we’ve described it.</p><h3>TLA+ Specifications</h3><p><em>TLA+</em> is primarily a language for writing system specifications i.e. a description of all the allowed <strong>behaviours</strong> a system may take during the course of an execution. Behaviours are represented as an infinite sequence of discrete <strong>steps</strong>, where a step is a transition from one <strong>state</strong> to the next.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xrdqLjNy0CWoMTZsrpQ26w.png" /><figcaption>Figure 2: Two different behaviours of the same system</figcaption></figure><p>And a state is simply the assignment of values to variables at a specific point in execution.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/658/1*Ky2aDhYRoWkKDq7Vjl0fkg.png" /><figcaption>Figure 3: A behaviour describing how variable `a` changes between states</figcaption></figure><p>As a result, the first step in writing a <em>TLA+</em> spec typically is to figure out what are the relevant <strong>variables</strong> in the system.</p><h3>Variables</h3><p>If we look carefully at Figure 1, we can see the only things that are changing in our system are the:</p><ol><li>Input topic</li><li>Message buffer</li><li>Output topic</li><li>Committed consumer offset</li></ol><p>These are the variables in our system. Based on this, we can start writing our first few lines of <em>TLA</em>+.</p><p>The first thing we need to do is create a new file <strong>ExactlyOnce.tla</strong>. Inside this file, we can declare a new <em>TLA</em>+ <strong>module </strong>like so:</p><pre><strong>---- MODULE ExactlyOnce ----  </strong>\* 1<br><br><strong>====</strong>                          \* 2</pre><ol><li><em>TLA+</em> modules are always begun with a <strong>MODULE ${filename}</strong> declaration surrounded by 4 (or more) dashes on either side. You can think of it as kind of like a header signalling the start of a document.<br> <br>We also have the <strong>\* XXX</strong> syntax at the end of the line which is used to write in-line comments in <em>TLA</em>+. We’ll be using it throughout the series to indicate which line of “code” each bullet point is addressing.</li><li>Similarly, <em>TLA</em>+ modules are always ended with 4 (or more) equals signs. You can think of this as kind of like a footer signalling the end of a document.</li></ol><p>In between these two lines, we can write the actual specification of our system. We’ll start by declaring the variables we just discovered:</p><pre><strong>VARIABLES InputTopic, Buffer, OutputTopic, CommittedConsumerOffset  </strong>\* 1</pre><ol><li>We use the <strong>VARIABLES</strong> keyword to declare any variables in our system as a comma separated list.</li></ol><p>Using these variables, we should be able to describe any behaviour of our system in terms of how it changes (or doesn’t change!) these variables. Our next step is to specify the initial state of our system using these variables.</p><h3>Initial State Predicate</h3><p>We can model the initial state of our system as though our application has not yet been launched. In this state, our output topic will be empty and the message buffer will be missing. Technically speaking, the committed consumer offset would also be missing if the application hadn’t launched yet but for simplicity, we’ll have it point to the offset of the first message in the input topic. For similar reasons, we’ll assume our input topic will only ever contain one message. Lastly, we’ll assume both our topics are singly partitioned and thus avoid the need to model the concept of partitions entirely.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*BwRFiMRy_kJ1jIK0doVVZQ.png" /><figcaption>Figure 4: Initial state</figcaption></figure><p>These kinds of simplifications and assumptions are a normal part of the process of building models. A model is an <strong>abstraction</strong> of reality; we can include as much or as little detail as we want depending on how we intend to use the model. In our case, our ultimate goal is to model exactly-once behaviour. If we can’t achieve exactly-once in the simplest of cases (replicating a single partition containing only one message), then it’s hardly likely we’ll be able to figure it out for more complex cases. Like most things in life, it’s best to start simple and gradually build up from there.</p><p><em>TLA+</em> is based on the idea that the best way to describe things precisely is with math. Let’s see what the initial state of our system looks like in math:</p><pre><strong>CONSTANT NULL                       </strong>\* 1<strong><br><br>Init ==                             </strong>\* 2<strong><br>    /\ InputTopic = &lt;&lt;1&gt;&gt;           </strong>\* 3<strong><br>    /\ Buffer = NULL                </strong>\* 4<strong><br>    /\ OutputTopic = &lt;&lt;&gt;&gt;           </strong>\* 5<strong><br>    /\ CommittedConsumerOffset = 1  </strong>\* 6</pre><ol><li><em>TLA+</em> doesn’t have any built-in concept of null so our first order of business is to declare a constant <strong>NULL</strong>. We’ll be using this shortly to represent missing data in our spec.</li><li>In <em>TLA+, </em>we use <strong>==</strong> to <strong>define</strong> things. Here we’re using it to define a new <strong>operator</strong> named <strong>Init</strong> which will describe the initial state of our system.</li><li>There are a bunch of symbols here so let’s try to understand what they each mean individually before putting them together. <br> <br>First we have the <strong>conjunction</strong> operator <strong>/\</strong>. This is used to combine boolean expressions <strong>AND</strong><em> </em>wise. We’ll see later we can also combine boolean expressions <strong>OR</strong> wise using the <strong>disjunction</strong> operator: <strong>\/</strong>. (An easy way to remember which operator is which is by pretending <strong>/\</strong> looks like the capital letter A, as in A for AND). We’ll be writing our definition of <strong>Init</strong> as a <strong>conjunction</strong> of 4 distinct expressions. <br> <br>Next, we have the angular brackets used for representing <strong>sequences</strong>: <br>- <strong>&lt;&lt;&gt;&gt;</strong> represents an empty sequence. <br>- <strong>&lt;&lt;1&gt;&gt;</strong> represents a sequence of one element; <strong>1</strong>.<br>- <strong>&lt;&lt;1, &quot;a&quot;&gt;&gt;</strong> represents a sequence of two elements; <strong>1</strong> and <strong>&quot;a&quot;</strong>. <br>- And so on. <br> <br>For now, it’s sufficient to think of sequences as similar to ordered collections in regular programming languages e.g. the Tuple data type in Python. (In reality, <em>TLA</em>+ doesn’t really have a concept of sequences, they are under the hood just <strong>functions </strong>but don’t worry about that for this series). This makes sequences a natural fit for modelling Kafka topics, where each element of the sequence is a Kafka message. <br> <br>Last but not least, we have <strong>=</strong> which is the standard math equality operator you remember from primary school e.g. <strong>1 = 1</strong>.<br> <br>Putting all of this together, you should now be able to read the first expression in our conjunction. Just like how in regular math we would read <strong>x + y = 1</strong> as “x plus y equals 1,” we can similarly read <strong>InputTopic = &lt;&lt;1&gt;&gt;</strong> as “<strong>InputTopic</strong> is equal to a sequence containing <strong>1</strong>” in the initial state.<br> <br>What’s the significance of the number <strong>1</strong> in our expression? We’ve chosen to represent our messages simply by their offset position in the input topic. So <strong>1</strong> represents the first (and only) message in the input topic. We <em>could</em> have modelled our messages as a struct type however for our purposes this will be more than sufficient and in fact it will make it easy for us to detect duplicates later (as Kafka offsets are unique within a topic-partition). This is another case of us simply choosing the level of detail we want to include in our model.<br> <br>Eagle-eyed readers might be surprised to see that the offset of the first message is 1 when, in reality, Kafka offsets start from 0. The problem here is that <em>TLA+</em> sequences happen to be <strong>1-indexed </strong>(<em>R</em> developers rejoice!). Whilst there are ways we could model this in <em>TLA+</em> more accurately, for the purposes of our specification it does not matter whether our offsets start at 0 or 1, so we won’t waste our time trying to fix this unimportant detail.</li><li>The next expression in our conjunction is <strong>Buffer = NULL</strong> which can be read as the <strong>Buffer</strong> is equal to <strong>NULL</strong> (in the initial state).</li><li>The next expression <strong>OutputTopic = &lt;&lt;&gt;&gt;</strong> can be read as the <strong>OutputTopic</strong> is equal to an empty sequence (in the initial state).</li><li>The final expression <strong>CommittedConsumerOffset = 1</strong> in our conjunction of expressions states that the committed consumer offset is equal to 1 (in the initial state) to indicate that our process should start reading messages from the beginning of the topic.</li></ol><p>What we’ve just written here is an example of an <strong>initial state predicate</strong> i.e. a boolean valued formula<em> </em>that specifies all the possible initial values of the variables in our system. You should be able to see clearly how each of the various <em>TLA</em>+ expressions we just defined map to our earlier description of the initial state. Even though we say <em>TLA+</em> is based on math, it’s mostly simple boolean logic and set theory.</p><p>However, a system wouldn’t be of much use if all it did was remain in one state. Most systems will have multiple states that they will transition between. Our next step will be to specify these next potential states in our <em>TLA+ </em>spec, again using “math.”</p><h3>Next-State Action</h3><p>In <em>TLA+</em>, we will typically write a <strong>next-state action</strong> to specify the potential next steps a system can take. Just like we can define <strong>state predicates</strong> as boolean valued operators, we can also define <strong>actions</strong> as boolean valued operators in <em>TLA</em>+. The only difference is that while <strong>state predicates</strong> describe <strong>states</strong>, <strong>actions </strong>describe <strong>steps</strong>. (You can also just think of actions as a predicate over a pair of states given that a step is just a transition from one state to the next). In our case, a first attempt at writing such a next-state action operator might look something like this:</p><pre><strong>EXTENDS Sequences, Integers</strong>                                         \* 1<br><br><strong>MessagesAvailable == CommittedConsumerOffset &lt; Len(InputTopic) + 1</strong>  \* 2<br> <br><strong>ConsumeProduceCommit ==</strong>                                             \* 3<br><strong>    /\ MessagesAvailable</strong>                                            \* 4<br><strong>    /\ Buffer&#39; = InputTopic[CommittedConsumerOffset]</strong>                \* 5<br><strong>    /\ OutputTopic&#39; = Append(OutputTopic, Buffer&#39;)</strong>                  \* 6<br><strong>    /\ CommittedConsumerOffset&#39; = Buffer&#39; + 1</strong>                       \* 7<br><strong>    /\ UNCHANGED InputTopic</strong>                                         \* 8<br> <br><strong>Next == ConsumeProduceCommit</strong>                                        \* 9</pre><ol><li>The statement <strong>EXTENDS Sequences, Integers</strong> extends the<br>scope of operators like <strong>Append</strong> defined in the <strong>Sequences</strong> module to our <strong>ExactlyOnce</strong> module. You can think of this as similar to import statements in Python.</li><li>We’ve defined <strong>MessagesAvailable</strong> as an expression which is true if our committed consumer offset is less than one plus the number of messages in our input topic i.e. if there are still messages in our input topic that our process hasn’t yet replicated successfully. We’ll be using this definition in a couple of places in our spec.</li><li>Similarly to how we defined <strong>Init</strong>, our <strong>ConsumeProduceCommit</strong> operator is also defined as a conjunction of several expressions.</li><li>The first conjoined expression in our conjunction <strong>MessagesAvailable</strong> specifies that our system can only take this step if there are messages available to be consumed.</li><li>There are a few new symbols here so let’s try to understand those first, starting with <strong>Buffer&#39;</strong>. <br> <br>Recall that a <strong>step</strong> in <em>TLA+</em> refers to a pair of consecutive states. Therefore, in order to define a step, we need to be able to refer the values of a variable in both states. We can do this by making use of <strong>unprimed</strong> and <strong>primed</strong> variables. <strong>Buffer</strong> is an example of an <strong>unprimed</strong> variable and it refers to the value of the <strong>Buffer</strong> variable in the <em>first</em> state of a step. In contrast, <strong>Buffer&#39;</strong> (read as “<strong>Buffer</strong> prime”) refers to the value of the <strong>Buffer</strong> variable in the <em>second</em> state of a step. Thus when we see an expression like <strong>Buffer&#39; = 1</strong> , we can read this as “the value of <strong>Buffer</strong> in the next state is equal to 1.” In this way, we are able to define steps. <br> <br>The last new piece of syntax here is: <strong>InputTopic[CommittedConsumerOffset]</strong>. Square brackets allow us to “index” a <em>TLA+</em> sequence in a similar way to how we can use square brackets in Python to index a Tuple. So for example, if we have a sequence <strong>Seq == &lt;&lt;&quot;a&quot;, &quot;b&quot;&gt;&gt;</strong>, then <strong>Seq[1] = &quot;a&quot;</strong> and <strong>Seq[2] = &quot;b&quot;</strong>. <br> <br>Thus we can read <strong>Buffer&#39; = InputTopic[CommittedConsumerOffset]</strong> as “the value of <strong>Buffer</strong> in the next state is equal to the value at the <strong>CommittedConsumerOffset</strong> index in the <strong>InputTopic</strong> sequence.” Essentially, this expression is simulating the process of consuming a message from our input topic and storing the message in a local buffer.</li><li><strong>OutputTopic&#39; = Append(OutputTopic, Buffer&#39;)</strong> can be read as “the value of <strong>OutputTopic</strong> in the next state is equal to the <strong>OutputTopic</strong> in the first state with the message stored in the buffer appended to it.” Essentially, this expression is simulating the process of producing the message stored in our local buffer to the output topic.</li><li><strong>CommittedConsumerOffset&#39; = Buffer&#39; + 1</strong> can be read as “the value of <strong>CommittedConsumerOffset</strong> in the next state is equal to the offset of the message in the buffer plus one.” Essentially, this expression is simulating the process of committing our new consumer offset.</li><li><em>TLA</em>+ is all about defining your system explicitly. Almost nothing about a system’s behaviours is left unspecified or implicit in a <em>TLA+</em> spec. As a result, we also have to declare any variables that are left unchanged in a step. This is usually done by using the <strong>UNCHANGED</strong> keyword followed by the relevant variable/s. <br> <br>We could also have chosen to explicitly write out the unchanged variables e.g. <strong>InputTopic&#39; = InputTopic</strong> which should read intuitively as “the value of <strong>InputTopic</strong> in the second state of this step is equal to the value of <strong>InputTopic</strong> in the first state of this step.” In general though, you’ll see most people prefer to use the <strong>UNCHANGED</strong> keyword.</li><li>Finally, we define a <strong>Next</strong> operator as simply equivalent to the <strong>ConsumeProduceCommit</strong> operator we just defined. This is by no means necessary but the general convention in <em>TLA+</em> is to name the next-state action formula <strong>Next</strong>. Of course, we could have also just renamed our <strong>ConsumeProduceCommit</strong> operator to <strong>Next</strong> but as we’ll see later on in the series, our definition of <strong>Next</strong> is far from complete.</li></ol><p>Hopefully you can see how we’ve translated the consume-produce-commit loop we illustrated earlier in Figure 1 into precise <em>TLA</em>+ expressions.</p><p>At this point, we have formulas defining both the initial state predicate and next-state action. Obviously a system has to transition from an initial state to the next state but how do we express this formally in <em>TLA+</em>?</p><h3>Spec</h3><p>In <em>TLA+</em>, we will typically define a <strong>Spec</strong> operator to bring together our initial predicate and next-state action formulas as a <strong>temporal formula</strong> that describes all the behaviours a system can exhibit. Let’s see what that looks like for our system:</p><pre><strong>vars == &lt;&lt;InputTopic, Buffer, OutputTopic, CommittedConsumerOffset&gt;&gt;  </strong>\* 1<strong><br><br>Spec ==                                                               </strong>\* 2<strong><br>    /\ Init                                                           </strong>\* 3 <strong><br>    /\ [][Next]_vars                                                  </strong>\* 4</pre><ol><li>First, we’ve defined an operator <strong>vars</strong> that, in each state, is equal to a sequence of the values of all our variables. We’ll be using this definition of <strong>vars</strong> shortly.</li><li>Next we’re defining a <strong>Spec</strong> operator as the conjunction of two separate expressions.</li><li>The first expression simply states that a valid behaviour is one that starts in conditions matching our initial state predicate exactly.</li><li>The second expression in our conjunction involves our next-state action formula and once again we have a bunch of new symbols that deserve some explanation. <br> <br>Let’s start with the square brackets at the beginning of the expression: <strong>[]</strong>. This <strong>temporal-logic</strong> operator is formally referred to as the <strong>box</strong> operator and is generally used to express that a formula is <strong>always</strong> true . For example, <strong>[]F</strong> asserts that the formula F is <strong>always</strong> true. In our case, <strong>[][Next]_vars</strong> asserts that <strong>[Next]_vars</strong> is true for every step of every behaviour. <br> <br>Naturally then the next thing we need to understand is what <strong>[Next]_vars </strong>means. <strong>[Next]_vars</strong> is actually short-hand/syntax-sugar for expressing <strong>Next \/ (vars&#39; = vars)</strong>. If we look at this expanded notation, what this is saying is either the system has to take one of the steps defined by <strong>Next</strong> <strong>OR</strong> it can take what is known as a <strong>stuttering step</strong> where no variables change. You’re probably wondering at this point, why would we want to write a system that can take steps in which nothing changes i.e. a system that can occasionally do nothing? <br> <br>The reason we have to specify our system like this is because <em>TLA</em>+ only allows temporal formulas that are <strong>invariant under stuttering </strong>i.e. temporal formulas must allow for stuttering steps to occur. This might seem strange at first glance but the underlying philosophy here is that <em>TLA</em>+ specifications describe more than just our system but rather an entire universe, of which the system we’re describing is just one part. In that universe, many events can take place besides those corresponding to your system and during those steps, your system’s variables will not change. Hence any sensible specification needs to allow stuttering steps. For a more in-depth explanation, you can read this <a href="https://lamport.azurewebsites.net/tla/stuttering.html">article</a> by <a href="https://en.wikipedia.org/wiki/Leslie_Lamport">Leslie Lamport</a> the original author of <em>TLA+</em>.<br> <br>For these reasons, <em>TLA</em>+ syntax rules make it illegal to write a temporal formula as simply <strong>[]A</strong> where <strong>A</strong> is an arbitrary action that does not allow stuttering. When using the <strong>[]</strong> temporal operator, <strong>A</strong> must allow stuttering steps and thus we usually write <strong>[][A]_v</strong> where the sub-expression <strong>[A]_v </strong>represents an <strong>A</strong> step <strong>or</strong> a stuttering step (and <strong>v</strong> represents all the variables that can change in your system).</li></ol><p>Syntax-intricacies aside, we say <strong>Spec</strong> is defined as <strong>the conjunction of the initial state and the next state, for all values of </strong><strong>vars</strong>. This formula asserts that a valid behaviour of a system is one that satisfies its initial state <strong>Init</strong>, and each of its steps satisfies <strong>Next</strong> or are stuttering steps. Thus, we’ve now formally defined all the behaviours our system can exhibit as a single formula, <strong>Spec</strong>.</p><h3>Reflections</h3><p>With a little rearrangement, we end up with the following spec:</p><pre><strong>---- MODULE ExactlyOnce ----<br><br>EXTENDS Sequences, Integers<br><br>CONSTANT NULL<br><br>VARIABLES InputTopic, Buffer, OutputTopic, CommittedConsumerOffset<br><br>vars == &lt;&lt;InputTopic, Buffer, OutputTopic, CommittedConsumerOffset&gt;&gt;<br><br>Init ==<br>    /\ InputTopic = &lt;&lt;1&gt;&gt;<br>    /\ Buffer = NULL<br>    /\ OutputTopic = &lt;&lt;&gt;&gt;<br>    /\ CommittedConsumerOffset = 1<br><br>MessagesAvailable == CommittedConsumerOffset &lt; Len(InputTopic) + 1<br><br>ConsumeProduceCommit ==<br>    /\ MessagesAvailable<br>    /\ Buffer&#39; = InputTopic[CommittedConsumerOffset]<br>    /\ OutputTopic&#39; = Append(OutputTopic, Buffer&#39;)<br>    /\ CommittedConsumerOffset&#39; = Buffer&#39; + 1<br>    /\ UNCHANGED InputTopic<br><br>Next == ConsumeProduceCommit<br><br>Spec ==<br>    /\ Init<br>    /\ [][Next]_vars<br><br>====</strong></pre><p>Notice how we call this a spec, as opposed to a program or code. Although we drew some parallels with programming, it’s important to remember that <em>TLA+</em> is <em>not</em> a programming language. There’s no code or program here that can be run. All we’ve done is write down a formal description of our system.</p><p>While it’s nice that we can describe systems in a more precise and concise language than plain English, how do we know what we’ve written is correct? Just because we’re writing something in “math” doesn’t magically make it correct e.g. writing 1 + 1 = 3 doesn’t make it a true statement. So how do we know our spec is correct? And what does it mean for a spec to be correct? To find out the answers to these questions and more, see <a href="https://medium.com/@fqaiser94/modelling-exactly-once-using-tla-f3eb15303b27"><strong>Part 2 - Checking a Specification</strong></a>.</p><p>In the meantime, if you want to learn more on your own, try:</p><ol><li>Extending the spec so that our system can read multiple messages at a time.</li><li>Thinking about what our system should do once it’s consumed all the messages in the input topic. What does our spec say about this, if anything?</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3c792655be44" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Concurrent Sudoku Solver: Part 4 - Using FS2 Stream + Topic]]></title>
            <link>https://medium.com/@fqaiser94/concurrent-sudoku-solver-part-4-using-fs2-stream-topic-949c8b099abb?source=rss-ac4d9cb6496a------2</link>
            <guid isPermaLink="false">https://medium.com/p/949c8b099abb</guid>
            <category><![CDATA[fs2]]></category>
            <category><![CDATA[cats-effect]]></category>
            <category><![CDATA[scala]]></category>
            <category><![CDATA[streaming]]></category>
            <dc:creator><![CDATA[Farooq Qaiser]]></dc:creator>
            <pubDate>Fri, 24 Jun 2022 02:29:15 GMT</pubDate>
            <atom:updated>2022-06-25T02:13:42.172Z</atom:updated>
            <content:encoded><![CDATA[<h3>Introduction</h3><p>In <a href="https://medium.com/@fqaiser94/concurrent-sudoku-solver-part-3-using-cats-effect-queue-459e2da28b6">Part 3</a>, we used Cats Effect Queue to implement a concurrent Sudoku solver. The way we used Queue in that post was a good indication that our problem could also be solved in a more streaming oriented fashion. In this post, we will write another concurrent Sudoku Solver implementation using the Stream and Topic abstractions from the FS2 library.</p><p>Before reading this blogpost, we strongly recommend you read at least <a href="https://medium.com/@fqaiser94/concurrent-sudoku-solver-part-1-single-candidate-technique-domain-modelling-6c885a1e4ef3">Part 1</a> of the series. Part 1 covers the theory behind the Single Candidate technique we’ll be applying, and also introduces the domain models we’ll be reusing here. Also, same as before, you can find all the code we’ll be writing today in the public <a href="https://github.com/fqaiser94/concurrent-sudoku-solver">concurrent-sudoku-solver</a> repo.</p><h3>High level architecture</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*e8X3TqXeh2JhRQLDu4rCOw.png" /></figure><p>In this architecture, we will represent the process of deducing the single candidate of a coordinate as a value of type Stream[IO, Candidate.Single]. We will need one such stream for each missing coordinate in a Sudoku board. Each of these streams will only ever emit a single Candidate.Single element (eventually) after which they will be terminated.</p><p>In addition, we will need a Stream[IO, Given] value which will emit the given values (i.e the initial clues in the Sudoku board) before terminating.</p><p>Using these streams, we will compose yet another stream Stream[IO, Value]that simply emits the values of all the preceding streams as they become available, and itself terminates only after all the preceding streams have terminated. We will ultimately want to collect the results of this stream as an IO[List[Value]] that we can return at the top-level of our program to satisfy the Solver interface we defined in Part 1.</p><p>We also need a way to communicate the Value of other cells to each Stream[IO, Candidate.Single] process. Each Stream[IO, Candidate.Single] process will need this information to deduce its own value using the single candidate technique. In <a href="https://medium.com/@fqaiser94/concurrent-sudoku-solver-part-3-using-cats-effect-queue-459e2da28b6">Part 3</a>, we gave each Cell its own Queue[IO, Value] from which it could consume updates about other cells. Instead of multiple Queue[IO, Value], here we will use a single Topic[IO, Value] to implement this functionality. Similar to a Queue, we can publish messages to a Topic. Where Topics differ from Queues is that once a consumer has read a message from a Queue, that message cannot be directly consumed again by a different consumer. A Topic on the other hand allows different consumers (more accurately, different <em>subscribers</em>) to consume the same message. This is how we’re able to replace multiple Queue instances with a single Topic instance in this architecture. More specifically, we will publish a message to the Topic each time we learn the Value of a coordinate. Each Stream[IO, Candidate.Single] process will individually subscribe to the Topic and then independently consume the messages from the Topic to reach a solution.</p><p>And of course, when we say independently, we also mean concurrently. That is to say, each of our Stream[IO, Candidate.Single] processes should run in a concurrent fashion (and ideally in parallel too if we have multiple cores available).</p><p>Hopefully that all made sense. Before you continue reading, go ahead and try implementing this yourself! It’s a little tricky so we’ll give you a hint: you’ll want to use Topic.subscribeAndAwait rather than Topic.subscribe. When you’re done, you can compare with our solution, as follows.</p><h3>Code</h3><p>We’ll start by writing a function to create Resource[IO, Stream[IO, Candidate.Single]] instances. Ignore the Resource part of the type for now, we’ll explain the need for that shortly. The goal of this function however is to essentially enable us to create a Stream[IO, Candidate.Single] instance for each missing coordinate. Recall that Stream[IO, Candidate.Single] in our architecture represents the process of deducing the single candidate for a missing coordinate.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xYhY49Pj9Nxm5zHhcEUqIw.png" /><figcaption>In terms of our architecture diagram, this is the part we’re focused on at the moment.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*JLZxGZKTgRaetLe_Mv_F2A.png" /></figure><ol><li>Our function will take a couple of inputs, the first being an updatesTopic: Topic[IO, Value] from which we can consume updates about the Value of other coordinates.</li><li>The second argument is the coord: Coord for which we are creating the Stream[IO, Candidate.Single] process. Those are all the arguments we need meaning we’re ready to move on to the body of our function.</li><li>The first thing we do is call the subscribeAndAwait method on our updatesTopic which returns to us a Resource[IO, Stream[IO, Value]]. This is where the Resource part of our function’s return type stems from. This Resource models the <em>effect</em> of acquiring and releasing a subscription. The acquisition part is of particular interest to us; acquisition of the Resource returns a Stream[IO, Value] after the underlying subscriber is subscribed to the topic but <em>before</em> it has started pulling any elements from the topic. In other words, the Resource gives us explicit control over when to start listening for messages on the topic. <br> <br>This is different from the subscribe method which just returns a Stream[IO, Value]. A “subscription” is opened only when we start pulling on the return stream. As a result, it&#39;s possible to miss messages from the beginning of the topic if we start publishing messages before we pull on the stream. While that might be okay for some use-cases, it’s not okay for our use-case here. We will want each of our deduce-single-candidate-streams to consume all of the messages on the topic starting from the very beginning. <br> <br>Coming back to the subscribeAndAwait method, it takes just one argument maxQueued: Int which is used internally by FS2 for back-pressuring publishers. For our use-case we can just set this to any number greater than or equal to 81 since the maximum number of messages we can expect to be published to the topic is 81 (the number of cells on a normal 9x9 Sudoku board) and as a result, we don’t really care much about back-pressuring our publishers.</li><li>We then map over the Resource so that we can transform the underlying Stream of messages from the topic which we’ll call updatesStream i.e. a stream of updates about other cell values.</li><li>We’ll start by creating a new Stream that filters the updatesStream for only Values about coordinates that are a peer of the coord that we are modelling the process of deducing the single candidate for. This filtering is not strictly necessary for the correctness of our program, it’s just an optimization we can make (we did something similar in each of the solutions to the previous two blogposts).</li><li>Next we will use a powerful method available on Stream instances called mapAccumulate. This method allows us to define a new Stream by applying a stateful operation that is expressed in the form of a “running total” over a Stream of elements. We will use this method to refine a set of initial candidates using the stream of updates. <br><br>The first argument to mapAccumulate is init: S, or rather in our case init: Candidate which represents the initial state we want to start our “running total” with. Just like in our previous posts, this will be Candidate.initial(coord) which returns a Candidate.Multiple(Set(1, 2, 3, 4, 5, 6, 7, 8, 9)) i.e. all the possible candidates when we have no other information. <br> <br>The last argument to mapAccumulate is a function f: (S, O) =&gt; (S, O2), or rather in our case f: (Candidate, Value) =&gt; (Candidate, Candidate). This is a function that takes in the current state (S/Candidate) and the next element in the stream (O/Value), and should return the next state (S/Candidate) and the next value that should be emitted by the stream (O2/Candidate). We will define our f as a couple of exhaustive case statements.</li><li>The first case we need to handle is if the state is still a multiple: Candidate.Multiple.</li><li>In this scenario, we call the refine method that is available on any Candidate.Multiple instance and pass in the next element of the stream, peerValue, as the argument. This will return the nextCandidate value which will be either another Candidate.Multiple or a Candidate.Single.</li><li>Either way, we return the result of that operation as both the next state and the next value to be emitted by the stream.</li><li>The remaining case is if the state has already been refined to a single: Candidate.Single. This scenario is even simpler to handle; we can just return the single as the next state and the next value to be emitted by the stream.</li><li>Finally, we use the collectFirst method to return a new Stream which only emits the first Candidate.Single it matches, after which the Stream is terminated. <br> <br>Note that we could have pattern matched on either of the elements of the tuple since they should both be the same value.</li></ol><p>We now have a function that we can use to generate Resource[IO, Stream[IO, Candidate.Single]]values to deduce the single candidate for a missing cell coordinate. We’re now at the point where we can, with the help of our missingValueStreamResource function, write another function that will return a Stream[IO, Value] which will emits the value of every (given and missing) coordinate in the Sudoku board. In other words, our function needs to materialize the following pieces of our architecture.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3_8dhWuZuAqe0OvQiunkog.png" /><figcaption>In terms of our architecture diagram, these are the parts we’re focused on at the moment.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*gUb4J7EawSSUyFn1pTSAWw.png" /></figure><ol><li>First, we create a Topic. Note that creating a Topic is an effectful action. We can lift this action into a Stream context using theStream.eval method.</li><li>Next, we create a Set of givenCoords.</li><li>Then we can generate a List of missingCoords by filtering out any elements in allCoords that are also in givenCoords.</li><li>Now we can start generating some of the streams in our architecture diagram. We first need a givensStream: Stream[IO, Value.Given]which we can create easily using Stream.emits(givens).</li><li>Now, we need a List[Stream[IO, Candidate.Single]] where each element of the list corresponds with a stream process for deducing the single candidate for one of the missing coordinates. We’ll break this step into two lines of code to make things clear. First we traverse missingCoords to create a Resource[IO, List[Stream[IO, Candidate.Single]]] by calling the missingValueStreamResource method we defined earlier with the updatesTopic argument. Note the = sign; all we’ve done is assign this pure value to a variable, we have not evaluated any <em>effect</em> yet.</li><li>Next, we lift our Resource into a Stream context using the Stream.resource method and actually evaluate the effect i.e. &lt;-. The result of this is our desiredList[Stream[IO, Candidate.Single]] which we assign to a variable called missingValueStreams. Remember, the Resource modelled the effect of subscribing, so at this point each of our missingValueStreams are subscribed to the updatesTopic. Any messages published to the updatesTopic from this point onwards will be read by each of our missingValueStreams.</li><li>We currently have missingValueStreams which is a List[Stream[IO, Candidate.Single]]. We need to reduce this List[Stream[IO, Candidate.Single]] into a single Stream[IO, Candidate.Single] which will emit the single candidate for each missing cell as they are deduced. We’ll call this missingValuesStream (note the change in pluralization). The only question is what binary op function do we pass to reduce?<br> <br>missingValuesStream = missingValueStreams.reduce(???)<br><br>The answer to that depends on how we want to run these streams in relation to each other. Do we want to run them sequentially? That won’t work, one stream might depend on another stream emitting a value first. This suggests that we want the streams to run in a concurrent fashion i.e. run one stream for a bit, then run another stream for a bit, and so on until all the streams in the list have terminated. This is exactly the behaviour we get when we merge two streams. Thus, we end up with:<br> <br>missingValuesStream = missingValueStreams.reduce(_ merge _)</li><li>Next we append missingValuesStream to givenValuesStream<br>using the ++ method giving us a valuesStream: Stream[IO, Value]. This valuesStream will emit the values of each and every coordinate in the Sudoku board. <br> <br>Note that the order of the arguments to ++ matters here, we want valuesStream to emit the elements of givenValuesStream first before emitting any elements of missingValuesStream. This is because our missingValuesStream won’t be able to deduce anything without any initial clues and our program would just get stuck! <br> <br>Also note that instead of combining givenValuesStream and missingValuesStream sequentially using ++ , we could have combined them in a concurrent fashion using merge. It doesn’t make any difference to the correctness of our program; it just makes more sense to seed the initial clues before attempting to deduce any of the single candidates for the missing cells.</li><li>Although valuesStream has the right type Stream[IO, Value] that we want our function to return, it won’t actually emit the values of every coordinate in the Sudoku board yet. The reason for this is because we’re not currently publishing any values to the updatesTopic. If we never publish any values to the updatesTopic, our missingValueStreams will never be able to deduce anything since they won’t have any clues to work with if the updatesTopic is forever empty. Fortunately, this is a simple matter to solve. We can just create a new stream, publishedValuesStream, that publishes each Value emitted by valuesStream via .evalTap(updatesTopic.publish1).</li><li>Finally we can evaluate (&lt;-) the publishedValuesStream which gives us back a value: Value.</li><li>The last step is to yield each emitted value.</li></ol><p>This function leaves us with a Stream[IO, Value] program that correctly describes our desired streaming program. However, our Solver[IO] interface requires that we return an IO[List[Value]]. We can “compile” our Stream[IO, Value] down into an IO[List[Value]] effect easily as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XgCveRr0Q78ogRdQ6pcpYA.png" /><figcaption>In terms of our architecture diagram, this is the part we’re focused on at the moment.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0aiRSUoZVOjH-w4b3XIDRw.png" /></figure><p>And that’s it! Our implementation is complete. At this point, you can try running this FS2StreamSolver against the unit tests in the repo and you should see that they pass.</p><h3>Reflections</h3><p>Using FS2 , we were able to write a fairly natural streaming solution for our problem. Most of our code was just creating and combining differentStream values. Combining streams in a concurrent vs sequential fashion itself was just a matter of just choosing the right method; merge vs ++.</p><p>On the flip side, we did have to deal with some relatively complicated looking types; at one point we even had a type of Resource[IO, List[Stream[IO, Candidate.Single]]]. Also, this implementation is a bit slower. If you run the unit tests, you’ll see the FS2StreamSolver takes a little bit longer than our previous two implementations (although we’re still talking in the range of milliseconds).</p><p>At the end of the day, there are always trade-offs and each of the solutions we presented in this series has different pros and cons. Our first solution (CatsEffectDeferredRefRaceSolver) was rather complicated and required us to think in terms of low-level constructs like fibers. On the other hand, it allowed us to express a solution that closely modelled the way an average person would typically solve a Sudoku puzzle with just pen and paper. Our second solution (CatsEffectQueueSolver) was much simpler as we were able to define our program in “higher-level” terms using purely “structured” concurrency primitives and methods. Our final solution FS2StreamSolver arguably goes even further on the “structured” concurrency path and this lends itself to a very natural seeming solution at the cost of having to occasionally work with some complicated types. As you can see, there’s a spectrum of valid design choices but in general, it’s preferable to use “structured” concurrency primitives like Queue where possible, and only drop to lower-level primitives (like Ref and DeferRed) when those prove insufficiently powerful for your use-case.</p><p>Ofcourse you can always solve this problem without any Cats Effect or FS2; in fact plain old Future and a concurrent, mutable Map implementation are sufficient to solve this problem, as long as you’re willing to sacrifice referential transparency and all the benefits that come with it. While that might be fine for a trivial program like this one, in larger and more complex programs, referential transparency and structured concurrency are much more maintainable over the long term.</p><p>That’s it for this series, we hope you enjoyed it and see you in a future blogpost.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=949c8b099abb" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Concurrent Sudoku Solver: Part 3 - Using Cats Effect Queue]]></title>
            <link>https://medium.com/@fqaiser94/concurrent-sudoku-solver-part-3-using-cats-effect-queue-459e2da28b6?source=rss-ac4d9cb6496a------2</link>
            <guid isPermaLink="false">https://medium.com/p/459e2da28b6</guid>
            <category><![CDATA[functional-programming]]></category>
            <category><![CDATA[cats-effect]]></category>
            <category><![CDATA[scala]]></category>
            <dc:creator><![CDATA[Farooq Qaiser]]></dc:creator>
            <pubDate>Tue, 24 May 2022 21:07:21 GMT</pubDate>
            <atom:updated>2022-06-24T02:30:52.841Z</atom:updated>
            <content:encoded><![CDATA[<h3>Introduction</h3><p>In <a href="https://medium.com/@fqaiser94/concurrent-sudoku-solver-part-2-using-cats-effect-ref-deferred-io-race-a380a182c233">Part 2</a>, we used a combination of Ref, Deferred, and IO.race from Cats Effect to implement a concurrent Sudoku solver. In this post, we will use a different concurrency primitive from the Cats Effect standard library, Queue, to write a much simpler Sudoku Solver implementation . As before, you can find all the code we’ll be writing today in the <a href="https://github.com/fqaiser94/concurrent-sudoku-solver">concurrent-sudoku-solver repo</a>.</p><h3>Queue</h3><p>You can find queue-like data structures in most languages/frameworks. The Scala standard library itself offers scala.collection.immutable.Queue. In this sense, Cats Effect’s Queue should look quite familiar. What’s nice about Cats Effect Queue however is that it is a purely functional implementation; it’s methods return IO i.e. referentially transparent values. In addition, it can be used in a concurrent fashion safely. Let’s take a closer look at a simplified version of Cats Effect Queue that has only the methods we care about for the purposes of this blogpost:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/666/1*hoBo_XN9cT3eDv_5raI8Dg.png" /></figure><ol><li>The take method returns an IO that models the effect of dequeueing an element from the front of the queue, potentially blocking (semantically) until an element becomes available.</li><li>The offer method returns an IO that models the effect of enqueueing the given element at the back of the queue.</li></ol><p>Nothing unusual to see there, they’re both relatively simple methods. So how exactly are we going to be using a Queue in our concurrent Sudoku solver?</p><h3>High level architecture</h3><p>For our purposes, we will be using Queue as a mechanism for delivering updates to a cell about its peers. Specifically, every time a Cell is solved, we will take its solved Value and offer it to each of its peers’ updatesQueue. Each peer cell will then be able to take Values from their updatesQueue to refine their own internal state of candidates and eventually reach a solution. At which point, they will return their solved Value which will then be offered to each of their peers via their updatesQueue, and so on.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*BlayW2bd9sXrytow-kF_IA.png" /></figure><p>As you can see, this is only slightly different from our solution in Part 2, where each Cell was directly connected to each of its peers via a Deferred. Here, we’ve “decoupled” things a little bit in the sense that we have an external-to-the-cell process that broadcasts changes in the board to each cell, and cells have no awareness of other cells except through their updatesQueue.</p><p>Hopefully that all made sense. Before we continue, go ahead and try implementing this yourself! It’s much easier than you think. When you’re done, you can compare with our solution, as follows.</p><h3>Code</h3><p>We’ll start by defining a small MissingCell class:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1AGA7tKKoY6xS-cMDLNyzQ.png" /></figure><ol><li>To initialize an instance of MissingCell , all we need to provide is a Coord and a Queue.</li><li>Each MissingCell exposes a solve value of type IO[Candidate.Single] . This IO value models the process of deducing the single candidate solution for this MissingCell, and this is the process we will need to execute for each missing cell in our Sudoku board at the top level of our program. <br> <br>As you can see though, this value is actually created by the refineToSingleCandidate method which accepts only one argument of type Candidate.Multiple. Recall from Part 1 that the only way to create a Candidate.Multiple is through the Candidate.initial(coord: Coord)method which returns a Candidate.Multiple(coord, Set(1, 2, 3, 4, 5, 6, 7, 8, 9)) i.e. an initial set of candidate values. The purpose of refineToSingleCandidate is to return an IO that refines this down to a Candidate.Single. So let’s take a look at how it does that next.</li><li>Our refineToSingleCandidate method starts by attempting to take a value from the updatesQueue of this MissingCell. As previously mentioned, this is a semantically blocking action, similar to Deferred.get which we saw in our last post. And again, this blocking behaviour is fine. Until an element is enqueued on this updatesQueue (i.e. until a peer is solved) there is nothing useful we can do anyway so we might as well be blocked.</li><li>However, once we do obtain a peerValue, we can attempt to refine our existing set of candidates.</li><li>If we are successful in refining it into a Candidate.Single, we simply return that single value wrapped in an IO.</li><li>If we are not successful, we call refineToSingleCandidate again with the potentially refined multiple , and we will continue to do this until we hit the terminating condition i.e. step 6. Effectively, what we’ve expressed here is a stateful operation using recursion instead of a mutable variable. Note that IO is naturally stack-safe so we don’t need to write refineToSingleCandidate in a tail-recursive fashion to avoid stack overflow.</li><li>Eventually though, we will be successful in refining to a Candidate.Single and we return this value (singleCandidate ).</li></ol><p>And that’s pretty much it for our MissingCell class. We can provide a convenience make method in the companion object which just takes care of initializing a separate Queue for each instance:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*YGvS0KnSPE9L8h5_H2nv1A.png" /></figure><p>The only worth noting here is that creating a Queue is itself an effectful action.</p><p>The last piece of functionality we’re missing is the “broadcast” function that will enqueue solved Value updates to each of the relevant peers’ updatesQueue. This is a trivial matter to code:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*dpNDeROf9F6jlZc4aiyrrQ.png" /></figure><ol><li>We filter the list of cells for only those that are peers of the update.</li><li>We offer (or enqueue) the update on to the updatesQueue of each of the filtered cells. It doesn’t matter for correctness if we did this using parTraverse_ or traverse_ , it just so happens that these are independent actions that we can perform concurrently so we might as well.</li></ol><p>Finally, we can take all of these pieces and put them together at the top level of our program in the solve method:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rc7BNMkKGzx3aBkz-ohOBw.png" /></figure><ol><li>First, we generate a Set of givenCoords.</li><li>Next, we generate a List of missingCoords by filtering out any elements in allCoords that are also in givenCoords.</li><li>We can now generate a List of MissingCell by passing each element of missingCoords to MissingCell.make.</li><li>Here we create a broadcast function which is just the broadcastToPeers function we defined earlier with the first argument “filled in” as missingCells.</li><li>Using the function we created in the previous step, we broadcast the givenValues to the relevant missingCells. All this means is we’re enqueueing the givenValues to the updatesQueue of the relevant MissingCell instances. At this point, we have “seeded” the initial state of the Sudoku board. Now we just need to kick off the process for solving each of the missingCells.</li><li>We can do that by executing the solve IO on each missingCell and whenever that returns a Candidate.Single, broadcast it to the relevant MissingCell peers. Note that we execute this action concurrently across all missingCells via the parTraverse combinator. If we were to do this sequentially (using just traverse), our program wouldn’t work (unless you were extremely lucky).</li><li>Lastly, we return the concatenated List of givenValues and the solved missingValues.</li></ol><p>And that’s it! We have finished writing another concurrent Sudoku Solver. You can check out the unit tests in the repo if you need more convincing that our code works.</p><h3>Reflections</h3><p>Cats EffectQueue offers almost exactly the high-level semantics we needed to solve this problem elegantly. This is in stark contrast with our solution in <a href="https://medium.com/@fqaiser94/concurrent-sudoku-solver-part-2-using-cats-effect-ref-deferred-io-race-a380a182c233">Part 2</a> where we had to think explicitly in terms of fibers, shared state, cancellation etc. In general, you should prefer the more structured APIs like Queue from the Cats Effect standard library and only consider using low-level primitives like Ref and Deferred when these fall short of your needs.</p><p>One thing you might have noticed about our solution in this post is how, inside the refineToSingleCandidate method, we used Queue to effectively produce a stream of updates about a cell’s peers, and then continuously consumed those updates until we reached a solution. We will take this idea further by writing a streaming oriented solution using the infamous FS2 library in the <a href="https://medium.com/@fqaiser94/concurrent-sudoku-solver-part-4-using-fs2-stream-topic-949c8b099abb">next</a> and final post of this series.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=459e2da28b6" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Concurrent Sudoku Solver: Part 2 - Using Cats Effect Ref + Deferred + IO.race]]></title>
            <link>https://medium.com/@fqaiser94/concurrent-sudoku-solver-part-2-using-cats-effect-ref-deferred-io-race-a380a182c233?source=rss-ac4d9cb6496a------2</link>
            <guid isPermaLink="false">https://medium.com/p/a380a182c233</guid>
            <category><![CDATA[functional-programming]]></category>
            <category><![CDATA[scala]]></category>
            <category><![CDATA[cats-effect]]></category>
            <dc:creator><![CDATA[Farooq Qaiser]]></dc:creator>
            <pubDate>Sun, 08 May 2022 19:48:45 GMT</pubDate>
            <atom:updated>2022-06-25T12:48:33.601Z</atom:updated>
            <content:encoded><![CDATA[<h3>Introduction</h3><p>In <a href="https://medium.com/@fqaiser94/concurrent-sudoku-solver-part-1-single-candidate-technique-domain-modelling-6c885a1e4ef3">Part 1</a>, we introduced the Single Candidate technique and defined some general classes and methods to model our Sudoku domain. In this post, we will use Ref, Deferred, and IO.race from Cats Effect to implement our first concurrent Sudoku Solver implementation. Don’t worry if you don’t know what each of these do yet, we’ll introduce them as we go. Same as before, you can find all the code we’ll be writing today in the <a href="https://github.com/fqaiser94/concurrent-sudoku-solver">concurrent-sudoku-solver repo</a>. Without further ado, let’s get started!</p><h3>Cell abstraction</h3><p>First, let’s give our problem some structure by defining what a Cell is in abstract terms:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wfy3EuxSwA2agK8EW3ItjQ.png" /></figure><p>Here we’ve defined Cell as a data structure consisting of 4 members:</p><ol><li>coord which models the co-ordinate the Cell represents.</li><li>deferredValue which is typed as a Deferred[IO, Value]. What exactly is a Deferred? If you’ve ever used something like a Promise in another language/framework, you’ll find Deferred a familiar concept. In the <a href="https://typelevel.org/cats-effect/docs/std/deferred">Cats Effect documentation</a>, Deferred is described as: <br> <br><em>“A purely functional synchronization primitive which represents a single value which may not yet be available. When created, a Deferred is empty. It can then be completed exactly once, and never be made empty again.”</em> <br> <br>In our case, we are mostly interested in using this data type to model the idea that a Cell will <strong><em>eventually</em></strong> have a Value, once we’re able to logically deduce it. This deferredValue is going to play a big role in enabling ourCells to “react” whenever one of their peers are solved, and we’ll talk more about this shortly. <br> <br> One thing you might have noticed about our deferredValue is we added a protected[this] access modifier. This ensures other Cells are not able to directly access the deferredValue. Specifically, we want to to ensure that no other Cell is able to .complete the deferredValue. We’ll see later in the solve method that each Cell is responsible for completing its own deferredValue.</li><li>However we do want other Cells to be able to read each other’s deferredValue so this line of code exposes a specific getValueAPI to enable exactly that. All we’re doing here is calling .get on the underlying Deferred. This is a <strong>blocking</strong> action; any fibers attempting to read the Value inside the Deferred will be blocked until the Deferred is completed. The term “blocking” might set off alarm bells in your head but there’s nothing to worry about here, .get is only semantically blocking in the sense that no actual threads are blocked so you’re not wasting compute power unnecessarily. This behaviour is similar to IO.sleep and other such async operations in Cats Effect.</li><li>Next we have the deduceSingleCandidate method which is expected to return an IO that models the process of deducing the Value of this Cell. To that end, this method accepts one further piece of information; allCells which is a reference to all 81 Cells in the Sudoku board which we’ll need to be able to get the Value of each of our peers (via their .getValue methods!)</li><li>Finally we have the solve method which is expected to do two things: <br>a) Return this Cell’s Value and <br>b) Complete this Cell’s deferredValue. Completing each Cell’s deferredValue is an important part of our program. If we don’t complete the deferredValue, it will remain empty forever, and any parts of our program that have called .get on that deferredValue will be blocked forever. In contrast, completing the deferredValue immediately unblocks any fibers attempting to read the deferredValue. This is why Deferred is often referred to as a “synchronization” primitive; it allows us to synchronize the timing of the execution of multiple fibers.<br> <br>We can already fully define the solve method for all implementations, as follows.</li><li>We first check if the coord of this Cell is in the givens, in which case we already know it’s value and we can simply .complete this Cell’s deferredValue using it.</li><li>Otherwise, we use the deduceSingleCandidate method to determine the Cell’s Value and use the result of that process to .complete the deferredValue.</li></ol><p>As you can see, a Cell as we’ve defined it isn’t a particularly complicated data structure. It’s mostly just a wrapper around Deferred. To write a concrete implementation of Cell, the bulk of the work is going to be in writing the deduceSingleCandidate method, which we will do in a moment. First however, let’s see how we will actually use this Cell abstraction inside the solve method of our Solver implementation which we’re going to unimaginatively call CatsEffectDeferredRefRaceSolver:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XpFpyb6eTdVvVsv6GgivDQ.png" /></figure><ol><li>We create an instance of Cell for each coordinate on the Sudoku board (assume for now that we have a working Cell.make method that effectfully returns a concrete implementation of our Cell trait for this purpose).</li><li>This is just a simple transformation of our givens from a List into a Map structure, which we will need for the next step.</li><li>Now, we call .solve on each Cell we created in step 1, and we perform this action on each Cell <strong><em>concurrently</em></strong> using the parTraverse combinator. .parTraverse is one of several IO combinators in the Cats Effect toolkit that allow us to express control-flow semantics (and we will see another one in action later). parTraverse takes a list of IO and runs them all concurrently, terminating only when all the IO in the list have terminated. This particular .parTraverse call is what makes our Sudoku Solver a <strong>Concurrent </strong>Sudoku Solver, and while we’re far from done yet, that is the whole point of this blogpost! <br> <br>Notice we are deliberately saying concurrently, rather than in parallel, as there is in fact a distinction between the two and we’re only really guaranteed the former. Our use of .parTraverse is merely declaring to the underlying runtime that these IO are independent and <em>can</em> be evaluated in parallel. Whether or not they <em>are </em>actually executed in parallel is up to the runtime (for example, Cats Effect won’t run anything in parallel if it’s being executed in a single-threaded language like JavaScript via Scala.js because it obviously can’t).</li><li>Finally, we return our list of solved Values.</li></ol><p>Hopefully at this point you understand the big picture of what we’re trying to do. Now all we need to do is figure out how to actually write a valid implementation of our Cell trait and have the Cell.make method return that.</p><h3>Cell implementation</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*bP8C3PASw4AQOObto44yCg.png" /></figure><ol><li>We start by creating an instance of a Deferred. Note that this is an effectful action, and this is why our make constructor method returns an IO[Cell] instead of just a Cell.</li><li>We assign to coord the _coord constructor argument.</li><li>We assign deferredValue the instance we created in step 1.</li><li>Now we get to deduceSingleCandidate. We start by creating a Ref. This is our first encounter with this concurrency primitive so let’s introduce it. <a href="https://typelevel.org/cats-effect/docs/std/ref">Cats Effect documentation</a> describes it as a construct that “<em>provides safe concurrent access and modification of its content</em>.” For our use-case, we’ll be using a Ref to store our state of available candidates for each Cell. Over the course of the solving process, we will “mutate” this state as we eliminate available candidates using the Single Candidate technique. As we’ll see shortly, we will actually have multiple processes accessing and modifying this Ref instance during the solving process so the “<em>safe concurrent access</em>” aspect of a Ref is also important to us. <br> <br>To create a Ref, we need to give it an initial value. In our case, we can provide this initial value using the Candidate.initial method we defined in <a href="https://medium.com/@fqaiser94/concurrent-sudoku-solver-part-1-single-candidate-technique-domain-modelling-6c885a1e4ef3">Part 1</a>. This returns a Candidate.Multiple(Set(1, 2, 3, 4, 5, 6, 7, 8, 9)). Note that, similar to Deferred, creating a Ref is also an effectful action. Our task now is to refine the Candidate.Multiple inside our Ref into a Candidate.Single which brings us to the next line of code.</li><li>We filter allCells for only cells that are peers of this cell. This isn’t strictly necessary but it’s a small optimization we can make as we know that the Value of each cell is determined solely by it’s peers when using the Single Candidate technique.</li><li>Then we take each peer and create an IO using a refineToSingleCandidateOrNever function. We’ll implement this function shortly but let’s at least define the behaviour we expect from this function here. This function will attempt to use each peer’s value to refine the Ref of available candidates. After refinement, if we discover that only one candidate is left, this function will return that single candidate. If however, the peer’s Value does not refine the number of candidates down to just a single candidate, the function will simply never return anything i.e. it will never terminate. This is why we’ve named the function refineToSingleCandidateOrNever. <br> <br>So what you will have at the end of this .map operation is a List consisting of 20 IO[Candidate.Single] values (since each cell has exactly 20 peers) but only one of these IO will actually eventually return the Candidate.Single Value of this Cell. The remaining 19 IO will simply never terminate. The question for us is how do we convert this List[IO[Candidate.Single]] into an IO[Candidate.Single]which <em>is</em> guaranteed to terminate and return a Candidate.Single Value? This brings us to the next line of code.</li><li>You might be tempted to use parTraverse again which will run each IO[Candidate.Single] in our list concurrently. However, since all but one of the IO in the List will never terminate, the resulting IO from .parTraverse itself will never terminate either. We could do something hack-y like add .timeout calls but this is obviously not optimal. <br> <br>Our problem here really is that parTraverse is the wrong combinator to use here. The behaviour we actually want is to run each IO[Candidate.Single] in our list concurrently, <strong><em>and</em></strong> return the result of the first IO in our list to complete successfully while cancelling the remaining IO. <br> <br>This is almost the behaviour offered by the aptly named IO.race combinator, the only difference is that IO.race takes only a pair of IO at a time and returns the first to finish in an Either type. Luckily, it’s easy enough to write a small helper function raceMany that just builds on top of IO.race with our desired type-signature and semantics (takes a list of IO, returns the result of first successful IO, and cancels the rest).</li><li>Finally, we can just return the result of applying our raceMany function to the listOfSingleCandidateOrNever i.e. singleCandidate and that concludes the definition of our deduceSingleCandidate function.</li></ol><p>At this point, you might be concerned about the number of concurrent processes we would be creating using this approach. For each Cell we call deduceSingleCandidate on, we end up creating 20 concurrent processes (one for each peer). So, if a Sudoku puzzle has 50 missing Cells, we would end up creating at least 1000 (50 * 20) concurrent processes. Now, that might sound like a lot but actually, there is nothing to be concerned about here. The fundamental abstraction in Cats Effect is a <a href="https://typelevel.org/cats-effect/docs/concepts#fibers">Fiber</a>, and this is ultimately what each of our concurrent processes will map back to. And unlike physical threads, which are extremely scarce, you can create literally millions of fibers as they’re quite lightweight and the IO runtime will take care of scheduling them in an efficient and fair manner. If you’re still unconvinced, here’s a short excerpt from the <a href="https://typelevel.org/cats-effect/docs/concepts#fibers">Cats Effect documentation</a>:</p><blockquote>Fibers are <em>the</em> fundamental abstraction in Cats Effect. The terminology is intentionally reminiscent of Threads since fibers are literally lightweight threads (often referred to as &quot;green threads&quot; or &quot;coroutines&quot;). Much like threads, they represent a sequence of actions which will ultimately be evaluated in that order by the underlying hardware. Where fibers diverge from threads is in their footprint and level of abstraction.</blockquote><blockquote>Fibers are <em>very</em> lightweight. The Cats Effect IO runtime implements fibers in roughly 150 <em>bytes</em> per fiber, meaning that you can literally create tens of millions of fibers within the same process without a problem, and your primary limiting factor will simply be memory.</blockquote><p>The last piece we need to figure out is how to write the refineToSingleCandidateOrNever function which bring us to our last snippet of code:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*AS9wEHt1ycGp9-A2n9NaYQ.png" /></figure><ol><li>We call .getValue on the peerCell. Recall that this is a blocking action; it will return a Value <em>eventually</em>, and this is absolutely fine! We want this IO to wait until the peerCell has been solved and has a Value. A peerCell that hasn’t been solved isn’t any use to us.</li><li>Once we have the peer’s Value, we can proceed to refining the Ref[IO, Candidate]. Ref offers a number of methods for modifying their contents such as .set, .update, .modify etc. Depending on the semantics you’re looking for, one or another method will make the most sense to use. In our case, we will use the .modify method. This is an extremely powerful function and a little hard to explain with just words. To make things easier, let’s look at a stripped down definition of Ref and the .modify method:<br> <br>class Ref[A] { def modify[B](f: A =&gt; (A, B)): IO[B] }<br> <br>As you can see from this type-signature, .modify is a higher-order function. The idea is that we give .modify a function (f) that can take in the existing value (A) of the Ref and return a tuple consisting of the next value (A) to set inside the Ref as well as another value (B) that .modify itself will return effectfully (IO[B]). .modify will attempt to run our function to completion but if at any point during the running of our function, the value (A) already inside the Ref changes (i.e. a concurrent modification occurs), .modify will re-run our function using the updated value in the Ref. Note that it may need to do this several times if there are a lot of concurrent modifications happening to the Ref. Under the hood, Ref is mostly just a functional wrapper around Java’s AtomicReference and will use a compare-and-swap (also known as a CAS) loop to make concurrent modifications safely, hence why f might be run multiple times. As a result, we should ensure our function f is <em>pure</em> (deterministic and free of side-effects) because .modify might run f multiple times, otherwise we risk getting unexpected results. <br> <br>So, our next course of action is to actually write our f which we will do as an anonymous function consisting of a series of case statements handling each of the states our Ref could be in.</li><li>Figuring out the next value (A) of the Ref based on the peerValue is the easy part for. If the value inside the Ref is a Candidate.Multiple, we can call the refine method on it. If this returns a Candidate.Single, it means we’ve successfully found the solution to this Cell! We can therefore set the next value of the Ref to this Candidate.Single. <br> <br>In addition, recall that .modify expects f to return a tuple of not just the next value (A) of the Ref but also the value (B) we want .modify itself to return. In our case, we can return the same Candidate.Single value we’ve obtained except we’ll wrap it in an IO using IO.pure. Why are we wrapping this in an IO? Why not just return the plain Candidate.Single value? The reason for this will become evident once we go through the other case statements.</li><li>Even if we aren’t able to refine the Candidate.Multiple into a Candidate.Single, we may have still managed to eliminate a candidate! For example, if the original state of our Ref is Candidate.Multiple(Set(1, 2, 3)) and we see the peerValue.value is 3, we can still refine our state to Candidate.Multiple(Set(1, 2))! Therefore, we can set the next value of the Ref to the potentially refined multiple. However, in this case, we return an IO.never as our B. IO.never describes a program that never terminates. At first glance, that probably seems like a stupid and wasteful thing to do but remember our deduceSingleCandidate function is prepared to handle this behaviour via the raceMany function i.e. it is expecting only one IO to return a Candidate.Single value (the first case statement), and the rest of the IO to simply never terminate.</li><li>Finally, in the case where the Ref is already a Candidate.Single, we simply set that as the next value (i.e. this is effectively a no-op) and return an IO.never as our B, similarly to the second case. We could have returned an IO.pure(single) here as well and it wouldn’t make any difference to the correctness of our program but this is not strictly necessary, as the only way to end up in this case is if a previous .modify of Ref already refined the Candidate.Multiple into a Candidate.Single for us, and this would have already returned an IO.pure(single) to the caller. <br> <br>And that’s it for our f function. .modify will run this function, potentially several times, and it will return an IO[IO[Candidate.Single]]. You might wonder, why do we have an IO nested in an IO? Glad you asked.</li><li>So, our f returns an IO[Candidate.Single] as it’s B and .modify will return this value to us but .modify itself is an effectful function meaning it will return this value to us effectfully as an IO[B] , or in our case IO[IO[Candidate.Single]]. Most of the time when you end up with an IO nested inside another IO, you’ve likely done something wrong like used .map instead of .flatMap. In this case however, there is no .flatModify variant of .modify so we’re going to have to just call .flatten ourselves to get back an IO[Candidate.Single]. While it’s not super important, it can be helpful to understand what exactly an IO[IO[Candidate.Single]] represents for us. <br> <br>First of all, recall that an IO is simply a <em>description of a program</em>. So IO[IO[Candidate.Single]] is a description of a program that describes how to generate a description of another program. In our case, the outer IO program describes how .modify will update the value of the Ref and return an IO[Candidate.Single] program. The IO[Candidate.Single] program itself is a description of a program that returns a Candidate.Single. More specifically, the inner IO (i.e. IO[Candidate.Single]) program, the way we’ve defined it, will return to us a Candidate.Single value if and only if we were able to refine our Ref into a Candidate.Single, otherwise it will never terminate. Therefore, if we want to run the inner program, we need to .flatten our IO[IO[Candidate.Single]] into a IO[Candidate.Single]<br> <br>This pattern of having f return an IO as the B and then calling .flatten on the resulting nested IO from .modify allows us to essentially run some code if and only if we’ve successfully updated the Ref. There’s other ways to write this that are perhaps less cryptic but this is probably the most concise way, and once you understand it, it’s pretty neat.</li><li>Finally, we return the singleCandidate we’ve deduced for this Cell, if ever.</li></ol><p>And with that, we’ve written all the code we need. If we run this Solver against an easy Sudoku puzzle, it will actually work! Below is the input and output from one of the unit tests in the repo:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fmCvN_UE4h1srPidQOyclQ.png" /></figure><h3>Reflections</h3><p>Phew, that was a lot of content to cover. Before we part ways, lets recap some of the interesting features of Cats Effect we encountered in this post:</p><ul><li>Deferred provides a nice way of synchronizing multiple IO. We didn’t have to write any logic to poll for the state of other cells. Instead we were able to just block any dependent IO via a Deferred.get call.</li><li>Ref on the other hand is great for sharing and modifying state between multiple IO safely. We not only get referential-transparency but also don’t have to deal with tricky locks and/or blocking of threads which is often the traditional solution.</li><li>Lastly, we saw how we can use combinators like parTraverse and race to compose concurrent operations. The key word to highlight here is that we <em>compose</em> IO values. Just like flatMap, parTraverse and race combine IO values and give back IO values. And these IO values we get back are still <em>just a value</em> describing a program. In this way, we’re able to iteratively build up complex IO programs simply by combining smaller IO programs, which is pretty neat.</li></ul><p>On the flip side though, it’s hard to deny our Solver implementation is complicated, and in particular the deduceSingleCandidate method. It’s not that we wrote a particularly large amount of code (in fact, this was just under 60 lines of code), it’s just the code is quite “dense.” While this is partly due to the concurrent nature of the program, we’ve also made our life a bit difficult by using relatively low-level primitives from the Cats Effect standard library such as Ref and Deferred. We have much more “structured” APIs available in Cats Effect for writing concurrent programs and we will use one of these to solve this same problem in the next post in a much simpler fashion. Join us in <a href="https://medium.com/@fqaiser94/concurrent-sudoku-solver-part-3-using-cats-effect-queue-459e2da28b6">Part 3</a> to see how we can solve this same problem using Cats Effect Queue!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a380a182c233" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Concurrent Sudoku Solver: Part 1 - Single Candidate Technique + Domain Modelling]]></title>
            <link>https://medium.com/@fqaiser94/concurrent-sudoku-solver-part-1-single-candidate-technique-domain-modelling-6c885a1e4ef3?source=rss-ac4d9cb6496a------2</link>
            <guid isPermaLink="false">https://medium.com/p/6c885a1e4ef3</guid>
            <category><![CDATA[cats-effect]]></category>
            <category><![CDATA[functional-programming]]></category>
            <category><![CDATA[fs2]]></category>
            <category><![CDATA[scala]]></category>
            <dc:creator><![CDATA[Farooq Qaiser]]></dc:creator>
            <pubDate>Sun, 08 May 2022 18:53:40 GMT</pubDate>
            <atom:updated>2022-06-24T02:30:18.324Z</atom:updated>
            <content:encoded><![CDATA[<h3>Introduction</h3><p>The Cats Effect family of libraries is well known in the Scala ecosystem. In addition to functional programming capabilities, they also offer a number of primitives for writing concurrent programs in a referentially transparent and highly composable fashion. In this series of blogposts, we’ll be exploring how we can leverage these capabilities to write a concurrent Sudoku solver in a few different ways. This will be a four-part series consisting of:</p><ul><li><a href="https://medium.com/@fqaiser94/concurrent-sudoku-solver-part-1-single-candidate-technique-domain-modelling-6c885a1e4ef3">Part 1 - Single Candidate Technique + Domain Modelling</a></li><li><a href="https://medium.com/@fqaiser94/concurrent-sudoku-solver-part-2-using-cats-effect-ref-deferred-io-race-a380a182c233">Part 2 - Using Cats Effect Ref + Deferred + IO.race</a></li><li><a href="https://medium.com/@fqaiser94/concurrent-sudoku-solver-part-3-using-cats-effect-queue-459e2da28b6">Part 3 - Using Cats Effect Queue</a></li><li><a href="https://medium.com/@fqaiser94/concurrent-sudoku-solver-part-4-using-fs2-stream-topic-949c8b099abb">Part 4 - Using FS2 Stream + Topic</a></li></ul><p>In this first post, we will be mostly laying the groundwork for future posts by going over basic Sudoku theory and modelling some reusable elements in the Sudoku domain.</p><h3>Heads-up</h3><p>Some things to be aware of before you decide to embark on this journey:</p><ol><li>The “algorithm” we’ll be implementing is very basic and only capable of solving easy Sudoku puzzles. The point of this blogpost series is <strong><em>not</em></strong> to build a super-duper Sudoku solver but rather to demonstrate concurrent programming capabilities in Cats Effect and FS2.</li><li>For the sake of brevity, we will assume you already have some familiarity with Cats Effect and FS2. For example, while we won’t explain what .traverse does, we will discuss its concurrent sibling .parTraverse.</li><li>We’ll write most of the code together but we’ll skip things like imports. You can find all of the code in the <a href="https://github.com/fqaiser94/concurrent-sudoku-solver">concurrent-sudoku-solver repository</a>.</li></ol><h3>Single Candidate Technique</h3><p>Simple Sudoku puzzles can be solved using just the Single (or Sole) Candidate technique. We can summarize the whole technique in a couple of sentences. Basically, if we have eliminated all other possibilities for a cell and only one choice remains, this must be the correct value. You can eliminate possibilities by applying the rules of Sudoku i.e. a particular digit (1 – 9) can only occur once in each row, column, and box. For example, let’s say we have the following Sudoku board and we’re trying to figure out what digit goes into the cell shaded in yellow:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/573/1*XhX00WSd032gt-sP_Tb4Vg.png" /></figure><p>In this case, we can logically deduce that the yellow cell:</p><ul><li>Can’t be 1 or 2 or 3 because they already exist in the same row.</li><li>Can’t be 4 or 5 or 6 because they already exist in the same column.</li><li>Can’t be 7 or 8 because they already exist in the same box.</li><li>Must be 9 as that is the only remaining digit.</li></ul><p>What’s great about this technique is that we can model it as a process that can be <strong><em>independently</em></strong> executed for each and every cell on the board, making it amenable to a concurrency based implementation. More specifically, each cell should:</p><ul><li>Maintain an internal state of candidates</li><li>React whenever any of its 20 peers (cells in the same row, column, or box as this cell) are solved by removing the peer’s value from the internal state of possible candidates</li><li>Return the cell’s solution when the internal state of candidates is reduced to exactly one possibility</li></ul><p>The key thing to note about this process is that every time a cell is solved, it sets off a chain reaction in which the solved cell’s peers react by attempting to use the solved cell’s value to to solve themselves. Any peers that are then solved would then in turn cause their own (unsolved) peers to react by attempting to solve themselves, and so on in a virtuous loop until eventually all the cells on the board are solved.</p><p>In this series, we will see how we can express this program in a number of different ways. However, before we dive into the wonderful world of concurrency, we’ll need to do the bare minimum in domain modelling to set ourselves up for success later.</p><h3>Domain Modelling</h3><p>We’ll start by defining the interface our concurrent Sudoku solver implementations will need to satisfy:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/988/1*PZ93xcfJf_LKMx3piBoWeQ.png" /></figure><p>As you can see, there is just one method solve that we need to define to satisfy this interface and this will take one argument, a List of Given values (i.e. the initial clues on the board), and is expected to return an F of a List containing the solved Value for all 81 cells on a Sudoku board. We’ll talk more about Value and Value.Given shortly. Note that while this signature isn’t completely type-safe (e.g. we could just return IO.pure(List.empty[Value])), writing the compile-time machinery to fix this is an unnecessary distraction for our purposes here. Also, don’t worry too much about the higher-kinded F type either; for most of this series this will just be hardcoded to IO.</p><p>Next, we have the Coord class:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*PRqI8-hpa0Y9Tjfg853usA.png" /></figure><p>The Coord class features two fields; row and col (short for “column”) and the intersection of those two fields can be used to uniquely identify a cell’s position on a Sudoku board. In addition, we have a isPeerOf method attached to each instance of Coord which accepts another Coord as an argument (that) and returns a boolean indicating whether that coord is a peer of this coord. Lastly, we have a few useful values in the companion object including allCoords which is a list of all the valid Coord values in a typical 9x9 Sudoku board.</p><p>Finally, let’s talk about the following code:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fgtbi8OoiAhB8ZZ7_l4WZQ.png" /></figure><p>First, we have a couple of sealed traits and classes that express the following sub-typing hierarchy:</p><ul><li>Value: Represents the idea of a final value that belongs to a co-ordinate. This could be either a:<br>- a Given i.e. one of the initial clues given to us on the board or<br>- a Single i.e. the single candidate that we’ve deduced for a cell.</li><li>Candidate: Represents the idea of candidate values for a coordinate. This could be either a: <br>- Multiple i.e. there are multiple candidates that could fill this cell or<br>- Single i.e. there is only one valid candidate that could fill this cell</li></ul><p>The interesting thing to note is that Single is both a Value and a Candidate.</p><p>Secondly, through our use of the private[Candidate] access modifier, we have enforced at compile time the following:</p><ul><li>a Candidate.Multiple can only be constructed via the initial method which initializes it with the natural default value ofSet(1, 2, 3, 4, 5, 6, 7, 8, 9)</li><li>a Candidate.Single cannot be constructed directly through any method; a Candidate.Single can only be obtained using the refine method on a Candidate.Multiple instance.</li></ul><p>Thirdly, you can think of the refine method as codifying the Single Candidate technique. It takes any Value (either a Given or Single) and removes the given Value.value from the set of candidates if the Value.coord is a peer of the coord, returning either a Multiple or Single based on the number of remaining candidates. Given the constraints enforced by private[Candidate] access modifiers, anyone attempting to use these domain objects is forced to use our implementation of the Single Candidate technique via the refine method to reach a solution.</p><p>There’s potentially other simpler ways we could have modelled this domain, but this particular approach has netted us <em>some</em> compile-time guarantees. It’s far from perfect but if we really wanted more than this, we’d be better off using something like <a href="https://www.idris-lang.org/">Idris</a> (possibly a topic for a future blogpost).</p><p>That’s it for domain modelling. We didn’t write a whole lot of code in this post, and we haven’t even so much as imported anything from Cats Effect yet! For that and more, join us in <a href="https://medium.com/@fqaiser94/concurrent-sudoku-solver-part-2-using-cats-effect-ref-deferred-io-race-a380a182c233">Part 2</a> of the series.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6c885a1e4ef3" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Using TestControl to Test FS2 Streams]]></title>
            <link>https://medium.com/@fqaiser94/using-testcontrol-to-test-fs2-streams-92cec1fac217?source=rss-ac4d9cb6496a------2</link>
            <guid isPermaLink="false">https://medium.com/p/92cec1fac217</guid>
            <category><![CDATA[fs2]]></category>
            <category><![CDATA[scala]]></category>
            <category><![CDATA[functional-programming]]></category>
            <category><![CDATA[testing]]></category>
            <category><![CDATA[cats-effect]]></category>
            <dc:creator><![CDATA[Farooq Qaiser]]></dc:creator>
            <pubDate>Mon, 21 Mar 2022 22:13:29 GMT</pubDate>
            <atom:updated>2024-08-18T09:10:00.229Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*CcJg7ZbMrSErS5iiepFuRQ.jpeg" /><figcaption>Image generated using Microsoft Designer with the prompt “time turner control over time”</figcaption></figure><h3>Introduction</h3><p>Recently I was working with an <a href="https://github.com/typelevel/fs2">FS2</a> stream and wanted to write some unit tests to ensure my events were being emitted at the expected rate. I also wanted these tests to be deterministic and fast. Since FS2 is built on top of <a href="https://github.com/typelevel/cats-effect">Cats Effect</a>, I figured I could use the recently released TestControl feature to do this. This is exactly what I’ll be demonstrating in this blogpost. It’s not particularly complicated but since it took me a little time to understand, I figured it deserved a blogpost.</p><p>Some quick notes before we get started:</p><ul><li>The solution I will be sharing in this blogpost is largely inspired by this <a href="https://discord.com/channels/632277896739946517/632310980449402880/947538194356903956">comment</a> from SystemFW (ps: I highly recommend their <a href="https://systemfw.org/">blog</a>!) in the FS2 discord channel.</li><li>Also, this article assumes readers already have some familiarity with Cats Effect and FS2.</li><li>Lastly, if you’re looking to follow along, you can find all the code we’ll be using in this <a href="https://github.com/fqaiser94/fs2-plus-test-control">GitHub repo</a>.</li></ul><h3>Non-deterministic, Inconsistent, and Slow Tests</h3><p>Let’s assume we have the following stream:</p><pre>val helloStream: Stream[IO, String] =<br>    Stream.<em>constant</em>(&quot;hello&quot;).covary[IO].metered(5.second).take(2)</pre><p>This code describes a stream that will output “hello” every 5 seconds, for a total of two times before terminating. To make sure this stream behaves as we expect, we’ll want to write a test for it.</p><p>To that end, we’ll first try to write a general assertion function which will take in as inputs the Stream[IO, A] that we want to test and our expectation Vector[(FiniteDuration, A)] of what elements should be returned by the stream and at what time. If the results of running the stream match our expectations, the function will return Unit, otherwise it will raise an exception. A first and naive attempt at writing this function might look something like this:</p><pre>def assertStreamOutputsWithTime[A](<br>  stream: Stream[IO, A],<br>  expected: Vector[(FiniteDuration, A)]<br>): IO[Unit] = {<br>  val streamWithTime: Stream[IO, (FiniteDuration, A)] =<br>    Stream.<em>eval</em>(IO.<em>monotonic</em>).flatMap { t0 =&gt;<br>      stream.evalMap(IO.<em>monotonic</em>.map(t1 =&gt; t1 - t0).tupleRight)<br>    }<br><br>  val ioProgram: IO[Vector[(FiniteDuration, A)]] =<br>    streamWithTime.compile.toVector<br><br>  ioProgram.assertEquals(expected)<br>}</pre><p>It’s a fairly simple function but let’s break it down bit by bit:</p><ul><li>First, we create an intermediate stream streamWithTime, which simply transforms every element of stream so that it’s tupled with the time since the start of the stream (t1 — t0).</li><li>We then compile the stream down into an ioProgram of type IO[Vector[(FiniteDuration, A)]].</li><li>Finally we assert that ioProgram matches our expected .</li></ul><p>Using this assertion function, testing our stream becomes a piece of cake. The following test is checking that our stream returns one “hello” after exactly 5 seconds and another “hello” after exactly 10 seconds:</p><pre>test(&quot;return hello every 5 seconds for 2 iterations&quot;) {<br>  val helloStream: Stream[IO, String] =<br>    Stream.<em>constant</em>(&quot;hello&quot;).covary[IO].metered(5.second).take(2)<br><br>  val expected = <em>Vector</em>(<br>    5.second -&gt; &quot;hello&quot;,<br>    10.second -&gt; &quot;hello&quot;<br>  )<br><br>  assertStreamOutputsWithTime(helloStream, expected)<br>}</pre><p>Now, if we run this test, we will likely observe three things:</p><ul><li>The test fails. Our events are being emitted ever-so-slightly later than we expect. Here are the results for one test run:</li></ul><pre>Expected :Vector((5 seconds,hello), (10 seconds,hello))<br>Actual   :Vector((5285798458 nanoseconds,hello), (10265032994 nanoseconds,hello))</pre><ul><li>The time at which our events are being emitted changes on each run. Here’s another failed test run:</li></ul><pre>Expected :Vector((5 seconds,hello), (10 seconds,hello))<br>Actual   :Vector((5357956494 nanoseconds,hello), (10327396702 nanoseconds,hello))</pre><ul><li>The test takes a long time to run. This might not seem surprising since our helloStream program itself only terminates after 10 seconds but it’s not ideal for a unit test to take this much time.</li></ul><p>So what’s going on? First things first, there is nothing wrong with our helloStream program, it actually should just work. The problem is with the way we’re testing. Time is an extremely difficult thing to measure precisely and despite how fast modern day computers are, it still takes some non-negligible amount of time for a computer to do things. As a result, we see that our events are being emitted a fraction of a second later than when we expect them to be.</p><p>To work around these problems, we could add some tolerance to our tests (e.g. by rounding to the nearest second) and make the metered rate in our helloStream configurable (so we could set it to something low like 1.second during testing). However, these kind of changes are fairly invasive, in the sense that they complicate our program and test code unnecessarily and distract from the core focus. And even with these changes, your tests might still be a bit flaky. How do we solve this problem then?</p><h3>TestControl</h3><p>The solution is to use TestControl. You can read about TestControl in detail in the <a href="https://typelevel.org/cats-effect/docs/core/test-runtime">Cats Effect docs</a> but to summarize, TestControl is a mock runtime for Cats Effect IO which fully implements IO’s functionality, including fibers, asynchronous callbacks, and most importantly for us, <strong>time support</strong>. In particular, where TestControl differs significantly from the default IORuntime (which is what we’ve been using so far) is:</p><blockquote>… within a TestControl universe, IO’s notion of time is artificially controlled and limited to only what the external controller dictates it to be. All three time functions — realTime, monotonic, and sleep — behave consistently within this control system. In other words, if you sleep for 256.millis and measure the current time before and after, you will find the latter measurement will be at least 256.millis beyond the former. The only caveat here is that TestControl cannot simulate the natural passage of time which occurs due to CPU cycles spent on calculations. From the perspective of a TestControl universe, all computation, all side-effects (including things like disk or network), all memory access, all everything except for sleep is instantaneous and does not cause time to advance.</blockquote><blockquote>- <a href="https://typelevel.org/cats-effect/docs/core/test-runtime">Cats Effect documentation</a></blockquote><p>This is all great news for testing because this means we will not only get deterministic and consistent results, but also fast results.</p><p>So how do we actually use this mock runtime? All we need to do is make one small change to our helper function:</p><pre>def assertStreamOutputsWithTime[A](<br>    stream: Stream[IO, A],<br>    expected: Vector[(FiniteDuration, A)]<br>): IO[Unit] = {<br>  val streamWithTime: Stream[IO, (FiniteDuration, A)] =<br>    Stream.<em>eval</em>(IO.<em>monotonic</em>).flatMap { t0 =&gt;<br>      stream.evalMap(IO.<em>monotonic</em>.map(t1 =&gt; t1 - t0).tupleRight)<br>    }<br><br>  val ioProgram: IO[Vector[(FiniteDuration, A)]] =<br>    streamWithTime.compile.toVector<br><br>  TestControl.<em>executeEmbed</em>(ioProgram).assertEquals(expected)<br>}</pre><p>The only thing that’s changed here is the second-last line where, instead of running the ioProgram using the default IORuntime, we are now using the TestControl.executeEmbed method to run it with the mock runtime.</p><p>We can leave the rest of our code and the test itself unchanged:</p><pre>test(&quot;return hello every 5 seconds for 2 iterations&quot;) {<br>  val helloStream: Stream[IO, String] =<br>    Stream.<em>constant</em>(&quot;hello&quot;).covary[IO].metered(5.second).take(2)<br><br>  val expected = <em>Vector</em>(<br>    5.second -&gt; &quot;hello&quot;,<br>    10.second -&gt; &quot;hello&quot;<br>  )<br><br>  assertStreamOutputsWithTime(helloStream, expected)<br>}</pre><p>And now, if we were to run our test again, you’ll see the test will pass deterministically, consistently, and almost instantaneously, solving all of our problems!</p><h3>Parting thoughts</h3><p>One great piece of advice I got when I was struggling to use TestControl was to just write tests as if you have only the default IORuntime available, and only after you’ve done that, switch to the mock runtime using the TestControl.executeEmbed method just to make the tests deterministic. This is pretty much the same approach we used in this blogpost. And that’s pretty much all I wanted to share in this article.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=92cec1fac217" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Manipulating Nested Data Just Got Easier in Apache Spark 3.1.1]]></title>
            <link>https://medium.com/@fqaiser94/manipulating-nested-data-just-got-easier-in-apache-spark-3-1-1-f88bc9003827?source=rss-ac4d9cb6496a------2</link>
            <guid isPermaLink="false">https://medium.com/p/f88bc9003827</guid>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[apache-spark]]></category>
            <category><![CDATA[spark]]></category>
            <category><![CDATA[big-data]]></category>
            <dc:creator><![CDATA[Farooq Qaiser]]></dc:creator>
            <pubDate>Mon, 08 Mar 2021 12:15:34 GMT</pubDate>
            <atom:updated>2021-03-10T00:39:42.784Z</atom:updated>
            <content:encoded><![CDATA[<p>In previous versions of Apache Spark, adding or dropping deeply nested fields could be a challenging programming exercise. In this article, we’ll be demonstrating how you can use the newly added <a href="https://spark.apache.org/docs/3.1.1/api/scala/org/apache/spark/sql/Column.html#withField(fieldName:String,col:org.apache.spark.sql.Column):org.apache.spark.sql.Column">Column.withField</a> and <a href="https://spark.apache.org/docs/3.1.1/api/scala/org/apache/spark/sql/Column.html#dropFields(fieldNames:String*):org.apache.spark.sql.Column">Column.dropFields</a> APIs to perform these kinds of operations trivially. In addition, we’ll also be sharing some of the thought-process that went into the design of these new APIs as well as taking a quick peek at how they work under-the-hood<strong>.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*2pVNQGvUeCIRKuc-BDaLeQ.png" /><figcaption>Spark 3.1.1 Scala 2.12.10</figcaption></figure><h3>Things to note</h3><p>As a disclaimer of sorts, I contributed most of the code for these new APIs to the Apache Spark project (with significant help from the open-source community!) so this article will likely be biased towards my own views and you should note that all opinions expressed herein are purely my own.</p><p>The other thing to note is that although we’ll be using Scala throughout this article, the equivalent code in Python or R shouldn’t look much different. If you’re looking to follow along in your REPL, you can find all the code we’ll be using in this <a href="https://gist.github.com/fqaiser94/fe5e1b06f79ee6ef4b747ec9479ab25a">gist</a>.</p><p>With those out of the way, let’s dive right in.</p><h3>Sample Data</h3><p>First, let’s create a DataFrame with some sample nested data to work with:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZOMuUzApfBICsY6PLxVc3w.png" /><figcaption>Generating a DataFrame with a StructType column.</figcaption></figure><p>To keep things simple, we’ve created our DataFrame with only one row containing actual data for a fictional person named James. We also have another row to represent missing data (don’t worry about this too much for now, it will soon become clear why we need this). Our DataFrame has one top-level field (or column if you prefer) named person and the rest of the fields are all <strong>nested</strong> inside this. If you care about terminology, we say the name field is nested one level deep whereas the city and income fields are nested two levels deep.</p><p>Now, let’s say we want to add a new nested age field inside of person. Before we demonstrate how easy it is to do this in the latest version of Apache Spark, it’s helpful to see how we would have done this in previous versions of Spark and understand why it could be challenging.</p><h3>Adding a new nested field prior to Apache Spark 3.1.1</h3><p>In previous versions of Spark, the only built-in function you had at your disposal for modifying nested fields was the functions.struct method. Using this method, we can add a new nested age field like so:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*b5uhOKu9p4nk79hLwejEvQ.png" /><figcaption>Adding a new nested field using the functions.struct API.</figcaption></figure><p>As you can see, we didn’t need to write much code for this simple exercise, which is good news. Unfortunately, while the result looks reasonable for the first row of our DataFrame, the second row probably isn’t what we had intended. Our code has expanded what was originally a null value into a struct consisting of null values for each of the pre-existing fields in the schema. In general, we would probably want to preserve the null values as just that. This is easily remedied with a little more code:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*zKG6SCiOiJyVMSY91iX7zg.png" /><figcaption>Adding a new nested field whilst preserving null values using the functions.struct API.</figcaption></figure><p>That’s better, now our null values remain as null values. Looking more closely at our schema though, it would probably make more sense if this new age field was nested inside person.details, so let’s try to adapt our code to do that next:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*k8wN93Gy0BqO_cGGTVhQPw.png" /><figcaption>Adding a deeply nested field using the functions.struct API.</figcaption></figure><p>Yikes, that’s a lot of code just to add one nested field! We’re starting to see the problem with using the functions.struct API for these kinds of operations. Specifically, the more deeply nested a field is, and the greater the number of fields at each level of nesting, the more code we have to write to modify it. As you can imagine, this quickly becomes tedious to write and hard to read.</p><p>Now, if you’re a competent programmer and willing to leave the comforts of the Spark-SQL DSL behind, you can reduce the amount of code you have to write, for example by referencing the DataFrame’s schema to recursively rebuild the struct with your new field inserted in. In fact, you can find a few different implementations of this idea floating around on StackOverflow (albeit of varying quality).</p><p>Unfortunately, for many Spark users this would be a challenging exercise. Think of your average Analyst or Product Manager who are just looking to query some data quickly and don’t necessarily use Spark on a daily basis. It’s not uncommon to see these kind of users reaching for suboptimal but perhaps easier to write alternatives such as using UDFs or dropping down to the RDD level. In the worst case scenario, these users may even demand data be stored only with flattened schemas purely for their convenience.</p><p>Now that we understand the limitations of the functions.struct API and the problems it can potentially lead to, let’s see how Apache Spark 3.1.1 fixes this issue.</p><h3>Enter Apache Spark 3.1.1</h3><p>As mentioned previously, Spark 3.1.1 introduced a couple of new methods on the Column class to make working with nested data easier. To demonstrate how easy it is to use these new methods, we’ll go through the same exercises as before, starting with adding an age field to the person struct:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-nbGxy1hP9rWR-aOYGVa0Q.png" /><figcaption>Adding a nested field with the Column.withField API.</figcaption></figure><p>Here we’re using our first new API; Column.withField. We can call the withField method on any StructType Column ($&quot;person&quot; in our case) and it takes exactly two arguments:</p><ol><li>fieldName: String <br>This is the name of the field we want to add (&quot;age&quot; in our case)</li><li>col: Column <br>This is the value we want to assign to the new field (lit(40) in our case)</li></ol><p>and it returns another StructType Column with the new field added to it. That’s all there is to it. And notice, with this API we get sane null handling behaviour out-of-the-box.</p><p>Now let’s try something more challenging; let’s try adding the age field so that it’s nested inside person.details:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ojzGHXh1E7a8wEpBCsirdw.png" /><figcaption>Adding a deeply nested field with the Column.withField API.</figcaption></figure><p>The interesting thing to note here is that the code is almost the same as in the previous image. The only thing we’ve had to change is instead of passing in &quot;age&quot; as the fieldName argument, we’re now passing in &quot;details.age&quot;. The reason this works is because the Column.withField API supports Spark’s “dot notation” feature which allows you to describe the path Spark should traverse to reach your target nested field. We’re able to use this naturally in the Column.withField API to easily modify deeply nested chains of structs.</p><p>In contrast, recall that when we were using the functions.struct method to achieve the same result, we were forced to rebuild the chain of structs in their entirety and this typically requires several lines of code (if you care about readability anyway). This is one of the main drawbacks the new API addresses. If you’ve ever had to modify deeply nested fields in the past, you’ll know this is going to save you a lot of code!</p><p>Before we move on to the remaining use-cases, let’s take a brief detour to try to understand what Spark is doing under-the-hood to execute our query.</p><h3>Detour: What is Spark really doing?</h3><p>As with any new technology, it’s always helpful to understand what is going on under-the-hood to make sure there aren’t edge cases you need to be wary of. Let’s take a look at the physical plan that Spark is generating for our previous query to get a high-level understanding of what’s happening here:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*HmPWxawR66vPP_gAkHpa7Q.png" /><figcaption>Spark plan for adding a deeply nested field with the Column.withField API.</figcaption></figure><p>As you can see, Spark is ultimately translating our Column.withField method call into a bunch of nested if-not_null-named_struct-else-null operations and, if you look closely, you’ll see it’s very similar to what we were doing before with the functions.struct method, except we were writing that out manually. Spark can obviously do this automatically for us because it knows the schema structure of our Dataset. At the end of the day, this is a reminder that however magical Spark may appear to be, it’s really just a clever program.</p><p>That’s the end of our brief detour. The rest of this article will focus on demonstrating how you can easily perform other kinds of common operations involving nested fields.</p><h3>Replacing nested fields</h3><p>Now let’s say there’s a mistake in our data and James is actually located in New York. How can we fix this?</p><p>Fortunately, the Column.withField method allows us to both add new fields <strong>or</strong> replace existing fields with the same name in our target struct. This is basically the same semantics as you get with the Dataset.withColumn method. In code, this looks like:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*PiJV4fhNBwumQNb9ee3IqQ.png" /><figcaption>Replacing a deeply nested field with the Column.withField API.</figcaption></figure><p>That about covers everything you need to know about the new Column.withField API.</p><h3>Dropping nested fields</h3><p>Now, what if instead of replacing the contents of the city field, we just want to drop this unreliable field entirely? For this, we can use the new Column.dropFields method:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*6JLZ89X75XXMXjYhlDvjiQ.png" /><figcaption>Dropping a deeply nested field with the Column.withField API.</figcaption></figure><p>We can call the dropFields method on any StructType column ($&quot;person&quot; in our case) and as it’s arguments, it will take one or more string values representing the names of the fields we want to drop (only &quot;details.city&quot; in our case), ultimately returning a new Column with only the specified fields removed. Much like the Column.withField method, we get sane null handling behaviour out-of-the-box and the ability to refer to deeply nested fields directly via dot notation.</p><p>Another minor benefit of using this new API is that it’s clear what fields are being dropped (provided they existed in the first place). With the functions.struct API, it’s not always clear which fields are being dropped (if any) as dropping is done by omitting fields and unless you know what the schema was prior to the functions.struct method call, you generally can’t tell from just looking at the code if any fields are being dropped.</p><p>Now what if you want to add and drop fields at the same time?</p><h3>Chaining withField and dropFields method calls</h3><p>Since both withField and dropFields return a new Column, we can chain these method calls one after another in any order and as many times as we want, for example:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xpbzIrPLSqTbybJM94BsUA.png" /><figcaption>Chaining consecutive Column.withField and Column.dropFields methods.</figcaption></figure><p>As you can see here, we’re adding two new nested fields (age and gender) and also dropping the nested city field. The nice thing about being able to chain these methods like this is it enables end-users to describe a sequence of Column level “transformations” to apply in a single flow. This is not only easier to write but also easier to read and understand.</p><h3>Bonus: Modifying Nested Fields in an Array of Struct</h3><p>Last but not least, let’s see how we can combine these new methods with the existing <a href="https://spark.apache.org/docs/3.1.1/api/scala/org/apache/spark/sql/functions$.html#transform(column:org.apache.spark.sql.Column,f:org.apache.spark.sql.Column=%3Eorg.apache.spark.sql.Column):org.apache.spark.sql.Column">functions.transform</a> method to manipulate structs nested inside an array. This is a common data science use-case (and in fact, the original problem that motivated me to write these new methods). We’ll need slightly different data to demonstrate this though:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*yV72FmLlBxmIOYE7a9KREw.png" /><figcaption>Generating an array of structs column.</figcaption></figure><p>All we’ve done here is taken what was previously our top-level (person) struct and nested it inside an array. And now, for the last time, let’s try to add a new field age to each of the structs nested inside the people array:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*B1_8Z5MtucylX7zWxVwY7g.png" /><figcaption>Adding a deeply nested field to structs nested inside an array.</figcaption></figure><p>Ta-da! Okay, the novelty of being able to add deeply nested fields easily is probably wearing off by now but that’s exactly how it should be. And as you can see, these new methods are fully compatible with all of the other existing functions Spark provides which means we can combine them in any way we want to get almost any desired result. This isn’t anything special; it’s just a natural consequence of having methods that both operate on and return Column objects.</p><h3>Conclusion</h3><p>To recap, we first looked at how we would traditionally add or drop nested fields in Spark and showed how this was painful to express using just the functions.struct API. We then demonstrated how we could dramatically simplify our code by using the new Column.withField and Column.dropFields APIs across a variety of different common use-cases.</p><p>One thing to note is that as awesome as these new APIs are, they aren’t intended to replace the functions.struct method, rather they fill in a previously missing gap. It’s easier to understand if you compare each of these APIs with their natural Dataset equivalents:</p><pre>+--------------------+-------------------+<br>|      Dataset       | StructType Column |<br>+--------------------+-------------------+<br>| Dataset.select     | functions.struct  |<br>| Dataset.withColumn | Column.withField  |<br>| Dataset.drop       | Column.dropFields |<br>+--------------------+-------------------+</pre><p>Imagine a world where you didn’t have the Dataset.withColumn or Dataset.drop methods. This would mean any time you wanted to add or drop a top-level column, you would be forced to use the Dataset.select API. That would be a relatively painful experience right? This was part of the problem we faced when all we had was the functions.struct method for manipulating nested fields. We were missing convenient, purpose-built APIs for performing these relatively common operations.</p><p>That’s all I wanted to share in this article. I hope these new APIs will make your life easier as a Spark developer going forwards. Last but not least, I wanted to give a shout-out to the awesome committers in the open-source Apache Spark community who patiently worked with me over several months to optimize and generally improve the design of these new APIs into what you see today. And this is only one of the many cool new features introduced in Apache Spark 3.1.1 so if you haven’t already, go check it out today!</p><h3>PS: What if you’re using an older version of Spark?</h3><ol><li>Upgrade to Spark 3.1.1</li><li>Assuming that’s not possible, you can check out the <a href="https://github.com/fqaiser94/mse">Make Structs Easy</a> library. It offers similar functionality but because it is essentially the proof-of-concept for the code I submitted to the Apache Spark project, it is lacking some features (less optimized, doesn’t support dot notation for referring to deeply nested fields, and no R support). So you can use it if you’re on an older version of Spark but really, you should just upgrade to Spark 3.1.1</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f88bc9003827" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>