System Design Notes

DNS Lookup Process

1. Look up browser cache
2. Look up OS cache
3. Look up DNS resolver which recursively looks up the domain name
   1. This involves many different servers.
   2. The "domain -> IP" mapping is cached in each of these servers.

HTTP Status Codes

https://developer.mozilla.org/en-US/docs/Web/HTTP/Status

• 100-level: Informational responses
• 200-level: Successful responses
• 300-level: Redirection messages
• 400-level: Something is wrong with request
• 500-level: Something is wrong with server (client might re-try, especially for idempotent requests)

Common codes:

• 200: OK
  • GET: Resource fetched successfully and returned in body.
  • HEAD: Representation headers are included in response without any message body.
  • PUT or POST: Resource describing the result of the action is in body.
  • TRACE Message body contains request message as received by server.
• 201: Created
  • indicates a resource has been created, usually after POST, and sometimes PUT
• 301: Moved Permanently
  • New URL is given in the response
  • Typically used by URL shorteners (bit.ly, goo.gl) for click tracking
• 304: Not Modified
  • Informs the client that the response is not modified, i.e. client can use the cached version
• 400: Bad Request
  • Client made an invalid request, perhaps invalid request syntax
• 401: Unauthorised
  • Although specified as unauthorised, it means unauthenticated.
  • Client needs to be authenticated to access the resource (client's identity is unknown).
• 403: Forbidden
  • Client's identity is known, but does not have access to this resource.
  • Can send 404 instead of 403 to hide the existence of the resource.
• 404: Not Found
  • Typically, resource does not exist.
  • Can send 404 instead of 403 to hide the existence of the resource.
• 418: I'm a teapot
  • See: https://developer.mozilla.org/en-US/docs/Web/HTTP/Status/418
• 429: Too Many Requests
  • Exceeded rate limit
• 500: Internal Server Error
  • Server cannot handle the situation.
• 501: Not Implemented
  • Request method is not supported by the server.
  • GET and HEAD methods must be supported by the server.
• 502: Bad Gateway
  • Server, while acting as a gateway, got an invalid response.
• 503: Service Unavailable
  • Server cannot handle the request for reasons like:
    • down for maintenance
    • server overloaded
  • Should include a user-friendly page explaining the problem
  • Should include a Retry-After HTTP header, if possible
• 504: Gateway Timeout
  • Server, while acting as a gateway, cannot get response in time.

API Versioning

Allows newer versions to introduce changes that would otherwise break compatibility.

REST API Parameters & Resources

https://stackoverflow.com/questions/4024271/rest-api-best-practices-where-to-put-parameters

• /api/user/XXX (path variables)
• /api/user?username=XXX (query parameters)

Path variables are generally used for:

• IDs / unique identifiers
• subresources

One reason why it is recommended to use path variables as much as possible is because some browsers do not cache the results if the query contains query parameters (because of RPC APIs)

Query parameters are generally used for:

• optional parameters
• filters
• other modifiers (e.g. sorted by)

However, these are not set in stone, and there is no general consensus on when to use which. It is more important to be consistent!

Non-CRUD with REST API

Some operations like archiving, deactivate, search do not naturally fit into any of the CRUD operations.

Archive

Typically, would use PATCH with a flag of "archive": true.

Deactivate

• PUT /users/user-1/deactivate
• Acceptable to use verbs in sub-resource, because there is no way otherwise.

Search

• GET /search/code?name=bob
• Recommended to use GET with query parameters. This is because browsers cache GET requests.

Do NOT use the request body because browser caching works only with the URL. GET requests with a request body also breaks the REST principle.

Pros of REST API

• standard method names, arguments and status codes
• utilises HTTP features
• easy to maintain and build

Cons of REST API

• big payloads: not all data may used
• multiple HTTP roundtrips: if there is a need to get a resource and a sub-resource

Pros of RPC API

• easy to understand
• lightweight payloads
• high performance: action-oriented

Cons of RPC API

• not standardised: hard to discover endpoints, have to constantly reference documentation
• number of endpoints can grow too much

gRPC

Video: What is RPC? gRPC Introduction

Google's implementation of RPC that is very widely used.

Protocol Buffers are used as the data interchange format, it is language-agnostic and platform-agnostic (works the same on all languages and platforms).

• Many languages are supported by gRPC
• Data / Schema is strongly typed and defined in a .proto file
• gRPC service is also defined in a .proto file
• These .proto files can be used to generate code / classes in the client and server for making RPC calls
• High performance
  • Protocol Buffers are binary encoded and faster than JSON
  • gRPC is built on top of HTTP/2 streams
• Browser support is not strong enough to support a gRPC client
• gRPC is used more for communication between microservices

Pros of RPC API

• saves multiple round trips: only needs a single call
• avoids versioning: because there is no need for any versioning
• smaller payload: client requests exactly what is needed

Cons of RPC API

• complexity: server needs to handle much more complex queries
  • too complicated for simple APIs
• optimising performance is difficult: hard to identify what to optimise for

Kafka

Distributed system of servers and clients communicating using TCP network protocol, can be deployed on bare-metal hardware, virtual machines, containers, cloud environments and the like.

There are Kafka Streams libraries in various popular programming languages.

Producer <-> Kafka Cluster (contains multiple brokers) <-> Consumer

https://kafka.apache.org/intro#intro_platform

Kafka use cases: https://www.neovasolutions.com/2020/07/20/apache-kafka-a-quick-overview/

• Implements event streaming end to end
• Handle connection between micro-services
• Useful for real-time data processing, monitoring, tracking
• Many types of connections, between different services, are implemented in Kafka, don't need to implement them yourself

Offset-Based Pagination

Commonly use limit & offset as parameters. If not specified, usually there are sensible default values.

• limit - maximum number of items in a batch
• offset - starting position
• similar to SQL syntax => easier to implement

Cursor-Based Pagination

1. Client requests with only a limit
2. Server responds with results and a next-cursor (typically integer value), aka continuation tokens
3. Client includes this cursor in subsequent requests

Basically a pointer that the server uses to optimise performance. There are many ways to implement this.

A possible cursor is: timestamp of row creation.

SELECT * FROM Products
WHERE created_timestamp < $1 -- $1 is the cursor
ORDER BY created_timestamp
LIMIT 50;

Be sure to index columns that the cursor value comes from to improve performance. SQL: CREATE INDEX index_name ON table_name (column_name);

Basic Authentication

1. base64 encode username & password
2. send encoded data in header, with SSL

Cons

• username & password needs to be sent with every request to the server: increases chances of compromise
• no way to use 3rd party application without sharing username and password!
• no way to revoke access to a single 3rd party application
• 3rd party applications have full access to the entire account

OAuth

https://developer.okta.com/blog/2017/06/21/what-the-heck-is-oauth (very in-depth article)

OAuth is a open standard for authorisation.

Allows users to grant access to applications without having to share passwords with them.

One such service is Auth0.

Used for authorisation, not authentication (user email, id, etc)!

1. no passwords being shared
2. can revoke access to each application individually
3. can control and limit access to each resource

• Redirect URI - callback URL: URL that the user is redirected to after authorisation
• response type (code is the most commonly used - authorisation code flow)
• scopes: read access, write access, ... (usually, can have multiple)

Returns authorisation code, then the client exchanges this code with the authorisation server to get an access token. Subsequent requests to the API uses this access token.

Need to exchange authorisation code to an access token for security reasons. During this exchange, a secret is also provided as a proof of identity.

OpenID Connect

A layer on top of the OAuth protocol that enables authentication. Allows client to verify the identity of end-users to get basic user profile.

Add a scope of openid.

Then, exchange for a (access token + ID token) from the authorisation server.

Uses JWT (JSON Web Token) to share identity between services.

The workflow is similar to SAML below, but instead of a signed SAML Assertion, a signed JWT is instead used.

SAML

Security Assertion Markup Language

XML-based open standard for exchanging identity information. An alternative to OpenID.

Generally used in enterprise. One account to connect to many services.

Basic SSO Login Flow

1. When logging in to a Service Provider (e.g. Gmail) with a (email with work domain).
2. Service Provider returns a SAML Authentication Request to the browser.
3. Browser redirects user to the Identity Provider for the company. (Identity Provider examples: Okta, Auth0, OneLogin)
4. User logs in via a login page.
5. Identity Provider generates and returns a signed SAML Assertion.
   • SAML Assertion is a XML document that contains: user info and user access permissions
6. Browser forwards signed SAML Assertion to the Service Provider.
7. Service Provider validates the assertion is signed by the Identity Provider.
   • Typically done with public key cryptography

Navigating to another SSO application

1. When logging in to another Service Provider (e.g. Workday) with a (email with work domain).
2. Service Provider returns a SAML Authentication Request to the browser.
3. Browser redirects user to the Identity Provider for the company. (Identity Provider examples: Okta, Auth0, OneLogin)
4. Login is skipped because the user is still logged in.
5. (from here on, same as before)

Forward Proxy

A Forward Proxy sits between a User and Internet. Forward Proxy intercepts requests to web servers and acts as a middleman between a User and a Web Server.

• Forward Proxy hides the Client's identity (IP address)
• Forward Proxy can bypass some browsing restrictions / firewalls
• Forward Proxy can block access to certain contents, by filtering them
• Forward Proxies require the Client to explicitly connect to them
  • But, there exists Transparent Proxies to redirect traffic to proxies automatically

Reverse Proxy

A Reverse Proxy sits between the Internet and a Web Server. Reverse Proxy intercepts requires from clients and acts as a middleman between a User and a Web Server.

• Reverse Proxy can hide a website's IP address: makes it harder to DOS attack
• Reverse Proxy can act as a load balancer by distributing requests to different web servers
  • Services like CloudFare put a lot of Reverse Proxy servers all around the world
• Reverse Proxy caches static content
• Reverse Proxy can handle SSL encryptions on behalf of all the clients

There can be many layers of reverse proxies. CloudFare + API Gateway / Load Balancer

Nginx, Apache are popular reverse proxies.

API Gateway

Video: What is API Gateway?

Typically, handles:

• authentication and security policy enforcements
• load balancing and circuit breaking
• protocol translation and service discovery
• monitoring, logging, analytics and billing
• caching
• error handling
• logging / monitoring
• analytics

Request flow

1. Client sends request to the server (API Gateway acts as the entry point)
2. API Gateway validates the HTTP request
3. API Gateway checks the IP address against Allow-list, Deny-list
4. API Gateway can also act as basic Rate Limiter
5. API Gateway handles authentication and authorisation
6. API Gateway does Rate Limiting based on the user's authentication
7. API Gateway does Service Discovery to locate the correct backend service, by checking the path
8. API Gateway transforms the request into the appropriate protocol via Protocol Conversion
9. API Gateway forwards this transformed request to the appropriate service
10. API Gateway receives the response
11. API Gateway transforms the response into the public-facing protocol
12. API Gateway returns the transformed response to the client

DNS-Based Routing

Each PoP has its own IP address. When the User looks up the IP address of the CDN, the DNS returns the IP address of the nearest / best PoP.

Hash-Based Solution (GeoHash)

1. Divide the world into 4 quadrants. Name them "00", "01", "10", "11". "0" for left/bottom. "1" for right/top. For example, the top left corner is "01".
2. Recursively divide each of these 4 quadrants until desired size is reached.
3. This very long binary string is typically converted into a base32 string for ease of storage and querying.
4. Index this column in the database for faster reads.

To query for nearby locations, typically will find the quadrant in O(1) and then find the 8 neighbouring quadrants in O(1) again. These will be the nearby locations.

Many libraries exist to convert GeoHash <-> latitude & longitude

Relational Database

Any relational database can handle this because it only requires a TEXT column!

Use compound key of (business_id, geohash) to allow for efficient removal of businesses.

Tree-Based Solutions

• QuadTree (https://en.wikipedia.org/wiki/Quadtree)
  • Recursively sub-divide into 4 quadrants to form a 4-child tree.
• Google S2 Geometry (https://s2geometry.io/)
• RTree (https://en.wikipedia.org/wiki/R-tree)

In-memory data structures, not database solutions!

Partitioning Data

• Horizontal Partitioning: split one table's rows into multiple different tables (partitions). Each partition has the exact same schema, but contains different rows.
• Vertical Partitioning: split columns into new, distinct tables, joined by foreign keys

Cache Layer / DB Caching

https://en.wikipedia.org/wiki/Database_caching

Add a cache layer in front of the database to cache commonly queried data to minimise actual DB queries.

There are many ways to achieve this.

• in-memory
• redis
• primary database
• etc...

DB Sharding

https://www.digitalocean.com/community/tutorials/understanding-database-sharding

Split the data into multiple smaller databases, called logical shards. Each shard contains a subset of the total data. Collectively, the shards hold the entire dataset.

Each data point might exist in more than 1 shard. There are some situations where this is useful: a table that contains conversion rate data.

Sharding is typically implemented at the application level. However, some DBMS have sharding capabilities built in.

DB Replication

https://www.integrate.io/glossary/what-is-database-replication/

https://www.indeed.com/career-advice/career-development/database-replication

Create partial or complete copies of a database.

Publisher Database -- (replicates to) -> Subscriber Databases

DDBMS - Distributed Database Management System

1. DDBMS replicates and distributes (syncs) data from the publisher database to the various subscriber databases.
2. DDBMS ensures changes are reflected in subscriber databases.

Change Data Capture (CDC) records the changes made to the publisher database. Then, the DDBMS applies these changes into the subscriber databases.

HTTPS

Hypertext Transfer Protocol Secure

HTTP extended to be encrypted by SSL/TLS.

1. TCP Handshake
2. Certificate Check
   1. Client Hello (Client -> Server) informs server of the following:
      • TLS version supported
      • Cyber suite supported: set of encryption algorithms
   2. Server Hello (Client <- Server)
      • Server chooses TLS version and cyber suite
   3. Certificate (Client <- Server)
      • Public key of server: used for asymmetric encryption
   4. Server Hello Done (Client <- Server)
   • Both the client and the server also refer to a trusted authority for authentication
     • The client verifies the server's SSL certificate this way
3. Key Exchange
   • Client comes up with the shared encryption key, encrypted with the server's public key
   • Server decrypts said encrypted key with its private key
   • Now, both sides hold the same encryption key
4. Data Transmission
   • Now, both sides transmit data encrypted with the shared encryption key

SSL

https://www.cloudflare.com/en-gb/learning/ssl/what-is-ssl/

Secure Sockets Layer

SSL is the predecessor to TLS. SSL is now deprecated and has not been updated since 1996, but people still refer to both technologies collectively as SSL/TLS.

TLS

Transport Layer Security

Man-in-the-middle attack only can see encrypted data.

Refer to HTTPS section for how it is used.

Monolith

(UI + Business Logic + Data) all in 1 application.

• used to be the main way to build systems
• difficult to maintain, evolve and scale

Multi-Tier

Separate different parts of the application into various tiers.

A common model is 3-tier Architecture:

1. Presentation Layer
   • Responsible for user interaction
   • Visual interface
2. Logic Layer
   • Responsible for business logic and processes relevant to business functions
3. Data Layer
   • Responsible for storing, accessing data

Microservices

Split the application into smaller, independent microservices. Each microservice deals with a single service of the application.

Microservices communicate through either HTTP or message queues.

Process

A process is an instance of an application / executable.

Processes are independent from each other.

Each process has its own:

• Processor registers (belonging to a thread)
• Program counters (belonging to a thread)
• Stack pointers (belonging to a thread)
• Memory pages

Each process will have at least one thread: the main thread.

CPUs perform Context Switching, by saving a process's state and loading another process's state to run different processes on one core. This is expensive.

Since Context Switching is expensive, there are other mechanisms like Fibers and Coroutines which are more efficient. However, these are more complex and generally require the application to manage the threads itself (instead of the OS).

Thread

A thread is the unit of execution within a process.

Each thread has its own:

• Stack
• Registers
• Program counters

Threads within a Process share a memory address space. So, threads within a process can communicate. One malfunctioning thread can crash the entire process.

CPUs perform Context Switching on Threads too, similarly to Processes. Switching threads is generally faster than switching processes because there is no need to switch out memory pages.

Go Goroutines

https://www.quora.com/What-is-difference-between-Goroutines-vs-OS-threads

Goroutines use N:M scheduling, where N goroutines are backed by M OS threads.

Empty Contexts

context.TODO() and context.Background() create "empty" contexts.

Background

main function, initialisation, and tests, and as the top-level Context for incoming requests

TODO

when it's unclear which Context to use or it is not yet available (because the surrounding function has not yet been extended to accept a Context parameter).

* these are directly quoted from the library's documentation

HTTP Requests

http.Request interface has a Context() function that returns the context of that request. It also ends if the client disconnects before the request is done.

Context Values

Context can contain values, but it is not wise to use them as they are untyped!

Instead, explicitly pass the values as function parameters!

Context Cancelling

context.WithCancel(parent context.Context) (ctx context.Context, cancel context.CancelFunc)

Context Deadline

Similar to cancel, but provide a deadline where the context will be done.

context.WithDeadline(parent context.Context, d time.Time) (context.Context, context.CancelFunc)

Context Timeout

Similar to deadline, but provide a duration instead of a time.

context.WithTimeout(parent context.Context, timeout time.Duration) (context.Context, context.CancelFunc)

Context Done

ctx.Done() returns a <-chan struct{} that closes when the context is done.

select {
case <-ctx.Done():
    // context is done!
    return
case result := <-data:
    // await data from channel
default:
    // if not using a data channel, use a default clause instead
}

Context Errors

ctx.Err()

If Done is not yet closed, Err returns nil. If Done is closed, Err returns a non-nil error explaining why: Canceled if the context was canceled or DeadlineExceeded if the context's deadline passed. After Err returns a non-nil error, successive calls to Err return the same error.

Database Normalisation

https://en.wikipedia.org/wiki/Database_normalization

1. Reduce database into normal form
2. Split table into multiple smaller tables, that when joined together will form the original table

• Reduces data redundancy
• Improves data integrity

Database Denormalisation

https://en.wikipedia.org/wiki/Denormalization

Strategy used on a previously normalised database, aims to

• Improve read performance (because joins are slow)
• At expense of losing write performance, by adding redundant copies of data or grouping data
  • Need to ensure that redundant data is kept consistent
• Not the same as an un-normalised database!

Simple forms of denormalisation

• Keep track of the count of a particular data (e.g. number of Groups a User has)
  • Useful for one-to-many relationship
• Adding attributes to a relation from another relation, which it is joined to