0%

《Volcano-An Extensible and Parallel Query Evaluation System》


Abstract

  1. volcano 提供一种方式增强扩展性并且支持并行的方式。 在算子,数据类型,算法,type-specific methods 上极具扩展性。 volcano 不假设任何特定的数据model, 仅仅假设查询基于用参数化算子来进行item tranformation。 为了达到data model 独立, 将processing control 和data item的interpretation 和manipulation 独立开。 可以同时在单进程环境和多进程环境下同时工作, 单进程query evalution plan 可以在shared-memory的机器上并行化, 也可以在distributed 环境下并行化。 并行查询过程的机制是独立算子和语义
  2. 用一种接口(support function)来将关系代数算子和算子实现隔离开,support function 可以轻松增加算子和算子实现,并且支持任意数据类型和任意实现的算子,非预定义的
  3. volcano 提供2种创新的meta-operators, choose-plan 算子和exchange 算子。
  4. choose-plan 算子可以用来干 dynamic query evalution, 并且可以支持延迟plan 优化直到runtime。 动态plan 允许准备多个等价plan, 每个plan 在一定实际参数下的范围下最优。choose-plan 在运行时(其他算子已经明确下来)选择一个plan,
  5. exchange meta-operator 算子支持并行操作, 可以在分区dataset 上进行算子间的并行, 也可以在算子内进行vertical 或horizontal 并行。其他算子可以不用exchange 算子就可以相互之间交换数据。其他算子都是设计为单进程处理环境, 并行由exchange 算子来实现, 其他算子都不考虑并行度, 所有并行问题如分区或data flow都封装在exchange 算子中。 因此data 操作和并行是正交的。
  6. volcano 提供mechanism 来支持policy。 policy 是由人经验或优化器来进行设置


相关工作:
Wisonsin Storage System 是一个record oriented file system 提供heap files, BTree/hash index, buffer, 带谓词的scan
GAMA 是一个分布式集群,通过token ring来连接17台VAX 11/750, 8个cpu 各带一个local disk, 访问使用WSS, 本地磁盘只能被本地cpu 访问, 不带磁盘的cpu 可以用来干join
EXODUS 是一个扩展的database, 带一些想tool-kit 方式的组件, 优化器生成器, storage manager。最开始,EXODUS 设计为data model 独立,但后来一个powerful,结构化的并且支持很多data model的object-oriented 的data model Extra 开发出来


整体框架

  1. volcano 是2层模块组成的library, 含1.5w行代码
image.png
image.png
  1. 2层模块实现动态query evaluation plan和允许并行处理各种算法。 filesystem layer 和query process layer. File system 提供record, file, index 等带谓词的scan 和buffer 系统。 查询层是一套查询的module, 并且支持可以嵌套来组成一个复杂的查询tree。
  2. 单个record上的所有操作都是精心设计为left open。
  3. support function 带合适的参数 传给查询operators


File system
buffer manager 是最有意思的部分, 对性能至关重要, 它被设计支持海量的context和各种policy, 它包含多个buffer pools, 称为clusters的可变长度的buffering unit, 从high level传过来的replacement hint。 buffer manager 仅仅提供机制 (hint 是提供机制来支持灵活的policy的典型范例), pinning, page replacement, reading/writing disk pages, 这些决定来自上层软件的policy, 这些policy 由 data semantics, importance, access pattern 来决定。 buffer manager 主要通过obsered reference 来获得replacement 决定,而不管这个行为是上层软件来决定还是本filesystem 的提前决定。
records/clusters/扩展 组成file。 因为file 操作是一个高频操作, 因此file module 只提供最基本的功能,但这些功能性能最佳。 一个cluster 由一个或多个page 来组成, 它(cluster)是I/O 或buffer 的一个操作单元。 cluster size 由每个文件独立设定。 不同的file 可以有不同的cluster size。文件上的磁盘空间是连续空间,避免磁盘寻道并且更好的预读和write-behind。
RID 来标识一个record, 可以用RID 直接来access 一个record, 为了快速access 大量的record, volcano 不仅支持file/record的操作, 也支持带read-next 的scan和append 操作。 file scan 有2个接口, 其中一个是file scan的标准流程, open, next, close, rewind。 next 返回下个record的内存地址, 这个地址保证pin到内存中,直到下个next 执行时。 获得同一个cluster的下个record不需要调用buffer manager(无内存申请操作),可以高效执行。 另外一套接口是在query process过程中描述。
为了快速创建文件, scan 支持append 操作。 它申请一个record slot并返回这个新slot的内存地址, 由调用者用有效信息来填充这个record space。 append 函数不知道data和它的含义。
scan支持谓词。 next procedure 带参数和一个record 地址 方式来调用predicate function。 selective scan就是一个support function, scan 机制依赖从上层level传过来的predicate function。
support function作为函数entry point 传给 一个operation, 一个无类型指针作为predicate 参数。 可以用2种方式使用support function的参数, compiled和解释型的查询执行。 在编译scan中, predicate evaluation 函数时机器代码, 它的参数可以时一个常量或指向几个常量的指针。 例如当predicate 是比较record field和一个string,comparison function是predicate function, string 是predicate 参数。 在解释型scan中, 一个通用的解释器用于evaluate 查询的所有predicate, 可以传合适的code 给解释器。 解释器的entry point是predicate function。
indices 目前支持B+ tree, 接口类似files 。 一个叶子节点包含一个key和对应的信息(这个信息包含RID, 这个信息可以允许任意内容), key 和信息可以时任何类型, 必须提供一个比较函数用于比较key。 比较函数类似predicate scan 一样使用一个参数。 b+ 树支持类似file 一样的scan, 如predicate和append 操作。除此之外,它还可以支持查询特定的key和 一个确定上下范围的区间。
处理的中间结果(后续称为streams), volcano 使用virtual device, 它是只存在于buffer中, 一旦unpin,他们就消失了。 对于持久化结果或中间结果,都是使用相同的机制来简化实现。
file system 功能基本上都是很常规的, 但他们用一种灵活,高效和compact 方式来实现

query processing
查询用查询plan或关系代数表达式来表示。 关系代数的算子带查询处理算法,可以称这种关系代数为executable 关系代数(物理关系代数), 另外一种是逻辑关系代数(relational 关系代数), 算子可被viewed并被实现为一组object。 实际上,更倾向在一个对象oriented数据库中使用volcano 作为query processing, 使用volcano 的关键是独立 processing 和data item的解释。
所有的关系代数算子都被实现为迭代器, 他们支持open-next-close 协议, 基本上, 迭代器提供一个loop中的迭代组件,如initialization, increment和loop termination condition和最后的housekeeping。 对任意operation结果上的迭代 函数类似对一个传统文件scan结果上的迭代操作。 每个迭代器带一个state record, 它包含一些参数, 如在open过程中申请hash table的大小和 state(hash table的location)。 迭代器的状态信息都存在state record并且没有static 变量, 因此可以在一个query中多次使用算法,只不过使用多个state record。

data object的操作和解释(如比较或hashing)以support function方式(entry point的指针)传给迭代器。 每个support function都使用一个参数。 如果没有support function,迭代器就是空算法壳子。
image.png
迭代器可以嵌套并且可以像coroutine一样操作。 state records之间用input 指针link 在一起, 并且input也保存在state中。 上图显示一个查询plan的2个算子。 filter operator的一个参数是print stream的function。 最顶上的结构可以访问state record和function。 通过指向这个结构的指针, 可以调用这个filter 函数并将他们的local state 作为处理参数传给它。 这些函数(如open-filter)可以使用被包含在state record内的input 指针来调用input 算子函数。 因此当需要时, filter的函数可以调用file scan的函数, 根据filter的需要来推进 file scan。 整体上就是打印一个文件中选中的行。
使用迭代器的标准形式, 一个算子不需要知道是什么算子产生它的输入,不论是复杂查询或一个简单的文件扫描。 我们称这种方式为匿名inputs或streams。 streams是一个简单但powerful的抽象, 允许combine 任意数量和任意类型的算子为一个复杂查询, 是volcano 扩展性的第二个基石, streams 代表了最高效的执行时间(无同步operator)和空间。
对最顶上的算子调用open 会导致实例化对应的state record 的状态(如申请一个hash table)并对所有的input进行open, 通过这种方式, 一个query的所有迭代器都会被递归初始化。 为了处理query, 持续不断call 顶层的next知道碰到end-of-stream 标记。 顶层算子调用next时, 如果他需要更多的input data 来产生output, 他会调用它input的next。 类似close 操作。

许多query或环境变量(query predicate 参数和system load 信息) 会影响policy 的决定,当opening 一个查询plan。 传递这些参数的过程称为bindings。 它是一个无类型指针。 同样用support function来实现policy 的决定。 例如, bindings 参数是在动态query evaluation plan中特别有用。

树形结构的query evaluation plan 通过命令驱动的dataflow来执行query。 next 操作的返回值除了状态标识器外,还有一个Next-Record 结构, 它包含一个RID 和在buffer pool中的record 地址。 pinned在buffer中的record 一次只能被一个operator拥有。 一个算子接受一个record 后, 可以hold 一会儿(如在hash table中), unfix 他当predicate失败或传给下一个operator。 复杂的操作会产生新的record 比如join, 必须在传出output之前组装output 并unfix他们的输入。这导致了大量的buffer call。
一个Next-Record 结构智能指向一个record。当前实现是传完整的record在operators之间。 在join中,会产生新的record,中间涉及不少copy操作, 这容易引起争论, 有一种选择是保留原始的record, 产生一个pairs、triples等。 但这个没有明确实现, 因为volcano已经实现了必要的机制,如filter 迭代器, 可以在一个stream中用一个RID 指针pair 来替换record。

  1. scans, functional join, filter。 第一套scan的接口已经在file system里面介绍了, 第二套scan 接口,可以scan file和b+ 树, 提供迭代器接口。 open 打开file或b+树,用文件系统level的scan 过程初始化scan。 把文件名或关闭的file descriptor 存到state record里面, 是一个可选的predicate和绑定到b+ 树scan。 2种scan接口功能上等价, 区别在于,filestem的scan大量被内部使用,迭代器接口提供在查询plan中的叶子操作。

B+树索引包含keys和RID 在他们的叶子, 想要用B+树的索引, 需要获得record 所在的数据文件。 在volcano中, 这种look-up 操作从B+树scan迭代器中剥离出来,用functional join 算子来执行。 这个算子获得包含RID 的stream records 作为输入,或者输出用RID对应的records, 或者用input record和retrieved record 组成新的record, 这样join b+树的entry和对应的data record。
上例的filter 算子执行3种功能, 依赖stat record 是否含对应的support function。 predicate 函数应用一个选择predicate, 实现bit vector filter。 transform 函数 创建一个新的record, 一般一个全新record。 apply 函数在每个record上调用一次 为了它的side effect受益, 如果update并打印。 filter 算子也是一个side-effect 算子。 filter 算子是一个单入单出的算子,可以干非常多的事情。
one-to-one match, 同filter 算子一起, one-to-one match 算子可能是最高频算子, 它实现了许多set-matching 函数。 在一个算子中, 他实现了join, semi-join, outer-join, anti-join, intersection, union, difference, anti-difference, aggregation, 和duiplicate elimination。 one-to-one match 算子是一个像sort 一样的物理算子。 operator来实现所有的操作, 包含一个item的输出依赖对一对item比较的结果.
image.png
上图显示在one-to-one match 的二元算子的基本规则, 切分matching和非matching 2个set的组件,称为R, S, 产生相应的子集, 可能在一些类似join后的transformation和combination。 因为所有操作基本要求相同的步骤, 因此逻辑上实现吗在一个通用和高效的模块内部。 一元操作(aggregation)和二元(equi-join)操作的区别在于前者是对同一个input进行比较,而后者是对不同input比较。
因为volcano的one-to-one match 是data model 独立, 所有data item上的操作都是通过support function引入的, module不限制为关系模型但可以在任意数据类型上执行set matching 功能。
在传统的hash join(纯内存操作,非hybrid hash join)上, build阶段后,probe 阶段后, 原来的hash table 会扔弃掉, 增加了第三个阶段, 这个阶段用于做aggregation或其他操作。
one-to-one match 算子也是象其他算子一样的迭代器, open 包含build 阶段, 其他2个阶段都包含在next function, 当第二个input exhausted后,自动从probe阶段切换至flush 阶段。
build阶段可以用来去重或在build input上执行aggregation。 one-to-one match module 不要求probe input, 如果只有aggregation而没有后续的join。
hash table 会消耗大量内存,当内存oom时, 称为hash table overflow, 有2种办法解决, 如果用了优化器时, 可以做partition input, 另外一种是,当出现overflow时 创建overflow 文件。 目前volcano 使用hybrid hash join算法。 有一个参数称为packing threshold 表示填充memory 非常快,当hash table中的item数到达这个数,就必须将item 发到overflow 文件(还在buffer中)中,当hash table中item数达到spilling threshold, 这时将第一个分区文件spill到磁盘。除了参数化来避免overflow, volcano 允许cluster size和迭代深度的优化, 类似用于sorting活非统一hash value 分布, 他可以操作变长record。
通过将item组的算子上的contril 和独立item上的解释/控制进行分离, 他可以高频执行大量的set matching task并可以在任意data types和models 上执行这种task。

one-to-many match: 将每个item同许多其他的item进行比较以决定是否产生一个新的item。 典型的是关系division,