Loading...
POST /url?long=
Response:
Status Created
Content-Type string
Body
GET /:short
Response:
Status Redirect
should redirect to long URL
or
Status NotFound
if long URL not found for provided "short"
Load balancer.
Distributing the load and route requests to API servers processing appropriate subset of URLs.
API.
Should be stateless and cache most recently used short URLs for performance.
When new short url is required it should be found in database - records are either used or free.
If no free record is found, a batch of new records should be generated.
Short_urls should be generated in ascending order with maximum current length, when length is exhausted keys with length greater byt 1 should start. It resembles how array is reallocated when new value is pushed.
Database.
We should optimise it for reading and it should allow sharding for scalability.
# Load balancer.
For scalability we may introduce sharding by short URL prefix (4 symbols for example) using consistent hash algorithm.
If corresponding upstream is dead, any API should be capable to respond correctly.
# API server.
Should keep LRU cache with short URL - long URL pairs. Cache size should be limited.
Items in cache should have relatively small TTL - for when short URL is invalidated it should not stay in cache for too long.
# Generator service.
Its task is to keep some amount of "free" records in the database.
It can free existing records regularly if they are not accessed for too long. (But I won't describe this mechanism in details for now)
It should create new short_urls in the ascending order and increasing the length of short_url when capacity is exhausted. Starting length is 8. So system starts with 2^64 free short urls.
## Use Cases
### Create
API Server receives long_url.
If a record for this long_url is found in database it is returned in response.
If no record found server retrieves any free record. To eliminate race it should be performed in atomic database operation.
If no free record found API server requests Generator service for new record. This should not happen often so using single instance of Generator seems reasonable.
### Read
API Server receives short_url.
It checks LRU cache.
If record is not found it queries the database (for performance it may query replicas).
Either "Found", "Not found", "Internal error" response is sent.
# Database.
Record format: short_url, long_url, status, last_accessed
Sharding by prefix of short_url field.
Index [short_url_prefix, short_url] allows sharded and fast queries.
Replication is must have, since we want high-availability.