Lossy Systems
There’s a pattern in software engineering which I call the ’lossy system’. A ’lossy’ system is any system designed to return only incomplete answers, either to make a problem at all tractable, or just to keep costs down.
Data compression is the easiest example. If you’re fine with storing “imperfect” images, you use JPEG. JPEG will throw away some of the data inside of your image, in return for making the image smaller.
The lines are blurry: Is reaching for the most common image format a “lossy system pattern”? No, not really. Yes, lossiness is built into JPEGs, but reaching for them is just the industry standard.
It becomes a pattern when you make a deliberate decision to drop data that you were previously processing, to approximate data, to compress, or to serve stale data, etc.
Big fucking whoop, who cares, etc., why is any of this interesting?
Sufficiently large systems inevitably become lossy. It’s what lets them scale, it’s also what makes big tech so complex, and explains why YouTube or Twitter’s algorithm only serves you hot garbage (maybe).
Additionally, your system is already lossy. Any distributed system has to account for data being dropped, components breaking, etc. Some systems are designed around this and resilient, other systems just break entirely.
In the following, let’s go over a short list of examples, each of which illustrates a different instance of what lossy systems look like.
This post is not going to be deeply technical, and it’s not a complete list. It’s just examples. Concepts. To get the basic shape. I may come back to it if I ever figure out a clean taxonomy.
Examples
Sampling
Simple. Instead of gathering “all” data, you just sample say, 1% of it. This is such a fundamental idea that it’s used everywhere, across all industries.
Instead of putting every single widget through quality control, only send 0.1%. Boom. You cut 99.9% of the cost required to process items.
Better yet, if you realize that this is where your costs are, you can easily just cut the sampling rate even further.
The tradeoff, of course, is that if your data is highly varied, you might care about single specific data points which did not get sampled. You lose certainty (this will be a common thread, for obvious reasons).
Approximate Data Structures
Your server handles 10,000 queries per second. You want to track how many distinct1 active2 users are using your service at any given moment in time.
The problem: You need to store each user’s identifier, so you can check if you’ve seen them before. This scales linearly in the number of active users you have, i.e. it may cost a lot of memory for just a single observability metric you want to track. Expensive!
Question: What if you could store the approximate user count, in a way that doesn’t cost a lot of memory?
Enter HyperLogLog. It works by noticing that if I give you a random number from 0 to 999,999 then the odds of seeing a number that ends in 0 are 10%. The odds of seeing a multiple of a hundred (0, 100, 200, … 900) are 1%. Etc.
Therefore, by mapping our users uniformly onto a slice of integers and keeping track of the most rare numbers we see, we get an approximate user count.
“The HyperLogLog algorithm is able to estimate cardinalities of > 10^9 with a typical accuracy (standard error) of 2%, using 1.5 kB of memory.” (Wikipedia)
There’s a whole bunch of fancy probabilistic data structures out there, see e.g. this post for a list of examples.
Dropping the Tail
You open up Google, enter a query. The Google search backend fans out, meaning that it sends your request to say, 100 different servers, each of which handles a “chunk” of the work required to answer your query.
If Google waits for all of the servers to complete their work before returning an answer, then you have to wait for the slowest server.
This is bad even under ideal circumstances: Imagine we have one hundred worker servers, each of which has a 1% chance of being slow. We are going to hit a slow server 63% of the time!
Instead, you follow cancellation policies which allow dropping the slowest or least important work:
- Deadlines: Drop everything that takes longer than one second.
- After enough of the servers returned, cancel the remaining ones. (Could be 90%, could be “enough to fill the first page of Google Search”).
- Deadlines with partial results: Each server is responsible for returning the ‘best currently known’ result after a deadline is up.
- Evaluate returned results by quality, then cancel everything once you have enough high-quality results.
The obvious tradeoff: The user has no guarantee you actually returned the data they were looking for.
Trimming with Cheaper Substitutes
Open any feedscroller app. Xitter, YouTube, TikTok, etc. Personalization is the name of the game, whatever you see at the top of the page has gone through some sort of ranking process that tries to maximize your engagement.
Imagine for a second, how long it would take to rank every single post on Twitter according to your preferences. Now imagine having to do this every single time someone refreshes the page, and having to do it for all users across the platform.
Expensive.
Instead, you put a cheap selection tool in front of the neural net. This tool grabs a pool of potential candidates (say, ~1,500 tweets, according to Twitter), which are then handed off to the (more expensive) neural network ranking them according to what it knows about your behavior.
If you think about this, this is aesthetically unsatisfying: You spent a long time building an amazing neural network to get down preferences. Woo!
And then, the final algorithm is still a Frankensteinian abomination, a complex multi-stage pipeline where every piece of content has to pass multiple stages, half of which may be ineffective or pure cost optimizations.
Is this an example of a lossy system?
Yes, of course. Running the algorithm on all available data is expensive, so you use heuristics to drop some of it, and then only process what’s left.
Caching / Staleness
Arguably the most fundamental pattern. Why re-compute everything from scratch every time you need the data?
Just store it somewhere, lmao.
Rollouts? Data consistency? Cache invalidation? Sharding and load-balancing? Consistent hashing?
How hard can it be?
This is everywhere. Recomputing everything on request is expensive, and takes a long time. If you believe that users are not going to care if say, their search results are 30 minutes out of date, then it’s fine for search data to be outdated by 30 minutes.
This is a pattern of a lossy system, in the sense that there is a deliberate decision to not gather data that you could have gathered.
It sounds laughably simple, but requires you to think about difficult questions, e.g.:
- Where does the stored data live? Is it on disk or in RAM?
- Who is responsible for managing the stored data? Who updates it to ensure it doesn’t get too stale?
- What happens if it does get stale? How are we going to notice? Is the system going to serve stale data, or will it just go back to recomputing everything on demand?
- Does it get updated on-demand, or is there a regularly running (say, daily) job that refreshes the data?
- Can it be updated on a chunk-by-chunk or item-by-item basis, or do you need to update the whole thing at once?
- Does the stored data have a specific layout or schema associated with it? If yes, what happens if the schema changes? Does the data need to be refreshed immediately? Is there a risk that loading data with the old schema may break something?
Depending on your situation, these questions will have vastly different answers.
Critically, it’s important to understand that “serving stale data” often involves adding a new node to your distributed system. It’s another link, another component that can (and will) break, and this will cause exciting new (and hard to detect) failure modes you never even thought possible.
No, really, why does it matter?
You live in a society governed by technology.
A small script on your computer behaves fundamentally differently from the mess that’s a big tech corporate technology microservice stack.
Understanding a few principles of how large-scale systems work may help you understand the technology that surrounds you.
We can couple our examples to obtain a worst possible outcome:
You urgently need to go somewhere. You reach for Google maps and enter the information you received. Now, imagine that:
- For whatever reason, the worker process that would’ve found the place you are looking for never returned. Therefore, you cannot find the place on Maps.
- When you try to repeat the search, the previous result was cached. So instead of finding it on the second search, it keeps telling you that the place doesn’t exist.
- Due to sampling reasons, your complaint / bad experience never even makes it anywhere, it just silently gets dropped.
This is (almost certainly) not how Google Maps actually works, but you can see the issue. Each piece of lossy friction within the system can increase the risk of errors or data loss, and multiple errors can combine into something worse than the sum of their parts.
If you've made it this far, consider signing up for e-mail notifications, following along on Substack, or adding this blog to your RSS reader.