Skip to content

基础结构

B+树

B+树

几个特征

  • 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
  • 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针（卫星数据），且叶子结点本身依关键字的大小自小而大顺序链接。
  • 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

优势

  • 单一节点存储更多的元素，使得查询的IO次数更少；
  • 所有查询都要查找到叶子节点，查询性能稳定；
  • 所有叶子节点形成有序链表，便于范围查询；

LSM 树

LSM树，即日志结构合并树(Log-Structured Merge-Tree)。其实它并不属于一个具体的数据结构，它更多是一种数据结构的设计思想。

大多NoSQL数据库核心思想都是基于LSM来做的，只是具体的实现不同。

LSM树原理把一棵大树拆分成N棵小树，它首先写入内存中，随着小树越来越大，内存中的小树会flush到磁盘中，磁盘中的树定期可以做merge操作，合并成一棵大树，以优化读性能。

LSM树能让我们进行顺序写磁盘，从而大幅提升写操作，作为代价的是牺牲了一些读性能。

LSM 结构和B-Tree结构的比较

传统关系型数据库使用btree或一些变体作为存储结构，能高效进行查找。但保存在磁盘中时它也有一个明显的缺陷，那就是逻辑上相离很近但物理却可能相隔很远，这就可能造成大量的磁盘随机读写。因此，BTree引擎的数据库，磁盘随机查找能力是其性能的瓶颈。

大部分NoSQL数据库，以LSM为存储引擎。通过内存+顺序读写的方式，将DB的瓶颈转换为磁盘顺序写。

选择时可以考虑以下：

  • 在SSD的支撑下BTree能够发挥相当优秀的性能，而对于廉价机械硬盘，LSM可能有更好表现。
  • 考虑磁盘限制，LSM写性能较好，BTree查询性能较好。
  • 如果有频繁的修改，LSM的性能更好；

HBASE 架构分析

Features

  • 强一致性读写，尤其适合高速计数器应用。
  • 通过regions机制自动分片。
  • 自动Failover
  • HBase支持HDFS作为其分布式文件系统。
  • HBase支持块缓存和布隆过滤器，以实现高容量查询优化。

使用场景

  • 亿级别的数据
  • 无需使用typed columns，secondary indexes，事务，高级查询语句

Catalog Table

hbase:meta

hbase:meta 保存了所有regions的位置信息，而hbase:meta的位置保存在Zookeeper中。

hbase:meta 的架构：

  key: [table],[region start key],[region id]

  values:
    - info: regioninfo 序列化的HRegionInfo实例
    - info: server 保存该RegionServer的server:port信息
    - info: serverstartcode 该RegionServer保存该region的开始时间
    - info: splitA/B 当table发生splitting时，会创建这两张，表示该regions的子regionx信息（同regioninfo），单分裂完成后，这两个columns会被删除

RegionServer

当HBase启动时，regions按照以下步骤进行分配：

  • Master创建AssignmentManager实例
  • AssignmentManager通过hbase:meta的判断当前存在的region
  • 如果region 配置合法，那么配置被保留
  • 如果配置不合法，Master启动LoadBalancerFactory实例，重新分配region
  • 更新hbase:meta表，启动RegionServer进程

RegionServer 的 Failover 进程：

  • 当RegionServer关闭时，对应的regions立刻变成不可用
  • Master 发现 RegionServer 故障
  • Master 触发Region 重新分配
  • 正在进行的查询开始重试，并切换到另一个RegionServer运行

Region

hbase:meta的状态保存在ZooKeeper中，而其他Region的状态保存在hbase:meta表中。

Splits

Region的Splits线程在RegionServer中独立运行，Master不参加Splits操作。RegionsServer将父region下线，然后拆分，在hbase:meta中添加子region的信息，并将相关信息汇报给Master。

用户可以定制表的Splits策略:

  • 全局策略：hbase.regionserver.region.split.policy
  • 通过JAVA API 可以表结构中为单个表定制策略

已知拆分策略：

策略 说明
ConstantSizeRegionSplitPolicy 根据公式min(r^2*flushSize，maxFileSize)确定split的maxFileSize，其中r为在线region个数，maxFileSize由hbase.hregion.max.filesize指定。
IncreasingToUpperBoundRegionSplitPolicy ConstantSizeRegionSplitPolicy，仅仅当region大小超过常量值（hbase.hregion.max.filesize大小）时，才进行拆分。
DelimitedKeyPrefixRegionSplitPolicy 保证以分隔符前面的前缀为splitPoint，保证相同RowKey前缀的数据在一个Region中
KeyPrefixRegionSplitPolicy 保证具有相同前缀的row在一个region中（要求设计中前缀具有同样长度）。指定rowkey前缀位数划分region，通过读取table的prefix_split_key_policy.prefix_length属性，该属性为数字类型，表示前缀长度，在进行split时，按此长度对splitPoint进行截取。此种策略比较适合固定前缀的rowkey。当table中没有设置该属性，或其属性不为Integer类型时，指定此策略效果等同与使用IncreasingToUpperBoundRegionSplitPolicy。

手动 Splits

可以在创建Table时进行预拆分，或者使用一段时间后对Table手工拆分。

下面几种情况，出现时用户可以手工进行splits：

  • 存在某个“热点Region”
  • 在群集中RegionServers数量大幅增加之后，快速分散负载。
  • 进行bulk-load之后，region之间可能分区不均衡。

PS： 使用时间作为row key，导致最后一个region过热，其余region全部空闲。因此，HBase中的row key不能设计为时间戳，或者任何递增的字符