作者：胡争,范欣欣
出版社：机械工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
HBase原理与实践试读：
前言
第1章 HBase概述1.1 HBase前生今世1.2 HBase数据模型1.2.1 逻辑视图1.2.2 多维稀疏排序Map1.2.3 物理视图1.2.4 行式存储、列式存储、列簇式存储1.3 HBase体系结构1.4 HBase系统特性
第2章 基础数据结构与算法2.1 跳跃表2.2 LSM树2.3 布隆过滤器2.4 设计KV存储引擎MiniBase
第3章 HBase依赖服务3.1 ZooKeeper简介3.2 HBase中ZooKeeper核心配置3.3 HDFS简介3.4 HBase在HDFS中的文件布局
第4章 HBase客户端4.1 HBase客户端实现4.1.1 定位Meta表4.1.2 Scan的复杂之处4.2 HBase客户端避坑指南
第5章 RegionServer的核心模块5.1 RegionServer内部结构5.2 HLog5.2.1 HLog文件结构5.2.2 HLog文件存储5.2.3 HLog生命周期5.3 MemStore5.3.1 MemStore内部结构5.3.2 MemStore的GC问题5.3.3 MSLAB内存管理方式5.3.4 MemStore Chunk Pool5.3.5 MSLAB相关配置5.4 HFile5.4.1 HFile逻辑结构5.4.2 HFile物理结构5.4.3 HFile的基础Block5.4.4 HFile中与布隆过滤器相关的Block5.4.5 HFile中索引相关的Block5.4.6 HFile文件查看工具5.4.7 HFile V3版本5.5 BlockCache5.5.1 LRUBlockCache5.5.2 SlabCache5.5.3 BucketCache
第6章 HBase读写流程6.1 HBase写入流程6.1.1 写入流程的三个阶段6.1.2 Region写入流程6.1.3 MemStore Flush6.2 BulkLoad功能6.2.1 BulkLoad核心流程6.2.2 BulkLoad基础案例6.3 HBase读取流程6.3.1 Client-Server读取交互逻辑6.3.2 Server端Scan框架体系6.3.3 过滤淘汰不符合查询条件的HFile6.3.4 从HFile中读取待查找Key6.4 深入理解Coprocessor6.4.1 Coprocessor分类6.4.2 Coprocessor加载
第7章 Compaction实现7.1 Compaction基本工作原理7.1.1 Compaction基本流程7.1.2 Compaction触发时机7.1.3 待合并HFile集合选择策略7.1.4 挑选合适的执行线程池7.1.5 HFile文件合并执行7.1.6 Compaction相关注意事项7.2 Compaction高级策略
第8章 负载均衡实现8.1 Region迁移8.2 Region合并8.3 Region分裂8.4 HBase的负载均衡应用
第9章 宕机恢复原理9.1 HBase常见故障分析9.2 HBase故障恢复基本原理9.3 HBase故障恢复流程9.4 HBase故障时间优化
第10章 复制10.1 复制场景及原理10.1.1 管理流程的设计和问题10.1.2 复制原理10.2 串行复制10.2.1 非串行复制导致的问题10.2.2 串行复制的设计思路10.3 同步复制10.3.1 设计思路10.3.2 同步复制和异步复制对比
第11章 备份与恢复11.1 Snapshot概述11.2 Snapshot创建11.2.1 Snapshot技术基础原理11.2.2 在线Snapshot的分布式架构—两阶段提交11.2.3 Snapshot核心实现11.3 Snapshot恢复11.4 Snapshot进阶
第12章 HBase运维12.1 HBase系统监控12.1.1 HBase监控指标输出方式12.1.2 HBase核心监控指标12.1.3 HBase表级监控12.2 HBase集群基准性能测试12.3 HBase YCSB12.4 HBase业务隔离12.5 HBase HBCK12.6 HBase核心参数配置12.7 HBase表设计12.8 Salted Table
第13章 HBase系统调优13.1 HBase GC调优13.2 G1GC性能调优13.3 HBase操作系统调优13.4 HBase-HDFS调优策略13.5 HBase读取性能优化13.5.1 HBase服务器端优化13.5.2 HBase客户端优化13.5.3 HBase列簇设计优化13.6 HBase写入性能调优13.6.1 HBase服务器端优化13.6.2 HBase客户端优化
第14章 HBase运维案例分析14.1 RegionServer宕机14.2 HBase写入异常14.3 HBase运维时问题分析思路
第15章 HBase 2.x核心技术15.1 Procedure功能15.2 In Memory Compaction15.3 MOB对象存储15.4 Offheap读路径和Offheap写路径15.5 异步化设计
第16章 高级话题16.1 二级索引16.2 单行事务和跨行事务16.3 HBase开发与测试16.3.1 HBase社区运作机制16.3.2 项目测试
附录A HBase热门问题集锦前言
Apache HBase是基于Apache Hadoop构建的一个高可用、高性能、多版本的分布式NoSQL数据库，是Google BigTable的开源实现，通过在廉价服务器上搭建大规模结构化存储集群，提供海量数据高性能的随机读写能力。
HBase项目自2006年提交第一行代码以来，经历了13年的蓬勃发展。现在已经有大量企业采用HBase来存储和分析飞速增长的业务数据。从全球范围来看，国内HBase的关注度更是高居榜首，这得益于国内互联网、移动互联网、物联网等领域庞大的数据体量。诸多国内大型科技公司，如阿里巴巴、小米、腾讯、网易、华为、滴滴、快手、中国移动等，都已经把HBase作为极重要的基础设施，很多公司对HBase社区也有长期的投入。截至2019年8月，HBase全球社区已经拥有了83位HBase Committer，而国内就有20位左右的Committer，占[1]了近1/4的比例。近一两年，HBase在国内更是得到了长足的发展，2018年中国HBase技术社区成立，一年时间里社区在多个城市相继组织了9次线下技术沙龙活动，为HBase更好地在国内各公司茁壮成长做出了卓越的贡献。
我们和社区用户多次交流后发现，很多人都希望我们能推荐一本HBase的书。当前市面上有关HBase的书籍大部分都集中于如何使用HBase，例如部署HBase集群，使用客户端API进行读写操作以及协处理器等，诚然，这些内容对快速掌握和使用HBase非常有好处，但是许多HBase使用者并不满足于此，他们更希望能了解和掌握其内部运行原理。因此，当机械工业出版社的吴怡编辑询问我们是否有想法为HBase写一本书时，我们毫不犹豫地答应了。
本书从设计的角度对HBase的整个体系架构和各核心组件进行系统的分析和讲解。与此同时，还介绍常用的性能调优策略以及问题诊断的方法和技巧，帮助读者更好地在实际生产环境中实践。另外，本书最后章节集中介绍HBase 2.x版本的核心特性，例如Procedure v2、In Memory Compaction以及MOB等。本书主要内容
本书不是一本入门级读物，本书面向那些使用HBase作为数据库后端存储的应用程序开发者、有一定经验的运维人员和对HBase内核设计感兴趣的人。
如果你想深入了解HBase的每个组件是如何工作的，如果你想更好地运维或者调优你的HBase集群，如果你想了解HBase 2.x版本的核心特性，就请阅读本书。想要更好地阅读本书，需要具备如下先决条件：
·了解HBase的基本操作。
·了解C、Java等高级语言。
·对一些基本算法有所了解，因为本书会从源代码层面分析HBase的工作机制，如果你能了解这些算法，会使你更深入地理解HBase。
本书共有16章，可以分为6个部分。
第一部分：HBase基础部分，包含第1、2章。其中，第1章主要介绍HBase系统的发展历史、数据模型以及体系结构，第2章主要介绍HBase系统中常用的数据结构以及基础算法。
第二部分：HBase系统相关组件，包含第3、4、5章。其中，第3章重点介绍HBase所依赖的核心组件，包括ZooKeeper、HDFS等，第4章介绍HBase客户端组件实现，第5章介绍RegionServer内部组件的实现。
第三部分：HBase核心工作原理，包含第6、7、8、9、10、11章。其中，第6章详细分析HBase读写流程，第7章介绍HBase Compaction的实现原理，第8章介绍HBase中Region的迁移、合并以及分裂等操作是如何实现的，第9章介绍RegionServer宕机后如何通过HLog进行数据恢复，第10章介绍HBase不同集群之间的复制是如何实现的，第11章介绍HBase如何通过Snapshot机制完成数据的备份和恢复。
第四部分：HBase运维调优实践，包含第12、13、14章。其中，第12章介绍HBase集群常用的运维管理操作，包括集群如何有效监控，基准性能如何测试等，第13章集中介绍HBase集群的常用调优技巧，第14章重点分析几个HBase实际运维案例，通过案例分析介绍HBase集群定位和处理问题的技巧。
第五部分：HBase 2.x核心特性（第15章），介绍HBase最新2.x版本的核心功能与特性。
第六部分：HBase高级话题（第16章），介绍社区中比较热门的二级索引话题，以及HBase内核的开发与测试。
本书的六个部分都是相互独立的话题，读者完全可以从书中任何一个部分开始阅读。当然，如果你想更加系统地学习HBase，建议你从前往后逐章阅读。致谢
在编写本书的过程中，我们非常感谢给予了我们如此多帮助和鼓励的朋友、家人以及同事们。首先感谢HBase官方社区的开发者，是他们极其卓越的工作让我们有机会写这样一本书。另外，还要感谢许许多多中国HBase技术社区的小伙伴，感谢他们提供丰富的HBase使用场景和相关解决方案，他们的经验和分享对推广和普及HBase项目做出了重大贡献。同时感谢我们的家人，没有他们的鼓励和支持，本书不可能完成。最后，一份特别的感谢要送给本书策划编辑吴怡，感谢她在全书撰写过程中所给予的详细指点以及有用的建议。[1] 目前中国区总共有18位HBase Committer，其中6位HBase PMC成员（张铎@小米、张洸豪、胡争@小米，沈春辉、李钰、杨文龙@阿里巴巴）。值得一提的是，张铎于2019年7月18日当选为Apache HBase项目的主席，他将在接下来的时间里带领Apache HBase社区实现HBase项目的更新迭代。第1章 HBase概述
HBase是目前非常热门的一款分布式KV（KeyValue，键值）数据库系统，无论是互联网行业还是其他传统IT行业都在大量使用。尤其是近几年随着国内大数据理念的普及，HBase凭借其高可靠、易扩展、高性能以及成熟的社区支持，受到越来越多企业的青睐。许多大数据系统都将HBase作为底层数据存储服务，例如Kylin、OpenTSDB等。
本章作为全书的开篇，将从HBase的历史发展、数据模型、体系结构、系统特性几个方面，向读者介绍这位主角。1.1 HBase前生今世1.HBase历史发展
要说清楚HBase的来龙去脉，还得从Google当年风靡一时的“三篇论文”——GFS、MapReduce、BigTable说起。2003年Google在SOSP会议上发表了大数据历史上第一篇公认的革命性论文——《GFS：The Google File System》，之所以称其为“革命性”是有多方面原因的：首先，Google在该论文中第一次揭示了如何在大量廉价机器基础上存储海量数据，这让人们第一次意识到海量数据可以在不需要任何高端设备的前提下实现存储，换句话说，任何一家公司都有技术实力存储海量数据，这为之后流行的海量数据处理奠定了坚实的基础。其次，GFS体现了非常超前的设计思想，以至于十几年之后的今天依然指导着大量的分布式系统设计，可以说，任何从事分布式系统开发的人都有必要反复阅读这篇经典论文。
2004年，Google又发表了另一篇非常重要的论文——《MapReduce：Simplefied Data Processing on Large Clusters》，这篇论文论述了两个方面的内容，其中之一是MapReduce的编程模型，在后来的很多讨论中，人们对该模型褒贬不一，该编程模型在之后的技术发展中接受了大量的架构性改进，演变成了很多其他的编程模型，例如DAG模型等。当然，MapReduce模型本身作为一种基础模型得到了保留并依然运行在很多特定领域（比如，Hive依然依赖MapReduce处理长时间的ETL业务）。MapReduce在GFS的基础上再一次将大数据往前推进了一步，论文论述了如何在大量廉价机器的基础上稳定地实现超大规模的并行数据处理，这无疑是非常重要的进步。这篇论文无论在学术界还是在工业界都得到了极度狂热的追捧。原因无非是分布式计算系统可以套用于大量真实的业务场景，几乎任何一套单机计算系统都可以用MapReduce去改良。
2006年，Google发布了第三篇重要论文——《BigTable：A Distributed Storage System for Structured Data》，用于解决Google内部海量结构化数据的存储以及高效读写问题。与前两篇论文相比，这篇论文更难理解一些。这是因为严格意义上来讲，BigTable属于分布式数据库领域，需要读者具备一定的数据库基础，而且论文中提到的数据模型（多维稀疏排序映射模型）对于习惯了关系型数据库的工程师来说确实不易理解。但从系统架构来看，BigTable还是有很多GFS的影子，包括Master-Slave模式、数据分片等。
这三篇论文在大数据历史上，甚至整个IT界的发展历史上都具有革命性意义。但真正让大数据“飞入寻常百姓家”，是另一个科技巨头——Yahoo。Google的三篇论文论证了在大量廉价机器上存储、处理海量数据（结构化数据、非结构化数据）是可行的，然而并没有给出开源方案。2004年，Doug Cutting和Mike Cafarella在为他们的搜索引擎爬虫（Nutch）实现分布式架构的时候看到了Google的GFS论文以及MapReduce论文。他们在之后的几个月里按照论文实现出一个简易版的HDFS和MapReduce，这也就是Hadoop的最早起源。最初这个简易系统确实可以稳定地运行在几十台机器上，但是没有经过大规模使用的系统谈不上完美。所幸他们收到了Yahoo的橄榄枝。在Yahoo，Doug领导的团队不断地对系统进行改进，促成了Hadoop从几十台到几百台再到几千台机器规模的演变，直到这个时候，大数据才真正在普通公司实现落地。
至于BigTable，没有在Yahoo内得到实现，原因不明。一家叫做Powerset的公司，为了高效处理自然语言搜索产生的海量数据实现了BigTable的开源版本——HBase，并在发展了2年之后被Apache收录为顶级项目，正式入驻Hadoop生态系统。HBase成为Apache顶级项目之后发展非常迅速，各大公司纷纷开始使用HBase，HBase社区的高度活跃性让HBase这个系统发展得更有活力。有意思的是，Google在将BigTable作为云服务对外开放的时候，决定提供兼容HBase的API。可见在业界，HBase已经一定程度上得到了广泛的认可和使用。2.HBase使用现状
HBase在国外起步很早，包括Facebook、Yahoo、Pinterest等大公司都大规模使用HBase作为基础服务。在国内HBase相对起步较晚，但现在各大公司对于HBase的使用已经越来越普遍，包括阿里巴巴、小米、华为、网易、京东、滴滴、中国电信、中国人寿等公司都使用HBase存储海量数据，服务于各种在线系统以及离线分析系统，其中阿里巴巴、小米以及京东更是有着数千台HBase的集群规模。业务场景包括订单系统、消息存储系统、用户画像、搜索推荐、安全风控以及物联网时序数据存储等。最近，阿里云、华为云等云提供商先后推出了HBase云服务，为国内更多公司低门槛地使用HBase服务提供了便利。
另外，相比其他技术社区，HBase社区非常活跃，每天都会有大量的国内外工程师参与HBase系统的开发维护，大部分问题都能在社区得到快速积极的响应。近几年，HBase社区中，国内开发者的影响力开始慢慢扩大，在某些功能领域甚至已经占据主导地位。3.HBase版本变迁
HBase从2010年开始前前后后经历了几十个版本的升级，不断地对读写性能、系统可用性以及稳定性等方面进行改进，如图1-1所示。在这些版本中，有部分版本在HBase的发展历程中可谓功勋卓著。图1-1 HBase版本变迁
0.94.x版本是HBase历史上第一个相对稳定的生产线版本，国内最早使用HBase的互联网公司（小米、阿里、网易等）都曾在生产线上大规模使用0.94.x作为服务版本，即使在当前，依然还有很多公司的业务运行在0.94.x版本，可见0.94.x版本在过去的几年时间里是多么辉煌。
之后的2年时间，官方在0.94版本之后发布了两个重要版本：0.96版本和0.98版本，0.96版本实现了很多重大的功能改进，比如BucketCache、MSLAB、MTTR优化等，但也因为功能太多而引入了很多bug，导致生产线上真正投入使用的并不多。直至0.98版本发布。0.98版本修复了大量的bug，大大提升了系统可用性以及稳定性。不得不说，0.98版本是目前业界公认的HBase历史上最稳定的版本之一，也是目前生产线上使用最广泛的版本之一。
2015年2月，社区发布了1.0.0版本，这个版本带来的最大改变是规范了HBase的版本号，此后的版本号都统一遵循semantic versioning语义，如图1-2所示。图1-2 HBase版本规则
比如1.2.6版本中MAJOR版本是1，MINOR版本是2，PATCH是6。不同MAJOR版本不保证功能的兼容性，比如2.x版本不保证一定兼容1.x版本。MINOR版本表示会新增新的功能，比如1.2.x会在1.1.x的基础上新增部分功能。而PATCH版本只负责修复bug，因此可以理解为MAJOR、MINOR相同的情况下，PATCH版本越大，系统越可靠。
在1.0的基础上官方先后发布了1.1.x、1.2.x、1.3.x以及1.4.x等多个版本。因为稳定性的原因，并不建议在生产线上使用1.0.0～1.1.2[1]中间的版本。目前，HBase社区推荐使用的稳定版本为1.4.10。
2.x版本是接下来最受期待的一个版本（升级要慎重，请参考社区中的实践），因为最近一两年社区开发的新功能都将集中在2.x版本发布，2.x包含的核心功能特别多，包括：大幅度减小GC影响的offheap read path/write path工作，极大提升系统稳定性的Procedure V2框架，支持多租户隔离的RegionServer Group功能，支持大对象存储的MOB功能等。[1] 随着HBase项目的不断更新迭代，社区推荐的稳定版也会不断更新。用户可以在这里看到当前HBase社区推荐使用的稳定版本：https://www.apache.org/dist/hbase/stable/。1.2 HBase数据模型
从使用角度来看，HBase包含了大量关系型数据库的基本概念——表、行、列，但在BigTable的论文中又称HBase为“sparse，distributed，persistent multidimensional sorted map”，即HBase本质来看是一个Map。那HBase到底是一个什么样的数据库呢？
实际上，从逻辑视图来看，HBase中的数据是以表形式进行组织的，而且和关系型数据库中的表一样，HBase中的表也由行和列构成，因此HBase非常容易理解。但从物理视图来看，HBase是一个Map，由键值（KeyValue，KV）构成，不过与普通的Map不同，HBase是一个稀疏的、分布式的、多维排序的Map。接下来，笔者首先从逻辑视图层面对HBase中的基本概念进行介绍，接着从稀疏多维排序Map这个视角进行深入解析，最后从物理视图层面说明HBase中的数据如何存储。1.2.1 逻辑视图
在具体了解逻辑视图之前有必要先看看HBase中的基本概念。
·table：表，一个表包含多行数据。
·row：行，一行数据包含一个唯一标识rowkey、多个column以及对应的值。在HBase中，一张表中所有row都按照rowkey的字典序由小到大排序。
·column：列，与关系型数据库中的列不同，HBase中的column由column family（列簇）以及qualifier（列名）两部分组成，两者中间使用"："相连。比如contents：html，其中contents为列簇，html为列簇下具体的一列。column family在表创建的时候需要指定，用户不能随意增减。一个column family下可以设置任意多个qualifier，因此可以理解为HBase中的列可以动态增加，理论上甚至可以扩展到上百万列。
·timestamp：时间戳，每个cell在写入HBase的时候都会默认分配一个时间戳作为该cell的版本，当然，用户也可以在写入的时候自带时间戳。HBase支持多版本特性，即同一rowkey、column下可以有多个value存在，这些value使用timestamp作为版本号，版本越大，表示数据越新。
·cell：单元格，由五元组（row，column，timestamp，type，value）组成的结构，其中type表示Put/Delete这样的操作类型，timestamp代表这个cell的版本。这个结构在数据库中实际是以KV结构存储的，其中（row，column，timestamp，type）是K，value字段对应KV结构的V。
图1-3是BigTable中一张示例表的逻辑视图，表中主要存储网页信息。示例表中包含两行数据，两个rowkey分别为com.cnn.www和com.example.www，按照字典序由小到大排列。每行数据有三个列簇，分别为anchor、contents以及people，其中列簇anchor下有两列，分别为cnnsi.com以及my.look.ca，其他两个列簇都仅有一列。可以看出，根据行com.cnn.www以及列anchor:nnsi.com可以定位到数据CNN，对应的时间戳信息是t9。而同一行的另一列contents:html下却有三个版本的数据，版本号分别为t5、t6和t7。图1-3 HBase逻辑视图
总体来看，HBase的逻辑视图是比较容易理解的，需要注意的是，HBase引入了列簇的概念，列簇下的列可以动态扩展；另外，HBase使用时间戳实现了数据的多版本支持。1.2.2 多维稀疏排序Map
使用关系型数据库中表的概念来描述HBase，对于HBase的入门使用大有裨益，然而，对于理解HBase的工作原理意义不大。要真正理解HBase的工作原理，需要从KV数据库这个视角重新对其审视。BigTable论文中称BigTable为"sparse，distributed，persistent multidimensional sorted map"，可见BigTable本质上是一个Map结构数据库，HBase亦然，也是由一系列KV构成的。然而HBase这个Map系统却并不简单，有很多限定词——稀疏的、分布式的、持久性的、多维的以及排序的。接下来，我们先对这个Map进行解析，这对于之后理解HBase的工作原理非常重要。
大家都知道Map由key和value组成，那组成HBase Map的key和value分别是什么？和普通Map的KV不同，HBase中Map的key是一个复合键，由rowkey、column family、qualifier、type以及timestamp组成，value即为cell的值。举个例子，上节逻辑视图中行"com.cnn.www"以及列"anchor：cnnsi.com"对应的数值"CNN"实际上在HBase中存储为如下KV结构：{"com.cnn.www","anchor","cnnsi.com","put","t9"} -> "CNN"
同理，其他的KV还有：{"com.cnn.www","anchor","my.look.ca","put","t8"} -> "CNN.com"{"com.cnn.www","contents","html","put","t7"} -> "..."{"com.cnn.www","contents","html","put","t6"} -> "..."{"com.cnn.www","contents","html","put","t5"} -> "..."{"com.example.www","people","author","put","t5"} -> "John Doe"
至此，读者对HBase中数据的存储形式有了初步的了解，在此基础上再来介绍多维、稀疏、排序等关键词。
·多维：这个特性比较容易理解。HBase中的Map与普通Map最大的不同在于，key是一个复合数据结构，由多维元素构成，包括rowkey、column family、qualifier、type以及timestamp。
·稀疏：稀疏性是HBase一个突出特点。从图1-3逻辑表中行"com.example.www"可以看出，整整一行仅有一列（people：author）有值，其他列都为空值。在其他数据库中，对于空值的处理一般都会填充null，而对于HBase，空值不需要任何填充。这个特性为什么重要？因为HBase的列在理论上是允许无限扩展的，对于成百万列的表来说，通常都会存在大量的空值，如果使用填充null的策略，势必会造成大量空间的浪费。因此稀疏性是HBase的列可以无限扩展的一个重要条件。
·排序：构成HBase的KV在同一个文件中都是有序的，但规则并不是仅仅按照rowkey排序，而是按照KV中的key进行排序——先比较rowkey，rowkey小的排在前面；如果rowkey相同，再比较column，即column family：qualifier，column小的排在前面；如果column还相同，再比较时间戳timestamp，即版本信息，timestamp大的排在前面。这样的多维元素排序规则对于提升HBase的读取性能至关重要，在后面读取章节会详细分析。
·分布式：很容易理解，构成HBase的所有Map并不集中在某台机器上，而是分布在整个集群中。1.2.3 物理视图
与大多数数据库系统不同，HBase中的数据是按照列簇存储的，即将数据按照列簇分别存储在不同的目录中。
列簇anchor的所有数据存储在一起形成：
列簇contents的所有数据存储在一起形成：
列簇people的所有数据存储在一起形成：1.2.4 行式存储、列式存储、列簇式存储
为什么HBase要将数据按照列簇分别存储？回答这个问题之前需要先了解两个非常常见的概念：行式存储、列式存储，这是数据存储领域比较常见的两种数据存储方式。
行式存储：行式存储系统会将一行数据存储在一起，一行数据写完之后再接着写下一行，最典型的如MySQL这类关系型数据库，如图1-4所示。图1-4 行式存储
行式存储在获取一行数据时是很高效的，但是如果某个查询只需要读取表中指定列对应的数据，那么行式存储会先取出一行行数据，再在每一行数据中截取待查找目标列。这种处理方式在查找过程中引入了大量无用列信息，从而导致大量内存占用。因此，这类系统仅适合于处理OLTP类型的负载，对于OLAP这类分析型负载并不擅长。
列式存储：列式存储理论上会将一列数据存储在一起，不同列的数据分别集中存储，最典型的如Kudu、Parquet on HDFS等系统（文件格式），如图1-5所示。图1-5 列式存储
列式存储对于只查找某些列数据的请求非常高效，只需要连续读出所有待查目标列，然后遍历处理即可；但是反过来，列式存储对于获取一行的请求就不那么高效了，需要多次IO读多个列数据，最终合并得到一行数据。另外，因为同一列的数据通常都具有相同的数据类型，因此列式存储具有天然的高压缩特性。
列簇式存储：从概念上来说，列簇式存储介于行式存储和列式存储之间，可以通过不同的设计思路在行式存储和列式存储两者之间相互切换。比如，一张表只设置一个列簇，这个列簇包含所有用户的列。HBase中一个列簇的数据是存储在一起的，因此这种设计模式就等同于行式存储。再比如，一张表设置大量列簇，每个列簇下仅有一列，很显然这种设计模式就等同于列式存储。上面两例当然是两种极端的情况，在当前体系中不建议设置太多列簇，但是这种架构为HBase将来演变成HTAP（Hybrid Transactional and Analytical Processing）系统提供了最核心的基础。1.3 HBase体系结构
HBase体系结构借鉴了BigTable论文，是典型的Master-Slave模型。系统中有一个管理集群的Master节点以及大量实际服务用户读写的RegionServer节点。除此之外，HBase中所有数据最终都存储在HDFS系统中，这与BigTable实际数据存储在GFS中相对应；系统中还有一个ZooKeeper节点，协助Master对集群进行管理。HBase体系结构如图1-6所示。图1-6 HBase体系结构1.HBase客户端
HBase客户端（Client）提供了Shell命令行接口、原生Java API编程接口、Thrift/REST API编程接口以及MapReduce编程接口。HBase客户端支持所有常见的DML操作以及DDL操作，即数据的增删改查和表的日常维护等。其中Thrift/REST API主要用于支持非Java的上层业务需求，MapReduce接口主要用于批量数据导入以及批量数据读取。
HBase客户端访问数据行之前，首先需要通过元数据表定位目标数据所在RegionServer，之后才会发送请求到该RegionServer。同时这些元数据会被缓存在客户端本地，以方便之后的请求访问。如果集群RegionServer发生宕机或者执行了负载均衡等，从而导致数据分片发生迁移，客户端需要重新请求最新的元数据并缓存在本地。2.ZooKeeper
ZooKeeper（ZK）也是Apache Hadoop的一个顶级项目，基于Google的Chubby开源实现，主要用于协调管理分布式应用程序。在HBase系统中，ZooKeeper扮演着非常重要的角色。
·实现Master高可用：通常情况下系统中只有一个Master工作，一旦Active Master由于异常宕机，ZooKeeper会检测到该宕机事件，并通过一定机制选举出新的Master，保证系统正常运转。
·管理系统核心元数据：比如，管理当前系统中正常工作的RegionServer集合，保存系统元数据表hbase：meta所在的RegionServer地址等。
·参与RegionServer宕机恢复：ZooKeeper通过心跳可以感知到RegionServer是否宕机，并在宕机后通知Master进行宕机处理。
·实现分布式表锁：HBase中对一张表进行各种管理操作（比如alter操作）需要先加表锁，防止其他用户对同一张表进行管理操作，造成表状态不一致。和其他RDBMS表不同，HBase中的表通常都是分布式存储，ZooKeeper可以通过特定机制实现分布式表锁。3.Master
Master主要负责HBase系统的各种管理工作：
·处理用户的各种管理请求，包括建表、修改表、权限操作、切分表、合并数据分片以及Compaction等。
·管理集群中所有RegionServer，包括RegionServer中Region的负载均衡、RegionServer的宕机恢复以及Region的迁移等。
·清理过期日志以及文件，Master会每隔一段时间检查HDFS中HLog是否过期、HFile是否已经被删除，并在过期之后将其删除。4.RegionServer
RegionServer主要用来响应用户的IO请求，是HBase中最核心的模块，由WAL（HLog）、BlockCache以及多个Region构成。
·WAL（HLog）：HLog在HBase中有两个核心作用——其一，用于实现数据的高可靠性，HBase数据随机写入时，并非直接写入HFile数据文件，而是先写入缓存，再异步刷新落盘。为了防止缓存数据丢失，数据写入缓存之前需要首先顺序写入HLog，这样，即使缓存数据丢失，仍然可以通过HLog日志恢复；其二，用于实现HBase集群间主从复制，通过回放主集群推送过来的HLog日志实现主从复制。
·BlockCache：HBase系统中的读缓存。客户端从磁盘读取数据之后通常会将数据缓存到系统内存中，后续访问同一行数据可以直接从内存中获取而不需要访问磁盘。对于带有大量热点读的业务请求来说，缓存机制会带来极大的性能提升。
BlockCache缓存对象是一系列Block块，一个Block默认为64K，由物理上相邻的多个KV数据组成。BlockCache同时利用了空间局部性和时间局部性原理，前者表示最近将读取的KV数据很可能与当前读取到的KV数据在地址上是邻近的，缓存单位是Block（块）而不是单个KV就可以实现空间局部性；后者表示一个KV数据正在被访问，那么近期它还可能再次被访问。当前BlockCache主要有两种实现——LRUBlockCache和BucketCache，前者实现相对简单，而后者在GC优化方面有明显的提升。
·Region：数据表的一个分片，当数据表大小超过一定阈值就会“水平切分”，分裂为两个Region。Region是集群负载均衡的基本单位。通常一张表的Region会分布在整个集群的多台RegionServer上，一个RegionServer上会管理多个Region，当然，这些Region一般来自不同的数据表。
一个Region由一个或者多个Store构成，Store的个数取决于表中列簇（column family）的个数，多少个列簇就有多少个Store。HBase中，每个列簇的数据都集中存放在一起形成一个存储单元Store，因此建议将具有相同IO特性的数据设置在同一个列簇中。
每个Store由一个MemStore和一个或多个HFile组成。MemStore称为写缓存，用户写入数据时首先会写到MemStore，当MemStore写满之后（缓存数据超过阈值，默认128M）系统会异步地将数据flush成一个HFile文件。显然，随着数据不断写入，HFile文件会越来越多，当HFile文件数超过一定阈值之后系统将会执行Compact操作，将这些小文件通过一定策略合并成一个或多个大文件。5.HDFS
HBase底层依赖HDFS组件存储实际数据，包括用户数据文件、HLog日志文件等最终都会写入HDFS落盘。HDFS是Hadoop生态圈内最成熟的组件之一，数据默认三副本存储策略可以有效保证数据的高可靠性。HBase内部封装了一个名为DFSClient的HDFS客户端组件，负责对HDFS的实际数据进行读写访问。1.4 HBase系统特性1.HBase的优点
与其他数据库相比，HBase在系统设计以及实际实践中有很多独特的优点。
·容量巨大：HBase的单表可以支持千亿行、百万列的数据规模，数据容量可以达到TB甚至PB级别。传统的关系型数据库，如Oracle和MySQL等，如果单表记录条数超过亿行，读写性能都会急剧下降，在HBase中并不会出现这样的问题。
·良好的可扩展性：HBase集群可以非常方便地实现集群容量扩展，主要包括数据存储节点扩展以及读写服务节点扩展。HBase底层数据存储依赖于HDFS系统，HDFS可以通过简单地增加DataNode实现扩展，HBase读写服务节点也一样，可以通过简单的增加RegionServer节点实现计算层的扩展。
·稀疏性：HBase支持大量稀疏存储，即允许大量列值为空，并不占用任何存储空间。这与传统数据库不同，传统数据库对于空值的处理要占用一定的存储空间，这会造成一定程度的存储空间浪费。因此可以使用HBase存储多至上百万列的数据，即使表中存在大量的空值，也不需要任何额外空间。
·高性能：HBase目前主要擅长于OLTP场景，数据写操作性能强劲，对于随机单点读以及小范围的扫描读，其性能也能够得到保证。对于大范围的扫描读可以使用MapReduce提供的API，以便实现更高效的并行扫描。
·多版本：HBase支持多版本特性，即一个KV可以同时保留多个版本，用户可以根据需要选择最新版本或者某个历史版本。
·支持过期：HBase支持TTL过期特性，用户只需要设置过期时间，超过TTL的数据就会被自动清理，不需要用户写程序手动删除。
·Hadoop原生支持：HBase是Hadoop生态中的核心成员之一，很多生态组件都可以与其直接对接。HBase数据存储依赖于HDFS，这样的架构可以带来很多好处，比如用户可以直接绕过HBase系统操作HDFS文件，高效地完成数据扫描或者数据导入工作；再比如可以利用HDFS提供的多级存储特性（Archival Storage Feature），根据业务的重要程度将HBase进行分级存储，重要的业务放到SSD，不重要的业务放到HDD。或者用户可以设置归档时间，进而将最近的数据放在SSD，将归档数据文件放在HDD。另外，HBase对MapReduce的支持也已经有了很多案例，后续还会针对Spark做更多的工作。2.HBase的缺点
任何一个系统都不会完美，HBase也一样。HBase不能适用于所有应用场景，例如：
·HBase本身不支持很复杂的聚合运算（如Join、GroupBy等）。如果业务中需要使用聚合运算，可以在HBase之上架设Phoenix组件或者Spark组件，前者主要应用于小规模聚合的OLTP场景，后者应用于大规模聚合的OLAP场景。
·HBase本身并没有实现二级索引功能，所以不支持二级索引查找。好在针对HBase实现的第三方二级索引方案非常丰富，比如目前比较普遍的使用Phoenix提供的二级索引功能。
·HBase原生不支持全局跨行事务，只支持单行事务模型。同样，可以使用Phoenix提供的全局事务模型组件来弥补HBase的这个缺陷。
可以看到，HBase系统本身虽然不擅长某些工作领域，但是借助于Hadoop强大的生态圈，用户只需要在其上架设Phoenix组件、Spark组件或者其他第三方组件，就可以有效地协同工作。第2章 基础数据结构与算法
著名的计算机科学家N.Wirth说过：程序=算法+数据结构。对于HBase这样的一个分布式数据库来说，它的代码规模已经非常庞大，如果加上测试代码以及序列化工具（Protobuf/Thrift）生成的代码，HBase项目（2.0分支）代码行数已经突破150万。但是，即使这样庞大的项目也是由一个个算法和数据结构组成。
本章将会介绍HBase用到的一些核心算法和数据结构。这里，我们假设读者已经具备了“数据结构”课程相关的基础知识，例如链表、栈、队列、平衡二叉树、堆等。
HBase的一个列簇（Column Family）本质上就是一棵LSM树（Log-Structured Merge-Tree）。LSM树分为内存部分和磁盘部分。内存部分是一个维护有序数据集合的数据结构。一般来讲，内存数据结构可以选择平衡二叉树、红黑树、跳跃表（SkipList）等维护有序集的数据结构，这里由于考虑并发性能，HBase选择了表现更优秀的跳跃表。磁盘部分是由一个个独立的文件组成，每一个文件又是由一个个数据块组成。对于数据存储在磁盘上的数据库系统来说，磁盘寻道以及数据读取都是非常耗时的操作（简称IO耗时）。因此，为了避免不必要的IO耗时，可以在磁盘中存储一些额外的二进制数据，这些数据用来判断对于给定的key是否有可能存储在这个数据块中，这个数据结构称为布隆过滤器（BloomFilter）。
本章将介绍HBase的核心数据结构，主要包括跳跃表、LSM树和布隆过滤器。同时，为了使读者加深印象，我们设计了一个轻量级[1]KV存储引擎MiniBase，并提供了一些相关的编程练习。[1] MiniBase是一个基于LSM树设计的轻量级KV存储引擎，代码开源在GitHub上：https://github.com/openinx/minibase。它不是一个适用于线上生产环境的KV引擎，仅用于学习交流。目前，它只是一个基础的轮廓，很多功能需要读者通过练习去完善。2.1 跳跃表
跳跃表（SkipList）是一种能高效实现插入、删除、查找的内存数据结构，这些操作的期望复杂度都是O（logN）。与红黑树以及其他的二分查找树相比，跳跃表的优势在于实现简单，而且在并发场景下加锁粒度更小，从而可以实现更高的并发性。正因为这些优点，跳跃表广泛使用于KV数据库中，诸如Redis、LevelDB、HBase都把跳跃表作为一种维护有序数据集合的基础数据结构。
众所周知，链表这种数据结构的查询复杂度为O（N），这里N是链表中元素的个数。在已经找到要删除元素的情况下，再执行链表的删除操作其实非常高效，只需把待删除元素前一个元素的next指针指向待删除元素的后一个元素即可，复杂度为O（1），如图2-1所示。图2-1 链表删除元素操作
但问题是，链表的查询复杂度太高，因为链表在查询的时候，需要逐个元素地查找。如果链表在查找的时候，能够避免依次查找元素，那么查找复杂度将降低。而跳跃表就是利用这一思想，在链表之上额外存储了一些节点的索引信息，达到避免依次查找元素的目的，从而将查询复杂度优化为O（logN）。将查询复杂度优化之后，自然也优化了插入和删除的复杂度。1.定义
如图2-2所示，跳跃表的定义如下：
·跳跃表由多条分层的链表组成（设为S，S，S，...，S），例012n如图中有6条链表。
·每条链表中的元素都是有序的。
·每条链表都有两个元素：+∞（正无穷大）和-∞（负无穷大），分别表示链表的头部和尾部。
·从上到下，上层链表元素集合是下层链表元素集合的子集，即S是S的子集，S是S的子集。1021
·跳跃表的高度定义为水平链表的层数。图2-2 跳跃表定义2.查找
在跳跃表中查找一个指定元素的流程比较简单。如图2-3所示，以左上角元素（设为currentNode）作为起点：
·如果发现currentNode后继节点的值小于等于待查询值，则沿着这条链表向后查询，否则，切换到当前节点的下一层链表。
·继续查询，直到找到待查询值为止（或者currentNode为空节点）为止。图2-3 在跳跃表中查找元素5的流程3.插入
跳跃表的插入算法要复杂一点。如图2-4所示。首先，需要按照上述查找流程找到待插入元素的前驱和后继；然后，按照如下随机算法生成一个高度值：// p是一个(0,1)之间的常数，一般取p=1/4或者1/2public void randomHeight(double p){ int height = 0 ; while(random.nextDouble() < p) height ++ ; return height + 1;}
最后，将待插入节点按照高度值生成一个垂直节点（这个节点的层数正好等于高度值），之后插入到跳跃表的多条链表中去。假设height=randomHeight（p），这里需要分两种情况讨论：
·如果height大于跳跃表的高度，那么跳跃表的高度被提升为height，同时需要更新头部节点和尾部节点的指针指向。
·如果height小于等于跳跃表的高度，那么需要更新待插入元素前驱和后继的指针指向。图2-4 在跳跃表中插入元素48的流程4.删除
删除操作和插入操作有点类似，请读者思考如何实现删除操作。5.复杂度分析
这里，我们一起来评估跳跃表的时间和空间复杂度。k-1
性质1 一个节点落在第k层的概率为p。
这条性质比较简单，如果randomHeight（p）函数返回的高度为k，那么必须要求前面（k-1）个随机数都小于p，（k-1）个概率为p的k-1独立事件概率相乘，因此高度为k的概率为p。
性质2 一个最底层链表有n个元素的跳跃表，总共元素个数为，其中k为跳跃表的高度。k-1
由于性质1，一个元素落在第k层概率为p，则第k层插入的元k-1素个数为n×p，所有k相加得到上述公式。当时，上述公式小于O（2n），所以空间复杂度为O（n）。
性质3 跳跃表的高度为O（logn）。
考虑第层，落在这层的期望节点数为，当n较大时，该层节点数为0，所以层数在这个数据级上。
性质4 跳跃表的查询时间复杂度为O（logN）。
查询时间复杂度关键取决于从最左上角到达最底层走过的横向步数和纵向步数之和。我们反过来考虑这个过程，也就是从最底层达到最左上角s走过的期望步数（包括横向步数）。对第k层第j列节点来说，它只可能从以下两种情况跳过来：
·第k-1层第j列节点往上走，跳到第k层第j列节点。根据randomHeight（p）函数定义，往上走的概率为p。
·第k层第j+1列节点往左走，跳到第k层第j列节点。这种情况，第k层第j+1列节点已经是垂直节点的最高点，也就是说，这个节点已经不能往上走，只能往左走。根据randomHeight（p）函数定义，往左走的概率为（1-p）。
设C为往上跳k层的期望步数（包括纵向步数和横向步数），那k么有：
C=0；0
C=（1-p）×（1+C）+p×（1+C）；kkk-1
根据递推式，推出：
由于高度k为O（logN）级别，所以，查询走过的期望步数也为O（logN）。
步数递推公式如图2-5所示。图2-5 期望步数递推公式
性质5 跳跃表的插入/删除时间复杂度为O（logN）。
由插入/删除的实现可以看出，插入/删除的时间复杂度和查询时间复杂度相等，故性质5成立。
因此，跳跃表的查找、删除、插入的复杂度都是O（logN）。2.2 LSM树
LSM树本质上和B+树一样，是一种磁盘数据的索引结构。但和B+树不同的是，LSM树的索引对写入请求更友好。因为无论是何种写入请求，LSM树都会将写入操作处理为一次顺序写，而HDFS擅长的正是顺序写（且HDFS不支持随机写），因此基于HDFS实现的HBase采用LSM树作为索引是一种很合适的选择。
LSM树的索引一般由两部分组成，一部分是内存部分，一部分是磁盘部分。内存部分一般采用跳跃表来维护一个有序的KeyValue集合。磁盘部分一般由多个内部KeyValue有序的文件组成。1.KeyValue存储格式
一般来说，LSM中存储的是多个KeyValue组成的集合，每一个KeyValue一般都会用一个字节数组来表示。这里，首先需要来理解KeyValue这个字节数组的设计。
以HBase为例，这个字节数组串设计如图2-6所示。图2-6 HBase rowkey组成
总体来说，字节数组主要分为以下几个字段。其中Rowkey、Family、Qualifier、Timestamp、
Type这5个字段组成KeyValue中的key部分。
·keyLen：占用4字节，用来存储KeyValue结构中Key所占用的字节长度。
·valueLen：占用4字节，用来存储KeyValue结构中Value所占用的字节长度。
·rowkeyLen：占用2字节，用来存储rowkey占用的字节长度。
·rowkeyBytes：占用rowkeyLen个字节，用来存储rowkey的二进制内容。
·familyLen：占用1字节，用来存储Family占用的字节长度。
·familyBytes：占用familyLen字节，用来存储Family的二进制内容。
·qualifierBytes：占用qualifierLen个字节，用来存储Qualifier的二进制内容。注意，HBase并没有单独分配字节用来存储qualifierLen，因为可以通过keyLen和其他字段的长度计算出qualifierLen。代码如下：qualifierLen = keyLen - 2B - rowkeyLen - 1B - familyLen - 8B - 1B
·timestamp：占用8字节，表示timestamp对应的long值。
试读结束[说明：试读内容隐藏了图片]