5 关键算法/流程
5.1 region定位
HBase如何找到某个row key （或者某个row key的range）所在的region？使用三层类似B+树的结构来保存region位置：
第一层：Zookeeper保存了-ROOT-表的位置。
第二层：-ROOT- 表保存了.META.表所有region的位置，通过-ROOT-表，可以访问.META.表的数据。
第三层：.META.是一个特殊的表，保存了HBase中所有数据表的region位置信息。
需要注意的是：
- -ROOT-表永远不会被split，保证了最需要三次跳转，就能定位到任意region
- META.表每行保存一个region的位置信息，row key采用表名+表的最后一行编码而成
- 为了加快访问，.META.表的全部region都保存在内存中
- Client会将查询过的位置信息保存缓存起来，缓存不会主动失效
5.2 region分配
任何时刻，一个region只能分配给一个HRegionServer。HMaster记录了当前有哪些可用的HRegionServer。以及当前哪些region分配给了哪些HRegionServer，哪些region还没有分配。当存在未分配的region，并且有一个HRegionServer上有可用空间时，HMaster就给这个HRegionServer发送一个装载请求，把region分配给这个HRegionServer。HRegionServer得到请求后，就开始对此region提供服务。
5.3 写请求处理
数据在更新时首先写入Log（WAL log）和内存（MemStore）中，MemStore中的数据是排序的，当MemStore累计到一定阈值时，就会创建一个新的MemStore，并且将老的MemStore添加到flush队列，由单独的线程flush到磁盘上，成为一个StoreFile。与此同时，系统会在Zookeeper中记录一个redo point，表示这个时刻之前的变更已经持久化了。
当系统出现意外时，可能导致内存（MemStore）中的数据丢失，此时使用Log（WAL log）来恢复checkpoint之后的数据。
前面提到过StoreFile是只读的，一旦创建后就不可以再修改。因此HBase的更新其实是不断追加的操作，所有的更新和删除操作都是在后续的compact过程中进行的，这使得用户的写操作只要 进入内存中就可以立即返回，保证了HBase I/O的高性能。
5.4 读请求处理
由于对表的更新是不断追加的，处理读请求时，需要访问Store中全部的StoreFile和MemStore，将他们的按照row key进行合并，由于StoreFile和MemStore都是经过排序的，并且StoreFile带有内存中索引，合并的过程还是比较快。
5.5 Compact/Split
在HStore中，当StoreFile文件数量增长到一定阈值，会触发compact合并操作，将多个StoreFiles合并成一个StoreFile，合并过程中会进 行版本合并和数据删除。当StoreFiles被compact后，会逐步形成越来越大的StoreFile，当单个StoreFile大小超过一定阈值后，会触发split操作，同时把当前region split成2个region，父region会下线，新split出的2个孩子region会被HMaster分配到相应的HRegionServer 上，使得原先1个region的压力得以分流到2个region上。
下图描述了compaction和split的过程：
注意：split操作过程完成的非常快，因为原始的数据文件并不会被改变，系统只是简单的创建两个Reference文件指向原始的数据文件，每个Reference文件管理原始文件一半的数据。Reference文件名字是一个ID，它使用被参考的region的名字的hash作为前缀，例如：1278437856009925445.3323223323。Reference文件只含有非常少量的信息，这些信息包括被分割的原始region的key以及这个文件管理前半段还是后半段。只有当系统做compaction的时候原始数据文件才会被分割成两个独立的文件并放到相应的region目录下面，同时原始数据文件和那些Reference文件也会被清除。
5.6 HRegionServer Failover
HStore在系统正常工作的前提下是没有问题的，但是在分布式系统环境中，无法避免系统出错或者宕机，因此一旦HRegionServer意外退出，MemStore中的内存数据将会丢失，这就需要引入HLog了。每个HRegionServer中都有一个HLog对象，HLog是一个实现Write Ahead Log的类，在每次用户操作写入MemStore的同时，也会写一份数据到HLog文件中（HLog文件格式见后续），HLog文件定期会滚动出新的，并删除旧的文件（已持久化到StoreFile中的数据）。当HRegionServer意外终止后，HMaster会通过Zookeeper感知到，HMaster首先会处理遗留的 HLog文件，将其中不同Region的Log数据进行拆分，分别放到相应region的目录下，然后再将失效的region重新分配，领取到这些region的HRegionServer在Load Region的过程中，会发现有历史HLog需要处理，因此会Replay HLog中的数据到MemStore中，然后flush到StoreFiles，完成数据恢复。
5.7 HRegionServer上线和下线
HMaster使用Zookeeper来跟踪HRegionServer状态。当某个HRegionServer启动时，会首先在Zookeeper上的server目录下建立代表自己的文件，并获得该文件的独占锁。由于HMaster订阅了server目录上的变更消息，当server目录下的文件出现新增或删除操作时，HMaster可以得到来自Zookeeper的实时通知。因此一旦HRegionServer上线，HMaster能马上得到消息。
当HRegionServer下线时，它和Zookeeper的会话断开，Zookeeper自动释放代表这台server的文件上的独占锁。而HMaster不断轮询server目录下文件的锁状态，如果发现某个HRegionServer丢失了它自己的独占锁（或者HMaster连续几次和HRegionServer通信都无法成功），HMaster就会去尝试获取代表这个HRegionServer的读写锁，一旦获取成功，就可以确定：
可能性一：HRegionServer和Zookeeper之间的网络断开了;
可能性二：HRegionServer挂了;
的其中一种情况发生了，无论哪种情况，HRegionServer都无法继续为它的region提供服务了，此时HMaster会删除server目录下代表这台HRegionServer的文件，并将这台HRegionServer的region分配给其它还活着的同志。
如果网络短暂出现问题导致HRegionServer丢失了它的锁，那么HRegionServer重新连接到Zookeeper之后，只要代表它的文件还在，它就会不断尝试获取这个文件上的锁，一旦获取到了，就可以继续提供服务。
5.8 HMaster上线和下线
HMaster启动会依次进行以下步骤:
1. 从Zookeeper上获取唯一一个master的锁，用来阻止其它HMaster成为工作HMaster。
2. 扫描Zookeeper上的server目录，获得当前可用的HRegionServer列表。
3. 和2中的每个HRegionServer通信，获得当前已分配的region和HRegionServer的对应关系。
4. 扫描.META.中region的集合，计算得到当前还未分配的region，将他们放入待分配region列表。
由于HMaster只维护表和region的元数据，而不参与表数据IO的过程，因此HMaster下线仅导致所有元数据的修改被冻结（无法创建删除表，无法修改表的schema，无法进行region的负载均衡，无法处理region上下线，无法进行region的合并，唯一例外的是region的split可以正常进行，因为只有HRegionServer参与），表的数据读写还可以正常进行。因此HMaster下线短时间内对整个HBase集群没有影响。
从上线过程可以看到，HMaster保存的信息全是可以冗余信息（都可以从系统其它地方收集到或者计算出来），因此，一般HBase集群中总是有一个HMaster在提供服务，还有一个以上的HMaster在等待时机抢占它的位置。