4store源码解析系列(2)–资源ID的存储

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

资源存储处理

资源类型简介

4store的资源主要分成三类:URI、Literal以及Blank Node。

MSB1 MSB2 Encodes
0 Literal
1 0 Blank Node
1 1 URI
  • Blank Node,只有rid,没有文本内容,较前两者区分开,在4store中是单独处理的,先不在这讲中具体介绍了。
  • Literal就是我们常见的各类文本的描述内容,长度从几个字节到成百上千字节不等。Literal中除了一些系统可以解析的number、date等类型,都作为纯文本内容进行处理。
  • 而URI其实也是一段文本,是全局资源描述符的缩写,通常会使用网站地址等作为前缀。

下面是一段RDF文档的实例:

<http://rdf.ali.com/ns/m.110219>    <http://rdf.ali.com/ns/rdf-schema#pvpv> <http://rdf.ali.com/ns/m.626780077> .
<http://rdf.ali.com/ns/m.626780077> <http://rdf.ali.com/ns/rdf-schema#pv1>  <http://rdf.ali.com/ns/m.772718841> .
<http://rdf.ali.com/ns/m.626780077> <http://rdf.ali.com/ns/rdf-schema#pv2>  <http://rdf.ali.com/ns/m.373648303> .
<http://rdf.ali.com/ns/m.772718841> <http://rdf.ali.com/ns/rdf-schema#pname>    "品牌"@zh .
<http://rdf.ali.com/ns/m.772718841> <http://rdf.ali.com/ns/rdf-schema#vname>    "Pisen/品胜"@zh   .
<http://rdf.ali.com/ns/m.772718841> <http://rdf.ali.com/ns/rdf-schema#commonid> <http://rdf.ali.com/ns/m.79258971>  .

在<>中的都是URI,而诸如 “品牌”@zh 以及 “Pisen/品胜”@zh 则是Literal。

下面介绍一下4store中对这两种资源的存储方式:

内存和文件存储结构

4store中,进行资源存储的核心数据结构是rhash。与rhash相关的文件包括:res.rhash、res.rhash.lex以及res.rhash.prefixes。

各个文件的大致结构如下:

resource_files

  • res.hash是其中最常被使用的,存储了每个资源的rid、内容以及类型等关键信息。
  • res.rhash.lex用来存储长度较长的文本
  • res.rhash.prefixes只用于存储了URI中重复出现的prefix文本。

接下来我们来详细分析一下rhash的结构,首先看一下hash entry的结构定义:

typedef struct _fs_rhash_entry {
    fs_rid rid;
    union {
        fs_rid attr;    // attribute value, lang tag or datatype
        unsigned char pstr[8]; // prefix code + first 7 chars
    }FS_PACKED aval;
    union {
        int64_t offset; // offset in lex file
        char str[INLINE_STR_LEN];   // inline string data
    }FS_PACKED val;
    char disp;          // disposition of data - lex file or inline
}FS_PACKED fs_rhash_entry;

fs_rhash_entry使用FS_PACKED来修饰,是为了让最后一个字节内容disp可以对其到第32字节,使得整体fs_rhash_entry的大小为32字节,从而在存储时更容易对齐文件和内存。

fs_rhash_entry

  • fs_rhash_entry的前8个字节存储内容是确定的,就是rid。
  • 第9-16字节是一个union。对于具有language tag, datatype等属性的Literal来说,这8个字节存储了这些属性的rid(属性被当做单独的一个资源来存储和处理)。对于URI来说,这8个字节存储了prefix的相关信息(关于prefix的处理,在下面详细介绍)。
  • 第17-31字节也是一个union,既可以用于直接存储长度较短的文本内容,也可以存储长度较长的文本的在res.rhash.lex文件中的offset。
  • 另外,对于文本长度特别长的Literal,虽然也是将内容存储在文件中,用val.offset来指示文件中的偏移。但是,4store会调用zlib的压缩接口来对文本数据进一步压缩。
  • 最后一个字节的内容,是用来指示当前entry的存储类型,有如下7种:
#define DISP_I_UTF8         'i'
#define DISP_I_NUMBER       'N'
#define DISP_I_DATE         'D'
#define DISP_I_PREFIX       'p'
#define DISP_F_UTF8         'f'
#define DISP_F_PREFIX       'P'
#define DISP_F_ZCOMP        'Z'

DISP_types

上图将fs_rhash_entry在7中不同类型DISP情况下的内存使用进行了示意说明,帮助大家理解。图中,实心的矩形表示uion中这部分字节内容按照这个类型进行解析,空心的矩形表示该字段未被按照这个类型解析或者未被使用。这些不同类型的内存使用方式,有一个非常直观的规则:DISP_F_XXX都需要访问文件,第17-24字节的被作为offset值使用;DISP_I_XXX都将数据存放在32字节的entry中,不访问文件,第17-31字节的内容都是当做str来使用;DISP_X_PREFIX都涉及prefix,没有attr域,第9字节都是prefix code。

Hash实现

#define FS_RHASH_ENTRY(rh, rid) (((uint64_t)(rid >> 10) & ((uint64_t)(rh->size - 1)))*rh->bucket_size)

基本的hash function是非常简单的,对rid进行位右移,然后根据size取余

(代码中虽然使用的是&(size-1)的操作,但是在size为power of 2的情况下,操作等同于%size)。

rhash主要提供了以下三种操作:

get_entry

  1. 通过上文定义的FS_RHASH_ENTRY,使用rid计算出hash表的入口地址
  2. 从entry到entry+search_dist位置的逐个检查entry的rid是否与当前检索的rid相等。 若相等,则表示已经找到。函数直接返回找到的entry
  3. 遍历结束,函数还是没有结束,则表示当前hash表中不存在要检索的entry。返回一个default的val

put_entry

put_entry示例

首先,做一次类似于get_entry 的操作,检查是否已经存在这个entry。

  • 若entry已经存在,只需要更新原来entry的内容。
  • 若发现不存在,则需要考虑是否search_dist内的所有entry都已经被使用了。若没有剩余的entry,则进行一次double_size操作,然后再重新调用put_entry。

完成可用的entry位置定位之后,下一步则是对存储的entry内容进行更新。内容更新环节,rhash因为其自身的优化需要,需要对res的文本内容进一步处理。关于资源处理部分的描述,会在下文具体解释。

需要特别注意的是,在找到空entry时,并不能马上就停止检索search_dist内的其他entry,因为这个空entry有可能是之前被使用节点被替换或者hash表进行了扩展导致的。如上图中最最后一次put_entry操作的情况,如果在找到unused entry就停止scan的过程,直接put数据,则会导致在table中存在两份rid一样的资源内容(且两份内容不一致)。每一次的put_entry操作,必选检查search_dist内的所有entry才能保证,空位置之后不存在rid相同的节点。

double_size

double_size示例

故名思议,这一个步骤就是扩表操作。

整体扩表的操作分成两个步骤

1. 扩大表大小,rhash需要重新映射内存和文件(munmap & mmap)。

2. 遍历读取原表中的每个entry。记录原rid对应的hash地址为org_addr,重算entry.rid对应的hash地址,不妨用new_addr表示。

3. 检查new_addr大小,若大于原hash表的大小(hash_size),则将entry从原位置剪贴到org_addr+hash_size的位置。

这里,特别解释一下entry内容剪切时的目标地址值为什么是org_addr+hash_size而不是new_addr。如上图所示,若依次将数据剪切到new_addr,那么在新的hash table中第四列的数据将和第一列的数据的位置冲突,需要在double_size的数据剪切过程中加入额外的检查过程,相对比较耗费时间。而使用org_addr+hash_size来更新那些new_addr大于hash_size的entry,这种做法虽然不是最大程度还原hash function指示的entry位置,但是在剪切数据时可以完全避开冲突问题。

与传统Hash实现的区别

4store中,扩表的条件相对比较容易到达,只要在search_dist内找不到空的entry,则进行扩表。潜在问题是,若hash function不是非常均衡,一旦单个冲突较高,则会不断double_size。其内存或硬盘的开销是指数级上升的。但是,4store的hash在检索时有个相对的搜索时间上限可以控制,无论是get_entry还是put_entry操作,都之多只进行search_dist次线性数据扫描。

而传统hash实现中,通常会使用一个list的内部结构来挂entry。出现冲突时,将不断使用指向下一个可用位置,直至整个表差不多满了位置。带来的潜在问题则是平均冲突发生时,会需要不断在list上遍历查找entry,导致hash表的性能整体退化。传统hash在整个表的利用率上相对会高一些,但是list结构需要存储next指针,有内存的额外开销。因此,传统hash在处理冲突时可能存在个别检索entry效率低的问题,在内存使用上虽然表的利用率提高了,但整体内存开销是否更加节省,还需视具体应用的数据结构和规模来具体讨论。

prefix

对于URI来说,经常会出现很多前缀非常重复的内容,如<http://rdf.ali.com/ns/m.7727> <http://rdf.ali.com/ns/rdf-schema#vname>。将URI的内容分成重复的prefix和独立的suffix来进行存储,可以有效压缩存储空间。

上文提到的fs_rhash_entry中的9-16字节用于存储prefix的相关信息。其中,第9个字节是用来存储prefix的编码。在suffix较短的情况下,剩余的10-16字节和val.str中的15个字节(共22个字节)被用来存储suffix。若suffix较长,则存入到‘res.rhash.lex’文件中,val.offset`指示其偏移。

rhash中使用过的prefix并非手动指定,而是程序根据读取到资源内容中URI内容的出现频率来生成的。这里使用到的一个关键数据结构就是trie树。Trie树 是一个非常方便存储和检索字符串的数据结构,此处暂不展开,预计在源码解析的下一讲中会再具体介绍其具体实现。

rhash中,使用了两个trie树结构,ptrie和prefixes。ptrie用来记录和统计所有出现过的Literal。当ptrie满了,则从中选择部分出现频率高,长度适合的Literal来作为prefix,加入到prefixes中。但是,若现有的prefix数量已经到达上限FS_MAX_PREFIXES(256)个时,则不再从ptrie中提取prefix。

需要注意的是,目前prefix的索引只用了一个字节保存,大小被限制在256,在一些特殊场景下可能会不够用。

发表评论