Forem: NK

Announcement: System Design Case Studies Newsletter

NK — Tue, 31 Oct 2023 20:52:00 +0000

I want to inform you that I started a weekly newsletter on system design case studies.

Consider subscribing to the system design newsletter to excel in system design interviews and software architecture.

Also get the powerful template to system design on sign up for FREE.

Maps System Design

NK — Thu, 16 Feb 2023 19:01:27 +0000

You can subscribe to the system design newsletter to excel in system design interviews and software architecture. The original article was published on systemdesign.one website. The popular implementations of the navigation service are the following:

Google Maps
OpenStreetMap
Bing Maps

Disclaimer: The system design questions are subjective. This article is written based on the research I have done on the topic. Feel free to share your feedback and ask questions in the comments. Some of the linked resources are affiliates.

Requirements

The user (client) can find the nearby points of interest within a given radius
The client can find the real-time estimated time of arrival (ETA) between two locations
The client receive suggestions on the possible routes between the two locations

Data storage

Database schema

The primary entities are the locations, the places, and the media tables
The relationship between the locations and the places table is 1-to-many
The relationship between the places and the media table is 1-to-many
The spatial index using Geohash or R-tree is created on the locations table

Type of data store

SQL database such as Postgres persists the location data (latitude, longitude) and the vector tiles
The PostGIS extension of Postgres is used to generate the spatial index
The wide-column data store (LSM tree-based) such as Apache Cassandra is used to persist the trip data for high write throughput
A cache server such as Redis is used to store the popular routes and the road segments
A message queue such as Apache Kafka is used to handle heavy traffic
The message queue is also configured as the pub-sub server
NoSQL document store such as MongoDB is used to store the metadata of the road segments
The media files and raster tiles are stored in a managed object storage such as AWS S3
The CDN caches the popular tiles and the media files
Lucene-based inverted-index data store such as Apache Solr is used to store the index data of locations

Subscribe to my newsletter and never miss a new blog post again, as you'll get notified via email every time I publish something. You will also receive the ultimate guide to approaching system design interviews on newsletter sign-up.

Further system design learning resources

Are you preparing for a system design interview and feeling overwhelmed by the complexity of the process? Do you want to gain the knowledge and confidence to ace the interview and advance your career in software engineering? Then you need to check out the Grokking the System Design Interview course by DesignGurus!

This comprehensive course is designed to help you master the system design interview process by breaking down complex concepts into easy-to-understand explanations. With a focus on practical, real-world examples, you’ll learn how to design scalable, fault-tolerant, and high-performance systems that can handle the most challenging problems.

Don’t miss this opportunity to take your system design skills to the next level and achieve your career goals. Sign up for the Grokking the System Design Interview course by DesignGurus today and take the first step towards success!

High-level design

Calculation of ETA is the shortest path in a directed weighted graph problem
The graph is partitioned and the routes are precomputed for scalability

The map matching is performed to improve the accuracy of ETA
The Kalman filter is used for map matching
The cache and data stores are replicated and sharded geographically through consistent hashing to handle hotspots
Monitoring and fallback can be configured for high availability

How to find the Points of Interest?

The client executes a DNS query to resolve the domain name
The client queries the CDN to check if the nearby points of interest are cached on the CDN
The client creates a WebSocket connection on the load balancer for real-time updates
The load balancer delegates the client's connection to a server with free capacity
The server queries the trie server to provide autocompletion functionality
The server delegates the search query of the client to the search service
The search service queries the inverted index data store to find the relevant locations
The server delegates the points of interest query from the client to the location service
The location service calculates the Geohash from the request and queries the location cache to fetch the list of nearby points of interest IDs
The location database (replica) is queried on a cache miss
The location service queries the places cache to fetch the metadata of a place
The places data store (replica) is queried on a cache miss
The location service queries the object store to fetch the relevant media files and the raster tiles
The tile server on the location service provides SQL functionality on vector tiles
LRU policy is used to evict the cache
GPS signals are not accurate for the identification of the static location due to the multipath effect (reflection from a building)
The WiFi access point is used in addition to GPS signals to find the static location of a client accurately
The map is displayed on a web browser by placing multiple smaller vector tiles and raster tiles next to each other to make up a single bigger picture
The raster tiles (png, jpg) are useful for off-road trajectories to speed up the loading of detected map errors
Vector tiles allow the reduction of bandwidth by restricting data transfer to the current viewport and zoom level
Vector tiles allow to apply styling on the fly on the client and thereby reduce the server load
Vector tiles transfer the vector information (path and polygon) instead of transferring the image tiles
Vector information is grouped into tiles for caching and partitioning
The tiles can be pre-generated and cached to improve latency
Each zoom level shows a unique set of tiles with a different granularity of information
The number of tiles doubles when the user zooms out
Geohash is used to identify the tile on the map
The viewport of the client encloses the container that assigns absolute positions to the tiles
The container is moved when the user pans the map
Street view and satellite imagery are used to identify places in the world

How to calculate the Estimated Time of Arrival?

The client executes a DNS query to resolve the domain name
The client queries the CDN to check if the requested route is cached on the CDN
The client creates a WebSocket connection on the load balancer for real-time bi-directional communication on ETA, trip, and traffic data
The load balancer delegates the client's request to a server with free capacity
The server queries the route cache to fetch the list of possible routes to the destination
The route database (replica) is queried on a cache miss
The server queries the road segment cache to fetch the metadata of the road segments on the suggested route
The road segment data store (replica) is queried on a cache miss
The server queries the trip data store to recalculate the real-time ETA
The server queries the map-matching service to calculate the ETA accurately
The map-matching service queries the trip data store to fetch the list of recent GPS signals
The map matching service queries the road segment data store to identify the nearest road segments
The weather service publishes the latest weather data on the pub-sub server
The traffic service (HyperLogLog based) publishes the latest traffic data on the pub-sub server
The server fetches the latest weather and traffic data using the publish-subscribe pattern
The server queries the route ranking service to filter and sort the result
The server publishes the GPS signals on the message queue for asynchronous processing
Apache Spark executes jobs on the trip data to detect changes in roads, hot spots, and traffic patterns
Apache Spark job asynchronously updates the route database with any detected changes
The physical map is represented as a graph with road segments as the directed edges and road intersections as the nodes
The route between the origin and destination on the road network should be calculated in the least cost (function of time and distance)
Map matching is the problem of matching the raw GPS signals to the relevant road segments
The embedded sensors on the smartphones are used to geo-localize the users
The graph can be partitioned to pre-compute the possible routes within the partitions with time complexity of sqrt(n), where n = number of road intersections
The partitions can be created on different granularities (country, city) to improve the latency of long-distance queries
The interactions are applied on the boundaries of the partitions to improve the accuracy and scalability
Dijkstra's algorithm (sub-optimal due to scalability) provides a time complexity of O(nlogn) for route calculation, where n = number of road intersections
The shortest path algorithm on the weighted graph such as the Bellman-Ford provides a time complexity of O(ve) for route calculation, where v = number of vertices and e = number of edges
The edge weight of the graph is populated with weather and traffic data
The popular partitions and routes can be cached to improve the latency
Alternate routes can be suggested if applying the weather and traffic data on the shortest distanced route returns a delayed ETA
The time series data (seasonality), map data, routing, and machine learning can be used to predict the ETA
Viterbi algorithm (dynamic programming) can be used to identify the most probable sequence of road segments using a sequence of GPS signals
Alternatively, the KNN algorithm with a minimum radius (k = 2) can be executed on the Geohash to identify the closest road segments
The marginalized particle filter running on an unscented Kalman filter is used for real-time map matching
Kalman filter is an optimal algorithm that uses multiple GPS signals to estimate the accurate road segment of the client
Kalman filter is also applied to the seasonality of the time series data
Additional data types such as traffic and weather can be added to marginalized particle filter
Machine learning on the time series historical data helps to predict traffic conditions

Support

If you enjoy the blog and would like to support my work, you can make a one-time donation on Ko-fi or Buy Me a Coffee or become a Patron on Patreon. Your support will help me continue to create quality content and bring new ideas to the blog. Thank you for your generosity!

License

CC BY-NC-ND: This license allows reusers to copy and distribute the images in this article in any medium or format in unadapted form only, for noncommercial purposes only, and only so long as attribution is given to the creator. The original article must be backlinked.

References

Antin Harasymiv, Prototyping a Smoother Map (2018), medium.com
wiki.openstreetmap.org
Sreeta Gorripaty, What's My ETA? (2018), Uber Engineering
Karan Parikh, Map Matching (2018), Uber Engineering

What happens when you type a URL into your browser?

NK — Sat, 03 Dec 2022 16:24:06 +0000

You can subscribe to the system design newsletter to excel in system design interviews and software architecture. This article aims the following audiences:

tech workers
students
product managers
marketing team
sales team

There are no prerequisites to reading this article. I assume that you have used a web browser to navigate across the internet. The original article was published on systemdesign.one website.

What happens when you type amazon.com or google.com in the browser?

At a high level, the following operations happen in the background when you type a URL into your browser and press Enter:

DNS resolution
TCP three-way handshake
HTTPS upgrade
HTTP Request/Response
Browser rendering the response from the server

The following terminology might be useful for you:

DNS: data store that contains the mapping from domain name to IP address
HTTP: standard application-level protocol used to exchange files on the internet
HTTPS: secure (encrypted) version of HTTP
TCP: standard that defines how to establish and maintain a network conversation between a client and a server
Client: web browser or a mobile device that lets you perform different actions on the internet
Server: a computer that stores files and information in the form of a website
URL: web address to identify a web resource on the internet

Introduction

When you type a Uniform Resource Locator (URL) into the browser and press Enter, a multitude of actions is executed in the background.

The browser (client) must find the Internet protocol (IP) address of the server that hosts the website. The client subsequently requests the IP address of the server to transfer or retrieve data.

Further system design learning resources

What is domain name resolution?

Domain Name System (DNS) is a data store that stores the mapping from a domain name (such as google.com) to its IP address (142.250.185.78). You could compare DNS to an address book or a telephone book [1].

You need a domain name (instead of using an IP address directly) because it’s trivial to remember domain names for a human. Each server (for example, google.com) should have a unique IP address on the internet. The DNS lets you find the IP address of the specific server on the internet using its domain name.

The domain name space (DNS hierarchy) is an inverted tree structure. The DNS hierarchy has a single domain at the top level known as the root domain.

The DNS resolution starts at the root domain, TLD, and works its way down to the second-level domain. The DNS resolution might traverse through multiple third-level domains until the hostname of the website resolves to an IP address.

A URL consists of the following parts [2]:

protocol (scheme)
subdomain
domain (second-level)
top-level domain

The protocol section of the URL informs the web server which protocol to use on accessing a website. The subdomain indicates the services offered by the website such as maps or mail. The second-level domain indicates the name of the website. The top-level domain indicates the type of entity the organization registers on the internet.

The DNS resolution is a sequential process. The subsequent steps of DNS resolution get executed only if the cache in the former step does not have the relevant DNS entry.

The following operations get executed in sequential order for DNS resolution:

The browser (client) checks if the hostname to IP address mapping exists in the local cache of the client.
If the last step failed, the client checks the Operating System (OS) local cache by executing a system call (syscall).
If the last step failed, the client makes a DNS request to the Gateway/Router and checks the local cache of the Router.
If the last step failed, the router forwards the request to Internet Service Provider (ISP) and checks the DNS cache of the ISP.
If the last step failed, the DNS resolver queries the root servers (there are 13 root servers with replicas in the world).
DNS resolver queries Top Level Domain (TLD) servers such as .com, or .org.
DNS resolver queries Authoritative name servers such as google.com.
Optionally, the DNS resolver queries Authoritative subdomain servers such as maps.google.com depending on your query.

Once the DNS query is resolved, the intermediate components in the DNS resolution process would cache the result with a Time-to-live (TTL) expiry time limit. If you change the IP address of a website, the client should wait until TTL has elapsed to automatically invalidate the cache. The cache also improves the latency of subsequent client requests.

TCP three-way handshake

The client should create a connection to the server to transfer and receive data. Transmission Control Protocol (TCP) is one of the underlying protocols in Hypertext Transfer Protocol (HTTP).

You can compare HTTP to an abstract or a high-level protocol (Application layer or layer 7 in the OSI model) used between the client and the server to transfer data. Data transferred in HTTP is human-readable. TCP is a lower-level protocol (Transport layer or layer 4 in the OSI model) that handles error detection and retransmission of data packets [3].

The client performs a three-way handshake with the server to establish a TCP connection. TCP requires a three-way handshake because of the bi-directional communication channel. If you make a two-way handshake, you can only start a single-directional communication channel.

The following synchronize (SYN) and acknowledge (ACK) messages are sent between the client and the server to open a TCP connection:

The client sends an SYN request with a random sequence number (x).
The server responds with SYN-ACK. The acknowledgment number is set to one more than the received sequence number (x+1). The server sends another random sequence number (y).
The client sends ACK. The client sends an acknowledgment number that is one more than the received sequence number (y+1).

HTTPS Upgrade

Hypertext Transfer Protocol Secure (HTTPS) is an extension of Hypertext Transfer Protocol (HTTP). The data transferred through HTTP is not encrypted and therefore anyone can eavesdrop on the data packets that are transferred. HTTPS encrypts the transferred data and thereby prevents man-in-the-middle attacks [4]. Most of the modern websites on the internet enable HTTPS for secure communication. HTTPS uses port 443 by default while HTTP uses port 80.

In asymmetric encryption, there is a key pair — public and private keys. The public keys can be shared with anyone on the internet while the private key should never be shared. In symmetric encryption, there is only a single private key and both parties should have access to the same key to encrypt or decrypt the message.

You could compare asymmetric encryption to an email service. The public key would be your Email address and the private key would be the password used to access the email account. Anyone can easily verify that you sent the email by looking at the Email address of the sender. However, if anyone sends an Email to your account, only you can access it using the password.

The following operations are executed between the client and server to upgrade HTTP to HTTPS before the transfer of any data packets:

The browser (client) uses the HTTP Request headers to make an HTTPS upgrade request to the server.
The server responds to the client with a Secure Sockets Layer (SSL) certificate that contains the public key of the server, which was signed by the Certificate Authority (CA).
The client by default has the public keys of popular CA (for example, Google CA). The client can use the public keys of the CA to verify the validity of the SSL certificate by checking the digital signature (digital signature in asymmetric encryption).
The client creates a new symmetric private key and encrypts the new symmetric private key with the public key of the server.
The server decrypts the new symmetric private key shared by the client using the server's private key.
Any further communication between the client and the server would be encrypted using the new symmetric private key and therefore remains secure.

Anyone listening to the HTTP Upgrade request or response messages would not be able to capture any meaningful data because of the asymmetric encryption. Once HTTPS is upgraded, further communication between the client and the server utilizes symmetric encryption.

To create an SSL certificate, the server executes a Certificate Signing Request (CSR) to the CA.

The CSR transfers the public key of the server to the CA. The CA has a pair of public and private keys. The CA signs the public key of the server using the private key of the CA and creates an SSL certificate. Anyone on the internet who has access to the public key of the CA could easily verify the digital signature of the SSL certificate.

HTTP Request/Response

Hypertext Transfer Protocol (HTTP) is a mechanism for transporting data between a client and a server. The client issues an HTTP(S) Request to the server to fetch or transfer data. The server responds with relevant content and completion status information about the request [5, 6].

The client makes a GET HTTP Request to view a website (such as google.com). The client makes a POST HTTP Request if the client wants to submit data to the server (such as searching for some keyword in google.com).

The URL can be broken down into multiple components. The domain name is used to identify the server. The URL path is used to identify the resource (a specific file or information) on the server. The query parameters are used to filter or sort the data (or transfer stateful information). The following is the simplified workflow when you view the google.com website on your client [7, 8]:

client makes an HTTP GET method Request to the google.com server
the server responds with a 200 OK status code if successful

The HTTP Request is composed of the following entities:

Uniform Resource Locator (URL)
HTTP headers
HTTP body (optional)

The HTTP Request method (Verb) defines the type of action that should be performed on the server. Some of the popular HTTP methods are the following:

The server (Nginx, Apache web server) delegates the HTTP Request to the Request handlers. The Request handler is a piece of code that is defined in any server-side programming language (such as Python, Node.js, or Java). The Request handler checks the HTTP headers of the Request (content-type, content-encoding, cookies, etc) and subsequently validates the HTTP Request body. The Request handler then generates an appropriate response in the content-type (JSON, XML) that was requested by the client.

The HTTP server response is composed of the following entities:

HTTP headers
HTTP body

The HTTP Response Status Code helps you to troubleshoot failures. The HTTP Status Codes can be categorised into the following [9, 10]:

The HTTP Request and Response headers are used to control the cache, authorize the client, or compress the data that is transferred between the client and the server. For example, the user-agent HTTP request header helps the server to identify if the client is a mobile or a desktop client. Some of the most popular HTTP headers are the following:

Browser rendering the response from the server

The browser might make multiple HTTP Requests to the server to fetch all the relevant data for a website such as Cascading Style Sheets (CSS), JavaScript files, Images, or Videos. Finally, the browser renders the HTML and the content received from the server [11].

Depending on the HTTP response headers (Cache-control), the browser caches the response to prevent re-requesting the same data from the server. The cache improves the latency of the website.

Summary

The client usually caches the DNS mapping and server response with an arbitrary Time-to-live (TTL) expiry time. The DNS server is not queried multiple times when you revisit the same website because of the local cache.

In an internet-scale system, there are multiple components as intermediate layers to meet the incoming load demand. Content Delivery Networks (CDN), Load Balancers, and Reverse Proxy are some of the intermediate components that might appear in a large-scale system.

Support

Questions and Solutions

If you would like to challenge your knowledge on the topic, visit the medium article: Knowledge Test

License

References

[1] DNS operation

[2] URL Syntax

[3] Transmission Control Protocol

[4] HTTPS

[5] MDN HTTP headers

[6] MDN HTTP Status Code

[7] HTTP methods

[8] HTTP explained

[9] Microsoft API design

[10] System Design Primer HTTP communication

[11] How browsers work