夏季 Ceph 冒险：构建 B 树
您好！我是 Inktank 的一名暑期实习生。我的暑期项目是创建一个分布式、类似 B 树的键值存储，使用 librados 和 Ceph 对象存储，并支持多个写入者。在我的 上一篇博文中，我写了关于我创建的单客户端实现。在过去的几周里，我玩得很开心，并且在我的项目上学到了很多东西。我设计并实现了一种算法，使我的程序能够为任意数量的客户端工作。我还有更多的工作要做——特别是，我一直在修改算法，因为我在 Teuthology 测试 期间遇到瓶颈——但我的项目的核心已经完成。
我面临的问题是如何允许多个并发操作，而不会造成干扰，从而导致系统处于不一致的状态。Ceph 对象存储对单个对象提供原子操作，但我有时需要原子地更改多个对象。在拆分或合并叶子节点时，我必须更改叶子对象和索引对象，而不能让其他客户端看到中间状态。
我阅读的所有处理此问题的论文都假定要么是具有共享内存和锁定的单个计算机，要么是由专用服务器或 Paxos 集群管理的锁定服务。在锁定系统中，修改对象的进程（或客户端）确保对该对象的独占访问权限，并且所有其他尝试访问该对象的线程（或客户端）都会阻塞，直到释放锁。Ceph 没有锁定服务，因为这种设置成本很高。锁定系统是悲观的——也就是说，它假定竞争的可能性很高。这在具有共享内存的单个机器上是高效的，但在分布式系统上使用锁管理器复制该功能会创建一个瓶颈。在我的键值存储的可能用例中，很可能存在大量的键和很少的竞争。我需要设计一种乐观算法，利用这种竞争的可能性较低。
我需要设计一种算法，即使在拆分和合并的情况下也能保证以下内容
- 前向进展，这意味着每个客户端最终都会取得进展。特别是，没有操作组合会触发活锁或死锁。
- 原子性，这意味着写入要么完全完成，要么回滚。任何在中间状态下死亡的客户端都将被清理。
- 一致性，这意味着在每个操作之前和之后，系统都处于有效状态。
在 Sam 的建议下，我对可能的用例做出了以下假设
- 单个键和值将很小——确切的大小会有所不同，但我可以假设它们可以容纳在内存中。
- 为了确定什么构成一致性，用户只能通过我的结构访问键值存储（即，不能通过 librados）。
- 不允许重复键
- Ceph 对象存储是可靠的。
考虑到这些目标，我开始集思广益算法的想法。起初，我寻找简单的办法来重新排列现有代码中的步骤，以解决竞争条件。在与 Sam 讨论了其中一些想法并发现它们的缺陷后，我决定从头开始。我并排打开了几个文本文件，每个操作一个，并开始编写伪代码。经过几天提出想法、检查各种交错以查找竞争条件以及发现它们无法工作的原因后，我终于想出了一个算法，我无法识别任何竞争条件。我与 Sam 讨论了它，经过一番讨论，他同意它似乎是有效的。
Ceph 提供了许多对我的设计至关重要的有用功能。特别是，我利用以下功能
- Ceph 允许用户将多个写入操作或多个读取操作组合到一个原子事务中，只要它们都执行在单个对象上。我使用它来实现几个复杂的测试和设置操作。例如，我可以有一个事务，只有当“大小”xattr 设置为小于 2 * k 的数字时才执行写入。
- Ceph 允许用户编写在 OSD 而不是在客户端上运行的代码，这使得某些操作更快。例如，OSD 类可以扫描对象的整个键值映射（omap），并向客户端返回有关该映射的一些信息，而无需通过网络发送整个映射。
- 当然，Ceph 完全处理跨不同机器分配对象、创建副本以及确保事务是原子、一致、隔离和持久的挑战。
- Teuthology 是一个功能强大且相对易于使用的测试套件，它允许我在多个机器的集群上测试 Ceph 和我的程序配置的许多不同配置。Teuthology 提供的工具对我的基准测试非常宝贵。
我仍在改进我的算法，因为我在 Teuthology 中运行基准测试。一旦算法完成，我将发布完整的算法编写以及指向 github 上源代码的链接。
设计我的算法的第一个草案具有挑战性、有趣且有益的原因有很多。问题本身很有趣——我必须使用特定的工具来解决一个通用用例，而这些工具与我阅读的论文中用于解决类似用例的工具有很大不同。除了问题本身的吸引力之外，通过与其他开发人员的讨论来完善和纠正我的想法也具有很高的教育意义和有效性。开源模式充分利用了编码的这种协作方面，秉承“足够多的眼睛，所有的错误都是浅显的”的原则。Ceph 社区是理想的开源社区——充满了友好、耐心和聪明的开发人员，他们都致力于创建良好的代码。这些因素使我在 Ceph 开发中工作，以及在我的项目上工作，成为真正美妙的体验。
