silikonsaver.blogg.se - Tinyurl system design

Tinyurl system design how to#
Tinyurl system design pro#

Both the app server checks if the same short URL exists in DB or not and both of them insert mapping into the table. However both of them got the same random number, as a result, generate same 7 char short URL, i.e we have same short URL for different long URL. 0 for Chinese websites, 1 for American websites.What if you have two different app servers and at one point in time they convert long URL A and long URL B to a short URL. Use geographical information as the sharding key, e.g. Put Chinese DB in China, American DB in the United States. Short_url request -> get the sharding key (first byte of the short_url) -> search in the corresponding machine based on sharding key -> return long_urlĮach time we add a new machine, put half of the range of the most used machine to the new machine. Write long_url -> hash(long_url)%62 -> put long_url to the specific machine according to hash value -> generate short_url on this machine -> return short_url Each machine is responsible for the service in the part of the cycle. It doesn't matter how many pieces because there probably would not be over 62 machines (it could be 360 or whatever).

Tinyurl system design pro#

The pro way is put the sharding key as the first byte of the short_url.Īnother way is to use consistent hashing to break the cycle into 62 pieces.

So, we do not use global auto_increment_id. Here comes another question: How could multiple machines share a global auto_increment_id? Horizontal shardingĬurrently table structure is (id, long_url). What if we need one more MySQL machine? Issues: All the areas share a DB used to match the users to the closest web server (through DNS) when they have a miss on the cache. Improve the response speed between web server and user's browserĭifferent locations use different web server and cache server. We could put 90% read request on the cache. When getting long_url, search in the cache first, then database.

Tinyurl system design how to#

String shorturl = base10ToBase62(COUNTER) įor (int i = 0 i = '0' & c = 'a' & c = 'A' & c Web Core DB O: optimize How to improve the response speed? Improve the response speed between web server and database It could be the auto_increment_id in SQL database.Įlements = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" 6 bits could represent 62^6=57 billion.Įach short_url represent a decimal digit.

base62 Take short_url as a 62 base notation.

Overall, when urls are over 1 billion, there would be a lot of conflicts and the efficiency could be very low. When conflicts, regenerates the hash value(it's different because timestamp changes). use (long_url + timestamp) as the hash function key. We could take the first 6 chars of the converted string. Any hash algorithm could have inevitable conflicts. These two algorithms could make sure hash values are randomly distributed, but the conflicts are inevitable.

sha1 convert a string into 160 binary bits, generally represented as 20 bytes hex:.

md5 convert a string into 128 binary bits, generally represented as 16 bytes hex:.

OK, let's talk about the system algorithm.

Our algorithm needs AUTO_INCREMENT ID.

Doesn't matter because there are only a few codes.

How high is the system's scalability? SQL requires developers write their codes to scale, while NoSQL comes with them (sharding, replica).

For example, Memcached's QPS could reach million level, MondoDB does 10K level, MySQL only supports K level.

Does the system has a high requirement for QPS? NoSQL has high performance.

Do we need to use AUTO_INCREMENT ID? NoSQL couldn't do this.

Pursue development efficiency? Most Web Framework supports SQL database very well (with ORM).

Do we need rich SQL query? NoSQL does not support as many queries as SQL.

Does it need to support transactions? NoSQL does not support transaction.

GET: / Return OK(200), short_url is included in the data K: Data Access Step 1: Pick a storage structure SQL vs NoSQL?.

In general, this system is not hard and could be handled by a single SSD Machine. Through SN analysis, we could have a big picture of the system.

Service like Netflix may have storage issues. Storage is not the problem for this kind of system.

assume each mapping takes 100B in average.

10M new mappings (long URL to short URL) per day.

(Thousand level can be handled by a single SSD MySQL Machine) Storage

QPS: Since a day is 86400s approximately 100K.

Daily usage per person: (Write) long2short 0.1, (Read) short2long 1.

N: Need (Assume the system is not massive if you are not sure) QPS (queries per second)