在页面维护期间保持行标识符的稳定性

Source: Dev.to

请提供您希望翻译的完整文本（文章正文），我将为您保留原始的链接并把内容翻译成简体中文。这样可以确保所有格式、代码块和技术术语都得到正确处理。

介绍

圣诞节、新年、一周的滑雪旅行、与家人相处、在阅读 How to Take Smart Notes（link）后，将我的 Obsidian 笔记库完整重组为 Zettelkasten 卡片盒——所有这些导致我在这个项目上的进展远低于预期，尤其是在我三周的寒假期间。尽管如此，还是有一些进展。

我仍然在存储系统中，处理堆的槽页，并且在数据库引擎处理某些页面维护操作的方式上遇到了一些有趣的事情。

Source: …

行 ID

大多数系统（虽然我主要了解 SQL Server 的处理方式）都会使用 行 ID 在内部标识一行。

行 ID 可以被视为任何能够让系统唯一识别单行的标识符。引擎可能需要在多个位置存储此标识符，但最典型的例子是非聚集（或二级）索引。在非聚集索引中，每个条目都包含指向其所属完整行的指针。当基于该索引检索行时，会使用行标识符来获取完整的行（如果需要的话）。

SQL Server 的实现方式

在 SQL Server 中，用于非聚集索引的行 ID 取决于源表，通常称为 row bookmark value（Delaney 等，2013，第 308 页）：

• Clustered table – 非聚集索引使用聚集键作为行标识符。
• Heap – 非聚集索引使用物理行定位器来标识行。

今天我们只关注堆（heap），因为聚集表是完全不同的情况。该物理行定位器（Microsoft 称为 RID）是一个 8 字节的值，由三个段 FileID:PageID:SlotID 组成，具体如下：

关键点： 行 ID 包含行的槽号，并且该行 ID 出现在所有非聚集索引中。这就引出了本文背后的概念。

稳定的槽位编号

因为索引将槽位 ID 作为行标识符的一部分，系统必须保证在内部页面维护操作期间，行保持其槽位编号。如果行被重新分配到其他槽位，则每个非聚集索引也都需要更新——这是一项代价高昂的操作。

该规则最直接的影响体现在页面压缩上，但确保其实现的过程始于删除操作。

行删除

抽象化通过槽数组访问行的一个优势是，某些操作（例如删除）变得非常简单。类似文件系统，从槽页中删除 并不需要触及实际的行数据；只需使指向该行的槽失效，使该行的字节不可达即可。

在我的实现中，使槽失效意味着将其 offset 和 length 字段都设为 0，而保持头部中的槽计数不变：

initial: [(96, 100), (196, 50), (246, 50)]
slot_count = 3

// delete slot index 1 (196, 50)
after:   [(96, 100), (0, 0), (246, 50)]
slot_count = 3

为什么这符合 稳定槽编号 规则

• 如果我们把槽从数组中完全移除（并递减 slot_count），就必须把后面的槽向下移动，这会破坏规则。
• 如果我们把槽设为 (0,0) 但 递减了 slot_count，最后一个有效槽将变得不可达。

因此，这条规则大大简化了实现。删除操作唯一更复杂的部分是我添加的一个小优化：如果被删除的行在页面上物理上是最后一行（即它位于数据区的末尾），我们可以通过将 free_start 指针移动到前一行的末尾来避免页面碎片化。在这种“理想情况”下，头部的 can_compact 标志不会被置位，表明碎片化尚未开始。

我最初在 Rust 实现中遗漏了这个优化（虽然在另一个显示器上打开的 Java 版本中已经存在）。我在设置插入测试时才意识到这一点。起初我把这些场景标记为“技术上可能，但无效”，但进一步思考后发现，只有在实现了此优化的情况下，它们才实际上是不可能的。你可以在这里看到我标记为不可能的注释：
GitHub commit comment。

Source: …

页面压缩

页面压缩是指在页面内部重新组织记录以消除碎片的过程。虽然所有页面最初都是紧密排列的数组，行占据连续的字节块，但删除和更新操作会在行之间产生小的间隙。于是，页面的空闲空间计数器可能很高，却没有足够大的连续区域来容纳新行。

压缩的工作方式是将所有现有行相互靠拢，从而消除任何间隙。它通常是惰性执行的，仅在插入操作找不到足够大的碎片来放置新行时才进行。

我的实现可能不是最优的，但能工作。我分配了一个新的字节数组，按顺序复制行，并相应地更新槽位偏移。（其余实现遵循上文描述的稳定槽位号原则。）

数据压缩概述

数据段的大小计算为 free_start - header_size。
要压缩页面，我们：

1. 遍历槽位数组。
2. 对每个 有效 槽位，将其行复制到新的字节数组中，按顺序打包行。
3. 更新槽位的偏移值，使其指向行的新位置。

处理完所有槽位后，我们用新的字节数组覆盖原始数据段。尾部的字节（即被碎片占用的部分）会变成 0。

注意： 更复杂的原位算法可以避免分配最多 4 KB 的临时数组，但这种优化属于“锦上添花”，可留待以后实现。当前实现满足最重要的要求：稳定的槽位号 得以保留。

原来的 Java 版本会分配一个全新的页面，只复制有效槽位，然后交换页面的字节数组。虽然这样方便，但破坏了稳定槽位规则——这是我们在一年后与同事讨论该过程时才发现的错误。因此才有了上述的重写。

结尾

这基本上就是这篇文章的全部内容，结果比我预期的要长。正如我在开头提到的，过去几周进展缓慢，但假期结束后情况应该会好转。

我也在构建更好的测试基础设施。我的目标是 在编写代码的同时 添加测试，避免以后出现大量未完成的场景。我正在探索 Rust 的特性如何帮助创建辅助工具，使得设置任何测试场景都变得轻而易举；我会在未来的文章中详细介绍。

另一个让我忙碌的领域是插入算法。Java 实现相当臃肿，所以我一直在把它拆分成更小的模块，进行清理，并尽可能全面地用测试覆盖它们。

接下来的步骤

• 完成与堆页面相关的工作。
• 决定是继续留在存储引擎（例如索引页面和 B+‑树）还是转向其他模块。

我倾向于后者。这个过程故意放慢速度——不是因为语言差异，而是因为我不断重新审视 Java DB 的实现细节，寻找改进并修复不足。构建一个跨所有层的小型可工作原型应该能让未来的决策更容易，并帮助我更快达到 MVP。就个人而言，我希望尽快拥有一个功能完整的原型。

参考文献

• Delaney, K., Beauchemin, B., Cunningham, C., Kehayias, J., Freeman, C., Nevarez, B., & Randal, P. S. (2013). Microsoft SQL Server 2012 Internals. https://www.microsoftpressstore.com/store/microsoft-sql-server-2012-internals-9780735658561