Workload-Aware Shard-Key Selection and Budget-Constrained Replica Placement for Geo-Distributed Online Transaction Processing Databases

Abstract

A shard key chosen once at design time and never revisited is a liability, not a decision. This article makes the case that shard-key selection and replica placement both belong in the category of things a running system should reassess against real traffic, not settle in advance and forget. We frame per-table shard-key selection as a search over candidates the schema itself already exposes  -  a table's own primary key, plus each parent's primary key reachable through a foreign key  -  scored on how much co-partitioning it buys, how far cross-partition fan-out drops, and how evenly load lands across partitions. Replica placement is treated separately: a budget-constrained allocation of primary regions and read-serving copies driven by where read and write demand actually originates. Simulated annealing handles the key-selection search; a demand-weighted heuristic handles placement. Both are tested, alone and combined, against primary-key hashing, range partitioning, and a fixed customer-centered heuristic that many teams treat as a safe default (it is not, as the results below show). Every compared placement strategy draws from the same twelve-slot replica budget across eight partitions  -  otherwise a faster-looking strategy might just be a better-funded one. The testbed is a synthetic 24-table OLTP schema with 28 foreign-key relationships, evaluated across sixteen independently generated workload seeds with paired statistical testing and Benjamini-Hochberg correction across the full family of confirmatory comparisons. Workload-aware key selection reaches 82.7 percent of the structural locality reference, well ahead of primary-key hashing (53.8 percent) and the customer-centered heuristic (55.4 percent), and cuts cross-partition query share by 24.2 percent and average fan-out by 17.6 percent against the hash baseline. Placement alone, under the fixed budget, reduces mean latency by roughly 46 to 54 percent, P95 latency by 42 to 50 percent, and P99 latency by 50 to 54 percent across every tested shard-key strategy. Combined, the pipeline cuts modeled mean latency by 53.1 percent, median latency by 82.6 percent, P95 latency by 45.7 percent, and P99 latency by 50.5 percent against the incumbent, with model-estimated throughput up 140 percent. An eight-seed exact-optimum check on a reduced six-table subset and a 200-fold sweep of the skew-penalty weight both hold up. None of this is production telemetry  -  it is simulation evidence, and the article treats that distinction as load-bearing throughout rather than a footnote.