最近使用HBase存储数据比较多，看了一些资料，这里记录一下笔记。HBase是Google开源项目bigtable的开源实现，在其基础上加入了更多的功能。本篇博客只是博主自己的学历过程的总结，如有错误还请不吝指出。
HBase简介
从典型的RDMBMS的角度来看，HBase并不是一个列式存储的数据库，但是它利用了磁盘上的列式存储格式，这也是RDBMS和HBase最大的相似之处，因为HBase以列式存储格式在磁盘上存储数据。HBase保存多个版本的数据，按照时间排序，每次都可以取到时间最新的数据版本。
HBase的数据是以列作为最小单位的。多列组成一行，每行都需要指定一个行键作为key，一行的数据作为value。这样就组成了一个完整的key-value的数据结构，我们称这个结构为cell，也就是一个单元格。另外除了通过行键来查找数据之外，HBase还提供给列直接分类的能力，可以根据列的属性指定该列属于哪个列族，一般列族不宜过多。过个cell就组成了表。这些就是我们在使用HBase所需要知道的基本结构。
- 列（column）
- 行（row）
- 行键（row key）
- 单元格（cell）
- 列族（column family）
- 表 （table）
可以看一下如下的逻辑示意图：
稍微解释一下这张图，我们存储了三列数据，分别是data、meta:mimetype、meta:size。我们看到data这列的数据有多个版本，如果我们不指定时间长度的话，那么默认取得就是排序在最前面的数据。
列式存储
列式存储数据库以列为单位聚合数据，然后将列值顺序地存入磁盘，这种存储方法不同于行式存储的传统数据库，行式存储数据库连续地存储整行。图1-1形象地展示了列式存储和行式存储的不同物理结构。列式存储的出现主要基于这样一种假设：对于特定的查询，不是所有的值都是必需的。尤其是在分析型数据库里，这种情形很常见，因此需要选择一种更为合适的存储模式。在这种新型的设计中，减少I/O只是众多主要因素之一，它还有其他的优点：因为列的数据类型天生是相似的，即便逻辑上每一行之间有轻微的不同，但仍旧比按行存储的结构聚集在一起的数据更利于压缩，因为大多数的压缩算法只关注有限的压缩窗口。像增量压缩或前缀压缩这类的专业算法，是基于列存储的类型定制的，因而大幅度提高了压缩比。更好的压缩比有利于在返回结果时降低带宽的消耗。
列式存储.png
关系型数据库(RDBMS)
关系型数据库已经应用非常广泛了，也有比较成熟的解决方案。目前我司的一些业务也已经到了分库分表的阶段了。
数据增长解决方案
读写分离
这种方案保留了一个主数据库服务器，但是这个主数据库服务器现在只服务于写请求，这样做主要是考虑到网站的请求主要由用户浏览产生，因此写请求远少于读请求。
增加缓存
Memcached。现在可以将读操作接入到高速的在内存中缓存数据的系统，但是这种方案没有办法保持数据的一致性，因为用户更新数据到数据库，而数据库并不能主动更新缓存系统中的数据，所以需要尽可能快地同步缓存和数据库视图，把更新缓存数据与更新数据库数据的时间差最小化。
这种方案减少了读的压力，但是写请求压力的增加问题没有得到解决。一旦写性能下降就需要垂直扩容，增加服务器更多的内核，更多的内存...同时，如果采用了读写分离的方案的话，那么就要让从服务器和主服务器一样强，成本也会增加一到两倍。
逆范式
随着业务的增加，以前顺利执行的SQL JOIN会慢慢变慢， 或者干脆无法执行，那么就要使用逆范式化的存储。适当的增加冗余减少join的次数
- 第一范式：如果数据表中的每个字段都是不可再分的最小数据单元，则满足第一范式。
user用户表
| id | username | password |
|---|
role角色表
| id | name |
|---|
- 第二范式：在第一范式的基础上，目标是确保表中的每列都和主键相关。如果一个关系满足第一范式，并且除了主键之外的其他列，都依赖于该主键，则满足第二范式。
user用户表
| id | username | password | role_id |
|---|
role角色表
| id | name |
|---|
- 第三范式：在第二范式的基础上更进一步，目标是确保表中的列都和主键直接相关，而不是间接相关。
user用户表
| id | username | password |
|---|
role角色表
| id | name |
|---|
role用户和角色中间表
| user_id | role_id |
|---|
- 反范式化：反范式化指的是通过增加冗余或重复的数据来提高数据库的读性能。
user用户表, role角色表
| id | username | password | role_id | role_name |
|---|
分库分表
可以根据某个值hash取余的方式，将数据进行分库分表。运维管理起来很复杂，成本很高。
RDBMS问题
不擅长大规模数据处理
RDBMS非常适合事务性操作，但不见长于超大规模的数据分析处理，因为超大规模的查询需要进行大范围的数据记录扫描或全量扫描。分析型数据库可以存储数百或数千TB的数据，在一台服务器上做查询工作的响应时间，会远远超过用户可接受的合理响应时间。垂直扩展服务器性能，即增加CPU核数和磁盘数目，也并不能很好地解决该问题。
等待与死锁
RDBMS的等待和死锁的出现频率，与事务和并发的增加并不是线性关系，准确地说，与并发数目的平方以及事务规模的3次方甚至5次方相关。分区通常是一个不切合实际的解决方案，因为它需要客户端采用非常复杂的方式和较高的代价来维护分区信息。
非关系型数据库Not-Only-SQL(NoSQL)
非关系型数据库和关系型数据库并没有严格的界限， 有些菲关系型数据库也实现了SQL语言的入口， 用于执行一些关系型数据库中常用的复杂查询条件查询。因此从查询方式上并没有严格的区分。实际上两者在底层上是有区别的，尤其是涉及到模式或者ACID事务特性时，因为这与实际的存储架构是相关的。很多这一类的新系统首先做的事情是：抛弃一些限制因素以提升扩展性。
一致性模型
- 严格一致性： 数据的变化是原子的，一经改变即时生效，这是一致性的最高形式。
- 顺序一致性： 每个客户端看到的数据依据他们操作执行的顺序而变化。
- 因果一致性： 客户端以因果顺序观察到数据的变化。
- 最终一致性： 在没有更新数据的一段时间里， 系统将通过广播保证副本之间的数据一致性。
- 弱一致性： 没有做出保证的情况下，所有的更新都会通过广播的形式传递，展现给不同客户端的数据顺序可能不一样。
CAP定理
一个分布式系统只能同时实现一致性、可用性和分区容忍性（或者分区容错性）中的两个。也就是说在较大型的分布式系统中，由于网络分隔，一致性与可用性不能同时满足。这意味着三个要素只能同时实现两个，不可能三者兼具；放宽一致性的要求会提升系统的可用性...提升一致性意味着系统需要牺牲一定的可用性。
存储
Region
HBase中扩展和负载均衡的基本单位称之为Region，region的本质上是以行键排序的连续存储的区间。如果region太大，系统就会把他们动态拆分，相反的，就把多个region合并，以减少存储文件的数量。一开始用户只有一个region，如果数据超过限制之后就会自动拆分成两个大致相等的region。每一个region只能由一台region服务器加载，每一台region服务器可以同时加载多个region。
HFile
数据存储在存储文件中，成为HFile，HFile中的存储的是经过排序的键值映射结构。文件内部由连续的块组成，块的索引信息存储在文件的尾部。当HFile打开并加载到内存中时，索引信息会优先加载到内存中。
更新数据
存储文件保存在Hadoop分布式文件系统中。每次更新数据时，都会将数据记录在 提交日志 （commit log）中，在HBASE中这叫预写日志（write-ahead log. WAL），然后才会将这些数据写入内存中。一旦保存在内存中的数据的累计大小超过了一个给定的最大值，系统就会将这些数据移除内存作为HFile文件刷写到磁盘中。数据移除内存之后，系统会丢弃对应的提交日志，只保留未持久化到磁盘中的提交日志。随着memstore中的数据不断的刷写到磁盘中，会产生很多的HFile文件，HBASE内部会将多个文件合并成一个大的文件。合并有两种类型：minor合并和major压缩合并。
memstore中的数据已经是按照行键排序，持久化到磁盘中的HFile也是按照这个顺序排序的，所以不必执行排序或者其他的特殊操作。
minor合并 将多个小文件重写为数量较少的大文件，减少存储文件的数量，这个过程实际上是个多路归并的过程。因为HFile的每个文件都是经过归类的，所以合并速度很快，只受到磁盘I/O性能的影响。
major合并 将一个region中的一个列族的若干个HFile重写为一个新HFile，与minor合并相比，还有更独特的功能：major合并能扫描所有键值对，顺序重写全部数据，重写数据的过程中会略过做了删除标记的数据。断言删除此时生效。例如，对于那些超过版本限制的数据以及生存时间到期的数据，在重写数据时就不再写入磁盘了。（这也就说说明了在实际使用过程中，如果是刚刚删除数据，然后再scan的时候也是很慢的原因：数据并没有立即删除）
查询数据
每个HFile文件都有一个块索引，通过一个磁盘查找就可以实现查询。首先，在内存的块索引中进行二分查找，确定可能包含给定键的块，然后读取磁盘块找到实际要找的键。读回的数据是两部分数据合并的结果：一部分是memstore中还没有写入磁盘的数据，另一部分是磁盘上的存储文件。
数据检索时用不到WAL，只有服务器内存中的数据在服务器崩溃前没有写入到磁盘，而后进行恢复数据的时候才会用到WAL。
删除数据
以为存储文件是不可被改变的，所以无法通过移除某个键值对来简单的删除。所以是做个删除标记，客户端在检索的时候读不到实际的值。具体删除操作可以参考major合并过程。
客户端API
HBase的主要客户端接口是由org.apache.hadoop.hbase.client中包含的HTable类提供的。所有的修改数据的操作都保证了行级别的 原子性 ，也就是说其他客户端或线程对同一行的读写操作都不会影响这行数据的原子性：要么读到最新的修改，要么等待系统允许写入该行修改。目前还不支持跨行事务和跨表事务。
创建HTable实例是有代价的。 每个实例都要扫描.META.表，以检查该表是否存在、是否可用，此外还要执行一些其他操作，这些检查和操作导致实例调用非常的耗时。因此，需要只创建一次实例，而且每个线程创建一个实例，然后在生命周期复用这个实例。如果需要创建多个实例的话，可以使用 HTablePool 类。
通常情况下，客户端读操作不会受到其他修改数据的客户端的影响，因为他们之间的冲突可以忽略不计，但是，当许多客户端需要同时修改同一行数据的时候就会产生问题。所以，用户应当尽量避免使用批量处理更新来减少单独操作同一行数据的次数。
CURD操作
SCAN操作
过滤器操作
| 比较运算符 | 描述 |
|---|---|
| LESS | 匹配小于设定值的值 |
| LESS_OR_EQUAL | 匹配小于或等于设定值的值 |
| EQUAL | 匹配等于设定值的值 |
| NOT_EQUAL | 匹配与设定值不相等的值 |
| GREATER_OR_EQUAL | 匹配大于或等于设定值的值 |
| GREATER | 匹配大于设定值的值 |
| NO_OP | 排除一切值 |
| 比较器 | 描述 |
|---|---|
| BinaryComparator | 使用Bytes.compareTo()比较当前值与阈值 |
| BinaryPrefixComparator | 与上面的相似，使用Bytes.compareTo()进行行匹配，但是是从左端开始进行前缀匹配 |
| NullComparator | 不做匹配，只判断当前值是不是null |
| BitComparator | 通过BitwiseOp类提供的an位与（AND）、或（OR）、异或（XOR）操作执行位级运算 |
| RegexStringComparator | 根据一个正则表达式，在实例化这个比较器的时候去匹配表中的数据 |
| SubStringComparator | 把阈值和表中数据当做string实例，同时通过contains()操作匹配字符串 |
| 具体比较器 | 描述 |
|---|---|
| RowFilter | 行过滤器基于行键过滤 |
| FamilyFilter | 比较列族返回结果 |
| QualifierFilter | 选择不同的列 |
| ValueFilter | 筛选某个特定的单元格 |
| DependentColumnFilter | 参考列过滤器，允许用户指定一个参考列或者引用列，并使用参考列控制其他列的过滤 |
| 专用过滤器 | 描述 |
|---|---|
| SingleColumnValueFilter | 单列过滤器，用一列的值决定是否一行数据被过滤 |
| SingleColumnValueExcludeFilter | 单列排除过滤器，参考列不被包括到结果中 |
| PrefixFilter | 前缀过滤器，对结果进行分页 |
| PageFilter | 分页过滤器，筛选某个特定的单元格 |
| KeyOnlyFilter | 行键过滤器，只返回KeyValue的键，而不返回实际数据 |
| FirstKeyOnlyFilter | 首次行键过滤器，找到每行中最早创建的列 |
| InclusiveStopFilter | 包含结束的过滤器，将结束行包括到结果中 |
| TimeStampsFilter | 时间戳过滤器，找到与之间戳精确匹配的列版本 |
| ColumnCountGetFilter | 列计数过滤器， 限制每行最多取回多少列 |
| ColumnPaginationFilter | 列分页过滤器，对一行所有的列进行分页 |
| ColumnPrefixFilter | 列前缀过滤器，通过对列名的前缀进行过滤 |
| RandomRowFilter | 随机行过滤器，0.0~1.0 |
架构
如上图所示，HBase是Hadoop生态圈的实时，分布式，高维数据库。有一下特点：
- 高可靠性、高性能、面向列、可伸缩、 实时读写的分布式数据库
- 利用Hadoop HDFS作为其文件存储系统,利用Hadoop MapReduce来处理 HBase中的海量数据,利用Zookeeper作为其分布式协同服务
- 主要用来存储非结构化和半结构化的松散数据（列存NoSQL数据库）
通过这个整体的框架图，我们可以看到，HBase数据库主要由三个部分组成，一部分是Zookeeper作为分布式协调系统，一部分是HBase实现的合并排序部分，还有一部分就是底层的数据存储，可以是HDFS文件系统，也可以是操作系统的文件系统。不过一般会使用HDFS文件系统，HDFS提供了数据冗余的功能，能有效防止数据的丢失。
Region查找过程
结合整体的架构图，我们可以看出来，首先是要查找到对应的region，从图中可以看到，client先请求zookeeper查询到Root表的地址，Root表里面存储的是META表的地址，通过META表能够查询到表和region的对相应关系，就可以定位到表在哪个region上。然后是以下的步骤：
- HBase Client写入数据，存入MemStore，一直到MemStore满 ，Flush成一个StoreFile；
- StoreFile直至增长到一定阈值 ，触发Compact合并操作 ，多个StoreFile合并成一个StoreFile，同时进行版本合并和数据删除，当StoreFiles Compact后，逐步形成越来越大的StoreFile。
- 单个StoreFile大小超过一定阈值后，触发Split操作，把当前Region Split成2个Region，Region会下线，新Split出的2个孩子Region会被HMaster分配到相应的HRegionServer 上，使得原先1个Region的压力得以分流到2个Region上。
- 由此过程可知，HBase只是增加数据，有所得更新和删除操作，都是在Compact阶段做的，所以，用户写操作只需要进入到内存即可立即返回，从而保证I/O高性能。
B+ Tree vs LSM Tree
B+树存储引擎是B+树的持久化实现，不仅支持单条记录的增、删、读、改操作，还支持顺序扫描（B+树的叶子节点之间的指针），对应的存储系统就是关系数据库（Mysql等）。因为随着insert操作，为了维护B+树结构，节点分裂。读磁盘的随机读写概率会变大，性能会逐渐减弱。
LSM树（Log-Structured MergeTree）存储引擎和B+树存储引擎一样，同样支持增、删、读、改、顺序扫描操作。而且通过批量存储技术规避磁盘随机写入问题。
当然凡事有利有弊，LSM树和B+树相比，LSM树牺牲了部分读性能，用来大幅提高写性能。LSM树存储引擎的代表数据库就是Hbase。LSM树核心思想的核心就是放弃部分读能力，换取写入的最大化能力。LSM Tree ，这个概念就是结构化合并树的意思，它的核心思路其实非常简单，就是假定内存足够大，因此不需要每次有数据更新就必须将数据写入到磁盘中，而可以先将最新的数据驻留在内存中，等到积累到足够多之后，再使用归并排序的方式将内存内的数据合并追加到磁盘队尾(因为所有待排序的树都是有序的，可以通过合并排序的方式快速合并到一起)。
日志结构的合并树（LSM-tree）是一种基于硬盘的数据结构，与B+tree相比，能显著地减少硬盘磁盘臂的开销，并能在较长的时间提供对文件的高速插入（删除）。然而LSM-tree在某些情况下，特别是在查询需要快速响应时性能不佳。通常LSM-tree适用于索引插入比检索更频繁的应用系统。
两种优化技术：
- Bloom filter: 就是个带随机概率的bitmap,可以快速的告诉你，某一个小的有序结构里有没有指定的那个数据的。于是就可以不用二分查找，而只需简单的计算几次就能知道数据是否在某个小集合里啦。效率得到了提升，但付出的是空间代价。
- compact:小树合并为大树:因为小树性能有问题，所以要有个进程不断地将小树合并到大树上，这样大部分的老数据查询也可以直接使用log2N的方式找到，不需要再进行(N/m)*log2n的查询了
B+树受限于磁盘的寻到速度，每次查找需要访问磁盘log(N)次，而LSM树利用存储的连续传输能力，并以一定的速率排序和合并文件，需要执行log(updates)次的操作。10 MB/s的传输带宽、10ms的磁盘寻到时间、没条目100字节（100亿条目）、每页10kB（10亿页），更新1%条目所需的时间，随机B-tree更新需要1000天，批量b-tree需要100天，使用排序和合并需要1天
布隆过滤器
布隆过滤器（Bloom Filter）的核心实现是一个超大的位数组和几个哈希函数。假设位数组的长度为m，哈希函数的个数为k
以上图为例，具体的操作流程：假设集合里面有3个元素{x, y, z}，哈希函数的个数为3。首先将位数组进行初始化，将里面每个位都设置位0。对于集合里面的每一个元素，将元素依次通过3个哈希函数进行映射，每次映射都会产生一个哈希值，这个值对应位数组上面的一个点，然后将位数组对应的位置标记为1。查询W元素是否存在集合中的时候，同样的方法将W通过哈希映射到位数组上的3个点。如果3个点的其中有一个点不为1，则可以判断该元素一定不存在集合中。反之，如果3个点都为1，则该元素可能存在集合中。注意：此处不能判断该元素是否一定存在集合中，可能存在一定的误判率。可以从图中可以看到：假设某个元素通过映射对应下标为4，5，6这3个点。虽然这3个点都为1，但是很明显这3个点是不同元素经过哈希得到的位置，因此这种情况说明元素虽然不在集合中，也可能对应的都是1，这是误判率存在的原因。
预写日志
写在内存中的数据在意外情况下很容易丢失。一个比较常见的解决方案就是预写日志，每次更新都会写入日志，只有写入成功才会通知客户端操作成功。类似于MySQL的binarylog，WAL存储了对数据的所有更改。这在主存储器出现意外的情况下非常重要。如果服务器崩溃，它可以有效地回放日志，使得服务器恢复到服务器崩溃以前。这也就意味着如果将记录写入到WAL失败时，整个操作也会被认为是失败的。处理过程如下：首先客户端启动一个操作来修改数据。例如，可以对put()、delete()和increment()进行调用。每一个修改都封装到一个KeyValue对象实例中，并通过RPC调用发送出去。这些调用（理想情况下）成批地发送给含有匹配region的HRegionServer。一旦KeyValue实例到达，它们会被发送到管理相应行的HRegion实例。数据被写入到WAL，然后被放入到实际拥有记录的存储文件的MemStore中。实质上，这就是HBase大体的写路径。如果服务终端，重启region的时候就会检查没有flush到磁盘的数据。
