System requirements

Functional:

• Create Short URL
• Redirect Short URL

Non-Functional:

• High availability 99.9%
• High RPS per redirect 20k
• 200 RPS creating
• Read-intensive system
• Very little response time for redirect 10ms, 5 sec for create
• Strong Consistency
• Monitoring

Capacity estimation

1000 symbols utf-16 = 2000 bytes

1 short link + 1 big link, aproxximately its 2kb for one link

200 rps per second = 2 kb * 200 = 400 kb per sec

400 kb * 86400 = 34.5 gb per day

34.5 tb per day * 365 = 12.5 tb per year, not a lot

12.5 * 5 = 60 tb for 5 years

API design

CreateLink(linkText)

• in: original link

ReadLink(shortLinkText)

• in: short link

Database design

It will be key-value database for speed of reading requests, I will chose Redis as most popular

Also I wanna use value optimization if we see a lost of simular values but I don't think people will have a lot of simular links

Database sharded for id to balance read and write requests, we need at least 10 shards to balance 20k read rps. Sharding using virtual buckets to be flexible adding new shards.

Master - master replicas for each shard

We use shards for balancing reading because if we use replicas there will be too many copies that leads to too many costs

Also we need have LFU key-value cache for this database for 1TB is ok

Database structure

key - short link - max 20 characters

value - original link - max 2000 characters

High-level design

Main thing is database

I mentioned design of it previously

We will have master-master replicas and lot of shard to handle such read rps

Url Creator Service will fill DB, Redirector will read DB. Redirector can't read links before Url Creator create it plus links are permanent so we dont need locks

Also we can have one slave DB for more accessibility

We have load balanced on top then API Gateway all with several instances to handle RPS

What about geo, we will have copy of our Server in each geo but sync their databases in master-master way. Long time write, but it is ok.

Url Creator will call Link Generator Service to general short link part

Generator will use fast encoding algorithm, let's take base64 for beginning

Generator will check for collision by accessing database and will use 2 instead of 1 random numbers based on time to handle collision and create unique link

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

Trade offs/Tech choices

We have long time write but have strong consistency, we are ok, we are read intensive

We have excessive caches and Databases for read optimization

Failure scenarios/bottlenecks

If any replica fails other is master master and will handle Critical time when we fix it

Also we can add one async slave replicas for each shard for more availability

Any of our Services use state in DB so they are stateless and we can easily multiple count of instances

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?