内存：（
保证有序
）平衡二叉树，红黑树，跳跃表 （
考虑并发
）选择了
跳跃表
。来维护一个有序的KeyValue集合。ConcurrSkipListMap
磁盘：布隆过滤器 + 多个内部k-v有序的文件组成。
1.1跳跃表
跳跃表是一种能高效实现，
插入，删除，查找的内存的数据结构，复杂度是O(logN),
相比红黑树，跳跃表的优势在于，
并发场景下锁粒度更小
。广泛用于KV数据库。
1.1多路归并
如何将K个内部有序的文件排序，合并成一个大的有序文件，这总排序算法叫做多路归并。（Compaction）
1.3LSM树
LSM树本质上和B+树一样，是一种磁盘数据的索引结构，相比B+树，LSM树的索引对写入请求更友好。
无论任何写入请求，LSM树都会将写入操作处理为一次顺序写
，而HDFS擅长的就是顺序写。
key-value排序 key按字典排序，相同的key，按timestamp排序，timestamp越大，越靠前，因为用户期望优先读取到版本号更新的数据。
一般来说，LSM中存储的是多个KeyValue组成的集合，每个KeyValue一般都用一个字节数组来表示。Hbase中该字节数组主要分为以下几个字段，其中Rowkey、Family、Qualifier、Timestamp、Type这5个字段组成KeyValue中的key部分。其中type字段表示这个KeyValue操作的类型，HBase内有Put、Delete、Delete Column、Delete Family等等。注意，这是一个非常关键的字段，
表明了LSM树内存储的不只是数据，而是每一次操作记录。
Value直接存储的是值的二进制内容。
本质上LSM树中存放的并非数据本身，而是操作记录，这对应了LSM树（Log-Structured Merge-Tree）
中Log的含义，即操作日志。
在整个过程中，LSM树全部使用append（磁盘顺序写），没有使用任何随机写，因此LSM树是一种对写入极为友好的索引结构。
随着写入的增加，内存数据会不断刷新到磁盘上。一旦用户有读取请求，则需要将大量的磁盘文件进行多路归并，之后才能读取到所需的数据。因为需要将key相同的数据综合起来，最终选出合适的版本返回给用户。
为了优化读取操作，可以设置一定的策略将多个HFile进行多路归并，合并为一个文件。
minor compact 选少数几个hfile，局部的compact，适合较高频率的跑，对于删除操作，无法在合并中删除。
major compact能完全清理delete操作
1.4 布隆过滤器
有一个长度为N的01数组组成，初始值为0，对集合中每个元素w，做k次哈希，第i次哈希值对N取模得到一个index(i), 将array数组中的array[index(i)]置为1。有一定的误判率。
w元素可能存在于集合A中。
w肯定不在集合A中。
1.4.1Hbase与布隆过滤器
Hbase就是通过布隆过滤器来过滤大量无效的数据块，从而节省磁盘io。
NONE：关闭布隆过滤器
ROW：按照rowkey来计算布隆过滤器，因为在get时，必须需要携带rowkey，所以这个时默认类型。
ROWCOL：按照rowkey+family+qualifier这3个字段来计算布隆过滤器。
二、HBase客户端
2.1 定位Meta表
HBas
e一张表的数据是由多个Region构成
，而
这些Region是分布在整个集群的RegionServer上
的。那么客户端在做任何数据操作时，都要先确定数据在哪个Region上，然后再根据Region的RegionServer信息，去对应的RegionServer上读取数据。而hbase:meta表就是专门用来存放整个集群所有的region信息。
Hbase保证hbase:meta 表始终只有一个region。这是为了确保meta表多次操作的原子性。Hbase只保证Region级别的事务。
hbase:meta的一个rowkey对应一个region。
因为hbase:meta是把startRow放在了rowkey上，而不是stopRow。如果某个Region对应的区间是[bbb, ccc)，为了定位rowkey=bc的Region， 通过正向Scan只会找到[bbb, ccc) 这个区间的下个区间，即使我们找到了[bbb, ccc) 下个区间，也没法快速找到[bbb, ccc) 这个Region信息，所以采用Reversed Scan比较合理。
2.2 防止hbase:meta的表成为热点region
hbase:meta表只有一个region，所有请求都会访问hbase:meta去找region，然后再去需要查找region所在的regionServer，这个region会成为热点region。
Hbase客户端有一个叫做MetaCache的缓存，客户端会先去MetaCache中找业务region所在的Region。
Region为空
，说明该客户端没有任何缓存，1.先要读取zookeeper中的/hbase/meta-region-server这个ZNode，确定hbase:meta表所在的regionServer，在hbase:meta表中找到业务rowkey所在的region，然后缓存在MetaCache中，一般发生在服务第一次建立后少数几个请求。
Region信息不为空
，但是通过调用RPC请求对应的RegionServer发现region不在该RegionServer上，说明信息过期，需要重新请求。发生在RS宕机，region迁移，平衡，概率较小。
Region信息不为空，请求成功
。
2.3 scan
通过table.getScanner(scan)可以拿到一个scanner，然后不断执行scanner.next()能够拿到下一个Result。
用户每次执行scanner.next()都会从cache队列中拿result。如果cache为空，那么就会发起一次RPC向服务端请求当前scanner的后续，需要将result内的cell数据进行重组，最终组成用户需要的result放入到cache中。
为什么需要在步骤3对RPC response中的result进行重组呢？这是因为RegionServer为了避免被当前RPC请求耗尽资源，实现了多个维度的资源限制（例如timeout、单次RPC响应最大字节数等），一旦某个维度资源达到阈值，就马上把当前拿到的cell返回给客户端。这样客户端拿到的result可能就不是一行完整的数据，因此在步骤3需要对result进行重组。
2.5 Hbase写数据
table.put(put) 最常见的
单行写入
数据。能保证put操作的原子性。
table.put(List<Put> puts)
批量写入
的接口，Hbase并不支持跨region的多行事务，这些put中，可能有一部分成功，一部分失败，失败的put操作会进行若干次重试。
bulk load 通过Hbase提供的工具直接将数据生成HFile，没有任何RPC调用，
完全离线的快速写入方式
。
bulk load常见场景：
1. 集群数据的拷贝。
2. 用户在写入大量数据后，发现选择的split keys不合适，想重新选择split keys建表，也可以通过snapshot生成HFile再bulk load生成新表。
2.6 常见错误
待访问的region所在的RS宕机，由于客户端存中缓存，首次访问还是旧的RS，后续重试发起RPC
单次RPC请求失败，后续继续重试
访问hbase:meta或者zookeeper失败，可能是zookeeper和客户端连接超时，连接数过多
业务请求延迟很高，服务端延迟正常。一般是hbase客户端可能存在GC问题
Batch数据量太大，会将对应的Block从HDFS中读取到Hbase内存中，一起量太大，会导致Hbase 的full GC。
