System requirements

Functional:

Client provides a really long url or just an url. System associates the url with a shorter version.

When shorter version is accessed from browser, or any other mean like curl cli or programmatically, system redirects shor url to to the original version.

Redirect URLs must be short, under 16 characters max.

Non-Functional:

Latency accessing short url and providing redirect to a user client should be as low as possible and close to just accessing original url. No more than 2ms to resolve a URL. Redirect on the browser side is out of our control.

Shor url expiration mechanism should be added which would expire short url in 1 year. User can specify expiration shorter than this.

Capacity estimation

System must be able to serve up to 10000 concurrent requests while maintaining latency standard.

One associative record should allow for 2048 bytes for a long url and 16 bytes for the shortened url id.

Extra 64 bit integer field for the clicks counter.

We do not allow more than 10 requests per second per url_id, throttling with 429 response.

API design

API will consist of creation endpoint and resolution endpoint.

POST /shorten

form urlencoded, or json body:

{ "url": "", expires_at: }

response 201:

{ "short_url": "/urls/", "authentication_token":"" }

PUT /shorten/

Header: x-auth-token:

Response 200

GET /urls/

Response 302, redirect to

GET /urls/

Response 404, Not Found

{"error":"the requested url has not been found"}

GET /urls/

Response 429, Throttled

{"error":"your request has been trottled"}

Database design

Database is SQL table will contain columns:

primary key, string: url_id, indexed

long_url, string: unindexed

authentication_token, string

expires_at, string

database will be partitioned by url_id hash allowing to reduce latency and balance the load. in addition subpartitions can be added whcih would partition by range(expires_at), so that partitions with expired urls cold be detached and deleted eventually.

Redis cache layer could be introduced in order to reduce latency further.

High level design

Load balancer as an entry point. Service to be deployed in either ec2, ecr or kubernetes in order to allow ease of services disposal and reinstantiation. Service will be serving HTTP API. Service will depend on cache layer Redis, deployed as a cluster of main and read replica. Cache will be a writethrough with TTL of record equal to 24 hours, assuming link will be "popular" for max of this amount of time for sure and then later on cache would refresh from db and will be available again.

Cache key is url_id, value url to redirect to.

Rmq queue to be introduced whcih will get event with url_id enqueued upon user uses the short url. Databases counter will be updated for the url_id in the event. Each event == 1 click, so that counter increase could be increased. In case of kafka bonus will be that statistics for the topic retention period will be available without quering main db.

Url will not be served if it is expired, clicks are not counted.

Expiration mechanism. Worker will go through the existing partitions which contain expired urls and delete the partitions altogether.

Request flows

create short url flow

• User initiates request and hits load balancer.
• Load balancer throttles if too many requests are coming from the same IP.
• Load balancer passes the request to one of the service instances.
• Service instance does a request to the db via writethrough cache.
• If DB is not available(maintenance?), retry occurs.
• If cache is not available, we still update db, but raise an alert if this happens too often, as it may indicate larger issue with caache.
• Response is sent back to the client

access shorten url:

• User initiates request and hits load balancer.
• Service does read request to the db transparetly via cache
• If cache returns value it is served in the response.
• Otherwise read from database occurs and cache is updated.

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

Explain any trade offs you have made and why you made certain tech choices...

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

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