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

标签： 未分类 | 发表时间：2012-07-31 09:53 | 作者：yangzhu
出处：http://rdc.taobao.com/team/jm
(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. 
     
  2.     id INT PRIMARY KEY,  
    3. 
     
  3.     name VARCHAR(20),  
    4. 
     
  4.     owner VARCHAR(20),  
    5. 
     
  5.     species VARCHAR(20),  
    6. 
     
  6.     sex CHAR(1)  
    7. 
     
  7. );  
    8. 




   

   
有如下记录:

   

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




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




   

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

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

   

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




   

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




   

   
1. 2 DATA_NODE页格式

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

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

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

   
DATA_NODE页格式

   

    

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




   

   
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的格式如下:

   

    

    
    
     
  1. 名称　　　          字节数                  说明  
    2. 
     
  2. ——————————————————————–  
    3. 
     
  3. keyLength　　         4                     表示Key所占的总字节数  
    4. 
     
  4. valueLength           4                     表示Value所占的总字节数  
    5. 
     
  5.   
    6. 
     
  6. rowKeyLength          2                     表示rowKey所占的字节数  
    7. 
     
  7. rowKey                rowKeyLength          rowKey  
    8. 
     
  8. columnFamilyLength    1                     表示列族名称所占的字节数  
    9. 
     
  9. columnFamily          columnFamilyLength    列族名称  
    10. 
     
  10. columnName            columnNameLength      列名  
    11. 
     
  11. timestamp             8                     时间戳  
    12. 
     
  12. type                  1                     Key类型，比如是新增(Put)，还是删除(Delete)  
    13. 
     
  13.   
    14. 
     
  14. value                 valueLength           列值  
    15. 
     
  15. ——————————————————————–  
    16. 
     
  16.                       表2.1  
    17. 




   
                      表2.1

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

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

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

   

    

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




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

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

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

   

    

    
    
     
  1. <rowKey 列族名称 列名 时间戳, 列值>  
    2. 
     
  2. ====================================================  
    3. 
     
  3. <1001  mycf  name     timestamp, Fluffy>  
    4. 
     
  4. <1001  mycf  owner    timestamp, Harold>  
    5. 
     
  5. <1001  mycf  sex      timestamp, f>  
    6. 
     
  6. <1001  mycf  species  timestamp, cat>  
    7. 
     
  7.   
    8. 
     
  8. <1002  mycf  name     timestamp, Claws>  
    9. 
     
  9. <1002  mycf  owner    timestamp, Gwen>  
    10. 
     
  10. <1002  mycf  sex      timestamp, m>  
    11. 
     
  11. <1002  mycf  species  timestamp, cat>  
    12. 
     
  12.   
    13. 
     
  13. <1003  mycf  name     timestamp, Buffy>  
    14. 
     
  14. <1003  mycf  owner    timestamp, Harold>  
    15. 
     
  15. <1003  mycf  sex      timestamp, f>  
    16. 
     
  16. <1003  mycf  species  timestamp, dog>  
    17. 
     
  17. ====================================================  
    18. 




   

   
与H2的DATA_LEAF相比，

   

    

    
    
     
  1. ====================================================  
    2. 
     
  2. ( /* key:1001 */ 1001, ‘Fluffy’, ‘Harold’, ‘cat’, ‘f’)  
    3. 
     
  3. ( /* key:1002 */ 1002, ‘Claws’, ‘Gwen’, ‘cat’, ‘m’)  
    4. 
     
  4. ( /* key:1003 */ 1003, ‘Buffy’, ‘Harold’, ‘dog’, ‘f’)  
    5. 
     
  5. ======================================================  
    6. 




   
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索引块 ==> 数据块






相关 [h2 hbase 向行] 推荐：
(H2与HBase)面向行or面向列的存储模型?

-  - 淘宝网综合业务平台团队博客

(H2与HBase)面向行or面向列的存储模型.                                 目录  . 1. H2怎么存储pet表的记录?  .     1. 1 DATA_LEAF页格式  .     1. 2 DATA_NODE页格式  . 2. HBase怎么存储pet表的记录?  . 
H2数据库引擎研究导言

-  - 开源软件 - ITeye博客

  有好长一段时间没有写博客了，最近这段时间觉得自己的Java基础不是很扎实，所以又重新捡起《Think in Java》这本来看了. Java高级特性更是接触得少，如网络编程，多线程编程等，所以最近就想开始学习这些内容，已经看了一段时间，以前就有看一些好的开源软件源代码的想法，也陆陆续续看了一些，但都没坚持下来，这次要下定决心好好看一个软件的源代码，数据库的一些高级特性和优化方面也涉及的很少，最近也想好好学习学习，所以由于以上一些想法就产生了研究一个java编写的数据库的想法. 
hbase介绍

- AreYouOK? - 淘宝数据平台与产品部官方博客 tbdata.org

hbase是bigtable的开源山寨版本. 是建立的hdfs之上，提供高可靠性、高性能、列存储、可伸缩、实时读写的数据库系统. 它介于nosql和RDBMS之间，仅能通过主键(row key)和主键的range来检索数据，仅支持单行事务(可通过hive支持来实现多表join等复杂操作). 主要用来存储非结构化和半结构化的松散数据. 
Riak对比HBase

-  - NoSQLFan

文章来自  Riak官方wiki，是一篇Riak与HBase的对比文章. Riak官方的对比通常都做得很中肯，并不刻意偏向自家产品. 对比的Riak版本是1.1.x，HBase是0.94.x. Riak 与 HBase 都是基于 Apache 2.0 licensed 发布. Riak 的实现是基于 Amazon 的 Dynamo 论文，HBase 是基于 Google 的 BigTable. 
[转]HBase简介

-  - 小鸥的博客

   Hbase是一个分布式开源数据库，基于Hadoop分布式文件系统，模仿并提供了基于Google文件系统的Bigtable数据库的所有功能. 其目标是处理非常庞大的表，可以用普通的计算机处理超过10亿行数据，并且有数百万列元素组成的数据表. Hbase可以直接使用本地文件系统或者Hadoop作为数据存储方式，不过为了提高数据可靠性和系统的健壮性，发挥Hbase处理大数据量等功能，需要使用Hadoop作为文件系统. 
HBase表设计

-  - 互联网 - ITeye博客

默认情况下，在创建HBase表的时候会自动创建一个region分区，当导入数据的时候，所有的HBase客户端都向这一个region写数据， 直到这 个region足够大了才进行切分. 一种可以加快批量写入速度的方法是通过预先创建一些空的regions，这样当数据写入HBase时，会按 照 region分区情况，在集群内做数据的负载均衡. 
HBase Memstore配置

-  - 行业应用 - ITeye博客

HBase Memstore配置. 本文为翻译，原英文地址：http://blog.sematext.com/2012/07/16/hbase-memstore-what-you-should-know/.     当regionserver（以下简称RS）收到一个写请求，会将这个请求定位到某个特定的region. 
hbase原理

-  - CSDN博客云计算推荐文章

1.hbase利用hdfs作为其文件存储系统，利用mapreduce来处理数据，利用zookeeper作为协调工具. 2.行键（row key），类似于主键，但row key是表自带的. 3.列族（column family） ,列（也称作标签/修饰符）的集合，定义表的时候指定的，列是在插入记录的时候动态增加的. 
hbase锁机制

-  - 数据库 - ITeye博客

博文说明：1、研究版本hbase0.94.12；2、贴出的源代码可能会有删减，只保留关键的代码.   hbase的锁是采用jdk的ReentrantReadWriteLock类实现.   一、HRegion有两种锁：lock、updatesLock，这两种锁均是ReentrantReadWriteLock类的实例，基本上所有的region操作均需要获取lock的read共享锁，在获取了lock的read锁后，如果是增加或者删除等影响数据内容的操作则还需要获取updatesLock的read锁. 
Hbase入门

-  - CSDN博客云计算推荐文章

Hbase 全称是Hadoop DataBase ，是一种开源的，可伸缩的，高可靠，高性能，面向列的分布式存储系统. 类似于Google的BigTable，其分布式计算采用MapReduce，通过MapReduce完成大块数据加载和全表扫描操作. 文件存储系统是HDFS，通过Zookeeper来完成状态管理协同服务.