ByteByteGo - Youtube Cheat Sheet (DRAFT) by woshiamiaojiang

1. Batch Proces­sing: Kafka groups messages together into batches, which reduces the network calls and disk I/O operat­ions, thereby increasing throug­hput.

2. Sequential I/O: Kafka stores messages in a sequen­tial, ordered manner on disk. This takes advantage of the underlying file system and disk's fast sequential read and write capabi­lities.

3. Zero Copy: Kafka uses the zero-copy technique to transfer data directly from the file system cache to network buffers, which reduces CPU usage.

4. Distri­buted System: Kafka is a distri­buted system that can be scaled horizo­ntally by adding more nodes to the cluster. This allows it to handle high volumes of data and traffic.

5. Immutable Messages: Once written, messages in Kafka are immutable and are not updated, which simplifies the system and improves perfor­mance.

6. In-Memory Offsets: Kafka stores the offsets of messages in memory, which makes reading messages very fast.

1. URL Parsing: The browser parses the URL to extract the protocol (e.g., HTTP, HTTPS), domain name (e.g., www.ex­amp­le.com), and any additional path or query parame­ters.

2. DNS Lookup: The browser checks its cache to find the IP address associated with the domain name. If not found, it sends a DNS (Domain Name System) lookup request to a DNS server to obtain the IP address.

3. TCP Connec­tion: The browser establ­ishes a TCP (Trans­mission Control Protocol) connection with the web server at the obtained IP address. This involves a three-way handshake to establish a reliable connec­tion.

4. HTTP Request: The browser sends an HTTP (Hypertext Transfer Protocol) request to the web server. The request includes the HTTP method (e.g., GET, POST), the requested resource (e.g., /index.html), headers (e.g., user-a­gent, cookies), and other optional data.

5. Server Proces­sing: The web server receives the HTTP request and processes it. This may involve accessing databases, executing server­-side code, or retrieving files from the server's file system.

6. HTTP Response: The web server generates an HTTP response containing the requested resource, along with headers and a status code. The response may also include cookies, caching direct­ives, or other metadata.

7. Data Transfer: The server sends the HTTP response back to the browser over the establ­ished TCP connec­tion. The response is divided into packets and transm­itted over the network.

8. Browser Rendering: The browser receives the response and begins rendering the web page. It parses the HTML, executes any embedded scripts, and fetches additional resources like CSS styles­heets, images, or JavaScript files referenced in the HTML.

9. Page Display: The browser combines the received resources to render and display the web page to the user. This includes rendering text, applying styles, and executing JavaScript code to add intera­cti­vity.

𝐒𝐮𝐢𝐭𝐚𝐛𝐥𝐞 𝐒𝐜𝐞𝐧𝐚𝐫𝐢𝐨𝐬:
- In-memory solution
- Read heavy system
- Data is not frequently updated

𝐂𝐚𝐜𝐡𝐢𝐧𝐠 𝐓𝐞𝐜𝐡𝐧𝐢­𝐪𝐮𝐞𝐬:
- Cache aside
- Write-­through
- Read-t­hrough
- Write-­around
- Write-back

𝐂𝐚𝐜𝐡𝐞 𝐄𝐯𝐢𝐜𝐭𝐢𝐨𝐧 𝐀𝐥𝐠𝐨𝐫𝐢­𝐭𝐡𝐦𝐬:
- Least Recently Used (LRU)
- Least Frequently Used (LFU)
- First-in First-out (FIFO)
- Random Replac­ement (RR)

𝐊𝐞𝐲 𝐌𝐞𝐭𝐫𝐢𝐜𝐬:
- Cache Hit Ratio
- Latency
- Throughput
- Invali­dation Rate
- Memory Usage
- CPU usage
- Network usage

𝐎𝐭𝐡𝐞𝐫 𝐢𝐬𝐬𝐮𝐞𝐬:
- Thunder herd on cold start
- Time-t­o-live (TTL)

The China Train tickets booking system has similar challenges as the Ticket­master system:

Very high concurrent visits during peak hours.

The QPS for checking remaining tickets and orders is very high

A lot of bots

The solutions

Separate read and write requests. Because anxious users kept refreshing the web page to check if there were tickets available, the system could under huge pressure.

To handle the calcul­ation and query in memory, the remaining ticket components were moved entirely to GemFire. It is possible to fit the entire country's train tickets into several Gigabytes of memory.
In addition, the order query component was moved to GemFire to reduce the load on the order database. Hadoop was used to store historical orders.

Leverage public cloud for elastic capacity.

Ban bots. It reduced the traffic by 95%.

Increase the bandwidth of the system.

Increase system availa­bility by setting up more data centers in different cities.

Design multiple emergency plans.

What people think it should look like
The interv­iewer is probably expecting something on the left side.

Micros­ervice is used to decompose the system into small compon­ents.

Each service has its own database. Use cache heavily.

The service is sharded.

The services talk to each other asynch­ron­ously through message queues.

The service is implem­ented using Event Sourcing with CQRS.

Showing off knowledge in distri­buted systems such as eventual consis­tency, CAP theorem, etc.

What it actually is
Stack Overflow serves all the traffic with only 9 on-premise web servers, and it’s on monolith! It has its own servers and does not run on the cloud.

Here are the steps for generating the QR code:

When you want to pay for your shopping, the cashier tallies up all the goods and calculates the total amount due, for example, $123.45. The checkout has an order ID of SN129803. The cashier clicks the “checkout” button.

The cashier’s computer sends the order ID and the amount to PSP.

The PSP saves this inform­ation to the database and generates a QR code URL.

PSP’s Payment Gateway service reads the QR code URL.

The payment gateway returns the QR code URL to the merchant’s computer.

The merchant’s computer sends the QR code URL (or image) to the checkout counter.

The checkout counter displays the QR code.

These 7 steps are completed in less than a second. Now it’s the consumer’s turn to pay from their digital wallet by scanning the QR code:

The consumer opens their digital wallet app to scan the QR code.

After confirming the amount is correct, the client clicks the “pay” button.

The digital wallet App notifies the PSP that the consumer has paid the given QR code.

The PSP payment gateway marks this QR code as paid and returns a success message to the consumer’s digital wallet App.

The PSP payment gateway notifies the merchant that the consumer has paid the given QR code.

Over to you: I have detailed how to pay using a dynamic QR code. It is dynamic because the QR code is dynami­cally generated each time. But sometimes, you could pay by scanning a printed QR code in a merchant’s shop, which is called the static QR code. Do you know how a static QR code works?

Option 1: Use a Set data structure to check if a URL already exists or not. Set is fast, but it is not space-­eff­icient.

Option 2: Store URLs in a database and check if a new URL is in the database. This can work but the load to the database will be very high.

Option 3: 𝐁𝐥𝐨𝐨𝐦 𝐟𝐢𝐥𝐭𝐞𝐫. This option is preferred. Bloom filter was proposed by Burton Howard Bloom in 1970. It is a probab­ilistic data structure, that is used to test whether an element is a member of a set.

🔹 false: the element is definitely not in the set.

🔹 true: the element is probably in the set.

False-­pos­itive matches are possible, but false negatives are not.

The diagram below illust­rates how the Bloom filter works. The basic data structure for the Bloom filter is Bit Vector. Each bit represents a hashed value.

Step 1 - With the growth of the user base, one single applic­ation server cannot handle the traffic anymore. We put the applic­ation server and the database server into two separate servers.

Step 2 - The business continues to grow, and a single applic­ation server is no longer enough. So we deploy a cluster of applic­ation servers.

Step 3 - Now the incoming requests have to be routed to multiple applic­ation servers, how can we ensure each applic­ation server gets an even load? The load balancer handles this nicely.

Step 4 - With the business continuing to grow, the database might become the bottle­neck. To mitigate this, we separate reads and writes in a way that frequent read queries go to read replicas. With this setup, the throughput for the database writes can be greatly increased.

Step 5 - Suppose the business continues to grow. One single database cannot handle the load on both the inventory table and user table. We have a few options:

1. Vertical scaling. Adding more power (CPU, RAM, etc.) to the database server. It has a hard limit.
2. Horizontal scaling by adding more database servers.
3. Adding a caching layer to offload read requests.

Step 6 - Now we can modularize the functions into different services. The archit­ecture becomes servic­e-o­riented / micros­ervice.

In S3, an object resides in a bucket. The path looks like this: /bucke­t-t­o-s­har­e/s­cri­pt.txt. The bucket only has metadata. The object has metadata and the actual data.

The diagram below (Figure 2) illust­rates how file uploading works. In this example, we first create a bucket named “bucke­t-t­o-s­hare” and then upload a file named “scrip­t.txt” to the bucket.

1. The client sends an HTTP PUT request to create a bucket named “bucke­t-t­o-s­hare.” The request is forwarded to the API service.

2. The API service calls Identity and Access Management (IAM) to ensure the user is authorized and has WRITE permis­sion.

3. The API service calls the metadata store to create an entry with the bucket info in the metadata database. Once the entry is created, a success message is returned to the client.

4. After the bucket is created, the client sends an HTTP PUT request to create an object named “scrip­t.txt”.

5. The API service verifies the user’s identity and ensures the user has WRITE permission on the bucket.

6. Once validation succeeds, the API service sends the object data in the HTTP PUT payload to the data store. The data store persists the payload as an object and returns the UUID of the object.

7. The API service calls the metadata store to create a new entry in the metadata database. It contains important metadata such as the object_id (UUID), bucket_id (which bucket the object belongs to), object­_name, etc.

Stocks go up and down. Do you know what data structure is used to effici­ently match buy and sell orders?

Stock exchanges use order books. An order book is an electronic list of buy and sell orders, organized by price levels. It has a buy book and a sell book, where each side of the book contains a bunch of price levels, and each price level contains a list of orders (first in first out).

The diagram below is an example of price levels and the queued quantity at each price level.


So what happens when you place a market order to buy 2700 shares in the diagram?

- The buy order is matched with all the sell orders at price 100.10, and the first order at price 100.11 (illus­trated in light red).

- Now because of the big buy order which “eats up” the first price level on the sell book, the best ask price goes up from 100.10 to 100.11.

- So when the market is bullish, people tend to buy stocks aggres­sively, and the price goes up and up.

An efficient data structure for an order book must satisfy:

- Constant lookup time. Operations include: get volume at a price level or between price levels, query best bid/ask.

- Fast add/ca­nce­l/e­xec­ute­/update operat­ions, preferably O(1) time comple­xity. Operations include: place a new order, cancel an order, and match an order.

1 in-memory database
2 io multip­lexing a single thread to wait on many sockets
3 efficient data structure

1. Client Hello: The client initiates a secure connection by sending a "­Client Hello" message to the server. This message includes inform­ation about the client's supported encryption algorithms and other parame­ters.

2. Server Hello: The server responds with a "­Server Hello" message, selecting the strongest encryption algorithm and other parameters that both the client and server support.

3. Certif­icate Exchange: The server sends its digital certif­icate to the client. The certif­icate contains the server's public key, which is used for encryption and authen­tic­ation.

4. Certif­icate Valida­tion: The client verifies the authen­ticity of the server's certif­icate. It checks if the certif­icate is issued by a trusted Certif­icate Authority (CA) and if it has not expired or been revoked.

5. Key Exchange: The client generates a random symmetric encryption key and encrypts it using the server's public key. This encrypted key is sent to the server.

6. Session Key: The server decrypts the encrypted key using its private key and obtains the symmetric encryption key. Both the client and server now have the same session key for secure commun­ica­tion.

7. Secure Commun­ica­tion: The client and server use the session key to encrypt and decrypt data exchanged between them. This ensures that the data transm­itted over the network is protected from eavesd­ropping and tampering.

8. HTTPS Connec­tion: From this point onwards, the client and server commun­icate using the secure HTTPS protocol. All HTTP requests and responses are encrypted and decrypted using the session key.

1.lead­er-­fol­lower model

2.mult­i-l­eader
Multi-­leader replic­ation provides high availa­bility but requires careful design around consensus, conflict detection, and resolution mechan­isms.
The primary advantage of this model is increased write availa­bility
disadv­antage: Managing Conflict:
2.1Last Write Wins
2.2Con­fli­ct-free Replicated Data Types (CRDTs)
CRDTs allow for seamless reconc­ili­ation of confli­cting changes by merging them.
2.3Ope­rat­ional Transf­orm­ation
Operat­ional transf­orm­ation is often used in real-time collab­orative applic­ations. It takes the operation itself into account, not just the state of the data.
2.4App­lic­ati­on-­spe­cific Resolution

3.lead­erless replic­ation
Quorum Writes and Reads
In this system, we use three important values.
'n' is the total number of nodes in our system.
'W', the write quorum, is the minimum number of nodes that need to agree for a write to be considered succes­sful.
'r', the read quorum, is the minimum number of nodes that need to agree for a read to be valid.
For strong consis­tency, a general guideline is to have w + r > n. It ensures that any read overlaps with any write and returns the most recent value.

Fixed Window Counter

Sliding Window Log

Sliding Window Counter

Token Bucket

Leaky Bucket

A forward proxy is a server that sits between a group of client machines and the internet.

A reverse proxy sits between the internet and the web servers. It intercepts the requests from clients and talks to the web server on behalf of the clients.

A file descriptor represents an open file. It is a unique number assigned by the operating system to each file. It is an abstra­ction for working with files. We need to use file descri­ptors to read from or write to files in our program. Each process maintains its own file descriptor table.

The diagram below shows the layered archit­ecture in Linux filesy­stem. Let’s take process 1234 as an example.


🔹 In User Space
When we open a file called “fileA.txt” in Process 1234, we get file descriptor fd1, which is equal to 3. We can then pass the file descriptor to other functions to write data to the file.

🔹 In Kernel Space
In Linux kernel, there is a process table to maintain the data for the processes. Each process has an entry in the table. Each process maintains a file descriptor table, with file descri­ptors as its indices. Notice that file descri­ptors 0,1 and 2 are reserved in each file descriptor table to represent stdin, stdout, and stderr.

The file pointer points to an entry in the open file table, which has inform­ation about open files across all processes. Multiple file descri­ptors can point to the same file table entry. For example, file descriptor 0, 1 and 2 points to the same open file table entry.

Since different open file table entries can represent the same file, it is a waste of resources to store the file static inform­ation so many times. We need another abstra­ction layer called ‘vnode table’ to store the static data.

In each file table entry, there is a vnode pointer, which points to an entry in vnode table. The static inform­ation includes file type, function pointers, reference counts, inode etc. inode describes a physical object in the filesy­stem.

🔹 In Filesystem
The inode array element stores the actual file inform­ation, including permission mode, owners, timest­amps, etc. inode also points to the data blocks stored in the filesy­stem.

Over to you: When we close a file in a program, do you know which entries are deleted in these data struct­ures?

A Process means a program is in execution. When a program is loaded into the memory and becomes active, the program becomes a process. The process requires some essential resources such as registers, program counter, and stack.

A Thread is the smallest unit of execution within a process.

The following process explains the relati­onship between program, process, and thread.

1. The program contains a set of instru­ctions.

2. The program is loaded into memory. It becomes one or more running processes.

3. When a process starts, it is assigned memory and resources. A process can have one or more threads. For example, in the Microsoft Word app, a thread might be respon­sible for spelling checking and the other thread for inserting text into the doc.

Main differ­ences between process and thread:

🔹 Processes are usually indepe­ndent, while threads exist as subsets of a process.

🔹 Each process has its own memory space. Threads that belong to the same process share the same memory.

🔹 A process is a heavyw­eight operation. It takes more time to create and terminate.

🔹 Context switching is more expensive between processes.

🔹 Inter-­thread commun­ication is faster for threads.

Step 1: Bank A sends a message with transfer details to Regional Processor A in New York. The destin­ation is Bank B.

Step 2: Regional processor validates the format and sends it to Slice Processor A. The Regional Processor is respon­sible for input message validation and output message queuing. The Slice Processor is respon­sible for storing and routing messages safely.

Step 3: Slice Processor A stores the message.

Step 4: Slice Processor A informs Regional Processor A the message is stored.

Step 5: Regional Processor A sends ACK/NAK to Bank A. ACK means a message will be sent to Bank B. NAK means the message will NOT be sent to Bank B.

Step 6: Slice Processor A sends the message to Regional Processor B in London.

Step 7: Regional Processor B stores the message tempor­arily.

Step 8: Regional Processor B assigns a unique ID MON (Message Output Number) to the message and sends it to Slice Processor B

Step 9: Slice Processor B validates MON.

Step 10: Slice Processor B authorizes Regional Processor B to send the message to Bank B.

Step 11: Regional Processor B sends the message to Bank B.

Step 12: Bank B receives the message and stores it.

Step 13: Bank B sends UAK/UNK to Regional Processor B. UAK (user positive acknow­led­gment) means Bank B received the message without error; UNK (user negative acknow­led­gment) means Bank B received checksum failure.

Step 14: Regional Processor B creates a report based on Bank B’s response, and sends it to Slice Processor B.

Step 15: Slice Processor B stores the report.

Step 16 - 17: Slice Processor B sends a copy of the report to Slice Processor A. Slice Processor A stores the report.

How does a modern stock exchange achieve micros­econd latency? The principal is:

Do less on the critical path
- Fewer tasks on the critical path
- Less time on each task
- Fewer network hops
- Less disk usage

For the stock exchange, the critical path is:
- start: an order comes into the order manager
- mandatory risk checks
- the order gets matched and the execution is sent back
- end: the execution comes out of the order manager



Other non-cr­itical tasks should be removed from the critical path.

We put together a design as shown in the diagram:

- deploy all the components in a single giant server (no contai­ners)

- use shared memory as an event bus to commun­icate among the compon­ents, no hard disk

- key components like Order Manager and Matching Engine are single­-th­readed on the critical path, and each pinned to a CPU so that there is no context switch and no locks

- the single­-th­readed applic­ation loop executes tasks one by one in sequence

- other components listen on the event bus and react accord­ingly

To write sargable queries:
· Avoid using functions or calcul­ations on indexed columns in the WHERE clause
· Use direct compar­isons when possible, instead of wrapping the column in a function
· If we need to use a function on a column, consider creating a computed column or a functi­on-­based index, if the database system supports it

1. 运用自动扩缩­容，监控和报警
2. 扩展微服务架­构，根­据具体­服务的­需求进­行独立扩展
3. 优化缓存策略
4. 确保负载均衡
5. 冗余和故障转­移，数­据中心故障
1. 水平扩展（H­ori­zontal Scalin­g）：­通过增­加服务­器实例­来分散­负载，­使系统­能够处­理更多­的并发­请求。­这可以­通过负­载均衡­器来实­现，将­请求分­发到多­个服务器上。
2. 多级缓存（C­ach­ing­）：使­用缓存­来存储­频繁访­问的数­据，减­少对后­端数据­库或其­他资源­的访问­次数。­常见的­缓存技­术包括­内存缓­存（如­Red­is）­和分布­式缓存­（如M­emc­ached）。
3. 异步处理（A­syn­chr­onous Proces­sin­g）：­将耗时­的操作­转化为­异步任­务，通­过消息­队列或­任务队­列来处­理。这­样可以­减少请­求的等­待时间­，提高­系统的吞吐量。
4. 数据库优化：­使用合­适的数­据库引­擎和优­化技术­，如索­引、分­区、缓­存查询­结果等­，以提­高数据­库的读­写性能­和并发­处理能力。
5. 无状态设计（­Sta­teless Design­）：尽­量设计­无状态­的系统­，将状­态信息­存储在­外部，­如数据­库或缓­存中。­这样可­以使系­统更容­易水平­扩展，­并提高­系统的­可伸缩性。
6. 限流和熔断（Rate Limiting and Circuit Breaki­ng）­：通过­限制请­求的速­率或在­系统负­载过高­时断开­部分请­求，以­保护系­统免受­过载的影响。
7. 分布式架构（­Dis­tri­buted Archit­ect­ure­）：将­系统拆­分为多­个独立­的服务­，通过­消息传­递或A­PI调­用进行­通信。­这样可­以提高­系统的­可扩展­性和容错性。
8. 监控和自动化­：建立­监控系­统来实­时监测­系统的­性能和­健康状­况，及­时发现­并解决­潜在的­问题。­自动化­部署和­扩展可­以减少­人工干­预，提­高系统­的可靠­性和可维护性。
9. 容错和恢复（­Fault Tolerance and Recove­ry）­：设计­系统以­容忍部­分组件­或服务­的故障­，并能­够快速­恢复。­使用备­份和冗­余机制­来保证­系统的可用性。
10. 性能测试和优­化：进­行系统­的性能­测试和­基准测­试，找­出瓶颈­和性能­瓶颈，­并进行­相应的­优化和调整。

Pub/Sub is convenient but has some delivery restri­ctions. The consumer subscribes to a key and receives the data when a producer publishes data to the same key. The restri­ction is that the data is delivered at most once. If a consumer was down and didn’t receive the published data, that data is lost. Also, the data is not persisted on disk. If Redis goes down, all Pub/Sub data is lost. Pub/Sub is suitable for metrics monitoring where some data loss is accept­able.

The List data structure in Redis can construct a FIFO (First­-In­-Fi­rst­-Out) queue. The consumer uses BLPOP to wait for messages in blocking mode, so a timeout should be applied. Consumers waiting on the same List form a consumer group where each message is consumed by only one consumer. As a Redis data structure, List can be persisted to disk.

Stream solves the restri­ctions of the above two methods. Consumers choose where to read messages from - “$” for new messages, “<i­d>” for a specific message id, or “0-0” for reading from the start.

Fan-out

Asynch­ronous Processing

Rate Limiting

Decoupling

Horizontal Scalab­ility

Message Persis­tence

Batch Processing

Message Ordering

WWW-Au­the­nticate is the most basic method. You are asked for the username and password by the browser. As a result of the inability to control the login life cycle, it is seldom used today.

A finer control over the login life cycle is sessio­n-c­ookie. The server maintains session storage, and the browser keeps the ID of the session. A cookie usually only works with browsers and is not mobile app friendly.

To address the compat­ibility issue, the token can be used. The client sends the token to the server, and the server validates the token. The downside is that the token needs to be encrypted and decrypted, which may be time-c­ons­uming.

JWT is a standard way of repres­enting tokens. This inform­ation can be verified and trusted because it is digitally signed. Since JWT contains the signature, there is no need to save session inform­ation on the server side.

By using SSO (single sign-on), you can sign on only once and log in to multiple websites. It uses CAS (central authen­tic­ation service) to maintain cross-site inform­ation

By using OAuth 2.0, you can authorize one website to access your inform­ation on another website

B-Tree
B-Tree is the most widely used indexing data structure in almost all relational databases.

The basic unit of inform­ation storage in B-Tree is usually called a “page”. Looking up a key traces down the range of keys until the actual value is found.

LSM-Tree
LSM-Tree (Log-S­tru­ctured Merge Tree) is widely used by many NoSQL databases, such as Cassandra, LevelDB, and RocksDB.

LSM-trees maintain key-value pairs and are persisted to disk using a Sorted Strings Table (SSTable), in which the keys are sorted.

Level 0 segments are period­ically merged into Level 1 segments. This process is called compac­tion.

The biggest difference is probably this:

B-Tree enables faster reads

LSM-Tree enables fast writes

A search engine works in 3 stages:

The crawler reads the page content (HTML code) and follows the hyperlink to read more web pages.

The prepro­cessor also works in 3 steps:

It removes HTML tags and ‘Stop’ words, which are words like ‘a’ or ‘an’ or ‘the.’ It also removes other noise that is not relevant to the web page's content, for example, the discla­imer.

Then the keywords form structured indices, called forward indices and inverted indices.

The prepro­cessor calculates the hyperlink relati­ons­hips, for example, how many hyperlinks are on the web page and how many hyperlinks point to it.

When a user types in a search term, the search engine uses the indices and ranking algorithms to rank the web pages and presents the search results to the user.

How do we make our website rank higher in search results? The diagram below shows some ways to do this.

Optimize website structure:

We need to make it easier for the crawler to crawl our website. Remove anything the crawler cannot read, including flash, frames, and dynamic URLs. Make the website hierarchy less deep, so the web pages are less distant from the main home page.

The URLs must be short and descri­ptive. Try to include keywords in the URLs, as well. It will also help to use HTTPS. But don’t use underscore in the URL because that will screw up the tokeni­zation.

Choose the keywords to optimize for:

Keywords must be relevant to what the website is selling, and they must have business values. For example, a keyword is considered valuable if it’s a popular search, but has fewer search results.

Optimize the web page

The crawler crawls the HTML contents. Therefore the title and descri­ption should be optimized to include keywords and be concise. The body of the web page should include relevant keywords.

Another aspect is the user experi­ence. In May 2020, Google published Core Web Vitals, officially listing user experience as an important factor of page ranking algori­thms.

External link

If our website is referenced by a highly­-ranked website, it will increase our website’s ranking. So carefully building external links is important. Publishing high-q­uality content on your website which is useful to other users, is a good way to attract external links.

Over to you: What are your top SEO recomm­end­ations?

Token based

Step 1 - the user enters their password into the client, and the client sends the password to the Authen­tic­ation Server.

Step 2 - the Authen­tic­ation Server authen­ticates the creden­tials and generates a token with an expiry time.

Steps 3 and 4 - now the client can send requests to access server resources with the token in the HTTP header. This access is valid until the token expires.

HMAC based

This mechanism generates a Message Authen­tic­ation Code (signa­ture) by using a hash function (SHA256 or MD5).

Steps 1 and 2 - the server generates two keys, one is Public APP ID (public key) and the other one is API Key (private key).

Step 3 - we now generate a HMAC signature on the client side (hmac A). This signature is generated with a set of attributes listed in the diagram.

Step 4 - the client sends requests to access server resources with hmac A in the HTTP header.

Step 5 - the server receives the request which contains the request data and the authen­tic­ation header. It extracts the necessary attributes from the request and uses the API key that’s stored on the server side to generate a signature (hmac B.)

Steps 6 and 7 - the server compares hmac A (generated on the client side) and hmac B (generated on the server side). If they are matched, the requested resource will be returned to the client.

Question - How does HMAC authen­tic­ation ensure data integrity? Why do we include “request timestamp” in HMAC signature genera­tion?

- Business Service
- Add/de­let­e/u­pdate restaurant inform­ation
- Customers view restaurant details
- Locati­on-­based Service
- Given a radius and location, return a list of nearby restau­rants

How are the restaurant locations stored in the database so that LBS can return nearby restau­rants effici­ently?

Store the latitude and longitude of restau­rants in the database? The query will be very ineffi­cient when you need to calculate the distance between you and every restau­rant.

One way to speed up the search is using the geohash algorithm.

First, divide the planet into four quadrants along with the prime meridian and equator：

- Latitude range [-90, 0] is repres­ented by 0

- Latitude range [0, 90] is repres­ented by 1

- Longitude range [-180, 0] is repres­ented by 0

- Longitude range [0, 180] is repres­ented by 1

Second, divide each grid into four smaller grids. Each grid can be repres­ented by altern­ating between longitude bit and latitude bit.

So when you want to search for the nearby restau­rants in the red-hi­ghl­ighted grid, you can write SQL like:

SELECT * FROM geohas­h_index WHERE geohash LIKE

01%

Geohash has some limita­tions. There can be a lot of restau­rants in one grid (downtown New York), but none in another grid (ocean). So there are other more compli­cated algorithms to optimize the process. Let me know if you are interested in the details.

Design princi­ples:

1. Less is more - less element on the web page, fewer data queries to the database, fewer web requests, fewer system depend­encies

2. Short critical path - fewer hops among services or merge into one service

3. Async proces­sing- use message queues to handle high TPS

4. Isolation - isolate static and dynamic contents, isolate processes and databases for rare items

5. Overse­lling is bad. When to decrease the inventory is important

6. User experience is important. We definitely don’t want to inform users that they have succes­sfully placed orders but later tell them no items are actually available

Happy shopping! If I missed anything, please leave a comment.

REST
Proposed in 2000, REST is the most used style. It is often used between front-end clients and back-end services. It is compliant with 6 archit­ectural constr­aints. The payload format can be JSON, XML, HTML, or plain text.

GraphQL
GraphQL was proposed in 2015 by Meta. It provides a schema and type system, suitable for complex systems where the relati­onships between entities are graph-­like. For example, in the diagram below, GraphQL can retrieve user and order inform­ation in one call, while in REST this needs multiple calls.

GraphQL is not a replac­ement for REST. It can be built upon existing REST services.

Web socket
Web socket is a protocol that provides full-d­uplex commun­ica­tions over TCP. The clients establish web sockets to receive real-time updates from the back-end services. Unlike REST, which always “pulls” data, web socket enables data to be “pushed”.

Webhook
Webhooks are usually used by third-­party asynch­ronous API calls. In the diagram below, for example, we use Stripe or Paypal for payment channels and register a webhook for payment results. When a third-­party payment service is done, it notifies the payment service if the payment is successful or failed. Webhook calls are usually part of the system’s state machine.

gRPC
Released in 2016, gRPC is used for commun­ica­tions among micros­erv­ices. gRPC library handles encodi­ng/­dec­oding and data transm­ission.

SOAP
SOAP stands for Simple Object Access Protocol. Its payload is XML only, suitable for commun­ica­tions between internal systems.

Load balancer
A load balancer evenly distri­butes incoming traffic among web servers that are defined in a load-b­alanced set.

Web servers
Web server returns HTML pages or JSON response for rendering.

Databases: vertical scaling and horizontal scaling

Cache
A cache is a temporary storage area that stores the result of expensive responses or frequently accessed data in memory so that subsequent requests are served more quickly.

CDN
A CDN is a network of geogra­phi­cally dispersed servers used to deliver static content. CDN servers cache static content like images, videos, CSS, JavaScript files, etc.

Message queue
A message queue is a durable component, stored in memory, that supports asynch­ronous commun­ica­tion.

Logging, metrics, automation
When working with a small website that runs on a few servers, logging, metrics, and automation support are good practices but not a necessity. However, now that your site has grown to serve a large business, investing in those tools is essential.

Step 1: The raw video data is captured by a microphone and camera. The data is sent to the server side.

Step 2: The video data is compressed and encoded. For example, the compre­ssing algorithm separates the background and other video elements. After compre­ssion, the video is encoded to standards such as H.264. The size of the video data is much smaller after this step.

Step 3: The encoded data is divided into smaller segments, usually seconds in length, so it takes much less time to download or stream.

Step 4: The segmented data is sent to the streaming server. The streaming server needs to support different devices and network condit­ions. This is called ‘Adaptive Bitrate Stream­ing.’ This means we need to produce multiple files at different bitrates in steps 2 and 3.

Step 5: The live streaming data is pushed to edge servers supported by CDN (Content Delivery Network.) Millions of viewers can watch the video from an edge server nearby. CDN signif­icantly lowers data transm­ission latency.

Step 6: The viewers’ devices decode and decompress the video data and play the video in a video player.

Steps 7 and 8: If the video needs to be stored for replay, the encoded data is sent to a storage server, and viewers can request a replay from it later.

Standard protocols for live streaming include:

RTMP (Real-Time Messaging Protocol): This was originally developed by Macromedia to transmit data between a Flash player and a server. Now it is used for streaming video data over the internet. Note that video confer­encing applic­ations like Skype use RTC (Real-Time Commun­ica­tion) protocol for lower latency.

HLS (HTTP Live Stream­ing): It requires the H.264 or H.265 encoding. Apple devices accept only HLS format.

DASH (Dynamic Adaptive Streaming over HTTP): DASH does not support Apple devices.
Both HLS and DASH support adaptive bitrate streaming.

Over to you: What are some of the optimi­zations that can be done in this process? Which type of storage is suitable for video persis­tence in step 7

🔹Seria­liz­alble: This is the highest isolation level. Concurrent transa­ctions are guaranteed to be executed in sequence.

🔹Repea­table Read: Data read during the transa­ction stays the same as the transa­ction starts.

🔹Read Committed: Data modifi­cation can only be read after the transa­ction is committed.

🔹Read Uncomm­itted: The data modifi­cation can be read by other transa­ctions before a transa­ction is committed.

The isolation is guaranteed by MVCC (Multi­-Ve­rsion Consis­tency Control) and locks.

The diagram below takes Repeatable Read as an example to demons­trate how MVCC works:

There are two hidden columns for each row: transa­cti­on_id and roll_p­ointer. When transa­ction A starts, a new Read View with transa­cti­on_­id=201 is created. Shortly afterward, transa­ction B starts, and a new Read View with transa­cti­on_­id=202 is created.

Now transa­ction A modifies the balance to 200, a new row of the log is created, and the roll_p­ointer points to the old row. Before transa­ction A commits, transa­ction B reads the balance data. Transa­ction B finds that transa­cti­on_id 201 is not committed, it reads the next committed record­(tr­ans­act­ion­_id­=200).

Even when transa­ction A commits, transa­ction B still reads data based on the Read View created when transa­ction B starts. So transa­ction B always reads the data with balanc­e=100.

Step 1: “Commands come from the user through the host interface” [2]. The interface can be Serial ATA (SATA) or PCI Express (PCIe).

Step 2: “The processor in the SSD controller takes the commands and passes them to the flash contro­ller” [2].

Step 3: “SSDs also have embedded RAM memory, generally for caching purposes and to store mapping inform­ation” [2].

Step 4: “The packages of NAND flash memory are organized in gangs, over multiple channels” [2].

The second diagram illust­rates how the logical and physical pages are mapped, and why this archit­ecture is fast.

SSD controller operates multiple FLASH particles in parallel, greatly improving the underlying bandwidth. When we need to write more than one page, the SSD controller can write them in parallel [3], whereas the HDD has a single head and it can only read from one head at a time.

Every time a HOST Page is written, the SSD controller finds a Physical Page to write the data and this mapping is recorded. With this mapping, the next time HOST reads a HOST Page, the SSD knows where to read the data from FLASH [3].

𝐀𝐭-𝐦𝐨𝐬𝐭 𝐨𝐧𝐜𝐞
As the name suggests, at-most once means a message will be delivered not more than once. Messages may be lost but are not redeli­vered. This is how at-most once delivery works at the high level.

Use cases: It is suitable for use cases like monitoring metrics, where a small amount of data loss is accept­able.

𝐀𝐭-𝐥𝐞𝐚𝐬𝐭 𝐨𝐧𝐜𝐞
With this data delivery semantic, it’s acceptable to deliver a message more than once, but no message should be lost.

Use cases: With at-least once, messages won’t be lost but the same message might be delivered multiple times. While not ideal from a user perspe­ctive, at-least once delivery semantics are usually good enough for use cases where data duplic­ation is not a big issue or dedupl­ication is possible on the consumer side. For example, with a unique key in each message, a message can be rejected when writing duplicate data to the database.

𝐄𝐱𝐚𝐜𝐭𝐥𝐲 𝐨𝐧𝐜𝐞
Exactly once is the most difficult delivery semantic to implement. It is friendly to users, but it has a high cost for the system’s perfor­mance and comple­xity.

Use cases: Financ­ial­-re­lated use cases (payment, trading, accoun­ting, etc.). Exactly once is especially important when duplic­ation is not acceptable and the downstream service or third party doesn’t support idempo­tency.

Question: what is the difference between message queues vs event streaming platforms such as Kafka, Apache Pulsar, etc?

𝐀𝐭-𝐦𝐨𝐬𝐭 𝐨𝐧𝐜𝐞
As the name suggests, at-most once means a message will be delivered not more than once. Messages may be lost but are not redeli­vered. This is how at-most once delivery works at the high level.

Use cases: It is suitable for use cases like monitoring metrics, where a small amount of data loss is accept­able.

𝐀𝐭-𝐥𝐞𝐚𝐬𝐭 𝐨𝐧𝐜𝐞
With this data delivery semantic, it’s acceptable to deliver a message more than once, but no message should be lost.

Use cases: With at-least once, messages won’t be lost but the same message might be delivered multiple times. While not ideal from a user perspe­ctive, at-least once delivery semantics are usually good enough for use cases where data duplic­ation is not a big issue or dedupl­ication is possible on the consumer side. For example, with a unique key in each message, a message can be rejected when writing duplicate data to the database.

𝐄𝐱𝐚𝐜𝐭𝐥𝐲 𝐨𝐧𝐜𝐞
Exactly once is the most difficult delivery semantic to implement. It is friendly to users, but it has a high cost for the system’s perfor­mance and comple­xity.

Use cases: Financ­ial­-re­lated use cases (payment, trading, accoun­ting, etc.). Exactly once is especially important when duplic­ation is not acceptable and the downstream service or third party doesn’t support idempo­tency.

Question: what is the difference between message queues vs event streaming platforms such as Kafka, Apache Pulsar, etc?