Hypertable是一个开源、高性能、可伸缩的数据库，采用与Google的BigTable相似的模型。BigTable让用户可以通过一些主键来组织海量数据，并实现高效的查询。Hypertable和HBase分别是BigTable的两个开源实现：HBase主要使用Java语言开发，而Hypertable使用Boost
C++，另外在一些细节的设计理念上也有所不同。
Hypertable系统主要包括Hyperspace、Master和Range
Server三大组件（如图1所示）。Hyperspace是一个锁服务，地位相当于Google的Chubby，主要用于同步、检测节点是否发生故障和存放顶层位置信息；Master主要用于完成任务分配，未来会有负载均衡以及灾后重建（Range
Server失效后自动恢复服务）等其他作用；Range Server是Hypertable的实际工作者，主要负责对一个Range中的数据提供服务，此外它还肩负起灾后重建的责任，即重放本地日志恢复自身故障前状态；另外，还有访问Hypertable的客户端Client等组件。
图1 Hypertable原有架构示意图
业务应用
Facebook在SIGMOD 2011会议上介绍了基于Hadoop/HBase的三种应用系统：Titan（Facebook
Messages）、Puma（Facebook Insights）和ODS（Facebook Internal
Metrics）。Titan主要用于用户数据存储，Puma用于MapReduce分布式计算，ODS用于存储公司内部监控数据，Facebook基于HBase的应用方式与国内几大互联网公司类似。
和ODS类似，对于一些硬件或软件的运行数据，我们会保存监控数据到数据库中，供软件工程师或者运维工程师查询。这里的查询可能是大批量的，也可能是个别条目；可能是延迟查询，也可能是即时查询。将此类业务的需求总结如下。
- 要求存储容量非常大，往往达到10～100TB，10亿～100亿条记录。
- 需要支持自动扩容，因为数据的增长模式不易估计，可能出现短时间的爆炸性增长。
- 写吞吐的压力较大，每秒超过1万次的插入。
- 近期导入数据能够快速检索。
- 需要支持扫描早期的大量数据，例如支持周期性的检查或回滚。
这里可选的一个方案是使用传统的DBMS（如MySQL）。但它存在如下弊端：首先MySQL单机存储有上限，一般超过1.5GB性能就会有波动；不过即使MySQL支持拆表，也并非完全分布式的，由于表的大小限制，对于不规则的数据增长模式，分布式MySQL也并不能很好地应对，如果抖动频率较大，需要引入较多的人工操作来进行数据迁移；再者MySQL也不支持表的Schema动态改变。另一个可选方式是使用Hadoop。不过MapReduce并非实时计算，并且HDFS不支持随机写，随机读性能也很差。
综上分析，我们选择BigTable类型的系统来支持业务需求，即使用Hypertable+Hadoop的方式（如图2所示）。
图2 监控数据收集与查询示意图
高可用改进
元数据集中化
挑战：在Hypertable或其他类似BigTable的系统中，元数据一般采用一种两级的类B+树结构，这主要是出于规模的考虑：采用这种结构理论上可以支持存放并索引2EB的用户数据。若要索引这么多用户数据，所需的元数据就高达16TB，一台机器是存不下的，因此在类BigTable系统中，元数据也是分布在不同节点上进行管理的，集群中任意一个节点既可能包含用户Range也可能包含元数据Range。
虽然这种做法可以解决规模问题，但在管理上带来了一些困难，特别是进行故障恢复时，由于用户表的Range恢复过程中需要读取元数据，所以必须先恢复METADATA表中的Range，再恢复用户表中的Range。如果有多台Range
Server同时故障，这种跨节点的依赖性处理起来非常困难，其他一些维护性操作同样具有类似问题。此外，由于一条METADATA实际上覆盖了一个200MB的Range，所以任何一台包含METADATA的Range
Server发生故障，都可能导致这部分METADATA所涵盖的一大批数据不可访问。将METADATA分布到多个不同的Range
Server上，无异于给系统增加了很多单点，降低了系统可靠性。
解决：本着简单原则，我们认为将元数据与用户数据分离，放在专用的Meta
Range Server上更具有可操作性。元数据集中化的唯一缺点是，由于受Meta Range Server内存限制，32GB物理内存所能存放的元数据理论上只能支持上PB的用户数据。但考虑一般机房所能容纳的机器规模，PB级的数据规模完全可以满足大多数公司的需要。
图3 Hypertable高可用改进架构示意图
图3给出了Hypertable元数据集中管理的整体结构。目前的实现将Hypertable中的数据服务器（Range
Server）分为两种：Meta Range Server和User Range Server。Meta
Range Server只管理Root表和METADATA表的Range，User Range Server只管理用户表的Range。由于Master的负载较轻，因此一般将Meta
Range Server与Master放在同一个节点上。
系统启动时，每个Range Server从配置文件得知自己的类型，并在注册时汇报自己的类型。Master记录每台Range
Server的信息。当Master需要将Range分配给Range Server时（例如表格创建和Range分裂），会根据Range所在表格的类型来选择合适的Range
Server，元数据Range分配到Meta Range Server，用户Range则分配到User
Range Server。
数据与日志存储分离
挑战：Hypertable集群中某些Range
Server发生故障（Range Server进程故障退出）时，需要重新启动该Range Server并恢复服务，这依赖于Range
Server记录的操作日志（CommitLog和SplitLog等）。BigTable系统（Hypertable/HBase）最重要的功能之一是自动恢复，自动恢复依赖操作日志（Commit
Log）能够真正写入HDFS（Sync），故障发生后，系统通过重放日志构建故障前的一致性状态。
在我们早期使用Hypertable和Hadoop系统时，Hadoop
0.18版本尚不支持Append Sync功能。即使当前版本的Hadoop支持了Append Sync功能，频繁使用Sync也会影响系统的写吞吐能力。另外，Hadoop的稳定性在当时还不能得到保证，存在写入失败的情况。如果Hadoop出现问题，那么Hypertable刚写入的数据可能丢失。如果是日志，那么重启时无法恢复系统状态。
解决：一般情况下，Hypertable系统的存储基于Hadoop文件系统，数据和日志都写入HDFS。而在改进后的Hypertable系统中我们采用了不同的存储方式：数据写HDFS，日志写Local
FS。
较之本地文件系统Ext2等，HDFS的稳定性还是略逊一些，在Hypertable的实际运维过程中，我们也遇到过Hypertable向Hadoop写入数据失败的情况。鉴于日志的重要性，我们选择将日志写入可靠性更高的本地文件系统，这样即使Hadoop写文件时出现问题，也可以通过重放本地日志来恢复Hypertable系统状态。
改进后的Hypertable集群发生故障时，有以下几种处理场景。
- 写日志故障：Range Server在写日志时（CommitLog等）发生错误，可能是本地磁盘故障。此时日志的完整性不能得到保证，需要在Range
Server写日志的相关操作上附加额外的例外处理。日志写例外将触发Range Server执行一次OFFLINE操作，即在日志完整性不能保证的前提下，尽快保证数据的完整性和一致性，之后再人工参与后续的恢复处理。
- 写数据故障：Range Server故障非日志操作引起的，可能由系统Bug导致，也可能是Hadoop写数据文件失败。此时日志的完整性有保障，可以直接执行SHUTDOWN操作，关闭各个Range
Server。待Bug解决或Hadoop恢复后，重启Hypertable重放日志即可恢复集群状态和数据。
以上提到半自动容错机制的两条路线分别保证了“日志- | 数据+”和“日志+
| 数据-”两种故障情况下集群数据的完整性和一致性。那么有没有“日志- | 数据-”的情况，极端情况下可能出现Hadoop写数据文件失败和某Data
Node（Range Server）硬盘故障同时发生，此时系统将不可避免地丢失数据，我们只能通过上层应用回滚重放的方式来恢复系统数据。
分裂日志策略
挑战：Hypertable系统涉及的日志为CommitLog和SplitLog等，日志写本地文件系统的策略约束了SplitLog的故障恢复。
Hypertable系统设计SplitLog的初衷在于保证导入数据的速率。Range
Server上的Range在分裂时，数据可以无阻塞地写入SplitLog（它必须写到分布式文件系统上，因为它保存的是实际数据），Range分裂完成后SplitLog文件可能被其他的Range
Server重放。CommitLog中记录了SplitLog的位置，系统恢复时日志重放会涉及SplitLog日志的重放，如果SplitLog写在本地，那么故障恢复时就无法读取该日志。
HBase系统中并未涉及SplitLog机制，在Range分裂时数据不能继续导入。
解决：解决方案有两种，一种是本着稳定性和可靠性优先于性能的原则，为了保证日志的可靠性和使得自动恢复机制更简单，取消SplitLog机制，修改后的Hypertable系统在Range分裂过程不涉及SplitLog相关操作；另一种是将SplitLog写入更加可靠的共享存储中，能够让Range
Server远程访问，这相当于引入了第三方系统。
安全停机策略
挑战：kill/run操作可以完成任意时刻Hypertable系统的关闭和启动，无论当前是否正在导入数据，因为Range
Server启动后会重放日志。但由于当时的Hypertable缺乏自动迁移（负载均衡）机制，这组操作并不适用于集群的变更，例如更替或添加节点。
解决：offline/online操作方式的提出是为了辅助kill/run操作，增加Hypertable集群的可扩展性。执行这组操作，可以保证offline执行时内存数据都写入文件系统，online执行时Range能够均匀分布加载，易于集群节点更换。系统管理员通过Hypertable命令行工具执行offline向各个Range
Server发出命令，Range Server进程收到offline命令后，等待其上执行的Maintenance任务执行完成，并卸载其上加载的Range后退出。Range卸载成功时，所有系统数据被成功写入分布式文件系统，本地文件系统的日志被删除；卸载失败时，日志保留。系统管理员通过Hypertable命令行工具执行online命令，Master收到online命令后，将METADATA记录的Ranges均匀分配给各个Range
Server加载，这就做到了半自动的负载均衡。
性能优化
内存优化
挑战：在Hypertable系统的运维中，我们发现，Hypertable在内存使用效率上存在严重问题。在数据插入过程中，Range
Server内存用量一直飙升，而且持久不下，很容易造成内存溢出并最终崩溃，严重威胁Hypertable的稳定性。
为了定位内存占用过量问题，我们使用valgrind和TCMalloc库的Heap
Profiling工具对Hypertable进行了测试，发现Hypertable内存飙升的原因是Cell
Cache代码中存在频繁分配、释放小片内存（从十几字节到几千字节不等）的情况，从而产生了大量内存碎片，致使内存效率存在严重问题。如图4所示，Range
Server中的大量内存分配集中于Cell Cache为<key, value>和Cell
Map进行空间分配的时候。
图4 改进前Range Server内存使用情况统计
解决：我们决定对Cell Cache相关的内存实施独立管理，即采用自定义的内存分配回收方式管理<key,
value>和Cell Map，使其产生的内存碎片最小化。
图5显示了Hypertable数据服务器上的数据更新过程。Client向Range
Server发送数据（<key, value>形式），Range Server首先将数据缓存在Cell
Cache中，并使用Cell Map结构建立树形索引。当需要进行Compaction时，会新开一个Cell
Cache，并把当前Cell Cache冻结，新写入的数据会进入新开的Cell Cache，而冻结的Cell
Cache则在后台写到文件系统中形成Cell Store文件，Compaction完成后，冻结了的Cell
Cache会被统一释放。此过程中，Cell Cache涉及的内存分配释放操作主要有：分配空间（new）容纳要写入的key/value；分配空间维护Cell
Map（本质上是一个std::map，使用默认的STL allocator分配空间）索引结构；释放数据和索引占用的全部空间。可见，问题主要出在内存分配太过细碎。
图5 Hypertable插入数据时Cell
Cache内存分配示意图
我们修改了Cell Cache的分配策略，利用简化的内存池思想，将内存分配策略改为统一分配。每个Cell
Cache使用1个内存池（MemPool），每个MemPool初始时包含1个4MB（默认设置）的缓冲区（MemBuf），所有的<key,
value>和Cell Map结构占用的空间都在MemBuf内部分配。当MemBuf满了之后，再分配一片新的MemBuf，释放时也是大片释放，这样就防止了频繁的new/delete操作。此外，<key,
value>和Cell Map结构占用的内存是分别从MemBuf的两端分配的，这样做的目的是保证Cell
Map内存对齐，减少因为内存非对齐访问带来的效率下降。当一个缓冲区用满后，内存池会自动扩充一个新的缓冲区，内存释放只是针对整个内存池。
这种内存池分配方式最终也被合入到Hypertable官方版本之中。
图6给出了Google Heap Profiling工具检测的Cell
Cache内存使用情况，对比图4中的数据，改进后版本Range Server的主要内存使用集中于CellCachePool::get_memory，即Cell
Cache的内存使用，这和原始版本中主要使用内存的地方是一致的。这说明如果我们的内存管理机制有效，就能大量减小Hypertable的内存占用量。
图6 改进后Range Server内存使用情况统计
图7给出了Range Server的Cell Cache在使用普通new/delete、TC
Malloc、Pool Malloc（with Map）以及Pool Malloc（without Map）四种内存分配方式下，插入数据过程及之后的内存占用量对比。图7中的蓝、绿、黄、红四种颜色分别对应上述的四种分配方式。可以看出，普通分配方式的内存占用量最不理想，并且最终不能降低，最终内存占用约6.4GB；TC
Malloc方式较前者略好，内存占用增长方式也与之相似，也是最终内存占用很大，约4.4GB；后两种内存池方式在整个过程中的内存占用变化趋势很一致，区别在于对Cell
Map使用内存池分配方式的曲线最终能够降到很低（30MB左右），而对Map使用默认（STL库）内存分配方式的曲线下降的幅度并没有那么大，最终的内存占用大约为929MB。
图7 各种分配策略下的Range Server内存使用情况对比
随机访问
挑战：Hypertable支持顺序读和随机读，相比顺序读，随机读的性能并不好。由于随机读（非批量）性能较低，基于Hypertable的某些应用功能也很难实现，因此优化随机性能对支持更多应用以及提升系统整体性能都非常有好处。
如图8所示，使用IOzone对一些常见机型的机器磁盘做随机读测试，可以看到，如果访问落到磁盘，性能会非常差，最好吞吐也是小于2MB/s。
图8 各种机型磁盘随机读写吞吐对比
解决：从磁盘分级、内存模式和Cache支持三个方面进行解决。
（1）磁盘分级向Hypertable系统导入470GB的原始数据，导入后经压缩实际占用360GB×3副本≈1.1TB磁盘空间，大约分裂为2600多个Range，平均每台服务器负责近300个。以下测试进行了3轮，每轮都分别进行单进程和多进程随机查询，每个进程共完成1000次查询。相对于第一轮，第二轮进行了两项优化：对row
key进行了反转，例如1234→4321，从而使之分布更均匀；调整每个range的cell store个数上限到5（默认是10），第三轮则把cell
store个数进一步缩小到1（通过发命令强制做major compaction）。测试结果如图9所示。
图9 cell store文件数配置不同时导入性能对比
此测试最大的特点是数据量远大于内存总数，因此存在较多随机磁盘访问。以第二轮16进程查询为例，平均每个Range有4.4个Cell
Store文件，因此每秒需要进行4.4×216≈950次HDFS文件随机访问。每读一次HDFS中的文件实际至少需要访问两个文件：一个blk文件和一个meta文件，因此每秒至少需要950×2=1900次随机磁盘访问，这还不算dentry
cache miss和超时重试。观察发现，实际测试过程中最繁忙的节点每秒的磁盘随机读取次数达500多次，磁盘I/O利用率达到100%。第三轮测试同样有类似的规律。因此我们可以得出结论，数据量较大时，Hypertable的瓶颈在于磁盘随机I/O次数。
我们使用分层的方式来提升磁盘随机访问性能。固化存储分级为SSD/SATA/SAS，随机读性能要求高的应用数据存储到SSD，依次类推。测试发现，使用SSD，随机读性能提升60%以上，不过随机写性能会有部分下降，而且SSD的更新寿命约为1万个操作。
（2）内存模式
对于那些频繁访问的数据，我们可以将其设置为in memory方式，这些数据将一直驻留内存（直接用一个C++
std::map结构存起来的，本质上相当于使用了红黑树索引），因此随机查询时不用从文件里读，效率很高。
如果只用一台Range Server，使用1个进程查询同一行数据（共约600字节数据），速度可达4650次/s，若用16个进程并行查询，每秒总查询次数达到12700次，40进程时达到峰值16000次/s，相当于约10MB/s；如果每次查询50行数据（40进程并行查询），每秒查询次数下降到1300左右，但聚合带宽达到40MB/s。此过程Range
Server的CPU sys时间较高（30%~40%），但user和iowait时间都比较低，因此认为瓶颈在网络RPC上。
但in memory这种模式非常耗费内存，原因有以下两点。
- 由于Hypertable设计时为了支持稀疏表，每个value是单独存的，而不是按行存的，因此每个value都需要存一份key
（包括row key、column family、column qualifier和timestamp，最小开销16字节），再加上map数据结构的开销24字节，一个value至少有40字节额外开销，一个帖子就是40×13=520字节，比帖子的实际内容（平均300多字节）还多。
- 为了支持高并发，Hypertable采用了MVCC（Multi-version Concurrency
Control）模式存储<key, value>，也就是说，删改一个value时只是追加了一个补丁，而不是在原值基础上修改，多余的版本只有当Cell
Cache大小达到一定程度时才会清理。
（3）Cache支持
当前版本的Hypertable依据当时的负载状况，动态调整分配给每个子系统的内存。对于读密集型的负载，Hypertable分配大部分内存给Block
Cache；而HBase则固定分配20%的Java Heap作为Block Cache。此外，Hypertable还提供Query
Cache机制，缓存查询结果，使得其随机访问性能超过了HBase，如图10所示。当然，Bloomfilter机制对HBase和Hypertable都支持，能够避免大量的无效访问。
图10 Hypertable vs. HBase随机读吞吐量测试
小结
HBase在Facebook的应用非常成功，后端平台的实时改进提高了其前端的业务水平。而Hypertable尚未在业界大规模使用，但我依然非常看好它，看好其精细的架构和高质量的代码实现。相信未来将会有更多的开发者来使用和改进Hypertable系统。
|
