PostgreSQL HOT Update解析
本文最后更新于 485 天前,其中的信息可能已经有所发展或是发生改变。

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只是个缩写,并不是表示“热”的意思,这里只是为了简略标题(其实我第一眼确实以为是热更新

上述的做法有它的坏处

  1. 对于每次更新,表上所有的索引都需要被更新,即使更新的字段上不涉及任何索引。
  2. 索引上的频繁插入对于使用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)

我们发现:

  1. 旧的数据被加上了 HEAP_HOT_UPDATED 的标志,表示其被一条 HOT 更新了,更新它的是 (0,2)
  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)

马老师发生甚么事了

  1. (0,2)(0,3) 被清理了,注意上面的例子和这里状态的不同
  2. (0,1) 作为头节点仍然保留着,但是状态设为了 redirect
  3. 新的数据写入在 (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 */

ItemIdDatalp_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 更新,条件如下:

  1. 此次 update 没有修改任何索引所涉及的列(通过检查 modified_attrshot_attrs 两个 bitmap 的交集确定)
  2. 页面未满,即!PageIsFull(page),这里的 PageIsFull 不代表这个页面没有空间写入了,只是剩余空间较少
  3. 最后判断 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 有关)

image-20230314162140724

Hot chain清理

之后我们再进行一次正向扫描,所有被清理的 tuple 会记录在 prstate->nowunusedprstate->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
    1. 如果当前 tuple 已经被处理,或者状态为 LP_UNUSED || LP_DEAD退出循环
    2. 如果当前 ItemID 状态为 LP_REDIRECT,加入 chainitems,跳转到其指向的位置,回到步骤1
    3. 如果上一次的 xmax 不等于当前的 xmin退出循环
    4. 将当前 tuple 加入 chainitems
    5. 如果 tuple 的状态为 HEAPTUPLE_DEAD,记录最后一次删除位置 latestdead;如果状态也不是 HEAPTUPLE_RECENTLY_DEAD退出循环
    6. 如果当前 tuple 不是 HOT updated,说明遍历到了末尾,退出循环,否则根据 ct_id 跳转回到步骤1
  • 如果 latestdead 值有效,将 chainitems 中其之前的 tuple 加入 nowunused
  • 如果 chainitems 最后一个元素也为 dead 状态,将链头标记为 nowdead,否则对链头进行 redirect
  • 如果链中只有一个 LP_REDIRECT 的 tuple,说明它没有指向任何有效的后继,直接标记为 nowdead

可以看到,对于非 HOT Update 数据来说,整个流程不会对它有影响

在扫描完整个页面后,如果存在需要清理和更新的 tuple,执行 heap_page_prune_execute 进行真正的更新,通过 PageRepairFragmentation 清理空间,将页面置脏并清除 PD_PAGE_FULL 的标记,写入必要的日志。

nowunusednowdead 的区别在于:

  1. heap_page_prune_execute 中,如果存在 unused 的 item,会给页面加上 PD_HAS_FREE_LINES 的标志
  2. 由于 dead tuple 可能仍然会被索引所引用,因此暂时不能移除

TODO

  1. 关于 HOT Update 的日志上有什么改动还没有去了解,这里有极简说明 PostgreSQL HOT(Heap Only Tuple) 技术

  2. 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中。

reference

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇