Design a Threshold-Based Database Partition Rebalancer

Problem Statement

You are tasked with designing a PartitionRebalancer for a distributed key-value store. The system stores data in contiguous key ranges (partitions). Each partition has a current_size (in bytes).

Requirements

1. Split Operation: If a partition's size exceeds MAX_THRESHOLD, it must be split into two smaller partitions at the median key.
2. Merge Operation: If the sum of sizes of two adjacent partitions is less than MIN_THRESHOLD, they should be merged into a single partition.
3. Concurrency Control: Ensure that no two operations (split or merge) can be performed on the same partition simultaneously to prevent data corruption or inconsistent states.
4. Safety: Design the logic to be idempotent. If a split or merge operation is interrupted by a node failure, the system should be able to resume or discard the partial state correctly.

Interface

Design the core logic for a RebalancePlanner class:

class Partition:
    def __init__(self, id, start_key, end_key, size):
        self.id = id
        self.start_key = start_key
        self.end_key = end_key
        self.size = size

class RebalancePlanner:
    def get_plan(self, partitions: List[Partition]) -> List[Action]:
        # Returns a list of pending split/merge actions to balance the cluster
        pass

Example

Given MAX_THRESHOLD = 100 and MIN_THRESHOLD = 20:

• If Partition A has size = 150, the plan should include Split(A).
• If Partition B (size = 8) and Partition C (size = 7) are adjacent, the plan should include Merge(B, C).

Considerations

• How do you ensure the plan converges and does not oscillate between splitting and merging (flapping)?
• What metadata or locking mechanisms are needed to track the state of a partition during a transition (e.g., PENDING_SPLIT)?
• How do you handle edge cases where a partition is updated while a plan is being calculated?