Loading...
1 User should be able to convert long url to short url
2 User should be redirected to the original URL when using the short URL
1 Availability over consistency: the application requires highly availability for user experience. Eventual consistency should be sufficient for our use cases.
2 Scalability: easy to scale up and down to support the change of daily active users, as well as to support multiple data centers.
3 Fault tolerance: generated short url should be kept for the desirable amount of time. Data replication accross database instances can help us acheive this.
Write requests: 1 million url generated perday, 1000000/24/3600 = 11.6 QPS for write
Read requests: 100 to 1 read to write ratio.
100000000/24/3600 = 1160 QPS for read
Data size: assume short urls will be kept for 6 months on average, and average url size is 100 bytes, the storage required will be 1000000 * 100 * 180 = 18 GB.
1 URL shortening: [POST] v1/urlservices/short
with body
{
longURL: longURLString
userID: userIDString
timeStamp: UTC time stamp
}
return the short url for the given long url
2 URL redirect: [GET] v1/urlservices/shorturl
return the long url for http redirection, or 404 not found if the given short url is not valid or expired.
We will use key value data base to store the url mapping because it suits our need for availability and scalability. The key can be the unique ID generated for the short URL, the value can contain short URL, long URL, user ID and other needed information.
1 URL shortening service
2 Unique id generator
3 URL redirect Service
4 Cache
5 Key value store database with read only followers
6 Load balancer
The URL shortening work flow:
1 The user sends the request with long url and other information. The request is then routed by the load balancer.
2 The URL shortening service will first check for the given long url and user, if a short url is already generated in the database (possibly through bloom filter with false positive).
3 If the URL is already generated, then update its expiration time and return it to the user.
4 If the URL is not ready, the Unique ID generator will be invoked and a new unique ID will be returned for the given user/long url combination.
5 Convert the ID to short url with base 62 conversion and create a new data base row with id, short url, long url and other information like user id, timestamp, etc. Invalidate or update the cache with the new short url and return it to the user.
The URL redirect work flow:
1 The user sends the request with short url. The request is later rerouted by the load balancer.
2 One available URL redirect service takes the request and check if the mapping is in the cache.
3 If the long URL is in the cache, return it to the user. If the long URL is not in the cache then check the database.
4 If the long URL is not in the database, 404 was returned. If the long URL is presented in the database, then the user is redirected to the long URL.
1 URL Shortening: we choose unique ID generator instead of hash collision detection because it is easier to figure out the next available short URL and satisfies our availability requirement. Base 62 conversion was used to convert the unique ID, which is a unique large number, to a short URL. A 8 character short URL can contain trillions of different unique ID, which will be sufficient to store the generated short URL.
2 Duplicate detection: we choose bloom filter to detect existing mappings accross database instances. Bloom filter will not give false negative answer to the question "if the short url is already there" , so it will help us for an efficient duplication check.
1) We use key value database as our main analytics database since it can handle a lot of traffic for writes. Since it is write optimized, it is a lot better than a relational database.
2) Read replicas take time to be updated, inconsistent results might be returned after a shorturl is generated, since we prioritize availability first and choose eventual consistence.
3) Cache invalidation policy is something to concern when using a cache to reduce the database query. We can also choose to prioritize the availability requiement and let the cache returns outdated results.
1 Load balancer can be a single point of failure, extra instances might be needed.
2 Extra instances for the services are available for handling failure cases, but we need to monitor the usage.
3 Cache node failure could result in lots of cache miss. We can use consistent hashing for the cache to minimize the impact of single cache node failure.
4 Hot spot issue could be a concern, and we need to monitor the usage for the need for potential scaling up requirement .
1 Handling cases when short urls expires or removed, for example regenerating the bloom filter for database periodically.
2 Add analytic services for the url shortening and redirection services usage, so we can make commercial use of the usage data.
3 Allow user to choose their favorite short url if it is not used.