DEV Community: João Godinho

Tail Latency

João Godinho — Mon, 24 Aug 2026 02:20:31 +0000

Overview

This article covers Tail at Scale by Jeffrey Dean and Luiz André Barroso, both contributed to building what we call today modern data centers and framed an important topic and its effects in systems at large scale called Tail Latency (coining the term "tail-tolerant").
Tail Latency is a topic that Google Search and other services take advantage of to avoid latency issues and reach that performance that we observe in our daily life.
We will discuss more than just "What is Tail Latency?", but also:
- What are p50, p99, p99.9, and other percentiles?
- Why both average and median lie?
- What causes tail latency?
- Parallelizing requests across multiple distributed systems using Fan-Out and Fan-In techniques.
- The effects of variability at small and large scale.
- Can we kill variability or do we need to understand how to engineer on top of that fact?
- What is the naive "latency fix" and why it spends unnecessary money, computing power and energy resources?
- How to apply that knowledge in the systems you are building? How to collect metrics, analyze them and take action? (prometheus, grafana, and k6)
- The risks of gathering incorrect data in load tests: Coordinated omission.

What is p50, p99, p99.9, and other percentiles?

Imagine you have a line cut into 100 equal pieces from left to right. The 50th piece represents the p50, also called the median.
The 99th piece is almost the last one closer to the right side.

Now imagine that this line represents requests sorted by their latency, where the leftmost one has the smallest latency and the further right we go, the higher the latency is.
When someone says "The p99 is 1s", it means: "1 of 100 users is facing a response time of 1 second or more."
When someone says "p50 is 100ms", it means: "50 of 100 users are facing a response time under 100ms"

To understand p99.9 we need to cut this line not in 100 pieces, but in 1000 smaller parts. It is the rightmost part, the 999th.
"p99.9 is 10s" = "1 of 1000 users is facing a response time of 10 seconds or more."

Why both Average and Median (p50) lie?

Average gets pulled by higher values, but at scale one slow request barely changes it, since that single value gets diluted across all the fast ones. It seems good for showing us problems, but it actually hides the tail.
Median is completely blind to the tail, we could make the 49% slowest requests take hours and the median would not move.
- p50(1,2,3,500) = (2+3)/2 = 2.5

What is Tail Latency and What Causes it?

What causes Tail Latency? Variability, response times are not constant, they spread out.
What is Tail Latency? The slow end of that spread of response times far above the median. It is a region of the distribution, not a single latency value.
- p99 and p99.9 are the metrics we use to measure the tail, and identify how bad the tail is.

And Why Latency Variability Exists?

Multiple factors, such as:
- Cache miss: forcing a slower path through the disk or doing network calls.
- Shared resources: CPU cores, processor caches, memory bandwidth, network bandwidth...
- Queueing: Requests do not arrive evenly, they come in bursts. If more arrive than the server can process, requests pile up in the queue and wait, which increases the total request time a lot.
- Background maintenance activities: such as cronjobs, log compaction, data reconstruction in distributed file systems, etc...
- Garbage Collector: The runtime of garbage-collected languages (e.g. Java) periodically pauses normal work to reclaim unused memory. Unlucky requests will get frozen for the duration of it.
- Even power limits used in hardware to control temperature of modern CPUs and other components.
- These and much more...

What is Fan-Out and Fan-In?

A technique used to turn a unit of work into multiple parallel units of work (1:M).
It can happen in the same server using different threads.
But in distributed systems it can also mean parallelizing requests across multiple different services and then merging their results into a single response. In this way you are not only limited to a single machine's cores to parallelize tasks, but to multiple nodes.
- The distributed systems concepts are very similar to the fork/join concepts when working with threads in a single machine.
Fan-Out = split a larger task into smaller sub tasks; root server distributes sub tasks to other services
Fan-In = used if you need to wait for all sub tasks to complete before moving to the next processing step; root receives the responses and merges them into a single response.
NO, Fan-In isn't required after Fan-Out!

How Scale Amplifies Variability Effects

If you don't understand the probabilities, I suggest you watch Independent & dependent probability - Khan Academy.

As you can see the effect of variability at scale can be a killer for your services. Imagine if Google hadn't cared about that, would they be that huge, or would customers use other, faster services?

Can we kill variability?

No, eliminating all variability is infeasible, so you build tail-tolerant systems instead. So how to do that?

1. Fix the node first

Before any sophisticated technique we start simple.
Run the server at realtime priority so background daemons cannot preempt it. (OS scheduling)
Dedicate a core to interrupts so network packet interrupts do not keep stealing the application's cores.

2. Within-request techniques

These act inside a single request, in tens of milliseconds, and reuse replicas you already keep for availability.
Hedged requests: if the request to the first replica (that seemed to be the most appropriate) lasts for more than p95, we send a copy to another replica and take whichever replies first cancelling the rest.
- It's especially good because if the first server hit a bad moment (GC pause, etc) the second rescues the application.
- Waiting too short (hedge at p50) = 50% of requests duplicated.
- Waiting too long (hedge at p99.9) = Almost no duplicates, but the response is very slow before help arrives.
- Because of that, the authors of the article "The Tail at Scale" suggest hedging at p95.
Tied requests: Send the request to two servers at once, each tagged with the other's identity. Whichever begins execution first sends a cancel to its twin, so our app rarely pays for double work.

3. Cross-request techniques

These handle coarser problems (load imbalance, or a particularly slow machine) over seconds to minutes.
Micro-partitions: Create many more partitions (data chunks) than machines, so you can move load between machines in small steps instead of moving a whole machine's worth at once. With 20 partitions per machine you shed load in 5% increments and rebalance much faster, since each move copies only a small chunk.
Selective replication: Detect (or predict) the items likely to get hot and make extra copies of just those, so the load balancer can spread that heat without moving whole partitions around.
Latency-induced probation: Watch each machine's latency and temporarily remove one that has turned slow, while still sending test requests to it in the background so you know when it recovers and can bring it back.
- It sounds counterintuitive, why would removing one slow machine help reduce latency and build a tail-tolerant system? Because we fan out and wait for all of them, so the slowest one sets the latency of the whole request. Removing it leaves only the fast ones, and we keep probing the slow one to bring it back once it recovers.

4. Information-retrieval techniques

For search-like systems where a good answer now beats a perfect answer later.
Good-enough responses: Once enough leaf servers have replied, return slightly incomplete results instead of waiting for slower ones.
Canary requests: Send the request to one or two leaves first, and only fan out to the rest if the canary comes back cleanly in a reasonable period of time, protecting against a bad request that could stall thousands of servers.
- "Canary" comes from the idea that miners used a bird to see if the mine had poison gas so if the bird died they could leave safely.
- Same as we do with canary deployment, slowly routing traffic to the server and if it dies we roll back to the stable one.

The naive fix and unnecessary waste of money

High utilization makes tail latency much worse.
- Imagine a supermarket cashier idle, then 3 customers arrive at once and they are served right away, no line forms.
- Now what if the cashier was busy most of the time? Then the same 3 customers at once will wait a long time.
The obvious move is to keep servers 30-40% busy, so there is always slack to handle incoming requests. It works and is pretty expensive as you can imagine.
- Naive approach: Paying for 100 servers to do the work of 40 just to reduce tail latency having 60 servers for latency insurance.
The right approach mentioned in the previous section: techniques to build tail-tolerant systems.
- Hedged requests and tied requests lean on already existent replicas for fault tolerance, not new servers to avoid tail latency.
- Tail-tolerant techniques let us keep the tail low while running servers hot, buying fewer machines.

Measuring the Tail in Real Systems

We could gather latency data using monitoring systems such as Prometheus and an observability system such as Grafana to build charts and dashboards to analyze these data.
We could also implement a load test on our service and analyze the results in charts and dashboards using k6

Now take a look at these K6 load test results: Github - K6 load test POC
Below I'll show only the latency and some percentiles, but k6 provides us much more information.
The overall p99 is 220ms which is good. The warmup pushed p99 above 1s which looks bad, but since it was just the warmup that spike is expected and not a real concern.
One problem of load test tools if misconfigured is Coordinated omission.
Coordinated omission happens when your load tester keeps waiting on a slow request instead of sending the next ones on schedule, so it silently skips the requests that would have been slow too, making your measured p99 look far better than reality.
- Named by Gil Tene on How NOT to Measure Latency (coordinated omission starts around 33:50).

References

Service Levels: Understanding SLIs, SLOs, and SLAs

João Godinho — Fri, 21 Aug 2026 02:02:45 +0000

Overview

This article covers Google Site Reliability Engineering (SRE) book material and Google Cloud material about service levels: SLIs, SLOs, and SLAs.
What are service levels? Their indicators, objectives, agreements and consequences.
Which metrics to gather, how to gather, and why?
Which objectives to set, and why?
When can we turn an SLO into an SLA?
Why is it so important, if you really want to reduce churn and customer's disappointment?

What are Service Levels

The measured quality of a service, expressed as a quantified target that matches user needs. It can be: availability, latency, throughput, error rate, data freshness, and more.
Even correctness can be measured: the proportion of requests that returned the right answers.
Why do we need service levels? Measurement is the key, saying "reliable system" isn't enough, we need to measure and verify it constantly.

Service Level Indicator (SLI)

SLI is the quantitative indicator, the metric, and it has observed values for those metrics.
SLIs examples: p99 = 200ms; correctness (right responses) = 99.7%; availability = 99.9% (three 9s);
Another good example is: data freshness = data that is less than 10 seconds old (current time - data timestamp) => 99 of 100 = 99%

Service Level Objective (SLO)

What we want to achieve in our system: The target we want the SLI to achieve.
It should be reliable enough to meet user needs, but not so tight that it becomes expensive and hard to maintain.
Generally people think the harder or bigger the SLO, the better, but this is not the idea, we will discuss it soon after covering basics.
SLO example: SLI: Latency - SLO: p99 < 200ms

Service Level Agreement (SLA)

An agreement with the customers about metrics the system will deliver, and the consequences if the agreed service level isn't met.
SLA example: SLA: 99.9% availability - if it falls below this, the customer receives 10% credit.
Target without contractual consequence = SLO.

Visual Flow of Service Levels

Collecting Indicators

For that use a monitoring system such as Prometheus.
Don't rely only on backend metrics, also track frontend. Since user experience and user satisfaction are our objective we should also track metrics and cover problems that happen only on frontend. For example, slow page TTFB (time to first byte), and other issues.
Common metrics and interpretations:
- p50 = median latency (50% of requests are faster than this)
- p99 = tail latency (99% of requests are faster than this)
- Why is p99 called "tail" latency? Because p99 measures the latency near the end of the distribution, where the slowest 1% of requests are.
- more variance = more tail latency effect
- Avoid variance, Google researched that users prefer slightly slower responses than high variance response times and unpredictability.

Standardizing Indicators

Create a SLI template with default settings. It is especially useful when starting with service levels to help understanding.
Example:
- Perform metrics aggregation every 1 min
- Aggregation region = all tasks of entire cluster
- Measure every 10s
- Data-access latency = time to last byte
- Which routes to monitor and measure? Features critical flow; the most important ones for users
These I've told you are examples, don't follow them blindly.
Google SRE book mentions it as examples. I believe it's a good start.

Which are Possible SLOs and How to Choose Them?

As we've discussed earlier the SLOs can be multiple, and they are based on the SLIs.
Common indicators are: availability, latency, throughput, correctness, data freshness...
But having multiple indicators is not the point, the key is understanding your users and their needs. And only then setting SLOs to match their expectations and increase customer satisfaction.
There are a lot of things to consider on user behavior and research you should do to achieve this, since this is not the focus of this post I'll limit myself in this topic here.

SLOS are Objectives, Not Ornaments

Don't create SLOs only because they are on top of indicators easy to measure and objectives easy to achieve.
It's better to have only a couple of SLOs that really match user expectations than easy and useless ones.
If you see that it is a good strategy to "categorize" users and identify needs for these categories, then you can see which ones to focus on. This is especially good when user needs vary a lot.

Final Tips from Google SRE book:

Insisting that SLOs be met 100% of the time kills innovation and software delivery, and is pretty expensive.
Keep it simple, don't build complex SLI aggregates.
Have as few SLOs as possible (just enough to meet user needs - understand your customers.)
Don't expect user needs will be easy to match, find the right balance.
Perfection can wait, find a good margin not too tight but good enough for users.
Keep a safety margin internally tighter than the public one.
SLA requires time, and analysis of the difficulty to meet it across time. If you can't ensure it, don't create one.
Research, run experiments and tests to understand your users' needs.

References

Requirements & Back-of-the-Envelope Calculation

João Godinho — Wed, 19 Aug 2026 23:01:43 +0000

Overview

This article covers how to size a system before building it: first gathering functional and non-functional requirements, then running back-of-the-envelope calculations (QPS, storage, bandwidth, cache, and server count) through a worked example.

Why estimation matters

Using estimations we can go from "build a url shortener" to concrete numbers:
- Queries per second (QPS)
- storage/year
- bandwidth
- server count
And with that you can spot bottlenecks before they turn into a problem.
It provides us the ability to think about feasibility and scale, and drives capacity planning: how many servers, how much cache, how many DB shards, how much network bandwidth...

Before talking about estimates

Before estimating anything, pin down the requirements: what the system must do (functional) and how it must behave (non-functional).

Functional Requirements

Describes what the system does, features from the user's perspective. "Ask yourself what can a user do in my app?"
- Twitter: post a tweet, follow another user, timeline, like/comment a tweet.
- Youtube: upload a video, play back a video, search for videos, like/share a video, recommendation feed.
As you can see these behaviors map directly to APIs and core use cases.
Trying to do everything, and losing time-to-market on your core features, is terrible.

How to gather Functional Requirements?

Think about the system, talk with stakeholders, and teammates.
List primary usecases && Identify the actors: "In this uber-like app, clients request a driver and drivers can accept or reject clients. Will clients be able to rate drivers? And vice-versa?"
Think about edge scenarios to consider: "What happens if no driver accepts the request? Can a client cancel after a driver already accepted? What if the driver cancels mid-ride, or the app loses connection during the trip?"

Non-Functional Requirements

Describes how the system behaves, the quality attributes and constraints: performance, reliability, and user experience.
The architectural trade-offs live here (e.g. read vs write optimized, strong vs eventual consistency) and also estimation targets (QPS, storage, latency, budgets).
Always attach numbers, don't be vague and say "the system must be fast and highly available", pin concrete targets to each attribute "p99 latency < 200ms" and "99.9% availability".

Some Important Categories of Non-Functional Requirements:

Scalability: ability to handle growth in users/traffic/data.
- 1M daily active users; 500M tweets/day; 10k requests/sec
- "Do we need geographical distribution or just a local region?"
Performance (latency and throughput): speed and responsiveness.
- p99 response < 200ms; sub-second search queries
Availability: Fraction of time the system is up.
- 99.9% (three nines) vs 99.99% (four nines) uptime.
Reliability: Correct operation, fault tolerance, no single point of failure (SPOF).
- Survive one AZ/node failure and still return the right responses.
- Redundant app servers, db replica, automatic failover, etc.
- Automatic failover = the system detects when a component failed and switches to a healthy backup on its own.
Durability: Data survives failures, no data loss.
- No committed write ever lost; e.g. AWS S3 is designed for 11 9s of object durability (99.999999999%)
Consistency: how up-to-date reads are across replicas.
- Strong (banking balances) vs eventual within a few seconds (social media posts).
Security and Privacy: Protection of data and access.
- Auth, encryption in transit + at rest, rate limiting, GDPR compliance.
- encryption at rest = data is encrypted while stored. (disk, database, backups)
- encryption in transit = data is encrypted while moving between two points. (HTTPS)
Maintainability/Monitoring: Ease of change; Logging and monitoring.
- Can also be non-functional requirements.

How to gather Non-Functional Requirements?

Generally developers only think about functional requirements and it only turns into a problem when software is shipped to production and users start to face slow responses and loadings.
Simple: question yourself or stakeholders about project's non-functional requirements.
- How many daily active users?
- Requests per second?
- Most requests under 200ms (p99 <200ms)?
- Can this data be eventually consistent within a few seconds?
- Is there an uptime target or no SPOF requirement (more than one server instance, DB, etc)?
- Do we have any reliability constraint, if one server goes down should we have two or more? Geographically distributed or same region?
- Any GDPR concerns, or special security/privacy requirements?
- Can users see stale data for a few seconds as a trade-off to reach the required faster responses?
- Is there a budget or cost ceiling constraining the design?
- Is it read-heavy or write-heavy, and how big are peaks vs average?
Obs: while talking with non-technical people we could ask the same questions in a different style to gather non-functional requirements.

Back-of-the-Envelope Estimation

Quick, rough calculations to size a system in minutes. It's not meant to be exact, it's just a good approximation to check feasibility and find bottlenecks.
Generally it uses rules of thumb, general guidelines or principles based on experience and observation, not 100% precise but helpful for back-of-the-envelope calculations.
First of all, you must know basic measures used for these quick calculations.

Data Volume Units (Powers of Two)

2^10 ~= 1 Thousand -> 1 KB (Kilobyte)
2^20 ~= 1 Million -> 1 MB (Megabyte)
2^30 ~= 1 Billion -> 1 GB (Gigabyte)
2^40 ~= 1 Trillion -> 1 TB (Terabyte)
2^50 ~= 1 Quadrillion -> 1 PB (Petabyte)

Latency numbers every programmer should know (Peter Norvig and Jeff Dean)

These numbers are dated, but the point isn't accuracy, it's the relative ratios / orders of magnitude between tiers (memory vs SSD vs disk vs network).
Memory is fast, disk is slow, network across regions is slowest (avoid disk and cross-region hops on the hot path).
If you need to send data across the network, compress it.
Caching in memory can turn a 30ms disk read into a ~100ns lookup.
A cross-continent round trip (~150ms) dominates everything else (put data near users).

Table from: ByteByteGo
ms = millisecond (10^-3 seconds)
µs = microsecond (10^-6 seconds)
ns = nanosecond (10^-9 seconds)

Estimation example

1. Estimating write QPS: start from daily active users (DAU) * actions per user per day, then convert to per-second (divide by the seconds in one day 86400)

100k daily active users (DAU)
each user posts 3 photos per day (a photo post is a write)

writes per day = 100,000 * 3 = 300,000 photos/day
write QPS = 300,000 / 86,400 = (3 * 10^5) / (8.64 * 10^4) = 30 / 8.64 ~= 3
(it doesn't need to be exact, it is an approximation)

write QPS = 3

2. Estimate peak QPS: multiply average QPS by a peak factor (2x-10x) to plan for spikes

PEAK write QPS = 2 * 3 = 6

3. Estimate read vs write QPS: apply the read/write ratio (this system is read-heavy, 100:1)

read QPS = 100 * 3 = 300
PEAK read QPS = 2 * 300 = 600

4. Estimate storage = objects per day * size per object * retention period * overhead factor

overhead factor = metadata, indexes, replication, etc... (e.g. double overhead = 2)
assumptions: 3mb avg photo size, 4 years retention, overhead factor = 2, writes = 300,000 photos/day (from step 1)

storage = 300,000 * 3mb * 365 * 4 * 2 ~= 2.6PB

5. Estimate bandwidth = QPS * payload size (split into ingress = writes, egress = reads)

ingress (writes) = write QPS * size = 3 * 3mb = 9 mb/s
egress (reads) = read QPS * size = 300 * 3mb = 900 mb/s
(peak 600 * 3mb = 1.8 gb/s)

reads dominate (read-heavy), use peak QPS for the peak value

6. Estimate memory/cache: use a rule of thumb -> Pareto principle (cache the hot 20% that serves 80% of reads).

cache = 20% of daily data = (300,000 * 3mb) * 0.2 = 900 GB * 0.2 = 180 GB

7. Estimate server count = required QPS / QPS a single server can handle (+redundancy for safety)

the dominant load is reads, so size on PEAK read QPS = 600
assume 1 server handles ~1,000 QPS

600 / 1,000 < 1 -> 1 server already handles the load
Server count = 1 + 1 = 2
(the +1 is for redundancy/availability, so there is no
single point of failure if one goes down)

What the numbers told us: it's a read-heavy service (100:1), so favor caching + read replicas and a CDN for media. Storage is large and media-dominated (~2.6PB over 4 years), so use object storage with tiering, not a single DB. Egress dominates bandwidth (~900 mb/s, peak ~1.8 gb/s), which is why media should go through a CDN. The request load itself is small (peak 600 read QPS), so 1 app server already handles it (plus 1 more for redundancy, 2 total) alongside a cache tier.

Conclusion

Gathering requirements, knowing about functional and non-functional requirements, and doing back-of-the-envelope calculations are important skills that every system architect must have.
Even if you didn't know these before this reading, if you already did that instinctively you were on the right path.
The biggest mistake of some developers is trying to develop a system when they don't know its functional and non-functional requirements. It will certainly be a mess and full of issues.
- Developing the wrong system well is worse than developing the right system poorly.
Obviously what we've discussed is just the start. The most important part is experience: doing and repeating.

References

System Design Primer (Donne Martin, GitHub)
Back-of-the-Envelope Estimation (ByteByteGo)
Teach Yourself Programming in Ten Years (Peter Norvig, the latency numbers table)
How to Gather Requirements in System Design Interviews (DesignGurus)

Deployment strategies

João Godinho — Wed, 12 Aug 2026 01:34:50 +0000

Overview

Every time you ship code you have to answer one question: how do the new version
and the old version hand off? Do all users move at once, or a few at a time? Is
there downtime? Can you roll back fast if something breaks?

Deployment strategies are the different answers to that question. Each one trades
simplicity for some mix of zero downtime, safer rollout, and better
testing, and each extra guarantee costs you complexity and infrastructure.

This article walks through the main strategies from the simplest to the most
advanced, then ends with a simple flow to pick one: you start at big-bang and
"buy" each new capability with a bit more complexity.

How to decouple release and deploy

Traditionally people mix release and deploy and treat them as one single event:
you freeze the code in a branch for tests and validation, then put it into
production available for all clients at once.

Decoupling them means splitting that single event into two separate things:

Deploy = publishing new code to production infrastructure.
Release = exposing that code to clients, whenever you decide.

We can achieve that by using feature flags, a technique that can be combined
with any of the deployment strategies below. A feature flag is a runtime switch (a
config value, not a code change) that decides whether a piece of code actually
runs. You wrap the new behavior in a flag that defaults to "off" and ship the
code, so it sits in production deployed but not released. Nobody sees it until you
flip the flag on, and flipping it off brings the old behavior back instantly (a
"kill switch").

Image from CircleCI.

Trade-offs:

Flag debt: flags pile up and need discipline to clean up once a feature is fully released. A good practice is to set a deadline for removing each flag so they don't live in the code forever.
Extra complexity in the code, since both the old and new paths live side by side while the flag exists.

Problems it solves:

A deploy stops being risky, because new code can go to production without being exposed to anyone.
Rollback is instant: flip the flag off instead of redeploying the old version. This gives us space to be more innovative and less busy putting out fires like firemen.
You can release to whoever you want first (1%, internal users, a single client) and widen from there.
The release decision no longer depends on a deploy, so product or ops can pick the timing instead of waiting on a new build.

Big-bang

Stop all instances of the current version, then start the new one. No traffic
splitting, no coexistence, every user moves at once.

It is simple and fast to implement, which is its whole appeal. The cost is
downtime during the swap (seconds to minutes), high risk, and no easy
rollback: if the new version is broken, every user hits the problem immediately.

Good for dev/staging, scheduled maintenance windows, and breaking changes where
running two versions at once would be a problem anyway. AWS calls this same idea
all-at-once.

Recreate

Terminate the previous version completely, then rebuild the whole environment
with the new one. Only one version ever runs.

This looks almost identical to big-bang. Both have downtime, both move everyone
at once, neither runs two versions together. The difference is emphasis:

Big-bang is about rollout scope: the change goes to everyone at once, with no phasing. It can happen in place on the same machine, so you stop the old process, swap the code, and start the new process.
Recreate is about the infrastructure: destroy the old environment and rebuild it from a clean image, then deploy onto it.

Why throw the whole box away? Restarting in place carries over old state (stale
files, cached artifacts, manual tweaks), which drifts your config over time.
Recreate guarantees a clean slate every deploy. It is simple and predictable, but
still has downtime and limited testing before the switch.

Rolling

Update instances in batches while the app stays up, so old and new versions
serve traffic at the same time until every instance is on the new version. No
downtime, and you reuse the existing capacity, so no new infrastructure.

The catch is that both versions run at once, so the new version must be
backward-compatible with the old (same database, same API contracts).
Rollback means rolling backward through the batches.

The diagram above (and what I'm describing here) is rolling instance-based,
without any traffic-splitting logic: you just swap whole instances one batch at a
time. But there are two common ways to do the rollout:

Instance-based (the traditional): swap whole instances one batch at a time. Simple, since you just need enough instances to roll through, and no logic to split requests. Each instance either runs the old version or the new one, and you accept a small dip in capacity during the rollout.
Traffic-based: keep both versions up and use a load balancer to decide which instance each request hits, shifting the percentage of traffic toward the new one, often in equal increments on a timer (AWS calls this linear). This needs a load balancer or proxy that can split requests, but it handles the transition more smoothly.

Rolling is a good default for backward-compatible changes when infra cost matters
and you release often.

Canary

Route a small slice of production traffic (typically 1% to 5%) to the new
version while everyone else stays on the current one. Watch the metrics; if they
stay healthy, grow the slice until the new version takes over.

Image from CircleCI.

Compared to rolling, canary adds real-time monitoring and automated analysis:
you are not just shifting traffic, you are watching a small blast radius for
errors and rolling back before most users ever see them. That buys minimal
production risk, early bug detection, and real feedback from real users, at a much
lower cost than a full duplicate environment.

The key difference from rolling is the rollback. Canary watches metrics and,
if they degrade, sends all traffic back to the current version. Rolling has no
metrics gate, so to undo it you roll backward through the batches, which is
slower and manual.

The price is the machinery: traffic splitting, monitoring, and enough traffic for
the metrics to mean something. Best for high-traffic services that already have
monitoring in place.

Blue/green

Keep two identical production environments. One (blue) serves all traffic;
the other (green) sits idle. Deploy the new version to green, validate it fully,
then switch all traffic over at once. If something breaks, switch back.

The win is rollback speed (under a minute) and full validation of the real
environment before any user touches it, with no downtime and a seamless switch.
The cost is double compute: you pay for two complete environments. A shared
database still needs care (an expand-migrate-contract approach), since both
versions may touch it around the switch. AWS notes this is sometimes called
red/black.

Reach for it when rollback speed is critical and the budget allows the
duplication.

Shadow

Run the new version alongside the current one and mirror real production
traffic to it, but never serve its responses to users. The shadow's output is
logged and compared, then discarded.

Image from CircleCI.

This is the safest way to test, because users are never affected while you put the
new version under real production load and uncover real-world issues. The catch is
stateful operations: database writes, payments, emails, anything with side
effects runs twice unless you filter it out. You also pay for a duplicate
environment plus the request-duplication plumbing.

Great for model swaps, algorithm rewrites, and validating database migrations
under real load when you cannot tolerate downtime. Feature flags cannot replicate
this, which is what makes it unique.

Pros and cons

Strategy	Pros	Cons
Big-bang	Simple and fast; fine for breaking changes (no coexistence)	Downtime; high risk; no easy rollback; every user hit immediately; new version isn't tested under real traffic before going live
Recreate	Simple and predictable; clean slate, single running version	Downtime; high risk; no easy rollback; every user hit immediately; new version isn't tested under real traffic before going live
Rolling	Reuses existing capacity (no new infra); no downtime; issues hit only a subset; old version still there to roll back to	Needs backward compatibility; rollback means rolling in reverse; traffic-based variant needs a load balancer; more to manage
Canary	Cheaper than blue/green; minimal production risk; early bug detection; real user feedback; easy rollback	Needs traffic splitting, monitoring, and automated analysis; slower to full release; needs enough traffic for metrics
Blue/green	No downtime; fast rollback (under a minute); full validation before the switch	Double compute cost; shared database still needs expand-migrate-contract
Shadow	Safest, since users are never affected; full production-load testing; finds real-world issues	Stateful ops run twice and must be filtered; duplicate environment plus request duplication
Feature flags (on top of any of the above)	Decouples deploy from release; instant kill-switch rollback; no extra infra	Flag debt; needs cleanup discipline; cannot replicate shadow

How to choose

Think of it as a ladder. You start simple and only climb when you need the next
capability, and each step costs more complexity and infrastructure than the last.
As pseudocode, cheapest first, adding one guarantee at every step:

// start simple; each need bumps you up one step (more complexity, more advantage)

pick = Big-bang / Recreate            // simplest: accepts downtime, risky

if (needZeroDowntime)
    pick = Rolling (instance-based)   // + no downtime

if (needSmootherTransition)
    pick = Rolling (traffic-based)    // + shift by % of traffic

if (needMonitoringOnSmallSlice)
    pick = Canary                     // + early detection, auto rollback

if (needFasterRollback)
    pick = Blue/green                 // + instant switch and rollback

if (needRealLoadTestingWithNoUserRisk)
    pick = Shadow                     // + test on real traffic, zero user impact

Can you accept downtime, and do you ship breaking changes? Stop here, at big-bang / recreate. No coexistence means breaking changes are fine, and there is nothing to configure.
Want zero downtime, but no duplicate environment and no traffic-splitting logic? Climb to rolling (instance-based). You roll batches of instances and accept a small capacity dip.
Want that transition to be smoother with traffic-splitting logic? Move to rolling (traffic-based / linear), shifting traffic by percentage instead of by whole instances.
Want to catch problems on a small slice with real-time monitoring? Step up to canary: expose 1% to 5%, watch the metrics, and roll back before most users are affected.
Want the fastest possible rollback and can pay for a duplicate environment? Go to blue/green: validate a full second environment, then flip.
Have a duplicate environment and need real production-load testing with no user risk? Top of the ladder is shadow: mirror real traffic, serve none of it.

Each step trades a bit more complexity for one more guarantee: zero downtime, then
smoother traffic, then early detection, then instant rollback, then risk-free
testing. Pick the lowest step that gives you what you actually need.

Read also

Jenkins CI/CD from scratch,
so you can learn how to implement these deployment strategies with the help of a
tool that lets you automate deploys and rollbacks easily, creating pipelines with
build, testing, validation and more.

References

Jenkins CI/CD from scratch

João Godinho — Tue, 11 Aug 2026 03:53:24 +0000

Overview

Shipping code by hand is slow and easy to get wrong: run the tests, build the
image, copy it to the server, restart, check it still works. CI/CD automates all
of that. You push code, and a pipeline runs those steps for you, every time, the
same way.

This article explains the basics of Jenkins and walks through a small, real
pipeline that tests, builds, deploys, and load-tests an API, and rolls back on
its own if something breaks. The full code is here:

Repository: https://github.com/godinhojoao/jenkins-demo

I run this on a homelab: a Raspberry Pi with Gitea
(a self-hosted Git server) next to Jenkins. The public repo above uses GitHub so
anyone can reproduce it.

What is Jenkins?

Jenkins is an open-source automation server for CI/CD (Continuous Integration and
Continuous Delivery). Instead of running build and deploy commands by hand, you
describe them once and Jenkins runs them on every push.

A few terms worth knowing:

Controller: the main Jenkins process. Hosts the web UI, stores jobs and config, and schedules work.
Agent (node): a worker that actually runs the build steps. With one machine, the controller also runs the builds (agent any).
Pipeline: a job whose steps are code, split into stages (Test, Build, Deploy, ...).
Jenkinsfile: the file that defines the pipeline, committed next to the app.
Trigger: what starts a build automatically (a webhook, or polling the repo).

The pipeline

The pipeline in this repo has five stages, and rolls back if anything fails after
a deploy:

Test    -> npm test inside a Docker build (broken code never ships)
Build   -> docker build, image tagged by commit
Deploy  -> docker compose up -d
Verify  -> hit /health until it responds
Load    -> k6 sends traffic and checks latency/error thresholds

If Test or Build fails, the pipeline stops and nothing is deployed. If
Verify or Load test fails, the new version was already deployed, so a
post { failure } block redeploys the last good image automatically.

Here is the whole thing as code (http-api/Jenkinsfile):

pipeline {
  agent any

  environment {
    IMAGE = 'http-api'
    TAG   = "${env.GIT_COMMIT?.take(7) ?: 'dev'}"    // tag image by commit
    STATE = "${JENKINS_HOME}/http-api.last_good"      // remembers last good tag
  }

  stages {
    stage('Test') {
      // runs the tests inside the Docker build; fails the run if a test fails
      steps { dir('http-api') { sh 'docker build --target test -t $IMAGE:test .' } }
    }
    stage('Build') {
      steps { dir('http-api') { sh 'docker build --target runtime -t $IMAGE:$TAG .' } }
    }
    stage('Deploy') {
      steps { dir('http-api') { sh 'IMAGE_TAG=$TAG docker compose up -d' } }
    }
    stage('Verify') {
      // is the app up? fail fast before wasting time on the load test
      steps {
        dir('http-api') {
          sh '''
            for n in $(seq 1 10); do
              if docker compose exec -T app wget -qO- http://localhost:3000/health >/dev/null 2>&1; then
                echo healthy; exit 0
              fi
              sleep 2
            done
            echo "health check failed"; exit 1
          '''
        }
      }
    }
    stage('Load test') {
      // k6 checks latency/error thresholds; a breach fails the stage
      steps {
        dir('http-api') {
          sh '''
            docker run --rm -i --network host \
              -e BASE_URL=http://localhost:8091 \
              grafana/k6 run - < loadtest.js
            echo $TAG > "$STATE"      # only now is this tag the rollback target
          '''
        }
      }
    }
  }

  post {
    failure {
      // auto-rollback: redeploy the last version that passed the load test
      dir('http-api') {
        sh '''
          if [ -f "$STATE" ]; then
            PREV=$(cat "$STATE")
            echo "rolling back to $PREV"
            IMAGE_TAG=$PREV docker compose up -d
          fi
        '''
      }
    }
  }
}

This is a recreate (big bang) deployment: one container is stopped and a new one
started, so there is a short downtime window during the swap. Strategies like
blue/green or canary remove that gap, but recreate is simple and fine for a
homelab.

The job as code (JCasC)

You can create a Jenkins job by clicking through the UI, but this repo defines it
as code with the Configuration as Code (JCasC) and Job DSL plugins. When
the Jenkins container starts, it reads jenkins-server/jenkins.yaml and creates
the job by itself: the repo URL, the branch, where the Jenkinsfile lives, how
often to poll, and which paths should trigger a build.

pipelineJob('jenkins-demo') {
  definition {
    cpsScm {
      scm {
        git {
          remote { url('https://github.com/godinhojoao/jenkins-demo.git') }
          branch('*/main')
          extensions {
            // only build when files under http-api/ change
            pathRestriction { includedRegions('http-api/.*') }
          }
        }
      }
      scriptPath('http-api/Jenkinsfile')
    }
  }
  triggers { scm('* * * * *') }   // poll every minute
}

The benefit: the whole setup is reproducible. Rebuild the machine and the job
comes back exactly the same, no manual clicking.

Build agents

In this homelab I don't use agents: the same Jenkins container runs the UI and
the builds (agent any). It is simple and fine for one machine and my own code.
In a real setup, though, running builds on separate agents is recommended. The
main gains are:

Isolation (security): builds run away from the controller, so they can't reach its config and credentials. Important for untrusted code, like public pull requests.
Scale: spread many builds across machines and run them in parallel.
Clean environments: a fresh, disposable container per build.
Different platforms: build on another OS or CPU architecture.

Setup in short

# 1. push the project to a public GitHub repo
git init && git add . && git commit -m "init"
git remote add origin https://github.com/<you>/jenkins-demo.git
git push -u origin main

# 2. start Jenkins
cd jenkins-server
docker compose up -d --build
docker compose logs jenkins        # copy the first-run admin password

Open the Jenkins UI, unlock it, install the suggested plugins, and create a user.
The job is created automatically from jenkins.yaml. From then on, a push runs
the pipeline.

What it looks like

A successful run: every stage passes and the app is deployed.

A failing test stops the pipeline, so nothing is deployed.

The app deployed but failed the load test, so it rolled back to the last good
image.

A change outside http-api/ (like editing the README) is ignored by polling, so
no build runs.

Running it on your own homelab

I run this on a Raspberry Pi with Gitea and Jenkins side by side. That keeps my
code and my pipelines fully under my control, with no dependency on any cloud.

In this public demo the job polls GitHub, because GitHub can't reach a machine on
a home network. On my own homelab I don't poll: since Gitea is local, it can
reach Jenkins directly, so a Gitea webhook triggers builds instantly on every
push. In production, with a public IP, a VPS, or a configured tunnel, you could
use GitHub webhooks the same way.

If you have a homelab, I recommend the same: self-host Gitea, connect it to
Jenkins with a webhook, and everything runs on hardware you own. That is the whole
point of a homelab, keeping your code and pipeline private and in your hands.

The full working example, all the configs, and a step-by-step setup are in the
repository: https://github.com/godinhojoao/jenkins-demo

References

Heap Data Structure

João Godinho — Sun, 10 May 2026 01:06:30 +0000

Introduction

This post covers binary heaps as a complete binary tree stored in an array, where each parent follows a priority rule (min-heap or max-heap). It explains the core operations push (heapifyUp) and pop (heapifyDown), the heap property, and provides an implementation.
It also covers trade-offs of using heaps as priority queues, real use in greedy algorithms like Dijkstra’s algorithm and Huffman coding, O(n) in-place heap construction, plus heapsort, and a discussion about introsort.

Binary Heap

A binary heap is a special case of a heap with the following properties:
1. It is a complete binary tree (every level is full except the last, which is filled from left to right).
2. Being a complete binary tree implies:
  - If a node is at index i:
  - Left child = 2*i + 1
  - Right child = 2*i + 2
  - Parent = (i - 1) / 2 (if not root)
3. Heap property (what differentiates heaps):
  - The parent has higher priority than its children
  - Example: min-heap (highest priority = smallest value)
  - Parent ≤ both children
As you can see, the parent always has the highest priority.
This implies that the root (first node) always has the highest priority.

K-ary Heap

We could have a k-ary heap, the properties stay the same, only changes are:
- If a node is at index i:
- first child = k*i + 1
- second child = k*i + 2
- k-th child = k*i + k
- Parent = (i - 1) / k (if not root)

Pseudocode for Binary Heap → MinHeap

We save heap items into an array: items = []
1. PUSH inserts new nodes
- a. Insert at end of array items.push(newItem), addedItemIndex = i
- b. Now if we have more than 1 element we have to check property validity:
  - i. parent ≤ child
  - ii. if true → valid, do nothing
  - iii. if false → invalid, swap(parent, child)
  - iv. repeat until reach valid heap state.
- We generally call this b step of fixing the tree when inserting as heapifyUp.
- heapifyUp because we start from the bottom (after adding at the end of the heap), and fix the heap bottom-to-top by comparing the node with its parent.
2. POP get root (highest priority element)
- a. Remove root node and put the last added on its place.
- b. Now if we have more than 1 element we have to check property validity:
  - i. parent ≤ both children
  - ii. if true → valid, do nothing
  - iii. if false → invalid, swap(parent, smallestChild)
  - iv. repeat until reach valid heap state.
- Here we call it heapifyDown since we start on root and go down, comparing the parent with its children.

Binary Heap Code

Huffman Code in C - contains minHeap implementation within it
JS implementation below: Github repository

class BinaryHeap {
  #items = [];
  #hasHigherPriorityFn;

  constructor({ items, hasHigherPriorityFn }) {
    if (!(items && items.length)) { throw Error("'items' field, is required") }
    // no types here in JS, so we trust hasHigherPriorityFn function and items array -> the focus is binary heap
    if (!hasHigherPriorityFn || typeof hasHigherPriorityFn !== "function") { throw Error("'hasHigherPriorityFn' function is required") }
    this.#hasHigherPriorityFn = hasHigherPriorityFn;

    this.#items = items;
    this.#buildHeapInPlace(this.#items);
  }

  #swap(addedIndex, parentIndex) {
    const temp = this.#items[addedIndex];
    this.#items[addedIndex] = this.#items[parentIndex];
    this.#items[parentIndex] = temp;
  }

  // time: O(log n), space O(log n) -> recursion, iterative is O(1) space
  #heapifyUp({ insertedItemCurrIndex }) {
    const parentIndex = Math.floor((insertedItemCurrIndex - 1) / 2);
    if (parentIndex < 0 || insertedItemCurrIndex == parentIndex) {
      return;
    }

    const insertedItem = this.#items[insertedItemCurrIndex];
    const shouldSwap = this.#hasHigherPriorityFn(insertedItem, this.#items[parentIndex]);
    if (shouldSwap) {
      this.#swap(insertedItemCurrIndex, parentIndex);
      this.#heapifyUp({ insertedItemCurrIndex: parentIndex });
    }
  }

  // time: O(log n), space O(log n) -> recursion, iterative is O(1) space
  #heapifyDown({ currItemPosition }) {
    let mostPriorityItemIndex = currItemPosition;
    const leftChildIndex = 2 * currItemPosition + 1;
    const rightChildIndex = 2 * currItemPosition + 2;

    const leftChildExists = leftChildIndex < this.#items.length;
    if (leftChildExists && this.#hasHigherPriorityFn(this.#items[leftChildIndex], this.#items[mostPriorityItemIndex])) {
      mostPriorityItemIndex = leftChildIndex;
    }

    const rightChildExists = rightChildIndex < this.#items.length;
    if (rightChildExists && this.#hasHigherPriorityFn(this.#items[rightChildIndex], this.#items[mostPriorityItemIndex])) {
      mostPriorityItemIndex = rightChildIndex;
    }

    // currItem = parent (start at index 0)
    // if parent already has the highest priority, do nothing
    // otherwise swap with highest priority child until heap is valid again
    if (mostPriorityItemIndex != currItemPosition) {
      this.#swap(currItemPosition, mostPriorityItemIndex);
      this.#heapifyDown({ currItemPosition: mostPriorityItemIndex });
    }
  }

  // O(n) because most heapifyDown calls run on small-height nodes.
  #buildHeapInPlace(arr) {
    const arrSize = arr.length;
    for (let i = Math.floor(arrSize / 2) - 1; i >= 0; i--) {
      this.#heapifyDown({ currItemPosition: i });
    }
  }

  // O(log n)
  push({ item }) {
    this.#items.push(item);
    if (this.#items.length >= 2) {
      this.#heapifyUp({ insertedItemCurrIndex: this.#items.length - 1 });
    }
  }

  // O(log n)
  pop() {
    const currLength = this.#items.length;
    if (currLength == 0) { return null; }

    const itemToReturn = this.#items[0];
    this.#items[0] = this.#items[currLength - 1]; // last item is new root
    this.#items.pop(); // remove last item from array

    if (currLength > 1) {
      this.#heapifyDown({ currItemPosition: 0 }); // fix top down
    }

    return itemToReturn;
  }

  // O(1)
  peek() {
    if (!this.#items.length) { return null; }
    return this.#items[0];
  }

  printItems() {
    console.log('this.#items', this.#items);
  }

  consumeAll(callback) {
    console.log(this.constructor.name, 'consumeAll:')
    console.log('this.#hasHigherPriorityFn.toString()', this.#hasHigherPriorityFn.toString())
    while (this.#items.length) {
      callback(this.pop());
    }
  }
}

// smallest item at root index = 0
class MinHeap extends BinaryHeap {
  constructor({ items }) {
    super({ items, hasHigherPriorityFn: (itemA, itemB) => itemA < itemB });
  }
}

// biggest item at root index = 0
class MaxHeap extends BinaryHeap {
  constructor({ items }) {
    super({ items, hasHigherPriorityFn: (itemA, itemB) => itemA > itemB });
  }
}

console.log('--------------------------------------------------------')

const minHeapTest = new MinHeap({ items: [8, 7, 6, 5, 4, 3, 2, 1] });
minHeapTest.printItems();
minHeapTest.consumeAll(console.log)

console.log('--------------------------------------------------------')

const maxHeap = new MaxHeap({ items: [1, 2, 3, 4, 5, 6, 7, 8] });
maxHeap.printItems();
maxHeap.consumeAll(console.log)

console.log('--------------------------------------------------------')

const people = [{ name: "João", age: 22 }, { name: "Turing", age: 41 }, { name: "Ada Lovelace", age: 36 }]
const elderlyPeopleFirstHeap = new BinaryHeap({ items: people, hasHigherPriorityFn: (a, b) => a.age > b.age });
elderlyPeopleFirstHeap.consumeAll(console.log)

console.log('--------------------------------------------------------')

OUTPUT:

Time Complexity

Operation	Time complexity
`Push`	O(log n)
`Peek`	O(1)
`Pop`	O(log n)

O(log n) → Because complete binary tree contains:
- 2^height ~ n
- height = log n
- It means that every time we fix the heap, the height decreases by one level at each step, and in the worst case it requires moving a node from the bottom (height = 0) to the top (height = log n), which is O(log n) in the worst case.
  - Or the opposite direction, from top to bottom.

Use cases and trade-offs

Commonly used to implement priority queues. Priority queues can also be implemented using other data structures such as arrays.
- But with a sorted array, for example, you would have O(1) pop and O(n) insert, since inserting a new item in the correct position may require shifting all items in the worst case.
To implement a priority queue
- Use a queue if you will set up all inserts at once and then only perform reads.
- Use a binary heap or k-ary heap if you require faster inserts O(log n).
Widely used in greedy algorithms that require extracting the highest priority item at each step from a priority queue:
- Huffman coding (greedy + min-heap) - C code here
- Dijkstra’s algorithm (greedy + min-heap) - C++ code here, developed by Matheus Persch.
- And more…

In place `O(n)` build max heap instead of `O(n * log n)`

Github Repository

// theory: all items after n/2 are leaves: A[n/2+1, ..., n]
// practice: as indexes start at 0, n/2 is already a leaf
// so we start at (n/2)-1 until 0
    // --> from height 1 until root

function buildHeapInPlace(arr) {
  const arrSize = arr.length;
  for (let i = Math.floor(arrSize / 2) - 1; i >= 0; i--) {
    heapifyDown({ items: arr, currItemPosition: i });
  }
}

How do we know that items after n/2 are leaves?
- 1. We know that leaves have no children
  - a. left child = 2*i+1 ; right child = 2*i+2
- 2. If has no children: 2*i > n 2*i outside array bound n so there is no children
  - a. And then we find: i > n/2 , so all items A[(n/2)+1, …, n] are leaves
Why do we start from height=1 and not from leaves at height = 0?
- index = n/2, height 1 = first non leaf node;
- Because leaves (h=0) are already valid heaps (don't require fix), and heapifyDown only works to fix a parent with valid heaps as children.
- In a heap, each operation fixes one node at a time.
Why do we go until height=log n ?
- height = 1 → first non-leaf node
- height = log n → root
- We fix the heap bottom-up.
- When we reach height = log n, we have fixed the root, so the entire tree is a valid heap.

Why is it **O(n) and not O(n *log n)?**

Both heapifyDown and heapifyUp have complexity of O(log n)
heapifyDown(node): max number of required movements = distance from node to the bottom of the tree (expensive if nodes are at the top)
heapifyUp(node): max number of required movements = distance from node to the top of the tree (expensive if nodes are at the bottom)
Given an array, what would you prefer? Start building a heap from top or bottom?
- Starting at top: use heapifyUp() in all nodes
- Starting at bottom: use heapifyDown() in all nodes

Building the sum for each approach to analyze it better

At height=0 we have n/2 nodes, at height=1 n/4, and so on…

moves per level = (nodes at that height) * (max movements each node can do)
Starting at top with heapifyUp(), the sum of movements/operations would be:
- tree height = h = log n
- (n/2 * h) + (n/4 * (h-1)) + (n/8 * (h-2)) + ... + (1 * 0)
But starting at bottom with heapifyDown(), the sum of operations is:
(n/2 * 0) + (n/4 * 1) + (n/8 * 2) + ... + (1 * h)
Compare item by item in the both sums, you will notice, for example, that:
- n/2 * logn > n/2 * 0
- And starting at top makes much more movements for each level.
But we still haven't answered: why starting at bottom makes it O(n)?
- If you have at least basic calculus knowledge it will be easier, but I'll not make a formal demonstration, only show an intuitive explanation. k = current level

The sum doesn't depend on n it converges to a constant.
So it would be n*O(1) → O(n)
In summary, many nodes do small work, and few nodes do large work. The balance gives a linear total O(n).
- leaf nodes = 0 moves
- level 1 (above leaves) = at most 1 move
- …
- root = at most log n moves
For more: watch starting at 30:00 - MIT OpenCourseWare - Lecture 4: Heaps and Heap Sort (Srini Devadas, 2011)

Use case for build heap in-place

If you already have an array, it is better to build the heap in-place using bottom-up heap construction than inserting items one by one and applying heapifyDown multiple times.

buildInPlaceMaxHeap(array); // O(n)

// O(n*log n)
for(item of array) { // O(n)
    existentMaxHeap.insert(item); // O(log n)
}

// When to use for (item of arr) existentMaxHeap.insert(item)?
// 1. you don't receive the entire array at once, just streaming single items
// 2. you already have a big existent heap
    // let's say your heap contains 10k items
    // and you receive 10 items at once
    // it isn't a good idea to rebuild the entire heap again

Heapsort

I hope you can read that. Good luck.

Just kidding, I'll write it down here:
1. Build a MaxHeap in O(n) in place using an array.
- a. The heap area starts from 0 to n-1. (the entire array is a heap)
2. Swap the ROOT and the last item, then decrease the heap area by one.
- a. The root was the biggest element (inside the heap area).
- b. Now the biggest element is at the end (the correct place in the sorted array).
3. Heapify Down to fix the ROOT.
4. if (heapArea > 1) { return to step 2 } else { HALT }
- a. In the handwritten note I put heapArea > 0, but if only one element remains, this is the smallest one. (The paper is quite wrong.)
I really suggest you to watch the last minutes starting at 48:00 - MIT OpenCourseWare - Lecture 4: Heaps and Heap Sort (2011)

Heapsort code

Time complexity: O(n * log n)
Space complexity: O(1) → iterative version
Github repository

function heapsort(items) { // O(n*log n)
  buildHeapInPlace(items);

  let heapAreaEnd = items.length - 1;

  // while runs n-1 times = O(n)
  while (heapAreaEnd > 1) {
    swap(items, 0, heapAreaEnd);
    --heapAreaEnd;
    // O(log n)
    iterativeHeapifyDown({ items, currItemPosition: 0, lastHeapIndex: heapAreaEnd });
    // now heapifyDown receives the lastHeapIndex, to change only heapArea
  }
  // return items; // not needed since heapsort is in place
}

const arr = [1, 2, 9, 4, 5, 6];
console.log('before: arr', arr) // [ 1, 2, 9, 4, 5, 6 ]
heapsort(arr)
console.log('after arr', arr) // [ 1, 2, 4, 5, 6, 9 ]

// simplifying: get biggest item (root) and put it at the end of heap area
// now the last item is in the correct position
// --> fix new root that breaks heap property, heapifyDown()
// repeat until all items are in the correct position

Heapsort is an unstable sort:

Heapsort and Merge sort comparison

If heapsort has the same Big-O time complexity as merge sort, why is merge sort generally faster?
- merge sort: time O(n*log n), space O(n)
- Memory locality: heapsort jumps around memory (left child = 2*i+1, ...) while merge sort uses sequential memory, taking advantage of cache locality and CPU cache.
- Comparisons and data movements: heapsort needs to repeatedly compute left and right children, compare multiple nodes using the max heap a > b property, and swap elements. These are all constant factors that are not counted in Big-O notation, but in practice they matter.

EXTRA: Introsort and the use of heapsort

Quicksort is known for being one of the fastest non-hybrid comparison sorting algorithms.
But there is no one size fits all in computer science. Some standard libs such as in c++ mix multiple sort algorithms for reaching a better hybrid sorting algorithm with best performance.

Algorithm Time (Average) Time (Worst) Space (Average) Space (Worst)

Quicksort O(n log n) O(n^2) O(log n) O(n)

Introsort O(n log n) O(n log n) O(log n) O(log n)
Introsort is a hybrid sorting algorithm that uses:
- insertion sort for small arrays
- quicksort until a maximum recursion stack depth is reached
- heapsort after reaching the maximum recursion stack depth
  - Why not merge sort, since it is better than heapsort? Because heapsort is in-place, so we can continue the work that quicksort has already done.

Algorithm	Time (Average)	Time (Worst)	Space (Average)	Space (Worst)
Quicksort	`O(n log n)`	`O(n^2)`	`O(log n)`	`O(n)`
Introsort	`O(n log n)`	`O(n log n)`	`O(log n)`	`O(log n)`

Pseudocode:

Introsort(A):
    depth_limit = 2 * floor(log2(n))
    introsort(A, depth_limit)

introsort(A, depth_limit):
    if size(A) <= 16: // small array -> insertion sort
        insertion_sort(A)
        return

    if depth_limit == 0: // reached recursion depth limit -> heapsort
        heapsort(A)
        return

  // fallback: quicksort
    pivot = partition(A) // using median-of-three
    introsort(left of pivot, depth_limit - 1)
    introsort(right of pivot, depth_limit - 1)

References

TSP - Travelling Salesman Problem

João Godinho — Wed, 06 May 2026 01:23:39 +0000

Introduction

I will talk about P vs NP, NP-complete, and NP-hard, define heuristics in computer science, Hamiltonian cycles, TSP and Metric TSP, approximation algorithms, and optimal vs suboptimal solutions. I will also mention local minima, combinatorial explosion, and why exact solutions become infeasible. Finally, we will see an optimal solution and also an approximation algorithm.
I’ll also discuss the limitations of the chosen approximation algorithm, what could be improved, and mention other options like MST-based solutions, k-opt methods, and metaheuristics such as genetic algorithms, and their trade-offs.
The project code and analysis were developed in collaboration with Matheus Persch as part of the DSA III class at Federal University of Pelotas (UFPel), Brazil.

Prerequisites

Types of problems

Decision problem: You want to answer yes or no.
- E.g. “Is there any Hamiltonian cycle in this graph G?” (YES/NO)
Search problem: You want to find a valid solution (if it exists).
- E.g. “Find a Hamiltonian cycle in this graph G.”
Optimization problem: You want to find the best solution according to some objective (min/max).
1. “Find the shortest Hamiltonian cycle in this graph G.” (TSP) - minimization problem
2. “Find the maximum clique in graph G.” - maximization
3. clique = subset of vertices in a graph that forms a complete subgraph

Time complexity class

Informal definition: Set of problems solvable in O(TIME(n)) time.
- Example: sorting is in P because it has polynomial-time algorithms.
Formal definition: TIME(t(n)) is the set of languages decidable by a deterministic Turing machine in O(t(n)) time.
- Note: “decidable” is formal for languages; for problems like sorting, this feels unnatural, so focus on the informal version for now.

P, NP, NP-Complete, NP-Hard

Polynomial time (P): Those problems which are decidable in polynomial time using a deterministic Turing machine.
- TIME(O(n^k)) → k constant
Nondeterministic Polynomial time (NP): Those decision problems whose solutions can be verified in polynomial time by a deterministic Turing machine.
- Verification: Given a candidate solution (certificate), we check if it is valid.
- E.g. “Given a graph and a certificate, check if it is a valid Hamiltonian cycle.”
NP-Complete (NPC):
1. is NP
2. Every problem in NP can be reduced to it in polynomial time
  - One example is the SAT
NP-Hard: Problems that are at least as hard as the hardest problems in NP.
1. Every problem in NP can be reduced to them in polynomial time
2. Not required to be in NP
  1. ALL NP-complete are NP-hard
  2. But not all NP-hard problems are NP-complete
3. NP-hard problems are not restricted to be decision problems such as P, NP and NPC.
4. Example: TSP (optimization version)
For more detailed explanations, read the chapters of Michael Sipser’s book or watch his lectures in the references of this post.

Image reference: Wikipedia NP-hardness

What is the Traveling Salesman problem?

Hamiltonian cycle Problem = Does a cycle exist that visits every vertex exactly once?
- Note: you can't repeat the same edge, but there are variations where you can do it.
TSP = Among all Hamiltonian cycles, which one has minimum cost?

Metric TSP

Metric TSP is formulated on a complete graph with distances satisfying the triangle inequality.
Metric TSP contains the following properties:
- nodes= (x,y,z); distance = d
- d(x,y) ≥ 0 (not negative)
- d(x,y) = d(y,x) (symmetric → undirected)
- d(x,y) + d(y,z) ≥ d(x,z) (triangle inequality)

Image reference: https://www.onlinemathlearning.com/triangle-inequality.html
This ensures that for a path a -> b -> c, replacing it with the direct edge a -> c will never increase the cost. It will stay the same or decrease.

Why finding the optimal TSP solution is infeasible in practice

Because it is NP-hard, it means there is no known polynomial-time solution for it.
There are multiple exact (optimal) algorithms, but brute force is the simplest and has time complexity of O(n!)
- Example: n = 40 n! ~= 8.1591528 * 10^47 ~= 10^47 tours required
- Imagine you can compute 1 billion tours per second: 10^9 tours
- 10^47 / 10^9 = 10^38 seconds ~= 3 * 10^30 years required to run it
- age of universe ^= 13.8 * 10^10 years
- It would take far longer than the age of the universe.
What I’ve shown above is called “combinatorial explosion”.
- For first city you have n options
- For second you have n-1 options
- And so on
- It is factorial: n * (n - 1) * (n - 2) * ... * 1 = n!

How to solve something that requires this amount of time?

As mentioned, it would require literally more time than is possible in this universe for a small n. To solve this type of problem, one possible approach is using approximation algorithms, which will provide you an approximate solution instead of the optimal one.

Heuristics in Computer Science

Hromkovič, J. (2004), Chapter 6, defines: ‘A heuristic algorithm in a very general sense is a consistent algorithm for an optimization problem that is based on some transparent (usually simple) strategy of searching in the set of all feasible solutions, and that does not guarantee finding any optimal solution’.
They must be much faster than the optimal solution, otherwise you would choose the optimal one.
Types of heuristics:
- Constructive: Build a solution following a set of pre defined rules.
- Improvement: Start with a feasible solution (any one), and apply successive small changes to improve it.
- Compound: Use both, constructive solution and then an improvement phase.

Approximation algorithms

If an optimization problem is NP-hard such as the TSP one, there is no polynomial-time algorithm to solve it, unless P=NP (something we don’t know yet).
- Optimal solution = the best solution using a non-approximation algorithm, for example, in TSP using brute force to test all possible tours would provide us for sure the cheapest Hamiltonian cycle.
- Suboptimal solution = an approximate solution, isn’t the optimal one, but is close to it.
What an approximation algorithm does is exactly this: instead of trying to get an optimal solution for an NP-hard problem until the universe ends, we use an approximation algorithm to achieve an approximate solution with much faster execution time.
k-approximate approximation algorithm = Means that it is no worse than k times the optimal solution.
- for minimization: optimal = 1; 2-approximate = 2 (2*opt)
- for maximization: optimal = 2; 2-approximate = 1 (1/2*opt)
- As you can see, an approximation algorithm is never better than the optimal; otherwise it would be the optimal one.
- It can even be equal to the optimal solution in some cases (but not always).
Note: To develop approximation algorithms we generally use heuristics (defined in the prerequisites).

Optimal solution for the TSP

There are many optimal solutions, all of them are too slow since this is an NP-hard problem.
We call brute force solution a solution that relies on exhaustive search.
The one I'll show you today is the Branch-and-Bound solution, that consists in backtracking plus pruning unnecessary paths before opening them.
If you don't understand backtracking check this Github (Code) - Backtracking playground

Branch-and-Bound for Metric TSP:

Branch = check new paths (permutations)
Bound = check the upper/lower bound and cut if already worse to avoid unnecessary paths
- lower if is a minimization problem
- upper if is a maximization problem
We fix the starting position as 0
Then we start checking permutations, such as (01230, 02130, 02310, …).
If we can identify that, before reaching the end, the current path is already worse than our current best, we do not need to continue (prune), and we stop exploring this path.
1. Since TSP is a minimization problem, if our currCost is already worse than our bestCost (lower bound), there is no reason to continue exploring that path.
When we reach the end of a path, we return to start and check if currCost < bestCost

Branch-and-Bound code

// Time Complexity: O(V!)
// Space complexity: O(V)
unsigned int Graph::runTSPBranchAndBound(TSPState state) const {
  int pathSize = state.path.size();
  int vertices = getVertices();

  if(pathSize == vertices) {
    int lastUsedPos = state.path.back();
    unsigned int totalCost = state.currCost + getDistance(lastUsedPos, 0);
    return totalCost < state.bestCost ? totalCost : state.bestCost;
  }

  for(int i = 0; i < vertices; i++) {
    if(state.visited[i]) {
      continue;
    }

    // key diff from brute-force version
    int currDist = getDistance(state.path.back(), i);
    int newCost = state.currCost + currDist;
    if(newCost >= state.bestCost) { // cleaning unnecessary paths (prune = Branch-and-Bound)
      continue;
      // if I use a specific graph where pruning never happens, it becomes as bad as brute force because
      // it ends up exploring the entire search space without cutting any branches
      // fortunately, this is not the case in most situations
    }

    state.currCost += currDist;
    state.visited[i] = true;
    state.path.push_back(i);

    state.bestCost = std::min(state.bestCost, runTSPBranchAndBound(state));

    state.path.pop_back();
    state.visited[i] = false;
    state.currCost -= currDist;
  }

  return state.bestCost;
}

But it is still too slow. Since TSP is an NP-hard problem, we still require an approximation algorithm to get a faster, approximate solution for that problem.

Approximation Algorithm for TSP

The difference between a heuristic and an approximation algorithm is that an approximation algorithm has a proven bound on how far its solution can be from the optimal one.
For example, a 2-approximation algorithm guarantees that in the worst case it will return a solution at most twice as bad as the optimal one. This is proven mathematically.
There are multiple approximation algorithms for the same problem, and this also happens in TSP, where you can solve it using, for example, the MST double-tree algorithm, Christofides algorithm, and more.

The Nearest Insertion Solution (2-approximate algorithm)

Image reference: Nearest Insertion - (Rosenkrantz, Stearns, Lewis, 1974)
Code here - Graph::runTSPNearestInsertion()
- Time Complexity: O(V^2)
- Space complexity: O(V)

Running Time Comparisons

Just some examples, on a random computer of ours.

Optimal: time O(V!)

Branch-And-Bound is already 10x faster than pure brute force for the 11x11 graph. Even though both algorithms have the same worst case, since branch-and-bound prunes some unnecessary paths.
But as we can see, running it for 15x15 would already take too much time so we didn't.

Approximate: time O(V^2)

And obviously the approximation is much faster and has a worst-case 2-approximation guarantee, and in our files the worst was not 2 but only ~11.45% worse than the optimal.

Extra: Metaheuristic and Genetic algorithm for TSP

Metaheuristics in Computer science

A metaheuristic is a high-level framework with some guidelines to build a heuristic (abstract idea to solve high-level).
A Genetic heuristic is made of:
1. populations
2. select
3. crossover
4. mutate (small percentage)
5. improve
6. repeat
It still requires problem specific solutions, where we use heuristics, for example:
- crossover operator (e.g., EAX for TSP)
- local search heuristics (2-opt, k-opt, …)

Genetic Algorithm with Edge Assembly Crossover (EAX-GA)

It is a TSP heuristic algorithm that does the following:
Populations
- N Hamiltonians cycles: [(A→B→C→D→E→A), ham cycle 2, …, ham cycle N]
Select (parents)
- Choose randomly X pairs of hamiltonians cycle within your population
Crossover (Edge Assembly Crossover)
- Combine the pair parent1 and parent2 (both hamiltonian cycles) to generate a child hamiltonian cycle.
Mutate
- Here we select a small rate such as 5% of the generated children and we try to improve them by mutating
Local Search (apply one heuristic to improve)
- child = improve_with_2opt_or_LK(child)
Repeat N times until reaching the stop condition (time or iterations)
- Now you have a new population of children, you can even get some of the best parents to put in your population and remove the “worst children”.
  - read best as smaller cost and worst as biggest cost to travel
  - “Keep best solutions within parents and children and repeat.”
- And within this population, select, crossover, mutate, and improve with local search once again until reaching the stop condition.

References

Github (Codes) - TSP-Approximation-Algorithm
Michael Sipser - Introduction to the Theory of Computation, 2nd edition
Michael Sipser - Theory of Computation MIT
MIT OpenCourseWare - R9. Approximation Algorithms: Traveling Salesman Problem
Heuristics and Local Search (José Fernando Oliveira, Maria Antónia Carravilla – FEUP)
Abdul Bari - 7.3 Traveling Salesman Problem – Branch and Bound
Nearest Insertion - (Rosenkrantz, Stearns, Lewis, 1974)

Set Data Structure in C

João Godinho — Fri, 24 Apr 2026 23:11:51 +0000

In this article I will show how to implement a Set data structure in C using a hashtable, and discuss complexity, trade-offs, and possible improvements.

Prerequisites:

Basic knowledge of programming (logic, etc);
C syntax, allocating variables;
Memory management in C: pointers, malloc, free;
Basic understanding of hashing;

What is a Set?

A data structure that stores unique elements.
Same idea as in set theory in mathematics: no repeated values are allowed.

Why use a Hashtable?

A hashtable is a good choice for implementing a Set:
- insert, find, remove -> O(1) average
Collisions can happen, so we need a strategy to handle them.

Collision Handling (Chaining)

In this implementation, collisions are handled using a linked list per bucket.
Multiple elements that hash to the same index are stored in the same list.

Complexity

Let:
- m = number of buckets
- k = elements in one bucket
- n = total elements
Worst case:
- insert O(k)
- find O(k)
- remove O(k)
- iterate O(m + n)
- isEmpty O(1)
Average case:
- insert O(1)
- find O(1)
- remove O(1)
- iterate O(m + n) -> O(n) if m is constant
- isEmpty O(1)

Trade-offs and Improvements

Load factor not handled:
- I haven't handled load factor by rehashing since the focus is the Set itself.
- This can degrade performance as n grows.
- Improvement: dynamic resizing (grow/shrink).
Hashtable vs Balanced Binary Search Tree (BST):
- A hashtable is generally better for unordered sets, because it provides constant-time average performance and does not maintain order.
- A balanced BST is preferable only when worst-case guarantees or sorted order are more important than average performance.
- A set is an unordered data structure, so using a hashtable is preferable.
Time complexity comparison (insert, find, remove):
- Hashtable:
- Average case: O(1)
- Worst case: O(n)
- Balanced BST:
- Average case: O(log n)
- Worst case: O(log n)
To check load factor handling and hashtable growth using open addressing with double hashing:

https://github.com/godinhojoao/dsa-studies/blob/main/dsa-in-c/hashtable.c

How to Develop a Set in C

In this code:
- A hashtable with fixed size is used
- Collisions are handled with linked lists (chaining)
- FNV-1a is used as the hash function

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SET_LIMIT_SIZE 1000

typedef struct SetNode {
  struct SetNode* next;
  int value;
} SetNode;

typedef struct Set {
  SetNode** nodes;
  int currLength;
} Set;

// 32-bit FNV-1a
unsigned int fnv1a_int(int value) {
  unsigned int hash = 2166136261u;
  unsigned char* p = (unsigned char*)&value;

  for(int i = 0; i < (int)sizeof(int); i++) {
    hash ^= (unsigned int)p[i];
    hash *= 16777619u;
  }

  return hash;
}

int itemIndex(int value, int arrLimit) {
  unsigned int hash = fnv1a_int(value);
  return hash % arrLimit;
}

Set* initializeSet() {
  Set* set = malloc(sizeof(Set));
  set->currLength = 0;
  set->nodes = malloc(sizeof(SetNode*) * SET_LIMIT_SIZE);

  for(int i = 0; i < SET_LIMIT_SIZE; i++) {
    set->nodes[i] = NULL;
  }

  return set;
}

SetNode* createNode(int value) {
  SetNode* newNode = malloc(sizeof(SetNode));
  newNode->next = NULL;
  newNode->value = value;
  return newNode;
}

void insert(Set* set, int value) {
  int index = itemIndex(value, SET_LIMIT_SIZE);
  SetNode* currentNode = set->nodes[index];

  SetNode* prevNode = NULL;
  while(currentNode != NULL) {
    if(currentNode->value == value) {
      printf("set do not allow repeated values: %d\n", value);
      return;
    }
    prevNode = currentNode;
    currentNode = currentNode->next;
  }

  SetNode* newNode = createNode(value);
  set->currLength += 1;

  if(prevNode == NULL) {
    set->nodes[index] = newNode;
  } else {
    prevNode->next = newNode;
  }
}

int isEmpty(Set* set) {
  return set->currLength == 0;
}

SetNode* find(Set* set, int value) {
  if(isEmpty(set))
    return NULL;

  int index = itemIndex(value, SET_LIMIT_SIZE);
  SetNode* currNode = set->nodes[index];

  while(currNode != NULL && currNode->value != value) {
    currNode = currNode->next;
  }

  return currNode;
}

int removeItem(Set* set, int value) {
  if(isEmpty(set))
    return -1;

  int index = itemIndex(value, SET_LIMIT_SIZE);
  SetNode* currentNodeToDelete = set->nodes[index];

  SetNode* prevNode = NULL;
  while(currentNodeToDelete != NULL && currentNodeToDelete->value != value) {
    prevNode = currentNodeToDelete;
    currentNodeToDelete = currentNodeToDelete->next;
  }

  if(currentNodeToDelete == NULL)
    return -1;

  if(prevNode != NULL) {
    prevNode->next = currentNodeToDelete->next;
  } else {
    set->nodes[index] = currentNodeToDelete->next;
  }

  free(currentNodeToDelete);
  set->currLength -= 1;

  return 1;
}

int main() {
  Set* set = initializeSet();

  printf("== insert 10, 20, 30, 10 ==\n");
  insert(set, 10);
  insert(set, 20);
  insert(set, 30);
  insert(set, 10);  // duplicate test

  printf("== find ==\n");
  printf("find 10: %s\n", find(set, 10) ? "found" : "not found");
  printf("find 99: %s\n", find(set, 99) ? "found" : "not found");

  printf("== remove ==\n");
  printf("remove 99: %d\n", removeItem(set, 99));
  printf("remove 20: %d\n", removeItem(set, 20));
  printf("remove 10: %d\n", removeItem(set, 10));
  printf("remove 10 again: %d\n", removeItem(set, 10));

  printf("== final finds ==\n");
  printf("find 10: %s\n", find(set, 10) ? "found" : "not found");
  printf("find 20: %s\n", find(set, 20) ? "found" : "not found");
  printf("find 30: %s\n", find(set, 30) ? "found" : "not found");

  return 0;
}

References

JVM vs V8: How Java and JavaScript Execution Works

João Godinho — Sun, 12 Apr 2026 22:55:58 +0000

Introduction

In this post I’ll discuss the differences between statically and dynamically typed languages, interpreted and compiled languages, what the languages in each set have in common. I’ll also talk about JIT compilation, and in the end compare the V8 engine developed by Google, used in Chrome and Node.js to run JavaScript, and the Java Virtual Machine (JVM).

Concepts before the comparison

Programming languages classification about typing

Dynamically typed: types are determined at runtime.
Statically typed: types are checked at compile time, before execution.
Strongly typed: the language strictly enforces type rules and limits implicit type conversions.
- Strongly typed isn’t a formal term in CS. It is more of a spectrum describing how strict a language is with type rules. Languages with fewer implicit conversions are considered “stronger,” while those with more relaxed conversions are considered “weaker.”
- C is statically typed but generally considered less strictly typed compared to Java due to more permissive casts and lower-level type operations.
- Given this, we could say that Python is stronger than JavaScript when talking about typing, since JavaScript does multiple uncommon type coercions such as 1 - "4" = -3

Programming languages classification about execution model

Compiled language: also called ahead-of-time (AOT) compilation, is when the source code is translated into machine code or some lower-level code before execution.
Interpreted language: source code is directly executed by another program.

General characteristics of each language based on their "classification"

Generally, compiled languages have characteristics such as static typing, strict type checking rules, and fewer type coercions. On the other hand, interpreted languages are generally dynamically typed.
Furthermore, compiled languages are generally faster than interpreted ones because interpreted languages add runtime overhead by doing type checks (dynamic typing) and other runtime checks that are done ahead of time in compiled languages. There are also other compile-time strategies to achieve performance optimizations.
There are advantages for both statically/dynamically typed languages:
- compiled and statically typed language: robustness because of type checks, performance.
- interpreted and dynamically typed language: productivity because of dynamic types and also portability, since it doesn’t have to be compiled for each architecture, if it contains the interpreter, it will run.

Hybrid model (Just in time compilation - JIT):

Today it is hard to give a strict binary classification for a language’s execution model (compiled or interpreted). We generally have a “hybrid” approach; even languages such as JavaScript that were historically interpreted are not interpreted anymore.

Reference: NodeJS Documentation
JIT is a technique to implement the execution model of a language and achieve better runtime speed. Instead of simply compiling or interpreting, with JIT compilation we first interpret the language (JVM bytecode in the case of Java, V8 bytecode in the case of JavaScript) and analyze its initial execution. After that, we can identify hot paths, most-called functions, and the values they are called with. With this information, it compiles these specific parts of the code to machine code to achieve better performance (the JVM does it, V8 does it).
This is a good example of JIT performance improvement: Just In Time (JIT) Compilers - Computerphile (watch time 5:49)

Virtual Machine

Virtual machine: A software that acts as an emulator of a physical computer system.
- System virtual machines: Replicates all that is required to run an etire system, with its own OS.
- Process virtual machine (where JVM is located): Also called application virtual machine, because it is used as a single process in the OS that provides a high level abstraction to run compatible languages in any computer architecture since the Process VM abstracts the compilation process to that specific computer architecture. One example is the JVM, in which the developer don’t need to worry about the underlying hardware platform your code is running - providing portability (runs anywhere).

What is the Java Virtual Machine (JVM)

The technology responsible for making Java both OS and hardware independent by abstracting specific computer architecture machine code.
An abstract computing machine, with its own instruction set (like a real machine that contains move, load, add…). The JVM knows nothing about the Java programming language; actually, it understands only the class file format, which contains JVM instructions (bytecodes), a symbol table, and more auxiliary information.
The JVM contains a public spec of its bytecode (the class file format - example.class), and this JVM bytecode is generated by javac during the compilation of Java source code.
Note: Since it contains a public spec of its bytecode and is intended to guarantee long-term support, other languages can also compile to JVM bytecode and enjoy the advantages of not worrying about the underlying computer architecture, having much more portability than with AOT compilation.

Image reference: Wikipedia

What is V8 JavaScript Engine

An engine that executes ECMAScript and WebAssembly specifications and handles memory allocation, garbage collection, and more. It contains AST parsing logic, an interpreter (Ignition), an internal bytecode, JIT compilers, and more specific logic to run the source code.
Why is V8 an engine and not a process VM like the JVM? The reason is that, differently from the JVM, which contains a public spec for the bytecode it runs (generated by javac and other compilers), V8 takes source JavaScript code (not lower-level code like bytecode) and uses Ignition to generate its bytecode. It doesn’t contain a public spec of its bytecode and doesn’t guarantee long-term support for it. Although V8 works similarly to the JVM to execute code, it contains important differences.
- JVM: abstract definition of a machine that contains its bytecode spec, instruction set, and more.
- V8: real implementation of the execution model of ECMAScript and WebAssembly specs.

Simplified execution model

Javascript with V8

image reference: Franziska Hinkelmann
JS source code -> AST -> Ignition (interpreter) compiles to bytecode -> Ignition executes its bytecode -> JIT hot paths with Turbofan or Crankshaft
image reference: V8 documentation

Java with JVM

So why people say JS is interpreted and Java is compiled if in practice both use JIT?

Although we saw that languages actually use a hybrid approach, we may ask ourselves: “Why do people call these languages interpreted or compiled if in reality it is not even true anymore?”
- Because they actually have strong reasons to do it.

1st: Traditional definitions vs real execution model

Code runs without an explicit compilation step = interpreted.
- In this case, JS source code is executed by V8, which first compiles the code into Ignition bytecode, then runs it through an interpreter, and uses JIT to compile JS hot paths (most used code) into machine code and execute them (hybrid approach). Even though it is a hybrid approach, the fact that execution starts immediately in a runtime is why we put it in the “interpreted languages bag.”
Code is translated to a lower level before execution = compiled.
- Java is compiled to bytecode using javac, and then the bytecode is executed in the JVM, which uses an interpreter and also JIT to compile hot paths into native machine code. It is also a hybrid approach because it runs bytecode and compiles hot paths to native machine code, but since there is a clear step where the source code is compiled into bytecode before execution, we put it in the “compiled languages bag.”

2nd: Historical design of these languages (Java and JS)

Because they were historically created like this, with these “style decisions” (compiled or interpreted) reflected in their syntax and way of working.
- For example, Java was designed as a statically and strongly typed language with a clear compilation step, focused on large-scale systems where correctness and structure before execution are important.
- JavaScript, on the other hand, was created as a lightweight scripting language for the browser. It is dynamically typed, making it more flexible and permissive, which was ideal for quick scripting and web interactivity, even if it can introduce more runtime ambiguity and errors.
- JavaScript is extremely permissive, allowing users to do unusual things to avoid breaking browser web pages (type coercion is a good example).

Which nomenclature to use for JS and Java and other languages (interpreted or compiled)?

Based on what I pointed out, the traditional nomenclatures (JS interpreted and Java compiled) are good choices.
But it’s important to understand how their execution model really works to achieve modern day performance, and also that we don’t stand still when it comes to programming languages’ execution models.
Note: Obviously, there are “pure” compilers or interpreters without this hybrid approach. GNU Compiler Collection - GCC, for example, is an ahead-of-time (AOT) compiler for C and other languages.

References

Consistency Models Part 1 - Linearizability

João Godinho — Mon, 06 Apr 2026 15:12:21 +0000

Distributed Systems

A system composed of multiple components running on different computers that communicate over a network to work together coherently.
“A distributed system is a collection of independent computers that appears to its users as a single coherent system.” - Tanenbaum and van Steen

Consistency in Distributed Systems

Consistency is a broader term that means multiple things depending on context.
- In database context (ACID): consistency means the system moves from one valid state to another, preserving all constraints and invariants (e.g. unique fields, foreign keys, business rules).
- Read-after-write consistency: what value you see when you read data after writes happen across multiple nodes, read last written data.
- Replication: Replica should be in the same state as other replicas (when? it can vary depending on your context).
As shown there are multiple definitions for consistency, and many to choose from.
You can achieve different consistency levels in your application.

Consistency Models

Consistency models are patterns regarding the different levels of consistency we can achieve in different aspects of a distributed system. For example, replication consistency, read-after-write consistency, and many others. People often informally call them “weak consistency” and “strong consistency”, but there are shades of consistency between these.
When talking about consistency models and focusing on data replication and read-after-write aspects, consistency is generally observed through reads, but it depends on how writes are handled.
- For read operations: the guarantees about which value is returned by a read in the presence of replication and concurrent writes.
- For write operations: the guarantees about how writes are ordered and propagated across replicas.
Each consistency model has trade-offs, and understanding them is crucial for selecting the best option for your business context. Today I'll discuss what is called “strong consistency”. I will not refer to it as “strong consistency” because this isn't a formal term. The formal one is linearizability.

Example where Consistency is a Point of Attention

Imagine a scenario where you have an e-commerce system built as a distributed system, similar to Amazon, containing multiple services.
Look at the diagram below to see these services:

Customer A accesses your e-commerce system and buys a product. Then OrderService creates an order, PaymentService processes the payment, and only then StockService updates the stock. But imagine that during the payment process, Customer B also buys the same product, and there are not enough units of this product in stock.
This is a scenario in which consistency becomes a problem that requires an architectural decision using the most appropriate consistency model for your context.

Business-Driven Consistency Trade-offs

Given the example above, you could imagine different requirements:

Prevent oversell:

“The better option is to avoid selling products we don’t have.” For this, you would prefer not to allow a purchase if the product isn’t available in stock.
- You avoid inconsistency by enforcing constraints at write time, typically using atomic operations.
- Atomic: the operation happens entirely or nothing changes. If it fails, no state is modified.

Allow oversell:

“It is acceptable to let multiple users buy because I can figure out how to restock later, but I cannot lose a sale.” For that, you would allow purchases even if stock is not available.
- You would then need to handle it with business options such as refunds or waiting for stock.
- As you can see, these are different consistency trade-offs. One is more strict, and the other is more relaxed. We cannot say one is better than the other, it depends on the context and business rules.

Trade-off: Availability vs Consistency

Sometimes you will want to favor high availability over consistency, but there are cases where linearizability is crucial. There is no fixed rule, you need to identify the specific parts of your system and their functional requirements (what the system must do) as well as their non-functional requirements (how the system should behave, such as performance, availability, and consistency constraints).

Linearizability - Multiple replicas behave as a single system

We have multiple servers and database replicas, but all operations behave as if they were executed on a single database. Every operation takes effect atomically from the user's perspective, not necessarily in the database internals. The focus is on client-observable behavior: when and what the operations return. We ignore the internal replication mechanism.
Atomic operations in distributed systems:
1. Either all nodes commit, or all abort.
2. If any node crashes, the system ensures the operation is aborted or completed safely.
The concept of linearizability is not restricted to distributed systems. It is also used in concurrent programming in general with shared memory.
Up-to-date value is returned for subsequent reads after one write. “Up-to-date” means that if write A finishes before read B starts, there is a real-time dependency to respect.

Image reference: Martin Kleppmann

Linearizability != Serializability

Linearizability: operations appear to execute in real time order. If A finishes before B starts, then B must see the effect of A.
Serializability: transactions produce a result equivalent to some serial (one-by-one) execution order. The order does not have to follow real time.

Examples of Linearizability with Real-time Dependency

Case1: A writes x = 1 → A finishes → B reads x = 1 (even for different DB replicas)
Case 2: (this is subject of common confusion - overlapping operations)
- A starts x = 1
- B starts reading x (while A is still in progress) → returns x = 0
- A finishes x = 1
- This is linearizable and valid, because the read overlaps the write, so the system can order it as: B → A
Case 3: (overlapping operations the other way is also valid)
- A starts x = 1
- B starts reading x (while A is still in progress)
- A finishes x = 1
- B returns x = 1

Ways of Achieving Linearizability

Typically requires synchronous data replication across multiple servers OR coordination mechanisms (such as quorum) to ensure necessary replicas reflect the latest write before reads are served.
Below there is a sync replication example, but it could be async using quorum or leader consensus.

And below there is a linearizability issue in which the write did not respect quorum, so when reading, client 3 got an invalid value (v0). The write happened from client 1 only to DB node A, so when reading from a quorum of 2 nodes does not work correctly, because B and C are not up to date with real-time dependencies, which are required for a linearizable system.

Image references: Martin Kleppmann
To solve the issue above following the quorum pattern, some solutions:
- Solution 1 - write quorum: set applied to a minimum quorum of N nodes - in this case 2 of 3.
- Solution 2 - read repair: still allow set only on one DB node, but once the server (client requesting data) identifies in a get request that a node has stale data, it will resend a set with the newest data to all nodes containing old data and will wait for at least one DB node to acknowledge.
  - In our case, client 2 on the get request would identify that node A is up to date and node B is outdated, then would send a set request to both B and C and wait for at least one to respond.
We will discuss more about practical implementations of consistency models such as quorum in further articles.

Use cases of Linearizability:

Systems that require strong consistency guarantees where operations must reflect the most recent completed write. Examples: banking/financial systems (you don’t want stale balances when updating accounts), flight booking systems (you don’t want multiple people successfully booking the same seat).
- no stale reads after a completed write
- strong ordering of operations
- correctness under concurrency

Linearizability Pros and Cons:

Trade-off: serving up-to-date data, but with higher latency and coordination cost. This involves a trade-off between consistency and availability.
Pros:
- No stale data for completed writes, reads always see the latest completed value.
- Simpler application logic in some cases because there is no need to handle read conflicts or inconsistent states.
- Guarantees correctness in concurrent systems even when many operations happen at the same time.
Cons:
- Higher latency, since writes (and sometimes reads) require coordination across replicas.
- Lower throughput, because coordination limits how many operations can be processed in parallel. Higher latency also contributes to reduced throughput.
- Reduced availability, because operations may block or fail if enough replicas are not reachable.
- More complex infrastructure, since it requires coordination protocols (e.g., leader election, quorum, consensus-based replication).

Linearizability Common Mistakes

A strongly consistent storage layer can still be part of a system that serves stale data if caches are involved. In that case, the database state is correct, but the overall system may return stale cached values, so it is no longer linearizable from the client’s perspective.
When a system implements linearizability, the cache must not break the guarantee that reads return the most recent committed write.

Exemplifying:

Think of a CDN or browser cache. With TTL, users may see stale data even if the database has the latest value. This is a freshness issue, not a consistency issue.
In distributed systems, even with linearizability, stale reads can still happen outside the database layer due to caches or read paths that bypass the primary source of truth.

In this case:
- Database: still linearizable
- Entire system (DB + cache + app): NOT linearizable
If you don't know cache basics, check my last article: https://dev.to/godinhojoao/cache-layers-in-modern-applications-563e

Final thoughts:

Trade-off between availability and consistency is important depending on your context. Since we can’t guarantee both, if some nodes are down, a linearizability model may become unavailable, but eventual consistency can still work even with some nodes down.
It is easier to ensure linearizability when your application doesn't handle multiple concurrent writes.
And probably you've noticed that:
- “As the system grows, despite the technology, you can’t rely on consistency.” - Dino Esposito
- You can build linearizable systems at large scale, but this highlights the cost in latency, coordination, and complexity, not to mention availability trade-offs. If it is required in your case, it is still the right choice.
Want to understand more about consistency models? I’ll continue developing content in this series about consistency models and later cover practical implementations of each model.

References

Cache Layers in Modern Applications

João Godinho — Sun, 29 Mar 2026 21:17:42 +0000

What is Cache?

Any temporary storage for copies of data in order to get faster responses. It can be related to hardware, where the CPU accesses caches (L1, L2, L3) to store copies of data from main memory and improve access speed. This happens due to multiple factors: the technology used to build caches (L1, L2, L3) is different from the one used for main memory, making it faster but more expensive, and it is also physically closer to the CPU, which reduces data transfer latency. The cache typically stores recently and/or frequently accessed data.
- Note: Cache is different from a Data Buffer, since a buffer is used as temporary storage not to get the most frequently and recently used data, but to manage the problem when we have consumers and producers operating at different rates.
In this post we will discuss primarily cache as internet technologies used to provide scalability, performance, cost reduction and more (focusing on system design). For example, web browsers cache HTML, images, and more after first load; cache of DNS records on the OS; CDN servers cache content to reduce latency. (We will not discuss hardware caches, DNS cache, DB caches and other caches, but they are also important)
Covered topics: the role of cache, cache layers, and how to combine them to achieve better performance and scalability.

Why to use caching?

Increase performance: Reading from memory is much faster than from disk, resulting in faster data access. Itsignificantly reduces database I/O and increases read throughput.
Reduce costs: Reduces database costs since cache can reduce database load, allowing you to reduce the number of DB instances, and if the DB service or VPS charges per throughput caching will also reduce costs.
Scalability: With in-memory cache we can handle application access spikes more easily, such as Black Friday. Caching most accessed data is crucial and ensures the app will handle the load without DB bottlenecks.
There are two main aspects about caching: performance and data freshness.
- We want to serve the fastest responses possible while still providing the required data freshness. This can vary depending on the application domain, for example, the price of a product should never be stale, but a blog post in general doesn’t require freshness.

CACHE HIT and CACHE MISS

HIT = data is in cache, use it from cache (faster load)
MISS = data isn’t in cache, save it to cache

Considerations before Cache layers

This nomenclature and numbering are not formal definitions. I am using them as a way to explain and make caching layers easier to understand. Don’t confuse this with memory hierarchy or OSI layers; the way I used this has nothing to do with either. It is only a naming approach to help understand different levels of caching.

Layer 1: Browser Cache (plus Concept of Time to Live)

A natural starting point is web browsers, one of the most used categories of applications in the contemporary world. As the name suggests, this cache isn’t handled by web developers but by the browser application itself, although developers can configure it correctly in their server responses, we will cover this topic below, first let’s understand this mechanism.
When a user first accesses a web page, the browser loads a huge amount of data, and to avoid loading it after every refresh it stores it on the user’s disk with a Time to Live - which determines how long the copy will stay stored in the cache - this copy can be deleted in some scenarios: time to live expires, using ETags, or the cache is full and needs to be replaced with other data.
As mentioned, it is provided by browsers, and is the best cache we can have since it is on the user’s computer, avoiding hitting our CDN servers or origin servers. But the developer needs to analyze it carefully since if you use it incorrectly you will face users with an outdated cache that you can’t clean programmatically because of misconfiguration.
It also works similarly on mobile applications, utilizing HTTP headers to configure cache constraints.

HTTP Cache Headers

It’s crucial to configure the cache correctly by setting the best matching HTTP cache headers for server responses.
With HTTP cache headers you can configure not only browser caches but other caches that we will discuss throughout this article. A key point is to understand that you can tell the cache layer (in this case the web browser) things like:
- 1 “DON’T CACHE THIS”
- 2 “CACHE FOR THIS TIME X”
- 3 “CACHE USING THIS TAG X, AND I TELL YOU IF SOMETHING CHANGED”
  - This last approach allows developers to update cache programmatically without the need for a TTL or the user manually cleaning the cache.
  - The browser sends a request with the ETag header before using data from cache, and the server can respond with one of the following: 1st - “304 Not Modified”, which means “use from cache” or 2nd - “200 OK”, which means “new response not from cache, update cache”
- Obviously there are multiple concerns about HTTP cache headers that I will not discuss here. For more about HTTP cache headers HTTP Caching 101

Layer 2: Content Delivery Network Cache

A CDN is a reverse proxy server that lives closer to end users, and can be used for many server optimizations, one of which is caching.
Everything that we’ve discussed about HTTP cache headers for browsers works almost the same here with an important difference: it works like a “centralized cache”, not on the user’s machine.
When talking about browser cache, you’ve ignored the following situation:
- Imagine that you have an admin user that accesses the /admin route, should you cache the response data for all your users? NO.
- If you still want to cache it, you need to better understand HTTP cache headers and set Cache-Control: private, which tells the CDN to not store it, only the web browser.

Layer 3: Reverse Proxy Cache (Infrastructure)

In a case where you have multiple server instances running in a single region, you can use a reverse proxy in front of these instances to load balance traffic among them and also cache their responses. It is also configured using HTTP headers.
It can be implemented using Varnish, Nginx, or other reverse proxies.
To understand better, read the section about reverse proxy in: How Content Delivery Networks

Layer 4: Application Cache

There are two scopes for this application cache: Local and Distributed
Local application cache: Only one instance has access to it (in-process cache)
- In the case where you have multiple instances, using local cache would introduce consistency issues, since each instance has its own local memory that is not shared.
- If you have a single instance, it’s clearly a good idea to use a local in-memory application cache, since it’s the fastest type of cache available.
- This reminds us of the idea of memoization, which is storing function results in memory for future use to improve computation speed. But here it is used for frequently accessed data.
- Ensure you manage it correctly to avoid excessive memory usage; for that, use libraries in your language, for example: NPM lru-cache - JS.
Distributed application cache: Used when you have multiple instances (Redis/Memcached)
- As mentioned, horizontal scaling requires more than a single instance server, and for that we need a shared cache, also called a distributed cache.
- It is slower than local in-memory cache since distributed cache adds network communication overhead. However, it is still much faster than querying the database directly.
Could we mix both local and distributed? Yes, by trying to achieve something similar to the hardware memory hierarchy, where we have different cache levels. However, it is important to take care with this approach since it can lead to consistency issues. If serving stale data for a short window is acceptable, this approach can work; otherwise, you should avoid mixing both strategies.

Last observations about these Cache Layers

People tend to think that only application cache exists, and also think that they can only use Redis/Memcached as distributed caches. This is an enormous mistake that can lead to low performance and high costs. Imagine having a multi-region application and a single Redis instance placed in one region, then you would pay too much latency for all other regions that do not share the same region as your Redis/Memcached.
Another thing is: not only static assets can be cached on browser and CDNs, you can and may cache your API responses.
The combination of these layers is the best case for application performance and scalability.

Start with the simplest caching layer that solves your problem. Browser caching and CDN caching are almost free. Application-level caching is the next step. Only add more complexity (write-through, stampede prevention, stale-while-revalidate) when you have evidence that you need it.

Caching caveats (mainly cache invalidation)

There are only two hard things in Computer Science: cache invalidation and naming things.

— Phil Karlton

Caching isn’t all about lightning speed, but also about using the best caching strategy to avoid serving stale data and crashing servers, especially at the application-level cache.
- If you don’t use the correct cache strategy, you will probably find yourself using too many resources to achieve what someone who knows cache strategies and when to use each can achieve. This is not the main topic of this article, but a discussion for a future one.
- You can serve stale data by not updating it in cache when it is necessary.
- You can crash your server in several ways with misuse of caching:
  - A hot key suddenly becomes invalid and then multiple DB calls happen at the same time to revalidate cache.
  - If you are using a local cache solution in your origin server that keeps growing indefinitely and consumes all your RAM.
  - Distributed cache failure: your entire cache cluster goes down and now all traffic falls back to the DB.
One example of misuse of caching is: using a high-cardinality cache key that is never reused: user:{timestamp}
- Congrats! By doing this you now have only unnecessary extra trips that always result in a miss: cache read -> miss -> db -> cache save
There are multiple things to take care of when using caching and multiple strategies to consider, but it can be a game changer for your application if well set. Stale data issues tend to be the most frequent ones. Also, never forget race conditions and other common issues that will be discussed in a future post.

References

How Content Delivery Networks Work

João Godinho — Wed, 25 Mar 2026 03:15:41 +0000

Introduction - Content Delivery Network

CDNs are important because they improve performance, scalability, availability, and reliability of services. Understanding what they are can help you not only work with them but also apply their ideas to solve similar problems in your own reverse proxies or infrastructure.
Short history:
- Before CDNs, websites depended on single origin servers, causing high latency and outages under traffic spikes. In the late 1990s, Akamai introduced distributed caching and routing users to nearby servers, selling it as a premium acceleration service for large enterprises. With the rise of video platforms like Youtube and Netflix, CDNs became essential to handle massive global traffic and streaming. Over time, pricing dropped and delivery became commoditized, so today CDNs compete mainly through services on top, such as WAF, DDoS protection, TLS termination, bot management, API protection, analytics, and edge compute, not just content delivery.

Forward and Reverse Proxy

Since a CDN is a reverse proxy, we need to first understand what a reverse proxy is.

Forward Proxy

Normally called just “Proxy”, it is a server placed in front of client machines that intercepts their internet requests and communicates with external servers on their behalf, acting as a middleman.

Image reference - Cloudflare Learning

What is a Forward Proxy used for?

To protect the user's identity online: Only the IP of the proxy will be easily known, but the real IP of the user may be harder to identify. (e.g. avoid censorship from a tyrant government)
To bypass firewall restrictions: For example, when a college firewall blocks specific websites, a user can still access the proxy, the proxy accesses the website A, and forwards responses to the user.
To block access to certain content: Also used for the opposite as seen before, for example, a school network configured to connect to the web through a forward proxy can refuse to forward responses from specific sites.

Reverse Proxy

Instead of being a man in the middle between client and server, a reverse proxy acts as a man in the middle between a client and one or more servers. The client requests one server, but it first reaches a reverse proxy that forwards the request to one or more servers (to the real origin server).

Image reference - Cloudflare Learning

What is a Reverse Proxy used for?

Load balancing: For some cases we can't handle all the requests with only one origin server, and for that we use multiple origin servers in which we need to balance traffic across them. For that we use a reverse proxy as a load balancer.
Protection from attacks: With a reverse proxy the origin server doesn't need to reveal its IP, making attacks harder to make. And also implementing good security techniques in this reverse proxy.
Caching: There are cases where you have multiple services around the globe, for example, a Brazil Server and an England Server, but you have Reverse Proxies that forward traffic to the closest server. However, to reach the origin server every time you lose a lot of time, and for that you can cache responses in the reverse proxy closest to the user.
SSL encryption: Instead of doing SSL or TLS encryption and decryption in all your origin servers, you can do it with a single reverse proxy, freeing resources from your real origin servers.

TLDR: Forward Proxy vs Reverse Proxy

The difference is subtle and important. It is not only about where the proxy sits, but also about its purpose.
Forward Proxy: Sits in front of the client and prevents the origin server from communicating directly with the user. Client → Forward Proxy → Internet → Origin Server
- In front of client; Forward user requests to the internet
Reverse Proxy: Sits in front of the origin server and prevents the user from communicating directly with the origin server. Client → Internet → Reverse Proxy → Origin Server
- In front of our servers; Manage incoming traffic from the internet to our servers.

How to implement a Reverse Proxy?

You can use existent services such as NGINX, APACHE, and more.
You can build your own (really hard and probably you will not achieve same results).
You can use a CDN, but sometimes you will use both: a CDN for edge caching and a reverse proxy near the origin servers for caching, routing, security and load balancing.
- This is useful in scenarios where you want to take advantage of both strategies.

FINALLY: What is a CDN in practice?

A reverse proxy… Eh, actually, multiple reverse proxies spread across the globe.
Maybe you were expecting something bigger since CDNs solve huge problems, but that's it. The power of a CDN resides, obviously, in the software, but mainly in the infrastructure the company has: with redundant energy, multiple data center sites, and reverse proxies with superpowers such as caching, routing, load balancing, and edge networks.
“ A content delivery network (CDN) is a geographically distributed group of servers that caches content close to end users. A CDN allows for the quick transfer of assets needed for loading Internet content, including HTML pages, JavaScript files, stylesheets, images, and videos.” - Cloudflare Learning

How does a CDN work?

As mentioned, the main goal of a CDN is to deliver content faster, cheaper, and more reliably.
For this to work, a CDN is a network of servers linked together and placed in data centers, often near Internet exchange points (IXPs) - places where internet providers connect to exchange traffic between networks.
In summary: A CDN is formed by multiple servers placed in strategic locations closer to users, enabling high-speed data delivery, and adding more optimizations on top of it to provide better security, reliability, redundancy, and more.

When to use a CDN?

To reduce website load time: A CDN distributes content closer to users, caches the content following configured rules, and also applies other optimizations such as compression of transferred data.
- “Edge cache” derives from this → cache closer to users
To reduce bandwidth costs: Before using a CDN, your origin servers would handle all requests, but now the CDN caches it, so you spend less on bandwidth and hosting.
Availability, reliability, and redundancy: A CDN can also load balance traffic across several servers and apply a failover strategy to ensure hitting an available origin server, avoiding downtime.
To improve security: DDoS mitigation through a Web Application Firewall (WAF) and other optimizations.

Multi-CDN

Multi-CDN is an approach where you use multiple CDN providers to improve reliability, performance, and global coverage. Instead of just failover, modern setups dynamically route traffic to the best-performing CDN in real time. There are trade-offs, since providers differ in APIs, caching behavior, and reporting, making it more complex to manage. Still, Multi-CDN is standard for large-scale platforms where availability and performance are critical.
Only use Multi-CDN if you identify that a single CDN isn’t enough for reliability and availability: outages, geo constraints (one CDN doesn’t have strong presence close to your users), etc. Analyze all aspects before using Multi-CDN since it’s not easy to manage.

DEV Community: João Godinho

Tail Latency

Overview

What is p50, p99, p99.9, and other percentiles?

Why both Average and Median (p50) lie?

What is Tail Latency and What Causes it?

And Why Latency Variability Exists?

What is Fan-Out and Fan-In?

How Scale Amplifies Variability Effects

Can we kill variability?

1. Fix the node first

2. Within-request techniques

3. Cross-request techniques

4. Information-retrieval techniques

The naive fix and unnecessary waste of money

Measuring the Tail in Real Systems

References

Service Levels: Understanding SLIs, SLOs, and SLAs

Overview

What are Service Levels

Service Level Indicator (SLI)

Service Level Objective (SLO)

Service Level Agreement (SLA)

Visual Flow of Service Levels

Collecting Indicators

Standardizing Indicators

Which are Possible SLOs and How to Choose Them?

SLOS are Objectives, Not Ornaments

Final Tips from Google SRE book:

References

Requirements & Back-of-the-Envelope Calculation

Overview

Why estimation matters

Before talking about estimates

Functional Requirements

How to gather Functional Requirements?

Non-Functional Requirements

Some Important Categories of Non-Functional Requirements:

How to gather Non-Functional Requirements?

Back-of-the-Envelope Estimation

Data Volume Units (Powers of Two)

Latency numbers every programmer should know (Peter Norvig and Jeff Dean)

Estimation example

Conclusion

References

Deployment strategies

Overview

How to decouple release and deploy

Big-bang

Recreate

Rolling

Canary

Blue/green

Shadow

Pros and cons

How to choose

Read also

References

Jenkins CI/CD from scratch

Overview

What is Jenkins?

The pipeline

The job as code (JCasC)

Build agents

Setup in short

What it looks like

Running it on your own homelab

References

Heap Data Structure

Introduction

Binary Heap

K-ary Heap

Pseudocode for Binary Heap → MinHeap

Binary Heap Code

Time Complexity

Use cases and trade-offs

In place O(n) build max heap instead of O(n * log n)

Why is it O(n) and not O(n *log n)?

Building the sum for each approach to analyze it better

Use case for build heap in-place

In place `O(n)` build max heap instead of `O(n * log n)`

Why is it **O(n) and not O(n *log n)?**