HOT Update
时隔一年零二个月的更新
简单介绍
常规更新
我们先来看一下正常情况下，对表的更新是怎么完成的。
首先我们创建表和对应的索引
CREATE TABLE hot(id integer, s char(2000)) WITH (fillfactor = 75);
CREATE INDEX hot_id ON hot(id);
CREATE INDEX hot_s ON hot(s);我们同时创建两个函数用于输出页面和索引的信息
CREATE FUNCTION heap_page(relname text, pageno integer)
RETURNS TABLE(ctid tid, state text, xmin text, xmax text, hhu text, hot text, t_ctid tid)
AS $$
SELECT (pageno,lp)::text::tid AS ctid,
CASE lp_flags
WHEN 0 THEN 'unused'
WHEN 1 THEN 'normal'
WHEN 2 THEN 'redirect to '||lp_off
WHEN 3 THEN 'dead'
END AS state,
t_xmin || CASE
WHEN (t_infomask & 256) > 0 THEN ' (c)'
WHEN (t_infomask & 512) > 0 THEN ' (a)'
ELSE ''
END AS xmin,
t_xmax || CASE
WHEN (t_infomask & 1024) > 0 THEN ' (c)'
WHEN (t_infomask & 2048) > 0 THEN ' (a)'
ELSE ''
END AS xmax,
CASE WHEN (t_infomask2 & 16384) > 0 THEN 't' END AS hhu,
CASE WHEN (t_infomask2 & 32768) > 0 THEN 't' END AS hot,
t_ctid
FROM heap_page_items(get_raw_page(relname,pageno))
ORDER BY lp;
$$ LANGUAGE SQL;
CREATE FUNCTION index_page(relname text, pageno integer)
RETURNS TABLE(itemoffset smallint, ctid tid)
AS $$
SELECT itemoffset,
ctid
FROM bt_page_items(relname,pageno);
$$ LANGUAGE SQL;我们先插入一条数据并更新三次
INSERT INTO hot VALUES (1, 'A');
UPDATE hot SET s = 'B';
UPDATE hot SET s = 'C';
UPDATE hot SET s = 'D';这时候我们查看页面状态
postgres=# SELECT * FROM heap_page('hot',0);
ctid | state | xmin | xmax | hhu | hot | t_ctid
-------+--------+---------+---------+-----+-----+--------
(0,1) | normal | 739 (c) | 740 (c) | | | (0,2)
(0,2) | normal | 740 (c) | 741 (c) | | | (0,3)
(0,3) | normal | 741 (c) | 742 | | | (0,4)
(0,4) | normal | 742 | 0 (a) | | | (0,4)由于设置了 fillfactor，下一条更新就会触发页面内的vacuum
postgres=# UPDATE hot SET s = 'E';
UPDATE 1
postgres=# SELECT * FROM heap_page('hot',0);
ctid | state | xmin | xmax | hhu | hot | t_ctid
-------+--------+---------+-------+-----+-----+--------
(0,1) | dead | | | | |
(0,2) | dead | | | | |
(0,3) | dead | | | | |
(0,4) | normal | 742 (c) | 743 | | | (0,5)
(0,5) | normal | 743 | 0 (a) | | | (0,5)
(5 rows)在vacuum过程中 (0, 1) (0, 2) 和 (0, 3) 都被清理了，并且 (0,4) 被向后移动以合并空间
查看索引，发现有5条记录，也就是说，每次更新都需要将新纪录插入索引中
postgres=# SELECT * FROM index_page('hot_s',1);
itemoffset | ctid
------------+-------
1 | (0,1)
2 | (0,2)
3 | (0,3)
4 | (0,4)
5 | (0,5)
(5 rows)热更新（）
hot只是个缩写，并不是表示“热”的意思，这里只是为了简略标题（其实我第一眼确实以为是热更新
上述的做法有它的坏处
- 对于每次更新，表上所有的索引都需要被更新，即使更新的字段上不涉及任何索引。
- 索引上的频繁插入对于使用B+树实现的索引来说，大量的冗余数据会带来性能上的影响，特别是节点的分裂操作。
直观上来想，如果更新的行不会对当前的索引产生影响，其实我们不需要向索引里插入新条目，这就是 Hot(Heap-Only Tuple) Update 的思想。
我们添加新的标志位以识别这种 tuple，具体的作用我们通过一个例子来说明：
#define HEAP_HOT_UPDATED 0x4000 /* tuple was HOT-updated */
#define HEAP_ONLY_TUPLE 0x8000 /* this is heap-only tuple */首先我们删掉一个索引，然后清空表，之后再进行插入和修改
DROP INDEX hot_s;
TRUNCATE TABLE hot;
INSERT INTO hot VALUES (1, 'A');
UPDATE hot SET s = 'B';这时候我们再看一下表结构
postgres=# SELECT * FROM heap_page('hot',0);
ctid | state | xmin | xmax | hhu | hot | t_ctid
-------+--------+---------+-------+-----+-----+--------
(0,1) | normal | 746 (c) | 747 | t | | (0,2)
(0,2) | normal | 747 | 0 (a) | | t | (0,2)
(2 rows)我们发现:
- 旧的数据被加上了
HEAP_HOT_UPDATED的标志，表示其被一条 HOT 更新了，更新它的是(0,2) - 新的数据被加上了
HEAP_ONLY_TUPLE的标志，表示其是一条 HOT 数据，它没有被更新
后续的更新也会串连到旧数据上
postgres=# UPDATE hot SET s = 'C';
UPDATE 1
postgres=# UPDATE hot SET s = 'D';
UPDATE 1
postgres=# SELECT * FROM heap_page('hot',0);
ctid | state | xmin | xmax | hhu | hot | t_ctid
-------+--------+---------+---------+-----+-----+--------
(0,1) | normal | 746 (c) | 747 (c) | t | | (0,2)
(0,2) | normal | 747 (c) | 748 (c) | t | t | (0,3)
(0,3) | normal | 748 (c) | 749 | t | t | (0,4)
(0,4) | normal | 749 | 0 (a) | | t | (0,4)
(4 rows)好像除了这个也没什么区别嘛，我们再看看索引
postgres=# SELECT * FROM index_page('hot_id',1);
itemoffset | ctid
------------+-------
1 | (0,1)
(1 row)只有一条数据，说明后续的更新确实没有影响索引
这就是HOT给我带来的自信这就是 Hot Update 的作用，我们会对被更新的 tuple 加上 HEAP_HOT_UPDATED 标志，对插入的 HOT 加上 HEAP_ONLY_TUPLE 标志，这些数据就被串了起来，称为 Hot chain，在索引扫描时，我们能够找到 chain 的头部，随后顺着链向后遍历就能获取最新的数据。之后的清理工作也是以 chain 为单位进行。
In-page vacuum
对 Hot 数据的 vacuum 操作会略有些不同，我们看一下例子：
我们在前述的基础上再更新一次数据就能触发 vacuum
postgres=# UPDATE hot SET s = 'E';
UPDATE 1
postgres=# SELECT * FROM heap_page('hot',0);
ctid | state | xmin | xmax | hhu | hot | t_ctid
-------+---------------+---------+-------+-----+-----+--------
(0,1) | redirect to 4 | | | | |
(0,2) | normal | 750 | 0 (a) | | t | (0,2)
(0,3) | unused | | | | |
(0,4) | normal | 749 (c) | 750 | t | t | (0,2)
(4 rows)马老师发生甚么事了
(0,2)和(0,3)被清理了，注意上面的例子和这里状态的不同(0,1)作为头节点仍然保留着，但是状态设为了redirect- 新的数据写入在
(0,2)上，因为没有索引条目指向它，旧的空间不需要了(unused)
这就是清理需要完成的事情：清理链表上不需要的 tuple，然后更新头节点并指向最新的数据，相比常规更新，vacuum能直接清理出可用的空间，而不需要等待对索引的修建
限制
需要注意的是，HOT Update 只针对单页面内的更新，不能跨页，下面的实验就可以说明这一点：在新页面插入的数据仍然需要插入索引。
postgres=# UPDATE hot SET s = 'I';
UPDATE 1
postgres=# UPDATE hot SET s = 'J';
UPDATE 1
postgres=# INSERT INTO hot VALUES (2, 'D');
postgres=# SELECT * FROM heap_page('hot',0);
ctid | state | xmin | xmax | hhu | hot | t_ctid
-------+---------------+---------+---------+-----+-----+--------
(0,1) | redirect to 4 | | | | |
(0,2) | normal | 750 (c) | 751 (c) | t | t | (0,3)
(0,3) | normal | 751 (c) | 752 | t | t | (0,5)
(0,4) | normal | 749 (c) | 750 (c) | t | t | (0,2)
(0,5) | normal | 752 | 0 (a) | | t | (0,5)
(5 rows)
postgres=# SELECT * FROM index_page('hot_id',1);
itemoffset | ctid
------------+-------
1 | (0,1)
2 | (1,1)
(2 rows)相关的结构体
t_infomask2 中也加入了新的标志位，上面已提及
#define HEAP_HOT_UPDATED 0x4000 /* tuple was HOT-updated */
#define HEAP_ONLY_TUPLE 0x8000 /* this is heap-only tuple */ItemIdData 的 lp_flags 可以确定 item 是否是用于 HOT redirect 的
#define LP_UNUSED 0 /* unused (should always have lp_len=0) */
#define LP_NORMAL 1 /* used (should always have lp_len>0) */
#define LP_REDIRECT 2 /* HOT redirect (should have lp_len=0) */
#define LP_DEAD 3 /* dead, may or may not have storage */Hot Update 触发时机
在 heap_update 时，会判断是否要进行 HOT 更新，条件如下：
- 此次 update 没有修改任何索引所涉及的列（通过检查
modified_attrs和hot_attrs两个 bitmap 的交集确定） - 页面未满，即
!PageIsFull(page)，这里的PageIsFull不代表这个页面没有空间写入了，只是剩余空间较少 - 最后判断 tuple 是否插入在原页面上，即
newbuf == buffer
根据是否要进行 HOT 更新设置给新旧数据加上/去除相应的 tag
if (use_hot_update)
{
HeapTupleSetHotUpdated(&oldtup); // Mark HEAP_HOT_UPDATED
HeapTupleSetHeapOnly(heaptup); // Mark HEAP_ONLY_TUPLE
HeapTupleSetHeapOnly(newtup); // Mark HEAP_ONLY_TUPLE
}
else
{
HeapTupleClearHotUpdated(&oldtup); // Clear HEAP_HOT_UPDATED
HeapTupleClearHeapOnly(heaptup); // Clear HEAP_HOT_UPDATED
HeapTupleClearHeapOnly(newtup); // Clear HEAP_HOT_UPDATED
}页面清理
在更新 heat_update 或删除数据 heap_delete 的时候，会通过 PageSetPrunable(page, xid) 尝试更新页面的 pd_prune_xid
之后在 heap_page_prune_opt 中，该值用于判断是否需要进行清理：GlobalVisTestIsRemovableXid(vistest, prune_xid)
如果页面空间不足并且需要清理，就会调用 heap_page_prune 清理 HOT Update 数据
确定 tuple 状态
清理的第一步就是检查每一条 tuple 的状态，首先我们会反向扫描并使用 heap_prune_satisfies_vacuum 检查每一条 flag 为 LP_NORMAL 的 tuple，记录其状态在 prstate.htsv 中。
状态有如下五种：
/* Result codes for HeapTupleSatisfiesVacuum */
typedef enum
{
HEAPTUPLE_DEAD, /* tuple is dead and deletable */
HEAPTUPLE_LIVE, /* tuple is live (committed, no deleter) */
HEAPTUPLE_RECENTLY_DEAD, /* tuple is dead, but not deletable yet */
HEAPTUPLE_INSERT_IN_PROGRESS, /* inserting xact is still in progress */
HEAPTUPLE_DELETE_IN_PROGRESS /* deleting xact is still in progress */
} HTSV_Result;代码里关于这一点有一段注释，但是我还是不理解为何要单独在一个循环里计算状态，而不能和下一个循环合并
- This is required for correctness to deal with cases where running HTSV
- twice could result in different results (e.g. RECENTLY_DEAD can turn to
- DEAD if another checked item causes GlobalVisTestIsRemovableFullXid()
- to update the horizon, INSERT_IN_PROGRESS can change to DEAD if the
- inserting transaction aborts, ...). That in turn could cause
- heap_prune_chain() to behave incorrectly if a tuple is reached twice,
- once directly via a heap_prune_chain() and once following a HOT chain.
heap_prune_satisfies_vacuum 的主要流程如下：
- 首先通过
HeapTupleSatisfiesVacuumHorizon确定 tuple 的状态，该函数判断条件很多，大致流程如下图所示，注意流程里忽略了 multi xact 的部分（因为还没看） - 如果状态不为
HEAPTUPLE_RECENTLY_DEAD直接返回 - 如果已经计算过
old_snap_xmin并且xmax(dead_after)在其之前，返回HEAPTUPLE_DEAD，否则返回原结果（这里和old_snapshot_threshold有关，不太明白） - 根据
GlobalVis*判断是否可以清理，可以则返回HEAPTUPLE_DEAD - 如果需要计算
old_snap_xmin，计算其值，然后判断（这里也和old_snapshot_threshold有关）
Hot chain清理
之后我们再进行一次正向扫描，所有被清理的 tuple 会记录在 prstate->nowunused 和 prstate->nowdead 中；prstate->marked 避免重复处理
对于每个 tuple：
- 如果
prstate.marked[offnum] == true，跳过，否则获取ItemID - 如果
ItemID的 tag 为LP_UNUSED || LP_DEAD，跳过 - 调用
heap_prune_chain对从当前下标开始的 chain 进行清理
heap_prune_chain 的逻辑如下：
- 由于我们只需要从每个 Hot chain 的起点开始进行清理，因此遇到
HEAP_ONLY_TUPLE的 tuple 不需要进行遍历，因为它一定不是起点。- 如果其满足
HEAPTUPLE_DEAD和!HeapTupleHeaderIsHotUpdated，可以直接移除它，并返回。 - 这种情况可能发生在 HOT Update 被 abort 的时候，此时其不在任何 Hot chain 中，PG将其称作
XMIN_INVALID heap-only tuple - 移除时我们需要推进
prstate->latestRemovedXid（这里不太明白）
- 如果其满足
- 从当前下标开始遍历，获取到的 tuple 记录在
chainitems中- 如果当前 tuple 已经被处理，或者状态为
LP_UNUSED || LP_DEAD，退出循环 - 如果当前
ItemID状态为LP_REDIRECT，加入chainitems，跳转到其指向的位置，回到步骤1 - 如果上一次的
xmax不等于当前的xmin，退出循环 - 将当前 tuple 加入
chainitems - 如果 tuple 的状态为
HEAPTUPLE_DEAD，记录最后一次删除位置latestdead；如果状态也不是HEAPTUPLE_RECENTLY_DEAD，退出循环 - 如果当前 tuple 不是 HOT updated，说明遍历到了末尾，退出循环，否则根据
ct_id跳转回到步骤1
- 如果当前 tuple 已经被处理，或者状态为
- 如果
latestdead值有效，将chainitems中其之前的 tuple 加入nowunused； - 如果
chainitems最后一个元素也为 dead 状态，将链头标记为nowdead，否则对链头进行 redirect - 如果链中只有一个
LP_REDIRECT的 tuple，说明它没有指向任何有效的后继，直接标记为nowdead
可以看到，对于非 HOT Update 数据来说，整个流程不会对它有影响
在扫描完整个页面后，如果存在需要清理和更新的 tuple，执行 heap_page_prune_execute 进行真正的更新，通过 PageRepairFragmentation 清理空间，将页面置脏并清除 PD_PAGE_FULL 的标记，写入必要的日志。
nowunused和nowdead的区别在于：
- 在
heap_page_prune_execute中，如果存在unused的 item，会给页面加上PD_HAS_FREE_LINES的标志- 由于 dead tuple 可能仍然会被索引所引用，因此暂时不能移除
TODO
-
关于 HOT Update 的日志上有什么改动还没有去了解，这里有极简说明 PostgreSQL HOT(Heap Only Tuple) 技术
-
MultiXact，具体机制以及存放数据的格式还没有看，借用阿里数据库月报的一段话来介绍什么是 MultiXact
对于FOR UPDATE和FOR NO KEY UPDATE锁，可以方便通过Tuple上的xmax判断谁持有锁，而对于FOR SHARE和FOR KEY SHARE，一个Tuple上面可能会被多个事务加锁，Tuple上动态维护这些事务代价很高，为了便于维护这些事务状态，PG引入了MultiXact机制，把多事务记录到独立buffer和文件中，如图所示。当触发多事务机制时，会生成一个新的MultiXactId，把当前Tuple对应的所有锁成员放在MultiXactMemberPage中，并把新的MultiXactId保存在xmax中。