the way to calculate this, in my eyes, work like this. I will take a simple example: 3 characters, a,b,c (instead of 62), each URL will have 2 characters. We have (ab) (ac) (ba) (bc) (ca) (cb). This is basically Arrangements of 3 taken by 2 => A(3,2) = 3!/(3-2)! = 6 If we accpept also combinations like (aa) (bb) (cc) then we will add also those 3 unique possibilities meaning we have 9 possible arrangements, thus we have the formula: Total URL number=> A(n,k) + n Where in your case n=62 and k=1...7.

? Isn't it simpler with 62^n meaning 62 * 62 * ... * 62, with n times 62. As an example, for n letters I have 62 choices, for two letter 62 * 62, so 62 choices for the first letter and for each letter 62 choices for the next letter, so we multiply which is in short 62^2. And that can be extended for any n.

@@querela92 "Isn't it simpler...". Hmm..you want simpler or precise? "And that can be extended for any n"...actually it can`t. Let`s take a larger number and let`s see where your mistake is: We have 62 elements that will be taken by 7. Your calculus will be: 62^7 = 3.521.614.606.208 But in reality it will be 62 + A(62,7) = 2.478.652.606.142 This means you will end up paying for a space, transactions, cache, etc on a server larger that your really need with: 1.042.962.000.066. This is about 1.04 TB of data you will never need. This is the difference between mathematics and "let`s make it simple".

Exactly what I was thinking, thanks for the correction.

Great spot thanks for that!

Lol yeah, 1^62 = 1

Yeah, that's very correct. So, it's now like 62⁷! , so that we get the total number of ways it can be written. Still some insane number.

yeah this just confused me lol

etcd can be another one, simpler than zookeeper.

Great suggestions!

How would you handle collisions?

@@sixoclock406 For MD5, the probability of just two hashes accidentally colliding is approximately 1.47*10^-29

Appreciate it!

That, or pregenerate x urls in a shared queue and just pop one when needed..

that chance increases the more urls are stored. After only a year you'll have 31B urls stored. If you continue to generate a URL at random, you'll then have a 1/100 chance of a collision.

@@awepicness This is also assuming urls don't expire.

I suggest you look into the Birthday Paradox

Just adding a single character in length drops that probability to 1/620, random URLs definitely seem to be the way to go here, simplifying the design. That's a 4E-9 probability that you won't be able to insert a URL within three attempts, basically negligible. You can opt to fail the request after 3 failed insertion attempts and it wouldn't measurably impact your service's reliability.

Appreciate the support! Could I use this comment on the website?

@@TechPrepYTYes.

Thanks!! That's exactly what the aim is 👍

What happens if you want to add additional servers at a later point?

​@@mariusheller8231do the first two or more. You can update the existing servers to then also enforce the longer prefix

only scale those servers?​@@mariusheller8231

I like this, but wouldn’t this mean the state of “last generated url” is stored in-memory in the application servers? What happens when the servers are redeployed? That state would be wiped out and there’s no way for each server to resume from where it left off

@@mariusheller8231Presumably you'd have a way to change the ranges for each server later.

A salt could help with resistance, but cannot prevent collisions at a reasonable level. So you could never fulfill a request to create a new URL with an accidental collision.

Once you cut up the hash to the required length there is no longer any guarantee that it's unique. We are talking about a 1000 new URL's per second so "pretty robust" isn't going to cut it. Dropping that many keys seems like a strange solution, but even if you reboot a 1000 servers every day for a year, you still have more then enough keys left for years to come. But if it could be a problem, you could also ask for a range of 1 to 100.000 and lose a lot less. Also keep in mind that you don't actually lose the entire range, because some have already been used. You could also schedule a server to go down instead of just dropping it. That it will reboot once all keys are release. But still, I don't think it's really an issue to lose those keys. I do agree with the latency problem mostly being a factor on reads. That is when a user manually creates a new URL and has to wait a second after clicking post. But for generating links via an API the latency is important both on insert and read.

@@degosoft With hash there is no uniqueness guarantee anyway, this is only about collision chance and key distribution. That's why I mentioned collision management. So, by "pretty robust" I mean "robust enough for the most cases". Of course, there is no silver bullet, all solutions have pros and cons. I'm just talking the way I prefer to solve the problem in real-world applications. And there is one more thing about using tiny URLs in real-world applications: they often not intended to live forever. In some cases, shorter URL with lifetime, for example, one year, may better suit your needs. Since the information at the source URL will no longer be valuable at that point. In this case, reclaiming space with hashed URLs will be a bit easier, just the matter of removing old entries from database by creation date. Another advantage to this approach is ability to set any tinyURL length at any time, even by request parameter. And, of course, absence of failproof zookeeper cluster reduces structural complexity of the system.

@@configaddNothing is guaranteed, but the chances for a sha256 collision are so incredibly small that it's practically none existent. And the chances get even smaller when we only use URL's as the input. But if you discard 25 of the 32 bytes in the output to get to a 7 byte shortcode, then you increase the odds by a lot. And bytes aren't even useful, so we need to encode the output bytes to something readable first which makes the default length even longer and thus you drop even more precision. Don't get me wrong, hashing is great and I've used it a lot for similar projects. But if "SHORT" is te requirement then hashing is not the way to go.

Great comment! A single point of failure (SPOF) is one that causes the entire system to go down. So while you’re correct that if a server goes down while responding to a request, that request will fail. However, it is not a SPOF as the system will still be up, as if the user were to send another request it would simply be routed to a different server. Having clusters of servers could be a great extension to the system. However, it does introduce more complexity that could be argued is over engineering the solution without adding a significant improvement to the overall system. But as you already mentioned it’s all about tradeoffs!

That just sounds like DynamoDB with extra steps.

I think you made the assumption that web servers are limited to their own range for responding to GET short-url requests, but that isn't said anywhere. The zookeeper gives them a range of free IDs to use for shortening urls, but each web server can accept any existing short url and will contact a cache and if not in there, the database to get the long url. So, if a web server dies, retrying the request would just be delegated to another web server that will return the correct long url. Even for shortening, if a web server dies and you retry the POST, you'll get a new shortened url from another web server (with an ID from another range)

Thanks for the comment! It’s an interesting proposition alright. In terms of generating the short URL, that takes a negligible amount of time and so precomputing that wouldn’t have any noticeable impact on performance. Not sure I fully understand the second part of the comment. Are you suggesting storing all the short URLs on a single server? By having all the short URLs on one server while convenient introduces a single point of failure and so thats why horizontal scaling is recommended. And then, once there is more than one server involved, a service for maintaining distributed synchronisation is typically recommended. It’s all about trade offs but typically a single point of failure is something you always want to avoid.

This doesn’t work well when scaling very wide. If we had 100 webservers, we’d be caching the data up to 100 times. A centralized cache is a much more effective solution

@@drewbrown1534 That makes sense, i think it would also be better to handle the LRU strategy that we may adopt to keep just the most used URLs in cache.

the whole point is to have a short url, 25 chars would be way too long

The only way to prevent collisions with the hashing method is to make the url longer which is counter-productive to the goals of the service.

It's fixed! Thanks for the recommendation!

It's on the roadmap!

Imagine going through chat history and seeing that link had expired 😢. Or embedded link stops working.

It's not discussed imo really clearly in the video. Here was my guess: If two incoming POST requests come in at the same time, and there are multiple web servers handling requests, it is possible for both to generate the same key and cause a collision. At a TPS of 1000, there is a high likelyhood of collision. Thus, the count cache and the zoo manager are ways to avoid this scenario of collisions between different webservers.

Yes, the text version (with the slides) of the tutorials will be available on the website soon!

One advantage that I *can* see over the method in the video, if I've understood it correctly, is that my method is more secure, it's pretty much impossible for someone to move characters around and find other URLs. Also, not that it matters much, but it also avoids wasting database space. I'm sure as a public service tons of people would be shortening links like google or the rickroll, meaning potentially thousands or even millions of short links would be wasted in our database when a single one would suffice, potentially slowing down performance.

I think this solution is assuming a random distribution or close to random distribution for inputs. This probably doesn't hold true

@@Squirvel That's the beauty of hashing functions, it doesn't have to assume anything about the distribution. If you change a single character, the whole hash is different.

Creating a shortened URL isn't necessarily idempotent.

Depends on what you want to learn!

Thank you!

Let's say you if you making url number 1,000,000 and convert in into base62 then it would be 4C92, if you are going sequentially I can tell that next number is 1,000,001, which I could predict and try the next link with 4C93. If you add random suffix, it gets harder to do that.

The count caches are distributed. It's essentially a random number generator... No more than 1 server instance can return a duplicate number

I think that’s the sound of his keyboard. He should probably invest in a microphone arm to keep it off the desk.

I’m curious, I can’t find anything online that states that you can’t have “create” in a REST API. Have you got any good sources on REST APIs that I can read?

@@Ziimzy Fielding's original paper doesnt mention everything that is not REST but it does tell you how. URLs are supposed to identify resources and you're meant to manipulate those resources through the verbs already provided. Beyond that, Googling for "verbs in url not rest" gives tonnes of info

@@Ziimzy You don't use the keyword create because by definition, if it is a POST endpoint, the fact that it is a POST type request then it is a creation.

@@alexiso2740 Ah I see, that makes sense

He mentioned in the beginning: 1000 new URLs created per second, 10000 queries per second.

No, just understand the key concepts of network like OSI stack and troubleshooting.