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

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

客户端的triple查询处理

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

缓存处理

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

首先，我们来回顾一下一条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查询逻辑：

判定当前query是否适用于加入缓存，若不适用则直接向服务器查询结果；
若适用，则计算cache_key，并判定cache_key指向的缓存中是否有记录；
若缓存命中，则返回缓存的结果；
若缓存没有命中，则继续向服务器查询结果；
检查服务器返回结果，若结果集不大，则将其插入到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等操作

基本步骤

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

它的基本步骤如下：

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

那么，是否我们每次找到一个需要查询的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即可。

由 udpwork.com 聚合
|
评论: 0
|
要! 要! 即刻! Now!