4store源码解析系列(1)–存储结构概述

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

前言

4store是一个RDF分布式存储和检索系统,其项目主页地址为http://4store.org/。 虽然源码都公开了,但是因为文档太稀缺,注释太少,再加上稍显混乱的C语言结构,让人很难去了解其实现细节。笔者和小伙伴两个人坚持看了一阵子,终于有些顿悟,打算做一个系列的学习笔记分享,以帮助那些同样对4store实现感兴趣的同学(估计是小小小众的)来一起入门。废话不多说,第一篇文章我们来对4store的整体存储结构做个概述,这样看起代码来会有个整体的脉络。至于各个数据结构的细节,会在后续文章中逐个详细分析。

资源id的保存

首先来看一个turtle [http://www.w3.org/TR/turtle/] 格式的RDF三元组:

<http://rdf.ali.com/ns/m.7727> <http://rdf.ali.com/ns/rdf-schema#vname> "Pisen/品胜" .

解析的时候这三列就对应了subject, predicate, object。此外4store中还多存储了一个model列,对应于RDF中的命名图或默认图。所以一个RDF三元组在4store中是以一个四元组[m, s, p, o]的格式来表示的。任何一个四元组当中的元素,在4store中都被称作资源,对应唯一的64bit的资源id(rid)。资源可以分为三种,分别是URI, literal, blank node,rid的最高两位bit表示资源类型,例子中的subject和predicate都属于URI类型,object则属于literal类型。对于URI类型和literal类型的资源,都有源字符串。rid到源字符串的映射关系,是通过fs_rhash来存储的。rhash的结构如下:

rhash1

rhash在保存字符串时有多重策略,disp字段表示了存储的策略。如果字符串小于等于15个字符串,直接保存到hash entry的str[]里面,如果超过15个字符,则字符串内容保存到lex文件中,hash entry里面保存offset, 另外对于URI类型的资源来说,会对频繁出现的字符串前缀编码,保存到prefix文件中,hash entry中的pstr字段保存prefix code。

四元组的保存

四元组的保存有两个维度,一个是在model维度,保存这个model下的所有三元组,另一个是在predicate维度,保存这个predicate关联的model, subject, object。我们先来看model维度的存储结构。

model维度的结构

结构图如下:

mhash1

大致来说,一个model下的所有三元组[s, p, o]会分块保存到文件中,不同的块之间通过指针链接起来。

predicate维度的结构

结构图如下:

ptree1

4store中会将每个predicate关联的[m,s,o]都记下来,为了支持s和o两个维度的快速查找,分别对s和o建了trie树索引。其中trie树每层的分支数为4(每层使用rid的两位),trie树的叶子节点指向pairs数组中属于该p & s或者p & o的首个元素。

粗略的概述就到此结束了,相信大家和我们一样,在很多细节的地方都还有很多疑问,没关系,后续的文章我们会逐个细细分析,敬请期待。

发表评论