System requirements

Functional:

• user calling our shorten service, inputting the long url, 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
• for simplicity, if two users generated the same url and one is set failed, then he can see the other successful users redirect site.

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

• A base62 algorithm to generate the short string for the long url, concluding A-Za-Z0-9 string.
• 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:

1. check if it's a valid user token in the header
   1. if not, return 401 status code
2. 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.
3. 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

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

Trade offs/Tech choices

using redis:

• accessing more fast, but it's less data persistent than database

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?

• user cannot see other user's redirect with the same short url
• 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.