已知热点key-range的数据库sharding相关文献、算法及策略咨询

你描述的是典型的负载感知的有序范围分片拆分场景，现有成熟的算法和理论可以完全满足你不破坏原有序列/索引的需求，具体如下：

核心可用算法 #

加权范围拆分算法（工业界落地最广泛） #

• 核心逻辑：将你已有的key range访问频率作为权重指标，预设单节点可承载的权重阈值，优先对权重超过阈值的连续key range做拆分，拆分时保证每个新生成的子range的总权重尽量接近单节点阈值，同时严格保留key的全局排序属性。
• 优势：完全不需要修改原有数据的有序索引，只需要在原有shard的key边界上做切分，拆分后仅更新路由表的[key_start, key_end] -> 节点ID映射即可，上层的范围查询、索引扫描逻辑完全无需调整。

动态有序分区负载均衡算法（学术领域成熟方案） #

• 核心逻辑：在拆分完成后的分片分发阶段，会优先将相邻的低访问权重range合并调度到同一节点，避免多个高权重的热点range被分配到同一节点，同时全局的key排序逻辑完全不受影响，分片迁移过程中也不会中断有序查询请求。

落地优化建议 #

以下规则可以帮你最大化拆分效率，降低对业务的影响：

• 仅对负载超过集群平均负载2倍以上的shard做拆分，避免产生过多细碎分片提升路由开销。
• 拆分边界优先对齐原有存储引擎的有序数据块边界（比如LSM树的SSTable边界、B+树的页边界），拆分过程不需要重写数据，耗时可以降低90%以上。
• 分片分发阶段优先把拆分出来的热点子range分发到当前负载最低的节点，分发完成后再更新路由表，全程不会影响业务读写。

相关理论背景 #

该场景属于分布式系统领域经典的有序数据动态分区优化问题，目前已经有非常多的成熟落地案例，包括Google Spanner的自动分片拆分、CockroachDB的负载感知分片调整、TiDB的热点拆分功能，底层都是基于上述算法实现。

内容的提问来源于stack exchange，提问作者Anurag Vohra