每个程序员都应该了解的延迟时间

L1 cache reference
L1 cache读取
0.5ns
Branch mispredict
分支误预测
5ns
L2 cache reference
L2 cache读取
7ns 14x L1 cache
Mutex lock/unlock
互斥锁
25ns
Main memory reference
主内存读取
100ns 20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy
压缩1KB数据
3,000ns
Send 1K bytes over 1 Gbps network
在1Gbps网络上发送2K数据
10,000ns 0.01ms
Read 4K randomly from SSD*
从SSD硬盘随机读取4K数据*
150,000ns 0.15ms
Read 1 MB sequentially from memory
从内存连续读取1MB数据
250,000ns 0.25ms
Round trip within same datacenter
同一数据中心的往返时间(RTT)
500,000ns 0.5ms
Read 1 MB sequentially from SSD*
从SSD硬盘顺序读取1MB数据*
1,000,000ns 1ms 4x memory
Disk seek
磁盘寻道时间
10,000,000ns 10ms 20x datacenter roundtrip
Read 1 MB sequentially from Network
从网络上顺序读取1M数据
10,000,000ns 10ms
Read 1 MB sequentially from disk
从磁盘上顺序读取1M数据
20,000,000ns 20ms 80x memory, 20x SSD
Send packet CA->Netherlands->CA
发送一个包从从加州->荷兰->加州
150,000,000ns 150ms

 

* Assuming ~1GB/sec SSD

注:原文来自https://gist.github.com/jboner/2841832,略有修改

 


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

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原创文章,转载请注明出处

    关于hive中not like的语法错误

    hive的低版本中不支持not like的语法,在执行类似如下语句时会报错

    create table ljp as
    select gmt_created, first_user_name, servicer_name
    from bds_c04_s_ocs_sessions
    where first_user_name not like ‘游客%’;

    错误信息如下:

    FAILED: Parse Error: line 16:4 cannot recognize input near ‘first_user_name’ ‘not’ ‘like’ in expression specification

    解决方案有两种:
    一、修改语句,将not放在表达式前面,即改为这样:not (a like ‘B%’)
    二、或升级hive版本,如在hive 1.1.7版本中,即可兼容not like语法。其他如not in等语句,也类似。详见社区的issue:https://issues.apache.org/jira/browse/HIVE-1740

    END


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

    ImportError: No module named bz2的解决方案

    make时出现类似错误:ImportError: No module named bz2
    多半是由于python的版本问题,新安装的python版本与系统自带的版本路径冲突,导致代码在import bz2模块时找不到路径。
    在GOOGLE后,本人认为最好的解决方案是通过临时改变PATH路径的方式解决:
    export PATH=/usr/bin:$PATH
    make


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

    Oracle中关于星期(IW和WW)的算法

    Oracle中对于星期的计算规则中,其中关于计算本周是一年的第几周,有两种格式,IW和WW,其中的区别官方文档解释如下:

  • IW:基于 ISO标准计算出来的该年的第几周(1-52 or 1-53) 。
  • WW:该年的第几周(1-53),其中第1周指该年的第1天至第7天。
  • 从文档中可以看出,WW的算法是: int(dayOfYear+6)/7,个人觉得这种算法有点“2”。相信一般情况下,我们不会使用WW的吧,应该IW使用的比较多。
    关于Oracle提到的这个星期的计算ISO标准,是这样的:

  • 每个星期总是从周一开始,周日结束。
  • 如果1月1日是周五、周六或周日,则这一周算为上一年的最后一周,因为这周的大部分时间属于上一年。
  • 如果1月1日是周一、周二、周三或周四,则这一周算为新年的第一周,因为这周的大部分时间属于新的一年。
  • 下面这两张表格,是从Oracle官方文档中截取出来的:

    Table 3-7 First ISO Week of the Year: Example 1, January 1998

    Mo Tu We Th Fr Sa Su ISO Week
    - - - 1 2 3 4 First ISO week of 1998
    5 6 7 8 9 10 11 Second ISO week of 1998
    12 13 14 15 16 17 18 Third ISO week of 1998
    19 20 21 22 23 24 25 Fourth ISO week of 1998
    26 27 28 29 30 31 - Fifth ISO week of 1998

    Table 3-8 First ISO Week of the Year: Example 2, January 1999

    Mo Tu We Th Fr Sa Su ISO Week
    - - - - 1 2 3 Fifty-third ISO week of 1998
    4 5 6 7 8 9 10 First ISO week of 1999
    11 12 13 14 15 16 17 Second ISO week of 1999
    18 19 20 21 22 23 24 Third ISO week of 1999
    25 26 27 28 29 30 31 Fourth ISO week of 1999

    从表中可以看出,按照ISO标准算法,同样是1月1日,1998年是算第一周,而1999年的1月1日却算为上一年的最后一周。

    这里需要注意的是,ISO标准中星期的第一天是周一,而Oracle中其他一些日期处理算法中(如D),默认每周的第一天是周日。因为第一天是周日还是周一,由参数NLS_TERRITORY决定,而该参数的默认值是从NLS_LANG继承过来的,NLS_LANG默认值为AMERICA,因此默认周日是每周的第一天)。
    我们很多人认为中国人每周第一天从周一开始,其实不是这样哦,从Oracle上可以看出来,其实我国的每周第一天仍然是周日,与美国一致,只有德国、法国等一些欧洲国家是从周一开始的:

    SQL> select to_char(sysdate,’yyyymmdd’) from dual;

    TO_CHAR(
    ——–
    20110901

    SQL> ALTER SESSION SET NLS_TERRITORY=AMERICA;

    Session altered.

    SQL> select to_char(sysdate,’d') from dual;

    T
    -
    5

    SQL> ALTER SESSION SET NLS_TERRITORY=China;

    Session altered.

    SQL> select to_char(sysdate,’d') from dual;

    T
    -
    5

    SQL> ALTER SESSION SET NLS_TERRITORY=GERMANY;

    Session altered.

    SQL> select to_char(sysdate,’d') from dual;

    T
    -
    4


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