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

本篇我们将具体介绍如何针对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的二级索引。

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定义的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插入操作

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

在上图的示例中，执行的是三次插入操作。其中，前两次插入由于访问都直接进入插入操作的步骤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删除操作

与插入操作的第一步类似，从高位向低位，同时ptree的root节点向下一层的node节点查找所要删除的节点。
若对应rid的leaf节点不存在，直接返回。若存在，则删除当前的leaf节点。
检查被删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情况的例子：

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

接下来是在删除操作中处理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。

如上图所示，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执行查询请求。

由 udpwork.com 聚合
|
评论: 0
|
要! 要! 即刻! Now!