EP3: An Algorithm Everyone Should Know!
In this episode of System Design Weekly, we dive into one of the most popular system design algorithms and explore how it works. Companies like Netflix, Akamai CDN, and Cassandra all use this algorithm which is also one of the most famous problems asked in system design interviews!
We also explore the Apache Thrift Compact Protocol developed by Meta (Facebook). Unlike textual serialisation formats like JSON and XML, Thrift allows for more efficient encoding, using less space while transmitting more information. Definitely a must know!
At the end, we introduce the brand new section of this newsletter the Tech Spotlight!
Consistent Hashing - An Algorithm Everyone Should Know!
Consistent hashing is an algorithm used to distribute workloads to servers in a distributed system. It works by hashing both the server IDs and request IDs and placing them on a ring structure called Hashring.
Using the Hashring, every request is assigned the server that first appears in the clockwise direction of the request.
The biggest advantage of consistent hashing is realised in a dynamic environment where servers come and go. While a simple hashing strategy would cause almost all of the keys to be re-assigned, consistent hashing only shuffles a fraction of the keys!
≫ Checkout my Medium blog for a deep dive
Apache Thrift Compact Encoding
Thrift serialisation protocol was developed by Engineers at Meta with the goal of developing an efficient and performant framework for cross-language service communication. The Compact encoding has been designed to minimize the size of encoded data by maintaining a schema for the data being encoded.
The encoded binary is simply a concatenation of data values, where each value is prefixed with a tag (an identifier for the field) and the data type of the value. One notable feature of Compact encoding is its use of variable-length integer encoding, which ensures that smaller integers are encoded using fewer bytes, further reducing the overall message size.
By relying on the schema and the binary encoding, a client can easily reconstruct the appropriate object, making the process efficient and straightforward. This compact format is especially beneficial in environments with constrained bandwidth or high throughput requirements.
≫ Read more about Thrift in this white paper
🔦 Tech Spotlight!
Welcome to a brand new section of my newsletter! Every week, I will be listing out one tech blog or article that stood out for me. Expect reads that will help you learn system design concepts through real-world deep dives from big tech firms.
So what are we reading this week?
HyperLogLog in Presto - Counting unique visitors on Facebook doesn’t seem to be much of a task at first, but when you’re dealing with billions of users, it’s a whole different story. Engineers at Facebook had to develop their own unique algorithm to estimate distinct values at massive scale. If you are curious about algorithms and optimisation at scale, this is a must read!
And that is it for this week! If you enjoyed what you read, consider clicking the ❤️ button below and leaving a comment.
See you next week in yet another release of System Design Weekly! Till then, happy learning!