元数据与调度

路由表（Routing Table）是存储所有区域分布信息的非常重要的模块。路由表必须保证准确性和高可用性。此外，如上所述，为了重新平衡数据，我们需要一个具有全局视角的调度程序。为了动态调整每个节点中区域的分布，调度程序需要知道哪个节点容量不足，哪个节点承受的压力更大，哪个节点具有更多的 Region Leader。这是因为所有节点几乎都是无状态的，并且它们无法自动迁移数据。相反，他们必须依靠调度程序来启动数据迁移。

您可能已经注意到，可以将调度程序和路由表集成到一个模块中 Google 的 Spanner 数据库使用这种单模块方法，并将其称为展示位置驱动程序（Placement Driver），简称为 PDPD 主要负责上述两个作业：路由表和调度程序。

PD

Google 的 Spanner 论文没有详细介绍展示位置驱动程序的设计。但是，可以肯定的是，设计大型分布式存储系统的一个核心思想是假设任何模块都可能崩溃。如果模块的状态相互依赖是非常危险的。这是因为一旦实例崩溃，备用实例必须立即启动，但是此新启动实例的状态可能与崩溃的实例不一致。这时，我们必须足够小心，以免引起可能的问题。

以一个简单的案例为例。PD 路由表存储在 etcd 中。但是，节点本身确定区域的划分。这样，节点可以快速知道其区域之一的大小是否超过阈值。当此拆分事件从节点主动推送到 PD 时，如果 PD 收到此事件但在将状态保持为 etcd 之前崩溃了，则新启动的 PD 不会知道拆分。此时，路由表中的信息可能是错误的。

我们要做的是将 PD 设计为完全无状态的。只有使其完全无状态，我们才能避免由于无法持久保存状态而导致的各种问题。每个节点定期使用心跳将有关其上区域的信息发送给 PD。然后，PD 获取接收到的信息并创建一个全局路由表。这样，即使 PD 崩溃，在新的 PD 启动之后，也只需等待一些心跳，然后就可以再次获取全局路由信息。此外，PD 可以将 etcd 用作缓存来加速此过程。也就是说，新的 PD 启动后，它将从 etcd 中提取路由信息，等待一些心跳，然后提供服务。

Epoch mechanism

但是，您可能已经注意到仍然存在问题。如果群集在某个部分中具有分区，则有关某些节点的信息可能是错误的。例如，某些区域在拆分后重新启动选举和拆分，但是另一批隔离的节点仍通过心跳将过时的信息发送给 PD。因此，对于一个地区，两个节点中的任何一个都可能会说它是领导者，而该地区也不知道可以信任谁。

在 TiKV 中，我们使用 Epoch mechanism，使用此机制，会用两个逻辑时钟标记更改：一个是 Raft 的配置更改版本，另一个是 Region 版本。对于每个配置更改，配置更改版本都会自动增加。同样，对于每个区域更改（例如拆分或合并），区域版本也会自动增加。

PD 采取的时代策略是通过比较两个节点的逻辑时钟值来获得更大的值。PD 首先比较两个节点的 Region 版本的值。如果值相同，PD 将比较配置更改版本的值。配置更改版本较大的节点必须具有较新的信息。