Algorithms

As the World Wide Web became more popular all of sudden a server could receive way more traffic than it could handle causing the server to service requests slowly or to not be able to serve them at all1. An intuitive solution to this problem is to cache2 the content served by the servers and allow the clients to fetch content from the caches instead of going to the original server. Several clients communicate with the same cache servers which means that if client 1 fetches the contents for the page example.com, client 2 can fetch the same contents from the cache instead of going to the oirignal server if it decides to visit example.com as well. ...

The problem You are developing an application backed by a database, something happens and then several of your users try to access the same content. Several requests are sent to your backend at almost the same time and your backend hits the database once for each request to fetch the same data. Fetching the data only once If N requests asking for the same data arrive at the backend at around the same time, the backend could hit the database to fetch the data when the first request arrives and force the other requests to await until the data is fetched. When a response to the request sent to the database arrives at the backend with the data, the data can be shared with the requests that are waiting for it. ...

What is a log A log is just a immutable sequence of records wih strong ordering semantics that can be used to provide durability, replication and to model consensus. It is usually a 0 indexed file that new entries are appended to because expensive disk seeks can usually be avoided when appending to a file1. Not to be confused with the type of logs most people are used to: application logs that are meant to be read by humans although application logs are a degenerative case of the log we are talking about2. ...

Intro Token bucket is an algorithm that can be used to rate limit requests made or received by a service. How it works The algorithm is called token bucket because of the way it works: imagine we have a bucket with x tokens where each accepted request consumes one token from the bucket and a token is added back to the bucket at an interval. A bucket with 1 token that is refilled each second means the service accepts one request per second. ...

Replicated And Fault Tolerant Raft is a consensus algorithm for managing a replicated log. The authors claim Raft to be more understandable than Paxos because Raft separates the key elements of consensus Leader election Log replication Safety and enforces a stronger degree of coherency to reduce the number of states that must be considered. Raft also includes a new mechanism for changing cluster membership. What is a consensus algorithm Consensus algorithms allow a collection of machines to work as a coherent group that can survive the failures of some of its members. ...