Database scalability: Sharding, partitioning & replication

Suppose you’re eagerly scrolling through your favorite social media platform, excited to see what your friends share. The app suddenly becomes super slow and takes a lot of time to load new posts as you scroll down. This isn’t just a minor inconvenience—it’s a major problem that can drive users away from using the application. This is precisely the kind of scenario that Facebook and Instagram faced in their early days. With millions of users joining every month, their database struggled to keep up, leading to slowdowns and even crashes.

Why does this happen? As your business grows, so does the demand on your database. More users mean more data and transactions, which can overwhelm even the best-designed systems. You need a database that can handle increasing loads to keep your app running smoothly and avoid slowdowns or crashes. This ability to scale ensures a great user experience and business success.

In the tech world, having a scalable database isn’t just nice to have—it is essential. This blog will dive into key strategies for scaling databases, including sharding, partitioning, replication, and clustering. We’ll explore how to choose the right approach for different applications and examine real-world case studies to see these strategies in action. At the end, we’ll also explore some advanced techniques and future trends.

Let’s start by exploring the latest scalable databases that tech giants use and how these databases scale by using the techniques mentioned above.

Modern databases in 2024#

In modern database architecture, database systems leverage sharding, partitioning, and replication to enhance scalability, enabling more effective database management and data distribution across multiple servers. Four common types of databases are in use today:

• SQL databases: They excel at structured data, complex queries, and transactions, making them ideal for traditional business applications.

• NoSQL databases: They easily handle unstructured or semi-structured data and offer high scalability for big data applications.

• In-memory databases: They prioritize speed by storing data in RAM, perfect for real-time analytics and caching.

• Time-series databases: They are specialized for handling data with timestamps, making them essential for IoT, finance, and website metrics. They are optimized for time-based queries, high performance, and efficient data compression.

Note: Explore SQL vs. NoSQL to better understand and choose the right database for your application.

There are many modern databases of the above four types that are renowned for their support for sharding, partitioning, and replication; the top few are listed below:

• Cassandra: Developed by Facebook in 2008 and handed over to Apache in 2009, it is a highly scalable, distributed NoSQL database designed to handle a large volume of data. It supports automatic replication and partitioning.

• MongoDB: Released in 2009, it is a NoSQL database supporting sharding, built-in replication, and distribution of data across multiple servers.

• Redis: Released in 2009, it is an in-memory data structure store that can be used as a database and cache. It is a good choice for distributed applications that support partitioning through Redis clusters and replication.

• Couchbase: Released in 2012, it is an advanced NoSQL database that combines key-value store functionality and document database features. It also supports sharding and replication.

• DynamoDB: Launched in 2012 by Amazon Web Services (AWS), it is a NoSQL database and a go-to solution for high-performing applications due to its features of scalability, auto-partitioning, and multi-region replication.

• BigTable: Developed internally in 2006 and released as a service on the Google Cloud Platform in 2015, BigTable is another NoSQL database that can handle massive amounts of data across multiple servers. It also supports auto-sharding and replication, suitable for big data applications. Apache HBase is also modeled after BigTable and is suitable for large datasets.

• CockroachDB: Launched in 2017, it is an SQL database designed for global consistency and scalability. It supports automatic sharding and replication across multiple regions.

• TimescaleDB: Launched in 2017/18, it is an open-source time-series database built on PostgreSQL. It is suitable for time-series data and analytics and supports partitioning and replication.

MySQL database is no exception and is a top choice of applications for storing structured data. It also supports partitioning, sharding, and replication.

Database scalability in System Design#

Database scalability refers to a system’s ability to handle increasing amounts of data and user load efficiently by adding storage or distributing data across multiple nodes. It is all about ensuring that data is available across different locations, maintaining backups for disaster recovery, and optimizing performance so clients can quickly perform read and write operations.

Now let’s explore the strategies and how we can make our databases scalable with these strategies.

Data partitioning#

Partitioning refers to dividing a single database into smaller, manageable pieces or within the same instance. It focuses on dividing larger tables into smaller sub-tables. We can access and manage these sub-tables separately to enhance database performance and scalability. The goal is to enhance query performance by reducing the data it needs to scan to retrieve results. We have the following two types of partitioning data:

• Horizontal partitioning is dividing data into smaller sub-tables horizontally, keeping the schema as it is. Imagine you’re organizing a large stack of papers into different folders by year. Each folder holds a portion of the papers, but they all have the same structure–like every folder containing invoices from a different year.
  In terms of database, a table with one million rows can be partitioned horizontally into two sub-tables with half a million rows each.

• Vertical partitioning changes the table schema by vertically dividing or partitioning the data. Think of sorting a pizza by toppings. Instead of serving one pizza with all the toppings together, you split it–one plate with slices that have just cheese and another plate with slices that have just veggies.
  In database terms, you’re splitting the columns: one table holds customer details, and another stores order preferences.

Partitioned data can be replicated to different nodes to overcome the load on a single node and for parallel query execution. To understand how this data is partitioned, let’s explore the techniques for horizontal partitions.

Note: You can explore a detailed chapter on data partitioning from our comprehensive course titled Grokking the Modern System Design Interview.

Data sharding#

Sharding is a method of splitting a larger database into smaller and more manageable pieces called shards. Each shard is a complete and independent database that holds a subset of the total data. They are distributed and stored on different servers and identified with shard keys. This enables horizontal scaling by distributing the load across multiple servers and improves performance. We’ve different techniques to shard databases discussed in the subsequent sections.

Note: You might think partitioning and sharding are the same. Yes, they are. Sharding is an advanced version with new techniques of horizontal partitioning. The main difference between the two is that in partitioning, data is split and placed within a single database node, whereas in sharding, data is placed on distinctly located nodes.

Sharding techniques#

There are several techniques for sharding a database, and we need to choose one based on our requirements.

Hash sharding#

Hash sharding is a method of distributing data across multiple database shards using a hash function. The basic idea is to apply a hash function to some key attribute of the data (such as a user ID) to determine which shard the data should be placed in. This ensures an even distribution of data across the shards, accessed with shard keys.

Social media platforms like Facebook have millions of users, and storing all user data in a single database would be inefficient and slow. Using hash sharding, Facebook can distribute user data across multiple databases (shards), ensuring that no single database becomes a bottleneck.

Example of hash sharding#

Suppose you have a user table and want to distribute it across four shards. The following is an example of calculating sharding keys using the hash function:

• Shard 1: User IDs whose hash value is % 4 == 0

• Shard 2: User IDs whose hash value is % 4 == 1

• Shard 3: User IDs whose hash value is % 4 == 2

• Shard 4: User IDs whose hash value is % 4 == 3

Let’s talk about the advantages, challenges, and security mechanisms to secure data for hash sharding.

Directory-based sharding#

Directory-based sharding is a method where a central directory (or lookup table) is maintained to map each data item to its corresponding shard. Unlike hash sharding, where the shard is determined algorithmically, directory-based sharding relies on this central directory to direct queries to the correct shard. When inserting data, the system first consults the directory to determine which shard the data should be placed in, and we can easily add new shards as the system or data grows.

Example of directory sharding#

Consider an e-commerce platform like Amazon, where customer orders are distributed across multiple database shards. Each order might have a specific order ID, and the directory keeps track of which shard contains the data for each order ID.

Let’s consider a simple example with user data spread across three different shards:

Let’s highlight the advantages, challenges, and security mechanisms of directory-based sharding.

Range-based sharding#

Range-based sharding is a technique where data is divided into shards based on predefined ranges of a key attribute, such as date, age, or user ID. Each shard is responsible for a specific range, making it easier to locate data.

Suppose you split your data into ranges; for example, if you’re using user IDs, you might decide that IDs from 1 to 1000 go into Shard 1, 1001 to 2000 into Shard 2, and so on. When new data comes in, it’s placed in the shard that covers its range. So, if a new user with ID 1500 signs up, their data goes into Shard 2. When you need to retrieve data, you simply check which range the data falls into and then query the corresponding shard.

Example of range sharding#

Imagine a bank managing millions of customer accounts where range-based sharding is applied based on customer age categories:

• Shard 1 (Age < 20): Accounts of customers aged less than 20 years

• Shard 2 (Age 20–30): Accounts of customers aged between 20 to 30 years

• Shard 3 (Age > 30): Accounts of customers aged greater than 30 years

This approach allows the bank to efficiently manage transactions, generate reports, and retrieve customer data by categorizing accounts into age groups. For instance:

Let’s discuss the advantages, challenges, and security mechanisms of range sharding.

Geographic sharding#

Geographic sharding is a method of distributing data across multiple database shards based on the physical location or region of the data’s origin. This approach is particularly useful for applications that serve users from different geographical areas, allowing data to be stored closer to where it’s most frequently accessed.

When data is inserted into the system, it’s placed in the shard corresponding to the data or user’s geographical location. Routing the queries to the shard associated with the region of interest ensures quick response time and localized data access.

Example of geographic sharding#

Let’s take the example of a video streaming service like Netflix:

• Shard 1 stores user profiles, viewing histories, and content data specific to users in America.

• Shard 2 manages similar data for users across Europe.

• Shard 3 contains data for users in Asia-Pacific regions.

Let’s explore the advantages, challenges, and security mechanisms of range sharding.

Entity-based sharding#

Entity-based sharding is a technique for dividing the database into shards based on specific entities or objects by grouping related data together according to their type, such as users, products, or orders. Data is routed to the appropriate shard based on its entity type. For instance, user data goes to a user-specific shard, while product data goes to a product-specific shard. Queries are directed to the relevant shard based on the entity being queried. A query involving multiple entities may need to access multiple shards.

Example of entity-based sharding#

For an e-commerce platform:

• Each user’s profile, including personal details and shopping history, is stored in a shard dedicated to the user shard.

• A separate product shard stores information about products, including descriptions, images, and stock levels.

• An order shard contains details about customer orders, including items purchased, payment information, and shipping status.

Let’s explore the advantages, challenges, and security mechanisms of entity-based sharding.

Hybrid sharding#

Hybrid sharding combines multiple strategies to optimize data distribution based on different criteria. It leverages the strengths of various sharding methods, such as range-based, hash-based, entity-based, or geographic-based sharding, to address the specific needs of an application or system. This approach is particularly useful in complex systems where no single sharding strategy is sufficient.

Hybrid sharding involves applying different sharding strategies to different aspects of the data. For example, you might use range-based sharding for certain data types while applying hash-based sharding for others.

Example of hybrid sharding#

We can consider an e-commerce service that employs hybrid sharding:

• It uses hash-based sharding to evenly distribute user data across shards. This helps in balancing the load and ensuring even distribution of user-related queries.

• It uses range-based sharding based on order dates. Orders are partitioned into shards based on date ranges, making it easier to manage and query historical data.

• It uses entity-based sharding based on product categories. Different product categories are stored in separate shards to optimize queries related to specific types of products.

Replication#

When we say replicate something, we mean to make a copy of it and keep it in another place. The same applies to database replication, where we make copies of entire or partial databases and keep them at multiple locations. It ensures that the same set of data is available on multiple database instances, typically located on different servers or geographical locations. The primary purposes of database replication include high availability, disaster recovery, and load distribution to optimize performance.

When we say replication, it means that when data is written to the primary database after a write request, the same data should also be written on replicas 1, 2, 3, and so on. The main concern is how to do it with minimum tradeoffs.

There are different techniques for making these copies or replicas, each with its own pros and cons. As stated above, the main goals are availability, load distribution, disaster recovery, and sometimes consistency as well. We need to figure out the best techniques for replication in different scenarios.

We have the following strategies for replication:

• Asynchronous replication: In asynchronous replication, we send the confirmation back to the client as soon as the data is successfully written to the primary database. After sending the confirmation to the client, the data is sent to the replicas, whether they’re live or not. What if the primary database node fails after sending the confirmation to the client and before writing data to replicas? This reduces client latency but can lead to data synchronization and consistency issues.

• Synchronous replication: In synchronous replication, we write data to the priamary database and the replicas before sending a confirmation response to the client. This ensures the replicated data is always up-to-date and safe with the primary, but the client must wait longer for confirmation. What if there are hundreds or thousands of replica nodes? A client will have to wait longer to get a confirmation, or a failure will occur if a replica node is unavailable and the operation is unsuccessful because we simply can’t write data to all replicas.

• Hybrid replication or semi-synchronous: To address the above issues, some databases allow us to define a configuration where we’ll write synchronously to a specified number of replicas, and all others will have asynchronous updates.

For the replication, either synchronous or asynchronous, there are specific strategies to follow, as given below:

• Primary-secondary replication: In primary-secondary replication, the primary database handles all write operations, while the secondary replicas only manage reads. This setup is ideal for scaling read-heavy applications without stressing the primary database. When a write request arrives, the primary database writes the transaction. Then, through its replication process, the primary database sends the changes to the secondary databases.
  We can benefit from the single primary by avoiding concurrent write conflicts. In cons, the single node can get overloaded by all the write requests—we need to make it able to handle such a load. The second issue is latency to the clients from different geographical locations. To resolve this, we can have more than one primary database.

• Primary-primary replication: In primary-primary replication, two or more databases act as primaries, and both can accept write requests. It means changes to any primary database are replicated across all the primary databases. It’s perfect for high availability but requires careful conflict management because no two primaries perform the same write operations.
  The simplest way is to not let the conflict happen at all. For example, let the primary 1 handle all the write requests for region A and primary 2 to handle all requests of region B. It is not a good solution for all kinds of applications. So, a technically viable option is to introduce timestamps to each write request with the synchronized clock. We can write codes to avoid conflicts or manually correct them, but applying for millions of requests daily is a bit hectic.

• Multi-primary replication: It is similar to primary-primary replication and involves multiple primary nodes across different locations, each capable of writing data. It’s ideal for geographically dispersed systems needing high availability and fault tolerance.

• Snapshot replication: In snapshot replication, there is a distributor that takes periodic snapshots of the main database and replicates them to the secondary databases or replicas. It is useful for applications where near real-time consistency is not critical and is a viable alternative to avoid concurrent write conflicts.

Note: Data replication and the use of indexesA method of optimizing query performance by creating a data structure that enables quick lookups and retrieval of records based on specific columns. are critical in modern database systems to ensure efficient System Design and high performance in both single server or single machine and distributed environments.

Database clustering#

Database clustering is another technique that helps in database scalability. It is a method of linking multiple database servers (or nodes) together to work as a single system, providing increased availability and scalability. For example, imagine an e-commerce website with a database cluster that includes three servers. When a user places an order, the request is distributed among the servers in the cluster, allowing them to handle more transactions simultaneously. If one server fails, the others continue to operate, ensuring the website remains accessible.

The two common clustering techniques are:

1. Active-active clustering: All servers in the cluster are actively handling requests at the same time. This helps distribute the load evenly and ensures high availability, as each server contributes to the work.

2. Active-passive clustering: One server (the active one) handles all the requests, while the others (the passive ones) stand by as backups. If the active server fails, one of the passive servers takes over, ensuring that the system continues to work.

Clustering techniques can opt for different strategies, such as shared-nothing clustering, in which each server operates independently and has its own storage. There’s no shared data, which can simplify scaling but may require more complex data synchronization. Another strategy is shared disk clustering, where all servers access shared disk storage. This allows for easier data consistency, but managing them becomes a bottleneck. It is preferable to use hybrid clustering that combines different approaches to balance availability, load distribution, and data management based on specific needs.

Clustering helps scale databases by distributing the workload across multiple servers, improving performance, and efficiently handling higher traffic.

Beyond these, there are plenty of other strategies, all designed with the same goals in mind: keeping the data available, scalable, and running smoothly, even under heavy loads or in case of failures. The key is to find the right balance between performance, consistency, and complexity for your specific needs.

A modern perspective on database scalability#

When it comes to managing large-scale databases, traditional methods can sometimes fall short of keeping up with the demands of modern applications. That’s where innovative techniques come into play, offering new ways to enhance database scalability. By exploring unique aspects of sharding, partitioning, and replication, we can solve today’s challenges and set the stage for future advancements.

Let’s dive into how these innovative approaches—like dynamic sharding with machine learning, AI-driven dynamic partitioning, and replication with distributed consensus—reshape the world of scalable databases.

Dynamic sharding with machine learning#

The techniques discussed for database sharding are static, which can be a limiting factor when data and load change constantly. We should somehow make it dynamic; machine learning can help us do so. It analyzes data patterns and system performance and automatically adjusts how data is split across shards in real time, as discussed below:

• Adaptive sharding: Machine learning algorithms analyze data access patterns, query loads, and system performance metrics to dynamically adjust shard boundaries. This helps in optimizing load balancing and query performance without manual intervention.

• Predictive modeling: ML models can predict future data growth and query loads, enabling preemptive adjustments to shard configurations. This proactive approach helps maintain system performance and minimize disruptions.

Clustering algorithms like K-means or DBSCAN can group similar data points, optimizing shard placement based on data similarity and access patterns. Similarly, reinforcement learning models can continuously learn and optimize sharding strategies by experimenting with different configurations and learning from the outcomes.

It is a bit challenging because implementing ML models requires expertise in data science and machine learning. Moreover, these models must be trained on secure, anonymized data to protect user privacy.

Note: Data ingestion and metrics collect real-time data and performance metrics from the system. This information is used by the AI model to make partitioning decisions. Partion adjustments, i.e., partitions are added, removed, or reconfigured based on the AI model’s recommendations.

Example#

We can use tools like Apache Spark MLlib or TensorFlow to implement something like this. These platforms help build machine learning models to predict the best way to distribute data across shards.

AI-driven dynamic partitioning#

Partitioning traditionally involves breaking down a large database into smaller, more manageable pieces based on specific criteria like range, hash, or list. However, AI-driven dynamic partitioning takes this a step further by using artificial intelligence to continuously analyze and adjust partitioning strategies based on real-time data usage patterns and query performance.

Example#

Replication with distributed consensus#

CockroachDB employs geo-partitioned replication combined with a distributed consensus protocol to achieve strong consistency and high availability across global deployments. This advanced technique allows CockroachDB to place data replicas in specific geographic locations while maintaining a unified view of data through its distributed consensus system.

Example#

Future trends#

Cutting-edge technologies are transforming how we manage databases. We can leverage quantum computing, which can make data sharding much faster and more efficient because it handles large amounts of data with ease. AI can help automate many database tasks, like adjusting data partitions and fixing issues before they become problems.

In new fields, such as the Internet of Things (IoT), where many devices constantly send data, sharding and partitioning can help manage this huge flow of information smoothly. AI-driven data analytics use these techniques to process and analyze complex data quickly. In decentralized finance (DeFi), advanced replication methods can keep transactions secure and consistent across a global network. These innovations are making databases more powerful and adaptable for the future.

Conclusion#

In modern applications with ever-increasing data and user base, achieving database scalability is crucial. We’ve discussed the key strategies to scale databases, such as partitioning, sharding, and replication. While these traditional methods have set the foundation for managing large databases, advanced techniques involving AI and machine learning have taken these concepts further.

These advanced techniques are not just about handling more data—they are about doing so efficiently and intelligently. These AI and machine learning techniques enhance how data is distributed, accessed, and maintained.

As the future of the data continues to shift toward automation and intelligence, the question becomes: How can you leverage AI and machine learning to not only scale but revolutionize your database architecture? Beyond managing today's traffic, it's about preparing for a future where databases become self-optimizing, anticipating the needs of tomorrow.

Related courses#

The following are some relevant courses that will help you further your learning in the System Design and distributed systems domain. Moreover, you’ll analyze the System Design of real-world applications and how they scale databases to manage the data of millions of users.