Database Sharding Strategy Implementation

Databases can grow to enormous sizes, making them slow and difficult to manage. Database sharding is a technique to partition a large database into smaller, more manageable pieces called "shards." This challenge focuses on implementing a common sharding strategy: horizontal sharding based on a primary key.

Problem Description

You are tasked with designing and implementing a pseudocode solution for routing database queries to the correct shard based on a given sharding key. This involves determining which shard a particular record belongs to and how to efficiently retrieve or modify that record.

Key Requirements:

• Sharding Logic: Implement a function that takes a sharding key (e.g., a user ID, order ID) and the total number of shards as input, and returns the index of the shard where the data for that key should reside.
• Query Routing: Simulate the process of routing a query (e.g., SELECT, INSERT, UPDATE, DELETE) to the appropriate shard. For this challenge, you will focus on the logic of determining the shard, not on actual database interactions.
• Data Integrity: Ensure that each unique sharding key maps to a single, deterministic shard.

Expected Behavior:

Given a sharding key and the total number of shards, your sharding logic should consistently return the same shard index for that key.

Edge Cases to Consider:

• What happens if the sharding key is zero or negative?
• What if the total number of shards is one?

Examples

Example 1:

Input:
  sharding_key = 12345
  total_shards = 10

Output:
  shard_index = 5

Explanation:
  A common sharding strategy is modulo hashing. In this case, 12345 % 10 = 5. The data associated with sharding_key 12345 would be stored on shard 5.

Example 2:

Input:
  sharding_key = 987654321
  total_shards = 100

Output:
  shard_index = 21

Explanation:
  Using modulo hashing again: 987654321 % 100 = 21. Data for this key resides on shard 21.

Example 3: (Edge Case)

Input:
  sharding_key = 789
  total_shards = 1

Output:
  shard_index = 0

Explanation:
  When there is only one shard, all data must reside on shard 0, regardless of the sharding key.

Constraints

• The sharding_key will be a non-negative integer.
• The total_shards will be a positive integer greater than or equal to 1.
• The sharding strategy should be deterministic.
• The pseudocode solution should be efficient, with a time complexity of O(1) for determining the shard index.

Notes

• Consider using a common hashing algorithm like the modulo operator (%) for distributing keys across shards.
• Think about how you would handle cases where total_shards might change in a real-world scenario. For this challenge, assume total_shards is fixed.
• Your implementation should be presented in a clear, readable pseudocode format. You are not expected to write actual executable code for a specific database system.