## Design a Threshold-Based Database Partition Rebalancer You are given database partitions and a size threshold. Oversized partitions should be split into smaller partitions, while sufficiently small partitions should be merged. Design the object model and rebalancing algorithm. The requirement intentionally omits the partition representation, legal merge partners, and the exact meaning of "otherwise merge." Resolve those ambiguities before writing code; a design that silently invents them is not complete. ### Constraints & Assumptions - A partition owns one contiguous, non-overlapping key range and has a measured or estimated size. - Only adjacent key ranges may merge under the practice contract. - A split strategy must return adjacent child ranges that exactly cover the parent range. - Metadata changes use versions so a plan based on stale sizes cannot overwrite newer topology. - Rebalancing may run repeatedly, so the policy must avoid immediate split-merge oscillation. ### Clarifying Questions to Ask - Does the threshold refer to bytes, rows, load, or a composite score, and how fresh is that measurement? - Into how many children should an oversized partition split, and how is the split key selected? - May any two small partitions merge, or only adjacent partitions whose combined size is within a limit? - Are split and merge metadata operations atomic, and what happens to concurrent reads and writes? - Should one rebalancing call perform one action, one pass, or continue until the layout is stable? ### Part 1 — Define the Domain Model and Policy Specify the partition, range, size observation, split plan, merge plan, and topology interfaces. Turn the verbal threshold rule into predicates that cannot select contradictory actions. #### What This Part Should Cover - Stable partition identity plus versioned key-range metadata. - Separate high and low conditions, or another explicit anti-oscillation rule. - Legal split points and merge partners. - Validation that ranges remain ordered, disjoint, and complete. ```hint Make the ambiguous branch executable Write the split and merge predicates in full, including the combined size of a proposed merged partition. ``` ### Part 2 — Plan and Apply Rebalancing Give pseudocode for scanning or selecting partitions, producing deterministic actions, and applying those actions safely. Explain how the algorithm reacts when an earlier action changes the neighbors of a later candidate. #### What This Part Should Cover - Deterministic candidate ordering. - No overlapping actions in one plan. - Revalidation or compare-and-set at apply time. - Complexity in the number of partitions and selected actions. ```hint Separate observation from mutation A plan can be deterministic over one topology snapshot, but every action still needs to prove that its inputs have not changed before commit. ``` ### Part 3 — Test Convergence and Failure Handling Describe tests for threshold boundaries, uneven splits, chained merges, stale observations, and partial failures. State the invariant that determines whether another pass is needed. #### What This Part Should Cover - Exact behavior at the threshold. - A layout that would oscillate under a naive single-threshold rule. - Recovery after data movement succeeds but metadata commit fails, or vice versa. - Idempotent action IDs and observable progress. ```hint Test the second pass A layout that looks correct after one action can reveal an unstable policy when the rebalancer evaluates it again. ``` ### What a Strong Answer Covers - Explicit answers to the missing input, output, ordering, and lifecycle rules. - A clean object model with topology invariants and versioned mutations. - Stable split and merge predicates that converge rather than thrash. - Tests and recovery behavior for concurrent change and partial failure. ### Follow-up Questions 1. How would you choose a split key when row sizes are highly skewed? 2. How would you limit concurrent data movement across the cluster? 3. What changes if the size measurement can lag by several minutes? 4. How would you prove that a completed plan neither loses nor overlaps a key range?