(H2与HBase)面向行or面向列的存储模型?-低调大师

(H2与HBase)面向行or面向列的存储模型?

2017-05-01 624

(H2与HBase)面向行or面向列的存储模型?

1. 目录
2. 0. 示例
3.
4. 1. H2怎么存储pet表的记录?
5. 1. 1 DATA_LEAF页格式
6. 1. 2 DATA_NODE页格式
7.
8. 2. HBase怎么存储pet表的记录?
9. 2. 1 Data Block格式
10. 2. 2 Data Block如何存下面这些记录?
11. 2. 3 leaf索引块的格式:
12. 2. 4 root索引块的格式:
13. 2. 5 IntermediateLevel索引块

## 0. 示例

假设有如下一张pet表 (改编自MySQL参考手册)

1. CREATE TABLE pet (
2. id INT PRIMARY KEY,
3. name VARCHAR(20),
4. owner VARCHAR(20),
5. species VARCHAR(20),
6. sex CHAR(1)
7. );

有如下记录:

1. id name owner species sex
2. ===============================
3. 1001 Fluffy Harold cat f
4. 1002 Claws Gwen cat m
5. 1003 Buffy Harold dog f

1. H2怎么存储pet表的记录?H2是一个Java SQL Database Engine，使用面向行(row-oriented)的存储模型(如果觉得拗口，就叫基于行(row-based)的存储模型吧)。

表元数据与表的记录分开，可以通过与INFORMATION_SCHEMA相关的系统表来查找元数据，

还可以通过JDBC的java.sql.DatabaseMetaData提供的相关API来查找。

H2内部的存储引擎使用页(Page)来组织数据，页的大小默认是2K，可通过参数PAGE_SIZE调整，

有8种不同的页：

DATA_LEAF

DATA_NODE

DATA_OVERFLOW

BTREE_LEAF

BTREE_NODE

FREE_LIST

STREAM_TRUNK

STREAM_DATA

本文只是说明H2怎么按行的方式来组织数据，所以只重点讲DATA_LEAF、DATA_NODE这两种页。

### 1. 1 DATA_LEAF页格式

1. 项占用字节数
2. ======================================================
3. type 1
4. checksum 2 (程序代码中一般是先用0值占位，等写完一页后对此页的数据计算校验和再回填)
5. parentPageId 4 (就是父DATA_NODE节点的ID)
6. tableId 可变int (该页所属的表的ID)
7. columnCount 可变int (该页所属的表有多少列)
8. entryCount 2 (该页有多少条记录)
9.
10. entryCount个
11. {
12. key 可变long (如果表存在主键，并且是BYTE、SHORT、INT、LONG类型，这个key就是主键的值，否则为每行生成一个唯一的数值)
13. offset 2 (该行在此页中的相对位置)
14. }
15.
16. entryCount个
17. {
18. columnValues 每一行记录从对应的offset位置开始存放，不同类型的字段会使用1个Byte来标识自己的格式
19. }
20. ======================================================

DATA_LEAF页并不存放表名、列名、列类型这些元数据

对于pet表中的三行记录放到一个DATA_LEAF页中会是这样(为了方便阅读未细化每一个字节，实际更复杂一些):

1. id name owner species sex
2. ===============================
3. 1001 Fluffy Harold cat f
4. 1002 Claws Gwen cat m
5. 1003 Buffy Harold dog f

1. 项值
2. ======================================================
3. type 17 (Page.TYPE_DATA_LEAF | Page.FLAG_LAST(当前只有一个页))
4. checksum 0x75CE (校验和计算比较复杂，也受当前pageId、pageType、pageSize影响)
5. parentPageId 0 (就是父DATA_NODE节点的ID，0说明是root节点)
6. tableId 14 (该页所属的表的ID)
7. columnCount 5 (该页所属的表有多少列)
8. entryCount 3 (该页有多少条记录)
9.
10. {
11. 1001, 2024, 1002, 2003, 1003, 1980 (其中1001、1002、1003是key，2024、2003、1980是offset)
12. }
13. {
14. ( / key:1001 / 1001, ‘Fluffy’, ‘Harold’, ‘cat’, ‘f’)
15. ( / key:1002 / 1002, ‘Claws’, ‘Gwen’, ‘cat’, ‘m’)
16. ( / key:1003 / 1003, ‘Buffy’, ‘Harold’, ‘dog’, ‘f’)
17. }
18. ======================================================

### 1. 2 DATA_NODE页格式

当某个DATA_LEAF页(page0)的大小超过pageSize时，会把它切掉一部分，得到一个新的DATA_LEAF页(page1)，

page0从切割点开始往右的keys和记录被转到page1中，切割点左边的继续留在page0，

同时生成一个新的DATA_NODE页作为page0、page1的父节点。

DATA_NODE页格式

项占用字节数
======================================================
type 1
checksum 2 (程序代码中一般是先用0值占位，等写完一页后对些页的数据计算校验和再回填)
parentPageId 4 (就是父DATA_NODE节点的ID)
tableId 可变int (该页所属的表的ID)
rowCountStored 4
entryCount 2
entryCount个
{
childPageId 4
key 可变long
}
======================================================

2. HBase怎么存储pet表的记录?

HBase使用面向列(column-oriented)的存储模型，不需要定义表的结构(schema-free),

可以随时动态添加新的列，理论上对于列的个数没有限制，

如果列很多，可以把相关的一组列归属到一个列族中(Column Family)，充分发挥数据的聚合特性。

通过RowKey能把同一个或多个列族中的列关联起来，

HBase的RowKey和列族的组合有点类似于传统关系数据库中有外键引用关系的两个关联表，

但是只是型像神不想，HBase中两个不同列族是平等的，没有主从关系，只是通过RowKey把两者关联起来。

HBase的Data Block对应H2的DATA_LEAF，

HBase的Leaf Index Block对应H2的DATA_NODE，

2. 1 Data Block格式

Data Block的格式有点复杂，如果不打算看代码可以不用关心的

每个block有一个33字节的头

===========================

前8个字节是表示block类型的MAGIC，对应org.apache.hadoop.hbase.io.hfile.BlockType的那些枚举常量名，

接着4个字节表示onDiskBytesWithHeader.length - HEADER_SIZE

接着4个字节表示uncompressedSizeWithoutHeader

接着8个字节表示prevOffset (前一个块的offset，比如，对于第一个块，那么它看到的prevOffset是-1，对于第二个块，是0)

接着1个字节表示checksumType code(默认是1: org.apache.hadoop.hbase.util.ChecksumType.CRC32)

接着4个字节表示bytesPerChecksum(默认16k，不能小于block头长度(头长度是33个字节))

最后4个字节表示onDiskDataSizeWithHeader

当不使用压缩时onDiskBytesWithHeader不包含checksums,

此时checksums放在onDiskChecksum中，

当使用压缩时checksums放在onDiskBytesWithHeader

checksums就是把onDiskBytesWithHeader中的所有字节以bytesPerChecksum个字节为单位求校验和，这个校验和用int(4字节)表示。

注意，在求校验和时，onDiskBytesWithHeader中还没有checksums

默认每个Data Block的大小是64K(头(33字节)不包含在内)(可以通过HColumnDescriptor.setBlocksize设置)，

64K只是一个阀值，实际的块大小要比它大(取决于最后存入的KeyValue的大小)，

比如上次存入的KeyValue导致块大小变成63K了，但是还没到64K，那么接着存入下一个KeyValue，如果此KeyValue有5K，

那么这个块的大小就变成了63+5=68K了。

=================================================================================

从这开始是重点:

Data Block的核心是一串KeyValue，

KeyValue的格式如下:

名称　　　字节数说明
——————————————————————–
keyLength　　 4 表示Key所占的总字节数
valueLength 4 表示Value所占的总字节数
rowKeyLength 2 表示rowKey所占的字节数
rowKey rowKeyLength rowKey
columnFamilyLength 1 表示列族名称所占的字节数
columnFamily columnFamilyLength 列族名称
columnName columnNameLength 列名
timestamp 8 时间戳
type 1 Key类型，比如是新增(Put)，还是删除(Delete)
value valueLength 列值
——————————————————————–
表2.1

关于KeyValue更完整更详细的内容请看这里:

HBase HFile与Prefix Compression内部实现全解–KeyValue格式

2. 2 Data Block如何存下面这些记录?

id name owner species sex
===============================
1001 Fluffy Harold cat f
1002 Claws Gwen cat m
1003 Buffy Harold dog f

把id作为rowkey，其他列不动，另外HBase至少需要一个列族，假设列族名是”mycf”，这三行记录会产生4*3=12个KeyValue，

存到Data Block会是这样，先按rowkey升序，rowkey相同的按列名升序排，

最后的布局类似这样(为了简化去掉了一些细节):

<rowKey 列族名称列名时间戳, 列值>
====================================================
<1001 mycf name timestamp, Fluffy>
<1001 mycf owner timestamp, Harold>
<1001 mycf sex timestamp, f>
<1001 mycf species timestamp, cat>
<1002 mycf name timestamp, Claws>
<1002 mycf owner timestamp, Gwen>
<1002 mycf sex timestamp, m>
<1002 mycf species timestamp, cat>
<1003 mycf name timestamp, Buffy>
<1003 mycf owner timestamp, Harold>
<1003 mycf sex timestamp, f>
<1003 mycf species timestamp, dog>
====================================================

与H2的DATA_LEAF相比，

====================================================

( / key:1001 / 1001, ‘Fluffy’, ‘Harold’, ‘cat’, ‘f’) ( / key:1002 / 1002, ‘Claws’, ‘Gwen’, ‘cat’, ‘m’) ( / key:1003 / 1003, ‘Buffy’, ‘Harold’, ‘dog’, ‘f’) ======================================================

HBase的格式存在大量的冗余(比如rowKey、列族名称、列名、时间戳)之所以要这样做是为了水平扩展、文件合并切分更容易，

因为HBase把列名、列族名称这些元数据和列值合在一起了，所以在分区时只须简单按rowkey切分，

就能把所有数据都转移到另一台机器上，不需要像H2那样要考虑INFORMATION_SCHEMA中的元数据与表记录是否同步的问题。

HBase基于LSM-Tree来存放KeyValue，H2基于类B+Tree的结构，

LSM-Tree只允许一次性添加，不需要考虑结点的删除修改，

数据会先写到内存(MemStore)，然后内存满了就flush到硬盘变成一棵小LSM-Tree，

多棵LSM-Tree会定期合并成一棵更大的LSM-Tree，大到一定程度再切分自动扩散到其他机器。

B+Tree对于行、列的添加、删除需要对结点进行调整，数据更新会出现overflow。

另外，观察上面两组数据，H2的方案只是把元数据抽出来放到别处了，然后通过表id把DATA_LEAF和元数据关联，

HBase 0.94可以使用前缀压缩的办法，把重复的东西提取出来，

如果把上面的两组数据分别串成一行，其实差别不大，只是HBase多了很多冗余信息而已，

把冗余信息清除一部份我看不出row-oriented和column-oriented有什么本质区别，至少HBase与H2是有点相似的。

反而差异最大的是:

1) LSM-Tree与B+Tree

2) 是否是schema-free的

(以下内容不重要)

2. 3 leaf索引块的格式:

数据块总个数N(int类型,4字节)

N个”数据块在此索引块中的相对位置”(从0开始，根据每个Entry的大小累加，每个相对位置是int类型,4字节)

N个Entry的总字节数(int类型,4字节)

N个Entry {

数据块在文件中的相对位置(long类型,8字节)

数据块的总长度(包括头) (int类型,4字节)

数据块第一个KeyValue中的Key字节数组

}

2. 4 root索引块的格式:

N个leaf索引块Entry {

leaf索引块在文件中的相对位置(long类型,8字节)

leaf索引块的总长度(包括头) (int类型,4字节)

leaf索引块第一个Entry的Key字节数组

}

2. 5 IntermediateLevel索引块

与leaf索引块类似，只不过它的Entry在第一层IntermediateLevel是leaf索引块Entry，

第二层以后是 IntermediateLevel块的entry。

查找key的顺序

root索引块 ==> IntermediateLevel索引块 ==> leaf索引块 ==> 数据块

本文来源于"阿里中间件团队播客",原文发表时间" 2012-07-31"

微信关注我们

原文链接：https://yq.aliyun.com/articles/85575

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

分布式深度学习算法产品及在蚂蚁金服中的应用（附33页PDF下载）

导读：8月3日-6日，世界公认的“必须参加”的数据盛典Strata + Hadoop World首次登陆中国。作为顶级的数据盛会，美国总统奥巴马曾亲自2015年加州的Strata + Hadoop World大会助阵送去贺词。会议议题关注于大数据、机器学习和数据分析以及它们社会带来的改变。数据科学家、分析师和来自各种规模的创新企业高管将在此汇聚一堂，分享数据案例研究、最佳实践、新的分析方法以及关键技能。让我们来看看在北京的Strata + Hadoop World大会有什么亮点：阿里云iDST褚崴讲《分布式深度学习算法产品及其在蚂蚁金服业务中的应用》近年来深度学习技术迅猛发展，在图像识别，语音交互，机器翻译等领域展现出了巨大的潜力。依托阿里云自主研发的分布式数据存储与计算服务ODPS，我们研发了机器学习平台产品PAI (platf

2017-05-01

706

《大数据架构和算法实现之路：电商系统的技术实战》——1.5　相关软件：R和Mahout

本节书摘来自华章计算机《大数据架构和算法实现之路：电商系统的技术实战》一书中的第1章，第1.5节，作者黄申，更多章节内容可以访问云栖社区“华章计算机”公众号查看。 1.5　相关软件：R和Mahout 了解了机器学习和分类的基本知识之后，你会发现相关算法本身的实现也是需要大量的专业知识的，开发的门槛也比较高。如果一切从头开始，整个流程将包括构建算法模型、计算离线评估的指标、打造在线实时服务等内容，完成所有这些我们才有可能满足业务的需求，如此之长的战线，对于竞争激烈的电商而言是无法接受的。那么有没有现成的软件可以帮助我们完成这个艰巨的任务呢？答案是肯定的。这里将介绍两个常见的机器学习软件工具：R和Mahout。 1.5.1　R简介 R（https://www.r-project.org/ ）提供了一套基于脚本语言的解决方案，协助没有足够计

2017-05-01

649

发表评论

资源下载

更多资源

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能，例如代码缩略图，Python的插件，代码段等。还可自定义键绑定，菜单和工具栏。Sublime Text 的主要功能包括：拼写检查，书签，完整的 Python API ， Goto 功能，即时项目切换，多选择，多窗口等等。Sublime Text 是一个跨平台的编辑器，同时支持Windows、Linux、Mac OS X等操作系统。

WebStorm

WebStorm 是jetbrains公司旗下一款JavaScript 开发工具。目前已经被广大中国JS开发者誉为“Web前端开发神器”、“最强大的HTML5编辑器”、“最智能的JavaScript IDE”等。与IntelliJ IDEA同源，继承了IntelliJ IDEA强大的JS部分的功能。

(H2与HBase)面向行or面向列的存储模型?