PostgreSQL 解決 “大 value”問題的存儲技術 -- TOAST(The Oversized Attributes Storage Technique)

文章目錄

前言
TOAST 基本政策及相關存儲政策生效方式
TOAST 機制的實作

TOAST 寫鍊路的實作
TOAST 讀鍊路的實作

結語
參考

前言

postgresql 作為關系型資料庫且支援各種資料類型的存儲，那大寬表存儲或者對于超大attribute(列)的存儲肯定需要特殊的存儲技術來避免性能問題。因為PG 的 heap 表存儲引擎是通過page 來管理行（tuple）資料的，且對于行資料的insert和update都是将page加載到記憶體中，完成操作之後再通過checkpointer子程序刷到磁盤上。讀的時候也是先把要讀的page加載到記憶體中，而且還有vacuum子程序來進行過期行資料的清理。如果“大value” 參與這個過程且使用者隻要讀或者修改一個tuple的某幾個非大value屬性，那也會伴随着巨量io的損耗。

本質上是和單機lsm-tree 存儲引擎遇到的大value問題一樣，heap 表引擎的tuple資料 insert/update可以看作是append-only形态的，vacuum 清理過期資料也和 compaction 清理過期資料的性質一樣，PG這裡考慮的情況和細節更多一些而已。lsm-tree 的解決方案是k/v分離，而我們heap表引擎的解決方案是 TOAST，也是将目前資料表的 “大value” 存儲到一個額外的 toast表，因為隻存儲大 attribute，是以其他的正常的 attribute還是儲存在原本要存儲的表對應的page中，讀/update 大 attr 之外的屬性的話就不需要讀 toast表的資料了。

接下來我們看看使用以及實作上的一些細節。

TOAST 基本政策及相關存儲政策生效方式

當然，PG 的TOAST方案有幾種可選的類型，并不是所有分辨出來的大value 都一股腦塞進toast表中。

heap 引擎中對 “大value” 的識别是如果一個tuple 資料總大小超過一個page的1/4(預設一個page的大小是8K，也就是tuple 除了header 之外的部分占用2000Bytes)，則認為這個tuple 是需要使用toast 方式存儲的。

我們建立一個如下的表：

testdb=# CREATE TABLE c(
      a integer,
      b numeric,
      c text,
      d json
    );

擁有

text

和

json

兩個文本屬性的列，檢視這個表的attribute屬性。

testdb=# SELECT attname, atttypid::regtype, attstorage 
         from pg_attribute where attrelid='c'::regclass and attnum > 0;
 attname | atttypid | attstorage
---------+----------+------------
 a       | integer  | p
 b       | numeric  | m
 c       | text     | x
 d       | json     | x
(4 rows)

-- 或者 \d+ c; 也能夠看到
                                  Table "public.c"
 Column |  Type   | Collation | Nullable | Default | Storage  | Stats target | Description
--------+---------+-----------+----------+---------+----------+--------------+-------------
 a      | integer |           |          |         | plain    |              |
 b      | numeric |           |          |         | main     |              |
 c      | text    |           |          |         | extended |              |
 d      | json    |           |          |         | extended |              |
Access method: heap

能夠看到

attstorage

屬性列中擁有幾種不同的類型：

。

我們能夠在

FormData_pg_attribute

結構體的源代碼中看到對這幾個 attr-storage屬性的注釋描述：

CATALOG(pg_attribute,1249,AttributeRelationId) BKI_BOOTSTRAP BKI_ROWTYPE_OID(75,AttributeRelation_Rowtype_Id) BKI_SCHEMA_MACRO
{
  ...
  /*----------
   * attstorage tells for VARLENA attributes, what the heap access
   * methods can do to it if a given tuple doesn't fit into a page.
   * Possible values are
   *    'p': Value must be stored plain always
   *    'e': Value can be stored in "secondary" relation (if relation
   *       has one, see pg_class.reltoastrelid)
   *    'm': Value can be stored compressed inline
   *    'x': Value can be stored compressed inline or in "secondary"
   * Note that 'm' fields can also be moved out to secondary storage,
   * but only as a last resort ('e' and 'x' fields are moved first).
   *----------
   */
  char    attstorage;
  ...
}

這幾種關于 attribute 的存儲政策其各自的作用如下：

p -- plain ，主要用于已知固定長度的attribute 的存儲，這種attr的類型包括(integer, boolean, bit等)，對于這種類型的 attr 存儲并不會使用 toast技術。
m -- main ，這種存儲政策在遇到比較長的 attr 的時候要求先嘗試對該 attr進行壓縮，壓縮後的資料大小能夠滿足前面提到的非 “大value” 的場景時則繼續留在目前page，否則就将這一些長的attribute資料單獨存儲到toast 表中。
x -- extended ，允許壓縮attributes 以及壓縮後的資料大小超過 1/4 page時存儲到toast 表中，未超過1/4大小的情況壓縮後的資料就直接存儲到原表的page中。。
e -- external ，前面的 c
表中沒有這個屬性，允許将較長的未經過壓縮的attributes資料存儲到 toast表中。

我們可以通過指令
ALTER TABLE c ALTER COLUMN d SET STORAGE external; 修改 attrstorage 政策。

這裡反複提到的 toast 額外的表可以看作是一個單獨為前面

表建立的存儲大attribute 的表，它在主搜尋路徑上是隐藏的，可以從 pg_class 表中看到：

testdb=# SELECT relnamespace::regnamespace, relname
FROM pg_class
WHERE oid = (
SELECT reltoastrelid
FROM pg_class WHERE relname = 'c'
);
 relnamespace |    relname
--------------+----------------
 pg_toast     | pg_toast_16450
(1 row)

testdb=# \d+ pg_toast.pg_toast_16450;
TOAST table "pg_toast.pg_toast_16450"
   Column   |  Type   | Storage
------------+---------+---------
 chunk_id   | oid     | plain
 chunk_seq  | integer | plain
 chunk_data | bytea   | plain

在toast表中，我們能夠看到總共隻有三列，

chunk_id

chunk_seq

和

chunk_data

，其中

chunk_id

和

chunk_seq

會被用來建立索引，加速針對目前 toast表的通路；

chunk_id

可以了解為對原本超大attribute 資料的分區（以tuple方式管理，每一個chunk作為一個toast-table 中的元組，PG 預設期望一個page存儲>=4個元組）。

testdb=# SELECT indexrelid::regclass FROM pg_index
WHERE indrelid = (
SELECT oid
FROM pg_class WHERE relname = 'pg_toast_16450'
);
          indexrelid
-------------------------------
 pg_toast.pg_toast_16450_index
(1 row)

testdb=# \d pg_toast.pg_toast_16450_index;
Unlogged index "pg_toast.pg_toast_16450_index"
  Column   |  Type   | Key? | Definition
-----------+---------+------+------------
 chunk_id  | oid     | yes  | chunk_id
 chunk_seq | integer | yes  | chunk_seq
primary key, btree, for table "pg_toast.pg_toast_16450"

接下來我們看看toast 中的

extended

政策特性，因為它最具有代表性，也最有可能産生“大value”，text 這樣的 attr 類型在預設場景都是使用 extended 政策，extended 特性主要是針對 “大value” 屬性壓縮之後允許原地存儲，如果壓縮失敗則直接放入到toast table中。

extended 原地存儲場景

testdb=# insert into c values (1, 2.0, 'foo', '{}');
INSERT 0 1
testdb=# update c set c=repeat('A',5000);
UPDATE 1
testdb=# select * from pg_toast.pg_toast_16450;;
 chunk_id | chunk_seq | chunk_data
----------+-----------+------------
(0 rows)

嘗試為 c(text) 字段插入5000 bytes的字元，因為都是有規律的字母 ‘A’，會被 pg_lzcompress 算法進行壓縮，壓縮後的資料依然能夠存儲到 c表的page中，就會原地存儲，這也是上面檢視 toast 表中資料為空的原因。

extended 存儲到toast表中的場景

插入随機字元串，pg_lz 算法會壓縮失敗。

testdb=# UPDATE c SET c = (
        SELECT string_agg( chr(trunc(65+random()*26)::integer), '')
        FROM generate_series(1,5000)
        )
        RETURNING left(c,10) || '...' || right(c,10);
        ?column?
-------------------------
 QHZSRFSBRO...AARGJDDJIJ
(1 row)

UPDATE 1

testdb=# SELECT chunk_id,
                chunk_seq,
                length(chunk_data),
                left(encode(chunk_data,'escape')::text, 10) || '...' ||
                right(encode(chunk_data,'escape')::text, 10)
                FROM pg_toast.pg_toast_16450;
 chunk_id | chunk_seq | length |        ?column?
----------+-----------+--------+-------------------------
    16456 |         0 |   1996 | QHZSRFSBRO...ITNHVALVFT
    16456 |         1 |   1996 | CHHPRAVYDP...RTMDGGNKTW
    16456 |         2 |   1008 | ENBXUMTZGG...AARGJDDJIJ
(3 rows)

因為pg_lz 算法壓縮失敗，對于text 字段還是會保留5000bytes，本地存儲肯定是達到 “大value” 的标準了，是以會被放入到toast table中。在toast tabale中被拆分為了三個chunk，每一個chunk 的大小維持在 <= page_size/4 ，這個時候存儲的是未壓縮的資料。

接下來我們看看toast機制的代碼實作。

TOAST 機制的實作

最終對于 “大value” 的處理形态類似如下圖，圖中沒有辦法展示其他各種情況的處理細節，toast 表出現的形态基本一樣：

PostgreSQL 解決 “大 value”問題的存儲技術 -- TOAST(The Oversized Attributes Storage Technique)

針對某一個超大attr的處理如果壓縮失敗，則會按照最大chunk-size 被拆分為多個tuple存儲到 toast表中（前面示範的c表 c列的處理情況），并對應建立一個toast表的index 用于讀時候的加速通路。

關于 TOAST 完整的處理流程如下：

周遊 attstorage 政策為 extended 和 external 的 attr，從最長的 attr開始。 extended 政策會對目前 attr 的資料先進行壓縮，如果目前attr 壓縮後的資料超過了 1/4 page的大小，會直接将目前 attr的資料（未壓縮的）移動到 TOAST表。 external 政策的處理方式是一樣的，隻是不會對資料進行壓縮而已。
如果最長的 attr 的資料已經被壓縮/移動到 TOAST 表中了，但是整個tuple的大小還是超過1/4 page，則将存儲政策為 extended 或者 external 的attr 都移動到 TOAST表中。
如果還是無法滿足tuple 大小的限制（大寬表場景，有非常多的attr，PG預設的一行 attr個數上限是 1600個），會嘗試壓縮 main 政策的 attr，但是會讓壓縮後的資料繼續保留在原本的table page中，不進行移動。
如果還是無法滿足存儲需求，那就将壓縮後的 main attrs 移動到 TOAST table中。

前面提到的 tuple大小的限制在12.12版本還沒有相關的配置，在14版本之後有一個 toast_tuple_target guc配置可以讓使用者指定這個門檻值的大小。12.12版本中，預設是 TOAST_TUPLE_THRESHOLD 宏定義，大概就是2000bytes，不過會随着page-size的變化而變化，page-size在編譯的時候指定了其他的大小，那這裡還會變化的。

接下來看看代碼細節。

TOAST 寫鍊路的實作

在

heap_insert --> heap_prepare_insert

中會生成後續要放入到page的tuple，這個時候已經能夠拿到所有目前tuple要插入的 attr資料。

static HeapTuple
heap_prepare_insert(Relation relation, HeapTuple tup, TransactionId xid,
          CommandId cid, int options)
{
  /* 處理一些tuple header，設定 c_tid, t_xmax 等 */
  ...
  if (relation->rd_rel->relkind != RELKIND_RELATION &&
    relation->rd_rel->relkind != RELKIND_MATVIEW)
  {
    /* toast table entries should never be recursively toasted */
    Assert(!HeapTupleHasExternal(tup));
    return tup;
  }
  else if (HeapTupleHasExternal(tup) || tup->t_len > TOAST_TUPLE_THRESHOLD)
    /* toast 寫入入口，因為我們是insert鍊路，是以這裡參數中的 oldtup 是NULL */
    return toast_insert_or_update(relation, tup, NULL, options);
  else
    return tup;
}

接下來就會進入

toast_insert_or_update

處理 TOAST 寫入的邏輯。

前面會先進行資料準備，重要的幾個資料屬性如下：

HeapTuple
toast_insert_or_update(Relation rel, HeapTuple newtup, HeapTuple oldtup,
             int options)
{
  ...
  bool    toast_isnull[MaxHeapAttributeNumber]; // 快速判斷某一個 attr的資料部分是否為空
  Datum   toast_values[MaxHeapAttributeNumber]; // 目前tuple 每一個attr 的data資料
  ...
  // 解析傳入的tuple，并填充toast_values部分
  heap_deform_tuple(newtup, tupleDesc, toast_values, toast_isnull); 
  ...
}

填充好了需要的資料結構之後，就進入到了前面說的基本步驟中了

步驟一: 優先處理

和

的存儲政策，找出目前所有的toast_values 其中最長的attr 進行壓縮，如果壓縮失敗，則整個 attr資料都存儲到toast表中。

// heap_compute_data_size 預先計算目前tuple的總大小是否超過了門檻值
  while (heap_compute_data_size(tupleDesc,
                  toast_values, toast_isnull) > maxDataLen)
  {
    ...
    // 周遊一輪所有的attr, 找出最大的attr的下标 以及 大小。
    for (i = 0; i < numAttrs; i++)
    {
      Form_pg_attribute att = TupleDescAttr(tupleDesc, i);

      if (toast_action[i] != ' ')
        continue;
      if (VARATT_IS_EXTERNAL(DatumGetPointer(toast_values[i])))
        continue;   /* can't happen, toast_action would be 'p' */
      if (VARATT_IS_COMPRESSED(DatumGetPointer(toast_values[i])))
        continue;
      if (att->attstorage != 'x' && att->attstorage != 'e')
        continue;
      if (toast_sizes[i] > biggest_size)
      {
        biggest_attno = i;
        biggest_size = toast_sizes[i];
      }
    }
    ...

    // 嘗試壓縮找出的這個 attr 的data資料。
    i = biggest_attno;
    if (TupleDescAttr(tupleDesc, i)->attstorage == 'x')
    {
      old_value = toast_values[i];
      new_value = toast_compress_datum(old_value);
      // 壓縮成功則儲存toast狀态，并釋放目前tuple對應的data部分的資料
      if (DatumGetPointer(new_value) != NULL)
      {
        /* successful compression */
        if (toast_free[i])
          pfree(DatumGetPointer(old_value));
        ...
      }
      else
      {
        /* incompressible, ignore on subsequent compression passes */
        toast_action[i] = 'x';
      }
    }
    else
    {
      /* 标記無法進行壓縮 */
      toast_action[i] = 'x';
    }
    
    // 壓縮失敗，則嘗試将attr對應的 toast_values 中的資料存儲到 toast 表中。
    if (toast_sizes[i] > maxDataLen &&
      rel->rd_rel->reltoastrelid != InvalidOid)
    {
      old_value = toast_values[i];
      toast_action[i] = 'p';
      toast_values[i] = toast_save_datum(rel, toast_values[i],
                         toast_oldexternal[i], options);
      if (toast_free[i])
        pfree(DatumGetPointer(old_value));
      ...
    }
  }

其中比較重要的兩個函數：

函數 toast_compress_datum 的實作是 PG 自實作的 lz算法，學習的是Adisak Pochanayon 提出的SLZ 算法的思想，本質上其實也是 LZ77 版本的算法。通過構造全局的字典來對重複的輸入字元進行編碼，PG這裡實作的版本對解壓縮性能更為友好，但是并不适合超大value，因為資料字典需要常駐記憶體才能保證解壓縮的高效比對性能。在PG 所支援的大多數資料存儲場景還是能夠滿足性能需求的，這個算法還是值得研究的（pg 這裡代碼細節上做了很多處理，短時間内細節沒有看的太明白 😐）。
函數 toast_save_datum 用來将目前attr 資料添加到toast 表中，該函數的核心邏輯如下：

在目前rel 表下面的table-space中建立一個 toastrel 來辨別一個toast表，用來存儲 toast資料。
建立一個 toastrel 對應的 index表 validIndex ，用來加速對 toast 表的通路。
計算好目前 attr 在toast中要存儲的資料大小 data_todo
data_todo 大小的attr 資料未寫入之前，循環寫入。每一次寫一個chunk的資料，在page-size 大小為 8K 的情況下每一個chunk的大小為 1996B。每一個chunk 封裝為一個tuple heap_form_tuple 函數來構造tuple，通過 heap_insert 插入 toast_rel 對應的 toast表中;緊接着通過 index_insert
插入這個toast 對應的index 表中。

循環第四步，直到完成目前 attr 所有的資料都寫入到tuple中。

這部分的代碼實作比較簡單，這裡就不貼了。

需要注意的是在将目前 attr 資料移動到toast 表之後會傳回一個指向toast 表的指針給tuple，這個pointer本質上是一個

varatt_external

資料結構對象，儲存的是toast 表relid以及value在toast表中的id，能夠用作後續讀原始tuple的時候能夠從toast 表中進行讀取。

繼續回到

toast_insert_or_update

函數。

步驟二: 如果目前tuple 剩下的attr 總大小還是超過限制，則處理剩下attr 中所有為

或者

存儲政策的attr。所有能夠壓縮的的且大小超過

maxDataLen

的 attr之前都已經處理完了，剩下的主要是處理之前不能壓縮的了，邏輯比較簡單：

// 除了check tuple-size 之外還需要確定 toast 表是有效的，這樣才能将 attr 移動到toast表中。
  while (heap_compute_data_size(tupleDesc,
                  toast_values, toast_isnull) > maxDataLen &&
       rel->rd_rel->reltoastrelid != InvalidOid)
  {
    ...
    // 對于剩下的，未壓縮的attr 還是按照從大到小進行處理
    for (i = 0; i < numAttrs; i++)
    {
      Form_pg_attribute att = TupleDescAttr(tupleDesc, i);

      if (toast_action[i] == 'p')
        continue;
      if (VARATT_IS_EXTERNAL(DatumGetPointer(toast_values[i])))
        continue;   /* can't happen, toast_action would be 'p' */
      if (att->attstorage != 'x' && att->attstorage != 'e')
        continue;
      if (toast_sizes[i] > biggest_size)
      {
        biggest_attno = i;
        biggest_size = toast_sizes[i];
      }
    }
    ...
    toast_values[i] = toast_save_datum(rel, toast_values[i],
                   toast_oldexternal[i], options);
    ...
  }

步驟三: tuple大小還是超過了限制的大小，主要是處理 attrstorage 為

的場景，即嘗試壓縮該類型的attr，并直接存儲在本地tuple中，邏輯基本同上。

步驟四: 将壓縮後的

類型的attr 移動到 toast 表中，邏輯基本同上。

進入到步驟三和四的邏輯基本就是大寬表了，這個時候隻能是一步步嘗試，讓tuple大小滿足要求。

完成以上步驟之後，函數

toast_insert_or_update

還需要構造一個新的tuple，儲存的是之或前壓縮後的資料，或移動到toast 之後的指針，将新的tuple傳回。

因為以上處理的其實是

heap_insert

的邏輯，如果是

heap_update

，則還需要提前将舊的tuple資料讀出來，在這個函數中完成更新。

整個 TOAST 方式的寫傳入連結路還是比較清晰的，對于 “大 attribute” 的資料或者大寬表的處理還是對性能有比較大的影響的，可能需要壓縮、建立toast表、toast索引表；雖然說PG 本身的heap表寫鍊路也是操作存儲于記憶體中的 page，後續才會刷盤，但每一個heap_insert 都伴随着一次wal page的寫入，對于大value場景（大attr），而且它的toast插入可能會伴随多個heap_insert，超大value 對性能本身還是有比較大的影響的。

TOAST 讀鍊路的實作

讀鍊路本身是會先把要讀的page加載到記憶體中，通過 bfmgr 管理起來；要讀的tuple 則會從page中進行逐個解析，和上層的查詢語句的要求做比對。

針對帶有 toast 屬性且已經分離存儲的 tuple的讀取調用棧如下：

* frame #0: 0x000000010025d6f4 postgres`heapam_index_fetch_tuple
    frame #1: 0x000000010026ab44 postgres`index_fetch_heap + 64
    frame #2: 0x000000010026abc0 postgres`index_getnext_slot + 64
    frame #3: 0x000000010026a440 postgres`systable_getnext_ordered + 28
    frame #4: 0x000000010026406c postgres`toast_fetch_datum + 280
    frame #5: 0x000000010026442c postgres`heap_tuple_untoast_attr + 60
    frame #6: 0x0000000100538b58 postgres`text_to_cstring + 24
    frame #7: 0x00000001005602ec postgres`FunctionCall1Coll + 80
    frame #8: 0x000000010022ffe8 postgres`printtup + 376
    frame #9: 0x00000001003676cc postgres`standard_ExecutorRun + 308
    frame #10: 0x00000001004814ac postgres`PortalRunSelect + 244
    frame #11: 0x00000001004810fc postgres`PortalRun + 468
    frame #12: 0x0000000100480240 postgres`exec_simple_query + 768
    frame #13: 0x000000010047e3d4 postgres`PostgresMain + 2852
    frame #14: 0x000000010041c3b8 postgres`BackendRun + 404
    frame #15: 0x000000010041ba3c postgres`ServerLoop + 2376
    frame #16: 0x0000000100419618 postgres`PostmasterMain + 3652
    frame #17: 0x00000001003a659c postgres`main + 636

本質上會先讀取 toast 表對應的index表，利用

chunk_id

或者

chunk_seq

兩個index-key 索引到對應的chunk_data中，然後解壓縮對應的 attr 或者根據原表中的toast_pointer中的va_valueid

将所有的與這個 id 相等的tuple都順序讀出來（一個 attr 可能會被拆分為多個tuple 存儲到toast表中），從toast 中讀取的邏輯主要是在

toast_fetch_datum

函數中。

結語

随着網際網路的普及對文檔(json – 極易分析)類型、k/v （超大規模的社交圖譜、知識圖譜）這樣的弱關系型資料有巨量的存儲需求，這一些存儲需求我們的關系型資料庫功能過于複雜而導緻性能上無法滿足存儲需求，是以nosql的出現也是必然的。
但時代又期望能夠在這種類型的資料中進行像 SQL 一樣的極為友善的關系模型的建立以及搜尋，又有了NewSQL 。
如今大家期望更易用，成本更低，隻能讓這一套體系又上雲了，進而将資料庫通路模式做成 SaaS(software-as-a-service) 服務。

參考

《postgresql_internals-14_parts1-3_en.pdf》
postgresql - REL_12_STABLE 源碼

PostgreSQL 解決 “大 value”問題的存儲技術 -- TOAST(The Oversized Attributes Storage Technique)

文章目錄

前言

TOAST 基本政策及相關存儲政策生效方式

TOAST 機制的實作

TOAST 寫鍊路的實作

TOAST 讀鍊路的實作

結語

參考

繼續閱讀

set define off關閉替代變量功能

報錯：'mysql' 不是内部或外部指令，也不是可運作的程式或批處理檔案。

Linxu常用指令技巧彙總

ERROR 1 (HY000): Can't create/write to file '/tmp/#sql_4188_1.MYI' (Errcode: 28)

艱難安裝LDAP,SSL認證

《Linux指令行與Shell腳本程式設計大全第2版.布盧姆》pdf

MySQL的4種隔離級别？出現問題

XX系統實施過程問題總結

無元件上傳圖檔到資料庫中，最完整解決方案

【MySQL資料庫】資料庫索引事務1.索引2.事務

neo4j之cypher使用文檔

詳解STM32單片機的堆棧

NOSQL安全攻擊

mybatis_入門程式Mybatis入門

登入plsql 報錯 the account is locked --使用者被鎖

SequoiaDB巨杉資料庫C++驅動概述

PostgreSQL 解決 “大 value”問題的 存儲技術 -- TOAST(The Oversized Attributes Storage Technique)

文章目錄

前言

TOAST 基本政策 及 相關存儲政策生效方式

TOAST 機制 的實作

TOAST 寫鍊路的實作

TOAST 讀鍊路的實作

結語

參考

繼續閱讀

PostgreSQL 解決 “大 value”問題的存儲技術 -- TOAST(The Oversized Attributes Storage Technique)

TOAST 基本政策及相關存儲政策生效方式

TOAST 機制的實作