3. 回滚段设计与MVCC
1） 回滚段
旧版本数据会集中在回滚段的undo目录中，为了减少读写冲突，旧版本数据（回滚记录）采用追加写的方式写入数据目录的undo目录下。这样旧版本数据的读取和写入不会发生冲突，同一个事务的旧版本数据也会连续存放，便于进行回滚操作。为了减少并发写入时的竞争，undo目录空间被划分成多个逻辑区域（UndoZone，回滚段逻辑区域）。线程会在自己的逻辑区域上进行分配，与其他线程完全隔离，从而写入旧数据分配空间时就不会有额外的锁开销。UndoZone还可以按照CPU的NUMA核进行划分，每个线程会从当前的NUMA核上的UndoZone进行分配，进一步提升分配效率。在分配undo空间时会按照事务粒度进行记录，旧版本数据一旦确认没有事务进行访问，就会进行回收。
为了在回滚段的空间寻址，回滚记录使用8字节的指针来进行寻址，如图4-14所示。
其中各个字段的含义如下：
（1） zoneId：占用20bit，表示逻辑区域的ID。
（2） blockId：占用31bit，表示块号，默认为8k。
（3） offset：占用13bit，表示块内偏移。
旧版本的数据采用回滚记录的格式存入回滚段中，其中回滚记录的格式如下所示：
…
UndoRecordHeader whdr_;
UndoRecordBlock wblk_;
UndoRecordTransaction wtxn_;
UndoRecordPayload wpay_;
UndoRecordOldTd wtd_;
UndoRecordPartition wpart_;
UndoRecordTablespace wtspc_;
StringInfoData rawdata_;
}
其中，除了rawdata_代表了旧版本数据，其他成员均为结构体，下面对每个结构体分别进行说明。
whdr_成员由下面的结构组成：
TransactionId xid;
CommandId cid;
Oid reloid;
Oid relfilenode;
uint8 utype;
uint8 uinfo;
} UndoRecordHeader;
各个字段的含义如下。
（1） xid：生成此回滚记录的事务ID，用于检查事务的可见性。“2）MVCC”小节有介绍。
（2） CID（Command ID，命令ID）：生成此回滚记录的命令ID，用于判断可见性。
（3） reloid：relation对象的ID，回滚时需要。
（4） relfilenode：relfilenode对象的ID，回滚时需要。
（5） utype：操作类型，像UNDO_INSERT、UNDO_DELETE、UNDO_UPDATE等。
（6） uinfo：控制字段，用来判断后续的结构是否存在，用来减少回滚记录的占用空间。
wblk_成员由下面的结构组成：
UndoRecPtr blkprev;
BlockNumber blkno;
OffsetNumber offset;
} UndoRecordBlock;
（1） blkprev：指向同一个block前一条回滚记录，用于回滚和事务可见性。“2）MVCC”小节有介绍。
（2） blkno：block number（块号）。
（3） Offset：修改的tuple在row pointer中的偏移。
wtxn_成员由下面的结构组成。
UndoRecPtr prevurp;
} UndoRecordTransaction;
prevurp：当一个事务的回滚记录跨越两个UndoZone时，后续的回滚记录使用此指针指向前一条回滚记录。
wpay_成员由下面的结构组成。
UndoRecordSize payloadlen;
}
payloadlen：rawdata_的长度。
wtd_成员由下面的结构组成。
TransactionId oldxactid;
} UndoRecordOldTd;
oldxactid：旧版本数据里事务目录的事务ID。
wpart_成员由下面的结构组成。
Oid partitionoid;
} UndoRecordPartition;
partitionoid：分区表的分区对象OID。
wtspc_成员由下面的结构组成。
Oid tablespace;
} UndoRecordTablespace;
tablespace：表空间的OID。
回滚段使用事务目录来记录每个事务分配的undo空间，便于事务回滚和回收。事务发生回滚时，会读取事务目录中记录的undo空间的起始位置，再读取undo空间中的回滚记录进行回滚操作，其中回滚记录中的字段如下：
TransactionId xactId_;
UndoRecPtr startUndoPtr_;/*事务分配的undo空间开始*/
UndoRecPtr endUndoPtr_;/*事务分配的undo空间结束*/
uint8 info_;/*标记：如事务回滚状态*/
Oid dbId_;/*数据库对象ID*/
}
（1） xactId：事务ID。
（2） startUndoPtr：事务分配的undo空间开始位置。
（3） endUndoPtr：事务分配的undo空间结束位置。
（4） info_：标记值，如事务回滚状态。
（5） dbId：数据库对象ID。
回滚段提供分配undo空间和更新事务目录的接口，主要接口如表4-21所示。
以ustore的删除操作为例，undo空间分配流程如下。
（1） UheapDelete作为ustore的删除接口，会调用UHeapPrepareUndoDelete函数准备回滚记录（undo record）。UHeapPrepareUndoDelete函数会填充回滚记录的各个字段（其中旧数据会设置到回滚记录的raw data字段上），再调用PrepareUndoRecord函数分配undo空间。PrepareUndoRecord函数调用“undo::AllocateUndoSpace”函数分配undo空间，再读取对应的回滚记录到缓冲池中。AllocateUndoSpace函数不仅会为回滚记录分配空间（使用“UndoZone::AllocateSpace”函数），如果是事务的第一条回滚记录，还会调用“UndoZone::AllocateSlotSpace”函数为事务目录分配空间。AllocateSpace函数会进行判断，如果回滚记录超过当前undo file的大小，就扩展当前的undo file，AllocateSlotSpace函数的逻辑类似。
（2） UheapDelete函数调用InsertPreparedUndo函数，将准备好的回滚记录追加写到缓冲池中的回滚段页面。
（3） UheapDelete函数调用UpdateTransactionSlot，记录下该事务分配的undo空间起始、事务ID、数据库ID。如果是事务的第一次更新，会从事务目录空间分配新的事务目录再进行更新。
undo空间需要回收回滚记录来保证undo空间不会无限膨胀，一旦事务id小于当前快照中最小的Xmin（oldestXmin），回滚记录中的旧版本数据就不会被访问，此时就可以对回滚记录进行回收。
如前述描述undo空间中的回滚记录按照事务ID递增的顺序存放在UndoZone中，回收的条件如下所示。
（1） 事务已经提交并且小于oldestXmin的undo空间可以回收。
（2） 事务发生回滚但已经完成回滚的undo空间可以回收。
如图4-15所示，UndoZone1中回收到小于oldestXmin的已提交事务16068，UndoZone2中回收到16050，UndoZone m回收到16056。而UndoZone n回收到事务16012，而事务16014待回滚但未发生回滚，因此UndoZone n回收事务id上限只到16014。其他zone的上限是oldestXmin，oldestXidInUndo会取所有undozone上的上限最小值，因此oldestXidInUndo等于16014。undo回收主要函数如表4-22所示。
2） MVCC
ustore的可见性检查和astore类似，将快照CSN和元组删除和插入事务的CSN进行比较，判断元组是否可见。ustore和astore使用同一套事务管理机制和快照管理机制。
ustore和astore最大的区别在于astore会在页面上保留旧版本数据，而ustore在将旧版本数据放到回滚段统一存放。在需要获取旧版本数据时，astore可以直接从tuple的头部读取到元组的插入和删除的事务号(XID)，来判断元组的可见性。但是ustore需要从回滚段里读取旧版本的事务信息，来判断旧版本是否可见。由于从回滚段中读取旧版本数据存在相对昂贵的开销，ustore通过一系列的优化手段来避免从回滚段中读取旧版本数据。
ustore在获取元组时，会先检查对应的事务目录。事务目录分成有效和无效两种。当事务目录是有效的，ustore直接就会得到元组上最新的事务。
如果事务目录被冻结（FROZEN），意味着元组已经在所有的事务中都会可见。如果事务目录中的事务id小于oldestXidInUndo，意味着元组已经足够旧在所有事务中都可见。同时会把事务目录置成冻结，来加速后续的查询。
如果元组被标记有一个无效事务目录，意味着修改元组的事务已经提交，并且比当前的事务目录中的事务旧。此时ustore会使用事务目录中的事务进行可见性判断。如果可见，意味着修改元组的事务更已经可见，就不需要从undo目录中再读取事务信息。
元组不可见的场景，ustore会从undo目录中读取回滚记录中的旧版本数据查找元组。例子如图4-16所示。查找tbl表中c1=1的数据项，从索引中读取到数据项位于block 1和offset 2，使用UHeapTupleFetch函数再从block 1中查询到元组，需要判断该元组的可见性。
（1） 从元组的TD读到ITL2，和astore类似，根据CSN的大小，判断TD2中的XID不可见，需要使用GetTupleFromUndo函数读取回滚记录。
（2） GetTupleFromUndo函数调用GetTupleFromUndoRecord函数读取回滚记录，使用InplaceSatisfyUndoRecord函数判断其中的block 1和offset 2是满足要求的元组。但是XID=1610可以判断出当前页面的tuple不可见，ustore继续查询更老的版本。由于旧元组的TD 1和当前的TD 2不一致，使用UHeapUpdateTDInfo从TD 2 undo链条进行切换，根据旧元组的TD 1找到当前的undo指针找到前一次修改。
（3） 再次读取到回滚记录，其中的block 1和offset 1并非要找的元组，ustore继续查询更老的版本，根据blkprev指针读取前一次修改。
（4） 读取到回滚记录，其中的block 1和offset 3并非要找的元组，ustore继续查询更老的版本，根据blkprev指针读取前一次修改。
（5） 读取到回滚记录，其中的block 1和offset 2是要求的元组，ustore判断可见性。根据CSN的大小，事务可见。因此前一次命中的元组可见，即(1, abc)可见，因此查找到元组的c2等于abc。
