DEV Community: Avash_Mitra

The Technical Breakdown: Slack's Near-Miss Database Overloado

Avash_Mitra — Fri, 12 Jan 2024 19:23:20 +0000

In the sphere of real-time communication, Slack stands out as a pivotal platform for corporate connectivity and collaboration. However, on October 12, 2022, the system's reliability was put to the test. The Datastores team, responsible for overseeing Slack's database clusters, encountered a significant challenge — a sudden increase in the number of failed database queries pointed to an underlying issue that required immediate attention.

Incident Onset and Immediate Response

During an onsite in Amsterdam, the Datastores team, freshly augmented with new engineers, was alerted to a troubling rise in database query failures. An investigation revealed the cause: a long-running asynchronous job was purging substantial amounts of data, leading to an overload on the database cluster. To mitigate this, the team executed a temporary solution known as 'shimming,' which allowed ongoing jobs to complete while halting the initiation of new processes.

Recurrence and Escalation

The remedy seemed effective until the very next day when the problem resurfaced with greater severity. This incident shed light on an edge-case bug within Datastores' automation, which had failed to manage a surge in requests, directly affecting customer access to Slack. The team responded by disabling certain features to alleviate the load on the cluster, which provided the necessary room for recovery.

Slack's datastore stratergy

Before discussing the trigger and the cascading effects of the incident, it is essential to understand Slack's datastore strategy, which is at the core of its operational integrity. Slack's data architecture is built around Vitess, a database clustering system for horizontal scaling of MySQL. By employing Vitess, Slack effectively shards its extensive dataset across multiple MySQL instances. This not only allows for more efficient data management and retrieval but also ensures that operations can continue seamlessly even if one shard encounters an issue. Each shard contains a portion of the database and operates in conjunction with replicas to balance the load and facilitate quick data access. This setup is designed to maximize uptime and performance, a necessity for a platform supporting millions of concurrent users. The strategic use of sharding and replication is central to Slack's ability to scale dynamically and maintain robust data integrity, even as user numbers and data volumes continue to grow.

The Trigger and Subsequent Measures

Upon further analysis, the team identified that the incident was triggered by a customer removing a large number of users from their workspace, an operation that initiated a cascade of data modifications beyond the usual scope. To address the immediate issue, the Datastores team manually provisioned larger instance types for replicas, circumventing the automated systems that were not equipped to handle such an anomaly.

Long-Term Solutions and Preventative Actions

Moving forward, the Datastores team has adopted several strategic measures to prevent a recurrence. They have implemented throttling mechanisms and the circuit breaker pattern, both of which serve as safeguards against query overload. These measures enable the team to proactively limit or cancel queries to affected shards, thereby maintaining database stability.

In addition, to address the specific challenges posed by the 'forgetUser' job, which was central to the incident, the team optimized the job's performance. They streamlined the process to reduce the load on the database during large-scale user removal operations.

Conclusion

The incidents of October 2022 highlighted the intricate balance required in managing large-scale, distributed databases. The Datastores team's adept response and the subsequent refinements to their systems underscore the continuous need for vigilance, adaptability, and innovation in database management. As a result of these efforts, Slack's infrastructure has been fortified, showcasing a commitment to resilience and the uninterrupted service that users rely on.

5 database engines you should know about

Avash_Mitra — Fri, 07 Apr 2023 15:12:52 +0000

We will discuss different types of engines, their use cases, pros and cons, and much more.

Database engines, also referred to as storage engines, are software programs that handle CRUD (Create, Read, Update, Delete) operations and disk storage for databases. While some are simple and only manage storage and CRUD, more complex engines offer advanced features like ACID support and transactions. Database systems build their functionalities on top of these engines.

In this discussion, we will explore various types of database engines, their use cases, and their pros and cons, to provide comprehensive insights into the world of database engines.

MyISAM

Written in C, MyISAM was the first database engine for MySQL.

ISAM stands for Indexed Sequential Access Method. In this engine every index that we create points to a row. It uses B-tree for indexing.
Since every index points to a row, read operations are fast. Even the insert operations are fast because we are appending the new record to the end of the file and we always know where the end of the file is. However, the main issue is with the update and delete operations. When we update/delete existing rows, we change the row size, this changes the offset and all the index pointers need to change. This is expensive.
It provides no Transaction support.
Database crashes corrupt tables and has to be manually repaired.
It only provides table-level locking. If you want isolation you just have to lock the entire table.

InnoDB

It replaced MyISAM as the default database engine of MySQL and MariaDB.

In this engine, the B+ tree is used for indexing. Each index points to a primary key and each primary key points to a row. If there is no primary key then the engine makes one for you.
It supports transactions and therefore implements ACID features.
It also allows row-level locking so you don’t need to lock your entire table. This makes query processing faster.
It also introduces a lot of new features like foreign keys, tablespaces, and spatial operations.

SQLite

It was designed by Dwayne Richard Hipp and written in C language

It is one of the most widely used embedded databases and is used in web browsers, mobile applications, operating systems, etc.

It used B-Tree for indexing.
It allows all ACID features
It allows table-level locking. It does not need row-level locking because it is usually used locally and there is only a single user.
It allows concurrent reads and writes.

LevelDB

It was designed by two Google engineers Jeffery Dean and Sanjay Ghemawat and written in C++ language. It was inspired by Google BigTable.

It is not a SQL database. It does not have a relational database model and does not support SQL queries.
It used Log-Structured Merge Trees for indexing. It works great for high insert volume. (unlike B tree that may need to rebalance itself after insert which makes insert operations slow)
It does not allow transactions.
It is single-threaded
There are levels of files and as the file grows large, levels are merged.
They also support Write Ahead Logs to ensure durability.

RocksDB

It is a fork of Google’s LevelDB and is further developed by Facebook. It is used as MyRocks for MySQL, MariaDB, and Percona. It is also used by MongoRocks for MongoDB.

Similarities with LevelDB

It also uses Log structured merge trees
It is also key-value pair storage and does not support SQL queries.

New features added to RocksDB

It allows transactions.
It also used multi-threading to improve performance.
Other features include Geospatial indexing, Bloom filters, merge operators, etc.

In conclusion, understanding different types of database engines and their use cases can greatly impact the performance and functionality of your database system. Each engine has its own strengths and weaknesses, making it crucial to choose the right one based on your specific requirements.

MyISAM, the first MySQL database engine, provides fast read and insert operations but lacks transaction support and may be prone to table corruption.
InnoDB, the default MySQL and MariaDB engine, offers ACID compliance, row-level locking, and advanced features like foreign keys and spatial operations.
SQLite, a popular embedded database, is widely used in web browsers, mobile applications, and operating systems, providing ACID features, table-level locking, and support for concurrent reads and writes.
LevelDB, inspired by Google's BigTable, is a non-SQL database with Log-Structured Merge Trees for indexing, making it ideal for high insert volume but lacks transaction support and is single-threaded.
RocksDB, a fork of LevelDB, adds features like transactions, multi-threading, and geospatial indexing, making it suitable for MySQL, MariaDB, Percona, and MongoDB.

Choosing the right database engine depends on your specific use case, performance requirements, and desired features. It is essential to carefully evaluate and compare different engines to make an informed decision and optimize your database system for efficiency and reliability.

Memcached at Scale: How Facebook Scaled and Optimized for Massive Request Volumes

Avash_Mitra — Thu, 06 Apr 2023 14:35:17 +0000

Facebook, one of the world's largest social media platforms, handles billions of requests per second and stores trillions of key-value pairs. To manage this scale, Meta uses Memcached, a simple Key-Value cache that stores data in memory. Since users consume a lot of content than they create caching had significant advantages. It reduced latency, reduced load on database servers, and much more. In this blog, we'll explore Meta's strategy for scaling their Memcached clusters to handle their high demand and discuss optimizations in these areas to improve performance and storage.

Optimizing clusters and regions of Memcache servers.
Optimizing a single Memcached server

Optimizing Clusters to Reduce Latency for Memcached

When scaling to thousands of servers per cluster, we run into some interesting problems

Increased latency due to the distributed nature in which the data is stored. Since each web server has to get the data from multiple cache servers, the latency increases.
Thundering Herd can occur when there is a cache miss and can severely affect the database servers.
Cascading failures can happen when one Memcached server goes offline and it puts additional strain on other servers
Users might get stale data if the cache invalidation method is not optimal.

So let's discuss how to solve each issue in detail

Reducing Latency by using TCP for Set and Delete, and UDP for Get Requests

For GET requests, we use UDP.
- Unlike TCP, UDP is connectionless (No connection needs to be established between the source and destination before you transmit data), so it reduces latency and overhead.
- Also, for GET requests, web servers can directly connect to the Memcached server (instead of connecting through the proxy). This further reduces the overhead.
- NOTE: We can use UDP for GET requests because GET requests do not change the state of the cache. So even if the request fails (which might happen because UDP is unreliable) it won't cause data inconsistency.
FOR SET and DELETE requests, we use TCP
- Since UDP is unreliable, we use TCP to perform these operations. Also, these requests are routed through the proxy.

Parallelizing and Batching Requests to reduce latency

To reduce latency, we need to minimize the number of round trips for fetching the data. To do so, we can parallelize the requests. But some data are dependent on other data i.e., we need to fetch the 'parent' data and use it to fetch the 'child' data (look at the example below). So, a Directed Acyclic Graph can be constructed. Now, for the data points that do not have any dependencies, we can send parallel requests to fetch them.
Ex:

Preventing Congestion

Sending a lot of requests parallelly can cause congestion. This can slow down responses, increase load on the Memcached servers, and in the worst case the server can crash. To prevent this from happening, the number of outstanding requests must be controlled. To do so, web servers use a sliding window.
In a web server, there is a sliding window for each Memcached server. If the request was successful, the sliding window size increases, but if the request failed it shrinks.
When the window size is very small, the web server has to wait more before sending a request and when the window size is very large the number of parallel requests can cause congestion. So the balance between these two extremes is where we prevent congestion and minimize latency.

Optimizing Clusters to Reduce Load on Servers

Reducing Load (on Databases) using Leases

This is one of my favorite techniques in this entire blog. This mechanism not only reduces load (and thereby prevents thundering herds) but also addresses the issue of stale data and is quite intuitive. But before discussing the solution let's understand in what scenario will the load on database servers increase.

Suppose 1000 web servers requested a key, but it is missing. Now all 100 web servers make requests to the database server. Now the database server has to 1000 servers at once which can cause it to crash. We call this scenario Thundering Herd.
Stale data can be added to the cache due to race conditions. Have a look at the illustration below to understand how it happens

A lease is a 64-bit token that is associated with a key. When there is a cache miss, a lease is assigned to the web server that experienced the cache miss.

The Memcache server regulates the rate at which it assigns a lease token (usually 10 seconds). So, within 10 seconds if any other web server requests for the key, they get a special responsibility to wait for a short amount of time. This prevents Thundering Herd because instead of sending requests to the database, now the web servers wait for the cache to be updated with the required value.
Only those servers can update the cache that has the lease token. If the data value is updated in the database, then the key is invalidated in the cache and so is the lease token. In that case, a new token is assigned to the servers that experience cache miss. So we can be ensured that only the latest value is added to the cache. Therefore it also solves the stale data issue.

Assigning different Pools for different types of data

Different types of data have different access patterns, memory footprints, and quality of service requirements. They can negatively affect each other so they are assigned different server pools.

E.g. A small pool of Memcached servers can be assigned for the keys that are accessed frequently but a cache miss is cheap (A smaller pool means less time is required to search the key) and a large pool for keys that are accessed infrequently but a cache miss is expensive.

Distributing Read Requests across the Replicas

We can create replicas of the Memcached servers within the same pool and replicate the keys. Now when we get read requests, we can distribute them across all the replicas. This reduces the load from the main Memcached server.

Preventing Cascading Failure

In a distributed system, servers going offline is a norm rather than an exception. To mitigate outages a small set of servers known as Gutter is used. It is just a Memcached server that is only used when any other Memcached server is offline. When the server sends a request to the Memcached server but does not receive any response, it assumes the server is offline and sends the request to the Gutter Pool.

There is another approach, where the key is rehashed and assigned to another server. This is not preferred because it can cause a cascading failure.

Image credits: https://interviewready.io/blog/ratelimiting

For instance, if a highly requested key is assigned to another server, then it might overload that server and crash it. Now, again it'll be assigned to a different server and repeat the same thing as above.

It'll continue until many servers crash due to overload, so using Gutter servers is a better option.

Improving Performance by using regions of Memcached servers

There is an upper limit to how many servers we can add to a cluster before the congestion worsens. Therefore it is better to split the web and Memcached servers into multiple frontend clusters. These clusters, along with a storage cluster that contains the databases, define a region.

Making regions of Memcached servers has many benefits like reduced latency because the servers are near the end users. It also mitigates the effects of large-scale power outages, natural calamities, etc. This makes the system more reliable and available.

Removing stale data from Memcached servers in different regions

A single key-value pair may be replicated to multiple Memcached servers in different regions. So, when the data is updated in the database, we have to invalidate the data from those servers. To do so, the following procedure is followed

SQL statements that modify the state have the required Memcached keys embedded in them.
Each database server also has an invalidation daemon called McSqueal. It analyzes the SQL statement, extracts the keys, and broadcasts the updates to different regions.
McSqueal also batches requests to reduce the number of data packets. These packets are then unpacked by the Memcached proxy (Mcrouter).

Optimizing a single Memcached server

A single server can easily become the bottleneck, so it is important to optimize the Memcached server.

Using Adaptive Slab Allocator for Better Memory Management

Allocating and Deallocating memory randomly causes Memory Fragmentation.

Memory fragmentation is when the sum of the available space in a memory heap is large enough to satisfy a memory allocation request but the size of any individual fragment (or contiguous fragments) is too small to satisfy that memory allocation request

It increases the read time as the memory gets more and more fragmented. To prevent this, Memcachedpre- allocates a large chunk and divides it into slab classes. The size of slab classes starts from 64 bytes up to 1MB. It stores the data in the smallest possible slab that can fit the data item.

Each slab class maintains a list of available memory and requests for more memory when this free list is empty.

Now, it is worth noting that there might be some wastage of memory inside a slab if the data item is smaller than the slab size (it is called internal fragmentation). But it does not degrade the performance as much as external fragmentation.

Choosing the right eviction policy

Memcached uses LRU (Least Recently Used) eviction policy. Each Slab class has its own LRU data structure (generally we use a linked list). When it cannot allocate any more memory in a slab, the least recently used (in other words, the oldest items) is evicted from the slab class.

This approach has one issue - The eviction rate across slab classes is unbalanced. This can cause performance issues as one slab is constantly evicting and adding data items, while other slabs are not being used. To prevent this, it is important to identify the slabs where the eviction rate is high and the evicted keys can be assigned to other slabs.

So, if a slab class is evicting a data item and it was used at least 20% (this a threshold) more recently than the average of least recently used items in other slab classes, then the data item is moved to any other class.

Reducing Memory Usage by removing short-lived keys

Memcached evicts an item

When the expiration time of the item has exceeded while serving a GET request.
Or, when the item has reached the end of LRU

In short, it removes the data items lazily. Short-lived keys that see a single burst of activity waste memory, until they reach the end of LRU.

To solve this issue, a hybrid method is used to lazily evict most keys and quickly evict short-lived keys when they expire. All the short-lived items are placed in a circular buffer of a linked list. We have a head pointer that iterates over the circular buffer and advances by one each second. Each second, all of the items in the bucket at the head pointer are evicted and the head pointer advances by one.

Using Multi-threading to boost performance

The Memcached server is multi-threaded to boost performance.

To prevent race conditions, a global lock is used to protect the data structures.
If a single port is used to connect to web servers, then it can easily bottleneck the whole server, so each thread is given its own UDP port.

In conclusion, Meta's strategy for scaling their Memcached clusters to handle their high demand involves optimizing clusters and regions of Memcached servers as well as optimizing a single Memcached server. They use techniques such as using TCP for Set and Delete requests, UDP for Get requests to reduce latency, parallelizing and batching requests to minimize round trips, and preventing congestion using a sliding window mechanism. They also use leases to reduce the load on databases and prevent thundering herds, and implement cache invalidation methods to address stale data issues.

These optimizations not only help reduce latency and load on servers, but also prevent cascading failures, thundering herds, and stale data issues, resulting in improved performance and storage for Meta's Memcached clusters. With these strategies in place, Meta can handle billions of requests per second and store trillions of key-value pairs, efficiently serving content to their users and maintaining a seamless user experience on their social media platform.

References

Memcached White Paper: https://www.usenix.org/system/files/conference/nsdi13/nsdi13-final170_update.pdf

Memcached architecture crash course: https://www.youtube.com/watch?v=NCePGsRZFus

Making a Dynamic Renderer with Golang from Scratch

Avash_Mitra — Tue, 07 Mar 2023 15:01:06 +0000

Understanding Dynamic Rendering: Why It Matters for Your Website's SEO

When it comes to building a website, the three key components are HTML, CSS, and Javascript. In recent years, client-side rendering (CSR) has become increasingly popular. With this approach, the browser downloads an empty HTML shell and uses Javascript to generate the content on the client side.

[Image credits: web.dev ]

However, while CSR may work well for users, it creates a significant problem for search engines and other bots. Bots rely on the generated HTML content to gather data and index your website. But when a bot visits a client-side rendered page, there is no data available because the Javascript hasn't been executed yet. As a result, the bot only sees an empty website, which can severely impact your website's SEO.

That's where dynamic rendering comes in. Dynamic rendering is the process of rendering a fully formed HTML page on the server side and sending it to bots, while still using client-side rendering for users. This approach allows bots to access the fully rendered HTML content and gather the data they need to index your website, without affecting the user experience.

In this article, we'll explore dynamic rendering in more detail and show you how to build a dynamic renderer using Golang, a powerful and efficient programming language, from scratch. With this knowledge, you'll be able to create high-performance web applications that not only deliver a great user experience but also rank well in search engines.

But do I even need Dynamic Rendering?

Well, that depends.

❌ You don't need dynamic rendering when -

If you are working with meta frameworks like NextJS, NuxtJS, Remix, etc. Because these are server-side rendering applications.
If your codebase is small and you can migrate it to server-side rendering applications

✅ You need dynamic rendering when

When your codebase is huge and you don't have the bandwidth to migrate it to server-side rendering applications. Also, you want to improve your website as soon as possible.

But keep in mind,

Dynamic rendering is a workaround and not a long-term fix for problems with javascript.

Implementing Dynamic Rendering

Let's first discuss the high-level overview, before jumping into the code.

Since we need to render the HTML before sending it to the bot, we need a server.
We will define a middleware, it intercepts the request made to the web app.
We will use the user agent to check if the request was made by a bot or a user.
If the request was made by a user, we send the client-side rendered app.
But if the request was made by a bot, we generate the HTML content (with something like puppeteer) and then send the rendered HTML to the bot

Now that we are done with the high-level overview, let's jump into the implementation

Setting up server

For setting up the server, I will be using the Gin framework.



func main() {
    r := gin.Default()
    r.Use(our_middleware)

    r.Static("/", "./frontend/dist")

    if err := r.Run(":3000"); err != nil {
        log.Fatal(err)
    }
}

This starts our server at port 3000. Our CSR frontend files are present in the folder frontend/dist. Now when someone sends a request for a page, we serve HTML, CSS, and JS from this folder.

Now we need middleware to intercept the traffic. So let's implement it.

Adding a middleware



func dynamicRenderer() gin.HandlerFunc {
    return func(c *gin.Context) {
        // Check if request is from a bot
        isBot := checkforBot()
        if isBot {
          // render page and send the rendered page
            return
        }

        // If not a bot, continue to serve as usual
        c.Next()
    }
}

func main() {
    r := gin.Default()
    r.Use(dynamicRenderer())

    r.Static("/", "./frontend/dist")

    if err := r.Run(":3000"); err != nil {
        log.Fatal(err)
    }
}

Now that the middleware is set up, let's write the code for rendering the HTML file. But before that, we need to run our front end on some other port. Because the puppeteer scrapes data from the website. So let's write code to start the frontend

Serving the actual front end from another port



func main() {
    // code

    cmd := exec.Command("command","to","serve","your","frontend")
    cmd.Dir = "./frontend"
    cmd.Stderr = os.Stderr

    wait_for_files_to_be_served()

    if err := r.Run(":3000"); err != nil {
        log.Fatal(err)
    }
}

Writing the code for the renderer



func dynamicRenderer() gin.HandlerFunc {
    return func(c *gin.Context) {
        isBot := checkForBot()

        if isBot {
            // Connect to Puppeteer
            ctx, cancel := chromedp.NewContext(context.Background())
          // We cancel the connection once the response is sent
            defer cancel()

            // Navigate to the page and wait for it to load
            url := "http://localhost:" + reactPort + c.Request.URL.Path
            var html string

          err := chromedp.Run(ctx,
                chromedp.Navigate(url),
                chromedp.InnerHTML("html", &html, chromedp.NodeVisible, chromedp.ByQuery),
            )
            if err != nil {
                log.Println(err)
                c.AbortWithStatus(http.StatusInternalServerError)
                return
            }

            // Send back the rendered HTML
            c.Data(http.StatusOK, "text/html; charset=utf-8", []byte(html))
          // We are done serving
            c.AbortWithStatus(http.StatusOK)
        }

        // If not a bot, continue to serve the React app as usual
        c.Next()
    }
}

Here's a short explanation of what happening:-

Once we know it's a bot, we connect to the puppeteer.
We then navigate to the URL, using chromedp.Navigate(url) .
We wait for all the children of the HTML tag to load by using chromedp.NodeVisible
Once the javascript has generated all the HTML content we store it in html variable and send it to the bot.

Well, that's the entire implementation !! (sort of). I have left some boring parts out, but if you want you can check this repository.

Now, let's look at the result

Our webpage looks like this

When the user is requesting for a file, we get

But when a bot requests a file, we get

Notice that the HTML is all rendered.

NOTE: When we send a rendered page there is not JS. So it won't function. But for a bot that is not an issuse because it does not use JS in any way

Well that's all. Thanks for reading. If you have any doubt, you can post it it comment. I'll try my best to clear your doubts

Mastering Factory Design Patterns through the Construction of a Banking System

Avash_Mitra — Tue, 31 Jan 2023 01:39:35 +0000

First of all, let's define the

Requirements of our problem

There can be multiple banks
- All banks share some common attributes and behavior like
  - Behavior - showBalance() , withdraw() , addBalance() etc
  - Attributes - amount_left , num_of_users etc.
- Banks can also implement their unique methods and attributes
Provide a simple interface to the user for creating bank objects of their choice (i.e., users should now be responsible for)
Our solution should follow S.O.L.I.D. Principle

Having Multiple Banks

Let's start by defining two banks classes - A1 and A2

class A1 {
    private:
        int amount_left , num_of_users; // .. other params
    public:
        int NumOfUsers(){...} 
        // Other attributes
};

class A2 {
    private:
        int amount_left , num_of_users; // .. other params
    public:
        int NumOfUsers(){...} 
        // other attributes
};

Notice something wrong.

First of all, there is a ton of code duplication. Since there are a lot of common attributes and methods we will be writing, the same code again and again.
Secondly, there is no guarantee that all classes will define the common attributes and methods.

To solve these issues, we can define a common interface. This common interface will have all common attributes and methods. All other classes that implement this common interface will have to define the methods.

It solves the code duplication part, as we don't need to redefine the attributes and methods in the subclasses. (classes that implement the interface)
Any class that implements the common interface needs to define the methods.

Let's have a look at the code now.

class Bank{
    protected:
        int amount_left , num_of_users; // .. other common attributes
    public:
        virtual int NumOfUsers(){ // Subclass can redefine this
            return this->num_of_users
        } 
        virtual int getBalance() const = 0; //Subclass have to redefine this
};

class A1 : public Bank {
    private:
        int special_params;
    public:
       int getBalance() const override{...}
};

class A2 : public Bank {
    private:
        int special_params;
    public:
       int getBalance() const override{...}
};

Okay, now that this is taken care of, let's focus on the second requirement.

Provide a simple interface to the user for creating `a bank` objects of their choice

In our existing code, if a user wants to create a bank object then

void client(){
    A1* a1 = new A1;
    std::cout<<a1->getBalance(); 
}

Well, this doesn't look that bad, but we are exposing too much of our backend logic to the client. Ideally, the client shouldn't know about every subclass. We should be providing a centralized code for bank selection. Let's define a new class for this.

class BankCreator{
    Bank* getBankInstance(string bankName){
        switch(bankName){
            case "a1":
                return new A1;
            case "a2":
                return new A2;
            default:
                return NULL;
        }
    }
};

void client(){
    BankCreator* backCreator = new BankCreator;
    Bank* a1 = backCreator->getBankInstance("a1");
    Bank* a2 = backCreator->getBankInstance("a2");
}

NOTE: All the objects created by the BankCreator class should have a common superclass.

Now, this looks great. But do you notice something wrong with our code?

The BankCreator class violates the Open For Extension and Closed for Modification Principle.

When we are adding a new bank (subclass) we need to modify the BankCreator class (add another case to the switch statement).

So, we need to define the creator class in such a way that whenever we add/remove a bank subclass, we do so without modifying the creator class. To do this

We first make the creator a class an interface

         class BankCreator{
          protected:
              virtual Bank* getBankInstance() const = 0;
      };
    ```
{% endraw %}


* Now to add a new {% raw %}`bank`{% endraw %} we simply implement this interface

*
{% raw %}
 ```cpp
      class A1Creator: public BankCreator{
          Bank* getBankInstance() const override{
              return new A1;
          }
      };

      class A2Creator: public BankCreator{
          Bank* getBankInstance() const override{
              return new A2;
          }
      };
    ```
{% endraw %}


    Since we can add new bank subclasses without modifying the creator class, we can say that we are following the **<mark>Open For Extension and Closed for Modification Principle.</mark>**


Now a client can create a bank object in the following way
{% raw %}


```cpp
void client(){
    A1Creator* a1creator = new A1Creator;
    A1* a1 = a1creator->getBankInstance();
    A1* a11 = a1creator->getBankInstance();
}

Also, it might look like we are exposing too much of our backend logic, but that's not the case. The client is not concerned about the implementation of the concrete subclasses (bank subclasses) but is only aware of creator classes.

Before moving forward, here's the entire

Pseudo code for Factory Design Pattern

//This is an Abstract class. But you can also make it an interface 
class Bank{
    protected:
        int amount_left , num_of_users; // .. other common attributes
    public:
        virtual int NumOfUsers(){ // Subclass can redefine this
            return this->num_of_users
        } 
        virtual int getBalance() const = 0; //Subclass have to redefine this
};

class A1 : public Bank {
    private:
        int special_params;
    public:
       int getBalance() const override{...}
};

class A2 : public Bank {
    private:
        int special_params;
    public:
       int getBalance() const override{...}
};

class BankCreator{
      protected:
          virtual Bank* getBankInstance() const = 0;
};

 class A1Creator: public BankCreator{
      Bank* getBankInstance() const override{
          return new A1;
      }
  };

  class A2Creator: public BankCreator{
      Bank* getBankInstance() const override{
          return new A2;
      }
  };

void client(){
    A1Creator* a1creator = new A1Creator;
    A1* a1 = a1creator->getBankInstance();
    A1* a11 = a1creator->getBankInstance();
}

Now, let's discuss the pros and cons of this pattern

✅ Pros

It follows the Single Responsibility Principle.

The creator class and each concrete creator subclass have only one responsibility. Tldr, there is a segregation of responsibility.
It follows the Open For Extension and Closed for Modification Principle.
There is loose coupling

Instead of adding the logic to decide the type of object in the creator class, we are assigning the responsibility to some other class

❌ Cons

Code can become too complex.

Since we are adding a lot of subclasses.

Cover image credit: Image by storyset on Freepik

How do databases recover from failure?

Avash_Mitra — Sun, 29 Jan 2023 04:16:27 +0000

In today's fast-paced and data-driven world, a reliable and robust database is essential for any business or organization. Unfortunately, database failures can occur due to a variety of reasons, such as hardware failures, software bugs, or human error. The impact of a database failure can be severe, causing lost revenue, customer dissatisfaction, and reputational damage. In this blog, we will discuss one of the most widely used recovery techniques called Log-Based Recovery.

Subscribe to my newsletter

Well, first let's discuss what is

What is Log-Based recovery?

Log-based recovery is a technique used to ensure data consistency and integrity in the event of a database failure. By using a log of all the transactions that have occurred on the database, log-based recovery allows for a precise and efficient recovery process that can minimize the impact of a failure and get your database back up and running as quickly as possible.

Now, let's dive deeper

What are logs?

To put it simply, logs are just a sequence of records, recording all activities. An update log has (generally) three fields

Transaction Identifier: Unique identifier of the transaction that performed the write operation.
Data item identifier: Unique identifier of the location of the disk where the new data item was written.
Old value: Value of the data item before the update.
New value: Value of the updated data item.

Recovery after system crashes

A transaction is always atomic, which means the transaction is either executed completely or rollback. A transaction is never executed partially. So after the system is online our recovery mechanism must detect which transactions were completed and which weren’t. It must redo the ones that were completed and undo the incomplete ones.

Before we jump into the process, here are some important bits of information

Here, we are considering databases that use deferred modification. All the modifications are stored in memory and only flushed to the database once the transactions are committed.
[T(i), start] indicates the start of the transaction
[T(i), end] indicates the end of the transaction
Format for each update/write statement in the transaction will be [T(i), X(j), old_val, new_val]

Phase 1: Redo Phase

We will go through the logs in the order in which they were carried out.

When we encounter a [T(i), start], we add T(i) to undo list. (Keep this one in mind.)
When we encounter a log [T(i), X(j), old_val, new_val] we write new_val to X(j).
When we encounter a log [T(i), end] we remove T(i) from the undo list.

If the transaction was completed, then all queries in it were redone. But in the process, we might have also redone queries from incomplete transactions. So how are we going to handle it? Well to handle that case we have a second phase.

Phase 2: Undo Phase

In this phase, we will go through the logs backward.

When we encounter a log [T(i), X(j), old_val, new_val], we check our undo list. If T(i) is present in the list we write old_val to X(j) basically undoing the operation done by the redo phase.
When we encounter the log [T(i), start], we remove T(i) from the undo list and add [T(i), abort] at the end of the log.
It is terminated after all action has been performed.

Optimizing Recovery Process

Did you notice any problem with this approach? Y*es, every time there is a failure we have to perform the recovery algorithm on the entire log. But we can optimize this using Checkpoint.*

To explain it simply, a checkpoint makes all the changes before it is permanent i.e., it writes all the updates to the disk and flushes all the data in the main memory to stable storage. It is also important to note that while the checkpoint is doing this no transactions are allowed to make write/update operations. So now instead of performing our recovery algorithm on the entire logs, we will start it from the latest checkpoint. A checkpoint is in the format [Checkpoint, L] where L represents Logs before the checkpoint.

But you might be thinking why do we need the L? Well, consider a case, where a transaction starts before Checkpoint but then aborts after the checkpoint. In that case, we need to roll back that transaction. The rest of the transactions that were committed can be erased to reduce occupied space.

What if we lose logs during a system crash, then we cannot redo or undo operations?

Well, this is where the concept of stable storage comes into play. How it works is beyond the scope of this article but in short, it replicates data in regular intervals to different non-volatile storage with independent failure recovery modes.

Credits for cover image: Image by pch. vector on Freepik

Preventing Goroutine Leaks: Best Practices and Tips for Go Developers

Avash_Mitra — Fri, 27 Jan 2023 13:50:31 +0000

This is the first blog in the series of Concurrency Design Patterns in Golang. I'll be adding more blogs with many complicated design patterns. If you want to be notified do subscribe to my Newsletter

Before starting with the design pattern, here are some prerequisites.

It would be best if you were comfortable with Golang's syntax.

Let's brush up on a few concepts before discussing the design pattern. (If you know all of these feel free to skip to the design pattern)

Goroutines

To put it simply, a goroutine is a part of code that run concurrently alongside other code. We won't go into much theory (we can leave that for some other blog).

To declare a goroutine you just have to use the go prefix while invoking a function.

Here's a simple example:



func main(){

go func(){
    for i:= 0 ;i<5;i++{
        fmt.Print(i + " ")
    }
}()

go func(){
    for i:= 5 ;i<10;i++{
        fmt.Println(i + " ")
    }
}()
}

The output of this code snippet will be something like this:



0 1 5 2 6 7 3 8 9 4
# It does not have to be exactly same.

Channels

Channels are one of the most essential building blocks of our concurrency design patterns. To put it very simply

Channels are just queues that can be used to send data from one goroutine to another.

Here are a few important facts about channels:

Channels can be either buffered (can hold one or more values) or unbuffered (cannot hold any values)
Channels are blocking.
- If you are pushing an object to a filled channel then the program won't proceed further until another object is popped from the channel
- If you are popping the element from an empty channel then the program won't proceed further until an object is pushed to the channel.



// This is a read channel. You can only read values
var readChannel <-chan interface{} 

// This is a write channel. You can only write values to this channel
var writeChannel chan<- interface{}

//You can read as well as write to this channel
var channel chan interface{}

channel1 <- val // we are pushing a value to a channel
val <- channel2 // we are reading from a channel

Now let's jump to the fun part

What is a goroutine leak?

We use a goroutine to perform some operations, and after some time send us the result and terminate. But what happens if it doesn't terminate? well, this is what we call a goroutine leak.

Even though goroutines are lightweight, if we invoke a lot of goroutines then we will be wasting a lot of resources.

Before we discuss, how we are gonna prevent goroutine leaks, let's check out an example:



func test() <-chan int {
    outStream := make(chan int)
    go func(outStream chan<- int) {
        for i := 0; i < 10; i-- {
            outStream <- i
        }
    }(outStream)
    return outStream
}

func main() {
    inStream := test()
    for i := 0; i < 10; i++ {
        val := <-inStream
        fmt.Println(val)
        time.Sleep(1 * time.Second)
    }
}

Here we have a test function that returns a read channel (we can only read values from this channel). It then invokes a goroutine and passes the channel as a write channel (we can only write to this channel). We are running a for loop and writing values to the channel. But here's the interesting part, the for loop is infinite!!. We have done this to mimic the case where our goroutine does not terminate and keeps sending value.

When we run the code, we get the following output:

We stopped the loop after 10 iterations but it can go on forever.

To stop the goroutine from executing forever, the parent needs to send it some signal. By parent, we mean the function that invoked the goroutine.
When the child receives the signal, it stops its operation. Since goroutines can only communicate via channels, the parent will send a channel to its child goroutine.
Once the parent wants to terminate the child it simply closes the channel. This signal is received by the child and it also terminates its action.

Let's look at the code implementation to understand it better



func test(terminate <-chan bool) <-chan int {
    outStream := make(chan int)
    go func(terminate <-chan bool, outStream chan<- int) {
        defer close(outStream) // Channel is closed when the function is finishes executing
        for i := 0; i < 10; i-- {
            select {
            case <-terminate:
                fmt.Println("Child Terminating")
                return
            case outStream <- i:
            }
        }
    }(terminate, outStream)
    return outStream
}

func main() {
    terminate := make(chan bool)

    inStream := test(terminate)
    for i := 0; i < 10; i++ {
        val, ok := <-inStream

       // If !ok, then it means channel is closed and we won't receive new value
        if !ok {
            fmt.Println("Channel closed")
            break
        }

        fmt.Println(val)
        time.Sleep(1 * time.Second)
        if i == 5 {
            close(terminate)
        }
    }
}

Okay, let's discuss how this code works

We make a new channel called 'terminate', and pass it as a read-only channel to the child.
Inside the infinite for-loop, we use a select statement. (A select statement is like a switch statement, it executes blocks of codes when their corresponding
Now, when the channel is closed by the parent, a closing signal is sent to the child. It then executes its corresponding code block i.e., a return statement. which breaks the infinite loop.
Now the goroutine terminates, and closes the 'outstream' channel and thus terminating the child.

Now if we execute the code, it looks something like this:

Thanks for reading till the end. If you liked my blog then do subscribe to my newsletter for more awesome content.

Cover picture credit: https://www.storj.io/blog/finding-goroutine-leaks-in-tests

Designing a Robust Web Crawler: From Requirements to Implementation

Avash_Mitra — Tue, 27 Dec 2022 16:37:19 +0000

Have you ever wondered how a search engine knows about the contents of a web page? How does it know when the contents of the page are updated? Well, the simple answer is web crawlers.

But what is a web crawler?

A web crawler is a bot that downloads and indexes contents from all over the internet. The goal of such bot is to learn what every page on the web is about, so the information can be retrieved when needed. - Cloudflare

We need to overcome a few obstacles while designing our web crawler

There are billions of web pages so are system should be** efficient in terms of memory and CPU usage**
It should be scalable (Especially horizontally scalable). Because as the web grows we can add more machines to compensate for that.
It should be fast. Our system should be able to process hundreds (or even thousands) of web pages in one second.
Web servers have implicit and explicit policies regulating the rate at which a crawler can visit them. These politeness policies must be respected.
It should crawl high-quality web pages frequently. The priority of a page should be a function of both its change rate and its quality

Let's list down the steps required while crawling websites and build components for each step

Get the URL to be crawled from the queue (It's called an URL frontier but we will get to that later)
Use DNS resolution to find the IP Address of the web page
Fetch the HTML content from the web page
If the content is already seen then discard the page
Parse the content and get all the anchor tags on the page. These anchor tags contain the next set of URLs. If the URLs are not seen then these URLs are added to the URL frontier.

Designing the URL Frontier

Before discussing the design of URL frontier, let's discuss why don't we use a standard queue. Well, a standard queue is FIFO. In the case of crawling, it is unacceptable because the in a page most URLs point to other pages hosted on the same server.

This can cause two types of problems

If we send the requests serially, We will be sending a burst of requests to the same server i.e., we will be spamming the server
If we send requests in parallel, the head of the queue would return an URL whose server has no outstanding requests.

Note: This implementation of URL frontier is based on the implementation in the Mercator web crawler

Components of URL frontiers are :

Front queues - This set of queues implement prioritization. Each queue has a priority label. The higher the priority, the sooner the URL popped from the queue.
Back queues - This set of queues implement politeness. Each queue contains URLs from only one host.
Min - Heap - There is one entry for each back queue. Each entry contains the server/host address and the earliest time when the request can be made (let's say t).
Caller threads - When we extract an URL from the back queue this thread group fetches the URLs and assigns URLs to the back queues.

How URL Frontier works:

The caller thread pops the top of the heap and waits for t seconds.
It gets the URL from the back queue and makes a fetch request.
If the back queue is not empty, it repeats the process.
If the back queue is empty (let's call this queue x), it picks one of the front queues (usually biased towards higher priority queues) and picks a URL from there.
Keep in mind, each back queue holds URLs belonging to the same host. So it checks if the URL's host is there in any back queue then the URL is pushed to that back queue.
If no queue is found it is pushed into back queue x and a new entry is added to the heap.
Well, if this feels overwhelming, don't worry. Here's the flow chart that summarizes all of it properly.

Diagram of URL Frontier

Overcoming the bottleneck of DNS Resolution

DNS Resolution is the process of finding the IP Address of a web page from its URL. In this process, we make requests to Domain Name Service and get the IP Address in response. We won't go into the details of how DNS resolution works but it can take multiple requests before we get the IP Address, so it can take a few seconds per request. This is unacceptable since we need to index hundreds of pages per second.

We can solve this bottleneck by

Caching the IP Addresses - We can use cache to store the key-value pair of hostname and IP address.
Fetching the IP Addresses asynchronously - When we are performing synchronous lookups the crawler thread is blocked until we get the IP Address, to prevent this we can use multi-threading for performing DNS lookups in parallel.
- We have separate worker threads that send requests to the DNS servers. Then it sleeps for a specified amount of time and only wakes up when the time quantum expires or another thread wakes it up
- Another single separate thread is listening to the standard DNS port. Upon receiving the response send it to the appropriate thread (one of the worker threads).
- If the thread does not receive the IP Address in a specified amount of time it makes a retry. There is a limit to the number of requests. If the lookup fails and the maximum number of retries is reached then it is aborted.

Fetching content from the web page

We will be fetching the webpage corresponding to a given URL using the appropriate network protocol. There can be multiple protocols like HTTP, FTP, etc.

Each fetch module will have multiple worker threads to make sure that there is no blocking.
To prevent the crawler from sending bursts of requests to the same host, we assign each host to one particular thread. We can achieve this by hashing the hostname and then assigning it to the thread.
- For example, if there are threads from 0 to N, then we can use the hash function h(host_name)%N. The result is the thread number.
Also, we must specify the maximum number of retries while fetching the content. If the number of tries exceeds it we will abort the process.

Designing the 'Content Seen' Module

If we use the naive approach, we store the entire content of a web page (either in cache or in secondary memory), and then whenever we get a new web page we compare it with the previous one.

This approach is simple, but it consumes a lot of time and memory. So, we won't be using this.

Instead, we use a structure called the document fingerprint set that stores a 64-bit checksum of the contents of each web page. Fingerprints offer provably strong probabilistic guarantees that two different strings will not have the same fingerprint.

It also consumes less memory and time.

The implementation of content seen module in Mercator uses Broder's implementation of Rabin's fingerprinting algorithm.

Like all other modules, we will have multiple worker threads to process web pages in parallel.

Designing the 'URL Seen' Test

This one seems really similar to the 'content seen' test. We can calculate the fingerprint for each URL and compare it with the rest.

While this approach works, it is far more efficient to hash the URL and store it for comparison. But there can be false positives if we just use the hash function so we use a data structure called Bloom Filters.

We won't go into much detail about the working of bloom filters, but here's a short explanation

It uses a large bit vector (only contains 0s and 1s). An element is added to the set by computing n hash functions of the element and setting the corresponding bits. An element is deemed to be in the set if the bits at all n of the element's hash locations are set.

By using a bloom filter

We make sure that a fixed amount of memory is used.
There are no false negatives and the probability of false positives is very less.

If the URL is not seen we add it to the URL Frontier and repeat the process.

Now that we are done, let's look at how our final architecture of web crawler looks