Loading...
User should be able to submit an url to be shortened, receiving the shortened url
User should be able to access the shortened url and have the browser be redirected to the previously submitted url
If a shortened url has a collision with one that we already created, we can rehash to find another shortened url which may be unique.
As the query pattern is random access, we can scale more easily with a simple key-value schema.
Real-time analytics can be achieved at the service layer, using instrumentation on read and write apis. Metrics can be scraped from services through http calls and stored in a time series database for dashboard queries.
To handle url expiration, we create a default input option of no expiration. If expiration is set, then we can marked an expired datetime in the record and have a scan job to periodically scan through the database and clean records with expired time in the past.
We explicitly state that user authentication, custom urls, and url editing is not in-scope.
The system should have high availability, low read latency for redirects, and low write latency for url submissions. As we can serve this data with a simple get, we look for <10ms response time.
With redundancy, we can achieve >99.9% availability. As we can create this system using stateless services, we can easily scale out with load balancers and sharding at the storage layer to help achieve this.
Failure isolation: if writes are not able to be processed, reads should continue
Let's estimate that a url is 450 bytes max. A shortened url is estimated at 50 bytes max. So, creating a mapping requires 500 bytes max. 2 records for 1kb = 2000 records for 1Mb = 2M records for 1GB = 2B records for 1TB
Data growth:
If we assume 100:1 read to write ratio and 100k read rps, then we have 1k write rps. 1k write rps = 2.5B writes per month ~= 90 TB per 3 years. So the data growth is reasonable considering a sharded storage layer.
Read URL api:
GET https://url.ly/urls/{hash}
< 301 Redirect https://{real url}
Write URL api:
POST https://url.ly/urls?url={url_input}&expiration={expiration_option}
< { shortenedUrl: 'https://url.ly/urls/{hash}'}
Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...
URL table:
(hash) -> url, expiration_time
where hash is the primary key, provided to the Read URL api and returned from the Write URL api
Writes:
Client access the write URl api, providing the url to be shortened as a query parameter. This api is directed to the write URL service by the reverse proxy. The Write URL service creates a random md5 hash based on the content provided and a timestamp. The md5 output is then base62 encoded for easier use as part of a url as base62 encoding is alphanumeric only, thus not requiring escape characters when used as part of a url. The write URL service then attempts to insert this record (hash) -> url, expiration_time into the Sharded Key Value DB, which will fail if there is a collision on the hash as the primary key. If this happens, the write URL service repeats the hash creation process and insertion.
Reads:
The client access the Real URL api, providing the hash as part of the url. This api is directed to the read URL service by the reverse proxy. The read URL service checks the sharded key value db for a matching record according to the hash primary key. If it locates such a record, then it returns the url value as part of a 301 redirect. To optimize urls which are being read frequently, we put an In Memory KV store as a cache in front of the Sharded KV DB. With this, the read URL service first checks to see if the record exists in the In-memory store. If it does, then it returns. If it doesn't, it reads the database and writes the result to the cache, then returns
Expiration:
Scan job periodically goes through all records in key value database, deleting ones with past expiration time
See high-level design
We already mention the base62 hash algorithm in the high-level design.
The sharded kv db allows us to horizontally scale across the primary key of hash. It is also replicated for better availability. Periodic backups are made for disaster recovery
Due to the simplicity of the schema, we can use a key value database and avoid joins. Also due to the large data size, we would be best off using a NoSQL database, such as Cassandra.
While Cassandra is based on LSM-trees, which are not the best for random access reads, we have an in-memory store in front which will be very fast for random access. Cassandra still performs well for reading recently written items as the record will still be in the memtable or a recent SSTable. Cassandra scales well to a large data set size.
Try to discuss as many failure scenarios/bottlenecks as possible.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?