Loading...
Optional:
High availablity, highly scalable system with low latency. Require strong consistency, which is strarightforward if we don't allow user to modify the existing short url to long url mapping.
Assume each user generates 0.1 url per minute on average, our DAU is 1M.
RPS is 10^7/60 * 0.1 = 1.5 * 10^5
~ 1.5 K writes/s
Assuming 10:1 read write ratio, would be
15 K reads/s
Each user generate 0.1 * 60 * 24 ~ 150 urls per day.
We have ~ 150 * 365 * 1M url ~= 50000* 1M ~= 50B urls generated per year
Long url ~ 100 bytes, short url ~ 10 bytes.
150 * 0.11 KB * 1M ~= 15 KB * 10 ^6 ~= 1.5 GB generated per day
~500 GB generated per year
2.5 TB for five years storage
{
method: 'POST'
body: {longUrl}
}
response: generated short url
{
method: 'GET'
}
response: origin long url
We could use a traditional SQL DB like Postgre SQL or My SQL, takes advantage of the auto-increment feature SQL DB has.
Primary key is the Row Id, column we store the generated short url and long Url. We build index on short url.
Key components:
API gateway, where we do load balance and service routing.
Cache between short url service to database. This could be used to cache top accessed short url.
SQL DB, is where we store the long urls.
Generate short url flow:
User made request to generate short url with a long url, we route based on the url to corresponding service, when insert in to the SQL DB, we use base64 to generate a 7 digits short url based on the new row id, then store the short url and long url in the new row.
The short url will be returned to client.
Newly generated short & long urls pair will be added to cache layer for faster access.
Fetch long url from short url flow:
User requested with short url, we firstly check if the short url exists in cache, if so, we return the cached long url with status code 301 (or 302). If not we looks up in the DB. If still not exists, return 404.
The API gateway load balancer is critical in the system as we can't afford all traffic to a single server to generate/retrieve urls.
For long url to short url scenario, we could use some hash func to generate hash (MD5, SHA-1) for long url and redirect based on the hash value. To avoid uneven traffic and hot node, we could use consistent hash and virtual nodes to minimize data movement when adding/removing servers.
For short url fetching long url we could load balance based on the last digit of short url. This way, we could divide the traffic to 64 node (short url generated using base64). We could have hot node problem, but from there, we could distribute even further by using the last two digits of the short url.
Another key factor for our short url generation is the auto increment feature of SQL database. This ensures we would generate unique shorturl. A single SQL DB would be a bottleneck for generating urls, to resolve, we could add multiple SQL DBs. And to avoid conflicting short urls, we could give each DB an id, which will be added as prefix to the shorturl. With this mechanism, it also make it easier when we fetch longUrl from shorUrl. The LB could distribute based on the prefix part to correspoding DB cluster first.
Cache is essential for faster longurl fetching. Based on the above LB approach, we could add cache between each service and DB. The cache is mostly a key value pair in memory cache like Redis/Memcached, store the top visited shorturls and evict based on LRU.
We choose base64 for url generation, this approach is easy to implement, and we could extend
We are using SQL DB here as the auto-increment id feature is useful for us to generate short url using base64. Meanwhile, it can't be auto-scaled as some NoSQL Key-Value DB like Dynamo. To support high write volume, we need to distribute traffic to multiple DBs. Adding prefix to short url could help to avoid conflicting short url across different DBs.
We will generate a new short url for any long url even if the long url has been generated before. This could be a waste of resources, especially when we have a lot of duplicated long urls. We could introduce another DB to store long url to short url mapping and check if long url has been generated. If so, we just return the generated short url. While it introduces additional complexity to duplicate and sync data, it would help to save a lot of storage in the long run. In addition, it would reduce write operations when user tries to generate short url for an existing long url.
For cache and DB, they could both went down in production. We could set up replicas. In case of outage, the replica could take over the traffic. We need to write commit logs in case outage happens before data is updated in replicas, so when the replicas need to go online, we replay the logs to ensure no data is lost.