[译]Presto 核心数据结构:Slice、Page、Block

栏目: IT技术 · 发布时间: 4年前

内容简介:在 Presto 中,我们需要了解一些非常重要的数据结构,例如,Slice,Block 以及 Page,下面将介绍这些数据结构。从用户的角度来看,Slice 是一个对开发人员更友好的虚拟内存,它定义了一组 getter 和 setter 方法,因此我们可以像使用结构化数据一样使用内存:

在 Presto 中,我们需要了解一些非常重要的数据结构,例如,Slice,Block 以及 Page,下面将介绍这些数据结构。

1. Slice

从用户的角度来看,Slice 是一个对开发人员更友好的虚拟内存,它定义了一组 getter 和 setter 方法,因此我们可以像使用结构化数据一样使用内存:

[译]Presto 核心数据结构:Slice、Page、Block

Slice 常用来表示一个字符串:

// use it as utf8 encoded string
Slice slice = Slices.utf8Slice("hello");
Slice subSlice = SliceUtf8.substring(slice, 1, 2);

我们可以像使用字符串一样使用 Slice,Presto 为什么选择 Slice 而不是 String:

  • 字符串创建代价昂贵(字符串拼接,StringBuilder等)。

  • Slice 是可变的,而 String 是不可变的,因此当我们需要进行字符串计算时,效率更高。

  • 字符串在内存中编码为 UTF16,而 Slice 使用 UTF8,这样可以提高内存效率。UTF16 最少使用两个字节来表示一个字符,而 UTF8 最少使用一个字节,因此,如果 String 内容主要是 ASCII 字符,则 UTF8 可以节省大量内存。

Slice(在 Presto 中)的另一种用法是表示原始字节(SQL中的 VARBINARY 类型):

// use it as raw bytes
block.getSlice().getBytes()

2. Block

由于 Page 由 Block 组成,因此我们首先介绍 Block。Block 可以认为是同一类数据(int,long,Slice等)的数组。每个数据项都有一个 position ,总位置个数代表 Block 中数据的总行数(Block 仅保存这些行中的一列)。

[译]Presto 核心数据结构:Slice、Page、Block

Block 定义了好几套 API,其中一个是 getXXX 方法,让我们以 getInt 为例:

/**
    * Gets a little endian int at {@code offset} in the value at {@code position}.
    */
default int getInt(int position, int offset) {
    throw new UnsupportedOperationException(getClass().getName());
}

通常,一个 Block 仅支持一种 getXxx 方法,因为一个 Block 中的数据都来自同一列,并且具有相同的类型。

Block 定义的另一个方法是 copyPositions,来代替从 Block 中获取某个值,通过返回一个新的 Block 来从指定的位置列表获取一组值:

/**
 * Returns a block containing the specified positions.
 * All specified positions must be valid for this block.
 * <p>
 * The returned block must be a compact representation of the original block.
 */
Block copyPositions(List<Integer> positions);

Presto 还定义了 BlockEncoding,定义了如何对 Block 进行序列化和反序列化:

public interface BlockEncoding {
    /**
     * Read a block from the specified input.  The returned
     * block should begin at the specified position.
     */
    Block readBlock(SliceInput input);

    /**
     * Write the specified block to the specified output
     */
    void writeBlock(SliceOutput sliceOutput, Block block);
}

我们以最简单的 BlockEncoding:IntArrayBlockEncoding 为例,其 readBlock 如下所示:

int positionCount = block.getPositionCount();
sliceOutput.appendInt(positionCount);

encodeNullsAsBits(sliceOutput, block);

for (int position = 0; position < positionCount; position++) {
    if (!block.isNull(position)) {
        sliceOutput.writeInt(block.getInt(position, 0));
    }
}

3. Page

Page 由不同的 Block 组成:

public class Page {
    private final Block[] blocks;
    private final int positionCount;
    ...
}

除 Block 外,Page 还有另一个称为 Channel 的概念:每个 Block 都是该 Page 的 Channel,Block 的总数就是 Channel 数。因此,让我们在这里总结一下数据是如何结构化的,当要发送一些行时,Presto 将:

  • 将每一列放入单独的 Block 中。

  • 将这些 Block 放入一个 Page 中。

  • 发送 Page。

Page 是保存数据并在 Presto 物理执行算子之间传输的数据结构:上游算子通过 getOutput() 产生输出:

/**
 * Gets an output page from the operator.  If no output data is currently
 * available, return null.
 */
Page getOutput();

下游算子通过 addInput() 方法获取输入:

/**
 * Adds an input page to the operator.  This method will only be called if
 * {@code needsInput()} returns true.
 */
void addInput(Page page);

[译]Presto 核心数据结构:Slice、Page、Block

就像 Block 一样,Page 也需要序列化和反序列化,序列化发生在工作进程之间传输数据时。 Page 进行序列化时,首先使用相应的 BlockEncoding 对 Block 进行编码。 如果有压缩器,将尝试对编码的块数据进行压缩,如果压缩效果良好(编码率低于0.8),将使用压缩数据,否则使用未压缩的数据。 编码后的块数据将与一些统计信息(压缩前后页面的字节大小)一起放入名为 SerializedPage 的类中。

4. 总结

我们介绍了 Presto 中三个核心数据结构:Slice,Block 和 Page。简而言之,Slice 是对开发人员更友好的虚拟内存,Block 代表列,Page 代表行组。

[译]Presto 核心数据结构:Slice、Page、Block


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

数据结构与算法分析

数据结构与算法分析

韦斯 / 机械工业 / 2007-1 / 55.00元

本书是国外数据结构与算法分析方面的标准教材,使用最卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。   随着计算机速度的不断增加和功能的日益强大,人们对有效编程和算法分析的要求也在增长。本书把算法分析与最有效率的Java程序的开发有机地结合起来,深入分析每种算法,内容全面、缜密严格,并细致讲解精心构造程序的方法。   第......一起来看看 《数据结构与算法分析》 这本书的介绍吧!

URL 编码/解码
URL 编码/解码

URL 编码/解码

MD5 加密
MD5 加密

MD5 加密工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换