Requirements

Functional Requirements:

1. Create a short URL for a given long URL.
2. Return the long URL associated with a given short URL.
3. User Authentication: Allow users to create accounts and manage their shortened URLs.
4. Custom Short URLs: Enable users to create custom short URLs instead of random ones.
5. Analytics: Provide users with analytics on how many times their short URLs have been accessed.
6. Expiration of URLs: Allow users to set expiration dates for their short URLs.

• Default Value: Determine a reasonable default TTL, such as 30 days or 1 year, depending on your service's use case and user expectations.
• User Awareness: Make sure users are aware of the default TTL when they create a short URL, so they know when it will expire if they don't set a custom duration.

1. Bulk URL Shortening: Enable users to shorten multiple URLs at once.

Non-Functional Requirements:

1. High avaiability

• 99,99% aviability
• more read-focused (read to write ratio 100:1), read aviability is critical, user can wait for writing (we can use some queue)

1. Low latency achieved by:

• 302 redirect
• caching urls,we check if url is in the Redis Cache (if yes then redirect isntantly), if not then get from DB -> save in redis -> redirect.
• Key-value DB (casandra or Dynamo DB)

1. shortened links should not be guessable (not predictable)

• In order to not have shortened links like short.ly/1 short.ly/2 etc we need to make them not predicatble. It will be achieved through Hashing mechanism with salt, enriched with collision handling mechanism (adding random number at the end of hash if collsiion occurs)
• Additionally rate limitng is introduced on the api level to avoid brute force attacs

1. Horizontal scaling: EDGE redirects and read-through caching with soft-TTL to avoid thundering herd problem

API Design

1. create_url(api_dev_key, original_url, custom_alias=None, user_name=None, expire_date=None)

• responsible for url shortening, will return shortened url on success, code name for error

1. GET/{short_url}

• redirection api, first regex validation, then checking the url in cache, if not present then check the db, return HTTP 302 on success

1. delete_url(api_dev_key, url_key)

• used for deleting shortened url

High-Level Design

User interacts with the url shoretning service via UI, he can either shorten the url or provide a shrot url for redirection to the long link. API gateway verifies and routes the request to the shortening service. the shortening service decides, basing on the request if it must rertieve long url (by checking or udpating the cache first and then redirecting to the logn url address) or shortening and storing the url. We'll use the hashing function to generate a short url. Storage layer will consist manly of the URL mapping table, with fields: short URL identifier, long url, creation_timestamp, user_name, user_email. Hash index on the short url field should speed up the retrieval process. The partition key might be the short URL. We'll use the key-value DB (Cassandra or DynamoDB) due to the high-read properties fo the service

Detailed Component Design

API Gateway

Key responsibilities:

1. Authorization and autorization: checking the JWT token and pass the traffic on when correct, this way other services don't have to do this
2. routing the request to th einternal services
3. rate limiting in case of many requests from the same ip
4. load balancing if we need mutliple shortening ulr services when scaling up

URL Shortening service

A small, dockerized service, so we can spin up many instances of it. Doesn't have to work in an async/await way, nice improvement though. Main problem is to properly hash and store short ulrs in case of many services. We can u In case of many services we would have to assign intervals in which particular instance can operate on so there will be no collisions between the instances. Quering the DB on every save is not feasible.

Redis will be used as a backend cache, fixed number of most popular urls for retrieval will be stored there and almost instantly returned, cache will be managed using the Time To Live with the LRU algorithm. Read-through caching system should be in place. this should mitigate the hot-spot potential problems. in case one or couple of short urls will become highly popular at some point, if not present in the cache this popular url will be saved there after the first usage. LRU mechanism will make sure that this popular url stays in the cache and is retrieved from it in many subsequentiall hot-spot traffic spike

A simple ragne managers service shoudl be in place - it sets and applies id ranges (e.g. 1-1000000 range) to a specific urls shortening service instances, which avoid collision risks further and allows the services to operate on their range even during outages and network partitions.

To achieve high concurrency and zero-collision architecture without querying the database, the system will use a Distributed Unique ID Generator inspired by the Twitter Snowflake algorithm, managed by a centralized Range Manager.

1. ID Structure (63-bit integer):
   • 41 bits: Custom epoch timestamp in milliseconds (provides ~69 years of lifespan).
   • 8 bits: Shard/Server ID (assigned dynamically by the Range Manager during instance startup, supporting up to 256 concurrent nodes).
   • 14 bits: Sequence number (increments every time an ID is generated within the same millisecond, resetting to 0. Supports up to 16,384 IDs/ms per node).
2. Guaranteed Uniqueness (Zero-Collision): Because each instance operates on a dedicated Shard ID and increments its own sequence per millisecond, ID collisions between instances are mathematically impossible. Therefore, expensive database lookups, optimistic locking for deduplication, and retry mechanisms on write are completely eliminated from the critical path.
3. Security & Non-Predictability (Addressing "Hard-to-guess" requirement): To prevent enumeration attacks (where attackers guess sequential short URLs), the generated 63-bit ID will not be mapped directly to Base62. Instead, we will apply a lightweight, deterministic bit-shuffling (Feistel cipher or bit-permutation) before encoding to Base62.
   • Result: Consecutive IDs will produce completely randomized, non-sequential Base62 strings (e.g., ID 1001 -> aX9zW, ID 1002 -> mP3kQ), ensuring security while maintaining 100% uniqueness without DB overhead.
4. Base62 Encoding: The obfuscated 63-bit integer is encoded into Base62 ([a-z, A-Z, 0-9]), resulting in a short URL string of 7 to 11 characters.

. We can use the optmistic locking mechanism (we check before commiting the transaction if the id is still possible to save) and additioanlly an unique constrain on a DB short_id field to avoid duplicates finally.

A monitoring service can be created that would count and inform us about unusally high number of collision