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

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

在源码解析系列的上一篇,我们详细介绍了资源ID的存储。从这一篇开始,我们将介绍如何将model, object, predicate以及subject资源对应的rid四元组(也称为quad)存储。4store对四元组进行了多种形式的存储,以应对不同类型的搜索需求。在这一篇中,我们重点介绍的是model维度的四元组存储,面向的需求是在已知model,检索model对应的object, predicate以及subject(即[O,P,S]三元组,也称为triple)集合。

model维度的四元组存储涉及两个问题,一是如何把model到三元组集合的映射关系保存下来,二是如何把三元组集合保存下来。在4store中,前者是通过mhash来实现的,而后者则提供了tlist和tbchain这两种方法来实现。下面我们将分别介绍mhash、tlist以及tbchain的具体实现。

mhash

typedef struct _fs_mhash_entry {
    fs_rid rid;
    fs_index_node val; // 0 = unused, 1 = in separate file, 2+ = in list
}FS_PACKED fs_mhash_entry;

mhash是用来映射model的rid和该rid对应的[O,P, S]三元组集合的。虽然mhash和rhash的源码是独立写在两个文件中的,但两者在实现上是完全相同的(忍不住吐槽一下代码重用性)。我们可以将mhash视为rhash的一种特例,只是mhash中没有bucket这个概念(或者我们可以认为mhash是bucket_size为1的rhash)。另外,mhash中的entry也没有rhash的那么复杂,从上面fs_mhash_entry的定义中可以看到,它只存储一个rid和一个4字节的整型val。

关于mhash的具体实现就不再此重复展开,感兴趣的同学可以参见我们的4store源码解析(2)中的”Hash实现“这部分内容。

fs_mhash_entry

根据4store的配置,在存储triple时可以选择以下两套方案中的一种:

  • 方案一:对于每个model的triples分别独立存储在一个tlist(即triple list的缩写)文件结构上。fs_mhash_entry.val只取值0和1,值为0表示mhash尚未记录该model的rid,值为1表示已经被存入到独立的文件中。
  • 方案二:在一个名为tbchain(即triple block chain的缩写)的文件结构中存储所有models的triples。fs_mhash_entry.val可以取0和2、3、4…等值,值为0依旧表示mhash尚未记录该model的rid,值为非0值表示当前model的rid在tbchain中最后一个block位置。

无论是tlist还是tbchain,都仅支持triple添加操作,不提供删除的接口,而且也没有提供随机读取某个位置的triple的接口,只能对所有triples进行顺序读取。

在默认情况下,4store使用的是tbchain来存储triple的。

tlist

struct tlist_header {
    int32_t id;
    int32_t superset;
    int64_t length;
    char padding[496];
};

tlist

tlist中添加triple的操作步骤如下:首先,判断当前内存中存储triple的buffer的位置是否已满。若buffer已满,则将buffer中的triples flush至文件中。然后,将当前triple,添加到buffer中。

tlist_header中虽然也包含superset这个域,但这个域目前并没有在任何地方被实际使用到。

tbchain

tbchain的存储结构和操作

#define FS_TBLOCK_LEN    5  /* in triples */
#define FS_TBLOCK_SIZE 128  /* in bytes */
typedef struct _fs_tblock {
    fs_index_node cont;
    uint8_t length;
    uint8_t flags;
    uint8_t padding[2];
    fs_rid data[FS_TBLOCK_LEN][3];
}FS_PACKED fs_tblock;

fs_tblock

tbchain虽然相比于tlist功能更加丰富,但其实现依旧是十分简单易懂的。

tbchain在存储时,不在以一个triple为单位,而是以block为单位,从而减少文件读写操作,提升tbchain的效率。从fs_block的定义可知,一个fs_tblock占用128个字节,可以支持存储5个triple。mhash在设计上定义了fs_mhash_entry.val只有在2、3、4…等值下才表示tbchain中的block位置,因此tbchain的前两个block位置是被留空的(下图中,由于空间限制将这两个block位置省略了)。

tbchain中,一个model下的blocks通过cont来串连,其添加triple的操作步骤如下:首先,判断当前要添加的block位置是否已经满了。若block为满,则直接添加triple到该block;若已满,则申请一块新的block之后再添加triple。在申请block时,优先考虑从free_list中获取之前清理出的block。若free_list没有空余block,则向文件末尾添加新的block。

tbchain是将所有model对应的triples存到一个文件中,各个model的triples虽存储在独立的block chain上,但都是在同一个文件的。在删除某个model时,则不能像tlist那样直接删除对应独立的tlist存储文件,而是只能在tbchain中加入一个remove_chain的操作,来回收该被删除model chain上的blocks。remove_chain操作是通过将这个被删除chain上的每个block连接到free_list所在的chain上来完成的。free_list作为一个资源回收者,也利用cont域来串连这些被清理的blocks。类似于这种通过free_list和元素中的cont指针来完成资源回收的思路,在4store中被广泛使用,在下一篇中还将见到许多包含free_list的数据结构实现。

下面我们通过一个例子来帮助大家理解tbchain如何进行triple的存储:

tbchain

在上面的示意图中有四个状态,分别对应的tbchain的四个不同状态,分别是:初始状态、向未满的block中添加triple、向已满的block中添加triple以及remove_chain。

tbchain的删除问题

typedef enum {
    /* bit set on first block if chain is sparse */
    FS_TBCHAIN_SPARSE = 1,
    /* bit set on first block if chain has triples that don't appear in the
         * graph */
    FS_TBCHAIN_SUPERSET = 2,
} fs_tbchain_bit;

在tbchain中,每个block都有一个flag域。flags值实际有两个bit位可以被置值。若两位值皆为0时,表示该chain上所有元素都存在;若第1位的值为1时,表明该确认该chain上有triple在ptree上不存在;若第2位的值为1时,表明该chain中有某个或某些triple已经被删除。从目前通读代码的情况来看, FS_TBCHAIN_SPARSE 虽然是在fs_tbchain_it_next中被设置,但该值仅在print这个非功能性的函数中出现,对于存储和检索逻辑并没有影响。但是,FS_TBCHAIN_SUPERSET的flag值,还是对检索会有很大影响的。

tbchain虽然不支持triple的delete操作,但有了FS_TBCHAIN_SUPERSET这个flag,就可以在检索时知晓该chain是否包含被删除的triple。FS_TBCHAIN_SUPERSET的flag仅在fs_delete_quads 时对涉及删除操作的model所在chain置值。对于tbchain遍历检索时,会检查chain第一个block上的flag。若flag被置位,则在访问该chain的block上的triple时,还会检查ptree中是否包含该值。因此,一旦出现规模较大的quads的删除操作,就可能会导致在使用tbchain遍历访问时,会有较大的性能瓶颈。

事实上,并不是只有tbchain有FS_TBCHAIN_SUPERSET的flag来指示其chain的状态,tlist在文件头中的superset域也应该具有同样的功能,只是tlist只是保留了这个域,并没有在实际中被使用起来。由此可见,tlist和tbchain在功能上是完全一样,唯一的区别在于是否将每个model的triples存储在独立的文件中。至于在性能上哪种实现更有优势,有待进一步实验论证。

发表评论