Uniform DB Sharding: Data Distribution and Search Strategies

Uniform Database Sharding: Data Distribution and Query Handling Strategies

Uniform sharding is a horizontal scaling technique for databases where data is distributed across shards without a predefined partitioning key. This approach tackles issues when business logic doesn't allow for a static key or when a key loses effectiveness over time. The main goal is to balance load and evenly distribute records across nodes, which is crucial for systems with evolving requirements.

Principles of Uniform Data Distribution

Uniformity is achieved through two primary methods: random shard selection or based on node load. Random distribution is straightforward to implement but doesn't correct imbalances if shards start with different sizes. A more flexible approach uses shard priorities based on current record counts, enabling:

• Automatic load leveling even from uneven starting points.
• Accounting for varying hardware in the cluster via priority tweaks.
• Temporarily excluding shards from writes (e.g., priority 0) for maintenance or archiving.

To monitor load, the service periodically queries the size of key tables in each shard and caches these values to minimize overhead.

Generating and Using Object Identifiers

In uniform sharding, an object's ID must embed shard information, such as an offset or seed in the numeric key. This speeds up OLTP operations like SELECT and UPDATE by a specific ID, as the shard is determined directly from the ID. Key generation needs an efficient strategy:

• Key requests should return batches (e.g., NN keys at once) rather than one-by-one to avoid performance bottlenecks.
• Seeds for each table can be stored in a shard's system table or connection config for flexible management.
• The business service runs a DML query to fetch a new key before inserting an object, ensuring data integrity.

Managing Reference Tables and Logical Replication

Sharded systems often include reference tables (lookup tables) that are small, rarely updated, but essential for query accuracy. Best practices include:

• Storing reference tables in a dedicated database instance, updating only there.
• Using logical replication (e.g., PostgreSQL mechanisms) to sync these tables to shards.
• This reduces shard load and simplifies data consistency without redundant update efforts.

Searching Data and Paging in Distributed Environments

With uniform sharding, searches without a known shard key require node coordination. Consider fetching the third page of an order feed, sorted by date descending. The coordinator (proxy or business service) handles it like this:

• Broadcasts the query to all shards, adjusting page bounds: LIMIT is page size * page number + 1, OFFSET always 0.
• Each shard returns locally sorted data within the LIMIT.
• The coordinator merges results from all shards, performing a global sort in one pass.
• It extracts the requested page from the merged list and returns it to the user.

This ensures read consistency but can be memory-intensive for deep paging due to coordinator resorting. Mitigations include:

• Users rarely go deep into pages, so optimize for common cases.
• For large exports (e.g., XLSX/CSV), use async file generation by a dedicated service with ample memory, processing data sequentially.

Paging Implementation Example

Assume a sharded table t1 with an id column distributed across shards A and B. A request for the first page of 2 records, sorted by id ascending, becomes: SELECT id FROM t1 ORDER BY id LIMIT 3 OFFSET 0. The coordinator sends it to each shard, merges and sorts results, then returns the page. For the second page, LIMIT becomes 5 (2 * 2 + 1), allowing detection of more data and showing a "Next page" button. This balances performance and consistency, adapting to navigation depth.

Key Takeaways

• Uniform sharding handles dynamic partitioning keys via load balancing.
• Embedding shard info in object IDs speeds OLTP ops and routing.
• Logical replication for reference tables cuts update overhead.
• Coordinated paging needs memory optimization but works well for typical user flows.
• Async processing suits large data exports, minimizing impact on the core system.

— Editorial Team