2.4 Google网页存储秘诀——BigTable
在前面的章节里提到过分布式系统通常采用key/value的形式存储数据，比如爬虫抓取页面后，页面的存储就是采用key/value形式。针对这一特点，Google在GFS文件系统的基础上，设计了一种名为BigTable的key/value型分布式数据库系统。应用程序通常都不会直接操作GFS文件系统，而是直接操作它的上一级存储结构——BigTable。这正如一般文件系统和关系数据库的道理一样。这一节，我们将详细讲述BigTable的相关知识。
2.4.1 详解BigTable
Bigtable（下文中简称BT）用来存储大规模结构化数据，它最多可以存储250字节，分布在几千个普通的服务器上。Google的很多项目都使用BT存储数据，包括网页查询、Google地图和Google金融。这些应用对BT的要求各不相同：数据大小（从URL到网页到卫星图像）不同，反应速度不同（从后端的大批处理到实时数据服务）。对于不同的项目需求，BT都提供了灵活高效的服务。
设计BT的目标是建立一个可以广泛应用的、高度扩缩的、高可靠性和高可用性的分布式数据库系统。现在，Google已有60多个产品和应用都采用BT作为存储结构。下面我们从几个方面介绍BT。
1. BT与关系数据库
BT在很多地方和关系数据库类似，它采用了许多关系数据库的实现策略。不同的是，BT采用了不同的用户接口。BT不支持完全的关系数据模型，而是为客户提供了简单的数据模型，让客户动态控制数据的分布和格式（就是只存储字符串，格式由客户来解释），这样能大幅度地提高访问速度。数据的下标是行和列的名字，数据本身可以是任意字符串。BT的数据是字符串，没有具体的类型。客户会把各种结构化或者半结构化的数据（比如日期串）序列化成字符串。最后，可以使用配置文件来控制数据是放在内存里还是在硬盘上。
2. BT的逻辑存储结构
BT的本质是一个稀疏的、分布式的、长期存储的、多维度的和排序的Map。Map的key是行关键字（Row）、列关键字（Column）和时间戳（Timestamp）。Value是一个普通的bytes数组。如下所示：
(row:string, column:string,time:int64)->string
图2.11是BT存储网页的底层数据结构示意图（webtable）。其中，每个网页的内容与相关信息作为一行，无论它有多少列。
如图2.11所示，以反转的URL作为Row，列关键字是contents、anchor:my.look.ca和anchor:cnnsi.com，时间戳是t3、t5、t6、t8、t9等。如果要查询t5时间URL为www.cnn.com的页面内容，可以使用{com.cnn.www,contents,t5}作为key去BT中查询相应的value。
图2.11 BT存储示意图
表中的行（Row）可以是任意长度的字符串（目前最多支持64KB，多数情况下10～100字节就足够了）。在同一行下的每一个读写操作都是原子操作（不管读写这一行里的多少个不同列），这使得在对同一行进行并发操作时，用户对系统行为更容易理解和掌控。
BT通过行关键字在字典中的顺序来维护数据。一张表可以动态划分成多个连续“子表”（tablet）。这些“子表”由一些连续行组成，它是数据分布和负载均衡的单位。这使得读取较少的连续行比较有效率，通常只需要少量机器之间的通信即可。用户可以利用这个属性来选择行关键字，从而达到较好的数据访问“局部性”。举例来说，在webtable中，通过反转URL中主机名的方式，可以把同一个域名下的网页组织成连续行。具体而言，可以把站点maps.google.com/index.html的数据存放在关键字com.google.maps/index.html所对应的数据中。这种存放方式可以让基于主机和域名的分析更加有效。
一组列关键字组成了“列族”（column famliy），这是访问控制的基本单位。同一列族下存放的所有数据通常都是同一类型的。“列族”必须先创建，然后才能在其中的“列关键字”下存放数据。“列族”创建后，其中任何一个“列关键字”都可使用。
“列关键字”的语法命名为：列族：限定词。“列族”名必须是看得懂的字符串，而限定词可以是任意字符串。比如，webtable可以有个“列族”叫language，存放撰写网页的语言。我们在language“列族”中只用一个“列关键字”，用来存放网页的语言标识符。该表的另一个有用的“列族”是anchor。“列族”的每一个“列关键字”代表一个锚链接，访问控制、磁盘使用统计和内存使用统计，均可在“列族”这个层面进行。在图2.11的例子中，可以使用这些功能来管理不同应用：有的应用添加新的基本数据，有的读取基本数据并创建引申的“列族”，有的则只能浏览数据（甚至可能因为隐私权的原因不能浏览所有数据）。
BT表中的每一个表项都可以包含同一数据的多个版本，由时间戳来索引。BT的时间戳是64位整型，表示准确到毫秒的“实时”。需要避免冲突的应用程序必须自己产生具有唯一性的时间戳。不同版本的表项内容按时间戳倒序排列，即最新的排在前面。在图2.11中，“contents:”列存放一个网页被抓取的时间戳。
BT使用Google分布式文件系统（GFS）来存储日志和数据文件。一个BT集群通常在一个共享的机器池中工作，池中的机器还运行着其他分布式应用，BT和其他程序共享机器（BT的瓶颈是I/O内存，可以和CPU要求高的程序并存）。BT依赖集群管理系统来安排工作，在共享的机器上管理资源，处理失效机器并监视机器状态。
3. BT内部存储格式——SSTable
BT内部采用SSTable格式存储数据。SSTable提供了一个从关键字到值的映射，关键字和值都可以是任意字符串，如图2.12所示。
图2.12 SSTable示意图
在SSTable格式中，映射是排序的、存储的（不会因为掉电而丢失）、不可更改的，且可以进行如下操作。
● 通过关键字查询相关的值。
● 根据给出的关键字范围遍历所有的关键字和值。
SSTable内部包含一列数据块，通常每个块的大小是64KB，但是大小是可以配置的。SSTable中块索引（index）大小是16位。块索引（存储在SSTable的最后）用来定位数据块。当打开SSTable的时候，块索引被读入内存。每次查找都可以用一次硬盘搜索完成，首先在内存中的索引里进行二分查找，获得数据块的位置，然后根据位置信息直接到硬盘读取数据块。最佳情况是：整个SSTable可以被放在内存里，这样一来就不必访问硬盘了。
4. BT的锁
BT还依赖一个高度可用的分布式数据锁服务（Chubby）。一个Chubby由5个“活跃”的备份构成，其中一个被这些备份选成主备份，并且处理请求。这个服务只有在大多数备份都是“活跃”的并且互相通信的时候才是“活跃”的。当有机器失效的时候，Chubby使用一定的算法来保证备份的一致性。Chubby提供了一个名字空间，里面包括目录和一系列文件。每个目录或者文件可以当成一个锁来用，读写文件操作都是原子操作。Chubby客户端的程序库提供了对Chubby文件的一致性缓存。每个Chubby客户维护一个和Chubby通信的会话。如果客户不能在一定时间内更新自己的会话，会话就失效了。当一个会话失效时，其拥有的锁和打开的文件句柄都失效。Chubby客户可以在文件和目录上登记回调函数，以获得改变或者会话过期的通知。
BT使用锁服务来完成以下几个任务。
● 保证任何时间最多只有一个活跃的主备份。
● 存储BT数据的启动位置。
● 发现“子表”服务器，并处理tablet服务器失效的情况。
● 存储BT数据的“模式”信息（每张表的列信息）。
● 存储访问权限列表。在Chubby中，存储了BT的访问权限，如果Chubby不能访问，那么由于获取不到访问权限，BT也就不能访问。
5. BT的主要组成部件
BT主要由以下三个构件组成。
● 一个客户端的链接库。
● 一个主服务器。
● 许多“子表”服务器。“子表”服务器可以动态地从群组中被添加和删除，以适应流量的改变。
主服务器的作用是给“子表”服务器分配“子表”、探测“子表”服务器的增加和缩减、平衡“子表”服务器负载，以及回收GFS系统中文件的碎片。此外，它还可以创建模式表。
一个“子表”服务器管理许多子表（一般每个“子表”服务器可以管理10～1000个子表）。“子表”服务器处理它所管理的“子表”的读写请求，还可以将那些变得很大的“子表”分割。
像许多单主机的分布式存储系统一样，客户端数据不是通过主服务器来传输的：客户端要读写时直接与“子表”服务器通信。因为BT客户端并不依赖主服务器来请求“子表”本地信息，大多数客户端从不与主服务器通信。因此，实际上主机的负载往往很小。
一个BT群组可以存储大量的表。每一个表有许多“子表”，并且每个“子表”包含一行上所有相关的数据。最初，每个表只包含一个子表。随着表的增长，自动分成了许多的“子表”，每个子表的默认大小为100～200MB。
BT用三层体系的B+树来存储子表的地址信息，如图2.13所示。
图2.13 BT的B+树体系结构
第一层是一个存储在Chubby中的文件，它包含“根子表”（Root tablet）的地址。如图2.13所示，“根子表”包含一些“元数据表”（MetaData tablets）的地址信息。这些“元数据表”包含用户“子表”的地址信息。“根子表”是“元数据表”中的第一个“子表”，但它从不会被分割。
客户端缓存“子表”地址，如果客户端发现缓存的地址信息是错误的，那么它会递归地提升“子表”地址等级。如果客户端缓存是空的，寻址算法需要三个网络往返过程，包括一次从Chubby的读取。如果客户端缓存是过期的，那么寻址算法可能要用6个往返过程。尽管“子表”地址缓存在内存里，不需要GFS访问，但还是可以通过客户端预提取“子表地址”来进一步降低性能损耗。
“子表”一次被分配给一个子表服务器。主服务器跟踪“活跃”的“子表”服务器集合以及当前“子表”对“子表服务器”的分配状况。当一个“子表”还没有被分配，并且有一个“子表”服务器是可用的，这时主机就通过传输一个“子表”装载请求到“子表”服务器来分配“子表”。
BT使用Chubby来跟踪“子表”服务器。当“子表”服务器启动时，它在一个特别的Chubby目录中创建一个文件，并且获得一个互斥锁。主机通过监听这个目录（服务器目录）来发现“子表”服务器，如果“子表”服务器丢失了自己的互斥锁，就会停止为它的“子表”服务。
主机负责探测何时“子表”服务器不再为它的“子表”服务，以便可以尽快地分配那些“子表”。为了达到这个目的，主机会周期性地询问每个“子表”服务器的锁的状态。如果一个“子表”服务器报告它丢失了锁，主机会尝试在服务器的文件中获取一把互斥锁。如果主机能获得这把锁，则表示Chubby是可用的并且“子表”服务器已经失效，因此主机通过删除“子表”服务器的服务文件来确保它不会再工作。一旦服务文件被删除，主机可以把先前分配给这台服务器的所有“子表”移到未分配的“子表”集合中。
“子表”的持久化状态存储在GFS文件里，如图2.14所示。
图2.14 “子表”持久化
每次更新“子表”前都要更新“子表“的重做日志（redo log）。最近更新的内容（已经提交但还没有写入到磁盘的内容）会存放在内存中，称为memtable。之前的更新（已经提交并且固化在磁盘的内容）会被持久化到一系列的SSTable中。
当一个写操作请求过来时，“子表”服务器会先写日志，提交的时候，就把这些更新写入memtable中。之后等系统不繁忙的时候，就写入SSTable中（这个过程和Oracle数据库写操作基本一致）。
如果请求是读操作，则可以根据当前的memtable和SSTable中的内容进行合并，然后对请求返回结果。因为memtable和SSTable有相同的结构，因此，合并是一个非常快的操作。
2.4.2 开源BigTable-HBase
Google提出“云计算”理论之后，很多团队都开始根据这一理论开发自己的云计算存储模型。其中，HBase是一个比较成功的实例。本小节就讲述HBase的相关知识。
HBase是一个Apache开源项目，它的目标是提供一个在Hadoop分布式环境中运行的类似于BT的存储系统。正如Google将BT架设在自己的分布式存储系统GFS中一样，HBase是基于HDFS的。
在HBase中，数据在逻辑上被组织成为表、行和列。客户可以使用类似于iterator的接口来遍历行数据，同时也可以通过行值来获取列值。同一个行对应多个不同版本的列值。
1. 数据模型
HBase使用的数据模型和BT类似。应用程序将数据行存储在“打上标签”的表中。一个数据行包含一个排好序的行键值和任意长度的列值。
列名的格式为“<family>:<label>”，其中<family>与<label>可以为任意的字节数组。表的<family>集合是固定的，如果希望修改表的<family>字段，需要管理员来操作；但可以随时增加<label>，而无需事先声明它。HBase在磁盘上按照<family>储存数据，所以<family>里的所有项应该有相同的读/写方式。
默认每次将一行数据进行锁定，行数据的写入是原子操作，写入时这行数据将被锁定，同时进行读和写操作。
2. 概念模型
从概念上来看，一个表由多个数据行组成，每个数据行中的列不一定有值。表2.2展示了一个来自BigTable的数据。
表2.2 BigTable中的数据
3. 物理存储模型
从概念上看，表数据是按照稀疏的行来存储的，物理上，它们是按照列来存储的。理解这个概念对考虑表的设计和程序设计是非常重要的。
回到先前的那个例子，物理存储结构如表2.3～表2.5所示。
表2.3 物理存储结构（1）
表2.4 物理存储结构（2）
表2.5 物理存储结构（3）
从上面的表中可以看出，空的列并没有被存储，所以当请求列值为"contents:"的时候，会返回空值。
如果请求数据的时候，没有提供时间戳（time stamp）的值，那么请求的数据将返回最新的值（时间戳最近的值），并且在实际的存储中，所有的值都是按照时间戳降序排列的。
4. 行的范围：区域
数据表是由一系列按升序排序的数据行组成的，在同一行中，数据列按名字的升序排列，时间戳按降序排列。物理上，数据表被拆分成由多个数据行组成的区域（这个概念在BT中就是tablet）。区域包含从开始行（包含）到终止行（排除）所有区域构成一个数据表。与BT不同的是，在BT中，数据行区域由表名和结束行值决定，而HBase的区域由表名和开始行值决定。
区域中的每一个“列族”都由一个名为HStore的对象管理，每个HStore由一个或多个MapFiles（Hadoop中的一个文件类型）组成。MapFiles的概念类似于Google的SSTable。MapFiles一旦被关闭，就是不可修改的类型了。MapFiles被存储在Hadoop的HDFS中，其与SSTable的不同之处如下。
● MapFiles目前还无法进行内存的映射。
● MapFiles由一些稀疏的索引文件来维护，而SSTable在其文件的最后。
● HBase扩展了MapFiles，所以使用布隆过滤器的时候可以提高查找的性能。
5. 架构与实现
HBase由以下三个主要构件组成。
（1）HBaseMaster（类似于BT主服务器）
HBaseMaster负责给HRegionServer分配区域。分配的第一个区域就是ROOT区域，它用于定位所有的META区域。一旦所有的META区域被分配好，Master便开始分配用户区域给HReginServer，同时维护每个HReginServer的负载平衡。
HBaseMaster还含有一个指向包含ROOT区域的HReginServer地址。
同时，HBaseMaster会监控每台HReginServer的健康状况，如果某台HReginServer不可用，它将会把不可用的HReginServer替换成其他HReginServer。
另外，HBaseMaster还负责对数据表进行管理，比如让表处于有效（online）或失效（offline）的状态，改变表的结构（增加或者减少列族），等等。
与BT不同的是，如果HBaseMaster失效了，整个集群就会关闭。在BT中，即使主服务器失效了，Tablet服务器依然可以提供服务。而HBase使用单点访问模式，即所有的HReginServer都访问HBaseMaster。
（2）HReginServer（类似于BT tablet服务器）
HReginServer负责处理用户读和写的操作。HReginServer通过与HBaseMaster通信获取需要服务的数据表，并向HBaseMaster反馈自己的运行状况。HReginServer的任务主要包括以下几类。
● 写请求（Write Request）：当一个写的请求到来时，它首先会写到一个称为HLog的日志模块中。HLog被缓存在内存中，称为Memcache，每一个HStore只能有一个Memcache。
● 读请求（Read Request）：当读取的请求到来时，HReginServer会先在Memcache中寻找该数据，找不到时，才会去MapFiles中寻找。
● 刷新缓存（Cache Flushe）：当Memcache到达配置的大小以后，会创建一个MapFile，将其写到磁盘中。这将减少HReginServer的内存压力。
在读和写的过程中，Cache Flushe会经常发生。当创建一个新的MapFile时，读和写的操作会被挂起，直到新的MapFile创建好，并被加入HStore的管理中才可以使用。
● 压缩（Compaction）：当一定数量的MapFiles超过一个配置的阈值之后，压缩操作就开始执行。压缩操作的主要工作就是周期性地将一些MapFiles合并成一个MapFile。
在执行压缩的过程中，HReginServer的读和写操作将被挂起，直到操作执行完毕。
● 区域切分（Region Split）：当一个HStore所管理的MapFiles超过一个配置（当前是256MB）的值以后，将会执行区域的切分操作。区域的切分操作将原先的区域对半分割为两个新的区域。
在进行区域切分的过程中，读和写操作将被挂起，直到完成为止。
（3）HBase客户端（由org.apache.hadoop.hbase.client.HTable定义）
HBase客户端负责寻找提供需求数据的HReginServer。在这个过程中，HBase客户端将首先与HBase主服务器通信，找到ROOT区域。这个操作是客户端和主服务器之间仅有的通信操作。
一旦ROOT区域找到以后，客户端就可以通过扫描ROOT来定位实际提供数据的HReginServer。
当定位到提供数据的HReginServer以后，客户端就可以通过这个HReginServer找到需要的数据了。
这些信息将会被客户端缓存起来，当下次请求的时候，就不需要再走上面的这个流程了。
当这些区域中的某个区域不可用时，客户端将会逆向执行上面的过程，直到找到实际提供数据的HReginServer为止。
接下来简单介绍如何操作HBase。HBase与我们常用数据库的最大差别就是列存储和无数据类型，所有数据都以string类型存储。如果在HBase中存储了5个字段，但实际只有4个字段有值，那么为空的那个字段不占用空间。具体使用请参考下面代码。
/**
* 定义几个常量
*/
public static HBaseConfiguration conf = new HBaseConfiguration();
static HTable table = null;
/**
* 创建HBase table
* @param table
* @throws IOException
*/
public static void creatTable(String tablename) throws IOException {
HBaseAdmin admin = new HBaseAdmin(conf);
if (!admin.tableExists(new Text(tablename))) {
HTableDescriptor tableDesc = new HTableDescriptor(tablename);
tableDesc.addFamily(new HColumnDescriptor("ip:"));
tableDesc.addFamily(new HColumnDescriptor("time:"));
tableDesc.addFamily(new HColumnDescriptor("type:"));
tableDesc.addFamily(new HColumnDescriptor("cookie:"));
//注意这个C列,下面以此列来说明列存储
tableDesc.addFamily(new HColumnDescriptor("c:"));
admin.createTable(tableDesc);
System.out.println("table create ok!!!");
} else {
System.out.println("table Already exists");
}
}
/**
* 录入数据
* @throws Exception
*/
public static void insertData() throws Exception{
//读取日志文件
BufferedReader reader = new BufferedReader(new FileReader("log file name"));
if(table==null)
table = new HTable(conf, new Text(tablename));
String line;
while((line = reader.readLine()) != null){
//这里就不介绍了，先前有说明
LogAccess log = new LogAccess(line);
//这里我使用time+cookie为row关键字，确保不重复，如果cookie记录有重复，
//将区别对待，这里暂不多做说明
String row = createRow(log.getTime(),log.getCookie());
long lockid = table.startUpdate(new Text(row));
if(!log.getIp().equals("") && log.getIp()!=null)
table.put(lockid, new Text("ip:"), log.getIp().getBytes());
if(!log.getTime().equals("") && log.getTime()!=null)
table.put(lockid, new Text("time:"), log.getTime().getBytes());
if(!log.getType().equals("") && log.getType()!=null)
table.put(lockid, new Text("type:"), log.getType().getBytes());
if(!log.getCookie().equals("") && log.getCookie()!=null)
table.put(lockid, new Text("cookie:"), log.getCookie().getBytes());
if(!log.getRegmark().equals("") && log.getRegmark()!=null)
table.put(lockid, new Text("c:_regmark"), log.getRegmark().getBytes());
if(!log.getRegmark2().equals("") && log.getRegmark2()!=null)
table.put(lockid, new Text("c:_regmark2"), log.getRegmark2().getBytes());
if(!log.getSendshow().equals("") && log.getSendshow()!=null)
table.put(lockid, new Text("c:_sendshow"), log.getSendshow().getBytes());
if(!log.getCurrenturl().equals("") && log.getCurrenturl()!=null)
table.put(lockid, new Text("c:_currenturl"), log.getCurrenturl().getBytes());
if(!log.getAgent().equals("") && log.getAgent()!=null)
table.put(lockid, new Text("c:_agent"), log.getAgent().getBytes());
//存入数据
table.commit(lockid);
}
}
本小节是针对HBase的简单介绍，如果想深入了解的话，请参考相关的内容。