hypertable介绍

一 Hypertable 是什么：
Hypertable 是一个正在进行中的开源项目，以google的bigtable论文为基础指导，使用c++语言实现。目的是为了解决大并发，大数据量的数据库需求。目前只支持最基本的查询功能，对于事物，关联查询等都不支持。对单条查询的响应时间可能也不如传统数据库（要看数据量，量越大，对hypertable越有力）。好处是，可以处理大量并发请求，和管理大量数据。可扩缩性好，扩容只需要增加集群中的机器就ok了。任何节点失效，既不会造成系统瘫痪也不会丢失数据。在集群节点足够的情况下，并发量和数据量对性能基本没有影响。
注意：Hypertable不是关系数据库。而且它对稀疏数据是只存储其有效部分的。举个例子来说，假设一个表有10列。表中的一条记录，只有第三列有值。那么实际上只有第三列被存储了，无值的列没有保留空位。这些特点使得 Hypertable 在使用的时候与关系数据库不同。

二  hypertable 的总体架构

上面是 Hypertable 项目文档中的总体架构图。简单介绍一下各个组成部分。
Hyperspace：可以认为是一个文件存储系统，用来存储一些元数据信息，同时提供一些锁的功能。在google的bigtable论文中，这个模块叫做 Chubby。是一个小集群来实现的。在 Hypertable 目前的版本中，这是一台单台服务器，内部采用 Berkeley Db 实现。单点服务器制造了一个系统瓶颈，这台服务器不能失效，所以在将来的版本中，这个模块将采用类似 Chubby 的集群实现。
Master：Master有两个主要责任。1 管理元操作，比如建表，更改表结构等。2 管理RangeServer,检测 RangeServer 的工作状态，调整 RangeServer 服务的数据以实现负载均衡。
RangeServer ：RangeServer 是真正提供服务的单元，每个 RangeServer 管理一张表的部分数据。RangeServer 的详细信息，后面在介绍
DFS Broker ：它的主要作用是使用底层的文件系统来完成 Hypertable 对文件系统的请求。Hypertable 对文件系统的使用有一个很简单的接口，只需要文件系统提供几个很简单的操作就可以。 Hypertable 的读写文件等操作都是以socker形式向 DFS Broker 发出请求来完成。这样对于不同的文件系统，只要实现一个 DFS Broker 就可以与 Hypertable 一起工作了。
存储引擎： Hypertable 设计是为了使用分布式存储系统，但是当然也可以使用本地文件系统。 存储引擎只需要提供最简单的几个功能就可以与 Hypertable 协同工作了。

三 分布式数据库要解决的问题和 Hypertable 的方法
首先说明一下，这里所提到的 Hypertable 的实现方法，基本都是学习自big table。 原创版权归 google 所有。一个分布式数据库，在仅仅实现最基本的数据库特性的时候要解决下面一些主要问题。1 怎么将数据分布到各个节点（注意，这里只是指对数据的服务分布到节点的问题，存储由底层存储引擎解决）。一种简单的方法是把数据按照某种方式均匀分布到所有节点。但是这就要求每一次查询都要所有节点参与。这只有在每个表，每次查询结果数据量都足够大的时候才是可行的。数据库显然不符合这个要求（搜索引擎在这一点上是ok的）。Hypertable 实际上是把一个表，按照主键顺序分成 range，每个range被一个 RangeServer 管理起来。2 负载均衡的处理。在 Hypertable 中，Master 负责负载均衡。它会检查各个 RangeServer 的状态，根据情况，调整 RangeServer 所负责的具体 Range. 3 数据的存储问题。因为 Hypertable 使用其他的分布式存储系统，所以它本省不需要考虑这个问题。但是为了适应其他的分布式存储，要求 Hypertable 在实现的时候只能使用文件系统的一个子集，而且要时刻考虑到分布式文件系统的一些特点。这直接决定了底层存储结构的设计。而 couch db 这种，自己开发了存储引擎的，在上层设计上就可以自由得多。4 版本控制和一致性问题。Hypertable 提供多版本支持，根据配置保存一定的历史版本记录，以时间作为索引。当使用查询限制条件的limit=1的时候，如果出来不止一条记录，不要奇怪，因为还有版本这个维度。除非再加上revs=1。 5 可靠性问题：一个节点挂掉，不能影响服务的提供。因为数据都存储在分布式的文件系统上。所以一个节点挂掉的时候，数据并没有丢失。这个时候，Master 会调度其他节点接过挂掉节点所负责的 range 继续对外提供服务。

四 基本概念介绍
1 range : 在 hypertable 中，一张表被按照主键划分成 N 个 range。range 是负责均衡的单位，一个 range 只能被一个 RangeServer 所管理。range在增长到一定大小之后要分裂。举一个具体的例子来解释一下。我们的示例表只有两个字段，id 和 name。 id是主键。开始的时候，整个表只有一个range， 所有对这个表的操作，都由一个 RangeServer 来处理。现在假设我们不断的插入数据，range内的数据在增长，当数据增长到一个配置值，这里假设是100条记录吧（实际上一般是百兆级别）。我们认为这个range已经太大了，需要分裂。 怎么分裂呢？按照主键从中间开始分成两个range。比如id现在的范围是1 – 100 那么从50开始，1-50的是一个range，51-无穷的是第二个range。这个时候 Master 会根据负载均衡，把其中一个调度到其他 RangeServer 上。这样就实现的负载均衡。这个例子里主键是id。那么第一个range，1-50的那个是不是就不会增长分裂了呢。不一定的，别忘了 hypertable 是保留多版本的。所以数据的修改也会导致range里数据量的增加，然后再分裂。
2 access group：数据库对数据的存储在逻辑上有两种方式，可以把所有列的数据存储在一起（按行存储），也可以把列分开存储（按列存储）。两种存储方式各有利弊。适用不同的应用场景。Hypertable 里增加了access group 概念。可以把几个列组成一个 access group，那么这几个列就会存储在一起。极端的，每个列一个access group 则等于按列存储。所有列一个access group 则等于按行存储。
3 column family 和 column qualifier：可以把 column family 想象成传统数据库的列，column qualifier 想象成列的某种分类。这个设计是为了方便互联网应用而做出的。这个概念在使用 Hypertable 的时候很有作用。本文的目的是介绍 Hypertable 的实现。对此不做详细讨论。

总体介绍就介绍到这里。下面将从存储结构开始，介绍 RangServer 的实现。

存储结构介绍：考虑到大部分分布式文件系统对文件追加容易修改困难的特点（为什么会有这种特点请参看分布式文件系统相关的论文），Hypertable 采用了只追加不修改的文件存储方式。任何对原来记录的修改都是在后面添加一条新的记录。在读取的时候可以指定读取的版本数。当每次只读取最新版本的时候，看到的就是最终结果。那么 Hypertable 是如何通过只追加的方式来实现数据的存储以及按照主键的查询的呢？回忆上一篇里面介绍的 range 概念，讲清楚了 range 是怎么存储的自然也就清楚了整个表数据的存储方式。简单来说，一个 range 在存储上是一系列的有序的数据块。Hypertable称之为CellStore。一个 CellStore 由一些列的 block 再加上一个对block的索引以及一些查询优化信息（Bloom Filter）组成。关于Bloom Filter 后边再介绍，我们先把注意力放到bolock和索引上。首先，一个 CellStore 中的数据是按照主键排序了的，其次，索引是只索引到block的。举一个具体的例子来看一下（我们只关注block和索引，忽略 Bloom Filter 信息文件头信息等）。还是那个id，name两个列的表。我们现在看一个CellStore，id从0到400.每一百数据为一个block。那么存储起来好像是类似的样子 :

一个range收到查询请求的时候先读取CellStore中的索引部分，这样可以定位出所需要的数据在哪个block中，然后读取相应的 block并遍历查找所需要的数据。一般一个block的大小为64k。看起来很简单，问题来了，数据的插入显然不是按照顺序插入的，怎么存储成这种排序的形式呢？这是因为所有插入操作其实都是在内存中进行。当内存中数据达到一定的数量的时候才持久化成上面的形式到文件系统里。那么假设现在id为0-400的数据已经持久化到文件系统了，新来的这一范围的数据怎么办呢（比如对id为205的数据做更新，我们知道所有的更新操作实际上是插入新的数据来实现的）？还是先写到内存中，当内存中的数据达到一定数量的时候在持久化成另外一个CellStore.那么查询的时候怎么得到所需要的数据呢，对的，要在几个 CellStore（内存中那个没持久化的也可以认为是一个特殊的CellStore）同时进行查找然后合并。再借用 Hypertable 的一个图释

上图中的Merge Scanner会负责把结果合并到一起的。

随着数据的变化，Cell Store在逐渐的增加，这样就会减慢查询的效率。为了解决这个问题，需要后台有进程合并已经持久化的Cell Store。这一个过程叫做merging compaction（big table术语）。这也是丢弃无用记录的好时候（hypertable 允许配置保留最近n个版本的记录或者最近n时间的记录）。这个过程就类似一个归并排序的过程。那么当数据越来越多的时候，是不是即便有合并过程，也会导致出现非常多的CellStore呢？别忘了，我们的range是有大小限制的。如果数据很多，range是要分裂的，另外一个range会被调度到较空闲的 RangeServer 去运行。所以只要集群的节点足够，不需要担心这个问题。

ok，介绍到这里应该对range的存储结构和工作方法有大略的认识了。table由range组成。那么下一个关心的问题可能就是元数据的问题了。一个 table有哪些range组成，各个range所管理的范围是什么。这些是元数据信息。这些信息怎么存储呢？这些其实也是以一个表（元数据表）的形式存贮在 Hypertable 中的。只是这个表有些特殊。先看一个从big table转过来的图释：

注意 bigtable 里的chubby就是Hypertable里面的Hyperspace。这个图释是什么意思呢？在Hyperspace里面存储了元数据表的元数据信息。听着绕嘴吧，这是因为元数据表也是一张普通的表，它足够大的时候也要分裂成很多range。关于元数据表的range等信息息存储在Hyperspace 中，叫做Root table。Root table只增长，不分裂。也就是说Root table永远只有一个range，这是为了控制找到一个具体表信息的间接性不会大于三层。假设我们要查找某个表的信息。这些信息是存储在元数据表中的。我们需要先查找元数据表，但是实际上我们不知道去如何以及怎样查找元数据表，所以先要向hyperspace请求元数据表的元信息，具体来说就是查到我们所需要查询的信息在元数据表的哪个rang中。然后去相应的range查找具体信息。为了减少与hyperspace的交互，客户端会缓存一些Root table的信息。

介绍到这里，大的逻辑层面上的重要概念就介绍完了。大家可以对Hypertable有一个大致的整体了解。但是很多优化，扩展等细节信息都被省略掉了，比 如数据压缩，Bloom Filter等。

Hypertable 代码可读性不错，推荐大家有时间的时候仔细读一下。 这里介绍一些 hypertable 的特性，在对 hypertable 代码研习和具体使用的时候都会有所帮助。
首先，必须非常明确的是 Hypertable 不是大家熟悉的关系数据库，也不打算取代关系数据库。在 hypertable 中数据是一系列的 key/value 对。其中 key 是一个所谓四维的关键字：

看到这样的 Key 可想而知，对于每行的每个列，都有一个上面这样的 key 存在。所以当 row key 比较长，而列的内容不是很大的时候，如果发现key占用的空间比value要大，也不要奇怪。插一句，通过对表本身的设计，可以达到数据非常好的可压缩性，再配以适合的压缩算法可以很大的提升对空间的利用。事实上，如何设计一个良好的 row key 在对 hyoertable 的使用中也是很重要的一个方面，别忘了 row key 是支持范围查找的。这种 key/value 结构对于按列存储有很好的支持，所以在设计 hypertable 应用的时候，列完全可以作为一种强有力的可查询手段。

  Hypertable 目前版本还只能按照主键进行查询。很多应用又的确有通过索引查询的需求，那么如何实现这种需求呢。我们可以读一读与 hypertable 同源的 Hbase 的实现。Hbase 现在已经支持了索引，可以预计，将来 Hypertable 支持索引的方式与 Hbase 应该是近似的。那么 Hbase 是如何来对列做索引的呢？其实就是再建立一张表，用需要被索引的列做键值，value是被索引记录的主键。实际上 Hbase 是允许用户自己定义索引的生成算法的，这里要注意，索引表的 row key 也要是唯一值。不然会认为后面的是对前面的版本覆盖。可是对于某些列，做索引的时候必然无法保证值的唯一。比如一个员工登记表，员工号是唯一 row key，而我们希望在员工名字上作索引，显然员工名字是有可能有重复的。按照上面的说法，为了在员工名字上建立索引我们需要另建一张表，row key 是员工名字，value 是员工号。假设员工号为10和40的员工都叫做张三。那么索引表里在row key 张三下就会出现两条记录，值分别是10和40. 这个时候就无法区分到底是新插入不同的记录还是对原来记录的修改，造成混乱。那么怎么解决呢，我们看一下Hbase的一个默认算法类 SimpleIndexKeyGenerator.java。 简单来说，他用被索引列的 column value 和 row key 作为索引列的 row key。还是上面的例子，现在我们索引表里两条记录分别是 row key = 张三_10 value = info1; row key = 张三_40 value = info2. 因为查询是支持范围查找的，所以当我们只查“张三”的时候，被索引的列都可以查到了。上面是简化例子说明，具体信息请查看源代码。