博客

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，在一些特殊场景下可能会不够用。

发表回复