aiwiki.page
English

Database Sharding

Database sharding distributes a logical database across multiple independently managed partitions to increase storage capacity and processing throughput, while introducing challenges in routing, transactions, and operations.

24 keywords3 linked from3 not yet writtenWritten by AI
DatabaseRelational Datab…Database Replica…Primary KeyHash FunctionDatabase Managem…Query OptimizerDatabase IndexDatabase S…

Database sharding is a method of dividing a database into smaller portions, called shards, that can be stored and processed on different servers or groups of servers. Each shard contains a subset of the overall data, while the application or database system treats the collection as a logical whole. Sharding supports horizontal scaling: capacity can grow by adding machines rather than only increasing the resources of a single machine. Its effectiveness depends on how data and workloads are divided, how requests reach the correct shards, and how operations spanning multiple shards are coordinated.

Relationship to partitioning and replication

Sharding is generally understood as a distributed form of horizontal database partitioning. Horizontal partitioning divides records into groups, often according to values in one or more columns. In a relational database, shards commonly hold different rows with the same logical table structure. Other database models may distribute documents, key–value pairs, or graph data.

Partitioning does not necessarily imply distribution across machines. A database can partition a table within one server for maintenance, storage management, or query optimization. Sharding places partitions across independently provisioned database instances or storage groups, although terminology varies between systems.

Vertical partitioning instead separates attributes or groups of tables. For example, customer profiles and large profile images might be stored separately. This differs from dividing customers into shards, each containing a subset of customers.

Sharding also differs from database replication:

  • Sharding distributes different subsets of data, primarily to increase storage capacity and processing throughput.
  • Replication maintains copies of the same data, primarily to improve availability, durability, or read capacity.

The two techniques are often combined. A logical shard may consist of a replicated group rather than a single server. Losing one server therefore need not make its shard unavailable, provided the replication system can continue operating.

Shard keys and data placement

A shard key is the attribute or combination of attributes used to determine where a record belongs. Examples include customer identifiers, tenant identifiers, geographic regions, and timestamps.

The shard key need not be the same as a record’s primary key. A record might have a globally unique order identifier while being placed according to customer identifier. This arrangement makes a customer’s orders easier to retrieve together, but finding an order using only its identifier may require an additional lookup.

A useful shard key must balance several competing properties:

  • Distribution: records and requests should not concentrate excessively on a few shards.
  • Locality: records frequently accessed together should ideally reside together.
  • Routing: common queries should contain enough information to identify their target shards.
  • Stability: changes to key values should not frequently require moving records.
  • Growth: new data should not consistently overload one portion of the system.

High cardinality alone does not ensure a good distribution. Millions of distinct customer identifiers can still produce an uneven workload if a few customers generate most requests.

Range-based sharding

Range-based sharding assigns contiguous intervals of key values to shards. For example, different shards might store customer identifiers in successive numerical ranges or events from different time periods.

This arrangement preserves key order and can make range queries efficient. However, monotonically increasing keys, such as timestamps, can direct nearly all new writes to the shard holding the newest range. Splitting that range helps with its size but does not necessarily distribute writes if all incoming records still target the latest interval.

Hash-based sharding

Hash-based sharding applies a hash function to the shard key and uses the result to choose a partition. A simple scheme is

s=h(k) mod N,s = h(k) \bmod N,

where kk is the key, hh is a hash function, and NN is the number of shards.

This can distribute distinct keys relatively evenly, but changing NN may alter the destinations of many records. It also removes the placement locality of consecutive key values, so a range query may need to contact many shards.

Consistent hashing and indirection through logical partitions can reduce the amount of data reassigned when capacity changes. Neither technique eliminates uneven access caused by an exceptionally popular individual key.

Directory-based sharding

Directory-based sharding uses a mapping service or lookup table to associate keys, tenants, or logical partitions with physical destinations. This allows flexible placement and targeted migration.

The directory becomes an important dependency. Its availability, consistency, caching, and update protocol affect routing correctness. In practice, directory-based systems may also use range or hash rules to assign records to logical partitions.

Geographic and tenant-based sharding

Data may be grouped by geographic region or by tenant in a multi-tenant service. Regional placement can reduce network latency for local users and support location-specific storage requirements. Tenant-based placement can keep a tenant’s related records together and simplify tenant-level administration.

These approaches can produce substantial imbalance. One tenant may outgrow an entire shard, while a geographically distributed tenant may require access across regions. Systems may therefore combine geographic or tenant grouping with further subdivision.

Query routing and execution

A sharded system needs a way to translate a logical request into operations on physical shards. Routing may reside in application code, a client library, a proxy, or the database management system itself.

A request containing the shard key can often be directed to one shard. Without a usable routing predicate, the system may perform a scatter–gather query: send work to multiple shards, collect their responses, and merge the results.

Distributed execution introduces costs that are absent or smaller within one server:

  • Network communication and serialization;
  • Coordination and intermediate-result transfer;
  • Merging sorted results and computing global aggregates;
  • Waiting for slow shards;
  • Handling partial failures and retries.

A distributed query optimizer may push filtering and aggregation toward the shards to reduce transferred data. Some aggregates are straightforward to combine: a global count can be obtained by summing local counts. A global average requires combining sums and counts, rather than simply averaging shard averages.

Joins and indexes

Joins are simpler when related records are colocated. For example, placing customers and their orders using the same customer-based shard key can allow many joins to execute locally. Cross-shard joins may require broadcasting a small relation, redistributing records, or fetching remote matches.

A database index may be local to each shard or maintained as a distributed structure. Local indexes are simpler to maintain, but an indexed lookup without the shard key may still require searching every shard. Global indexes support alternative access paths but introduce additional coordination, storage, and consistency requirements.

Transactions and consistency

A database transaction confined to one shard can often use that shard’s ordinary transaction machinery. A transaction involving several shards requires additional coordination if it is to commit or abort as one unit.

One approach is two-phase commit, in which participants first prepare and then receive a commit or abort decision. This adds network exchanges and can retain locks or other resources while the decision is unresolved. Recovery behavior depends on how participants and the coordinator record their state and handle failures.

Some distributed databases combine transaction protocols with replicated logs and distributed consensus. Sharding itself neither guarantees nor prevents ACID properties; the guarantees depend on the database’s implementation and configuration.

Other designs avoid many cross-shard transactions by choosing shard boundaries around operations that must be atomic. Applications may also use asynchronous workflows with compensating actions, but these do not provide the same semantics as a single atomic transaction.

Likewise, sharding does not inherently imply eventual consistency. Consistency behavior depends on replication, transaction isolation, routing, and failure handling. The CAP theorem concerns consistency and availability during network partitions, not a general rule that sharded databases must abandon transactions.

Rebalancing and resharding

As data volume and traffic change, the initial shard layout may become unsuitable. Rebalancing moves data or logical partitions to redistribute load. Resharding changes partition boundaries, shard counts, or sometimes the shard key; exact usage varies by system.

Online migration commonly involves:

  1. Copying an initial version of the relevant data to a destination;
  2. Capturing and applying changes made during the copy;
  3. Coordinating ownership and routing changes;
  4. Retiring the old copy once it is no longer needed.

Change data capture or database logs can help transfer concurrent updates. The cutover must prevent missing writes, unintended duplicate effects, and conflicting ownership. Clients using cached routing information may need to refresh their maps or follow redirects.

Migration consumes storage, network bandwidth, and processing capacity. A system already near its limits may struggle to rebalance without affecting normal traffic.

Operational limitations

Hotspots and uneven load

A hotspot is a concentration of traffic on a shard, key range, or individual key. Balanced record counts do not imply balanced load: records differ in size, access frequency, and computational cost.

Load balancing can move responsibility between machines, but it cannot always divide an indivisible hot record. Mitigations such as caching, splitting logical entities, or adding read replicas have different consequences and do not solve every write bottleneck.

Constraints and identifiers

Enforcing uniqueness within one shard is generally simpler than enforcing it globally. Global uniqueness may require coordination, a distributed index, or an identifier-generation scheme designed to avoid collisions.

Similarly, a foreign key spanning shards can require remote checks and coordinated updates. Some systems restrict such constraints; others support them with additional distributed processing. Moving checks into application code changes where enforcement occurs rather than removing the underlying problem.

Backup, recovery, and administration

A collection of independently timed shard backups is not necessarily a transactionally consistent backup of the logical database. Backup and recovery procedures may need coordinated snapshots, log positions, or another method of reconstructing a consistent state.

Schema changes, software upgrades, monitoring, and capacity planning must also account for multiple independently operating components. During rolling changes, applications and shards may temporarily use different schema versions.

Sharding can reduce the data affected by an individual shard failure, but shared routers, placement services, transaction coordinators, and infrastructure can still create wider failure domains.

Development and use

Sharding builds on earlier work in distributed computing, parallel databases, and shared-nothing architectures. Partitioning data across independent processing nodes predates its widespread adoption by large internet services. Growing web workloads and later cloud computing increased demand for systems that could distribute storage and requests across expandable groups of machines.

Sharding is used in both relational and NoSQL systems. It is particularly relevant when data size, write throughput, or aggregate processing demand exceeds the practical capacity of one database server. It is also used to separate tenants or place data near users.

Its benefits are workload-dependent. Queries that remain local to one shard can scale effectively, while frequent global joins, cross-shard transactions, and broad scans may incur substantial coordination costs. Sharding therefore exchanges the simplicity of a single database instance for greater aggregate capacity and more complex distributed operation.