4store源码解析系列(4)–predicate维度的四元组存储

  • Post author:
  • Post category:IT
  • Post comments:0评论

本篇我们将具体介绍如何针对predicate维度的搜索需求,来实现四元组的存储的。

predicate维度的存储结构

而在检索中,有很大一部分需求是在已知[P, O]或[P, S]的情况(即文章标题所说的predicate维度的检索需求)下,检索[M, S]或[M, O]。为了满足对于这类需求,我们一般需要建立一个两层索引结构才能完成检索任务。在实际应用中,RDF文档一般保存的是特定领域或应用的[M, O, P, S]四元组,其中P的数量相比于O和S往往要小很多。因此,我们可以首先基于P建立一级索引,然后再对每个P的所有triples(此处的triple为[M, O, S]三元组)分别建立基于O和S的二级索引。

predicate维度的存储结构

4store源码解析(1)中的图非常形象的对predicate维度的存储结构进行说明。在4store在设计上就是采用上文所说的方式实现的。一级索引使用glib的g_hash_table,建立了一个从P的rid到其triples集合的映射,即源码中的rid_id_map。二级索引使用一个叫做ptree的数据结构,分别建立一个从O的rid到其[M, S]二元组(也称pairs)的映射和一个从S的rid到其[M, O]二元组的映射,即源码中的ptree_o和ptree_s。在处理这些二元组时,又利用了一个叫做ptable的数据结构来管理其存储和访问。

利用4s-import导入数据之后,我们也可以看到每个P都会独立保存其对应的ptree_o和ptree_s到文件系统中。而所有ptree_o和ptree_s映射的[M, O]和[M, S]二元组则一起保存在同一个名为pairs.ptable的文件结构中。

当已知[P, O]进行检索时,会先用P的rid在rid_id_map找到ptree_o的位置,然后再用O的rid在ptree_o中找到[M, S]二元组集合在ptable的入口位置,最后再访问ptable的入口位置即可遍历访问所存的内容即可完成检索。

ptree

ptree本质上是一个trie树,实现从rid到pairs在ptable中存储位置的映射。

接下来,我们将具体介绍ptree的内存结构以及其涉及的插入和删除这两个操作。对于插入和删除操作,分别用示例来具体说明其实现细节。

ptree节点元素的内存结构

#define FS_PTREE_BRANCHES    4
typedef uint32_t nodeid;

typedef struct _node {
    nodeid branch[FS_PTREE_BRANCHES];
} node;

typedef struct _leaf {
    fs_rid pk;
    uint32_t block;
    uint32_t length;
} leaf;

ptree_element

目前,ptree定义的node和leaf节点大小是一样的,都是16字节。ptree的每个node中包含4个branch,与rid中的2个bit相对应。即rid的2bits的00对应branch[0],01对应branch[1],10对应branch[2]以及11对应branch[3]。因此,ptree是一个4叉的trie树。但从代码实现来看,只要 sizeof(node) 是 sizeof(leaf) 的2指数次倍数即可。

ptree的leaf中,pk保存的是当前leaf对应的rid(ptree_o存的是O的rid,而ptree_s存的是S的rid),block是指向ptable中pairs的存储位置,length记录ptable中存储的pairs数量。

ptree中的node和leaf节点都是直接存储在文件中的。这个文件如上图所示,其中除了文件头外,node和leaf是分别成块连续存储的(笔者在此定义它为连续存储块)。在初始化的时候,文件头之后跟两个连续存储块,第一个连续存储块用来存储node,第二个用于存储leaf。

ptree_header中还有两个索引值:node_free和leaf_free,分别用来指向回收的node和leaf。回收node节点时,node_free指向下一个空的node,而node再继续用branch[0]来继续指向下一个空的node。回收leaf节点时也是类似的,leaf_free指向下一个空的leaf,而leaf再继续用block域来继续指向下一个空的leaf。node_free和leaf_free的实现方式,与tbchain中的free_list是基本一致的。

在ptree中添加node和leaf元素时,首先会检查对应的node_free和leaf_free中是否还有空节点,然后再从之前文件分配好的连续存储块中申请新的位置。若当前的连续存储块也已满,则需要再开辟下一块连续存储块,来继续存储新添加的节点。

ptree插入操作

  1. 从rid的高位(rid的最高两位是node类型信息,因此是从62-61位向2-1位检查,最多31层)开始,同时ptree也是从root节点开始一层层往下检查。
  2. 若node节点对应branch值为 FS_PTREE_NULL_NODE,则表明当前插入的rid不在ptree中。此时,新建一个leaf节点,并将branch指向该leaf节点。
  3. 若node节点对应branch值指向的是某个leaf,检查该leaf节点的rid是否和当前插入的rid一致。若一致,则表明当前插入的rid在ptree中,返回即可。若不一致,则表明当前leaf节点之前的node节点需要split。
  4. split节点时,需要从高位到低位,每2位次,不断比较当前插入rid和leaf节点上的rid。若值相同,则添加一个新的node,原node的branch指向新的node,新node对应的branch指向原leaf节点;若值不同,则进入步骤2的逻辑,添加一个leaf节点,插入rid。

ptree_insert

在上图的示例中,执行的是三次插入操作。其中,前两次插入由于访问都直接进入插入操作的步骤2,完成rid的插入。而第三次插入时,两次进入步骤4的节点split逻辑。

#define FS_PTREE_BRANCHES    4
#define FS_PTREE_BRANCH_BITS 2  /* log2(FS_PTREE_BRANCHES) */
#define PK_BRANCH(pk, i) (pk >> (((64/FS_PTREE_BRANCH_BITS)-1-i) * FS_PTREE_BRANCH_BITS)) & (FS_PTREE_BRANCHES-1)

需要注意的是,4store中使用PK_BRANCH宏来计算rid在第i层node上branch的index。但是,宏PK_BRANCH在传参时并没有使用括号来,而宏是直接展开的。在下面这段关键代码中,这个宏的使用会对我们的阅读代码,理解逻辑带来很大困扰。int oldkbr = PK_BRANCH(existpk, i-1); 指的并不是rid的第i-1层branch index,而是i+1层。

static nodeid get_or_create_leaf(fs_ptree *pt, fs_rid pk) {
    nodeid pos = FS_PTREE_ROOT_NODE;
    for (int i = 0; i < 64 / FS_PTREE_BRANCH_BITS; i++) {
        int kbranch = PK_BRANCH(pk, i);
        again: ;
        node *nr = node_ref(pt, pos);
        nodeid newpos = nr->branch[kbranch];
        if (newpos == FS_PTREE_NULL_NODE) {
            // comment out
        } else if (IS_LEAF(newpos)) {
            const fs_rid existpk = LEAF_REF(pt, newpos)->pk;
            if (pk == existpk) {
                /* PKs are the same, we can reuse the block */
                return newpos;
            }
            /* split and insert node */
            int oldkbr = PK_BRANCH(existpk, i-1);
            nodeid split = fs_ptree_new_node(pt);
            node_ref(pt, pos)->branch[kbranch] = split;
            node_ref(pt, split)->branch[oldkbr] = newpos;
            goto again;
        }
        pos = newpos;
    }
    // comment out
    return 0;
}

ptree删除操作

  1. 与插入操作的第一步类似,从高位向低位,同时ptree的root节点向下一层的node节点查找所要删除的节点。
  2. 若对应rid的leaf节点不存在,直接返回。若存在,则删除当前的leaf节点。
  3. 检查被删leaf对应node节点的所有branch。若所有branch指向无效位置,则表明当前node节点无效的,也需要删除。若所有branch只有一个指向有效位置,则表明需要MERGE处理。

以上步骤中,删除的leaf和node节点,分别被node_free和leaf_free回收资源。

/* MERGE not currently implemented, harmless, but less efficient
* than it could be */

在目前的ptree实现中,有两个粒度的pair数据删除操作:删除某个rid映射到ptable行中的特定pair和删除所有rid映射到ptable行中的特定pair。无论是那种pair数据删除,都可能会涉及ptree的leaf节点删除操作(一旦该leaf对应的ptable行中的pair数据被全部删除,则该leaf需要被删除)。在ptree实现中,两种情况对应的leaf节点删除操作却是不一样的。在第一种情况下,并没有处理MERGE,仅在那个位置留下了代码逻辑的注释。正如代码注释中所说的:不处理MERGE情况并不会来带什么问题,但是可能会稍微低效一些。而在第二种情况下,是处理了MERGE的,这很可能是因为涉及的删除操作量比较大,MERGE会带来一些性能提升。

下面我们用同样删除示例展示了,在不处理和处理MERGE情况下的具体步骤区别。首先是在删除操作中不处理MERGE情况的例子:

ptree_delete

在上图的示例中,执行的是两次删除操作。展现了四个状态,分别是:初始状态、删除第1个leaf之后的状态、删除第2个leaf之后的状态,删除当前的无效node。

接下来是在删除操作中处理MERGE情况的例子:

ptree_delete_merge

在上图的示例中,执行的是两次删除操作,其中第一次删除之后,执行了MERGE操作。图中展现了五个状态,分别是:初始状态、删除第1个leaf之后的状态、删除当前node并merge leaf到上一层node节点之后的状态、再次删除当前node并merge leaf到上一层node节点之后的状态,删除第2个leaf之后的状态。

ptable

ptable是服务于ptree,用于具体存储[M, O]二元组(即文中提到的pair)和[M, S]二元组的数据结构。

typedef struct _row {
    fs_row_id cont;
    fs_rid data[2];
} row;

在ptable中,二元组是以row这个结构来进行存储的。row中除了包含可以存储二元组rid的data域外,还有一个cont域用来指向下一个row。从row的定义,我们也不难猜出ptable的数据结构及其对应的插入和删除操作。ptree中存储的一个rid,映射到ptable中的一行pairs。

ptable

如上图所示,ptree中的每个leaf对应于ptable中的一个row,leaf中存储的block逻辑上指向于ptable中的某个row结构位置。

分段(segment)机制

4store中使用了分段(segment)机制,来完成数据存储的replica、数据的分布式存储和查询等功能。对于资源ID的存储和四元组的存储和查询,分段机制有一些区别。

分段存储

资源存储,实际存储的是rid及其对应的文本/URI内容。每个rid可以对应到一个segment(无备份的情况)或多个segment(数据备份的情况)。将rid及其对应的资源内容存储到相应的segment中,就是4store中对于资源ID存储时使用的分段存储的实现机制。

四元组存储,存储的是[M, S, P, O]的rid四元组。4store存储的时候,会分别从model维度和predicate维度来对四元组的值进行存储。但无论是从哪个维度考虑,在分段存储时,都是使用subject的rid来决定这个四元组所对应的segment/segments。

分段查询

资源查询,与资源存储对应,使用rid来决定去哪个segment查询。

四元组查询,在已知S的情况下,向S对应segment去执行查询请求。在S未知的情况下,向所有的segment执行查询请求。

发表评论