user calling our shorten service, inputting the long url, user token, getting the short url.
when user calling a valid short url with a valid user token in header, it will return 302 status code with the location header in response, and the browser can skip to the long url website automatically.
when user calling a invalid short url with a valid user token, a 404 status code would be returned.
when the user token is invalid, the 401 status code would be returned
two different users who share the same url can return different short url result because the user token is also taken part in the generation method.
Non-Functional:
To be flexible, the short url has expirations. it could return 404 status code if short url expires
Finding a secure and efficient hash algorithm to hash the long url to short.
Using retry method to tolerate collision error, for example, a random number can be added to regenerate the short url.
Finding a particular way to do the user auth. Such as oauth2 or access token way. Just make sure the service cannot be over exploiting and can identify the legal request.
Capacity estimation
storage: one url map, short to long, using 1kB at most, 1GB can satisfy the 10^6 items
access per day: suppose 10^6 a day
API design
POST /v1/url/share
body
url: string, the url to transform, original raw string, without url encoding.
success return format:
code: 0
message: "success"
data:
url: "<short url>"
GET {our service domain}/{path}
param:
path: short url path
return
302 or 404
Database design
using redis to store key-value pairs, with string structure
the key is short url which generated by our backend code, the value is original long url, and also the expiration would be attached.
depending on the hash algorithm result, we can split the short url in different redis database in some order. which mains if we know the short url, we can find which database it rests.
setting url with atom operation, that is to say there's only one process can finally set the short-long url mapping, and the other requests would return failed. The `setnx` operation would be perfect.
the data should be write to a file in case of the redis crash.
High-level design
for data security and duration, we can set another sync cronjob to move the data in redis, maybe in every night. It's optional.
Request flows
when user try to generate short url:
check if it's a valid user token in the header
if not, return 401 status code
user calling the api service above, the backend accept the long url, then it generate the short url, using the setnx method to set the mapping in redis. and then return the result.
user then try to access short url with valid token, then we try to find the original url using short url path, and return the result.
Detailed component design
A base62 algorithm to generate the short string for the long url, concluding A-Za-Z0-9 string.
Trade offs/Tech choices
using redis:
accessing more fast in performance, but it's less data persistent than database. It depends on our requirements.
once if the redis crashes:
redirect the request to other redis service in cluster
using backup sql database to restore the data in redis.
Failure scenarios/bottlenecks
concurrenty access the service will make the access to redis difficult, a redis cluster can help solve the problem.
also, if we want to smooth the access traffic, a message queue can be taken into consideration.
the hash algorithm may be complexed and easy to collide, using more simple and fast method to generate this.
Future improvements
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?
using more efficient way to deal with restful APIs where the path contains different params because maybe these kind of urls can take up more hash key slots.