背景

  1. Dremel的推出,在一定程度上减轻了Google内部对于MapReduce系统的依赖。
  2. 但是随着数据规模的增大和Google内部对ad hoc查询(即席查询)需求的增多,Google设计和开发了新的交互式查询系统PowerDrill。
  3. ad hoc查询是用户根据自己的需求,灵活地选择查询条件,系统根据用户的选择生成相应的统计结果。
  4. 通常的查询在系统设计和实施时是已知的,所以我们可以在系统构建时通过建立索引、分区等技术来优化这些查询,达到提升查询效率的目的。
  5. 但ad hoc查询是用户在使用时临时产生的,系统无法预先优化这些查询,因此需要通过其他技术手段来实现高效的ad hoc查询。

设计目标

通过对内部数据和查询类型的分析,PowerDrill开发团队得出了以下两个假设结论,整个系统的开发和优化都基于这两个假设:

  1. 绝大多数的查询是类似和一致的。
  2. 存储系统中的表只有一小部分是经常被使用的,绝大部分的表使用频率不高。

在这两个假设的指导下,为了实现高效的查询,PowerDrill开发团队主要考虑如下两方面的内容:

  1. 如何尽可能在查询中略去不需要的数据分块。
  2. 如何尽可能地减少数据在内存中的占用,占用越少意味着越多的数据可以被加载进内存中处理。

与Dremel数据处理方式不同的是,PowerDrill需要尽可能地将数据加载至内存,在某种程度上其计算方式更接近内存计算。PowerDrill整个系统实际分为三个部分:

  1. Web UI,用于和用户进行交互;
  2. 一个抽象层,用户的命令会被转换成SQL,然后根据不同的需求,这些命令会被发送至不同的终端,比如Dremel,Bigtable等;
  3. 列式存储。

基本数据结构

列式存储主要有两个好处:减少查询涉及的数据量以及便于数据压缩。传统的关系数据库一般通过索引来减少查询中用到的数据量,但是在ad hoc查询这样的场景下,索引基本不起作用。PowerDrill采用的方式是对数据进行分块,对块数据设计巧妙的数据结构,使得在查询时可以确定哪些块不需要,可以直接被略去,这样就大大减少了所需的数据量。

图片加载失败

  • 全局字典表:存储全局id和搜索关键字的对应关系。
  • 块字典:记录的是块id(chunk-id)和全局id的映射关系。
  • 块元素:记录的是块中存储数据的块id(注意不是全局id)

假如说我们要的查询字符串为“ebay”,流程如下:

  1. 查询全局数据字典得到“ebay”的全局ID为5。
  2. 查询每个块的块字典.
  3. 在chunk0的块字典中中查询到在chunk0中的3号块存储这对应的信息。
  4. 在chunk1的块字典中中查询到在chunk1中的2号块存储着对应的信息。
  5. 在chunk2的块字典中中查询到在chunk2中的2号块存储着对应的信息。

性能优化

PowerDrill系统更关心查询的时效性,如果对于任何的查询,都需要从磁盘上将数据加载至内存,势必会严重影响查询效率。因此如何在基本的数据结构之上进行全面的优化,使得尽可能多的数据能够常驻内存才是性能得到显著提升的关键因素。在实际的开发中,PowerDrill团队采用了多种优化技术,虽然不是全新的方法,但是组合起来对PowerDrill系统性能的提升还是很显著的。

数据分块

由于传统的索引对于PowerDrill的查询场景作用不是很大,因此一个很自然的考虑就是对数据进行分块,然后通过一些方法过滤查询中不需要的数据块来减少数据量。数据分块的另一个好处就是防止单个数据表过大,导致性能下降。基本上现代的数据库系统都是支持数据分区的,常见的分区方法有范围分区(range partitioning)、散列分区(hash partitioning)等。

PowerDrill实际采用的是一种组合范围分区 (composite range partitioning)方法,大致流程如下

  1. 领域专家确定若干个划分的域。
  2. 利用这几个域对数据进行划分。
  3. 每个块的行数达到阈值时就停止划分。

PowerDrill采用的数据分块方法简单实用,但是由于域的确定需要领域专家,因此这种方法在实际使用中还有一定的局限性。

数据编码的优化

  1. 在实际存储中选择合适的编码方式也很重要。最简单的自然是统一编码,比如对所有的块id都采用32位的整型来记录。
  2. 但是这种方法会带来空间上的浪费。比如一个块中仅有1个不同值,那我们实际只需要记录块中的记录数即可。
  3. 如果有两个不同值,1比特位也就足够了。依次类推,对于不同的块,如果我们可以确定块中不同值的数量,那么就可以根据这个数量值来选择可变的比特位来记录块id。
  4. 统计一组数中不同值的个数有一个专有名词,称为“基数估计”。
  5. 对于小规模的数据集,可以比较容易地统计出精确的基数。
  6. 但是在大数据的环境下,精确的基数统计非常耗时,因此能保证一定精度的基数估计就可以满足实际的需求。
  7. 基数估计的方法很多,大多利用了散列函数的一些特性,Google内部使用的是一种称为Hyperloglog的基数估计方法的变种。

全局字典优化

对于Google的生产环境来说,全局字典是非常庞大的,因此有必要对全局字典进行优化。在优化中主要利用了两个特性:

  • 全局字典是有序的;
  • 排序后的数据常常有共同的前缀。

基于这两个特性,前缀树是一个不错的选择。实际使用中为了进一步减少查询中需要加载到内存的全局字典,对全局字典又进行了分块,因为不同的值使用的频度是不一样的,将最常用的值组织成一个块,全局字典中剩余值再组织成其他若干个块,这样就能保证每次涉及的块较少。除此之外,对每个全局字典块还会维护一个布隆过滤器(bloom filter)来快速确定某个值是否在字典中。

压缩算法

  1. 上面提到过列存储的最大优势之一就是便于数据的压缩,当然不同的压缩算法在执行效率上是有差别的。
  2. Google曾经对一些主流的压缩算法做过简单的测试,但是PowerDrill的开发团队在经过测试之后,最终选择了LZO算法的一个变种作为实际生产环境中的压缩算法,可能是因为LZO算法整体表现比较均衡。
  3. 不管压缩算法的解压速度多快,总会消耗一定的物理资源与时间。
  4. 对此PowerDrill采用了一种冷热数据分别对待的策略。
  5. 即在内存中保有压缩和未压缩的数据,根据需要对数据进行压缩和解压缩。
  6. 在冷热数据切换策略中,比较常用的是LRU算法。LRU是Least Recently Used的缩写,即最近最少使用页面置换算法。
  7. 但是PowerDrill开发团队认为直接的LRU算法效果还不是很理想,为此他们采用了一种启发式的缓存策略来代替原始的LRU算法。

行的重排

有研究表明,在列存储中,对行进行适当的重排不会影响结果且会提升压缩效率。这个是比较好理解的,

性能分析与对比

PowerDrill在Google内部已经使用了一段时间,令我们比较关注的是两组数字:

  1. 在查询过程中,平均92.41%的数据被略去,5.02%的数据会直接被缓存命中,一般仅须扫描2.66%的数据即可得到查询结果。这说明PowerDrill的数据分块策略是比较成功的。
  2. 虽然PowerDrill的设计目标是将尽可能多的数据加载进内存,使得查询能够直接利用内存中的数据完成,但实际使用过程中不可避免地会有查询需要访问磁盘。根据Google自己的统计,超过70%的查询是不需要从磁盘访问任何数据的,这些查询的平均访问延迟大约是25秒。96.5%的查询需要访问的磁盘量不超过1GB。

PowerDrill与Dremel的对比

由于均采用列存储,因此PowerDrill不可避免地被人们拿来和Dremel做对比,但实际上除了都采用列存储之外,二者并没有什么特别共同的地方,相反却有不少区别。

  • 两者的设计目标不同,Dremel用来处理非常大量的数据集(指数据集的数量和每个数据集的规模都大),而PowerDrill设计用来分析少量的核心数据集(指每个数据集的规模大,但数据集的数量不多)。
  • 基本设计理念路不同,主要有:
    • Dremel处理的数据来自外存,PowerDrill处理的数据尽可能地存于内存。
    • Dremel未进行数据分区,分析时要扫描所有需要的列;PowerDrill使用了组合范围分区,分析时可以跳过很多不需要的分区。
    • Dremel数据通常不需要加载,增加数据很方便;PowerDrill数据需要加载,增加数据相对不便。

总的来看,PowerDrill涉及的技术手段并无特别新颖之处,大都是对已有技术手段直接采用或进行改进。