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...

Hash Generation

total usable chars - [A-Za-z0-9] = 62 chars
exclude confusing chars - 0, O,1,l = 58 chars
Base58 encoding = 58^6 = 38B URLs, this is sufficient for 5yrs, post 5 yrs the short URLs can be generated with 7 chars = 2T Urls

Short Url Generation

Approach 1 - Short URLs can be generated by hashing a unique combination of 6 chars out of 58 choosable chars which can produce 38B URLs for 5yrs which satisfies our requirement of 2B urls. In this case one single service generates a set of unique combinations of 6chars and hashes it to generate a short url. However this single service handling 300URLs/sec is reasonable, however incase it goes down we may have to bring another service up or keep a standby service ready. However the chances of it generating a duplicate is high and we will have to check for uniqueness - 300 RPS/sec to database which is not great. When the URL generation request goes to 1000/sec the no of uniqueness checks increases to 3000 RPS to database and so on
Approach - 2 : Standup 3 nodes for url generation and each generates its own hashes. In this case, we let each machine generate a unique number and compute hash by base58 encoding or base64 encoding. However we cannot avoid the confusing chars - 0, o, l, 1, doing this might waste cpu cycles and delay the generation. In this approach each node uses a Twitter-Snowflake Id which can be used to compute hash. By doing so, even if one machine goes, we can bring in another node without worrying about hash collision.

Twitter SnowFlake Id

A 48 bit id,

0th bit - sign byte
1 to 33 bits = a 32 bit timestamp
34 to 37 bits = 4 bit int represents machine id
38 to 48 bits = 8 bit int, a random number

Base 58 hashing a 48 bit id (6 chars) can generate 38B URLs and when we run out of unique hashes, change the epoch date of timestamp to a recent date say 01-01-2027 00:00:00, this will give another 38B unique URLs.

In this case we can horizontally scale no of nodes that generate unique short codes for urls.

Redirecting URLs

Browser of client ask for a long url in a head request which is lightweight and faster than a GET request. The request url contains the short code, this is looked up against a in-memory cache, if the cache misses the the redirection microservice goes to database and pull the url, add to cache with a TTL (LRU eviction strategy) and returns the URL in request header with 301 HTTP response code. We dont want to return 302 HTTP, since this gets cached into CDNs or ISPs. In this case we cannot mark the no of redirections performed for a short code.

Scaling redirection microservice

The redirection service will experience heavy traffic and when the url becomes viral, this will introduce spikes and redirection service goes under heavy load. Redirection service is stateless and we stand up multiple nodes of Redirection service (auto-scaling if lambda/function or auto-scaling pods in Kubernetes deployment) helps here.

Caching Short URLs

A Memcache is introduced to cache ShortUrl=LongUrl, memcache is distribute cache and helps in standing replica in multiple regions and syncs between the cache. We need a simple Map data structure here. This can helps in handling read spikes and viral urls

Data durability

The multi-region data redundancy is ensured to handle disaster recovery, the database nodes are deployed across multiple regions with asynchronous less than 1 sec replication. A master node takes the writes (300 writes/sec) and these gets replicated to 2 nodes making it 3 nodes in the database cluster. The 2 nodes are deployed in different regions. In case of master node going down, any of read replica can be promoted to master node within 1 sec. The master node can be brought up reclaim its membership.

Data Reliability

In each region, the data is replicated to 2 other nodes to ensure 3 copies exists in a region. This means total 3 regions with 2 copies each making it 6 copies of a Short URL record.

Data Eventual Consistency

the data is replicated asynchronously with in a sec, this means the URL generated at Reston, VA may not be available immediately on Europe region, however this is expected and 4xx error on a short URL is acceptable for upto 1 sec

Data Partitioning

Url record is partitioned by generated Short url and sortable by unique Id (twitter-snowflake id). This makes the data residency spread across multiple partitions in master and read-replicas, avoiding hot partitions. The cache also uses the same strategy making it spread across regions and partition data in each region.

Data Availability

Data in database is replicated to 5 other nodes, which are read replicas. These 5 nodes take in only reads and denies writes unless one of these nodes are elected to be a Master node. Only master node takes the writes. On top of database, a caching layer is introduced for fast lookups hence the no of queries to database is reduced.

Submissions

Displaying Solutions with Scores Ranging from 1 to 10

Submissions

Displaying Solutions with Scores Ranging from 1 to 10