Loading...
F1.Given a long URL, create an unique associated shorter URL
F2.Redirect to the original long URL when accessing the shorter one.
1.Availability: this service has to be highly available, especially for the redirection function.
2.Performance: it needs low response time. F2 has to have low latency, eg. less than 10ms, while F1 can be slower, e.g. less than 10s
3.Scalability: this service can handle a large number of concurrent requests.
200 requests per second for F1 (create short URL)
20,000 requests per second for F2 (short URL redirection)
I assume long URL are on average 100 characters, and the random portion of shorted URL is 8 characters.
Each long -> short URL conversion would include:
Each entry has 144B, we round it up to 256bytes
Per day, the service will generate 200 *86400 * 256B = 4.4GB of data
Within 5 years, its about 8TB
Considering some growth and buffer, we assume it would be 15TB.
But we need to take care of the CPU and bandwidth consumption.
We assume a normal server can handle 6,400 requests per second. Then, we need at least 20,000/6400=3.125 servers, we round it up to 5. But as there comes more and more requests, we need to ensure that this system can scale well.
1. POST /api/shortenURL(str long_url, user_ID, expiration_time=None)
Takes a long URL and returns a short URL
2.GET /api/redirectURL(str short_url)
Takes a short URL and returns the associated long URL
The primary data model is simple mapping from short URL to long URL,
we do not need complex relational query.
Strong consistency is required. Once a mapping is written, all readers should be able to read it.
We can use a key-value datastore, like a DynamoDB. It is horizontally scalable and performant, and can be configured to be strongly consistent.
The data model is:
Secondary indices are for additional features.
API Gateway forwards requests to corresponding servers, and provides TLS termination, DDos protection, etc.
We have two microservices. Shortening services specializes in creating short URL -> long URL mapping and storing it in the database.
Mapping services answers redirectURL calls.
Because mapping services need high performance, we introduce cache in two places:
1) inside the datacenter, with Redis cache
2) outside the datacenter, with CDN. this can be expensive, thus only store a smaller set of the most commonly accessed URLs
Both cache use Least Recently Used eviction policy.
shortenURL API:
Client sends the request. API gateway forwards it to shortening service. It creates the short URL-> long URL mapping and store it in the database
redirectURL API:
client sends request. If the mapping is found in a regional, nearby CDN, it is returned from the CDN. Otherwise, the request reaches API Gateway and the Mapping service. It checks if the mapping exists in Redis Cache. If it does, the mapping is returned. If not, it reads the Database.
Caching
Performance and scalability of redirectURL() API is extremely important. We employ two levels of caching.
At the closet location from the clients, we will have CDN storing short->long mappings for the most frequently requested URLs. For example, if a celebrity posts a short URL link in their Social Network post, this mapping shoud be in CDN. CDN can be hosted at Internet Exchange Points (IXPs), making the response time from client quite short. It has limited storage space, so it should store a small set of the most frequently accessed mappings. High volume of requests are handled by CDN, without even reaching the API gateway. It is quite beneficial from scalability & fault tolerance perspective.
In the datacenter, we employ a caching node, e.g. Redis. As we can install multiple Redis nodes with 100s of GBs of memory, it can store larger set of mappings, can provide faster access than to the database.
Both CDN and Redis Cache employ Least Recently Used eviction algorithm to ensure currently popular mappings stay in cache.
Partitioning
Database and cache should be partitioned for improved scalability.
Short URL is a good choice for a partitioning key because:
1) The services primarily look up cache & Database by short
We choose to use random character generation for shorten URL, instead of hashing.
Pros: no need to consider hash collide, and it is simple to evenly distributed among multiple partitions.
Cons: compared with hash, it needs more computing resources, but is manageable with /dev/urandom in Linux and other OS.
We choose latency over consistency. For example, with multiple Redis replicas for cache, we return "OK" to clients' shortenURL() requests when the entry is just written to the leader
All components in our system has failure risks. Therefore, we can construct a monitoring and altering system for them.
For some specific scenarios:
1) Mapping service failures can severely impact system performance. We need multiple nodes and can manage them with Zookeeper.
2) Cache miss can impact latency and may cause thundering herd problem. We can have replicas and can conduct backoff strategies on database calls.
3) When there comes more and more requests, the system may be blocked. To improve scalability, we use 2-layer cache for the mapping service. Besides, we add a message queue between the shorten service and database.
1.Users can custom the shorten URL with chosen alias and expiration time.
2.We need to improve security of this system. For example, prevent misuse and unauthorized access.
3.We can integrate with external analytics tools