ThePolymathicEng

Official account of the Polymathic Engineer newsletter, written by @franc0fernand0. Algorithms, distributed systems, and software engineering. Subscribe here:

[ThePolymathicEng @EngPolymathic]

This week in the 192nd issue of the Polymathic Engineer, we keep talking about APIs:

- Why a shared spec matters
- Generating code from the spec
- Validating live traffic
- Examples and mocking
- Versioning
- Catching breaking changes

link: https://t.co/2T80kGNyr8

[ThePolymathicEng @EngPolymathic]

The 191st issue of the Polymathic Engineer newsletter is out.

This weeks's article is about:

- API design and coupling
- What makes an API RESTful
- The Richardson Maturity Model
- Adopting an API standard
- Designing collections
- Error handling

Link:
https://t.co/tGs4rPvMbc

[Fernando @Franc0Fernand0]

Your latency benchmark shows a great p99. It might still be lying to you.

The most popular way to measure latency is to wait for each response before sending the next request, which inadvertently coordinates with the system being measured.

Think about a garbage collection pause. The system freezes for 100 ms, and a real workload would queue up dozens of slow requests. But the benchmark just logs a single one and moves on.

Your p99 looks great, but it’s a lie. This is known as coordinated omission.

I wrote the second article in my latency series that also covers where all that variance comes from, from CPU caches to garbage collectors, how latency compounds across services, and a small ping tool you can run to see your own network’s tail.

Give it a read in this week’s issue of @EngPolymathic

[ThePolymathicEng @EngPolymathic]

The 190th issue of the Polymathic Engineer is out.

This week we keep discussing latency:

- Sources of latency

- How latency compounds

- Measuring without lying to yourself

- Hands-on: measure your own network’s tail

Read it here:

https://t.co/NRfDEtW5QL

[ThePolymathicEng @EngPolymathic]

Good books to read

[Fernando @Franc0Fernand0]

Two books that shaped how I think about the software engineering job, and had a big impact on my career:

1. The Standout Developer by @RandallKanna is about getting in. The job hunt, the interviews, how to be the candidate people remember.

2. The Software Craftsman by @sandromancuso is about what happens once you’re in. Doing the work with pride, and building a career with autonomy, mastery, and purpose.

Both aged well and read even sharper now that so much of the code writes itself.

[ThePolymathicEng @EngPolymathic]

The 189th issue of the Polymathic Engineer is out.

This week's article is about latency:

- What latency is
- Units and the limits of physics
- Why latency matters
- The laws of latency
- Latency is a distribution

Read it here:

https://t.co/4yAz7GV6M4

[ThePolymathicEng @EngPolymathic]

system design articles

[Fernando @Franc0Fernand0]

If you want to become dangerous at system design, study these 10 systems running in production (save this) ↓

[Fernando @Franc0Fernand0]

What’s the difference between a blocking and a 𝐧𝐨𝐧-𝐛𝐥𝐨𝐜𝐤𝐢𝐧𝐠 algorithm?

The best way to understand it is to start with blocking algorithms and continue with non-blocking ones.

A blocking algorithm does one out of two things:

- performs the action requested by a thread
- blocks the thread until the action can be done safely

If a thread (B) acquires the lock first and gets suspended, another thread (A) must wait for an arbitrary time.

A non-blocking algorithm does one out of two things:

- performs the action requested by the thread
- notifies the requesting thread that the action can’t be done

If a thread (B) acquires the lock first and gets suspended, another thread (A) gets turned down.

The 𝐝𝐢𝐟𝐟𝐞𝐫𝐞𝐧𝐜𝐞 between blocking and non-blocking algorithms is in the second step. A blocking algorithm stops A until the lock is released, while a non-blocking algorithm notifies A that access is rejected.

The most common way to implement a non-blocking algorithm is by implementing the data structure using CAS operations. CAS stands for “Compare and Swap”, and is an atomic operation. It compares the value of a variable to an expected value. If they do, it gives the variable a new value. Specific CPU instructions typically support CAS operations. Therefore, no synchronization or thread suspension is necessary.

Using a non-blocking algorithm in a concurrent environment brings two main benefits:

- No thread suspension. Thread B has a lower latency. It receives a response immediately and can decide what to do next.

- No deadlocks. Thread B does not wait for the lock to release, and there is no possibility that a deadlock occurs.

[ThePolymathicEng @EngPolymathic]

The full article article about sweep line:
https://t.co/Z0dkFyFN0l

[Fernando @Franc0Fernand0]

Simple algorithms can solve complex problems.

Sweep Line is one of them.

I used it mainly in computer vision apps, but it applies to many contexts.

It looks like a geometry trick, but it is mostly a way to process events in sorted order.

Let’s consider a shop and all the customers’ arrival and departure times in a day.

Suppose you need to calculate the maximum number of customers in the shop at the same time.

You can solve the problem by creating 2 events for each customer: one for the arrival and one for the departure.

After this, you can sort the events and map them on a line representing the time.

Then, you process the events in order according to their times.

While going through the events, you can keep a counter. The counter increases for each arrival and decreases for each departure. The largest value of the counter answers the problem.

The sweep line part runs in O(n) time, but the overall algorithm takes O(nlogn) due to the sorting step.

But this is always better than the brute-force solution, which would require comparing the events for each pair of customers in O(n²).

This was just a simple example. But the sweep line is a crucial technique in computational geometry and can solve complex problems like:

- find the closest pair of points in a set
- find the area of a union of rectangles

[Fernando @Franc0Fernand0]

Hash maps and hash sets show up in interviews all the time.

The good news is that there are only two scenarios for using them.

1. Existence

Checking whether an element exists in an array is a linear-time operation.

Hash sets make it possible to do the check with amortized constant time.

Suppose you have an algorithm that needs to perform this operation M times.

With an array, the time complexity of this algorithm would be O(NM); with a hash set, only O(M).

2. Frequency

A hash map can be used to translate keys to integers. Each integer represents the occurrences of the corresponding key.

For example, suppose you want to verify if all characters in a string have the same frequency.

A hash map is the ideal data structure for counting character frequencies in linear time. You can check if the frequencies are unique with a single iteration over the map.

[Fernando @Franc0Fernand0]

Dangerous failures are not the ones that crash your app.

They are the silent ones.

Empty catch blocks, unawaited tasks, and exceptions printed to standard output are all different ways to lose exactly what you need when something breaks.

Good exception handling is not about catching everything.

It is about never losing information about a failure.

Full breakdown in the latest issue of @EngPolymathic

[ThePolymathicEng @EngPolymathic]

The 188th issue of the Polymathic Engineer is out.

This time, we discuss exception handling:

- A map of exceptions
- How wide should catch be?
- Designing failures into your API
- Anti-patterns
- Cleaning up
- 3rd-party code
- When failures go async

https://t.co/qMeXfvRshO

[ThePolymathicEng @EngPolymathic]

Great share

[Fernando @Franc0Fernand0]

If you want to see what running a system at real scale looks like, read this deep dive on how S3 works.

The numbers alone are hard to think about: 280 trillion objects, 100 million requests per second.

Three aspects particularly struck me:

• S3 is not a single system. It consists of hundreds of microservices managed by different teams, communicating via API-based contracts.

• The enemy is “heat” (i.e., load concentration), not storage capacity. Too many requests hit the same disk, the disk becomes overloaded, and everything slows down. Data is protected using erasure coding and replicated across numerous disks, and objects within the same bucket are deliberately distributed separately. A traffic spike from a single customer is spread across many disks rather than burdening just one.

• The storage node code was rewritten in Rust and formally verified. It’s rare to see formal verification outside academia and safety-critical niches.

Capacity planning is easy. Preventing the load from building up in one spot is not.

Link in the reply:

[ThePolymathicEng @EngPolymathic]

Networking

[Fernando @Franc0Fernand0]

Type a URL and press enter.

Before the first byte arrives, a dozen protocols have already done their job.

Here’s each one, in the order it runs: ↓

[Fernando @Franc0Fernand0]

HTTP client-side caching (explained simply in 3 minutes):

HTTP servers host two types of resources:

• Static → don’t change between requests
• Dynamic → generated on the fly

Since static resources don’t change, they can be cached to reduce load on the servers and lower response time for users.

HTTP allows caching these resources on the client side using specific headers. Here’s how it works:

1. The client requests a GET for a resource that nobody accessed before. The local cache intercepts the request. Since the resource is not there, the cache requests it from the origin server.

2. The server tells the client that the resource can be cached using response headers:
- Cache-Control → how long the resource can be cached
- ETag → identifies a specific version of the resource

3. When the client receives the response, it caches the resource.

4. Later, when the client makes the same GET request: If the resource is still valid, the local cache returns it immediately.

The server can still update a resource before it expires, so cache and server are not strongly consistent. This is usually an acceptable trade-off. The server can also force clients to fetch a new version by changing the ETag.

If the resource has expired, the client sends a conditional request with If-None-Match (the ETag it has stored).

- If the server has a new version → it returns it
- If not → it replies with 304 Not Modified, and the cache renews the freshness of the stored resource

You can also use Last-Modified + If-Modified-Since instead of ETag.

[ThePolymathicEng @EngPolymathic]

Great summary

[Fernando @Franc0Fernand0]

Every software developer needs to know how the HTTP protocol works.

Here are the 8 fundamental things you need to grasp:

[Fernando @Franc0Fernand0]

Most software engineers focus on how to read data from a cache.

But reading is only half of the battle.

Here are the 3 main cache writing strategies:

1. Write-through

The application writes to the cache, and the cache immediately writes to the database. This keeps cache and database consistent. No data loss if the cache crashes. The downside is higher write latency.

2. Write-back

The application writes to the cache. The cache writes to the database asynchronously. Better for write-heavy workloads: lower latency, less load on the database, more tolerant to database failures. The risk is data loss if the cache crashes before the data is flushed.

3. Write-around

The application writes directly to the database. Data only enters the cache when it is read. Good for data that is written once and rarely read (for example, real-time logs). The downside is higher latency when reading recently written data (always a cache miss).

The best strategy depends on the use case: write-back for write-heavy workloads, write-around when data is written once and rarely read.

[Fernando @Franc0Fernand0]

I just published a new article on logistic regression.

It is one of the most used classification models. If you have not used it, it returns a probability instead of a simple yes/no (spam 88%, not spam 12%).

It builds on the perceptron concept from another article and shows how the two are nearly identical.

The whole difference is one function at the end: replace the step function with a sigmoid, and “yes” turns into “yes, 88% sure.”

The rest of the article covers the log loss, training, and softmax.

Give it a read in this week’s issue of @EngPolymathic

[ThePolymathicEng @EngPolymathic]

The 187th issue of the Polymathic engineer is out.

This time, we dig into logistic regression:

- From the Step Function to the Sigmoid
- Probabilities
- The Log Loss
- Comparing classifiers
- The Logistic Trick
- The Algorithm
- Softmax

link:
https://t.co/KqRZjVneyG

[Fernando @Franc0Fernand0]

How Amazon DynamoDB works under the hood (in under 3 minutes):

1. Data model

DynamoDB has a flexible data model where data is saved in tables that hold items. Each item is made of attributes like numbers, strings, boolean, binaries, lists, maps, or sets. Because of this, you can model complex data relationships. Items are identified based on the partition key and the sort key. The partition key is mandatory, while the sort key is optional. You can use both keys to query data. For additional attributes, you need to create secondary indexes.

2. Scalability

DynamoDB has almost infinite scalability. This is done by spreading tables across several storage nodes. The partition key is hashed to find the node for each item. The mapping between items and storage nodes can change dynamically. Partitions that get a lot of requests are moved to storage nodes with more power.

3. Availability

DynamoDB stores each item on 3 nodes in different availability zones for redundancy. The nodes are kept in sync using a Paxos-based algorithm for consensus and leader election. You can always get to your data because DynamoDB saves the B-tree and write-ahead logs for each node in AWS S3.When a node fails, the leader copies the failed node’s B-Tree and Write-Ahead log to add a new node right away. Checksums are used a lot to make sure that data is correct.

DynamoDB has many strengths but isn’t perfect though.

First, a monolithic database might provide better performance for small data sizes.

Second, you need a good understanding of your access patterns to design tables and effectively get most of the benefits.