Loading...
The system should convert the long url into a 9 character alphanumeric code.
The system should ensure that similar urls submitted by different users should have different codes.
A good hashing function should be used to convert the long url to a short url
A key-pair database such as dynamoo db should be used for easy horizontal scalling due to the high number of urls generated daily.
The system should be highly availabe to ensure that url redirects do not fail
The system should be highly effective ensuring that no two different urls have the same short url
100,000,000 urls created per day
Assuming to store each key-value pair {short_url: long_url} is 100 bytes and we need storage for 5 years:
100,000,000 * 365 * 10 * 100 = 36.5 TB
Total storage needed to store urls for the next five years is 36.5 TB
Assuming the number of users for the next 5 years will be 10 million and the mount of meta data required to store data for one user is 2KB:
10,000,000 * 2 = 20GB
1: CreateShortUrl(
user_id,
long_url
)
method = POST
return: short_url
2: GetLongUrl(
short_url
)
method = GET
return: long_url
status_code = 301 (url redirect)
The database used for user information will be: PostgreSQL for consistency purposes:
UserData:
first_name: string
last_name: string
email = string
password = string
The database used for storing {short_url: long_url} key-value pairs will be DynamoDB for easy horizontal scalling for high availability
ShortUrls Key-value pairs:
{
short_url: long_url
user_data: user_id
}
The system will have several load balancers between the client and the application servers so as to distribute the traffic among the servers depending on the traffic load. Between the application servers and the database servers will be several cache servers to cache recently accessed data by the api servers. The cache will use an Least Recently Used eviction policy to evict cache. The databases will be of two types, relational databases such as Postgres to store user information and a non-relational database such as DynamoDB to store key-value pairs of short_url to long_url. The sharding on dynamo db will be based on a consistent hashing algorithm that maps the short_urls to the non-relational database depending on the characters of the short_url.
The authenticated user fills us out a form with a long_url field which he/she then submits the form via a post method. On the backend the server recieves the post data containing both the long_url and the id of the user who submitted the form. The hashing algorithm then maps the long_url into a short_url depending using both the user_id and the long_url to create the hash. Based on the hash value, the short_url is then mapped to one of the database shards via a consitent hashing algorithm. The system then returns the value of the short_url to the user with a status code of 200 indicating successful creation.
On clicking the generated short_url , a get request is sent to the server. The server then queries the database and returns the associated long_url with a status code of 301 indicating a permanent redirect.
Application server
Their would be several Application servers to distribute the workload so as to faciltate faster response times as requests are served quickly.
Load Balancers:
The load balancers will distribute the traffic among the application servers using a weighted round robin algorithm which will check the capacity of the server and the current server load before allocating traffic.
Cache Servers:
The cache server will cache recently requested data to reduce the number of expensive database reads. The cache eviction policy used will be LRU (Least Recently Used) which will evict least recently accessed cache data.
Hashing Function for URL Shortening:
The choice of hashing function plays a crucial role in ensuring both uniqueness and efficiency in the URL shortening process. One commonly used hashing function for URL shortening is SHA-256 (Secure Hash Algorithm 256-bit). It generates a unique 256-bit hash value for each input, making it highly unlikely for collisions to occur.
import hashlib
def generate_short_url(long_url):
# Hash the long URL using SHA-256
hashed_value = hashlib.sha256(long_url.encode()).hexdigest()
# Take a portion of the hash value to create a short URL
short_url = hashed_value[:8] # Consider only the first 8 characters for simplicity
return short_url
DynamoDB: Horizontal Scalling
PostgreSQL: Consistency
Load balancers: Reduce traffic bottle necks
Multiple API Servers: To reduce server response times
Multiple Databases: Master - Slave Architecture tp make sure that their is a failover mechanism to ensure that data is not lost. A slave is selected to be a master temporarily in the event that the master database fails.
Trade offs: The slave databases on different nodes will recieve new data at different times leading to a minimal delay in data consistency which in this case is permissible.
Handling Concurrent Requests and Ensuring Thread Safety:
In a high-traffic environment, it's crucial to handle concurrent requests and ensure thread safety to prevent data corruption and maintain consistency. One approach is to use locking mechanisms to synchronize access to shared resources.
Example:
import threading
lock = threading.Lock()
def shorten_url(long_url):
with lock:
# Generate short URL in a thread-safe manner
short_url = generate_short_url(long_url)
# Save short URL to database
save_to_database(long_url, short_url)
return short_url
In this example, a lock is acquired before generating and saving the short URL to the database. This ensures that only one thread can execute this critical section of the code at a time, preventing race conditions.
Ensuring Data Consistency Across Different Database Instances:
When dealing with multiple database instances, maintaining data consistency is essential to ensure that all instances have the same view of the data. Techniques such as distributed transactions or eventual consistency models can be employed.
Example:
from sqlalchemy import create_engine
from sqlalchemy.orm import sessionmaker
from sqlalchemy.ext.declarative import declarative_base
Base = declarative_base()
# Define your database model here...
def save_to_database(long_url, short_url):
# Create a database session
engine = create_engine('sqlite:///urls.db')
Session = sessionmaker(bind=engine)
session = Session()
# Save the URL mapping to the database
try:
url_mapping = URLMapping(long_url=long_url, short_url=short_url)
session.add(url_mapping)
session.commit() # Ensure data consistency across database instances
except Exception as e:
session.rollback()
raise e
finally:
session.close()
In this example, SQLAlchemy is used to interact with the database. The session.commit() method is called to commit the transaction, ensuring that the data is consistent across all database instances. If an exception occurs, the transaction is rolled back to maintain data integrity.
Load balancers: To redirect traffic to other servers in the case that a particular server fails. To also distribute traffic among the various application servers.
Master - Slave database architecture: To ensure that read request are distributed among the multiple slave databases and also to make sure that their is a failover mechanism incase the master database fails.
To use a multi-master database architecture to ensure that recently stored data is not lost in the case the master database fails, the other master or master can take over from where it left.
API rate limiting is a critical aspect of any web service, including a URL shortening service, as it helps control the rate at which clients can make requests to the service's API endpoints. Implementing rate limiting is essential for several reasons:
Preventing Abuse: Rate limiting helps prevent abuse of the service by limiting the number of requests a client can make within a specific time window. This prevents clients from overwhelming the service with a large number of requests, which can lead to degraded performance or service downtime.
Protecting Resources: By limiting the rate of requests, rate limiting protects the service's resources from being exhausted by a single client or a group of clients. It ensures fair usage of resources and allows the service to maintain optimal performance for all users.
Ensuring Availability: Rate limiting helps ensure the availability and responsiveness of the service by preventing it from becoming overloaded with requests. By enforcing limits on the rate of requests, the service can better manage its resources and maintain consistent performance levels.
Implementing API rate limiting involves defining limits on the number of requests that clients can make within a specified time period, as well as handling requests that exceed these limits.