System requirements

Functional:

• Create a short link
• Get Original URL

Non-Functional:

• High-availability
• low latency

Capacity estimation

• Assuming 200 requests per second to shorten URLs
• Assuming 20000 requests per seconds of fetch + redirect shortened URLs
• Assuming the TTL is 48 hours by default, to fit a mail campaign for instance, it represent 200 * 3600 * 48 records so about 35Milions active records in the DB.
• If we impose 500 bytes of max length for original URL it means we have a database size of 200 * 3600 * 48 * 500 so about 17TeraBytes.
• We would need about 5 to 6 Terabytes to fit the metadata.
• We should plan about 500MB storage for every Million of registred user.

API design

• createShortURL(AuthenticatedUser, orignalUrl, ttl=172800)
  • return a short URL
• redirectShortURL(shortURL): fetch original URL and redirect to it.
• listShortURL(AuthenticatedUser): fetch all created and not expired ShortURL for the authenticateduser
• UpdateShortURL(AuthenticatedUser, shortURL, newTTL): Update the TTL of the shortURL

Database design

a User table, and a URL table.

User:

UserId int

UserName str 32

UserEmail str 128

Password str 256

ShortUrl:

ShortURLID int

ShortURL str 8

OriginalURL str 500

User table contains everything related to the User and the URL table contain the mapping between ShortURL and Original URL.

High-level design

There is a load-balancer that redirect to API components.

API query a Cache and the Database.

The cache is handled by a redis

The database is handled by pgbouncer / patroni / haproxy and postgres with both a master and a replica.

A garbage collector handle removing the data from the db once the TTL is passed every hour. Every hour it would delete 200 * 3600 rows.

Request flows

• Client wants to create a short URL
  • Post an authenticated request to the API containing the URL to shorten.
  • Load balancer redirect to the most available API
  • The API generate a random string of 8 to 9 characters.
  • The API send the request to Pgbouncer (r/w connection) as a transaction.
  • The API once the transacton is commited send back the identifier to the client.
  • If the transaction failed, because of a collision in the name, then a new random string is computed and the transaction is replayed on the DB with the new identifier.
• Client wants to fetch an URL from a short URL
  • Load balancer redirect to the most suitable API
  • Api first query the redis cache and if it found a match it return early.
  • If not in cache, the Api query the database with an Read Only connection and return the result, and store the result in cache as well.

Detailed component design

APIs:

Apis are stateless and can scale horizontally if needed.

Cache:

Cache is handled by redis an in-memory and fast KV store. it can be scaled by using a redis cluster if needed.

Database component is handled by :

• pgbouncer to pool connection efficiently.
• Patroni to handle high-availabitlity, master/slave replication and automatic fallover.
• haproxy to handle routing of connections from pgbouncer to either master for read/write connection or any replica for read-only connections.
• Postgresql master and replica to handle the data

Trade offs/Tech choices

• API are stateless and very simple, so it can scale.
• Redis is used to speed up read only and can scale both vertically and horizontally with redis-cluster.
• Postgress can handle transactional connection the stack patroni / bgbouncer / haproxy can handle high-availability.

Failure scenarios/bottlenecks

• Bottlenecks can happen if the throughput of write put too much pressure on the master PostgreSQL
• A Scanning attack could also exhaust resources
• Garbage collector can also create tension on the DB if there is too much row to delete.

Future improvements

• we can use a redis-cluster to scale the amount of data the cache can hold.
• We can also shard the ShortURL table to divide the load on the shortURL table and scale more using citus.
• We can add a system of rolling bloom filter to avoid querying the database unnecessarily.