1/11/2024 0 Comments Design tinyurl thushar royRaft and Paxos, for example, only works if the number of failed nodes is less than half the total number of nodes in the system. However if you ever need to work with those directly, an important thing to pay attention to is that they are not perfect. Afterall, they are quite complicated and sometimes difficult to understand. I won't get into details on how these algorithms work. Zookeeper itself uses a consensus protocol called Zab (which stands for Zookeeper atomic broadcast). There are several algorithms that can be used to get consensus, like Paxos or Raft. And in this model, consensus is possible. This is known as the FLP Impossibility.įortunately, in most of the systems in practice, we can workaround this issue by modelling them as "partially synchronous systems", that is, we can apply a boundary on how long it takes to send messages between servers. In fact, it has been mathematically proven that, in an asynchronous system (meaning a system where we don't know how long it takes for messages to travel between servers), there is NO way to guarantee distributed consensus. This is know as the distributed consensus problem, which actually is one of the hardest problems in Distributed systems. ![]() So let's try to simplify & generalize the problem: given a set of servers, how do we ensure that all servers agree on a value, even if the servers might fail randomly (the value in this case would be the range assignment). The only way to do that is to make all servers agree on which ranges have been given, and which have not. In this case, when one servers in the Zookeeper cluster fails, somehow the system needs to make sure that the others don't return a duplicate range. That is why when we design systems, we design for failure. Unfortunately, in practice machines do fail, and in fact, they fail all the time. I probably wouldn't need multiple servers either, one beefy machine might be enough to do the job. If I had the guarantee that my servers never fails, then I wouldn't need Zookeeper. it is resilient to failures).Īnd that's the gist of the problem. But how does Zookeeper do that?įirst of all, why is it so hard to generate a unique sequence? Afterall, I can use a single computer to keep increasing a counter, and that would be unique, right? In fact, that solution is mentioned by Tushar in the video, but later rejected, because the counter-generating server might fail (either the machine itself crashes, or the network might go down etc.), and Zookeeper, somehow, magically provides "high availability" (i.e. Instead of answering the question "how to generate a unique sequence?" (or sequence range, in this case), this solution simply says "I'll just ask Zookeeper to give me one". The reason I think this answer is unsatisfying is because, while it works, it simply shifts the responsibility of generating the "unique" part of the sequence, which, is the hardest part of the problem, to Zookeeper. If the each server has a unique range, then they are guaranteed to generate unique sequences. Each server would be in assigned only one particular range to work with, and Apache Zookeeper is used to coordinate the sequence range assignments. To summarize, the most sophisticated solution proposed in the video is to partition all possible short sequences into ranges, and use a set of servers to return a monotonically increasing sequence, which falls within a range. That being said, they are sort of unsatisfying. Tushar's proposed solutions are quite good and I think most interviewers would be satisfied with them (please watch the video before continuing to read this post). The main problem is the createShort() API: How do you generate a short sequence of characters that is unique among URLs (note that uniqueness is an important property, we don't want different URLs to have the same shortcut). The second one is easy, you simply need to do a lookup and return the long URL (or 404 if none exists). This video discusses a common developer interview question, namely, how do you design a service like TinyURL, which allows users to turn long URLs into short ones that are just several characters long ( ).īasically, a TinyURL-like service would have 2 main APIs: createShort(longUrl) and getLong(shortUrl). Recently I came across a Youtube video called: System Design : Design a service like TinyUrl, from the channel Tushar Roy - Coding Made Simple. ![]() How would you design a service like TinyURL or Bitly ?
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |