Mrinal's Blog

Search Engines at scale : From a Beginners POV

Mrinal — Invalid Date

Search Engines at scale from a Beginners POV

6th April, 2026

Last time time we discussed on the basics of search engines and two ways on how does it indexes everything. In this blog I will try to share how these search engines work at scale and handles not thousands but millions or billions of documents.

As search engine grows keeping the entire index on a single machine becomes nearly impossible. We eventually hit physical limits regarding RAM, storage space and processing power. Adding more resources to a single machine is known as vertical scaling which is somewhat costly and offers diminishing returns. The only viable path forward is horizontal scaling, which involves distributing the data across many separate computers. This is called Sharding

Partitioning data horizontally

To distribute data more effectively we need to explain how to route specific documents to specific machines. Two main strategies exist for this allocation which are range based partitioning which assigns documents to shards based on alphaetical or numerical ranges. For example documents starting with A through M go to shard 1 while N through Z go to shard 2. This approach makes range scans easy and effective but can lead to uneven distribution if certain letters are more common. Then comes Hash Based partitioning this applies a mathematical formula to a unique identifier, such as the document ID to deteremine its destination. This ensures an even spread of data across all machines which optimizes storage usage but makes querying by range difficult.

Example of range based partitioning

Now splitting data introduces the distributedd indexing problem. When we replicate data across nodes to secure the loss we must balance consistency and availability. If a user updates a document we must decide how strictly to enforce that update across all replicas before acknowledging success. Relying on consistency would mean that all users see the same data but may slow down the system or have some errors if a node goes down. While if we prioritize availability which will allow the systems to keep functioning during outages but it risks returning stale results.

To answer a user query the system must often ask multiple machines for their portion of the results and combine them. The difficulty is in executing this without the user waiting for the slowest machine in the cluster to respond. If one shard is lagging due to heavy load the entire search experience suffers.

The biggest problem here is the straggler effect. If even one shard is slow (due to high load, hardware issues, or bad luck) the entire query has to wait for that slowest shard. The user doesn’t care which shard is slow they just want fast results.

Query Federation

To allow searching across multiple shards we use a pattern known as scatter gather or query federation. The query lifecycle begins when a coordinator node receives a user request and the node acts as the central conductor. It scatters the request to all relevant shards simultaneously. This parallel execution is important because it allows the system to use the combined processing powwer of of every machine in the cluster and each shard executes the search locally on its own subset of data. Once the shards find their matches they send their individual results back to the coordinator. The coordinator then gathers these partiall results to form a complete response for the user.

The Map-reduce

I am sure till now you have seen many people to read and implement map reduce research paper, inface I did the same :p. While scatter gather describes the flow of data the root computational model is often referred to as Map-Reduce. In the context of a live search query this pattern splits the workload into two distict phases. The Map phase occurs at the shard level when a shard receives a query it maps the search terms against its local index amd ot calculates a relevance score for every matching document and generates a list of candidate results. The shard then filters this list to keep only the most promising candidates which reduces the amount of data that must travel over the network.

Reduce phase takes place on the coordinator node. Here, the system receives the candidate lists from all the shards. It must reduce this multitude of lists into a single, ordered result set. This involves comparing the relevance scores from different shards and sorting them to identify the absolute best matches and by separating the work into a mapping step that runs in parallel and a reduction step that consolidates the output the system can process massive datasets successfully without overwhelming a single machine.

Coordinating and Merging Results

It requires careful sorting logic. Each shard returns a list of documents ranked by relevance based on its local view of the data amd the coordinator cannot simply append these lists together. It must merge them into a single, sorted list. This process involves taking the top results from each shard and re-ranking them to find the global best matches.

If a user requests the top ten results, the coordinator cannot just ask for ten items from each shard. It might need to retrieve the top fifty or one hundred results from each shard to ensure accuracy and this buffer is necessary because a document ranked fifteenth on one specific shard might actually be more relevant globally than the top result on another shard. The coordinator uses a priority queue or a merge algorithm to compare the heads of these lists and select the highest scoring documents until the final page of results is complete.

We are all covered for the second part of this Search Engines series next week we will be moving ahead with the last part of this series which is the study of architecture of ElasticSearch Hope I was able to add some value to your today's learning ^^
Happy Learning Anon

Search Engines 101 : From a Beginners POV

Mrinal — Invalid Date

Search Engines from Beginners POV

1st March, 2026

Search engines are simple to define with respect to their core job which is to return the most relevant documents for a query in milliseconds. But still it is arguably the most complex software systems in existence.

How Inverted Indices Work

To understand the "Search" part of search engines, one must first understand why traditional databases fail at it. In a standard relational database (like PostgreSQL or MySQL), data is stored in rows. If you want to find a specific word in a description column, the database effectively has to open every single row and scan the text to see if the word exists. In computer science terms, this is an \( O(n) \) operation which means as my data will grow, the speed to reach that drops linearly. For a web scale dataset this is unacceptably slow.
The solution for this is Inverted Index

Instead of mapping Documenting terms like a book's chapter, an inverted index maps the terms according to the documents.

Inverted Index consists of two components, first one is Term Dictionary which is an aplhabetized list of every unique word (term) found in entire dataset. This is often kept in memory using a Hash Map or a Trie(Prefix tree) for speed. Second one is Posting Lists for every term in the dictionary, there is an associated list of document IDs where that term appears.

This makes a search engine to query millions of documents in thee exact same amount of time it takes to query one but the questions is how does it even happen ??

When the user searches for the word "data," the engine does not scan documents. Instead it hashes the word "data" and then jumps directly to that entry in the term dictionary (an \(O(1)\) or constant time operation). Than retrieves the the posting list like [Doc1, Doc4, Doc87]

However, this raw speed relies on exact matching. A computer views "Running" and "run" as completely different binary strings. If our index is too literal, it becomes brittle. But if we just store every word, how do we handle "running" vs "run" or typos ??

Tokenization, Stemming and Analysis

So to handle the variation of human language is not by indexing instead by transforming the data before it enters the index. This process is called Analysis. When we insert text into a search engine, it doesn't just store the string. It passes the text through an Analysis Chain, a pipeline of processors that standardize the text

The Analysis Pipeline

(Character filters) The raw stream is cleaned, like the stripping HTML tags to make <"h1">Hello<"/h1"> into Hello or converting & to and. Then comes (Tokenizer) the text is chopped into discrete chunks called tokens. A standard whitespace tokenizer splits "Hello, myself Mrinal" into [Hello, myself, Mrinal]

(Tokenizers) the text is chopped into discrete chunks called tokens. A standard whitespace tokenizer splits "The quick brown fox" into [The, quick, brown, fox]

Now there are few steps which get followed for the process where the normalization happens. The tokens flow through a series of transformations

Lowercasing : "The" becomes "the". this ensures searches are case insensitive.
Stop word removal : Common words with little semantic value (like "a", "an", "the", "is") are often removed to save space and reduce noice.
Stemming : This algorithm reduces words to their root form. It chops suffixes, turning "running," "runs," and "ran" all into the root token "run." This ensures a search for one tense finds all variations.
Synonyms : You can inject rules where if the engine sees "notebook," it also indexes the token "laptop."

Why "CAT" != "cat != "kitten"

Without this pipeline, the byte sequence for "CAT" does not match "cat". By running both the document text and the user's query text through the same analysis chain, we ensure they meet in the middle. If the document contains "Running" and the user searches "run," the analyzer reduces both to "run," creating a match

Now we have a system that can tolerate human variation and retrieve all documents containing our terms. However, mere retrieval is not enough. If I search for "News," I might get 10 millions documents. So we can index text effectively, but how do we actually decide what results matter most ??

Ranking and Relevance

We decide what matters most by calculating a Relevance Score for every matching document. This is not boolean "yes/no" but a floating point number representing how well a document matches the query. Although newer engines uses machine learning (learning to rank), the foundational algorithms rely on statitical probablity

TF-IDF | Measuring the rarity

Term Frequency Inverse Document Frequency. This method quantifies how important a word is to a document within a larger collection (or corpus) by balancing two key intuition

TF (Term Frequency)

This measures how frequently a term appears in a specific document. The underlying idea is that repetition signals importance. For instance, if the search term "quantum" appears 5 times in Document A and only once in Document B, Document A is likely more relevant to a query about quantum physics. The basic formula is \[ \text{TF (t, d)} = \text{count of term t in document d} \] Variations exist, such as normalized TF to account for document lenght \[ \text{TF(t, d)} = \frac{ \text{count of t in d}}{ \text{total words in d}} \] this prevents longer documents from being unfairly favoured due to huge size.

IDF (Inverse Document Frequency)

Not all words are created equal, common ones like "the" or "and" appear everywhere and offer little discriminatory power. IDF downweights these by highlighting rarity. For example in a search for "The Matrix," the word "The" is universal and useless, while "Matrix" is rarer and thus more informative. The formula is
\[ \text{IDF(t)} = \log \frac{\text{Total number of documents in corpus}}{\text{Number of documents containing t}} \]

The logarithm smooths the scale and adding 1 to the denominator avoids division by zero ...
\[ \text{IDF(t)} = \log \frac{\text{Total number of documents in corpus + 1}}{\text{Number of documents containing t + 1}} \]

The final TF-IDF weight for a term in a document combines these \[ Weight(t, d) = TF(t, d) \times IDF(t) \] Higher weights indicate terms that are both frequent in the document and rare across the corpus, making them strong indicators of relevance.

Example usecase using a calculation

we have a corpus of 100 documents, and we're querying for "apple computer." The term "apple" appears in 10 documents (IDF = log(100/10) ≈ 1.0), while "computer" appears in 20 (IDF ≈ 0.7). In Document A: "apple" appears 3 times (TF=3), "computer" 2 times (TF=2). TF-IDF for "apple" = 3 × 1.0 = 3; for "computer" = 2 × 0.7 = 1.4. The document's score could be the sum or average of these, depending on the implementation.

Vector Space Model

TF-IDF weights form the foundation for representing text in a mathematical framework called the Vector Space Model (VSM). Here, each document and query is treated as a vector in a high-dimensional space, where each dimension corresponds to a unique term in the vocabulary.

Vector Representation : If the corpus vocabulary has 10,000 unique words, every document becomes a 10,000-dimensional vector. The value in each dimension is the TF-IDF weight for that term (or 0 if absent). For a query like "The Matrix," its vector would have non-zero weights only for relevant terms.
This sparse representation (mostly zeros) is efficient but can be computationally intensive for large vocabularies.
Similarity Measurement : To rank documents, we compare the query vector \( \vec{q} \) to each document vector \( \vec{d} \). The most common metric is Cosine Similarity, which measures the angle between vectors (ignoring magnitude to focus on direction/orientation)
\[ Cosine(\vec{q}, \vec{d}) = \frac{\vec{q} \cdot \vec{d}}{||\vec{q}|| \times ||\vec{d}||} \] Where \[ \vec{q} \cdot \vec{d} \] is the dot product, and \[ ||\vec{q}|| \] is the Euclidean norm. Scores range from -1 (opposite) to 1 (identical); higher values indicate closer semantic alignment. A smaller angle means better relevance.

Whats Next ??

We have covered how to find and rank text, but what happens when the data is too big to fit on one machine? In Part II, we will look at Distributed Search, exploring Sharding, Replication, and the consensus algorithms that keep the engine running when servers fail.

That's all from my side for the first part, I am working on part II and will be releasing it soon .... Hope I was able to add some value to your learning ^^

Redis 101 : From a Beginners POV

Mrinal — Invalid Date

Redis 101 : From a Beginners POV

2nd October, 2025

Whenever I have talked about redis in my projects people woud think it as a cache to use . But redis is more than that we can use redis as rate limiter, message broker and as a database ... But what is even redis, why is it even so fast and how are we even using it . Raising all this question made me curious about this topic and so I want you to be ...

Foundation

Lets first start with What is Cache so its simple caching is like keeping frequently used items on your desk instead of fetching them from a storage room. Caching stores frequently accessed data in a temporary, high-speed storage layer, reducing latency and improving performance by minimizing redundant computations or database queries. Now Redis is our high speed storage layer stands for remote dictionary server, its a single threaded, in memory data structure storage model .. Which means unlike databases like PostgreSQL, MySQL which stores data on slower mechanical or solid state drives, redis keeps all its data in RAM. This means every read and write operation happens at memory speed wihtout the worrying about disk input / output

Why Redis is this fast ??

There are three main pillers behind this speed, first being the In Memory Data Storage, this is the most significant factor as accessing data from RAM is orders of magnitude faster than from even the fastest SSDs or NVMe drives. Main memory access latency is typically in the nanosecond range, while disk access is in the microsecond to millisecond range. By keeping the entire dataset in RAM, redis eliminates biggest bottleneck in database systems which is disk I/O

Second reason being Single threaded command execution, redis processes all commands on a single thread. This design avoids the overhead of multithreading. There are no locks to acquire, no context switching between threads and no race conditions to manage. The CPU can focus purely on executing commands sequentially without interruption, which is incredibly efficient for the workload Redis is designed for (many small, fast operations).

Third reason being highly optimized C code and data structures, redis is written in ANSI C, a language known for its performance. Beyond the language, it uses custom, highly-tuned data structures. For example, its Simple Dynamic String (SDS) and the various encodings for Hashes and Sets (like ziplists) are designed to minimize memory usage and CPU cycles for common operations, ensuring that not only is the data in RAM, but it's stored in the most efficient way possible.

You might get a question that redis must handle thousand of concurrent client connections and execute commands with microsecond latency, what architectural mode allows it to manage this so effieciently??

The single threaded nature

The core of Redis's command processing is single threaded. This means it uses a single CPU core to process all incoming commands, parse them and execute them. This choice is intentional,as it eliminates the complexity and performance overhead of multithreading, such as lock contention, race condition and context switching

To handle concurrency, redis employes an event driven architecture using an I/O multiplexing mechanism. The main thread runs an event loop that uses system calls epoll, kqueue or IOCP to effieciently observe multiple network sockets

Lets take up a scene in which you are the only one who knows how to cook and chop veggies, but you can only chop one ingredient at a time(the single redis thread). But you have multiple assistants (your friends ofc) (the operating system's I/0 multiplexing features, like kqueue and IOCP). You told your friends to watch all these pots on the stove. The moment one is ready, they should inform you. All this to not waste your time standing and string at the pots. Instead you chop veggies, when one of your assistant shouts, "pot#3 is boiling !!" then you immediately stop what ever was being done, deal with that pot and then go back to chopping. So in this scenario you are the redis main event loop, pots are client connections and your friends are the operating system's kernel, which efficiently notifies Redis when a client has sent a request or is ready to receive a response.

So this is what the actual process looks like :

The event loop registers all client sockets with the multiplexing API.
The API notifies the Redis event loop only when a socket is ready for an I/O operation (e.g., a client has sent data, or a TCP buffer is ready to receive a response).
The single thread then processes the ready event: it reads the command from the socket, parses it, executes it, and writes the response back to the socket.

This non-blocking I/O model ensures the single thread is never idle waiting for network or disk operations. It is always busy processing events, which is how it achieves high throughput and concurrency with a single thread.

As a engineer you should get this question, that Redis's primary storage is volatile RAM. What mechanisms does it provide to ensure data persistence and durability, allowing it to recover from server restarts or crashes?

Lets talk about Persistance

Redis provides two distinct, complementary persistence mechanisms to save the in-memory dataset to non-volatile storage.

RDB (Redis Database): This persistence method creates point-in-time snapshots of the dataset. It works by forking a child process, as described previously. The child process writes the entire dataset to a single, compact, binary .rdb file on disk. This is efficient in terms of CPU and I/O. The main advantage is that the resulting file is perfect for backups and allows for fast data restoration on restart. The primary disadvantage is the potential for data loss: if the server crashes between two configured snapshots, all writes since the last snapshot are lost.
AOF (Append Only File): This method logs every write operation command that modifies the dataset. These commands are appended to an appendonly.aof file. Upon restart, Redis re-executes these commands in sequence to reconstruct the original dataset. Durability is controlled by the appendfsync configuration:
- always: Syncs after every write. Slowest but safest.
- everysec: Syncs once per second. The recommended default, providing a good balance of speed and safety (max 1 second of data loss).
- no: Lets the OS decide when to flush. Fastest but least safe.

To prevent the AOF file from growing indefinitely, Redis can automatically rewrite it in the background. It forks a child process that writes the minimal set of commands needed to recreate the current dataset into a new, temporary AOF file, which is then atomically swapped with the old one.

For maximum durability, it is common practice to use both AOF for near-real-time persistence and RDB for periodic backups.

Lets take a some good use cases of redis in production grade application

First which is commonly known and used by every developers and engineers out there, Redis as cache layer.

Lets say you have a web application where users frequently view their profiles fetching this data from a disk based database like MySQL everytime can be slow instead we can use redis to cache the user profile data so when a user requests their profile the application first checks redis, if the desired data is in redis it's a cache hit it is returned immediately, if the data is not in redis it's a cache miss the cache miss the application fetches it from the primary database stores it in redis and then returns it to the user. The data in redis can have TTL or Time To Live so it can automatically expire after a certain time for example say 15 to 20 minutes to ensure fresh is there all the time.

Second scenario is using Redis as Database specially for use cases where speed and low latency are very much important, just like building a gaming application.

Here we need to maintain a realtime leaderboard where player scores are constantly updated and we need to display the top 10 players instantly. So here we can use redis as sorted set data structure to store player scores, each player score is added to the sorted set with their ID as the key and the score as the value this automatically sorts the scores so we can quickly retrieve the top 10 players using a single command like ZREVRANGE leaderboard 0 9. Redis can then process this data to disk using RDB or AOF to ensure durability.

What internal data structures and optimizations allow it to store complex data types with minimal overhead?

Memory Management

Redis's memory efficiency stems from its use of custom, highly-optimized data structures and dynamic encoding strategies.

Redis does not use standard C-style null-terminated strings. Instead, it uses its own SDS structure. An SDS (Simple Dynamic String) is a struct that contains metadata (like the length of the string and the total allocated memory) followed by a byte array holding the actual data. This design provides several advantages which are

O(1) Length Lookup: The length is stored directly in the struct, avoiding the need to scan the entire string.
When an SDS is grown, it allocates more memory than immediately required (e.g., 1MB of free space for a 1MB string), so subsequent appends may not require a new reallocation and memory copy.

Redis dynamically switches internal encodings for a data type based on the data's size and content to save memory. For example

A Hash with few, small elements might be encoded as a ziplist (or listpack in newer versions), which stores all elements in a single, contiguous block of memory with no pointers, drastically reducing overhead. As the hash grows, Redis automatically converts it to a full hashtable for better performance on large datasets.
A Set containing only integers may be encoded as an intset, a specialized data structure that stores integers in a sorted array without any overhead.
Small Sorted Sets can also be encoded as a ziplist.

That's all from my side for the very first part of deep diving into redis, we got more parts for redis to explore for next few blogs :) Hope I was able to add few value to your today's learning :)

Distributed Systems 101 : From a Beginners POV

Mrinal — Invalid Date

Distributed Systems 101 : From a Beginners POV

8th August, 2025

Distributed Systems is one best topics which I encounter on daily basis. A collection of computers or nodes which are independent have to work together to perform a task, isn't this alone so much interesting to know how does it all work behind the scene ??

The Foundation

For the very simple start, distributed system is a collection of independent computers or we also call it nodes, that appear to users as a single coherent (as one) system. These computers communicate over a network to coordinate their actions and share resources.

But the fundamental challenge is making multiple independent computers work together seamlessly while dealing with network delays, failures and inconsistency

Cool isn't it, but what happens when these independent computers can't agree on something ?? What happens then ??

Why distributed systems can't be perfect ?

When independent computers in a distributed system can't agree, it creates a conflict that must be resolved to main system reliability. This challenge is addressed by the CAP theorem, which states that a distributed system can only guarantee two out of three properties which is Consistency this ensure all nodes have the same data at the same time, Availability ensures every request receives a response, and Partition Tolerance ensures the system continues to operate despite network failures. Now according to this theorem we need to have 2/3 ratio and sacrifice one :(

Here comes another one, network partition (P) will happen in any real distributed system. Internet get cut, routers fail, data centers lose connectivity. So we must choose between C and A

Consistency focused systems (CP), like banking databases, ensures all nodes have the same accurate data, such as correct account balances, even if it means temporarily halting operations during a failure (that means sacrificing A of CAP). For example, MongoDB stops accepting updates during network issues to maintain data accuracy

Whereas, Availability focused systems like DNS or Amazon's shopping cart, keep operating despite failure, even if it risks delivering slightly outdated information (that means sacrificing C of CAP). For example an old IP address or an inconsistent cart count

Everything is cool, but if we have to choose between consistency and availability, how do we actually make that choice in practice?

The Spectrum of "Good Enough" | Consistency Models

The answer lies in selecting the right consistency model a set of rules defining how “consistent” the system’s data needs to be. Different applications have different needs. Strong Consistency ensures that every read retrieves the latest write, providing a unified view of data across all nodes. This is serious for systems like banking databases, where showing an outdated account balance could cause serious issues. Traditional databases like PostgreSQL often use this model, but it comes at a cost: slower response times and reduced availability during network issues, as the system waits to ensure all nodes agree.
Eventual Consistency prioritizes availability, allowing temporary differences in data across nodes, with the promise that updates will sync over time. For example, in Amazon’s DynamoDB or email systems, a sent message might take a moment to appear everywhere, but the system stays operational. This model suits applications where slight delays are acceptable, offering high availability and the ability to scale easily.
Casual Consistency ensures that events with a cause-and-effect relationship are seen in the correct order. Like on social media platforms, everyone sees a reply after its original post, but unrelated posts might appear in different orders for different users. This strikes a balance between strict consistency and flexibility, maintaining logical order for related actions without requiring instant global agreement.
Session Consistency ensures that within a single user session, a user sees their own changes immediately. For example, when we upload a photo to a platform like Facebook, we see it right away, even if it takes a moment to appear for others. This model enhances user experience by prioritizing personal consistency while allowing slight delays for others.

Why "Eventual Consistency" wins ??

Most successful companies, especially those operating at massive scale, lean toward eventual consistency. Why? Users rarely notice brief delays in data syncing, and the high availability and scalability it offers outweigh the need for instant consistency in many cases. Systems like Amazon’s shopping cart or WhatsApp prioritize staying online and responsive, even if it means occasional, minor inconsistencies. By carefully choosing a consistency model that aligns with their priorities, companies ensure their distributed systems are both reliable and efficient, meeting user needs without overcomplicating the infrastructure.

This makes sense, but how do we actually implement these consistency guarantees ?? What happens under the hood when we're trying to keep data synchronized across multiple machines?

Getting Computers to Agree | Consensus Algorithms

Here consensus algorithms work in, they are the mechanisms that allow nodes to agree on shared state, even when some are unreliable. Consensus algorithms ensure everyone ends up on the same page

The challenge, often called the Byzantine Generals Problem, tells the core issue: a group of generals (nodes) must agree to attack or retreat together, but some messages might get lost, and some generals could even act maliciously. In distributed systems, nodes face similar obstacles—network delays, crashes, or even intentional sabotage and still need to reach a unified decision.

One widely used solution is the Raft algorithm, which simplifies consensus by electing a leader. The process works in three steps: nodes vote to select a leader, the leader handles all client requests and replicates them to follower nodes, and changes are finalized only when a majority of nodes confirm they’ve received them. For example etcd, a key-value store used by Kubernetes, relies on Raft to maintain consistent cluster state across nodes, ensuring reliable coordination even if some nodes fail.

Another approach is the Paxos algorithm, favored in academic settings and used by systems like Google’s Chubby lock service. Paxos is robust, handling complex failure scenarios, but it’s harder to implement due to its complexity.
here malicious nodes are a concern, like in blockchain, the Practical Byzantine Fault Tolerance (PBFT) algorithm steps in. PBFT ensures agreement even when some nodes behave dishonestly, though it’s slower and more resource-intensive.

Few Notes on trade offs we are making while using these

Raft is fast and straightforward but assumes nodes fail innocently. PBFT handles malicious nodes but sacrifices speed. Proof of Work offers high security at the cost of efficiency.

Okay, so we can get computers to agree on things, but what about the actual data ?? How do we store and retrieve information across multiple machines efficiently ??

Data Partitioning and Sharding

I have written an overview of data partitioning in this blog System Design 101 you can check this out too.

To handle massive datasets in distributed systems, data partitioning or sharding splits information across multiple machines, enabling scalability and faster queries. Range Based Partitioning divides data into segments based on a key’s value range, such as sorting user records by surname. For example, one node might store surnames A–F, another G–M, and a third N–Z. This approach shines for range queries, like finding all users with surnames starting with “C,” as the system knows exactly which node to check. However, it can lead to uneven data distribution if some ranges are more populated like having many “Singh”s in one partition causing bottlenecks.

Hash-Based Partitioning uses a hash function to evenly distribute data across nodes. Like, a user ID might be hashed and assigned to one of several partitions, ensuring a balanced spread. If user ID 12345 hashes to partition 1 and 67890 to partition 3, the load stays roughly equal across nodes. This method excels for scalability and uniform data distribution, making it ideal for systems like Apache Cassandra.

The downside? Range queries become slower, as the system may need to check all partitions, since hashed values don’t preserve order.

Directory Based Partitioning relies on a lookup service to track where each piece of data is stored. Instead of calculating a partition based on the data itself, the system queries a directory to find the right node. Amazon’s DynamoDB uses this approach to route data efficiently using partition keys. This method offers flexibility, as it can adapt to complex data placement needs, but the lookup service must be fast and reliable to avoid becoming a performance bottleneck.

All these are cool for storing data, but how do we ensure our data doesn't disappear when machines fail ??

Replication

It plays as a major role, replication is technique that create multiple copies of data across different nodes to ensure fault tolerance. Like keeping copies of vital documents in a safe deposit box and the cloud, replication ensures your data remains accessible and secure even if a machine goes offline.

There are types of replications too (I am way too cooked while writing this)

Master-Slave (Primary - Replica) Replication
In this model, one primary server handles all write operations, while multiple replica servers handle read requests. The primary server sends updates to the replicas, which store copies of the data. For example, MySQL’s master-slave setup uses this approach. A client writes to the primary, and the changes are copied to replicas, from which clients can read. This setup is straightforward, ensures consistent writes through a single source of truth, and scales well for read-heavy workloads, but if the primary server fails, writes are disrupted until a new primary is chosen. Additionally, replication lag can lead to slightly outdated data on replicas

Master - Master (Multi Primary) Replication
Here, multiple servers can handle both reads and writes, synchronizing changes between them. Systems like CouchDB or MySQL’s master-master configuration use this model, allowing clients to interact with any primary node. This is useful for geographically distributed systems, where users in different regions can write to nearby servers. This eliminates a single point of failure for writes and improves scalability for both reads and writes but synchronizing writes across multiple primaries can lead to conflicts, requiring complex resolution mechanisms, and managing the system is more challenging.

Peer to Peer Replication
In peer-to-peer replication, all nodes are equal, capable of handling both read and write requests, with data copied to multiple nodes. Systems like Apache Cassandra and Amazon DynamoDB use this approach, often relying on consensus algorithms to maintain consistency. Any node can serve client requests, and data is replicated to a set number of nodes for redundancy.

Small Note : MySQL’s master-slave setup is ideal for read-heavy applications, while Cassandra’s peer-to-peer model suits systems needing high availability across regions

replication protects our data, but what about when users are scattered across the globe ?? How do we serve them efficiently from the closes location ??

Content Delivery Network (CDNs)

CDNs comes in clutch to deliver content from the closest possible location, slashing latency and performance. Like you can imagine the frustration of waiting for a webpage to load, CDNs solves this by bringing data closer to you.

The problem starts with physics: data travels through fiber optic cables at about 200,000 km/second, which sounds fast but isn’t enough for today’s expectations. For instance, a round trip from New York to Sydney (~15,000 km) takes ~75ms just for light to travel, and with routing, processing, and queuing, you’re looking at 200–300ms of delay. Yet, users demand web pages to load in under 100ms. CDNs resolve this by acting like local coffee shops scattered worldwide, serving content quickly instead of relying on one distant central hub.

CDNs work by deploying edge servers, or Points of Presence (PoPs), in strategic locations: major cities like New York and Tokyo (Tier 1), regional hubs like Austin or Osaka (Tier 2), and even smaller cities for popular content (Tier 3). When a user requests content, like a video or webpage, the request goes to the nearest edge server. If the content is cached there, it’s served instantly. If not, the edge server fetches it from the origin server, caches it locally, and delivers it to the user, minimizing future delays.

CDNs works well with static content, like images, CSS, JavaScript files, videos, or software downloads, which can be cached for hours, days, or weeks since they rarely change. Dynamic content, like personalized web pages or real-time API responses, is trickier. Solutions like Edge-Side Includes (ESI) cache page templates while inserting dynamic parts, or caching different versions for user segments, help balance speed and accuracy.

Netflix serves 95% of its traffic through its custom CDN, Open Connect, with appliances in ISP data centers. Popular shows are pre-positioned worldwide based on predictive algorithms, ensuring fast streaming with minimal buffering. YouTube delivers billions of hours of video daily, caching popular videos at edge servers and adjusting quality based on your connection. Steam uses CDNs to distribute massive game downloads, saturating your connection while reducing strain on central servers.

There are challenges here too, one is known as Cache Invalidation updating cached content when the origin changes—is notoriously tough. Strategies like Time To Live (TTL) for automatic expiration, manual purging, or URL versioning help. Cache coherence is another different edge servers might hold different versions of content. Eventual consistency or regional cache hierarchies can address this.

All this from my side on Distributed System 101 : Part 1, for the part 2 I have some interesting topics to cover and some use cases to share which I learned during my internships. Hope I was able to make you learn something new today .. HAVE A GREAT DAY AHEAD :)

Sockets 101 : From a Beginners POV

Mrinal — Invalid Date

Sockets 101 : From a Beginners POV

26th July, 2025

When your web browser fetches this blog post, when your messaging app sends a text, or when you stream a video, there's a fundamental mechanism at work, we call it SOCKETS

Sockets are the endpoints of communication channels that allow processes to exchange data, whether they're on the same machine or across the globe. At its core, a socket is an abstraction provided by the operating system that represents one endpoint of a bidirectional communication link. The socket API, originally developed for Unix systems, has become the standard interface for network programming across virtually.

Socket operate at different layers of the network stack. TCP sockets provide reliable, ordered data delivery with error detection and correction. UDP sockets offer faster, connection less communication without delivery guarantees

The socket abstraction hides the complexity of network protocols, hardware interface and routing decisions. When you create a socket, the operating systems allocates kernel data structures, assigns network resources, and manages the connection lifecycle. This abstraction enables developers to focus on application logic rather than low-level network details.

But how do processes on the same machine communicate without going through the network stack at all ??

The Silent Communication Channel

An anonymous pipe is a unidirectional communication channel that exists only in memory. Unlike named pipes (FIFOs), anonymous pipes have no filesystem representation and can only be shared between related processes, typically a parent and its child processes

The kernel implements anonymous pipes using a circular buffer, typically 64KB on Linux systems. This buffer acts as a temporary storage area between the writing and reading processes. When the buffer fills up, writers are blocked until readers consume data, providing natural flow control.

Anonymous Pipes working in C

#include <"stdio.h">
#include <"unistd.h">
#include <"stdio.h">

int main() {
    int pipefd[2];
    pid_t pid;
    
    // creating a pipe
    if (pipe(pipefd) == -1) {
        perror("pipe");
        return 1;
    }
    
    pid = fork();
    if (pid == 0) {
        // child process - writer
        close(pipefd[0]); // Close read end
        write(pipefd[1], "Hello from child", 16);
        close(pipefd[1]);
    } else {
        //parent process - reader
        char buffer[20];
        close(pipefd[1]); // Close write end
        read(pipefd[0], buffer, 16);
        printf("Received: %s\n", buffer);
        close(pipefd[0]);
    }
    
    return 0;
}

The pipe() system call creates two file descriptors: pipefd[0] for reading and pipefd[1] for writing. The kernel maintains a circular buffer (typically 64KB on Linux) between these endpoints. When the buffer fills up, writers block until readers consume data.

The creation of anonymous pipes involves the operating system allocating two file descriptors: one for reading and one for writing. These descriptors can be inherited by child processes through fork(), enabling parent-child communication. The pipe exists as long as at least one process holds either descriptor open.

Unlike network sockets, pipes operate entirely within kernel memory, making them extremely fast for local communication. There's no network protocol overhead, no packet serialization, and no routing decisions just direct memory-to-memory data transfer managed by the kernel.

But what exactly are these file descriptors that pipes return, and how does the operating system manage them?

File Descriptors

File descriptors are the answer to our previous question about how the OS manages communication endpoints. A file descriptor (fd) is a non-negative integer that serves as an abstract handle for accessing files, sockets, pipes, devices, and other I/O resources in Unix-like systems.

The operating system maintains a file descriptor table for each process, mapping fd numbers to kernel data structures that contain the actual details about the resource. This indirection allows the kernel to manage resources centrally while providing processes with simple integer handles.

File Descriptors in C

#include <"sys/socket.h">
#include <"netinet/in.h">
#include <"unistd.h">

int main() {
    // Creating different types of file descriptors
    
    // 1. Socket file descriptor
    int sockfd = socket(AF_INET, SOCK_STREAM, 0);
    printf("Socket fd: %d\n", sockfd);
    
    // 2. File descriptor for regular file
    int filefd = open("/tmp/test.txt", O_CREAT | O_RDWR, 0644);
    printf("File fd: %d\n", filefd);
    
    // 3. Pipe file descriptors
    int pipefd[2];
    pipe(pipefd);
    printf("Pipe read fd: %d, write fd: %d\n", pipefd[0], pipefd[1]);
    
    // All can be used with same I/O operations
    char buffer[100];
    read(sockfd, buffer, 100);    // Read from socket
    read(filefd, buffer, 100);    // Read from file
    read(pipefd[0], buffer, 100); // Read from pipe
    
    close(sockfd);
    close(filefd);
    close(pipefd[0]);
    close(pipefd[1]);
    
    return 0;
}

Whether we are dealing with network socket, a regular file, or a pipe, you use the same system calls : read(), write(), close(), and others. This abstraction is what makes Unix-like systems so powerful for system programming.

File descriptors are process-specific resources. When a process forks, the child inherits copies of the parent's file descriptors, but subsequent operations on these descriptors in either process don't affect the other. However, both processes share the same underlying kernel file description, so operations like changing file position affect both processes.

The kernel enforces limits on file descriptors to prevent resource exhaustion. Each process has both soft and hard limits on the maximum number of open file descriptors. These limits can typically be viewed and modified using system utilities, and they're crucial for server applications that handle many concurrent connections.

But how do we efficiently monitor multiple file descriptors for activity without constantly polling them?

Managing Multiple Connections

I/O multiplexing solves the challenge of monitoring multiple file descriptors simultaneously. Instead of creating separate threads for each connection or constantly polling each descriptor, multiplexing allows a single thread to wait for activity on multiple file descriptors at once.

The fundamental problem that I/O multiplexing addresses is the blocking nature of I/O operations. When a process calls read() on a socket with no available data, the process blocks until data arrives. For a server handling multiple clients, this means either dedicating one thread per connection or missing data from other connections.

I/O multiplexing enables a single process to efficiently handle multiple input/output sources, such as sockets, without blocking on each one individually. The application process communicates with an I/O multiplexer (e.g., select, poll, or epoll), requesting it to monitor a set of file descriptors (FDs) in this case, three socket FDs. The multiplexer continuously checks the status of these FDs and blocks the process until one or more of them become "ready" (e.g., data is available to read). When an event occurs on a monitored FD (like FD 1 or FD 3 becoming readable), the multiplexer returns control to the process with information about which FDs are ready.

The process can then perform non-blocking I/O only on those specific descriptors. This mechanism allows efficient use of system resources by avoiding the need to spawn multiple threads or processes for each I/O source.

epoll() in C

#include <"sys/epoll.h">

int epoll_fd = epoll_create1(0);
struct epoll_event event, events[MAX_EVENTS];

// Add socket to epoll
event.events = EPOLLIN;
event.data.fd = socket_fd;
epoll_ctl(epoll_fd, EPOLL_CTL_ADD, socket_fd, &event);

// Wait for events
int num_events = epoll_wait(epoll_fd, events, MAX_EVENTS, -1);

I/O multiplexing enables servers to handle thousands of concurrent connections with a single thread, but what about connections that are meant to be temporary and don't need to persist?

The Temporary Connection Endpoints

Ephemeral ports provide the answer to temporary connections. When a client application creates an outbound connection, it doesn't typically specify a source port. Instead, the operating system automatically assigns an ephemeral (temporary) port from a predefined range.

The ephemeral port range varies by operating system. Linux typically uses ports 32768-60999, while Windows uses 1024-65535. These ranges are configurable and represent a balance between providing enough ports for concurrent connections while reserving lower-numbered ports for well-known services.

How ephermal ports work in practice

#include <"sys/socket.h">
#include <"netinet/in.h">
#include <"arpa/inet.h">

int main() {
    int sockfd = socket(AF_INET, SOCK_STREAM, 0);
    struct sockaddr_in server_addr, local_addr;
    socklen_t addr_len = sizeof(local_addr);
    
    // Connect to server (OS assigns ephemeral port automatically)
    server_addr.sin_family = AF_INET;
    server_addr.sin_port = htons(80);
    inet_pton(AF_INET, "93.184.216.34", &server_addr.sin_addr); // example.com
    
    connect(sockfd, (struct sockaddr*)&server_addr, sizeof(server_addr));
    
    // Check what ephemeral port was assigned
    getsockname(sockfd, (struct sockaddr*)&local_addr, &addr_len);
    printf("Local port assigned: %d\n", ntohs(local_addr.sin_port));
    
    close(sockfd);
    return 0;
}

Ephemeral port allocation strategies differ across operating systems. Some use sequential allocation, starting from the lowest available port in the range. Others use random or hash-based algorithms to distribute ports more evenly across the range. The choice affects performance, security, and the ability to handle high connection rates.

The lifecycle of an ephemeral port begins when a client initiates an outbound connection. The operating system selects an available port, binds it to the socket, and uses it as the source port for the connection. When the connection closes, the port enters a TIME_WAIT state before becoming available for reuse.

TCP (Transmission Control Protocol) state machine, which outlines the various states a TCP connection transitions through during its lifecycle.

TIME_WAIT is a crucial TCP state that prevents delayed packets from a closed connection from interfering with new connections using the same port pair. The typical TIME_WAIT duration is twice the Maximum Segment Lifetime (MSL), often 60-120 seconds. This can become a limiting factor for applications making many short-lived connections.

Port exhaustion occurs when all ephemeral ports are in use or in TIME_WAIT state. This is a common problem for high-traffic proxy servers or applications making many outbound connections. Solutions include using multiple IP addresses, tuning TIME_WAIT parameters, or implementing connection pooling.

Raw Sockets and custom protocols

What about scenarios where we need to implement custom protocols or handle raw network data?

Raw sockets provide direct access to network protocols below the transport layer, allowing applications to craft custom packets or implement protocols not directly supported by the operating system.

Operating systems typically provide TCP and UDP socket abstractions that handle most application needs. However, some applications require lower-level access to implement custom protocols, perform network analysis, or bypass standard protocol limitations.

Implementing raw sockets

#include <"sys/socket.h">
#include <"netinet/ip.h">
#include <"netinet/tcp.h">
#include <"arpa/inet.h">

// Creating a raw socket (requires root privileges)
int create_raw_socket() {
    int sockfd = socket(AF_INET, SOCK_RAW, IPPROTO_TCP);
    if (sockfd < 0) {
        perror("raw socket creation failed");
        return -1;
    }
    
    // Tell kernel not to add IP header (we'll craft it ourselves)
    int one = 1;
    if (setsockopt(sockfd, IPPROTO_IP, IP_HDRINCL, &one, sizeof(one)) < 0) {
        perror("setsockopt IP_HDRINCL failed");
        return -1;
    }
    
    return sockfd;
}

// Craft a custom TCP packet
void craft_tcp_packet(char *packet, const char *src_ip, const char *dst_ip, 
                      uint16_t src_port, uint16_t dst_port) {
    struct iphdr *ip_header = (struct iphdr *)packet;
    struct tcphdr *tcp_header = (struct tcphdr *)(packet + sizeof(struct iphdr));
    
    // Fill IP header
    ip_header->version = 4;
    ip_header->ihl = 5;
    ip_header->tos = 0;
    ip_header->tot_len = htons(sizeof(struct iphdr) + sizeof(struct tcphdr));
    ip_header->id = htons(12345);
    ip_header->frag_off = 0;
    ip_header->ttl = 64;
    ip_header->protocol = IPPROTO_TCP;
    ip_header->check = 0; // Kernel will calculate
    inet_pton(AF_INET, src_ip, &ip_header->saddr);
    inet_pton(AF_INET, dst_ip, &ip_header->daddr);
    
    // Fill TCP header
    tcp_header->source = htons(src_port);
    tcp_header->dest = htons(dst_port);
    tcp_header->seq = htonl(1000);
    tcp_header->ack_seq = 0;
    tcp_header->doff = 5;
    tcp_header->syn = 1; // SYN flag
    tcp_header->window = htons(65535);
    tcp_header->check = 0; // Calculate separately
    tcp_header->urg_ptr = 0;
}

Raw sockets operate at the IP level or even lower, depending on the socket type and options. Applications using raw sockets must manually construct protocol headers and handle details normally managed by the operating system, such as checksums, fragmentation, and addressing.

Notes on Performance and Optimization

Buffer management significantly impacts socket performance. The bandwidth-delay product determines optimal buffer sizes - the product of network bandwidth and round-trip time indicates how much data should be "in flight" for maximum throughput. Undersized buffers limit throughput, while oversized buffers waste memory.

Connection reuse and pooling strategies reduce the overhead of connection establishment and teardown. HTTP/1.1 introduced persistent connections to avoid repeated TCP handshakes. HTTP/2 multiplexes multiple streams over single connections. Connection pools maintain ready-to-use connections to frequently accessed servers.

Connection reusing and pooling

typedef struct {
    int *sockets;
    int count;
    int capacity;
    pthread_mutex_t mutex;
} connection_pool_t;

int get_connection(connection_pool_t *pool, const char *host, int port) {
    pthread_mutex_lock(&pool->mutex);
    
    if (pool->count > 0) {
        // Reuse existing connection
        int sockfd = pool->sockets[--pool->count];
        pthread_mutex_unlock(&pool->mutex);
        return sockfd;
    }
    
    pthread_mutex_unlock(&pool->mutex);
    
    // Create new connection
    return create_connection(host, port);
}

void return_connection(connection_pool_t *pool, int sockfd) {
    pthread_mutex_lock(&pool->mutex);
    
    if (pool->count < pool->capacity) {
        pool->sockets[pool->count++] = sockfd;
    } else {
        close(sockfd); // Pool full, close connection
    }
    
    pthread_mutex_unlock(&pool->mutex);
}

Memory mapping can improve performance for applications that repeatedly access the same data. By mapping files into memory, applications can avoid system call overhead and benefit from the operating system's virtual memory management.

Zero-copy operations eliminate unnecessary data copying between user and kernel space. Techniques like sendfile() allow the kernel to transfer data directly from files to sockets without involving user-space buffers. This approach significantly improves performance for file serving applications.

Zero Copy operations

        #include 
          
          // Use sendfile() for efficient file transfers
          ssize_t send_file_efficient(int out_fd, int in_fd, off_t offset, size_t count) {
            return sendfile(out_fd, in_fd, &offset, count);
          }
          
          // Use splice() for pipe-to-socket transfers (Linux)
          ssize_t splice_data(int fd_in, int fd_out, size_t len) {
            int pipefd[2];
            pipe(pipefd);
            
            // Move data from input to pipe
            ssize_t bytes_in = splice(fd_in, NULL, pipefd[1], NULL, len, SPLICE_F_MOVE);
            
            // Move data from pipe to output
            ssize_t bytes_out = splice(pipefd[0], NULL, fd_out, NULL, bytes_in, SPLICE_F_MOVE);
            
            close(pipefd[0]);
            close(pipefd[1]);
            
            return bytes_out;
          }

Network programming is ultimately about enabling communication between processes, whether they're on the same machine or across the globe. Hope I was able to add value to your today's learning :)

Vector Database 101 : From a Beginners POV

Mrinal — Invalid Date

Vector Database from a Beginners POV

3rd July, 2025

Vector databases have been generating a lot of excitement lately, with companies raising hundreds of millions of dollars to develop them. Some even call them the new era of AI databases because they’re designed to handle complex data, like embeddings used in AI applications. They’re incredibly powerful and enable some amazing use cases, such as real-time recommendation systems or advanced search features. However, for many projects, using a vector database might be overkill, as simpler solutions could work just fine.

About 80% of the data we encounter today is unstructured, meaning it doesn’t neatly fit into the rows and columns of traditional relational databases. This includes things like social media posts, images, videos, audio files, and even emails or text documents. Unlike structured data, such as numbers or predefined categories, unstructured data is messy and complex, making it hard to maintain and query using conventional databases. Lets take an example of a image if we want to put this into relational database in order to search for similar

What ends up up happening is that often we manually assign keywords or tags to it because from the pixel values alone we cannot search for similar images and the same hodls true for unstructured text blobs or audio and video data.

So to ease this up here comes vector embeddings or vector databases

Vector databases solve this problem by understanding that "maroon," "orange," and "black" are mathematically similar, even though they're different words. They store information as numbers (vectors) and use math to find similar items instead of looking for exact matches.

This way it helps how we build smart applications, from search engines that understand what we really mean to, recommendation systems that knows our preferences better than we do. But how exactly do it turn words, images, and other data into numbers that computers can compare mathematically?

Converting Data into Numbers

It uses clever algorithms to so called the vector embeddings this is done using a Machine Learning Model, a vector embedding is simply a list of numbers, like [0.2, 0.8, 0.1, 0.9]. We can take it as coordinates that describe where something sits in a mathematical space.

Taking colors as example like, each position in our color vector represents [first number (how much red 0.0 = minimum red, 1.0 = maximum red), second number(how much green), third number (how much blue)] we call rgb color code so for Red it becomes [1.0, 0.0, 0.0] for Blue is becomes [0.0, 0.0, 0.1] for green it becomes [0.0, 1.0, 0.0] and for purple it becomes [0.5, 0.0, 0.5]. Now if we want to find colors similar to purple, we can use math to calculate which other colors are closest. Purple [0.5, 0.0, 0.5] is mathematically closer to red than to green. How ?? in purple if we look into closely [0.5 (50% is red), 0.0 (0% green), 0.5 (50% blue)]

For text, the process is more complex but follows the same principle. We use machine learning models to convert words into vectors of hundreds or thousands of numbers. These numbers capture the meaning and relationships between words. For example: "Sedan" might become [0.2, 0.8, 0.1, 0.9, 0.3, ...], "SUV" might become [0.3, 0.7, 0.2, 0.8, 0.4, ...], "Chocolates" might become [0.9, 0.1, 0.8, 0.2, 0.1, ...]. Notice how "SEDAN" and "SUV" have similar numbers, while "Chocolates" has very different numbers. This mathematical similarity reflects their real-world relationship.
But once we have these vectors, how do we actually calculate which ones are similar to each other?

How Computers Find "Close" Vectors

When we have vectors, we need mathematical formulas to measure how similar they are. The most common methods are cosine similarityand euclidean distance (I have only tried these twoo T_T )

Cosine Similarity measures the angle between two vectors. Two vectors pointing in the same direction have a cosine similarity of 1.0, while vectors pointing in opposite directions have a similarity of -1.0. The formula is \(\text{cosine_similarity} = \frac{\mathbf{A} \cdot \mathbf{B}}{|\mathbf{A}| \times |\mathbf{B}|}\)

Let's calculate this for two simple vectors:

Vector A = \([1, 2, 3]\)
Vector B = \([2, 4, 6]\)

First, we calculate the dot product (A · B): \(A · B = (1×2) + (2×4) + (3×6) = 2 + 8 + 18 = 28\)

Next, we calculate the magnitudes:

\(|A| = √(1² + 2² + 3²) = √(1 + 4 + 9) = √14 ≈ 3.74\)
\(|B| = √(2² + 4² + 6²) = √(4 + 16 + 36) = √56 ≈ 7.48\)

Finally: cosine_similarity = \(28 / (3.74 × 7.48) ≈ 1.0\)

This result of 1.0 makes sense because vector B is exactly twice vector A, so they point in the same direction.

Euclidean distance is a fundamental metric used in vector databases to measure the "straight-line" distance between two points (or vectors) in a multi-dimensional space. It is derived from the Pythagorean theorem and is particularly useful for quantifying the similarity or dissimilarity between data points represented as vectors, such as embeddings for text, images, or other data types in a vector database. \[\text{distance} = \sqrt{(A_1 - B_1)^2 + (A_2 - B_2)^2 + \cdots + (A_n - B_n)^2}\]

In vector databases, Euclidean distance is used to find nearest neighbors or cluster similar items. Like, when searching for similar documents or images, the database compares the Euclidean distance between their vector representations (embeddings). Smaller distances indicate greater similarity.

Time to face a canon event question : How do we organize millions of vectors so we can find similar ones quickly ??
here comes

\(\text{distance} = \sqrt{\sum_{i=1}^{n} (A_i - B_i)^2}\)

Vector Indexing

Vector databases faces challenges while storing millions of vectors, they need an system to find similar vector quickly.

This is where vector indexing comes in. An index is like a sophisticate filing system that organizes vectors based on thier similarity, allowing the database to skip most vectors during a search. Its similar to what database indexing we have discussed during System Design 101

where indexes (e.g., B-trees or hash tables) optimize retrieval by organizing data for efficient access. In vector databases, specialized indexing techniques like Approximate Nearest Neighbor (ANN) algorithms, hierarchical navigable small world (HNSW) graphs, or product quantization are often used to balance speed, accuracy, and memory usage, making sure that our database is scalable and performant similarity searches even with massive datasets.

Now that we understand the math, how do these calculations help us build useful applications?

Where Vector Math Solves Problems

Search Engines are one of the best examples when we search for "how to fix a broken faucet," the search engine converts your query into a high-dimensional vector using techniques like word embeddings or transformer models. It then compares this query vector to vectors representing web pages, finding those with similar semantic content, even if they use different phrasing, such as "repair leaky tap" or "plumbing maintenance." By leveraging vector similarity, search engines deliver relevant results that align with the user's intent, regardless of exact keyword matches.

Instagram converts photos into vectors that describe colors, shapes, objects, and even abstract features like artistic style. These vectors enable the platform to recommend visually similar photos, detect duplicate uploads, or identify content that violates community guidelines. Similarly, video platforms use vector representations to analyze scenes or frames, enabling features like content-based video recommendations or automated highlight detection.

The math remains the same in all these cases, we're calculating similarity between vectors using the formulas we learned earlier. The difference is in how we create the vectors and what we do with the similarity results.

This is all from myside on Vector Database. Hope I was able to add few value to your today's learning :)

Graphs 101 : From a Beginners POV

Mrinal — Invalid Date

Graph : From a Beginners POV

1st July, 2025

So a graph data structure is like a map of connections, like a bunch of dots that represent stuffs like people, cities or even web pages. Then you've got lines which connects these dots, showing some kind off relationships, like who's friends with who or which cities have direct roads between them.

Unlike linear data structures like arrays or linked lists, graphs represent relationships between entities in way that mirrors how connections are formed. At its core, graph is simply collection of nodes connected by edges. Its like a network where each point represents an entity, and the lines between them represent relationships or connections

Covering the fundamentals

Graphs are simple and flexible, every graph consists of just two fundamental components which are vertices and edges. Vertices are the individual data point or nodes that store information, while edges are the connections that define relationships between these vertices.

Taking an example like LinkedIN. Yeahh LinkedIN XDD Each user would be represented as a vertex, containing information like name, age and location. The friendship/connection between users would be represented as edges connecting these vertices. This simple model can represent millions of users and their complex web of relationships

Edges can carry additional information too. In a weighted graph, each edge has numerical value associated with it. For instance we in a road network, vertices might represent cities, and edges might represent roads with weights indicating the distance or travel time between cities. This additional information transforms a simple connection into a rich data relationship.

Now that we understand the basic building blocks, how do we actually store and organize this information in computer memory?

Graph Representation and Memory

When it comes to storing graphs in computer memory, we have two primary approaches: adjacency matrices and adjacency lists. Each method has its own strengths and is suited for different scenarios, depending on whether the graph is directed or undirected. In a directed graph, edges have a direction, meaning the relationship from vertex A to vertex B is not necessarily reciprocal. In an undirected graph, edges are bidirectional, so an edge between A and B implies a mutual connection..

Adjacency matrices use a 2D array where entry (i,j) indicates whether there's an edge between vertex i and vertex j. For a graph with n vertices, this creates an n×n matrix. In an undirected graph, the matrix is symmetric because an edge from i to j implies an edge from j to i, whereas in a directed graph, the matrix may be asymmetric since edges are one-way. While this approach uses more memory (O(n²) space), it provides constant-time lookup (O(1)) to check if two vertices are connected, making it ideal for dense graphs or when frequent edge queries are needed.

class AdjacencyMatrix {
  constructor(n) {
    this.numVertices = n;
    // Initialize a 2D matrix with false (no edges initially)
    this.matrix = new Array(n);
    for (let i = 0; i < n; i++) {
        this.matrix[i] = new Array(n).fill(false);
    }
}

    // Add an undirected edge between u and v
    addEdge(u, v) {
      this.matrix[u][v] = true;
      this.matrix[v][u] = true; // For undirected graph
    }

    // Check if there is an edge between u and v
    hasEdge(u, v) {
      return this.matrix[u][v];
    }
}

Lets talk about some memory here, For n vertices, adjacency matrices require exactly n² memory locations, regardless of the actual number of edges. With boolean values, this means n²/8 bytes (since booleans can be packed). For a social network with 1 million users, this translates to 125 GB of memory just for the adjacency matrix, even if most users have only a few hundred connections. The memory layout is cache-friendly for row-wise access patterns, but checking all neighbors of a vertex requires scanning an entire row, touching n memory locations regardless of the actual degree.

Adjacency lists, conversely, store a graph by maintaining a list for each vertex, where each list contains the vertices adjacent to it. For an undirected graph, each edge appears in the lists of both vertices it connects, while in a directed graph, an edge from i to j appears only in i's list. This method is more memory-efficient for sparse graphs (O(V + E) space, where V is vertices and E is edges) but requires O(degree(v)) time to check if an edge exists, where degree(v) is the number of neighbors of vertex v.

In adjaceny lists emory usage scales with O(V + E), where V is vertices and E is edges. For our million-user social network with an average of 300 connections per user, this requires only about 2.4 GB of memory - a 50x improvement over adjacency matrices. However, checking if a specific edge exists becomes O(degree) operation, requiring a linear search through the neighbor list. This can be optimized using hash sets instead of vectors for neighbor storage.

class AdjacencyList {
    constructor(n) {
        this.numVertices = n;
        this.adjList = new Array(n);
        for (let i = 0; i < n; i++) {
            this.adjList[i] = []; // Initialize each vertex's neighbor list
        }
    }

    // Add an undirected edge between u and v
    addEdge(u, v) {
        this.adjList[u].push(v);
        this.adjList[v].push(u); // For undirected graph
    }

    // Get neighbors of vertex u
    getNeighbors(u) {
        return this.adjList[u];
    }
}

const graph = new AdjacencyList(5);

graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 3);

console.log(graph.getNeighbors(0)); // [1]
console.log(graph.getNeighbors(1)); // [0, 2]
console.log(graph.getNeighbors(2)); // [1, 3]

With our data properly organized, what can actually do with these graph structures ??

Exploring Graphs

Graph traversal algorithms are the foundation for most graph operations. They allow us to systematically visit every vertex in a graph, forming the basis for more complex algorithms. The two fundamental traversal methods are Depth-First Search (DFS) and Breadth-First Search (BFS).

For new audience (if any, yeah I am delusional) I have explained Depth First Search and Breadth First Search in my previous blog about Algorithms from Beginners POV do check it out. I will be just skimming through the topics here :))

Depth-First Search explores a graph by going as deep as possible along each branch before backtracking. It's like we are exploring a maze by always taking the first available path and only turning back when we hit a dead end. DFS uses a stack (either explicitly or through recursion) to keep track of vertices to visit. This approach is excellent for problems like detecting cycles, finding connected components, or exploring all possible paths.

Breadth-First Search, conversely, explores all vertices at the current depth before moving to vertices at the next depth level. It's like ripples spreading out from a stone dropped in water. BFS uses a queue to ensure vertices are visited in order of their distance from the starting point. This makes it perfect for finding the shortest path in unweighted graphs or for level-order traversals.

These traversal methods sound useful, but how do they help us solve real-world problems like finding the shortest route between two locations?

Finding the Optimal Route

Finding the shortest path between two points is one of the most practical applications of graph algorithms. While BFS can find the shortest path in unweighted graphs, real-world scenarios often involve weighted edges where we need more sophisticated approaches.

Dijkstra's algorithm is the gold standard for finding shortest paths in weighted graphs with non-negative edge weights. It works by maintaining a set of vertices whose shortest distance from the source is known, gradually expanding this set by always choosing the vertex with the minimum tentative distance. Think of it as simultaneously exploring all possible routes from your starting point, but always prioritizing the most promising paths.

The algorithm maintains a priority queue of vertices to visit, always processing the one with the smallest known distance first. As it visits each vertex, it updates the distances to its neighbors if a shorter path is found. This greedy approach guarantees finding the optimal solution.

For graphs with negative edge weights, the Bellman-Ford algorithm provides a solution, though it's slower than Dijkstra's algorithm. It works by repeatedly relaxing all edges, gradually improving distance estimates until no further improvements are possible.

These algorithms power GPS navigation systems, network routing protocols, and any application where finding optimal paths is crucial.

Shortest paths are fascinating, but what about scenarios where we need to connect multiple points efficiently, like designing a network infrastructure ??

Connecting Everything Efficiently

When we need to connect all vertices in a graph with the minimum total cost, we are looking for a Minimum Spanning Tree (MST). This is crucial in network design, where we want to ensure all nodes are connected while minimizing the total cost of connections.

A spanning tree of a graph is a subgraph that includes all vertices and is connected (you can reach any vertex from any other vertex) but contains no cycles. The minimum spanning tree is the spanning tree with the smallest total edge weight.

Kruskal's algorithm approaches this problem by sorting all edges by weight and adding them to the MST one by one, skipping any edge that would create a cycle. It uses a disjoint set data structure to efficiently detect cycles. This greedy approach works because the optimal solution always includes the cheapest available connection that doesn't create redundancy.

Prim's algorithm takes a different approach, starting with an arbitrary vertex and growing the MST by repeatedly adding the cheapest edge that connects a vertex in the MST to a vertex outside it. Both algorithms guarantee finding the optimal solution, but they approach the problem from different angles.

class PriorityQueue {
    constructor() {
        this.items = [];
    }

    enqueue(item, priority) {
        this.items.push({ item, priority });
        this.items.sort((a, b) => a.priority - b.priority);
    }

    dequeue() {
        return this.items.shift().item;
    }

    isEmpty() {
        return this.items.length === 0;
    }
}

function primMST(graph) {
    const vertices = Object.keys(graph);
    if (vertices.length === 0) return [];

    // Initialize data structures
    const parent = {};
    const key = {};
    const inMST = {};
    const pq = new PriorityQueue();

    // Initialize all keys to Infinity and parents to null
    vertices.forEach(vertex => {
        key[vertex] = Infinity;
        parent[vertex] = null;
        inMST[vertex] = false;
    });

    // Start with the first vertex
    const startVertex = vertices[0];
    key[startVertex] = 0;
    pq.enqueue(startVertex, 0);

    while (!pq.isEmpty()) {
        const currentVertex = pq.dequeue();
        inMST[currentVertex] = true;

        // Explore all adjacent vertices
        for (const neighbor in graph[currentVertex]) {
            const weight = graph[currentVertex][neighbor];

            // If neighbor is not in MST and weight is less than current key
            if (!inMST[neighbor] && weight < key[neighbor]) {
                parent[neighbor] = currentVertex;
                key[neighbor] = weight;
                pq.enqueue(neighbor, key[neighbor]);
            }
        }
    }

    // Construct the MST edges (excluding the root)
    const mst = [];
    for (const vertex in parent) {
        if (parent[vertex] !== null) {
            mst.push({
                from: parent[vertex],
                to: vertex,
                weight: graph[parent[vertex]][vertex]
            });
        }
    }

    return mst;
}

// using Prim's algorithm
const graph = {
    'A': { 'B': 2, 'D': 6 },
    'B': { 'A': 2, 'C': 3, 'D': 8, 'E': 5 },
    'C': { 'B': 3, 'E': 7 },
    'D': { 'A': 6, 'B': 8, 'E': 9 },
    'E': { 'B': 5, 'C': 7, 'D': 9 }
};

const minimumSpanningTree = primMST(graph);
console.log("Minimum Spanning Tree Edges:");
console.log(minimumSpanningTree);

These algorithms are essential in designing telecommunication networks, electrical grids, and any infrastructure where you need universal connectivity at minimum cost.

Directed Graphs and Network Flow

Directed graphs introduce concepts like in-degree and out-degree (the number of incoming and outgoing edges for each vertex). They also enable topological sorting, which arranges vertices in a linear order such that for every directed edge from vertex A to vertex B, A appears before B in the ordering. This is crucial for scheduling tasks with dependencies.

Network flow problems take directed graphs further by adding capacity constraints to edges. Like a network of pipes where each pipe can only carry a certain amount of fluid. The maximum flow problem asks: what's the maximum amount of flow you can push from a source to a sink?

The Ford-Fulkerson algorithm solves this by repeatedly finding augmenting paths (paths from source to sink with available capacity) and pushing flow along them until no more augmenting paths exist. This approach has applications in traffic management, resource allocation, and even matching problems.

/**
* Ford-Fulkerson Algorithm for Maximum Flow in a Flow Network
* 
* This implementation uses the Edmonds-Karp approach (BFS for finding augmenting paths)
* to ensure polynomial time complexity O(VE²).
* 
* The algorithm finds the maximum possible flow from a source node to a sink node
* in a directed graph where each edge has a capacity.
*/

class FlowNetwork {
    /**
    * Initialize the flow network with adjacency list representation
    * @param {number} vertices - Number of vertices in the graph
    */
    constructor(vertices) {
        this.V = vertices; // Number of vertices
        this.graph = new Array(vertices); // Residual graph
        
        // Initialize adjacency list for each vertex
        for (let i = 0; i < vertices; i++) {
            this.graph[i] = new Array(vertices).fill(0);
        }
    }

    /**
    * Add an edge to the flow network with a given capacity
    * @param {number} u - Source vertex
    * @param {number} v - Destination vertex
    * @param {number} capacity - Maximum flow capacity of the edge
    */
    addEdge(u, v, capacity) {
        this.graph[u][v] = capacity; // Forward edge capacity
        this.graph[v][u] = 0; // Backward edge initially 0 (for residual graph)
    }

    /**
    * Breadth-First Search to find if there's a path from source to sink with available capacity
    * Also stores the path found in parent[] array
    * @param {number} s - Source vertex
    * @param {number} t - Sink vertex
    * @param {number[]} parent - Array to store the path
    * @returns {boolean} - True if path exists, False otherwise
    */
    bfs(s, t, parent) {
        // Create a visited array and mark all vertices as not visited
        const visited = new Array(this.V).fill(false);
        
        // Create a queue for BFS, enqueue source vertex
        const queue = [];
        queue.push(s);
        visited[s] = true;
        parent[s] = -1; // Source has no parent

        // Standard BFS loop
        while (queue.length > 0) {
            const u = queue.shift();

            // Explore all adjacent vertices
            for (let v = 0; v < this.V; v++) {
                // If vertex not visited and residual capacity > 0
                if (!visited[v] && this.graph[u][v] > 0) {
                    // If we reach the sink, we have a path
                    if (v === t) {
                        parent[v] = u;
                        return true;
                    }
                    
                    queue.push(v);
                    parent[v] = u;
                    visited[v] = true;
                }
            }
        }

        // We didn't reach the sink
        return false;
    }

    /**
    * Main function implementing Ford-Fulkerson algorithm
    * @param {number} source - Source vertex
    * @param {number} sink - Sink vertex
    * @returns {number} - Maximum flow from source to sink
    */
    fordFulkerson(source, sink) {
        // Validate input
        if (source < 0 || source >= this.V || sink < 0 || sink >= this.V) {
            throw new Error("Invalid source or sink vertex");
        }
        if (source === sink) {
            return 0; // No flow if source and sink are same
        }

        // This array is filled by BFS and stores path
        const parent = new Array(this.V).fill(-1);
        let maxFlow = 0; // Initialize max flow to 0

        // Augment the flow while there is path from source to sink
        while (this.bfs(source, sink, parent)) {
            // Find minimum residual capacity of the edges along the path
            let pathFlow = Infinity;
            
            // Traverse from sink to source using parent array
            for (let v = sink; v !== source; v = parent[v]) {
                const u = parent[v];
                pathFlow = Math.min(pathFlow, this.graph[u][v]);
            }

            // Update residual capacities of the edges and reverse edges
            for (let v = sink; v !== source; v = parent[v]) {
                const u = parent[v];
                // Subtract path flow from forward edge
                this.graph[u][v] -= pathFlow;
                // Add path flow to reverse edge
                this.graph[v][u] += pathFlow;
            }

            // Add path flow to overall flow
            maxFlow += pathFlow;
        }

        return maxFlow;
    }
}


function main() {
    // Create a flow network with 6 vertices (0 to 5)
    const g = new FlowNetwork(6);

    // Add edges with capacities
    g.addEdge(0, 1, 16); // s -> v1
    g.addEdge(0, 2, 13); // s -> v2
    g.addEdge(1, 2, 10); // v1 -> v2
    g.addEdge(1, 3, 12); // v1 -> v3
    g.addEdge(2, 1, 4);  // v2 -> v1
    g.addEdge(2, 4, 14); // v2 -> v4
    g.addEdge(3, 2, 9);  // v3 -> v2
    g.addEdge(3, 5, 20); // v3 -> t
    g.addEdge(4, 3, 7);  // v4 -> v3
    g.addEdge(4, 5, 4);  // v4 -> t

    const source = 0; // Source vertex (s)
    const sink = 5;   // Sink vertex (t)

    console.log("Running Ford-Fulkerson algorithm...");
    const maxFlow = g.fordFulkerson(source, sink);
    console.log(`The maximum possible flow from ${source} to ${sink} is: ${maxFlow}`);
}

main();

Here's my few notes on graphs and why am I investing my time in graphs

Web search engines model the internet as a massive directed graph where web pages are vertices and hyperlinks are edges. Google's PageRank algorithm uses this graph structure to determine page importance based on the link structure, revolutionizing how we find information online.

After spending so much time with machine learning algorithms and neural network, ml on graphs is an ongoing thing which everyone should once go through, with graph neural networks learning representations directly from graph structure. This opens new possibilities for problems like node classification, link prediction, and graph generation.

This is all from myside on Graphs. Hope I was able to add few value to your today's learning :)

Algorithms 101 : From Beginners POV

Mrinal — Invalid Date

Algorithms 101 : From a Beginners POV

12th June, 2025

Before writing this I took a minute and remembered how I imagined myself writing algorithms for optimizing data models which fastens up the data retrieval rate would look like. But by time I grew in this field I got to know that algorithms aren’t just code. These are some of the smart ways to tackle a problem and make data work faster

As ritual I will be covering few algo topics here which I use/have used on basis of my projects, paid gigs etc. The complexity of these algorithms will rise up gradually as the blog continues.
I hope you all know what is Linear Search ?
If not no worries this is the most common technique used by algorithms to lookup for a solution to the problem, take it as searching for word in dictionary before knowing "How to search words in dictionary" going through all the pages, but its okkay if the dictionary had only 10 to 15 pages but you would need a better and optimized way when there are literally 800+ pages

Binary Search

This is a fast and efficient algorithms but only for sorted array or list, works by repeatedly dividing in the search space in half, which reduces the number of elements to check. Starting at the middle of the array, it compares the target value to middle element. If the target matches, the search is complete.
If the target is smaller, it searches the left half, if larger the right half. This process continues until the value is found

For algorithms we will be talking more about time complexity. So Binary Search's time complexity is \(O (\log n)\), making it faster than linear search for large sorted datasets

This is mainly used in searching databases, lookup tables, or implementing features like autocomplete. Here is an example of an api function which searches for a user by ID in a sorted list of users.

// Using Linear Search an going in sequential order
// it will take 10k iterations if we want to find the last user
const users = [
{ id: 1, name: "Sonita" },
{ id: 2, name: "Bonita" },
{ id: 3, name: "Aarav" },
// ... 10 thousand more more
];
function findUser(userId) {
  return users.find(user => user.id === userId); // O(n)
}

After using Binary Search Algorithm, for 10k users it just needs 14 comparisons at most to find any user

// ideal for static, sorted data like indexes or databases 
function binarySearch(users, userId) {
  let left = 0, right = users.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (users[mid].id === userId) return users[mid];
    if (users[mid].id < userId) left = mid + 1;
    else right = mid - 1;
  }
  return null;
}

This algorithm can also be applied in client side for searching an item in a sorted dropdown list

Depth First Search

The idea of DFS is starting with the root node and go as far down one branch as possible, all the way to the end.

After reaching the dead end we come back to the last visited node, this process of going back to the last visited node is called Backtracking[2]. We check if there are any unvisited nodes left. If there are, we explore those nodes next. If not, we backtrack again to the previous node. This process repeats until every node in the graph or tree has been visited[3].

The time complexity of DFS depends on the graph's structure. For a graph with Vvertices (nodes) and E edges (connections), using a list of connected nodes. DFS takes \(O(V + E)\) time. This because it visits each vertex once and checks all edges to explore neighbors. It’s fast for most graphs, especially sparse ones like social networks, as it only processes the actual connections

One of the OSS issue on which I worked was related to ui rendering nested comments inefficiently with manual looping, which struggled with deep nesting

// the comments where fetched from db and stored in a list
const comments = [
  { id: 1, text: "Great!", replies: [{ id: 2, text: "Thanks!" }] },
  { id: 3, text: "Cool", replies: [] },
];
function renderComments() {
  let html = "";
  for (let comment of comments) {
    html += `${comment.text}`;
    if (comment.replies) {
      for (let reply of comment.replies) {
        html += `${reply.text}`;
      }
    }
  }
  return html;
}

My Pull request for the same issue, used DFS. I have attached the full anatomy here

//  Ideal for exploring all paths, detecting cycles, or solving problems requiring exhaustive search.

// "comments" is an array of comment objects
// "deep" is an optional parameter indicating how deep in the reply
// hierarchy we are, will be starting at 0 (top-comment)
function renderComments(comments, depth = 0) {
  // this will hold the final html output that gets
  // returned
  let html = "";
  // helps in iterating through each comment
  for (let comment of comments) {
    // appending the current comment's text to
    // the html string
    "html += `${comment.text}`;"

    // using recursion here
    if (comment.replies) {

      // if the comment has replies 'comment.replies' exits, then recursively renderComments
      // on those replies
      // and increase the depth by 1 to indicate you are now
      // rendering a deeper level of replies
      html += renderCommentsDFS(comment.replies, depth + 1);
    }
  }
  return html;
}

This can also be used for detecting cycles in dependency graphs for building package managers.

Breadth First Search

In Breadth first search it explores graphs differently. Instead of diving deep like DFS, BFS visits all nodes at the current "level" before moving to next.

Starting from a chosen node, it explores all its immediate neighbors first, then their neighbors, and so on. This makes BFS ideal for finding the shortest path in unweighted graphs for exploring nodes closer to starting point.

For the time complexity part we can say its similar to DFS which is \(O (V + E) \) but the only difference is, BFS uses queue to track nodes, ensuring it explores closer nodes first, which is why its great for finding shortest paths in unweighted graphs, like in navigation apps or GPS

Code Dissection of Friends graph is written below


const users = {
  'Sonita': ['Aarav', 'Charlie'],
  'Bonita': ['Vegeta', 'David'],
  'Gojita': ['Vegito'],
  'Majin Buu': ['Mr. Satan']
};

function findConnection(user1, user2) {
  // starting with user1 with a connection distance of 0
  const queue = [[user1, 0]];
  // this const keeps track and avoids revisiting
  const visited = new Set([user1]);

  // this is the main loop for BFS
  while (queue.length) {
    // taking the front node using 'shift()' is used because it's a
    // queue, 'user' is the current person being explored
    // distance is how many steps away this user is from user1
    const [user, distance] = queue.shift();

    // if the current user is the target, return the distance
    // this also shows no.of steps needed to get from user1 to user2
    if (user === user2) return distance;

    // for every friend of current user
    // if we haven't seen this friend before
    // mark them as visited
    // add them to queue with an updated distance (distance + 1) 
    // one more step away from user1
    for (let friend of users[user]) {
      if (!visited.has(friend)) {
        visited.add(friend);
        queue.push([friend, distance + 1]);
      }
    }
  }

  // if loop finishes without any friends
  // than we return -1 means (not found)
  return -1;
}

Insertion Sort Algorithm

Insertion sort is a simple sorting algorithm that builds a sorted array one element at a time.

Starting with the second element, insertion sort compares it to the previous ones, shifting larger elements right until it finds the right spot to "insert" the element. This process repeats for each element until the entire array is sorted. Works well for small datasets or nearly sorted lists, like organizing a short list of names or numbers.

The time complexity of Insertion Sort depends on the array size and its initial order. For an array with n elements, the worst-case time complexity is \(O(n^2)\), as each element may need to be compared and shifted against all previous elements, like when the array is reverse-sorted. In the best case, such as a nearly sorted array, it runs in \(O(n)\) time, as each element requires minimal comparisons and shifts. This makes Insertion Sort efficient for small or nearly sorted datasets but less ideal for large, unsorted lists compared to faster algorithms like Quick Sort.

We can code a Search history using insertion sort


function insertionSort(arr) {
  // Start from the second element (i = 1), since the first element is considered "sorted"
  for (let i = 1; i < arr.length; i++) {
    
    // 'key' is the current element we want to insert into the sorted part of the array
    let key = arr[i];

    // 'j' marks the end of the sorted portion (just before the current element)
    let j = i - 1;

    // Move elements of arr[0..i-1], that are less than 'key.time', one position ahead
    // We sort in descending order based on 'time' property
    while (j >= 0 && arr[j].time < key.time) {
      // Shift the element to the right
      arr[j + 1] = arr[j];
      j--; // Move one step back in the array
    }

    // Insert the 'key' in its correct position
    arr[j + 1] = key;
  }

  // Return the sorted array
  return arr;
}

Merge Sort Algorithm

Its a reliable sorting algorithm which uses a divide and conquer approach to sort arrays efficiently.

It works by splitting the array into two halves, sorting each half recursively, and then merging the sorted halves back together to create a fully sorted array. Its stable meaning, it preserves the relative order of equal elements, and is ideal for large datasets, like sorting customer records or database entries, due to its consistent performance.

Lets talk a little about the time complexity here, merge sort has a time complexity of \(O(n log n)\) in all cases from best, average to worst. For example lets take the above figure which is [4, 2, 5, 1, 8, 3, 7, 6] here \(n=8\) elements and for \(n=8\), it takes \(log_2 8 = 3\) levels of division (8 -> 4 pairs -> 2 groups of 4 -> 1 group of 8). Our figure starts with four groups of two, which is part of this process

At each level, all \(n\) elements are merged. Merging two sorted lists compares and combines elements in linear time. Merging four pairs \(([4, 2], [5, 1], [8, 3], [7, 6])\) into two groups takes about 8 comparisons total. Merging two groups \(([1, 2, 4, 5], [3, 6, 7, 8])\) into one takes another 8 comparisons
The O(n log n) complexity holds because the number of divisions is logarithmic \(log n \), and each merge step scales linearly with \(n \). Unlike Insertion Sort's \(O(n^2)\) (upto 64 operations for n = 8)

Before
The API gets session data from the DB. Uses .sort() which may be unstable or optimized differently depending on V8 engine. So we get less control over performance in large datasets

// routes/sessionStats.js
app.get('/api/sessions/sorted', async (req, res) => {
  const sessions = await db.getUserSessions(); // returns array like [120, 30, 45, 60]
  
  // Using built-in sort (not always stable or predictable)
  const sorted = sessions.sort((a, b) => a - b);

  res.json({ sorted });
});

After using Merge Sort
After using our own implementation of merge sort and replacing it with built-in sort, it helped with performance tuning and custom rules which can handling large logs or preprocessing logs offline

// utils/mergeSort.js
function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }

  return result.concat(left.slice(i)).concat(right.slice(j));
}

module.exports = { mergeSort };


// on different file we can call the function and use it
const { mergeSort } = require('../utils/mergeSort');

app.get('/api/sessions/sorted', async (req, res) => {
  const sessions = await db.getUserSessions();

  const sorted = mergeSort(sessions);

  res.json({ sorted });
});

Quick Sort Algorithm

This uses the same strategy as Merge Sort algorithm which is divide and conquer strategy to sort arrays. But it works by picking a "pivot" element, partitioning the array so that element smaller than the pivot are on its left and larger ones on its right, then recursively sorting the left and right sub-arrays.

Quick Sort is fast and widely used for large datasets, like sorting student grades or product lists, due to its average-case speed.

For an array with n elements, Quick Sort’s time complexity is \(O (n log n)\) on average, making it very fast for most cases. It divides the array into two parts around a pivot, ideally halving the problem size each time, requiring log n levels and n comparisons per level. sorting an array of 8 elements takes about 24 operations (8 * log 8). In the worst case, like a sorted or reverse-sorted array with a poor pivot choice, it can degrade to O(n²), but this is rare with good pivot strategies.

Choosing a good pivot is crucial for efficiency, as it effects how evenly the array is split. Here are some common steps you can include while choosing one :

First / Last Element: Pick the first or last element, but this can lead to \(O(n^2)\) time in sorted or reverse-sorted average performance.
Random Pivot : Select a random element to reduce the chance of worst-case scenarios, improving average performance. But how you would ask. Choosing a random pivot in quick sort increases avg. performance by reducing the likelihood of consistently poor partitions, which can lead to worst-case \(O(n^2)\) time complexity.When a pivot is randomly selected from the array, it’s unlikely to repeatedly pick the smallest or largest element, as happens in sorted or nearly sorted arrays with fixed pivots (e.g., first element). Instead, random pivots tend to create more balanced partitions, splitting the array closer to half each time, which aligns with the ideal \(O(n log n)\) average-case performance. For example, in \([4, 3, 5, 2, 6, 1, 7, 8]\), a random pivot like 5 might split into [4, 3, 2, 1] and [6, 7, 8], keeping sub-arrays roughly equal. This randomness averages out bad cases over many runs, ensuring partitions are balanced more often, with each level taking O(n) comparisons across log n levels.

Before
The best way I learned quick sort algorithm was by implementing it in a e-commerce api in which products were sorted by price, at first I thought using .sort() would be but NVM XDD. It was simple and short but lacked control and it can't handle complex logic lick preprocessing, side effects, or tracing steps for debugging

// routes/products.js
app.get('/api/products/sorted', async (req, res) => {
  const products = await db.getProducts(); // [{ name: "Shoes", price: 80 }, ...]

  const sorted = products.sort((a, b) => a.price - b.price);

  res.json({ sorted });
});

After
After learning and implementing my own Quick Sort to sort products by price, this let me add debug logs, skip invalid prices, add thresholds or filtering inline, or customize order (ascending / descending)

function quickSortProducts(arr, ascending = true) {
  if (arr.length <= 1) return arr;

  const pivot = arr[arr.length - 1];
  const left = [];
  const right = [];

  for (let i = 0; i < arr.length - 1; i++) {
    if (!arr[i].price) continue; // skip if price is missing

    if (ascending ? arr[i].price < pivot.price : arr[i].price > pivot.price) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return [
    ...quickSortProducts(left, ascending),
    pivot,
    ...quickSortProducts(right, ascending),
  ];
}

module.exports = { quickSortProducts };

const { quickSortProducts } = require('../utils/quickSortProducts');

app.get('/api/products/sorted', async (req, res) => {
  const products = await db.getProducts();

  const order = req.query.order || 'asc'; // ?order=desc
  const sorted = quickSortProducts(products, order === 'asc');

  res.json({ sorted });
});

I wanted to add greedy algorithm and DP but that would be an overkill for this blog, these are searching and sorting algorithms which is mainly used during development
Hope I was able to add few value to your today's learning :)

Using Data Structures and Algorithms practically

Mrinal — Invalid Date

Using Data Structures practically

2nd June, 2025

Whenever I think of data structures and algorithms it scares me a little because, past few interviews I have been lacking on my algorithms skills a little bit. But when I changed my prespective to learn it through building projects with just raw code like "Just working" mindset and then picking up every topic of data structures, learning it, and then applying the topic in the "Just working" project to make it more optimize

I will be covering few ds and algo that I use on everyday basis for my development of project, paid gigs etc.
For the very first lets start with data structure topics, so going by the name it means structuring a data or large set of data in a mannered way . :)) WOOWWW !!

Data Structures and its usage

Starting with the easiest one, which is arrays then gradually increase the complexity of topics.

Arrays

These are containers for storing multiple data types in a ordered manner, like a bunch of strings, a bunch of integers, or you can mix up the types of data that you want to be stored (only few languages allow this mix-up). Each elements in an array is assigned with a number known as "indexing", and arrays are zero-indexed which means first element's index is 0.

Lets talk a little bit about memory here, see arrays are stored in contiguos manner means each elements are stored which means elements of arrays are next to one another this makes reading arrays faster which is O(1) according to time complexity, but this also makes insertion and deletion of items slower

How doest insertion and deletion becomes slower ?? So here is the thing, arrays are always grouped together so if user pushes a new variable in the middle the arrays get updated accordingly. But what if the very next memory is not free, whole array with allocated memory needs to shift to a new place. This makes reading easier (O(1)) but insertion (O(n)) and deletion (O(n)) gets a bit slower.

Now arrays are basic, foundational data structures commonly used in the first approach itself without even thinking, as they efficiently store and manage collections of elements. But we will look down for problem which it really solves. :))

You are building a simple to-do list app for yourself, you want to store and display tasks they've completed today.

// Without arrays - manual handling
let task1 = "Buy groceries";
let task2 = "Finish homework";
let task3 = "Call mom";
          
console.log("Completed Tasks:");
console.log("1. " + task1);
console.log("2. " + task2);
console.log("3. " + task3);

// After using Arrays
let tasks = ["Buy groceries", "Finish homework", "Call mom"];

console.log("Completed Tasks:");
for (let i = 0; i < tasks.length; i++) {
    console.log((i + 1) + ". " + tasks[i]);
}

Linked List

Linked list are just opposite to arrays, they are faster while insertion and deletion of items while a bit slow on reading items. It consists of nodes where each node holds data and a pointer(address to another node). Also

This structure makes linked lists dynamic and flexible in scenarios where frequent insertions and deletions are required.

Let's talk about memory a little bit, each node is stored independently, containing the data and a pointer to next node, which allows linked lists to grow or shrink dynamically without needing to resize a predefined array. This dynamic allocation is memory efficient for datasets which are unpredictable with their sizes. However reading becomes slow as if you want a element from middle you need to get the first element then to the desired item, this some times leads to memory fragmentation over time, as nodes are scattered across memory.

Okkay how I learned it in a hard way ?? I was building a backend service to manage a queue of user support ticket. Each ticket needs to be processed in order, and new tickets can come in dynamincally.

After discussing with GPT, I got to realise this is not the most efficent methods to use, go then I got to know about Linked List and then how to use it, this is how I implemented it from scratch.

// this represents the a single node in the linked list
// holding one ticket
class TicketNode {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

// this class will be managing the queue of tickets using Linked List
// keeping the track of head(first node) and tail(last node) nodes
class TicketQueue {
    constructor() {
        this.head = null;
        this.tail = null;
    }
    
    // enqueue method adds a new ticket to the end of the queue
    // (FIFO principle : last in, processed last)
    // time complexity : O(1), as it 
    // only involves creating a node and updating pointers

    enqueue(data) {
        const newNode = new TicketNode(data);
        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
    }

    // this method removes and returns the ticket at the front of the queue
    // FIFO : first in, processed first
    // O(1) : as it only updates the pointer
    dequeue() {
        if (!this.head) return null;
        const removed = this.head.data;
        this.head = this.head.next;
        if (!this.head) this.tail = null;
        return removed;
    }

    // printAll method is like reading and displaying
    // O(n) : where n is the number of nodes, 
    // because its going to visit each node once 
    printAll() {
        let current = this.head;
        let index = 1;
        while (current) {
            console.log(`${index++}. ${current.data}`);
            current = current.next;
        }
    }
}

const queue = new TicketQueue();
queue.enqueue("Ticket #001: Login issue");
queue.enqueue("Ticket #002: Payment error");
queue.enqueue("Ticket #003: Forgot password");

console.log("Processing:", queue.dequeue());

console.log("Remaining Tickets:");
queue.printAll();

Now what is FIFO ?? its a simple way of saying how the data will be flowing in a particular way, like FIFO means First In First Out, and on the other hand we have LIFO which means Last In First Out

As an engineer I would have questioned, how would I optimize a linked list for faster read operations if traversal time becomes a bottleneck ??

HashMaps

Hash maps or Hash tables, are just like arrays but here the values of a key instead of a index number, which makes it a key-value pair. This makes the reading, inserting and deleting process faster typically O(1) on average. Hash maps use a clever trick called hashing to map keys directly to their values, making them incredibly efficient for specific use cases.

For example if we are storing capitals of a country then instead of indexing we can store the country name instead.

Here is a small example which I learned in python, it is also known as dictionary in python

user_map = {}

# Setting up Key-value pair 
user_map["mrinaltest@example.com"] = {"name": "Mrinal", "id": 123}
user_map["mrinaltest2@example.com"] = {"name": "Pramanick", "id": 456}

# Lookup in O(1) average time
print(user_map["mrinaltest3@example.com"]) 
# Output: {"name": "Pramanick", "id": 123}

Lets talk about memory little bit. Hash maps gives up on memory for speed. They allocate fized-size, which might waste space if not full utilized. Collisions can also slow things down if the hash function isn't well-designed or the load factor (ratio of entries to array size) gets to high. Unlike linked lists, hash maps don't preserve insertion order so they're not suited for sequential processing.

Stacks and Queues

So you might have question what if we need to maintain the order of elements while also needing fast lookups ?? Here comes stacks, its a linear data structure that follows the Last In, First Out(LIFO) principle. A simple explaination of stacks would be a stack of plate, the first plate would be at bottom and picked at last, and the last plate would be picked up at first

there are four major operations performed on this and the upcoming data structure which are Push (add an element to the top (O(1)). Pop (remove and return the top element (O(1)). Peek/Top (view the top element without removing it (O(1)). IsEmpty checks if the stack is empty (O(1))

My favourite part MEMORY, stacks can be implemented using arrays or linked lists. An array-based stack requires a fixed or dynamically resized array, which may waste space if not fully utilized(similar to hash maps). A linked list-based stack allocates memory per node (data + pointer), growing or shrinking dynamically like a linked list.
Linked list-based stacks avoid resizing overhead but may cause memory fragmentation, as nodes are non-contiguous. Array-based stacks are more memory-efficient for predictable sizes but require resizing if the stack grows beyond capacity, temporarily doubling memory use during resizing

The best pactical way to use stacks is by building a UNDO or REDO funtion, each user action (e.g., typing or deleting) is to be pushed onto a stack. Pressing "undo" popped the most recent action, reverting the change. A stack is ideal because the last action needed to be undone first

class UndoStack:
def __init__(self):
    self.stack = []

def push_action(self, action):
    self.stack.append(action)

def undo(self):
    if self.stack:
        return self.stack.pop()
    return None

def is_empty(self):
    return len(self.stack) == 0

undo_stack = UndoStack()
undo_stack.push_action({"id": 1, "type": "type", "value": "Hello"})
undo_stack.push_action({"id": 2, "type": "delete", "value": "o"})
print(undo_stack.undo())  
# Output: {"id": 2, "type": "delete", "value": "o"}

Queues are just opposite to stacks they follow the FIFO principle which means First In First Out, like a line at a ticket counter: the first person in line is served first. Queues are ideal for processing tasks in the order they arrive. Also queues and stacks share the same memory implications

One of the best ways to visualize a stack is with a YouTube channel's video list. The most recently uploaded video appears at the top, while the oldest video is at the bottom, resembling a stack's Last In, First Out (LIFO) structure.

The upcoming topics are one the best things I have learned so far, also do give some attempts for solving the few questions related to all the topics enlisted here :)

Trees

Trees are hierarchical data structures consisting of nodes connected by edges, with a single root node at the top and child nodes branching out. Each node can have zero or more children, and nodes without children are called leaves.

Nodes have parent child direction, where each node (except the root) has exactly one parent, and a parent node can have zero or more children. This directional structure defines the hierarchy, with edges pointing from parent to child, enabling efficient modeling of relationships like organizational charts or file systems.

Knowing little about memory here, trees are memory efficient for hierarchical data but fragmented due to dynamic allocation, if a tree is balanced it optimizes memory and performance by keeping height low, while unbalanced trees waste memory on pointers for deep, linear structures

A question would pop on your mind, what is even a balanced tree ?? So memory scales with the number of nodes (O(n)). A balanced tree with n nodes has a height of O(log n), minimizing traversal time, while an unbalanced tree may resemble a linked list with O(n) height

Lets talk more indepthly about trees using Binary Search tree, a tree where the left child's value is less than the parent's, and the right child's value is greater, this enables O(log n) searches, insertions, deletions if balanced, but O(n) if skewed

One best usecase for BST could implementing a topic from my blog about System Design which is database indexing for ordered data retrieval


class BSTNode:
# record ID or file name
# e.g., metadata (record details)
def __init__(self, key, value):
  self.key = key       
  self.value = value    
  self.left = None      # Left child
  self.right = None     # Right child

class DatabaseIndex:
    def __init__(self):
        self.root = None
    
    def insert(self, key, value):
        """Insert a key-value pair into the BST."""
        if not self.root:
            self.root = BSTNode(key, value)
        else:
            self._insert_recursive(self.root, key, value)
    
    def _insert_recursive(self, node, key, value):
        """Helper method for recursive insertion."""
        if key < node.key:
            if node.left is None:
                node.left = BSTNode(key, value)
            else:
                self._insert_recursive(node.left, key, value)
        else:
            if node.right is None:
                node.right = BSTNode(key, value)
            else:
                self._insert_recursive(node.right, key, value)
    
    def inorder_retrieval(self):
        """Retrieve all records in sorted order (inorder traversal)."""
        result = []
        self._inorder_recursive(self.root, result)
        return result
    
    def _inorder_recursive(self, node, result):
        """Helper method for inorder traversal."""
        if node:
            self._inorder_recursive(node.left, result)
            result.append((node.key, node.value))  # Store key-value pair
            self._inorder_recursive(node.right, result)

# Database indexing for ordered retrieval
db_index = DatabaseIndex()
# Insert records (e.g., file names or IDs with metadata)
db_index.insert("file1.pdf", {"size": 100, "path": "/docs/file1.pdf"})
db_index.insert("file3.pdf", {"size": 300, "path": "/docs/file3.pdf"})
db_index.insert("file2.pdf", {"size": 200, "path": "/docs/file2.pdf"})

# Retrieve records in sorted order (by key)
ordered_records = db_index.inorder_retrieval()
for key, value in ordered_records:
    print(f"Key: {key}, Value: {value}")
# Output:
# Key: file1.pdf, Value: {'size': 100, 'path': '/docs/file1.pdf'}
# Key: file2.pdf, Value: {'size': 200, 'path': '/docs/file2.pdf'}
# Key: file3.pdf, Value: {'size': 300, 'path': '/docs/file3.pdf'}

Graphs and algorithms need separate attention, so I am working on those blogs in my free time. If you urgently need those you can ping me or mention me on X(@Hi_Mrinal) will release it asap. Hope I was able to add few value to your todays learning :))
Happy Learning Anon :)

How to Read Research Papers

Mrinal — Invalid Date

Reading Research Papers 101

18th May, 2025

After reading white papers for a long peried, I have noticed that academic papers can hard to understand because of jargons and complex ideas, but they hold a lot of valuable information if we learn how to read to them.

Two papers which I haven't read

I get it, there are lots of research papers related to ai, backend, infrastructure coming out weekly. People posting I have read this paper, learned X Y Z and sometimes people (me) post that they have mimic the benchmarks and logic of the paper to build something out of it as a project and sometimes these projects can stand out from others and create a big difference.

But now you are excited, searched for papers from perplexity, it showed a arivx paper, you installed the pdf of the paper. NOW WHATT !! you go through the paper understand nil about the topic nor did you get the abstract :((

I have nearly read 30 ~ 35 papers this year from papers having 5 pages to papers having 30+ pages, so thought to write a little bit on how to start reading :))
Okkay first of all I want you to develop the ...

"Why am I reading this ?" habbit

Always have this question before staring any paper. This may looks simple but it really matters on how are your learnings from this paper will go through. Defining the purpose sharpens our focus, saves time and esures we extract meaningful insights from the paper, whether it's 5 page or 100+ page paper.

Now you would have the question, How to even build this habbit ?? so here is my trick before opening the PDF, take 30 seconds to jot down your purpose. Be specific. Instead of “I want to learn AI,” try “I want to understand how this paper’s attention mechanism improves model efficiency for my chatbot project.” Revisit this why if you feel lost mid-paper, it’s our anchor.

You have your paper installed, you got your "Why" now what ?? ...

The Helicopter View

Okkay starting with the second step, you need to know if the paper is really falling under your category of learning or the paper should be just surfed around. What does surfed around means ?? for me I dont really read papers to gain core knowledge, sometimes I read different genre research papers to gain a general knowledge of different fields so that when time comes I can really brag about it in twitter spaces or meetups and gain some new friends who can really teach me more :))

So comming back to our topic what is even Helicopter View ?? .. its just skimming the whole paper or just the title and abstract and categorize the paper, for me I my categories are core learning (learning related to skillset I own for now), surfing(just to read and take small notes), time pass(nothing serious just reading it to make a habbit).

This step helps me decide if I should go all in for paper and complete the paper in 1 ~ 2 weeks digging deep around the topics of the paper or just chill with the paper

You have gone through the title and the abstract, it's a paper that attracts your interest for learning and diving deep into the topic. Now what ?? .. Read it anon

Get the Hooks

This is what I do with most of the papers I dig deep into, after skimming the paper once I note down these questions and try to answer it my self, What are the main research question ?, What methods did they use ?, What are the main conclusions ? getting some of the core details help me to finish the paper with more understanding in least amount time spent on it.

Why does this work ? Answering these questions forces me to engage with the paper’s big picture before I get bogged down in details. For example, identifying the main research question tells me what problem the authors are tackling maybe it’s improving neural network efficiency or optimizing database queries. Knowing the methods (e.g., a novel algorithm or a specific dataset) gives me a sense of how they approached it, which is critical if I'm planning to replicate or build on their work. And the conclusions? They’re the payoff—what did the authors prove or discover? These hooks anchor my reading, so I'm not just passively scanning pages.

This step also helps me decide my commitment level. Let’s say the paper’s research question aligns perfectly with my project, and the methods are something I can experiment with. That’s my signal to go deep—maybe spend a week reading related papers or coding a small prototype. On the flip side, if the conclusions are interesting but not directly relevant, I can chill, extract the key takeaways, and move on. I’ve saved hours by using these hooks to avoid over-investing in papers that sound cool but don’t serve my goals.

Eye to Eye with the paper

Now, if I’ve decided to go all-in, it’s time to get eye to eye with the paper. When diving deep into the topics of research papers, I like to print a hard copy. There’s something about holding those pages that gives me a sense of responsibility to complete the paper. Replicating the system built by the authors give me a deeper knowledge of the methods and thier approach. I break the paper into sections and tackle them over a few days. For example, I’ll spend one session on the introduction and background to get the context, another on the methodology to understand the nuts and bolts, and a third on results and discussion to see what it all means. This paced approach prevents burnout and lets me absorb complex ideas. If the paper has code or datasets (check GitHub or the authors’ website!), I download them and start experimenting. Even a small replication like running their model on a toy dataset—can reveal insights that skimming never will.

How do I even remember what I have read and implemented ?? ..

Teach someone about the paper

I tend to teach the learnings of my paper either to one of my best friend or record a video while explaining the paper deeply which also enhances my speaking part and expands my vocabulary

Me explaining my best friend about the distributed system paper which I read. :))

Something to note

Often times the writing structure of the paper is bad becuase sometimes English is the second language for the author. There maybe some grammatical mistakes or punctuation mistakes but the most important thing should be the outcome or the message from the paper.
after finishing the paper, I always drop my notes as a cold email to the authors gmail and send a thank you message from my side just as a token of appreciation :))

Hope I was able to add value to your today's learning goal !! Happy Learning ..

Concurrency from a Beginners POV

Mrinal — Invalid Date

Concurrency 101 : From a Beginners POV

10th May, 2025

Concurrency has always been a difficult topic for me to wrap my head around, eiter be it in golang, javascript or python. Python and JavaScript approach concurrency in different ways because of their runtime environments. In this blog I want to deep dive into theory of concurrency because if we understand the engineering behind these topics we can easily code out it any language, thats what I believe.

Concurrency is not about doing many things at once, but about managing multiple tasks in a way that makes progress on all of them, even if they take turns, in todays time it helps to build faster, more reponsive, and scalable applications.

What is Concurrency ??

It is the ability of a program to manage multiple tasks at the same time. Concurrency dosen't necessarily mean these tasks are happening simultaneously ( like in parallel processing), it means they're interleaved or coordinated to make progress together. In programming, concurrency lets our app respond to user clicks while downloading data or processing a file.

it makes our program faster, more responsive, and efficient. Without it, our app might freeze while waiting for a slow database query which will make the users frustate and leave our app.

You might get a question if concurrency is about managing multiple tasks, how does a program actually switch between them without causing chaos ??
So moving to our next topic

Switching between tasks in Concurrency

Programs switch tasks using mechanisms like threads, processes, or event loops, managed by the operating system or the runtime. The CPU can only do one thing at a time, but by rapidly switching, it feels like multitasking

Process : Independent execution units with their own memory space, managed by the operating system. Each process has its own address space, stack and resources. For example, running two python scripts spawns two process. Processes communicate via inter-process communication (IPC) mechanisms like pipes, sockets, or shared files. They are heavyweight due to memory isolation but sage since they don't share data directly.

this is what process looks like under the hood, every other process has its own sets of code memory space and stack resource

Threads : its lightweight execution units within a process, sharing same memory space. They are managed by the OS and are cheaper to create than processes ( less memory overhead ), however shared memoery introduces risks like race conditions.

this is what shared memory space looks like :))

Event Loops : A single threaded mechanism that multiplexes tasks by processing a queue of events (eg. user clicks, I/O completions). The event loop checks for pending events, runs their handlers, and yields control when tasks wait (eg. a for a network reponse). Its like a waiter taking orders one at a time but moving fast keep tables happy.

the operating system's scheduler decides which task runs when, using context switching (saving and restoring task state), and for threads and processes, the scheduler uses preemption (pausing a task to run another) which are based on priorities and time slices.

Here is note from my side, context switching for processes is costlier than for threads due to memory management (e.g., updating page tables). Event loops minimize switching overhead by staying single-threaded, but they require tasks to be non-blocking. Example: In C, pthread_create spawns a thread with low overhead (~10µs), while fork() for a process takes ~100µs due to memory copying.

Okkay now after all this you might have a question if threads share memory, how do we prevent chaos when they access the same data simultaneously ??

Preventing chaos when threads access shared data

Shared memory threads risks race conditions, where the outcome depends on unpredictable execution order. Lets take two threads incrementing a shared variable counter = counter + 1. The operation involves three steps : read counter, increment, write back. If both threads readd counter as 10, increment to 11, and write, the final value is 11 instead of 12 due to overwriting.

Locks (Mutexes) : Ensure only one thread access shared data at a time. It acts like a key, if a thread locks the mutex, no other thread can enter the protected section until the original thread unlocks it. This prevents race conditions when multiple threads try to read or modify the same data simultaneously.

Internal workings of locks in a unit of execution

Semaphore : A semaphore is a more flexible synchronization mechanism than a mutex. It maintains an internal counter representing the number of available resources. Threads can wait on the semaphore (decrementing the counter), and if the counter becomes negative, the thread blocks until another thread signals (increments the counter)

Internal working of sempahores in a unit of execution

These primitives are implemente using OS-level constructs or hardware instructions. However, they introduce overhead and risks like priority inversion, where a low priority thread holding a lock delays a high-priority one.

So now what is overhead, and if locks add overhead and complexity, what to do if threads get stuck waiting for each other ?? But before this we need to know ..

What happens when threads get stuck waiting for locks ??

Lock, like mutexes or semaphores are essential for preventing race conditions when threads access shared data, but they introduce challenges like deadlocks, livelocks and performance overhead, but first what is overhead ?, it refers to the extra computational cost or resources consume by a system, process or operation which is not directly linked to the main task.

Deadlocks : This occurs when two or more threads are stuck, each waiting for a resource another holdds, forming a cicular dependency. Its like Chef A has the knife and needs the cutting board, while cheg B has the cutting board and needs the knife, neither can proceed. In code, this happens when threads acquire locks in different orders. If thread1 locks lock1 and thread2 locks lock2 simultaneously, they deadlock waiting for each other’s lock.
Livelock : Threads are active but make no progress because they keep responding to each other's actions. Taking examples my friends, (i dont have any) we both stepping aside and thinking one will pass but in reality nothing happens. In code, livelocks occur in algorithms where threads retry operations in a loop without resolving conflicts.
Starvation : A thread is denied access to a resource because other threads keep acquiring the lock. This often happens with unfair lock implementation or when high-priority threads dominate.

But now raises the question how do we prevent all these locks from happening ?

Always acquire locks in a consistent order to prevent deadlocks, this requires careful design for your program execution and from my experience the best you can do is use comments in code to serialize your locks :)). This strategy is known as Lock Ordering
Use non-blocking lock attempts to avoid waiting idefinitely or use logic which returns immediately if the lock is unavailable.
We can use timeouts which sets a deadline for lock acquisition, releases if the lock isn't acquired in time

If using lock is soo much hectic, can we coordinate tasks without using them at all ??

Cordinating tasks without Locks

There are two methods by which we can avoid locks that are lock-free programming and message passing.

Lock Free Programming this uses atomic operations, which are hardware-supported instructions that complete in a single, uninterruptible step. These operations avoid locks by ensuring sage updates to shared data. there are some common atomic operations which includes :

Compare and Swap : Checks if a variable has an expected value and updates it if so, atomically.
Fetch and Add : increments a variable and returns its old value.
Test and Set : sets a flag and returns its previous state

Lock-free algorithms are used in data structures like queues or counters, but they’re complex to design due to issues like the ABA problem (where a value changes from A to B and back to A, confusing the algorithm).

Message Passing : Message passing avoids shared memory entirely by having tasks communicate via messages. Each task (or “actor” in the Actor Model) has its own state and processes messages from a queue, eliminating race conditions. This is common in systems like Go’s concurrency model.

Actor Model what are these ?? its is a way to build computer programs that can do many things at once, without getting confused. Instead of sharing data or working on the same memory like in traditional programming, everything in the Actor Model is made up of small, independent units called actors . Each actor can receive messages, make decisions, send messages to other actors, and even create new actors all on their own.

We saw the problem with Locks and also solved it with Lock-free programming, now the question is with scalability for thousands of tasks

Scaling our concurrent program for many tasks

Processes : Scale by distributing tasks across cores or machines. Python’s multiprocessing.Pool creates a fixed number of processes (~10MB each), communicating via Queue. Distributed systems like Apache Spark use processes across nodes, coordinated via network messages. Processes are robust but memory-intensive, ideal for CPU-bound tasks like data analysis.
Threads : Scale using thread pools, which reuse threads (~1MB stack) to avoid creation overhead. Thread pools cap concurrency (e.g., 100 threads) to prevent exhaustion, using work-stealing algorithms for load balancing. Shared memory requires synchronization, limiting scalability under contention.

Event loops scale via OS multiplexing (epoll handles ~1M events), while thread pools optimize via work-stealing. Processes leverage distributed logs (e.g., Spark’s RDDs) for massive scale. Performance depends on workload: Input/Output-bound favors event loops, CPU-bound favors processes/threads.

Hope I was able to add value to your today's learning goal !! Happy Learning ..

System Design from a Beginners POV

Mrinal — Invalid Date

System Design 101 : From a Beginners POV

28th April, 2025

I really like to talk about system with people who are either really great at designing it or with peeps who are just getting started with this topic. For me System is very much vast topic to learn and be mastery off, as in tech there will always be something new to explore and learn.

System Design is not about writing the code, its about figuring out how everything fits together. Its the process defining the architecture, components, modules, interfaces and data flow of a system to meet specefic requirements

Small Components of Chat Application

Introduction

I am building a platform which is LeetSys, a small app running on a single server. When a user [client] wants to see questions, thier browser sends a request to our server. The server process this request, which then fetches posts from a database. The database sends back a response with the question data.

This client-server model is the foundation of web interactions. Requests and responses are typically sent over HTTP(HyperText Transfer Protocol), a stateless protocol that governs how clients and server should communicate. But soon LeetSys started to gain attraction among the users and gained a lot of virality, more and more users joined. So we need to scale our small app to millions of requests which can't be handled by our single CS[Client => Server] model

Scaling our platform

Our server is overwhelmed, and load times are sky rocketting. So what to do now ? We can do two things either opt for

Vertical Scaling : Which means we have to upgrade our server with more CPU, RAM and storage, this will boost performance temporarily, but there's a ceiling to how powerful a single server can get, and will cost us wayyyy to much !!

Or we can opt for

Horizontal Scaling : Instead of one bigg server, we deploy multiple smaller servers, each handling a subset of requests. This is more cost-effecient and effective, but introduces way more complexity to our systems.

How do we distribute incoming requests across these servers ? LoadBalancer ?? HELL YEAHHH !!!

Load Balancers

So you choose horizontal scaling and there are many servers to which 100's of requests can be passed on . But what if a server ends up recieving more requests than others ?

To manage the request we use load balancers to distribute requests among the servers so that no signle server can get huge number of requests. If any of the server is down load balancer will only redirect traffic to healthy servers

Load Balancer Algorithms : there are several algorithms to distribute the traffic to the healthy servers.

Least Connection : Sends request to server with the fewest active connections. By continuously monitoring the number of active connections on each server, this algorithm adapts in real-time to shifting traffic patterns and workloads, making it particularly effective when handling sessions or tasks that require varying processing times.
Round Robin : This algorithm cycles through a list server sequentially, each server is assigned a request in turn, ensuring an equal distribution of traffic over time. While this algorithm does not take into account the current load or capacity of individual servers, it works well in scenarios where all servers have similar processing capabilities and are equally equipped to handle requests.

There are many more interesting topics related to Load Balancing for example, What is IP Hashing technique ?, What is StandBy Load Balancers ? all these will be covered in the blog Do you know Load Balancers well ??

Everything is going fine we have a large user base, a load balancer which can redirect traffic . But we get to notice there are request for the same data from our database. Can we optimize it ?? Can we do something to make client not wait much for response from our db ?? HELL YEAHHH !!

Caching

For a general context caching is like keeping frequently used items on your desk instead of fetching them from a storage room. Caching stores frequently accessed data in a temporary, high-speed storage layer, reducing latency and improving performance by minimizing redundant computations or database queries. It enhances scalability and user experience, it reduces database load and speeds up responses.

But with caching comes a problem of maintaining the data consistency of cache and the database, we should not source the data from cache if its not up-to-date with the database. What to do now ?? How are we going to update both the source of data and the cache ??

Time Based Expiration : Cache entries are invalidated after a set time period (Time-to-Live), ensuring data is refreshed periodically
Write Through : Data is written to the cache and backend simultaneously, ensuring consistency but with higher write latency.

We also have many interesting topics to cover for more about Caching invalidation strategies and Cache Eviction Policies which we will cover in upcoming blogs !!

Now, LeetSys's users are spreading across the globe, and those in distant regions experience latency because our server are in the data center, we need to bring content closer to users.

Content Delivery Networks (CDNs)

To reduce latency, we integrate a Content Delivery Network (CDN). CDNs are networks of geographically distributed servers (edge servers) that cache static content like images, videos, and CSS files closer to users. When a user in Tokyo accesses LeetSys, the CDN’s Tokyo edge server delivers cached content, reducing the round-trip time to our main servers in the India CDNs rely heavily on caching

For now this is what our system has been evolved too, from a single client server request

Time to focus on our Database, becuase there are many things to store now !! There are often questions asked when to choose SQL databases and when to choose NoSQL database ?? But first lets get through each of them to know in-depth

Structured Query Language (SQL)

SQL databases like PostgreSQL, Oracle, MySQL, which organizes data into tables with defined schemas, these database excel at structured data and complex queries. SQL databases scale vertically which means we need to upgrade our machine power to scale databases like this. If you had to change or add a new column the changes need to be applied to all the records in the table.

SQL has Rigid schema which will struggle with massive, unstructured data like user activity logs. For this lets explore NoSQL databases

NoSQL

NoSQL databases like MongoDB are schema-less, allowing flexible storage for documents, JSON-like for our user activity logs. They scale horizontally better than SQL but sacrifice some ACID rules for better availabiity and performance.

There are majorly 4 types of NoSQL databases

Key Value Stores : These databases store data as key-value pairs, making them highly efficient for simple lookups and caching ex : Redis, DynamoDB
Document Stores : These database store data as documents (often in JSON or BSON format), allowing for flexible schemas and nested structures. Ex : MongoDB, Firebase Firestore
Column Family Stores : These database organize data into columns rather than rows, optimized for large scale data and high write/read performance. ex : Apache Cassandra

What to choose and when to choose ??

If you want strong consistency, reliability with highly structured data and consistent schema go for SQL like PostgreSQL, Oracle Database

but

If your data semi-structured, unstructured or has a dynamic schema also you want high performance with simple queries which also horizontally scales to handle massive amounts of data and high traffic you can go for NoSQL like Cassandra or Neo4j

As our user base grows we can notice a slow query performance from our backend, What to do in this situation ??

Database Indexing

Whenever there is a query our algorithm is consistently looking up from the whole database content which is making our response slow, for this we introduce Database Indexing all the primary key, or username can be indexed at a place which will help speeding up our database lookups pointing the actual location of the data.

There's a point to which we can scale our database but after that threshold point, how we will be scaling our database to meet the requirements for our growing user base ??

Data Partioning

When the database can no longer scale vertically then we perform data partitioning which is a technique to breakdown large databases into smaller components which enhances the performance, availabiity and load balancing as our application grows

There are mainly 4 major ways of breaking down a large database

Horizontal Partitioning : Also known as Sharding in this the data is divided by rows, meaning each partition contains a subset of rows from the dataset. Its ideal for large datasets where different subsets of rows can be stored on separate nodes
Vertical Partitioning : Data is is divided by columns, meaning each partition contains a subset of columns from the dataset, its useful when certain columns are accessed more frequently than others, allowing us to separate "Hot" (frequently accessed) and "Cold" (less frequently accessed) data. Vertical partitioning also simplifies schema design by grouping related attributes.

So these are the to begin our journey with system design, more often you practise questions you get to know more and more topics differenc between HLD [High Level Design] and LLD [Low Level Design]also you will get to know topics like micro services, distributed systems and more. I may write blogs on topics like this but I am leaving it to the future decesions.

This is what are system has evolved into with large user base, load balancers, cache to our web servers and database with partitioning

Hope I was able to add value to your today's learning goal !! Happy Learning ..

Flash Attention from a Beginners POV

Mrinal — Invalid Date

Pre-Requisites to know [Click on the topic header of these below to make it collapse or expand]

Attention : [Link]
- Complete the attention blog to get an idea why even Multi-Head is needed. Its like a homework you can do to understand better about the topic of this blog.
Articles you should go through once : [Link]
- Go through these articles after or before reading this blog, its up to you anon !!
Tile Matrix Multiplication : [Link]
- Study Anon !!

Flash Attention from a Beginner's Point of View

23rd March, 2025

Transformers are amazing, right? Their attention mechanisms like self-attention and multi-head attention make them super powerful for understanding context in text, translations, and more. But there’s a catch: traditional attention can be a memory hog and slowpoke, especially when dealing with long sequences. Enter Flash Attention, a clever optimization that makes attention faster and more efficient without sacrificing accuracy. Let’s dive in!

This is just merely part I of what Flash attention is in upcoming parts of Flash attention we will be diving deeper into flash attention internals and implementation in pytorch

What is Flash Attention and Why is it Needed?

Attention, as we know, computes a weighted sum of values (V) based on how relevant each key (K) is to a query (Q). The problem? For a sequence of length N, the attention mechanism needs to create an N × N attention score matrix. That’s a lot of memory! For example, if N = 10,000 (think a long document), you’re storing 100 million numbers just for that matrix. GPUs, which power these models, choke on this because they have limited memory, and moving data back and forth slows everything down.

Flash Attention is a way to compute attention without ever fully building that giant N × N matrix in memory. Instead, it processes the data in smaller chunks (or "tiles") and does the math on-the-fly. It’s like solving a puzzle piece by piece instead of laying out the whole picture at once. This saves memory, speeds things up, and lets Transformers handle much longer sequences—like entire books—without crashing.

Why is it Needed?

Memory Efficiency: Traditional attention’s memory usage grows quadratically (N²), while Flash Attention scales linearly (N).
Speed: It reduces redundant data movement between GPU memory layers.
Scalability: It unlocks Transformers for super-long sequences (e.g., 64k tokens instead of 512).

How Does Flash Attention Work?

Let’s break it down :

Compute the dot product of Q and K to get the attention scores (N × N matrix).
Scale and apply softmax to turn scores into weights.
Multiply those weights by V to get the output.

Flash Attention says, “Why store that huge score matrix?” Instead, it:

Splits Q, K, and V into smaller blocks (like cutting a big cake into slices).
Computes attention for one block at a time, using a technique called tiling.
Updates the output incrementally, keeping only what’s needed in memory.

Here’s the trick: it avoids storing the full attention score matrix by recomputing intermediate results when necessary and using clever math to keep the softmax accurate across blocks. This happens entirely on the GPU’s fast memory (SRAM), skipping the slower main memory (HBM).

Step-by-Step:

Input: Q, K, and V matrices (say, each is N × d, where d is the embedding size).
Tiling: Break them into smaller chunks (e.g., blocks of size B × d, where B << N).
Inner Loop: For each block of Q, compute attention with all blocks of K and V, but only store tiny temporary results.
Softmax Trick: Use a running normalization to combine results across blocks without ever needing the full matrix.
Output: Build the final attention output block-by-block.

The result? Same output as regular attention, but way less memory and faster computation.

Mathematical Representation

Let’s keep it simple but precise. Regular attention computes:

Attention(Q, K, V) = softmax(^{QK^T}_{√d_k})V

Where:

\( Q, K, V \in \mathbb{R}^{N \times d} \) (N = sequence length, d = dimension).
\( QK^T \in \mathbb{R}^{N \times N} \) (the big, problematic score matrix).

Flash Attention avoids materializing \( QK^T \) fully. Instead:

Split \( Q \) into blocks \( Q_1, Q_2, ..., Q_m \) (each \( B \times d \)).
Split \( K \) and \( V \) similarly into \( K_1, K_2, ..., K_m \) and \( V_1, V_2, ..., V_m \).
For each block \( Q_i \):
- Compute \( S_i = Q_i K^T \) (small \( B \times N \) matrix).
- Scale: \( S_i / \sqrt{d_k} \).
- Apply softmax incrementally, tracking running sums and normalization constants.
- Compute \( O_i = \text{softmax}(S_i)V \) and add to the output.

The magic is in the incremental softmax, which uses two extra variables (a max and a sum) to stitch everything together accurately without the full matrix.

With Flash Attention, the operator is smarter. They only look at one section of the stage at a time (a block), figure out who’s important in that moment, and adjust the spotlight right away. They keep a tiny notepad (fast GPU memory) with just enough info to move to the next section. The play (computation) goes on smoothly, and the audience (model) still sees the full story—no one notices the operator’s trick!

Flash Attention in the Transformer Architecture

Flash Attention fits right into the Transformer’s attention layers:

Encoder: Replaces self-attention with Flash Attention to process input sequences efficiently.
Decoder: Handles masked self-attention (for previous tokens only) and cross-attention (connecting to the encoder) with the same block-wise trick.

It’s plug-and-play: same Transformer, just faster and leaner.

Why Is Flash Attention a Big Deal?

Longer Sequences: Models can now process tens of thousands of tokens (e.g., 64k) instead of hitting a wall at 512 or 1024.
Energy Savings: Less memory movement = less power, which matters for big AI training runs.

Intuition: Flash Attention as a Spotlight

Remember our theater analogy? In regular attention, the spotlight operator (Attention) scans the entire stage (all tokens) at once, writing down a huge list of who’s important (the N × N matrix) before deciding where to shine the light. With a big stage, that list gets unwieldy, and the operator runs out of paper (memory).
With Flash Attention, the operator is smarter. They only look at one section of the stage at a time (a block), figure out who’s important in that moment, and adjust the spotlight right away. They keep a tiny notepad (fast GPU memory) with just enough info to move to the next section. The play (computation) goes on smoothly, and the audience (model) still sees the full story—no one notices the operator’s trick!

Multi-Head Attention from a Beginners POV

Mrinal — Invalid Date

Pre-Requisites to know

Attention : [Link]
- Complete the attention blog to get an idea why even Multi-Head is needed. Its like a homework you can do to understand better about the topic of this blog.
Dot Product Attention
- > Dot Product attention is a specific type of attention mechanism that computes attention scores using the dot product between vectors.
- > Computing the dot product between each query vector \(\text{Q}\) and each key vector \(\text{K}\). This gives a raw measure of similarity between the query and the keys. \[\text{Raw Scores} = \text{Q} \cdot K^T\]
Emeddings
- > Embeddings are a way to transform raw input data—like words, tokens, or symbols—into dense, continuous vectors of numbers that a machine learning model can understand and process. Here embeddings are crucial because they provide the starting point for computing Queries (Q), Keys (K), and Values (V), which drive how the model focuses on different parts of the input.
Dimensionality
- > It refers to the number of features, attributes, or components used to represent data in a mathematical space. In simpler terms, it describes how many "dimensions" or variables are present in a dataset or a vector for a machine to learn.
Softmax Function
- > Softmax is a mathematical function which converts a vector of real-valued numbers into a probability distribution, where the values are non-negative and sum to 1. This makes it ideal for scenarios where you need to assign probablities to multiple classes to options.

Multi-Head Attention from Beginners POV

In Transformers, Multi-Head Attention takes the same Query (Q), Key (K), and Value (V) inputs as single-head attention but splits the work across multiple “heads.” Each head focuses on different aspects of the input—like grammar, meaning, or context—and together, they give the model a more nuanced understanding. It's the secret sauce behind why Transformers are so good at everything from translation to generating text like this!

This is how Multi-Head Attention works inside, we will discuss everything about this diagram later in this blog. For now lets cover a main topic which is

Why "Scale" the Dot Product ?

In the original dot-product attention, the raw scores can become very large if the dimensionality of the query and key vectors \( (d_k)\) is high. This can cause the softmax function to produce extremely small gradients, leading to numerical instability during training.

To address this issue, the scaled dot-product attention introduces a scalling factor

\[\text{Attention{Q, K, V}} = \text{softmax} \left(\frac{Q \cdot K^T}{\sqrt{d_k}}\right) \cdot V\]

Here, \( (d_k)\), is the dimensionality of the key vectors. Dividing by \(\sqrt{d_k}\) ensures that the dot product are scaled appropriately, preventing the softmax function from saturing

After all this you might get up with a question

Why Multi-Head Attention ?

Single head attention is great, but it's limited. It computes one set of attention weights and mixes all the information into single output. That's like trying to hear every instrument in symphony with one ear it works, but you miss the layers. Multi-Head Attention says, "Why settle for one prespective?" By running attention multiple times in parallel. each with its own lens (or "head"), the model captures diverse relationships in the data-like how " it" refers to "cat" in one head, while another head notices the verb tense.

Plus, its still parallelizable (unlike RNN's), so its fast. More heads = more insights, without slowing things down. Genius, right ?

Now one would wonder if Multi Head Attention helps so much, how does it work under the hood ? So lets start with our second most important topic which is

How Does Multi-Head Attention Work ?

Let’s get into the nitty-gritty. Here’s the step-by-step breakdown, with all the crazy details:

Start with Q, K, V

We've got your input sequence turned into embeddings (say a matrix (X) of shape \(\text{batch_size} \times \text{sequence_length} \times d_{\text{model}}\))
From (X), we can compute \[Q = X \cdot W_Q \] \[K = X \cdot W_K\] \[V = X \cdot W_V \]
Here, \(d_{\text{model}}\) is the embedding size (e.g., 512 in the original Transformer). Each (W) is a learned weight matrix

Split Into Heads

Instead of using the full \(d_{\text{model}}\) dimensional vectors, split them into (h) heads (e.g h=8)
Each Head gets a smaller chunk of the dimensions: \(d_k = d_v = d_{\text{model}} / h\) (e.g., 512 / 8 = 64)
For each head (i):
\[Q_i = X \cdot W_Q^i\] (shape: \(\text{batch_size} \times \text{sequence_length} \times d_k\))
\[K_i = X \cdot W_K^i\] (shape: \(\text{batch_size} \times \text{sequence_length} \times d_k\))
\[V_i = X \cdot W_V^i\] (shape: \(\text{batch_size} \times \text{sequence_length} \times d_v\))
Each \(W_Q^i, W_K^i, W_V^i\) is a slice of the original weight matrices, tailored to that head

Run Attention per Head

For each head (i), compute Scaled Dot-Product Attention:
\[\text{head}_i = \text{Attention}(Q_i, K_i, V_i) = \text{softmax}\left(\frac{Q_i \cdot K_i^T}{\sqrt{d_k}}\right) \cdot V_i\]
Each head produces an output of shape \(\text{batch_size} \times \text{sequence_length} \times d_v\)
So, with (h) heads, you get (h) different outputs, each capturing a unique perspective

Concatenate the Heads

Stack all the head outputs side-by-side:
\[\text{MultiHead}(Q, K, V) = \text{Concat}(\text{head}_1, \text{head}_2, ..., \text{head}_h)\]
Shape becomes \(\text{batch_size} \times \text{sequence_length} \times (h \cdot d_v)\), which matches the original \(d_{\text{model}}\) (e.g., \(8 \cdot 64 = 512\))

Final Linear Transformation

Run the concatenated output through a learned linear layer to mix the heads’ insights:
\[\text{Output} = \text{MultiHead}(Q, K, V) \cdot W_O\]
\(W_O\) (shape: \(h \cdot d_v \times d_{\text{model}}\)) ensures the output shape is \(\text{batch_size} \times \text{sequence_length} \times d_{\text{model}}\), ready for the next layer

The Math, Condensed

Here’s the full formula:

\[\text{MultiHead}(Q, K, V) = \text{Concat}(\text{head}_1, ..., \text{head}_h) \cdot W_O\]

where:

\[\text{head}_i = \text{softmax}\left(\frac{(X \cdot W_Q^i) \cdot (X \cdot W_K^i)^T}{\sqrt{d_k}}\right) \cdot (X \cdot W_V^i)\]

For self-attention, (Q, K, V) all come from the same (X)
For cross-attention (e.g., in the decoder), (Q) might come from the decoder, and (K, V) from the encoder

Okkay now we are heading to the part which everyone liked in the previous blog. Yupp the INTUITION. Sorry if I cannot carry up the hype, but I will try my best <3

Intuition : (Heist Edition)

Your are a Detective | 刑事

There has been a recent Bank Heist in your nearby bank and you are piecing together the details of the heist : The thief escaped after the guard dozed off. With single-head attention, you are like one detective with a flashlight, sweeping the crime scene and connecting clus. You might lock onto "thief" and "escaped" but miss how "guard" and "dozed off" set the stage for the getaway !!

Now Multi Head attention steps in like a team of detectives, each with their own flashlight and intelligence

Detective 1 : Focuses on the players (“thief” → “guard”). Who’s involved? They spot the key characters in this drama.
Detective 2: Tracks the action and timing (“escaped” → “dozed off”). When did it happen? They link the verbs to figure out the sequence.
Detective 3: Sniffs out the cause-and-effect (“after” ties it all together). Why did it work? They catch the sneaky logic of the heist.

The result? A richer, multi-layered picture of the heist—way more detailed than what one lone detective could crack on their own.