One of the handiest intellectual tools I have built for myself in designing distributed systems is a two out of three conjecture on stream processors in analogy with the CAP theorem for distributed systems.
Probably the most famous theorem in distributed systems is the CAP theorem. It says that if I have a value that I can store and retrieve in my system, my system has at most two of the three properties consistency, availability, and partition tolerance.
Partition tolerance means that if the communication between parts of my system is cut in such a way that they are split into two halves, the system continues to function.
Availability means that I continue to be able to read and write the value at all times.
Consistency means that no matter how I read the value from different parts of the system at a given point in time, I get the same answer.
Making this all formal requires a bit more machinery and makes this more precise, but the intuition is straightforward. Imagine I have two computers running a distributed database. If I cut the network connection between them, then either I can still read and write to each of them but their values can go out of sync since there is no means of communicating the change (which mean I have chosen partition tolerant and available), or I block writes until the network connection is restored (which means I have chosen partition tolerant and consistent). If I am building a computer with many processors, where the different processors will not be partitioned unless something catastrophic happens to the machine, then I can drop partition tolerance and choose consistent and available.
A while back I was designing a system—I don’t remember what I was designing, but it was probably something banal like logging—and I realized that there was a similar description to be had of stream processors.
In this case, instead of talking about what happens when we cut communication between parts of a distributed system, we look at what happens when we overload the stream processing system and it cannot keep up with the data arriving.
The three properties are:
1. If we send a sequence of data through the stream processor when it's overloaded and when it's not overloaded, does the stream processor produce the same state when the overload is finished?2. Can the programs that are writing to the stream processor continue sending data even when the stream processor is overloaded, or are they blocked?3. and, does the stream processor ever replay data to process it again, or does it only make a single pass forward in time?The first property, that we end up in the same state in the end whether the stream processor is overloaded or not, I call "faithfulness." The name comes from representation of groups in mathematics where a faithful representation of a group is mapping of the group into some other space that preserves all of the group's structure. In this case, the mapping of the input stream through any state of the processor produces a the same result.
The second property, that writers to the stream can continue to write no matter the state of the processor, I call liveness, which is probably what anyone else with a background in distributed systems would call it.
The last one, that the stream processor works in one direction along the stream without backtracking or replaying earlier data, is an example of naming being hard. I originally called it "progressive," with the mental image of the processor only progressing in one direction along the stream. But with faithful and live as the other two properties, this becomes the FLP conjecture. Sadly, the FLP conjecture is already the name of another seminal two-out-of-three theorem that applies to distributed consensus.
The next most obvious name to me was "unidirectional." That makes this the FLU conjecture. I spent enough years working on infectious diseases that that feels a little close to home. Plus I feel like the FLU conjecture should be, "Patients demanding antibiotics are more likely to have a viral infection than bacterial" or something equally cynical.
If I tap into English's German roots and go straight for "one directional" I get an O, and the FLO (or "flow") conjecture seems pretty apropos for stream processing.
So much for naming. Is this likely true? Let's start by considering each choice of two properties that we can make.
First, what if we choose faithful and live? We can overload our stream processor to the point where it can't do anything with data sent to it besides dropping it. Fill its RAM. Fill its disk. Push its CPUs to 100% utilization. And yet, at the end, we have to have the same result as if it were not overloaded.
For that to happen, it has to have another opportunity to process the dropped events later on, so the writers must resend them. The stream processor has to backtrack and replay events, so it cannot be one directional.
Next, what if we choose faithful and one directional? We're not allowing backtracking and replaying in this case, so when the stream processor is completely overloaded we can't drop data. The only other option is to tell programs writing to it to wait. They cannot write until the system is no longer overloaded. So it is not live.
Finally, if we choose live and one directional, our stream processor has to always accept writes and cannot backtrack and replay. If it has nowhere to store that data and no capacity to process them now, it can only drop them. For any given stream and stream processor we can find some schedule of overload where data critical to calculating the final output is lost to this, so such a system cannot be faithful.
In practice, we use all three variations daily.
A faithful and live system? That's TCP. One side of the connection keeps sending packets. If the network or receiver are overloaded, they send messages back saying what needs to be resent.
A faithful and progressive system? Those are shell pipelines. If you pipe the output of one program to another in bash, the first program's output is written to a buffer. When that buffer is full, the first program is blocked until the second program runs and drains that buffer.
A live and one directional system? That's UDP. One side of the connection sends datagrams. They may or may not get through, but you can always send them.
One of the other common distinctions that people make about stream handling is at-most-once delivery versus at-least-once delivery. The FLP conjecture that I mentioned before tells us that we can't have exactly once delivery, so when we design a stream processing system we must choose whether we may lose data in the event of system problems or whether we may have duplicate data.
How does this interact with the FLO conjecture?
Recall that faithful and live systems have to drop events to stay live, but must have those events resent in order to be faithful, so they must clearly have at-least-once delivery.
Live and one directional systems, on the other hand, drop events that arrive when they are overloaded to stay live, and never see them again to stay one directional, so they must have at-most-once delivery?
What about faithful and one directional systems? This varies a bit with the implementation.
When the writer communicates with the stream processor via message passing, such as over the network, the writer sends a message with data, and waits for the stream processor's response. If it gets, "Not now, try again later," it does so, then tries sending it again. This is clearly at-least-once delivery.
If the writer communicates with the stream processor via shared memory, such as writing to and reading from a shared buffer, then typically something else like the kernel is handling the scheduling of both pieces. When the writer tries to write to a full buffer, the kernel ceases to schedule it until the buffer has been drained and can accept writes again. It's possible that something happens to the writer before it's scheduled again, and its write may be lost. So with shared memory, faithful and one directional systems are at-most-once delivery.
None of this is particularly earth shattering, but I have found picking which two properties I need of faithful, live, and one directional I need to be a useful first approximation when I start thinking about shipping data from one part of a system to another.