Pinned Tweet
No single data structure can build a fast LRU cache.
A hash table finds a key in O(1) but can't tell you which entry is the oldest, so eviction turns into a scan. A linked list keeps the order but can't find a key.
Put the two together: the hash table points to nodes of a doubly linked list. On a hit, you move the node to the front. When the cache is full, you drop the tail. Every operation takes O(1).
Python's OrderedDict and lru_cache are implemented exactly this way.
Read this week's article on @EngPolymathic
A hash table finds a key in O(1) but can't tell you which entry is the oldest, so eviction turns into a scan. A linked list keeps the order but can't find a key.
Put the two together: the hash table points to nodes of a doubly linked list. On a hit, you move the node to the front. When the cache is full, you drop the tail. Every operation takes O(1).
Python's OrderedDict and lru_cache are implemented exactly this way.
Read this week's article on @EngPolymathic
The 194th issue of the Polymathic Engineer is out.
This week, we discuss how to build a cache:
- The API contract
- Memory alone is not enough
- Building an LRU cache
- When fresher data isn’t better: the LFU cache
- Implementation
Read it here:
newsletter.francofernando.com/p/no-single-da…
4
77
879
37,391
Every time I recommend learning something, I get the same two answers:
"I don't have the time." and "it takes too long to get good."
Both are true, and both are irrelevant.
30 minutes a day is all you need, and almost everyone can find it. And yes, it will take years. Everything worth knowing does.
The only version of this that fails is the one where you wait until you have more time.
"I don't have the time." and "it takes too long to get good."
Both are true, and both are irrelevant.
30 minutes a day is all you need, and almost everyone can find it. And yes, it will take years. Everything worth knowing does.
The only version of this that fails is the one where you wait until you have more time.
4
1
16
1,523
One of the most underrated skills at work is also the simplest: give people your full attention when they talk to you.
Phone face down. Laptop closed. Look at them, ask a question, stay in the conversation.
It sounds obvious, but in most meetings half the room is typing. Being the one person who is actually present is noticed more than you think.
It works at home too. Kids and partners notice even faster than colleagues.
Phone face down. Laptop closed. Look at them, ask a question, stay in the conversation.
It sounds obvious, but in most meetings half the room is typing. Being the one person who is actually present is noticed more than you think.
It works at home too. Kids and partners notice even faster than colleagues.
8
1
51
2,477
Every time you make your library more flexible, somebody has to pay for it. Not always you.
If you hide a dependency behind an interface, your code becomes simpler, but now all clients must implement this interface.
If you add hooks so clients can plug in their own code, you're running code you don't control. It can throw or block your thread for a second. You can wrap it in a try-catch, move it to a thread pool, and still wait for the slowest one.
The complexity doesn't disappear. The only thing to decide is where it goes.
Free this week on @EngPolymathic
If you hide a dependency behind an interface, your code becomes simpler, but now all clients must implement this interface.
If you add hooks so clients can plug in their own code, you're running code you don't control. It can throw or block your thread for a second. You can wrap it in a try-catch, move it to a thread pool, and still wait for the slowest one.
The complexity doesn't disappear. The only thing to decide is where it goes.
Free this week on @EngPolymathic
The 197th issue of the Polymathic Engineer is out. We discuss complexity vs. flexibility:
- The straightforward version
- Letting clients bring their library
- Hooks: running client code between phases
- Listeners: notify, don’t wait
- Picking your spot
newsletter.francofernando.com/p/the-complexi…
1
3
19
160,241
A tenth of a microsecond became a third of a second.
The Patriot system used an internal clock with a counter incremented every tenth of a second, and the software multiplied the counter by 0.1, storing the result in a 24-bit register. 0.1 has no finite binary expansion, so the register held a truncated value, short by about 0.000000095.
That is a tenth of a microsecond, and nothing to worry about for one tick. But the battery had been running for about 100 hours, 3.6 million ticks, and by then the computed time was 0.34 seconds off. The Scud was not where the Patriot looked.
The accuracy lost in a single operation is usually small. But if you compute a value that is the result of a sequence of operations, the error accumulates.
Nothing in the software was broken. Every step did what the format said it would do.
Free this week on @EngPolymathic
The Patriot system used an internal clock with a counter incremented every tenth of a second, and the software multiplied the counter by 0.1, storing the result in a 24-bit register. 0.1 has no finite binary expansion, so the register held a truncated value, short by about 0.000000095.
That is a tenth of a microsecond, and nothing to worry about for one tick. But the battery had been running for about 100 hours, 3.6 million ticks, and by then the computed time was 0.34 seconds off. The Scud was not where the Patriot looked.
The accuracy lost in a single operation is usually small. But if you compute a value that is the result of a sequence of operations, the error accumulates.
Nothing in the software was broken. Every step did what the format said it would do.
Free this week on @EngPolymathic
The 156th issue of the Polymathic Engineer is out. This time, we discuss what happens when you compute with floats:
- Adding floats
- Multiplying floats
- Comparing floats
Free to read here:
newsletter.francofernando.com/p/a-tenth-of-a…
2
0
10
1,473
Your computer can't store 0.2.
Binary can only represent numbers that are an integer times a power of two, and 0.2 isn't one. It expands like 0.00110011… but never ends, like 1/3 in decimal.
You can add bits and get closer, but at some point you have to stop.
A float is a sign, an exponent, and a fraction with a hidden 1 in front. The exponent buys you range. The fraction sets how many digits you can trust. The rest gets rounded.
Full article this week on @EngPolymathic
Binary can only represent numbers that are an integer times a power of two, and 0.2 isn't one. It expands like 0.00110011… but never ends, like 1/3 in decimal.
You can add bits and get closer, but at some point you have to stop.
A float is a sign, an exponent, and a fraction with a hidden 1 in front. The exponent buys you range. The fraction sets how many digits you can trust. The rest gets rounded.
Full article this week on @EngPolymathic
The 195th issue of the Polymathic Engineer is out.
This week, we discuss how floating-point works:
- Why the point has to float
- Fractions in binary
- The IEEE 754 layout
- Normalized, denormalized, and special values
- Rounding
Read it here:
newsletter.francofernando.com/p/your-compute…
4
3
19
1,887
Splitting matrix multiplication into smaller pieces doesn’t make it faster. Removing one multiplication does.
The naive way is O(n³).
Looking at the formula, you might think O(n³) is the lower bound for any matrix multiplication algorithm. That assumption is incorrect.
Divide each matrix into four submatrices of size n/2 x n/2. But each recursion step requires 8 matrix multiplications and 4 additions, and the time complexity is still O(n³), the same as brute force.
The Strassen algorithm divides the matrices the same way but combines the results differently. It needs only 7 multiplications at each step, and its time complexity drops to O(n^2.81).
This seems like a minor improvement, but it is significant for large input sizes.
The naive way is O(n³).
Looking at the formula, you might think O(n³) is the lower bound for any matrix multiplication algorithm. That assumption is incorrect.
Divide each matrix into four submatrices of size n/2 x n/2. But each recursion step requires 8 matrix multiplications and 4 additions, and the time complexity is still O(n³), the same as brute force.
The Strassen algorithm divides the matrices the same way but combines the results differently. It needs only 7 multiplications at each step, and its time complexity drops to O(n^2.81).
This seems like a minor improvement, but it is significant for large input sizes.
0
2
11
1,348
Your servers can report high availability while your clients can't reach them.
A network cut drops availability for the clients. The servers can still look fine because they were up the whole time.
What matters is the system the client can actually use.
A network cut drops availability for the clients. The servers can still look fine because they were up the whole time.
What matters is the system the client can actually use.
4
0
7
2,137
Sharding by hash modulo the number of shards works until you add a shard.
Redis Cluster spreads your data across multiple machines. Each machine with a piece of your data is a shard. You need to know where a key lives.
Hash the key and take it modulo the number of shards. Each key always goes to the same shard.
Add a shard and that breaks. A key that used to go to shard 1 might now go to shard 4. Moving everything would be a lot of work.
Redis puts a logical unit between a key and a shard, a hash slot. One shard contains many hash slots, a hash slot contains many keys. The modulo is done with the number of hash slots instead.
The total number of hash slots is fixed at 16K, so the hash result stays the same when you add shards. Adding a shard just moves hash slots from one shard to another.
Redis Cluster spreads your data across multiple machines. Each machine with a piece of your data is a shard. You need to know where a key lives.
Hash the key and take it modulo the number of shards. Each key always goes to the same shard.
Add a shard and that breaks. A key that used to go to shard 1 might now go to shard 4. Moving everything would be a lot of work.
Redis puts a logical unit between a key and a shard, a hash slot. One shard contains many hash slots, a hash slot contains many keys. The modulo is done with the number of hash slots instead.
The total number of hash slots is fixed at 16K, so the hash result stays the same when you add shards. Adding a shard just moves hash slots from one shard to another.
3
2
22
2,248
A system that never failed isn’t necessarily highly available.
Availability measures how resistant a system is to failures. The more a system stays operational when a component fails, the higher its availability.
It’s often measured in nines. A system that is 99% available has 3.65 days of downtime per year. At 99.9%, it’s 8.76 hours. At 99.99%, it’s 52.6 minutes.
But high availability is not only about specific numbers. Suppose you create a web application and deploy it to a single server in production. If the server and the network were always healthy, all the requests would be successfully processed.
That wouldn’t mean the system is highly available. If the server goes down, the whole system becomes unavailable.
High uptime values are not the goal of highly available systems, they are a by-product. Those systems have many nines because they are designed, implemented, and maintained that way.
Availability measures how resistant a system is to failures. The more a system stays operational when a component fails, the higher its availability.
It’s often measured in nines. A system that is 99% available has 3.65 days of downtime per year. At 99.9%, it’s 8.76 hours. At 99.99%, it’s 52.6 minutes.
But high availability is not only about specific numbers. Suppose you create a web application and deploy it to a single server in production. If the server and the network were always healthy, all the requests would be successfully processed.
That wouldn’t mean the system is highly available. If the server goes down, the whole system becomes unavailable.
High uptime values are not the goal of highly available systems, they are a by-product. Those systems have many nines because they are designed, implemented, and maintained that way.
3
0
14
1,765
Most backends talk to themselves like they're calling a stranger on the internet.
One user request turns into 5-10 hops inside the cluster, and every hop is JSON over HTTP. But you control and ship both sides. Nobody in there needs pretty field names, and you parse the same text again and again.
The question is just where the call comes from. Outside the cluster: REST. Between your own services: gRPC.
Read it this week on @EngPolymathic
One user request turns into 5-10 hops inside the cluster, and every hop is JSON over HTTP. But you control and ship both sides. Nobody in there needs pretty field names, and you parse the same text again and again.
The question is just where the call comes from. Outside the cluster: REST. Between your own services: gRPC.
Read it this week on @EngPolymathic
The 193rd issue of the Polymathic Engineer is out.
This is the last article on API design:
- What RPC really is
- North-south vs. east-west traffic
- gRPC and Protobuf
- When performance tips the scale
- Where GraphQL fits
- Can one service offer both?
newsletter.francofernando.com/p/your-service…
1
2
13
1,954
Every guarantee TCP gives you is paid in bandwidth and latency.
The IP protocol doesn’t ensure that the data you send arrives at its destination. If a router gets overloaded, it might start dropping packets.
TCP fixes that on top of IP. It breaks the byte stream into numbered segments, so the receiver can find gaps and duplicates. The receiver acknowledges every segment, and the sender transmits it again if the acknowledgment doesn’t arrive in time.
That’s how data arrives in order, no gaps. It’s also why TCP gives you lower bandwidth and higher latencies than the underlying network can provide.
But you don't always want that deal. Online games sample events several times per second and send them to a server. If an update gets lost, sending it again wouldn’t help. By the time it arrives, it’s obsolete.
There, TCP’s reliable delivery makes the experience worse. UDP drops all those guarantees, and you build only the ones your use case needs.
The IP protocol doesn’t ensure that the data you send arrives at its destination. If a router gets overloaded, it might start dropping packets.
TCP fixes that on top of IP. It breaks the byte stream into numbered segments, so the receiver can find gaps and duplicates. The receiver acknowledges every segment, and the sender transmits it again if the acknowledgment doesn’t arrive in time.
That’s how data arrives in order, no gaps. It’s also why TCP gives you lower bandwidth and higher latencies than the underlying network can provide.
But you don't always want that deal. Online games sample events several times per second and send them to a server. If an update gets lost, sending it again wouldn’t help. By the time it arrives, it’s obsolete.
There, TCP’s reliable delivery makes the experience worse. UDP drops all those guarantees, and you build only the ones your use case needs.
7
10
97
5,647
The most dangerous change to a published API is a rename.
An API is a running service, not a library. Every consumer gets what you deploy.
Rename one field and every client that parsed the old name dies on deploy. In reviews, it looks harmless. Someone reading the backend logic walks past it.
Put the layout in an OpenAPI file, diff it in CI, and fail the build on a breaking change.
An accidental rename should break a build, not an integration.
This week on @EngPolymathic
An API is a running service, not a library. Every consumer gets what you deploy.
Rename one field and every client that parsed the old name dies on deploy. In reviews, it looks harmless. Someone reading the backend logic walks past it.
Put the layout in an OpenAPI file, diff it in CI, and fail the build on a breaking change.
An accidental rename should break a build, not an integration.
This week on @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: newsletter.francofernando.com/p/the-most-dan…
1
0
13
1,874
DRY is about knowledge, not lines of code.
validate_age and validate_quantity can both call validate_positive_integer(min_value=0). Same code, two different business rules.
Most reviewers judge duplication by how alike the code looks but it’s a trap. Merge those two and they’re tied together.
Before you extract: if this rule changes, does the other have to? If no, it’s a coincidence. Merge them and the first change means splitting that function apart again.
validate_age and validate_quantity can both call validate_positive_integer(min_value=0). Same code, two different business rules.
Most reviewers judge duplication by how alike the code looks but it’s a trap. Merge those two and they’re tied together.
Before you extract: if this rule changes, does the other have to? If no, it’s a coincidence. Merge them and the first change means splitting that function apart again.
1
0
12
1,691
A binary semaphore is not a mutex, even if you initialize it to 1.
A mutex has an owner. Only the thread that locked it can unlock it. A semaphore has no owner. Any thread can signal it.
That flexibility is what makes semaphores useful for signaling, rendezvous and limiting why they’re easier to misuse. If you use a semaphore as a lock, you lose the check that catches a thread releasing a lock it never took.
If you need mutual exclusion, use what enforces ownership.
A mutex has an owner. Only the thread that locked it can unlock it. A semaphore has no owner. Any thread can signal it.
That flexibility is what makes semaphores useful for signaling, rendezvous and limiting why they’re easier to misuse. If you use a semaphore as a lock, you lose the check that catches a thread releasing a lock it never took.
If you need mutual exclusion, use what enforces ownership.
0
0
20
1,954
Your program never reads a file. It asks the kernel to do it.
The kernel is the only part with direct control over the hardware. A read is a system call: control goes to the kernel, the kernel does the work, and control comes back.
That's the price of a buggy program not ruining the others. Every bit of I/O is a round trip.
The kernel is the only part with direct control over the hardware. A read is a system call: control goes to the kernel, the kernel does the work, and control comes back.
That's the price of a buggy program not ruining the others. Every bit of I/O is a round trip.
3
3
47
4,680
Building an API is quite fast with modern frameworks: you can get a working endpoint up and running in minutes.
The nightmare starts a few months later, once consumers rely on the API. Every name you picked and structure you chose becomes hard to change or remove.
Much of the discussion around API design is userName vs displayName or PATCH vs PUT. The cost is coupling.
Once an API is published, you can refactor the backend logic as much as you want, but you can’t change the API itself.
You need to design the API from the outside in, starting from the consumer’s perspective.
I started a new series of articles on API design. The first one covers what makes an API RESTful, the Richardson Maturity Model, API standards, and how to design collections and errors that leave room to evolve. Free this week on @EngPolymathic
The nightmare starts a few months later, once consumers rely on the API. Every name you picked and structure you chose becomes hard to change or remove.
Much of the discussion around API design is userName vs displayName or PATCH vs PUT. The cost is coupling.
Once an API is published, you can refactor the backend logic as much as you want, but you can’t change the API itself.
You need to design the API from the outside in, starting from the consumer’s perspective.
I started a new series of articles on API design. The first one covers what makes an API RESTful, the Richardson Maturity Model, API standards, and how to design collections and errors that leave room to evolve. Free this week on @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:
newsletter.francofernando.com/p/you-can-refa…
7
2
41
3,450
The worst duplication doesn't look like copy-paste.
It's the same rule written three ways: a permission check in the API, one in the service, one in the database.
A diff won't catch it. Review won't either. Each version looks correct by itself.
Then you change the rule in two places, and production still uses the old one.
It's the same rule written three ways: a permission check in the API, one in the service, one in the database.
A diff won't catch it. Review won't either. Each version looks correct by itself.
Then you change the rule in two places, and production still uses the old one.
2
0
11
1,726