MySQL 线性散列分区

Question

MySQL 使用相当简单的算法将键分配给分区：

https://dev.mysql.com/doc/refman/8.0/en/partitioning-linear-hash.html

基本上，给定 num 个可用分区，以及键 k:

MySQL 尝试将键 k 分配给分区 "k modulo V”，其中 V 是大于分区的 2 的最小幂。如果输出超过 num，他们会反复尝试 2 的下一个更小的幂：k mod V/2.. .

我不明白的是他们为什么需要循环：他们似乎可以停在 V/2 而永远不需要考虑 V/4。我是不是遗漏了什么，还是文档让事情变得比应有的更复杂？

我正在回忆下面的 Mysql 文档代码：

V = POWER(2, CEILING(LOG(2, num)))
N = F(k) & (V - 1)
While N >= num
{ V = V / 2 
  N = N & (V - 1)
}
Assign key k to N

Answer 1

你说的对，实际上是calculated没有循环：

static uint32 get_part_id_from_linear_hash(longlong hash_value, uint mask,
                                           uint num_parts) {
  uint32 part_id = (uint32)(hash_value & mask);

  if (part_id >= num_parts) {
    uint new_mask = ((mask + 1) >> 1) - 1;
    part_id = (uint32)(hash_value & new_mask);
  }
  return part_id;
}

我不完全确定文档想要表达什么，但是由于 MySQL 中使用的实现是更通用的线性哈希的特定版本，作者可能只是没有简化更通用的案例（你实际上可能会使用循环）到绝对结束，或者使用白皮书中关于算法的描述。它仍然是正确的。

MySQL 线性散列分区

MySQL Linear Hash partitioning

mysql

database-partitioning