4store源码解析系列(6)–查询处理细节

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

在上一篇中,我们对4store查询的基本流程进行了梳理。在这一篇中,我们将对查询在客户端和服务端的一些处理细节展开讨论。

客户端的triple查询处理

关于triple查询的最底层实现,我们在上一篇源码解析中已经具体介绍了,我们这里要讨论的是在底层查询接口之上的一些优化和处理。

缓存处理

一般来说,在单条query查询语句中虽然可能涉及多条triple查询,但这些triple查询请求很少会重复。但是,我们在使用4store进行多次query查询时,则很有可能会出现重复的triple查询了。我们这一节中所说的缓存处理,就是针对重复的triple查询而设计的。

BIND_LIMIT_MSG

首先,我们来回顾一下一条triple查询语句有哪些元素。在上一篇中,我们提到的flag域、[M, S, P, O]的rids,决定了这次查询的主要内容。细心的同学会发现,在那篇文章的示例图中,还有limit和offset这两个域,它们也是triple查询的一个组成部分。limit和offset主要用在LIMIT和OFFSET这两个关键字上,关于它们的使用说明,可以详见文档。除此之外,query是否需要向所有的segment发送,也是一个隐式的属性。

4store在处理triple查询的缓存时,并不是所有triple查询结果都缓存的。它仅缓存[M, S, P, O]中每项查询条件,不包含多个rid的情况。而且,查询结果中包含过多结果时(大于10000条),也不进行缓存。缓存使用一个数组指针来保存,在查询和插入缓存时我们就需要一个cache_key作为这个数组的下标。我们使用flags、limit、offset、以及all(即是否向所有segment发送的属性)以及[M, S, P, O]的rid值,进行了一些异或等数值处理,来得到这个cache_key。

完整的triple查询逻辑:

  1. 判定当前query是否适用于加入缓存,若不适用则直接向服务器查询结果;
  2. 若适用,则计算cache_key,并判定cache_key指向的缓存中是否有记录;
  3. 若缓存命中,则返回缓存的结果;
  4. 若缓存没有命中,则继续向服务器查询结果;
  5. 检查服务器返回结果,若结果集不大,则将其插入到cache_key指向的缓存位置。

权限管理

4store中提供了非常简单的权限管理功能。其实现机制如下:

  • 向服务器端发起一次特殊的triple查询请求,查询服务器端记录的权限管理记录
  • 根据查询结果中的配置,来建立具体哪些graph是哪些用户可以访问的映射
  • 对于每一次的triple查询结果,首先获得当前用户没有访问权限的model列表
  • 依次检查每条triple查询结果中mrid,将其中没有访问权限的那部分结果剔除

这个特殊的triple查询请求,与包含了正常triple查询的所有元素,只是其mrids是system_config,而prids是fs_acl_admin和fs_acl_access_by,而srids和orids则都留空,表示需要返回它们的值。简单理解这条查询的含义,就是向system_config这个model,查询predicate为fs_acl_admin或fs_acl_access_by的三元组的值。fs_acl_admin在返回值的object域中返回所有admin用户的rid。fs_acl_access_by在返回值的subject域是model的rid,对应于object是拥有这个model访问权限的用户的rid。有了这些权限记录表,就可以非常容易判断特定用户对于某条triple查询结构是否有访问权限了。

需要特别注意的是,权限过滤是在获得triple的查询结果之后,在客户端进行处理的,并不是在服务器端执行的。目前这种设计,可以减少服务器端的处理压力,但是却存在着很大的安全隐患。4store在数据传输时并没有任何加密保护,在客户端进行数据的权限管理,过滤不符合权限的结果数据。如果我们要将4store用于敏感信息的存储和查询,这部分必须重新设计。

客户端资源查询处理

查询rid对应资源内容的需求主要来自以下几个方面:

  • 资源内容被query语句显示要求查询,如SELECT
  • 资源内容涉及到expression的计算
  • 资源内容涉及到order等操作

基本步骤

FS_RESOLVE_ATTR_MSG

根据rid来查询资源的请求是4store中最为简洁的几种命令之一。

它的基本步骤如下:

  1. 在客户端收集需要查询资源的那些rid,并对这些rid去重
  2. 对这些rid根据其资源内容所属的segment进行分类
  3. 对每一类的rid数据,按照如上图所示的消息格式进行编码,并发送给客户端
  4. 服务端收到消息后,从rhash和tbchain/tlist中获取资源的具体内容
  5. 将查询到的资源打包发送回客户端(资源打包的格式与请求消息类似)

那么,是否我们每次找到一个需要查询的rid就马上向服务端发起一个资源查询请求呢?显然这样的做法是十分低效的,会将大量的时间浪费在网络交互上,同时还可能在服务端引起频繁的IO请求。

下面我们将具体描述资源获取在客户端的优化。

资源预获取和两级缓存

上文所述的每个rid进行一次查询请求的做法,显示是每个人都会去避免的。查询资源内容的需求中,都是需要我们遍历整个query查询结果中的所有rid。因此一种比较常见的查询做法,会先过滤出查询结果中需要与服务端交互的那些rid,然后再具体编码消息,获取具体资源内容。

但是,我们还需要考虑一些比较特别的情况:如果query查询的结果非常大,我们是否依旧一次性将所有需要查询的rid值进行查询呢?实际应用场景中,收到本身rdf存储量、query设计等因素影响,查询结果是很有可能出现较多的情况。

在4store中的资源查询中,使用了一种prefetch的机制,来避免上述提到的频繁请求和一次性请求大量结果的问题。在遍历query查询结果,每次尝试获取一行所需的资源内容时,会先检查当前是否需要进行一次资源预获取。若需要,则预先查询从当前行开始的前几千行结果中的rid对应的资源内容,并将这部分内容进行保存;下一次资源预获取则会发生在遍历完这几千行结果之后。当query的结果较少时,这种机制下会一次将所有需要的资源内容全部获取了。当query结果非常多时,则会分批次处理,来获取资源内容。

在资源内容的结果保存中,4store又采用了一种两级缓存机制。第一层缓存,称之为L1,由一个hash表实现,主key是rid,value是对应的资源内容。第二层缓存,称之为L2,有一个定长的资源内容数组组成,通过rid取余来获取数组的访问下标(取余,可以视为最简单一种hash)。L1缓存有冲突解决机制,使用的glib提供的hash实现。而L2则并不存在冲突解决机制,当插入值遇到冲突时,会直接进行替换。

_

两级缓存机制是配合着之前资源预获取机制一起工作的。具体来说:

  • 每次进行资源预获取前,先将L1中的内容插入到L2中,同时清空L1
  • 将资源预获取请求所得的资源内容,插入到L1中
  • 当请求rid对应的资源内容时,则会先检查L2中是否存在符合条件的资源,然后再检查L1。若都不存在,则再向服务端请求单条的资源内容。

如上图所示的示例中,每6条query进行一次prefetch。每次prefetch检查结果中需要查询资源内容的rid,例子中需要查询的是srid和orid。每次查询前,先将L1的结果导入到L2,然后再将查询的资源内容导入到L1中。实例中,表现的是三个状态的结果。第一个状态描述的是,L2为空,L1中保存着此次prefetch到的rid和对应的资源内容。第二个状态描述的是,L2中保存着从L1中导入的结果,L1中保存着第二次prefetch到的资源内容。第三个状态描述的是,L2中保存着前两次从L1中导入的结果,L1中保存着第三次prefetch到的资源内容。为了方面阅读,图中还将从L1到L2导入资源时,每个位置最后一个drop out后的资源值也表示了一下;在实际实现中,并没有drop out列。

需要注意的是,tmp_resource中也会保存一些资源,这部分资源值并不是直接从服务端获取所得,而是一些经过expression计算之后的资源值。在请求rid对应的资源内容时,也会在tmp_resource中进行检查。tmp_resource的实现机制与L1类同,除了其并不会在资源预获取时进行清理。

看到这里,可能你不禁会问:为什么需要双层缓存机制?如果我们只使用L1,在只进行遍历的query结果任务时,并不会有太多问题。但是,若我们偶尔需要访问前几行结果中的资源内容时,则很可能因为L1刚刚被清理,而出现访问失败。使用一个L2后,用一个很小的开销,可以将一些最近访问的资源内容进行缓存。

服务端的triple查询处理逻辑

triple查询在服务端的处理,是按照查询的不同条件来分别实现的。

在分条件讨论处理逻辑之前,我们再对triple查询的消息进行解读。首先是消息中flag域,flag是一个32位的整型变量,4store使用了其中的20个bit,来标记查询请求的一些信息。

#define FS_BIND_MODEL              0x01
#define FS_BIND_SUBJECT            0x02
#define FS_BIND_PREDICATE          0x04
#define FS_BIND_OBJECT             0x08
#define FS_BIND_BY_SUBJECT        0x1000000
#define FS_BIND_BY_OBJECT         0x2000000

上面代码中,列出了其中服务端处理中涉及的最主要的6个bit。flag的底四位bit:FS_BIND_MODEL、 FS_BIND_SUBJECT、 FS_BIND_PREDICATE 和 FS_BIND_OBJECT 用来说明这一次triple查询,[M, S, P, O]这四个域的变量有哪些是需要返回rid结果的。在第四篇的源码解析中,我们可以知道四元组信息分了两组ptree来存储,一组是用S来作为ptree的key,另一组则使用了O。而 FS_BIND_BY_SUBJECT 和 FS_BIND_BY_SUBJECT 这两个bit,就是用来指定这一次的triple查询,分别需要使用S为key和O为key的ptree来进行查询。

消息中还有一个重要组成部分就是mrids、srids、prids以及orids。它们中的任意一个长度不为0,则表示这一次triple查询中对应的M、S、P以及O是已知条件。

根据flag的以上6个bit值以及mrids、srids、prids、orids的长度信息,一次triple查询在服务器端的逻辑就可以确定了。flag中还有一些其他bit位,同时消息中也还有offset、limit等域,则是作为查询结果的辅助过滤条件存在,并不会影响服务端的查询主逻辑。

接下来,我们就分别讨论4store定义的每一项服务端triple查询条件及在该条件下的具体查询步骤。

查询model列表

直接访问mhash,获取其所有的key,就可以作为结果返回了。我们在第三篇的源码解析中,有具体介绍mhash的设计。hash文件中,entry是定长的,虽然保存的内容不连续,但是也可以通过entry位置的val值来得知其是否有效。因此,要获取所有的key,只需要读取odels.mhash这个mhash的文件,然后按照entry大小遍历这个文件,将其中被使用的entry全部返回。

查询predicate列表

可以直接访问保存的predicate列表。4store中,还会加载列表中每个predicate对应的ptree文件,检查其存储的二元组内容长度,过滤掉空ptree。

已知P(且唯一),查询O

在具体展开查询之前,我们先回顾一下ptree及其实现,详见第四篇源码解析。ptree是一个保存从O到ptable入口的映射或是从S到ptable入口的映射的tie树。predicate列表保存着一系列ptree指针,由一个hash表实现从P到predicate列表的下标位置的映射。其中映射O的ptree,称为ptree_o;从映射S的ptree称为ptree_s。ptree的每个entry,指向这个rid的key对应在ptable中存储的[M, S]或[M, O]列表的入口。[M, S]或[M, O]二元组在ptable中本质上一种链表的存储方式。

接下来我们具体展开查询的具体步骤:

  • 根据P,查询其在predicate列表的入口
  • 从入口找到P对应的ptree_s
  • 遍历ptree_s中的每一个entry
  • 根据entry指向的ptable入口,访问其中的[M, O]二元组列表
  • 收集所有访问过的[M, O]二元组中的O,并将其返回

其中,遍历ptree的操作,是这边需要特别说明一下的。在源码实现中,使用了两个goto和一个stack 来避开递归搜索。整体遍历使用了一个深度优先的做法,依次遍历每个叶子节点的每个branch检查,并将其他尚未访问的branch加入到stack中。

已知M,查询[S, P, O]

这里需要我们更进一步的了解第三篇的源码解析中关于mhash以及tlist和tbchain实现的介绍。关于查询的基本步骤如下:

  • 通过mhash,找到M对应的[S, P, O]存储链位置。
  • 若是tlist实现,则mhash只作为确定M对应的model是否存在用。访问tlist可以直接通过M的值,找到对应文件。然后依次读取其中存储的[S, P, O],并返回。
  • 若是tbchain实现,则mhash映射了M到其对应的triple chain在tbchain文件中的入口位置。然后通过tbchain的链表结构,依次访问chain上的每个[S, P, O]元素,并返回。

从S维度查询,且S未知,查询其他

首先,我们可能会好奇为什么会设计这样的请求。从S维度查询,且S未知,查询其他虽然没有提到O,但其隐含着一层含义,即O未知(至于其是否需要返回值,则由具体的triple查询语句决定)。因此,解决这个问题比较简单的方式,是按照要求使用ptree_s来进行遍历的查询。此外,而M, P则皆有可能是限制条件。根据P的值是否已知,可以分情况来讨论。

P已知

此时,作为与已知P(且唯一),查询O的情况基本一致,具体步骤:

  • 根据P,查询其在predicate列表的入口
  • 从入口找到P对应的ptree_s
  • 遍历ptree_s中的每一个entry
  • 根据entry指向的ptable入口,访问其中的[M, O]二元组列表
  • 过滤所有访问过的[M, O]二元组(过滤仅有可能M被显示定义的情况发生),并将其中符合条件的返回

P未知

与P已知的情况的区别在于,增加一层遍历维度。此时需要遍历predicate列表,对列表中的每个P,然后再执行与P已知相同的操作。

S和P已知,查询其他

这是一种标准的需要我们访问ptree_s来进行高效查询的条件,它不需要像之前那样进行ptree的遍历操作。具体的查询步骤如下:

  • 根据P,查询其在predicate列表的入口
  • 从入口找到P对应的ptree_s
  • 根据S,在ptree_s中查询entry
  • 根据entry指向的ptable入口,访问其中的[M, O]二元组列表
  • 过滤所有访问过的[M, O]二元组(过滤仅有可能M被显示定义的情况发生),并将其中符合条件的返回

需要注意的是,4store中还定义了一个conjuctive(应该是单词conjunctive,源码中拼写错误)。conjuctive指的是,选择从S维度查询,查询已知P和S,且两者数量相同,或者选择从O维度查询,查询已知P和O,且两者数量相同。满足conjuctive条件的查询,认为每一行的P和S(后者情况是P和O),同时对一次triple查询起约束作用,是一种类似逻辑的AND关系。

更具体来说,若我们查询的时候,已知3个P(P1、P2、P3)和2个S(S1、S2),则我们需要分别查询到满足P1S1、P1S2、P2S1、P2S2、P3S1、P3S2条件的结果。若我们查询的时候,选择从S维度查询,且已知3个P(P1、P2、P3)和3个S(S1、S2、S3)则满足conjuctive条件,则我们只需要查询满足P1S1、P2S2和P3S3条件的结果。

在进行S和P已知,查询其他这种查询的时候,需要考虑conjuctive条件的查询。

P和O已知,查询其他

这是一种标准的需要我们访问ptree_o来进行高效查询的条件,它也不需要对进行ptree的遍历操作。其具体操作与S和P已知,查询其他情况下完全一致,也需要注意conjuctive条件的查询。

其他情况

首先,这里的其他情况可以比较确定的是P是未知的。因此,在P维度上只能进行predicate列表的遍历。[M, S, O]则都可能是已知的,来约束查询。

4store在这里的做法,是分成是否定义了S维度查询这个关键字,来确定使用ptree_s遍历还是ptree_o遍历。无论哪种遍历,都是嵌套的[M, S, O]三层循环的条件遍历。

若已定义从S维度查询,其具体的步骤如下:

  • 遍历predicate列表
  • 找到列表每一项中对应存储的ptree_s
  • 根据S,在ptree_s中查询entry
  • 根据entry指向的ptable入口,访问其中的[M, O]二元组列表
  • 过滤所有访问过的[M, O]二元组,并将其中符合条件的返回

若未声明查询维度,其查询逻辑与已定义从S维度查询一致,将其中的ptree_s替换为ptree_o即可。

发表评论