POLARDB IMCI 白皮书 云原生HTAP 数据库系统 一 数据压缩和打包处理与数据更新

4.3 数据打包压缩和整理压缩

当部分package达到最大容量后，它会被转换为big package并压缩到磁盘上以减少空间消耗。压缩过程采用写时复制模式以避免访问冲突。也就是说，生成一个新package来保存压缩数据，而不对部分package进行任何更改。PolarDB-IMCI在压缩后更新元数据，将部分打包替换为新的package（即以原子方式更新指向新打包的指针）,对于不同的数据类型，列索引采用不同的压缩算法。数值列采用参考帧、delta编码和位压缩的组合，而字符串列使用字典压缩。此外，由于打包是不可变的，当活动事务大于所有VID时，即没有活动事务引用插入VID映射时，该打包的插入VID映射是无用的。在这种情况下，PolarDB-IMCI会删除行组中的插入VID映射以减少内存占用。

整理

删除操作可能在一个打包中设置删除VID，从而在该打包中留下空洞。随着无效行的数量随时间增加，扫描性能和空间利用效率会降低。PolarDB-IMCI定期检测和重新整理不足的打包，以保持列索引无效行的低水位。例如，少于一半有效行的稀疏包被选为不能进行package。然后，后台线程发起一个整理事务，其中包括大量的更新操作，针对每个迁移的有效行，将选定的打包的所有有效行重新追加到部分打包中。请记住，列索引的更新操作是就地进行的，因此旧行在整理期间甚至之后仍然可以进行前台操作，这使得更新操作不受阻塞。整理后选定的打包在没有活动事务访问时将被永久删除。

5 更新传播

在本节中，我们描述了我们在同步异构数据存储方面的努力。对OLTP的最小干扰是PolarDB-IMCI的一个高优先级目标。为了实现这个目标，PolarDB-IMCI中的更新传播是通过REDO日志实现的，消除了将额外逻辑日志持久化的开销。在REDO日志的基础上，PolarDB需要尽可能及时地保持RO节点的更新以保持数据的新鲜度。为此，我们引入了前置提交日志传送(CALS)来减少可见延迟，并引入了两阶段无冲突并行回放(2P-COFFER)机制来提高回放吞吐量。

5.1 提前提交日志传输 为了最小化性能干扰，在PolarDB-IMCI中，对RO节点的更新是完全异步的。鉴于此，为增强数据的新鲜度，PolarDB-IMCI使用了提前提交日志传输（CALS）技术，在提交之前将事务传送到其他节点。如图5所示，一个事务由多个日志项组成：最后一个日志项是提交或中止日志，前面的日志项是DML日志。每个日志项都被分配了一个日志序列号（LSN）。例如，事务TID为101的日志项有LSN 300∼302。日志项300和301是DML操作的日志，而日志项302包含了事务的决定（即中止）。当RW节点将一个日志项写入共享存储（即PolarFS）后，它通过广播其最新的LSN（在我们的例子中为299）通知RO节点。当接收到LSN时，RO节点立即从PolarFS中读取日志。然后，每个DML日志都会被解析为一个DML语句，并基于其TID存储在一个事务缓冲区中（每个事务一个缓冲单元）。整个过程不需要等待RW节点提交事务。例如，在日志项299中的最终提交之前，具有TID 100的事务中的DML操作将被传输。当RO节点读取一个提交日志项时，较早的DML语句已经被解析并作为逻辑操作交付到事务缓冲区中，使得PolarDB-IMCI能够立即重放这些DML操作。当读取一个中止日志项时，RO节点只需释放事务缓冲区，无需回滚数据。

5.2 两阶段无冲突并行回放 如前所述，PolarDB-IMCI不会为了更新传播而生成额外的逻辑日志，而是重用REDO日志。其原因是日志传送会使RW节点写入更多的日志项，从而影响OLTP性能。然而，从长远来看，使用REDO日志同步异构存储被认为几乎是不可能的[34]。这存在三个挑战：(1) REDO日志仅记录行存储中物理页面的变化，缺乏数据库级别或表级别的信息[42]（例如，RO节点不知道页面更改对应哪个表）。(2) REDO日志还包括由行存储本身引起的页面更改，而不仅仅是用户的DML操作，例如B+树的分裂/合并和页面整理。列索引不能应用这些日志，否则可能导致不一致。(3) REDO日志仅包含差异而不是完整的更新，以减少日志占用空间。

如图6所示，PolarDB-IMCI通过两个重放阶段解决了这些挑战。第一阶段是将REDO日志重放到RO节点的内存中的行存储的副本。在这个阶段，PolarDB-IMCI获取完整的信息，将REDO日志解析为逻辑DML语句。然后，第二阶段是将DML语句重放到列索引中。重放的性能对我们的系统至关重要。为了实现高性能，文献中提出了几种并行重放机制[6, 45, 46, 54]。这些工作要么以会话粒度进行并行重放，要么以事务粒度进行并行重放，并借助冲突处理辅助工具（例如锁或依赖图）或者乐观控制。与这些工作不同，PolarDB-IMCI提出了一种新的重放方法，即2P-COFFER，使得两个重放阶段都是无冲突的。在2P-COFFER中，第一阶段以页面粒度进行，而第二阶段以行粒度进行，以实现对不同页面/行的并发修改。修改相同页面/行但属于不同事务的日志条目被视为依赖项，应该按顺序重放。使用2P-COFFER，RO节点的重放吞吐量要远高于RW节点的OLTP吞吐量（图13）。

5.3 第一阶段：物理日志解析 如图7所示，PolarDB的REDO日志记录包含多个字段。为简单起见，我们以更新操作为例，其他类型的操作类似。

• TID是创建此记录的事务标识符。
• LSN表示日志中此记录的顺序。
• PageID标识此记录更新的行所属的物理页面。偏移字段（SlotID）进一步确定更新的行在页面上的位置。
• Data字段（差分日志）包含更新值与原始值之间的差异。在图6的左侧，第一阶段根据PageID将REDO日志分发给不同的工作者，并且每个工作者按照LSN的顺序重放页面更改以重现DML的细节。分发过程与第二阶段（第5.4节）类似，但是以页面粒度进行。对于更新类型的日志记录，工作者在重放过程中将生成一个删除DML和一个插入DML，因为列索引是被更新到非原地的。但是REDO日志的差分字段可能不包含主键（PK）信息，而删除DML需要主键信息因此，工作者根据PageID和偏移字段从PolarFS中获取旧行，并在申请条目之前使用旧行组装一个删除类型的DML。然后，工作者将差分字段应用于提取的行中以重放页面更改，并在应用后组装插入DML。为了真正将操作组合成逻辑DML，每个操作还必须补充其表模式。工作者通过记录在页面上的表ID来获取表模式信息。此外，工作者必须识别行存储本身生成的日志条目（例如，B+树分裂）。为了处理这个问题，工作者首先检查一个日志条目是否属于活动事务。如果不属于，则确认该条目不是由用户事务生成的。如果属于，则工作者进一步检查该条目的主键是否在活动事务中被重复插入（通过一个主键集合）。注意，重复的主键插入不是用户DML。因此，重复使用REDO日志会导致重放所有页面更改。作为一种优化，PolarDB-IMCI允许RO节点像RW节点一样维护行存储的缓冲池，以减少数据页面读取量。在我们的实践中，第一阶段的计算能力远远超过RW的日志产生能力。一方面，RO节点直接重现页面更改，无需重做事务的开销，如B+树遍历。另一方面，REDO日志在实际工作负载下始终作用于热页面，使得缓冲池的命中率接近99%。尽管缓冲池减少了用于OLAP的内存，但我们在这里进行了权衡，因为通过REDO日志减少对OLTP的干扰在我们的场景中是更高优先级的。
• 5.4 第二阶段：逻辑DML应用 REDO日志的LSN顺序确保了日志重放的基本前提，这意味着在RO节点中的更改可以按照与RW相同的顺序进行。第一阶段打破了这个顺序。因此，在转换之后，后台线程将根据关联日志条目的LSN对DML进行排序。然后，后台线程将DML插入到事务缓冲单元中。
• 在第二阶段，调度程序将一批事务分发给多个工作者，以并行的方式对列索引进行修改。分发是逐行进行的，来自单个事务的DML语句将被分配给多个工作者进行重放。对于一个DML语句，调度程序通过对行主键的哈希值取模来分配指定的工作者。因此，即使这些DML语句属于不同的事务，修改相同行的DML语句将按照提交顺序被分配给相同的工作者。调度程序按照提交顺序处理每个事务，确保对同一行的不同修改按照顺序传递给相同的工作者，从而保证一致性。每个工作者按照§4.2中描述的步骤依次重放每个DML语句，并将更改批量提交到列索引中。
• 图6的右侧示例演示了两个工作者（W1和W2）如何同时重放两个事务（T1和T2）。T1分别执行插入（1，“A”）和插入（2，“D”）。T2执行更新（2，“B”）和插入（3，“C”）。插入（2，“D”）和更新（2，“B”）按照T1和T2的提交顺序分配给W2。W1按顺序执行这两个DML语句，没有并发冲突。

• 5.5 处理大事务 到目前为止，我们已经介绍了PolarDB-IMCI的更新传播，但还有一个问题。如5.1所述，CALS从PolarFS预取日志条目到事务缓冲区。因此，如果一个事务包含太多的操作，它的事务缓冲区单元可能会消耗大量的内存。 为了避免过度的内存消耗，PolarDB-IMCI对大事务进行预提交：当事务缓冲单元中的DML语句数量达到给定阈值时，将进行预提交。预提交的基本思想是将更新写入到具有无效插入和删除VID的部分数据包中，使得更新在暂时不可见。预提交的具体步骤如下。首先，为当前事务缓冲区中的所有行请求连续的RID，并保存此RID范围。重要的是要注意，在预提交阶段，全局RID定位器尚不能更改，以避免未提交事务的暴露。因此，PolarDB-IMCI创建一个临时的RID定位器，而不是更新RID全局定位器以缓存新的PK到RID映射关系。然后，PolarDB-IMCI将更新写入到部分数据包中，同时将插入和删除VID设置为无效以使其不可见。最后，PolarDB-IMCI释放事务缓冲单元使用的内存。 当大事务提交时，PolarDB-IMCI将临时RID定位器合并到全局RID定位器中，并使用事务提交序列号纠正无效的VID（在保存的RID范围内）。否则，如果大事务中止，则临时定位器将被清除。部分数据包中剩余的预提交行无效，并将在后台的压缩线程中稍后消除。