An alphabet is any set of finite symbols such as a and b. For example, the alphabet Σ = {a, b} is an alphabet that contains the strings that can be built by combining a and b and the alphabet Σ = {0, 1} is the an alphabet that contains the strings that can be built by combining 0 and 1. Symbols such as a and b put together to form something like bbaa are called strings. ...
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. ...
What’s a Bloom filter A bloom filter is a data-structure that can be used to check if a set contains an element. It uses way less memory than a conventional set data-structure by sacrificing accuracy. Example Say we are building a log-structured merge-tree, we can use a bloom filter to find out if the LSM-tree contains a particular key in O(1) time in most cases, the downside is that sometimes the bloom filter would say that the LSM-tree contains a key, but it actually does not and we would go searching for the value that’s mapped to the key and never actually find it. ...