#Design tinyurl plus#

How do we shard the database in case there’s not enough space on one database instance? Shard based on hash(short url) using consistent hashing in nosql? Other than hash based partitioning, there’s also key range based partitioning, which is good for range scan, however in our case range scan efficiency is not useful, compared to that we probably want more even load balance between different partitions where consistent hashing is good at.A URL shortener is one of the most famous system design interview questions. It is scalable, we could easily spin up more app servers to handle more load, just add 1 more app entry on ZK and make the dedicated service assign a counter range for it. Performance is good since we don’t require extra look up into the database to ensure no duplicates. Technique 3 is highly available since we could have as many servers serving shortening request as possible. Or we could use a new server for the server, with a backup to avoid Single Point Failure. The dedicated service can just be a thread running on these app servers, we could use ZK to elect the service if the service is down. On startup, each app would consume its range stored in ZK and use the range for generating countersĪ dedicated service is responsible for watching changes in these range, once it’s consumed, the service is responsible for filling in new counter ranges servers/app1/range (counter_range str, consumed bool) (More details on the ZooKeeper configuration)įor example we could have data nodes like below in ZK I.e each app server asks for a counter range on startup and allocate short urls using this range, if the app server is down, simply ask for another range What if we have multiple counter nodes, each responsible for certain range of numbers?įor that we need ZooKeeper for coordinating assignation of these ranges The counter service would be a single point of failure, and we need to scale it if we have lots of app servers. Use a counter service to keep track of a counter, short url = base62(counter), insert into database Similarly, it’s possible to collide short urls here, and NoSql has no transaction Technique3

#Design tinyurl plus#

Multiple app servers generate the same short url for two different short URLs, NoSQL has no transaction?Īs the free pool of short urls saturates, generating URL will be slower as you’d need to constantly re-generate, plus the risk of race condition in NoSQL database Technique2įor a long URL input, short url = first 7 chars of mdb5(random), insert into database Here’s a good blog how Pinterest shards their databaseĪn article on Sql vs NoSql Techniques to generate URLs Technique1įor a long URL input, generate a random number and short url = base62(random), insert into database With relational db like mysql, shard-ing doesn’t come out of the box, so we’ll have to build our own services to maintain these shards and scaling them(like keep track of shards->machines config with ZK, etc) (There’re much more details about ACID than these definitions, like different levels of isolations, how are ACID implemented, etc, does ACID still hold on shared MySql servers?) Isolation: Transactions are executed as if they are carried out sequentially.ĭurability: Once transaction is committed it’ll remain committed even in case of system failure Prevent partial writes during outageĬonsistency: a transaction will bring the database from one valid state to another valid state, i.e database constraints will still hold Problem is collision if we only take 7 digits Choose Database Relational DatabaseĪtomicity: two database transaction are done as if they are done in one setting, transaction either succeed completely or fail completely. If we use base62 to encode the integer, we’re essentially converting a base10 integer to base62 integerĮach of the number from 0 to 350B-1 maps to a 7-char base62 number represented in string Then you can look further for things like traffic(QPS) load and get conclusion like we need multiple machine to handle the traffic(maybe 1GB/s etc) Algorithms for generating short urlīase62 (integer -> str) is this 1–1 mapping? These stats lead to conclusion like we should add scalability to our arch at some point, or like we should be sharding the database since 1 machine can’t hold this much data, although 3.5TB is pretty reasonable for 1 machine lol. To start designing, first we need to make assumptions so that we could make decisions based on the assumptions.ģ0 million * 2074 = about 2000*30 million = 600000000000 = 60GB Design a TinyURL service that takes a long URL and convert to short URL.