存储架构空间 - 元数据 （P2）

这是长篇“分布式存储架构和设计空间”的第三篇。原文有5W多字词，受微信公众号长度限制，需要分P发出。全文将依次总结各存储组件的技术和设计空间，本章关注元数据。

元数据（Metadata）

元数据的关键问题是元数据体积、如何横向扩展、如何存储、以及一致性。元数据体积与数据分区（partitioning）和放置（placement）密切相关。

元数据体积（Metadata size）

本质上，元数据体积取决于存储对象的 跟踪粒度（tracking granularity） 和 自由度（degree of freedom）。它们是设计空间的关键维度

• 跟踪粒度 。较小的分区通常会产生更好的平衡，但会消耗更多内存。这同样适用于任务调度，想象将随机球扔进纸箱；越小/越多的球，箱内球数越平衡。不同的冷热分层可以使用不同的跟踪粒度，例如，缓存中使用块，存储使用文件，例如 Akkio u-shards 。

• 自由度 。对象需要内存来跟踪放置位置的根本原因是，对象可以自由地放置在任何位置。限制可能的放置位置通常会减少内存消耗，例如哈希对象 ID 以映射到放置位置。然而，这使得放置不灵活并且会产生迁移成本。

总结通常的技术和设计模式，有的用最少的元数据，有的用更多的元数据以进行细粒度控制

• 基于哈希的放置 （Hash-based placement），零元数据的极端。典型的例子是 Ceph CRUSH，或一致性哈希（consistent hashing）。Ceph PG 的位置由确定性算法（deterministic algorithm）计算得出，该算法没有自由度，因此不需要元数据。优点是元数据内存成本很小。缺点是是增加/删除节点时的数据迁移，放置按容量平衡而不是热度，当集群接近满时几乎无法放置。

• 跟踪完全放置 （Tracking full placement），完整元数据的极端。一个对象能够放置在任何节点上，并且该位置在内存中被跟踪。优点是很容易实现复杂的迁移，以及容量、热度的细粒度平衡。缺点是元数据体积大，但有一些方法可以减少或卸载（offloading）。

• VNode ，混合方法，用两层结构，在对象侧限制自由度。一个对象首先被确定性地映射到一个 VNode，然后 VNode 可被放置在任何节点上。VNode 增加了跟踪粒度，因此需要跟踪的元数据更少，但仍然享有放置自由。例如数据库的分区可自由放置，行通过主键哈希决定所属的分区。例如 Ceph PG 和 Dynamo 的 VNode，通过哈希将较小的对象组合成较大的组（尽管PG、VNode仍然使用哈希放置）。例如Azure 存储的 Extent，它组合来自表格层的小块。

• 将索引分区 （Partitioned Index）。混合方法，限制可放置的空间的大小，用于 Kangaroo KLog 索引。不是允许将条目（entry）放置在哈希表的任何槽（slot）中，而是将哈希表分成多个分区，对象只能放置在确定的分区中。因此索引的空间减少，索引/指针所需内存减少。另一种限制放置空间的方法是 Copyset[291]。

• 叠加 （Overlay），混合方法，将自由放置层叠加在基于哈希的放置层上。现有对象保留旧的基于哈希的放置。新对象在元数据中被跟踪，并使用不同放置算法。添加节点不会强制迁移现有对象。 MAPX[292] 是一个例子。

• 减少对象链接 （Reduce object linkage）。元数据体积的另一个来源是用于查找对象的映射链接，例如 16 字节的 UUID。当对象很小并且组件被分解到系统中的不同层或节点时，它尤其会增长。一个减少此元数据体积的方法是，将子对象 piggyback 到其父对象中以省去查找 ID 。

元数据横向扩展（Metadata scaleout）

处理横向扩展的主流方法是分区（partitioning，也称分片 sharding），但也有更简单的方法。

• 分区 （Partitioning）。元数据按主键范围切割，由不同的 Paxos Quorum 管理，例如 Tectonic 。对象也可以按主键哈希分区。这种方法解决了可扩展性问题，增加实现复杂性，并且会带来一致性方面的挑战。

• 解耦 （Decoupuling）。并非所有元数据都必须存储在中央存储中，不太重要的部分可以解耦到其它存储，以不同方式横向扩展，例如 Tectonic 。这种方法增加了复杂性，并会产生消息传递成本，尤其是对于解耦前的密集的内存扫描。

• 下推 （Pushdown）。元数据可以分为两个层级。第一层仍然在中央存储中。第二层按需查找，下推到更多的数据节点，或者下推到 SSD 。一个典型的例子是处理 “Lots of small files”（LOSF）：小文件被压缩成一个大文件，大文件本地存储了自己的索引；例如 HDFS[293] 只管理大文件，而文件内索引则按需加载。

• 层层代理 （Levels of delegation）。与 Pushdown 类似，示例是 Big Table 。将集群范围的 B+-tree 视为元数据， 元数据本质上是一种查找数据的索引，如果是树状结构，可以逐层分解，自然地 scaleout 低级层次到整个集群，而顶层则专门保存在一致性的 Paxos Quorum 中 。

元数据存储

在哪里托管元数据，例如专用集群、分布在数据节点、动态即时生成等等。

• Paxos Quorum 是流行的方法，例如 Ceph、FaRM、TiDB、CockroachDB 。它们使用专用的 Paxos（或变体 variant）集群来托管元数据，或由 Paxos（变体）支持的 Etcd、ZooKeeper。

• 点对点 （Peer-to-peer）。源自 Dynamo 系统，不使用专用的元数据集群，而是将信息分布在整个集群中。它使用 Gossip 协议来达到最终一致性。此外，Dynamo 没有太多要跟踪的元数据，因为它使用一致性哈希放置。

• 主/从 （Primary/Secondary）。HDFS 使用单个 Namenode 来托管所有元数据并处理事务。相比 Paxos 集群，这样更简单。为实现 HA，HDFS 增加了一个（或多个）从备份节点。

• 上帝节点 （God node）。你可以看到分布式数据库从一个（或一个 Paxos Quorum 的） “timestamp oracle” 节点或 “sequencer” 节点获取事务时间戳。例如 TiDB 的 PD，FoundationDB，CORFU。Sequencer 节点是无状态的，可以通过重启快速恢复，并使用 Epoch 来分离新/旧。

元数据卸载（Metadata offloading）

元数据可以由别处代为管理，以避免自己处理横向扩展、一致性和持久性的麻烦。

• Consistent Core 。App 由微服务框架提供的 ZooKeeper、Etcd 管理元数据。通过这种方式，问题被卸载到别处。这种方法很受欢迎。

• 内存中的数据库 （In-memory DB）。存储集群的可用内存数据库管理元数据。例如 HopsFS 或 Hekaton。数据库管理元数据分区、一致性、横向扩展以及将冷数据分层到 SSD 。在单个数据节点级别，Ceph BlueStore 将元数据卸载到 RocksDB，并复用其事务功能。

• 冷热分层 （Cold tiering）。冷的元数据可以卸载（offloading）到 SSD。何时卸载什么数据需要仔细管理，以避免减慢定时维护的扫描循环，尤其是在多重节点故障（correlated node failures）和紧要数据修复时。也可以将冷数据内存压缩，但这会消耗 CPU。

元数据一致性（Metadata consistency）

关于一致性，不同的领域有自己的术语，例如 DB、Storage、Filesystem，这有时会带来混淆：

• 数据库 领域通常使用诸如强一致性（strong consistency）、外部一致性（external consistency）、可串行化（serializability）、隔离级别（isolation levels）、快照一致性（snapshot consistency）等术语。参见 分布式事务[294] 。

• 存储 领域和 分布式系统 可能使用线性化（linearizability）、顺序一致性（sequential consistency，见上文）等术语。而弱一致性有，最终一致性（eventual consistency）、因果一致性（causal consistency）。（良好实现的）最终一致性（eventual consistency）保证更新在给定的时间窗口内完成传播，不会翻悔，并且单向传播。因果一致性经常用于客户端的消息传递，例如其需要查看自己的修改结果。

• 文件系统 领域用 “journaling” 表示元数据的日志，用 “logging” 表示数据的日志。它们涉及写入原子性（write atomicity）、操作原子性（operation atomicity）、崩溃一致性（crash consistency）等。写入原子性的例子是，如果一个写同时更改数据和 inode，则它们应该全部成功或全部不成功。操作原子性的例子有 rmdir、rename ，这些操作不应该向用户暴露进行到一半的状态。崩溃一致性意味着在节点崩溃后，文件系统应该恢复到正确的状态，例如没有执行一半却可见的 rmdir、rename ，例如 PMEM 上没有损坏的链表。

• 虚拟机 （VM） 和 备份 系统使用一致性快照（consistent snapshot）等术语。数据建库可以使用计算 VM、缓存 VM、存储 VM 。当 Hypervisor 拍摄一致性快照时，这要求所有 VM 都在一致的时间点拍摄快照。反例是，计算 VM 认为更新已提交，但存储 VM 的快照时间较早，并表示没有此提交。

• Paxos 算法使用一致性读取（consistent read）或 Quorum 读取（quorum read）等术语。问题来自于一半的投票者可能正滞后投票（lag votes），或者一半的副本可能正滞后执行（lag execution），因此客户端可能从副本读取过时（stale）的状态。为了克服这个问题，客户端只能从 Paxos leader 读取（不能分配负载，并且 leader 可能已经发生故障转移），或者使用包含超过一半非 leader 副本的 quorum read，或者切换到因果一致性。

元数据一致性和数据一致性涉及共同的技术，元数据需要与数据保持一致地更新。 Epoch[295] 和 fencing token[296] 是常用的技术，它们使过时的元数据/数据过期（例如崩溃重启后），以及排除过时 leader。我将大部分篇幅留给数据一致性章节。一般来说，元数据需要强一致性，或者更弱但版本化（versioned）。

• 单节点 ，强一致性。将所有元数据放在一个节点上是老办法，但实现起来非常简单。HA 可以通过一个备节点来实现，或者简单地依靠更快的重启。现代 CPU 确保每个核的顺序一致性，跨核可以通过锁来实现线性化。

• Paxos ，强一致性，在 Quorum 中。依赖 Paxos Quorum 是实现元数据强一致性的主流方法，例如 Ceph、HBase 。一个流行的变体是 Raft[297] ，它起源于 RAMCloud[287]，但更加知名。

• 因果一致性 ，弱一致性，依赖传播。当强一致性代价高昂时，通常出于性能考虑，元数据可以切换到较弱的一致性。最常用的是因果一致性，它利用传播中的顺序。它可以通过在消息中添加版本号（简化 vector clocks[298]）来实现。

• 快照一致性 ，弱一致性，依赖版本控制。与约束传播的因果一致性类似，快照一致性约束版本，后者看到的所有组件状态都处于一致的时间点。通常两者都需要版本号或时间戳。一般来说，“弱”一致性是模糊的，而版本号提供了进行测量和控制的方法。

• Gossip 。跨节点传播元数据的一种常见方法是 Gossip，即在节点之间的通信中 piggyback 元数据，例如 Ceph。该方法也常用于节点心跳检测、成员资格（node membership）。 最终一致性 可以通过版本跟踪来实现。节点通常还需要联络 Consistent Core 以定期刷新可能过时的元数据。