How to rebuild index gracefully and safely

Prior knowledge about index

What is relfilenode:

pg_class 里面有一列叫 relfilenode , pg 官方的文档对这列的解释是：

Name of the on-disk file of this relation; zero means this is a "mapped" relation whose disk file name is determined by low-level state

也就是这个值表示 pg_class 里面某个对象在磁盘上存储的文件名。

How to identify an index:

可以用 pg_class 中的 oid （在 pg_index 中为 indexrelid ）来唯一标识一个索引。当然，用 relfilenode 来进行标识也是可以的。

How to store an index:

这里讨论的是分布式存储下索引的存储方式。
从存储的角度来看，一条索引存储的目录如下：
/index_data_dir/dbid/tableid/indexid/indexfile
indexfile 的文件名的命名方式为：

highvalue-lowvalue.mi
highvalue = dbid << 32 + tableid;
lowvalue = indexid << 32 + fileid;

dbid , tableid , indexid 可以用 oid 来表示，也可以用 relfilenode 来表示（目前的方法是用 table relfilenode 和 index relfilenode 来表示 tableid 和 indexid ）。
fileid 用来表示文件的版本，比如对一个索引做过 compact 后，会把数据翻新到一个新的文件中然后删除旧的文件，此时 fileid++ 。

What is shared relation

postgres 中的元数据通常都是每个数据库自己独占的，比如 pg_class 中存的就是当前数据库中所有对象的信息，所以理应每个数据库有一份自己的 pg_class ，但是对于某些元数据，比如 pg_database , pg_authid 这种所有数据库共享的信息，只会在 template1 中存储一份，其他数据库想要访问 Shared Relation 的时候会去 template1 中读取。

How to rebuild an index

pg 的官方文档是这么定义REINDEX的：

REINDEX rebuilds an index using the data stored in the index's table, replacing the old copy of the index.

就是用表里的数据重建索引，可以用该操作来恢复出错的索引。
现在代码里的 REINDEX 有两套逻辑：

• 第一套逻辑是5.x的逻辑，通过magma_tool直接在存储侧进行一个类似 compact 的操作，把索引文件的 fileid 加一，创建一个新的文件，把数据导入到新文件中，然后删除掉老的文件。这个过程对于上层来说是不感知的（比如对于查这个索引对应的元数据的时候，该索引的 oid 和 relfilenode 都是不变的）。
• 第二套逻辑是6.x的逻辑，是按照 postgres 的逻辑来的，大概是这样的一个流程：
  1. 给 index 申请一个新的 relfilenode , 然后把老的文件注册删除并创建一个新的索引文件，并且更新 pg_class 中的 relfilenode 值为最新申请的。
  2. 然后调用 index_build 接口，把数据从表中读上来再插入到索引中。
  3. 新索引创建成功，事务提交，真正删除老的文件。
     这套逻辑上层是感知的（ relfilenode 变了）。

Defect of current REINDEX logic

目前两套逻辑各有缺陷，下面分析一下：

5.x的逻辑：

这套逻辑最大的问题是不支持全局二级索引(Global Secondary Index)的 rebuild , 因为在存储侧做这个操作，各个分片不会去其他分片读取数据，每个分片只会用自己分片的数据去重建索引，而全局二级索引的分布和主表不同，所以这套逻辑无法 handle 全局二级索引的情况。

其次就是这套逻辑的做法有些太 hack 了，使得 reindex 看起来不像是一个数据库内部的操作，更像是一个index恢复脚本。

6.x的逻辑：

这套逻辑在用户表和非 Shared Relation 上是没有任何问题的，因为这套逻辑相当于 drop index 后再 create ，并且中间任何一个环节出问题都是可以恢复的，比如旧的文件注册删除了，这时候不会真正的删除，只有在事务成功提交之后才会去真正的删除，假如事务 abort 了，会把旧的文件恢复。
但是当我们在 Shared Relation 上做 REINDEX 操作的时候，问题出现了。
我们再细致的观察一下 REINDEX 的流程，然后看看问题出在哪里：

void
reindex_index(Oid indexId, bool skip_constraint_checks, char persistence,  
           int options)
   {
    ...
    heapId = IndexGetRelation(indexId, false);  
	heapRelation = table_open(heapId, ShareLock);
	...
	iRel = index_open(indexId, AccessExclusiveLock);
	...
	/* Create a new physical relation for the index */  
	RelationSetNewRelfilenode(iRel, persistence);
	...
	/* Initialize the index and rebuild */
	index_build(heapRelation, iRel, indexInfo, true, true);
	...
	index_close(iRel, NoLock);  
	table_close(heapRelation, NoLock);
   }
void  
RelationSetNewRelfilenode(Relation relation, char persistence)
{
	...
	/* Allocate a new relfilenode */  
	newrelfilenode = GetNewRelFileNode(relation->rd_rel->reltablespace, NULL, persistence);
	...
	/*  
	 * Get a writable copy of the pg_class tuple for the given relation. 
	 */
	pg_class = table_open(RelationRelationId, RowExclusiveLock);
	...
	RelationDropStorage(relation);
	...
	srel = RelationCreateStorage(newrnode, persistence, smgr_type);
	...
	CatalogTupleUpdate(pg_class, oldtuple, tuple);
	...
}

当我们更新 pg_class 中的条目的时候（该对象的 relfilenode 改变，所以要更新），我们更新的是当前数据库的 pg_class 表，设想下面一种情况：

假设我们当前在名为test1的数据库中执行：

REINDEX INDEX pg_database_datname_index

（ pg_database 是一个 Shared Relation ），该索引的 relfilnode 假设从 2671 变成了 16388 ，那么test1中的 pg_class 中relname = pg_database_datname_index的一条就会从
oid = 2671, relname = pg_database_datname_index, relfilenode = 2671
变成
oid = 2671, relname = pg_database_datname_index, relfilenode = 16388。

磁盘上的文件目录也会从/1/1262/2671变成/1/1262/16388(因为该索引只存储在 template1 数据库中，所以dbid = 1，也就是template1的 dbid )。

那么假设 REINDEX 操作成功执行，这时候另一个psql的连接过来了，说想要连接test1数据库，收到这条请求之后，会根据test1这个 name 去 pg_database 进行 indexscan ,用哪个 index 进行 indexscan 呢？没错，就是刚刚 REINDEX 过的 pg_database_datname_index 。

进行 indexscan 之前需要先拿一下索引的信息，因为这个索引是 Shared Relation ,这条信息就去要去template1中拿，这时候问题来了，template1中的这条索引的 relfilenode 还是 2671 ，因为我们刚刚更新的是test1中这条索引的 relfilenode ,并没有改template1中的 relfilenode ，但是磁盘上的文件又已经发生了改变，用relfilenode = 2671已经找不到这个索引对应的文件了，这时候数据库就会报错并挂掉。

How does postgres rebuild index on SharedRelation

现在我们发现了对 Shared Relation 做 REINDEX 操作会导致无法找到正确的 relfilenode 。那么我们看看万能的 postgres 是怎么处理这个问题的。
仔细阅读 postgres 的代码，我们可以发现有一个文件叫relmapper.c， 里面的注释是这样写的：

/*-------------------------------------------------------------------------  
 * relmapper.c 
 *    Catalog-to-filenode mapping 
 * 
 * For most tables, the physical file underlying the table is specified by 
 * pg_class.relfilenode.  (blablablablablablablablablablablabla)  It also 
 * does not work for shared catalogs, since there is no practical way to 
 * update other databases' pg_class entries when relocating a shared catalog.
 * 
 * Therefore, for these special catalogs (henceforth referred to as "mapped  
 * catalogs") we rely on a separately maintained file that shows the mapping  
 * from catalog OIDs to filenode numbers.  Each database has a map file for  
 * its local mapped catalogs, and there is a separate map file for shared  
 * catalogs.  Mapped catalogs have zero in their pg_class.relfilenode entries.
 *  
 *-------------------------------------------------------------------------

看来 postgres 也早已发现 Shared Relation 修改 relfilenode 会有问题了，他们的解决方案是用一个额外的文件pg_filenode.map来存储从 oid 到 relfilenode 的映射，然后在元数据中给这些需要映射的对象的 relfilenode 设置为0，然后在需要用到其 relfilenode 的时候再从这个映射的文件里面查。
relcache.c里面的一段代码可以直观的看出这段逻辑是如何工作的：

if (relation->rd_rel->relfilenode)  
{  
	.......
    relation->rd_node.relNode = relation->rd_rel->relfilenode;  
}  
else  
{  
    /* Consult the relation mapper */  
    relation->rd_node.relNode =  
       RelationMapOidToFilenode(relation->rd_id,  
                          relation->rd_rel->relisshared);  
    if (!OidIsValid(relation->rd_node.relNode))  
       elog(ERROR, "could not find relation mapping for relation \"%s\", OID %u", RelationGetRelationName(relation), relation->rd_id);  
}

当然这里只是简述了一下这个映射是如何工作的，具体的实现还涉及到很多，比如考虑修改 relfilenode 的事务是否成功提交以及和WAL协作等，这里就不细讨论了。

How should we rebuild an distributed index

单机数据库中的 REINDEX 已经没什么问题了，那么这套逻辑在处理分布式存储的索引的时候是否还能正常工作呢？

答案是不可以，因为 postgres 这套逻辑是映射文件只存在 master 节点的，并且该文件只有一份，假设有多个 master ，如果照搬这套逻辑，不同的 master 文件里面存的映射可能会不同，导致还是不能拿到正确的 relfilenode 。

那么我们需要考虑如何对分布式存储的索引做 REINDEX 操作。在开始想如何做的时候，我们先想想现在存在什么问题：

• 问题一：要考虑如何处理 GSI 分布和主表分布不同的情况。
• 问题二：要考虑 REINDEX Shared Relation 后如何处理 relfilenode 发生变化的情况。
• 问题三：要考虑 REINDEX 过程中出错后如何处理。

要解决问题一，就不能在存储侧做 REINDEX 操作，要从QD调用 drop index + create index 的流程，因为目前 create index 是支持GSI的创建的，所以可以处理GSI分布不同的情况。
要解决问题二，有两种方案，第一种方案是存储目录使用 indexoid 来标识，这样即使 relfilenode 改变， indexoid 也不会改变，根据之前的 indexoid 依然可以找到正确的目录，然后读取到索引，第二种方案是像 postgres 一样使用一个映射来找到正确的 relfilenode 。
要解决问题三， 就需要具体考虑 REINDEX 过程中各个阶段的文件变化，这个在后面详细讨论。

综上，提出如下的解决方案：

这个方案的做法是把index的存储目录从
/index_data_dir/dbid/tableid/indexrelfilenode/indexfile
变成
/index_data_dir/dbid/tableid/indexoid/indexfile
并且把 indexfile name 中的 lowvalue 做一下变化，原先的 lowvalue 计算方法是：

indexid << 32 + fileId << 4 + BTFT_INDEX

并且将 fileId 从 uint8_t 变更为 uint32_t ,新的 lowvalue 的计算方法为：

indexid << 32 + fileId

在本方案中， indexId 用 index Oid 来代替 index relfilenode ，假设
tableId = 1262, indexOid = 2671, REINDEX 前 fileId = 1 ,REINDEX 后 fileId = 2,
那么原先的文件目录是：
1/1262/2671/4294968558-11471857647617.mi
REINDEX后，文件目录是：
1/1262/2671/4294968558-11471857647618.mi

REINDEX后再对该索引进行操作的时候，根据 dbid + tableId + indexoid 的组合来找到目录，并且highvalue 和 lowvalue 中的 indexid 都不会变，所以也可以定位到索引文件。

那么 REINDEX 过程中，该文件夹内的文件状态如下：

BEFORE REINDEX
Status 1 : *-11471857647617.mi
REINDEXING
	BEGIN REINDEX(create new file):
	Status 2 : *-11471857647617.mi      *-11471857647618.mi.tmp
	DO REINDEX(insert into new file):
	Status 3 : *-11471857647617.mi      *-11471857647618.mi.tmp
	END REINDEX(convert new file to visible and delete old file):
	Status 4 : *-11471857647617.mi      *-11471857647618.mi
	Status 5 : *-11471857647618.mi
AFTER REINDEX
Status 6 : *-11471857647618.mi

sequenceDiagram

QD->>+MagmaClient: REBUILD INDEX request

MagmaClient->>+MagmaServer: REBUILD INDEX request

Note right of MagmaServer: BEGIN REBUILD : 1.mi -> 1.mi 2.mi.tmp

Note right of MagmaServer: DO REBUILD : insert 2.mi.tmp

Note right of MagmaServer: END REBUILD : 1.mi 2.mi.tmp -> 2.mi

MagmaServer-->>-MagmaClient: Done

MagmaClient-->>-QD: Done

对于全局二级索引，由于插入数据需要在QD读所有的数据，排序然后再插入，总体流程如下：

sequenceDiagram

Note right of QD: begin transaction

QD->>+MagmaClient: REBUILD INDEX request

MagmaClient->>+MagmaServer: REBUILD INDEX request

Note right of MagmaServer: BEGIN REBUILD : 1.mi -> 1.mi 2.mi.tmp

MagmaServer-->>-MagmaClient: waiting for insert GSI

MagmaClient-->>-QD: waiting for insert GSI

Note right of QD: Read GSI data and sort

QD->>+MagmaClient: insert GSI

MagmaClient->>+MagmaServer: insert GSI

Note right of MagmaServer: DO REBUILD : insert 2.mi.tmp

MagmaServer-->>-MagmaClient: waiting for end Rebulid

MagmaClient-->>-QD: waiting for end Rebuild

QD->>+MagmaClient: drop old index and convert

MagmaClient->>+MagmaServer: drop old index and convert

Note right of MagmaServer: END REBUILD : drop 1.mi and convert 2.mi.tmp to 2.mi

MagmaServer-->>-MagmaClient: Done

MagmaClient-->>-QD: Done

Note right of QD: commit transaction

现在来考虑出错的场景该如何处理和恢复：
如果在 magma server 收到 REINDEX request 之前就出错，事务 abort 即可，无需特殊处理。
如果在 magma server 收到 request 之后出错：

• 在Status 2, Status 3出错：会残留一个.tmp文件，这个可以在每次 BEGIN REINDEX 之前进行一次检查，如果目录中有残留的.tmp文件就清理一下。
• 在Status 4出错：发现多个 visible 的文件，选取 filenum 小的文件，可以在每次 BEGIN REINDEX 之前检查的时候发现有残留的.mi文件就把 filenum 大的一个清理掉。
• 在Status 5出错：无需特殊处理，事务 abort 即可。
  如果在 magma server 返回 response 的时候出错：事务 abort 即可，无需特殊处理。