Monthly Archives: May 2013

Trevni:一种列文件格式

Version 0.1
草案
本文档是一种文件格式的权威规范,它的意图是允许各种兼容和独立的实现,以便读写这种格式的文件。

概述

数据集通常被描述为由行、列组成的表。每个数据集中的记录被视为行,记录的每个字段被视为不同的列。在以行为主(row-major)格式的系统中,新创建的记录被逐个写入文件,如Hadoop SequenceFile或Avro数据文件。
但在许多情况下,如果数据是以列为主(column-major)的格式进行组织,其中给定列的多个值相邻存储,这样可以实现更高的查询性能。本文档定义的正是这样一种以列为主的数据文件格式。
要允许可扩展的、分布式的查询评估,数据集被划分为行组(row group),包含不同的行的集合。每个行组是按照以列为主的顺序组织的,而这些行组按照以行为主的分区组成整个数据集。

基本原理

目标

这种格式是为了满足以下目标:
1.最大化行组的大小。顺序访问数据时,使用磁盘驱动器是最有效的。假设某驱动器花费10ms进行寻道,以100MB/秒的速度进行传输。如果有一个10列的数据集(所有列值都是相同大小的),被分成10MB的行组,那么,访问单个列将需要一次寻道和1MB的读取,即处理速度为20ms/MB。如果相同的数据集被分成100MB的行组,那么处理速度将提高到11ms/MB。数据集的列越多、列值越小,这种效果就会越夸张。所以,我们偏好100MB或更大的行组。
2.允许行组内的随机访问。某些查询​​将首先检查一列,并且,只有当一些比较少见的条件得到满足,才检查其他列。与通过并行遍历行组中的选定列相比,人们更常见的是遍历其中一列并随机访问其他列。这就是所谓的支持WHERE子句,即SQL中的WHERE操作。
3.数据文件的数量最小化。 HDFS是这些文件的主要预期部署平台,该文件系统中的每个文件都需要HDFS NameNode的内存,因此,为了HDFS友好性(HDFS-friendly),这种文件格式应该努力做到文件的数量最小。
4.支持在行组内对列的协同定位(co-location)。在基于列的数据集中,行组是并行操作的单元。为了高效的文件IO,理想情况下,整个行组应该分布在同一主机上进行查询评估,以避免网络延迟和瓶颈。
5.数据完整性。该格式应允许应用检测数据是否损坏。许多文件系统可以防止数据损坏,但文件可能会在文件系统之间移动的过程中损坏。所以,最好在文件中的数据可以被独立地校验。
6.可扩展性。该格式应允许应用在文件中存储一个数据集的额外信息,如 文件类型信息、来源等。某些环境可能存储了这些信息的元数据,但并非所有的都是这样,并且,文件可能会在系统之间移动,这些系统有不同的元数据体系。因此,在文件中保存类似信息的能力,简化了这些信息的协调过程。
7.最小的开销。列格式不应该让数据集更大。存储是主要的成本之一,选择使用这种格式,不应该需要额外的存储。
8.主要格式。列格式应该被用作数据集的主要格式,而不是作为辅助、加速的格式。那些原本以行为主的顺序对数据集进行处理的应用,应该能够很容易地处理列文件;那些原本以行为主的顺序产生数据集的程序,也应该能方便地生成列文件。

设计

为了实现这些目标,我们提出了以下的设计:
1.每个行组是一个单独的文件。列在一个文件中的所有值被连续地写入。这使得行组的大小最大化,当查询更少、更小的列时性能最优。
2.每个文件占用一个单一HDFS块(block)。可以指定更大的block size,例如,1GB,而不是典型的100MB。这保证了co-location,同时当查询的数据co-located在文件内时避免了网络使用。这也缓和了HDFS NameNode的内存的影响,因为没有小文件的写入。
3.文件中的每一列以64kB的压缩块序列写入。该序列的前缀是描述了列中所有数据块的表,以允许随机存取。
4.应用程序特定的元数据可以是文件、列或数据块级别。
5.为了数据的完整性,每个数据库都包含校验。

讨论

CIF论文描述了一种方法,这种方法是每个文件使用一个单独的数据块,这样也可以达到自定义数据块存放策略相同的效果,同时还允许HDFS rebalancing且不增加命名空间的文件数量。

格式规范

本节正式介绍了列文件格式。

数据模型

我们假设一个简单的数据模型,其中一条记录是一组命名的字段,每个字段的值是一个无类型的字节序列。 在此之上可以有一个类型体系,如同下文类型映射(Type Mapping)一节中所指定的那样。

原型

我们定义了一下原型(primitive value types):

  • long:有符号的64位类型,zig-zag编码,可变长度,其中每个字节的高位(high-order bit)确定是否存在后续字节。例如:
十进制值 十六进制字节
0 00
-1 01
1 02
-64 7f
64 80 01

 

  • bytes:前面是个long值,后面跟着该长度的字节串;
  • string:前面是个long值,后面跟着该长度的UTF-8编码的字符串。
  • 例如,三个字符的string“foo”是这样编码的:
    long类型的3(十六进制06),后面是UTF-8编码的“f”、“o”和“o”(十六进制66 6f 6f),整体:06 66 6f 6f

类型名称

下列类型名称用于描述列值:

  • null,需要0字节,有时候用于数组列(array column)。
  • boolean,1个bit,打包为字节,低位优先(little-endian);
  • int,类似long,但严格限制为32位有符号值;
  • long,64位有符号值;
  • Fixed32,32位,存储为4字节,little-endian;
  • Fixed64,64位,存储为8字节,little-endian;
  • float,32位IEEE浮点值,little-endian;
  • double,64位IEEE浮点值,little-endian;
  • string,见上;
  • bytes,见上,可用于封装更复杂的string类型(UTF-8编码,长度为前缀)。

元数据

元数据(metadata)包含如下:

  • long值,表示元数据的KV值有多少对;
  • 每一对KV中,string类型的key和bytes类型的Value。

所有以“trevni.”开头的元数据属性都是预留的。

文件元数据

文件元数据属性定义如下:

  • trevni.codec:默认的数据块压缩编解码器的名称,string类型。所有实现需要支持“null”值。可选。如不指定则被假定为“null”。下文会有更详细的编解码器描述。
  • trevni.checksum:文件中使用的校验算法名称,string类型。所有实现需支持“CRC-32”校验。可选。如不指定则被假定为“null”。下文会有更详细的校验和描述。

列元数据

列元数据属性定义如下:

  • trevni.codec 用于压缩列数据块的压缩编解码器的名称,string类型。所有实现需要支持“null”值。可选。如不指定则被假定为“null”。下文会有更详细的编解码器描述。
  • trevni.name 列的名称,string类型,必选。
  • trevni.type 列数据的类型,上面类型名称的一种。必选。
  • trevni.values 如果存在,表示此列中的每个块的初始值将被存储在该块的描述符中。不允许数组列或指定了parent的列(参见下面2个)。
  • trevni.array 如果存在,表示此列中的每一行包含了指定类型的一序列值,而不是单个值。每个序列之前都有一个整型的数值表示序列的长度。
  • trevni.parent 如果存在,表示该数组列的长度与指定的parent名称的array列的长度一样。因此,这一列的值也是序列的,但是不会存储长度。

举例说明,假如有以下JSON格式的行,所有的值都是原型,但其中一个有多个值:
{"id"=566, "date"=23423234234
"from"="foo@bar.com",
"to"=["bar@baz.com", "bang@foo.com"],
"content"="Hi!"}

这样的列可能会这样指定:

name=id              type=int
name=date         type=long
name=from        type=string
name=to              type=string         array=true
name=content  type=string

如果有一行包含了一个记录数组,如下面的“received”:
{"id"=566, "date"=23423234234
"from"="foo@bar.com",
"to"=["bar@baz.com", "bang@foo.com"],
"content"="Hi!"
"received"=[{"date"=234234234234, "host"="192.168.0.0.1"},
{"date"=234234545645, "host"="192.168.0.0.2"}]
}

那么,我们就可以在这个记录中的每个字段后面定义一个父列(parent column),即增加以下列:

name=received        type=null           array=true
name=date                 type=long          parent=received
name=host                type=string        parent=received

如果一个数组值本身包含一个数组,如下面的“sigs”:
{"id"=566, "date"=23423234234
"from"="foo@bar.com",
"to"=["bar@baz.com", "bang@foo.com"],
"content"="Hi!"
"received"=[{"date"=234234234234, "host"="192.168.0.0.1",
"sigs"=[{"algo"="weak", "value"="0af345de"}]},
{"date"=234234545645, "host"="192.168.0.0.2",
"sigs"=[]}]
}

那么可以定义嵌套的父列:

name=sigs             type=null            array=true parent=received
name=algo            type=string        parent=sigs
name=value         type=string        parent=sigs

块元数据

目前没有定义块元数据。

文件格式

一个file包括:

  • 一个file header,后面是
  • 一个或多个列(column)

一个file header包括:

  • 四个字节,ACSII ‘T’, ‘r’, ‘v’,后面是1。
  • 一个fixed64,表示文件的行数
  • 一个fixed32,表示文件的列数
  • 文件元数据
  • 每个列的列元数据
  • 每个列在文件中的开始位置,以fixed64表示

一个column包括:

  • 一个fixed32,表示这个column的的数据块(block)数量
  • 每个数据块的块描述符(block descriptor)
  • 一个或多个数据块

一个block descriptor包括:

  • 一个fixed32,表示块中的行数
  • 一个fixed32,表示编码前的块大小,单位是字节(不包含校验和)
  • 一个fixed32,表示编码后的块大小,单位是字节(不包含校验和)
  • 如果这个列的元数据表明它包含值,列的第一个值,根据这个列的类型进行序列化

一个block包括:

  • 序列化的列值。如果是数组列,则这一序列值之前是它们的int类型的长度。如果指定了编码格式,这些值和长度将以这种格式进行压缩。
  • 校验和,根据文件元数据决定。

编码格式(Codecs)

  • null:“null”表示数据不压缩,直接存储;
  • deflate:表示以RFC 1951中指定的deflate算法编码写入数据。
  • snappy:表示使用Google Snappy压缩库。

校验和算法

  • null:“null”校验和包含0字节。
  • Crc-32:每个crc-32校验和包含四字节的ISO 3309 CRC-32校验和,以块未压缩时的数据进行计算,类型是fixed32。

类型映射

为了表示在不同的序列化系统中,列文件的数据类型是如何定义的,我们定义一套标准的映射关系。在这些系统中,记录被切分为列。当记录被嵌套时,depth-first递归方式可以为每个原型指定一个单独的列。
Avro
Protocol Buffers
Thrift

实现注意事项

可能有些写列文件的技术如下列所示:
1. 使用标准的〜100MB的block,缓冲区的内存最大为block size,然后直接将文件flush到HDFS。单个reduce任务可能会创建多个输出文件。 NameNode的需要的内存与命名数量和块*副本的数量成正比。这会增加一些命名的数量,但不是block的数量,所以这应该还是大大优于一列一个文件的方式。
2. 文件的block size设置为与整个文件一样,spill每列到一个单独的本地临时文件,当文件被关闭时,追加这些文件,然后往HDFS写入一个单独的文件。这样可能会有点慢,并且当本地磁盘满了的时候可能会出问题,但是当处理值很小的列时,这会减少对HDFS的namespace的使用,减少查找次数,从而达到更好的性能。
3. 使用单独的mapreduce job转换row-major文件为column-major。map的输出是一个(row#, column#, value)元组,partitioned by row# 但是sorted by column#和 row#.而reduce可以直接输出列文件。但是这样列文件格式需改为在文件结尾处写入记录数、描述符等信息,而不是在开头。
上面第1条是最简单的实现,大部分实现应该从这个开始。

参考资料

  • CIF Column-Oriented Storage Techniques for MapReduce, Floratou, Patel, Shekita, & Tata, VLDB 2011.
  • DREMEL Dremel: Interactive Analysis of Web-Scale Datasets, Melnik, Gubarev, Long, Romer, Shivakumar, & Tolton, VLDB 2010.
  • 英文原版:Trevni: A Column File Format


    Data Warehouse For Ever原创文章,转载请注明出处