When you inject events into the cloud, do you care whether they come out in the same order they went in? If you do, you’ll be asking for “FIFO” (rhymes with “Fly, foe!”) (stands for “First In First Out”). Some software has it, some doesn’t.

[This is part of the Event Facets series.]

If you think about it carefully, FIFO is only meaningful when you have a single-threaded sender and a single-threaded receiver; with more than one, who gets to say which message was sent (or received) first?

Caravan in the desert, Morocco.

Real-world FIFO semantics.
Credit: “Caravan in the desert. Morocco, Sahara.”
©Sergey Pesterev/Wikimedia Commons/CC BY-SA 4.0

In practice, this means that a FIFO event stream can really only run as fast a single computer can send messages. Assuming there’s any real business significance to the messages, this is pretty slow: hundreds of transactions/second is regarded as extremely fast for a FIFO sequence.

It turns out that in a high proportion of cases, what you have is a huge fast data stream that’s partitioned into many sub-streams, and the FIFO operates at the sub-stream level. Think of the clickstream coming off a big Web site. You might care about the order of events that are part of an individual session (there could be thousands or millions of sessions), but not whether one session’s events are before or after another’s.

This is common enough that you’ll hear people use phrases like “session ordering”.

That’s why I like the picture above. There are actually three strongly-ordered mini-caravans, which could arrive at the oasis in any old order while locally preserving strict within-caravan camel ordering.

If you look at actual real-world software, there’s usually good support for this big-river-of-ordered-sessions model. For example, both Kinesis and Kafka have session selection arguments and call them Partition Keys. Both expose their shards, which are selected by the partition keys and where the FIFO semantics apply. This makes them shine for huge-scale session-oriented pub/sub streaming.

SQS FIFO calls its session identifier Message Group IDs and hides the internal shards.

I always want FIFO, right? · Certainly, if you’re applying transactions to a bank account. But maybe not; Consider the case of Amazon.com. Every time you press “buy”, the Web site generates a message saying what you bought, how you paid for it, where, to ship it, and so on, and drops that into the cloud, where it’ll eventually be picked up by the systems that do acquisition and packaging and shipping and accounting and tax and compliance and so on. But if you think of it, since each of those orders is independent of all the others, the order doesn’t matter that much.

2019年のジャパンカップ スタート後の先行争い

Not FIFO.
Credit: “2019年のジャパンカップ スタート後の先行争い”,
by nakashi.

FIFO is hard · If your app is like Amazon.com, you should definitely use a service that doesn’t offer FIFO, because it’ll be cheaper and more elastic. It turns out that FIFO isn’t free — it’s not even cheap —  because it’s hard to build and operate.

It’s not hard to understand why. A typical big Web service is commonly sharded, which is to say there’s a front-end fleet of hosts handling a flow of requests from many sources, which it deals out to more hosts in the back-end fleet to process. Sharding lets you handle really any level of traffic.

The way it typically works is that incoming requests end up at some sort of “load balancer” to deal the traffic out. Obviously this means you can’t maintain global FIFO ordering; that’s sort of OK for the reasons described just above. If you want to maintain the more typical and useful “session FIFO” semantics, you need to route the messages associated with each session to the same shard. This practice is called “affinity” and, as I described here, it’s difficult.


author · Dad · software · colophon · rights

March 07, 2020
· Technology (85 fragments)
· · Software (70 fragments)
· · · Eventing (5 more)

By

I am an employee of Amazon.com, but the opinions expressed here are my own, and no other party necessarily agrees with them.

A full disclosure of my professional interests is on the author page.