海量存储系列之十一
上一期我们主要在介绍hash相关的切分方式，那么这次我们来看一下有序结构的切分
有序结构的拆分，目前主要就是使用树或类似树的结构进行拆分，这里主要就是指HBase和MongoDB.
使用树结构切分，带来的好处就如hbase和mongoDB的宣传标语一样，可以无缝的实现自由扩展。但反过来，带来的问题其实也不少，下面我们一起来看一看吧。
首先复习B树知识 http://qing.weibo.com/1765738567/693f0847330008ii.html
在B树中，最关键的处理逻辑是如果单个节点数据满的时候，应该进行节点分裂和节点合并。
那么，其实在HBase中也有类似这样的过程。
对于巨大量的数据来说，整个树的Branch节点都有可能超过单机的内存大小上限，甚至超过单机的硬盘大小上限。
这时候就需要把BTree进行拆分，这种拆分的最标准实现映射，就是HBase.
(图片版权方在： http://blog.csdn.net/HEYUTAO007/article/details/5766951 )
![]()
看这个图可能会比较晕，没关系，听我分析之。
首先，整个Hbase就是为了解决一个B树非常巨大，以至于单机无法承载其branch and root节点之后，使用分布式存储的方式来提升整个树的容灾量的一种尝试。
抽象的来看，每一个HRegion都是一个Btree的Node，这个Node会挂在在某个Region server上面，RangeServer内可以存放多个Hregion ,其实就是Btree的branch节点了，但因为Branch也很多，以至于单机无法存放所有branch节点，因此就还需要一层结构来处理这个问题。这就是HMaster 。
上图
![]()
虽然可能有点抽象，不过本质来说就是这样一个东西。
当然，细节有点变化：
HMaster ，在上面的图中是单个点，实际的实现是一个btree,三层结构的。
针对这个问题，Hbase提出的解决思路是，既然变动不大，那就允许他错吧，只要咱知道出错了，改正了就行了。
也即，允许HClient根据错误的Btree选择到错误的Region Server,但一旦发现自己所选的数据在那台Region server上无法找到，则立刻重新更新自己的HMaster表。已达到同步。
这基本上就是BTree的分布式实践中做的最好的HBase的一些过程了。
然后然后，私货时间开始: )
借助HDFS,Hbase几乎实现了无限的扩展性，但整体结构过于复杂和庞大了，最终，他只解决了一个K-V写入的问题，同时又希望对所有用户屏蔽底层的所有数据节点的具体位置。
这套思路有其优势之处（也就是Btree的优势）：
1. 纯粹log场景，btree管理起来非常方便
2. 支持范围查询
但可能的劣势其实也很多
1. 结构繁杂，在各种角色中进行数据同步，这件事本身听起来就已经很吓人了。然而，最终，他只是解决了一个按照K找到V的过程。。Hash一样可以做到
2. Region server ，维护难度较高，核心数据结构点，虽然该机器可以认为是个接近无状态的机器，但如果想拿一台空机器恢复到可以承担某个Region server的指责，这个过程需要的时间会很长，导致的问题就是，系统的一部分数据不可用，甚至发生雪崩。
3. BTree 在不断追加append的时候，其实是有热点的，目前没有很好地办法能在按照时间序或按照自增id序列的时候保证所有的数据存储机都能够比较均衡的写入数据。会存在热点问题，这个问题的源头在BTree需要有序并连续，这意味着连续的数据只会被写在一个region块内，这个问题在单机btree其实也是存在的，但有raid技术，以及有二级索引，所以问题没有那么明显。（感谢@bluedavy)
综上，HBase其实从一开始是一个面向后端处理的数据引擎，在数据一致性上是可以期待的，但对于线上系统来说，他违背了重要的一个原则：简单。所以我“个人”对这一点持保留态度。
不过，这么多大牛在努力的经营HBase这个产品，那么我也乐观其成，毕竟能把这么复杂的东西整的能在这么多台机器上用，也是个巨大成就了。
MongoDB其实也是在学Hbase的这种有序的BTree结构，不过它的实现就简单的多了。
就是把数据拆分成一段一段的数据，用一个公用的配置角色存储这段数据所在的分片。查询时进行二分查找找到。
思路类似。
从角色来看
他的规则引擎实现就是个有序数据的实现，可以认为是个两层有序结构查找.第一层决定数据的具体机器(Mongos+config server)，第二层决定数据在该机的具体位置MongoServer。
有序结构的拆分，目前主要就是使用树或类似树的结构进行拆分，这里主要就是指HBase和MongoDB.
使用树结构切分，带来的好处就如hbase和mongoDB的宣传标语一样，可以无缝的实现自由扩展。但反过来，带来的问题其实也不少，下面我们一起来看一看吧。
首先复习B树知识 http://qing.weibo.com/1765738567/693f0847330008ii.html
在B树中，最关键的处理逻辑是如果单个节点数据满的时候，应该进行节点分裂和节点合并。
那么，其实在HBase中也有类似这样的过程。
对于巨大量的数据来说，整个树的Branch节点都有可能超过单机的内存大小上限，甚至超过单机的硬盘大小上限。
这时候就需要把BTree进行拆分，这种拆分的最标准实现映射，就是HBase.
(图片版权方在： http://blog.csdn.net/HEYUTAO007/article/details/5766951 )
看这个图可能会比较晕，没关系，听我分析之。
首先，整个Hbase就是为了解决一个B树非常巨大，以至于单机无法承载其branch and root节点之后，使用分布式存储的方式来提升整个树的容灾量的一种尝试。
抽象的来看，每一个HRegion都是一个Btree的Node，这个Node会挂在在某个Region server上面，RangeServer内可以存放多个Hregion ,其实就是Btree的branch节点了，但因为Branch也很多，以至于单机无法存放所有branch节点，因此就还需要一层结构来处理这个问题。这就是HMaster 。
上图
当然，细节有点变化：
HMaster ，在上面的图中是单个点，实际的实现是一个btree,三层结构的。
因为HMaster的数据不经常发生变化，同时，每次请求都去访问HMaster，那么HMaster所承担的读写压力就过大了。所以，HBase增加了一个客户端的Cache.来存HMaster中的这几层BTree.
针对这个问题，Hbase提出的解决思路是，既然变动不大，那就允许他错吧，只要咱知道出错了，改正了就行了。
也即，允许HClient根据错误的Btree选择到错误的Region Server,但一旦发现自己所选的数据在那台Region server上无法找到，则立刻重新更新自己的HMaster表。已达到同步。
这基本上就是BTree的分布式实践中做的最好的HBase的一些过程了。
然后然后，私货时间开始: )
借助HDFS,Hbase几乎实现了无限的扩展性，但整体结构过于复杂和庞大了，最终，他只解决了一个K-V写入的问题，同时又希望对所有用户屏蔽底层的所有数据节点的具体位置。
这套思路有其优势之处（也就是Btree的优势）：
1. 纯粹log场景，btree管理起来非常方便
2. 支持范围查询
但可能的劣势其实也很多
1. 结构繁杂，在各种角色中进行数据同步，这件事本身听起来就已经很吓人了。然而，最终，他只是解决了一个按照K找到V的过程。。Hash一样可以做到
2. Region server ，维护难度较高，核心数据结构点，虽然该机器可以认为是个接近无状态的机器，但如果想拿一台空机器恢复到可以承担某个Region server的指责，这个过程需要的时间会很长，导致的问题就是，系统的一部分数据不可用，甚至发生雪崩。
3. BTree 在不断追加append的时候，其实是有热点的，目前没有很好地办法能在按照时间序或按照自增id序列的时候保证所有的数据存储机都能够比较均衡的写入数据。会存在热点问题，这个问题的源头在BTree需要有序并连续，这意味着连续的数据只会被写在一个region块内，这个问题在单机btree其实也是存在的，但有raid技术，以及有二级索引，所以问题没有那么明显。（感谢@bluedavy)
综上，HBase其实从一开始是一个面向后端处理的数据引擎，在数据一致性上是可以期待的，但对于线上系统来说，他违背了重要的一个原则：简单。所以我“个人”对这一点持保留态度。
不过，这么多大牛在努力的经营HBase这个产品，那么我也乐观其成，毕竟能把这么复杂的东西整的能在这么多台机器上用，也是个巨大成就了。
MongoDB其实也是在学Hbase的这种有序的BTree结构，不过它的实现就简单的多了。
就是把数据拆分成一段一段的数据，用一个公用的配置角色存储这段数据所在的分片。查询时进行二分查找找到。
思路类似。
从角色来看
他的规则引擎实现就是个有序数据的实现，可以认为是个两层有序结构查找.第一层决定数据的具体机器(Mongos+config server)，第二层决定数据在该机的具体位置MongoServer。
好了，画个图用了20分钟，今天的介绍就到这里，下期我们来探讨分布式场景下一个必要的过程。数据的迁移方式讨论。
本文来源于"阿里中间件团队播客",原文发表时间" 2012-01-22 "
