1 Introduction

随着互联网技术的发展，尤其是云计算平台的出现，分布式应用程序需要处理大量的数据(PB级)。在一个或多个云计算平台中(成千上万的计算主机)，如何保证数据的有效存储和组织，为应用提供高效和可靠的访问接口，并且保持良好的伸缩性和可扩展性，成为云计算平台需要解决的关键问题之一。分布式并行文件系统，为云计算平台解决了海量数据存储问题，并且提供了统一的文件系统命令空间，如GFS、Hadoop HDFS、KFS等，在此基础上， Hypertable实现了分布式结构化的数据组织，Hypertable可以对海量的结构化的数据(PB级)提供面向表形式的组织方式,并向应用提供类似表访问的接口(如SQL接口)。

2 Structured Data and Tablet Location

2.1 数据模型（Data Model）

Hypertable采用类似表的形式组织数据，但目前Hypertable并不支持关系数据库中丰富的关系属性。Hypertable将数据组织成一个多维稀疏矩阵。该矩阵中的所有行信息可以基于主键（Primary Key）进行排序。在该多维矩阵中第一维称为行（Row），行键值（Row Key）即为Primary Key；第二维即列族（Column Family），一个列族包含多个列（Column Qualifier）的集合，它们一般具有相同的类型属性，系统在存储和访问表时，都是以Column Family为单元组织；第三维即列（Column Qualifier），理论上，一个列族中列的个数不受限制，列的命名方式通常采用family:qualifier的方式；最后一维就是时间戳（Timetstamp），它通常是系统在插入一项数据时自动赋予。如果我们把行和列族看成三维矩阵的行和列，那么我们可以将“时间戳”看成是纵向深度坐标。如图2-1所示，Tn就是每项值（Value）的“深度”标签。

Figure 2-1 A Multi-Dimensional Table

2.1.1 行键（Row Key）

Hypertable中Row Key定义为任意的字符序列（长度不超过64Kbyte，通常的应用也就百个字节左右），所有行以Row key为主键进行字典排序。在Hypertable中队行的操作保持原子性，对行的插入（Insert）、更新（Update）、删除（Delete）等都保持整行的原子操作，无论行操作涉及到的列的个数。在Hypertable中保持行操作的原子性，对应用程序来说显然具有积极的意义，它使得Hypertable对应用程序来说，行的一致性得到保证。

在Hypertable中，所有的行数据按照Row Key的字典序排列，如图2-1，随着数据量的不断增长（不断的有新的数据插入），该多维数据表会不断增长，在一个并行的云计算平台中，当该表增长到一定大小时，系统会将该表一分为二，分别由平台中不同的主机维护，分裂后的表可以独立增长，再进行分裂，由此反复，最终一个多维的Hypertable表实际上是以大量的“小表（Tablet）”的形式存在于云计算平台中，它们具有完全对等的属性，分别维护表中的部分数据；一个小表（Tablet）由一台主机维护，一台主机可以维护多个小表。在Hypertable中，表的分裂沿行区间（Row Range）切分，如图2-2所示，一张表在生长过程中，在一定的行区间被分裂为多个行区间（Row Range），每一个行区间成文一个新的小表（Tablet）。在Hypertable中缺省是一个Tablet增长到200M左右分裂，同时由于系统在并行处理平台上运行，会根据负载均衡原则进行调解。在云计算平台中，分裂出来的Tablet基于Load Balance原则被分布在不同的主机上维护，从而，对表的操作演化成对各小表（Tablet）的操作，处理效率显然高于对整个大表的操作。用户在使用Hypertable时合理的选择Row Key，可以得到更好的数据处理效率。例如在处理大量网页数据时（网页crawler获取的网页数据），通常把网页URL作为Row Key，其中URL的主机域名被反序处理（如maps.google.com/index.html被反置为com.google.maps/index.html），如此具有相同域的网页被尽可能的组织在相同或相邻的Tablet中，因此应用程序在处理这些数据时能得到更好的效率。

Figure 2-2 Tablets Splitting

2.1.2 列族与列（Column Family & Column Qualifier）

Hypertable表的列键（Column Key）被分组为不同的列族（Column Family），列族（Column Family）是Hypertable系统中数据存储和访问控制的基本单元。在一个Column Family中的所有列通常具有相同的类型。在表的生长过程中，新的Column可以被动态创建，在创建Column前，相应的Column Family必须存在。Hypertable系统中，一个表的Column Family个数不大于256，而且一旦Column Family被创建，很少会被修改。

在Hypertable中，Column的个数基本上没有限制。一个Column Key的命名采用 Column Family:Qualifier形式，其中Column Family是可显示字符串，代表该Column所属的Column Family，而Qualifier可以是任意的字符串。如图2-1所示，该表至少包括两个Column Family，其中一个Column Family只有一个Qualifier：“contents”,用于存储网页的内容；另一个Column Family是“anchor”，用于表示该网页被其它网页引用的情况。对于表中的每一行，该Column Family包含有不定数目的列，也即qualifier的个数不定，因此该表在逻辑上会形成一个稀疏矩阵。图中，www.cnn.com 主页被www.cnnsi.com 和 www.my.look.ca 分别用“CNN”和“CNN.com”命名的链接引用。

在Hypertable中，数据的存储以Access Group为单位组织，一个Access Group可以包括一个或多个Column Family。因此数据存储组织的最小单位是Column Family. 在定义Hypertable表的机构时可以定义Access Group包含的Column Family。

2.1.3 时间戳（Timestamp）

如图2-1，在Hypertable的表中，任意的格子（cell）都可以保存不同版本数据，用时间戳进行（timestamp）排序，从而形成表的时间维度。在Hypertable系统中，时间戳是由64-bit整数表示，他们值可以有系统自动赋予，也可以在由客户端应用程序指定。Timestamp在表中以降序排列，最新版本的数据会被最先读取。客户端在操作数据时，必须保证数据在时间序的逻辑性。如，当前数据的Timestamp为T0，新的操作时间戳被指定（客户端或系统指定）T1，则必须保证T1>T0，操作才能被系统接受。

Hypertable在维护数据版本时，不能无限制的维护版本个数，系统提供了两种手段维护有限个数的数据版本（Timestamp），一种是系统设置最多能维护的版本个数，当数据版本超出最大版本数时，系统的数据维护模块会清理版本相对较老的数据；另一种手段是系统动态设置最老版本的时间点，当该参数被更改后，系统数据维护模块会将旧改时间点的数据版本删除。

2.1.4 表的扁平化（Flattening）

在Hypertable中，四维（Row Key、Column Family、Column Qualifier、Timestamp）表最终被扁平化处理成（Key、Value）对的形式存储，其中Key的表示形式为Row Key，Column Family（处理时使用系统编号），Column Qualifier和Timestamp组成的字符串。Value为相应的值。如图2-3所示一个row range的扁平化方式。Row Key保持字典升序排列，Column保持schema定义的顺序，Timetamp保持降序排列。

Figure 2-3 Flattening

2.2 表的寻址和存储

Hypertable主要解决的是数据的组织和存储策略问题，数据的物理存储由分布式并行文件系统完成。分布式并行文件系统作为云计算平台的基础组件，为Hypertable提供统一的文件系统命名空间（namespace）。

在Hypertable中，数据在存储前经过了排序和压缩，表中的数据类型都被串行化为字符数据。一张表，在它的生长过程中，会分裂为许多小表（tablet）,新产生的tablet可以被指定到云计算平台中的任意物理主机维护。在Hypertable系统中维护着一个全局Tablet索引表Metadata Table，Metadata Table本身是一张Hypertable表，它负责保存和维护系统中所有小表（Tablet）的索引。

2.2.1 Tablet索引

在Hypertable中，采用三级层次建立tablet的索引。如前所述，表是按row range分裂为许多的tablet，所有在tablet的集合组成完整的Table。系统中为了维护每张表的tablet位置信息（tablet分布在云计算平台的主机中），会创建一个特殊的表：Metadata table。Metadata表具备一般用户表的属性，也有它的特殊性，根据不同索引级别，分为两类tablet：metadata0 tablet和metadata1 tablet，其中：

Metadata 0的位置信息称为一级索引，通常是一个位置指针存放在系统中，系统初始化时，读取该指针获得metadata0的位置信息；

Metadata 0 tablet作为二级索引，它是一个不会分裂的tablet，运行时，系统在内存中维护它，同时该tablet被定义为metadata表的第一个tablet，在初始化时被创建。Metadata 0中保存Metadata 1 tablets的位置信息；

第三级索引为metadata 1 tablets，这一级的metadata1 tablets具备和用户tablet相同的属性，系统初始化时，会创建第一个metdata1 tablet。Metadata tablet中保存用户表的tablets位置信息。

Figure 2-4 Tablet location hierarchy

Metadata schema的XML文件描述形式为：

<Name>LogDir</Name>

</ColumnFamily>

<Name>Files</Name>

</ColumnFamily>

</AccessGroup>

<Name>StartRow</Name>

</ColumnFamily>

<Name>Location</Name>

</ColumnFamily>

</AccessGroup>

<Name>Event</Name>

</ColumnFamily>

</AccessGroup>

</Schema>

表2-1列出了Metadata的表结构。其中最底下彩色区域就是一行metadata的各项值区域。其中：

l Row key：是table_id:end_row_key表示，table id是表在创建时，系统赋予的唯一表标识号，0号码保留给metadata table用。end_row_key是一个任意字符串，表示该记录指向的tablet的最后一行的row key。

l Access group：metadata table包括三个access group，分别是：default、Location、Logging。

l Column Family：metadata table包含五个column families，分别是：LogDir、Files、Start row、Location、Event。其中Start row记录该行指向的tablet的第一行的row key；Location记录的是该tablet是由云计算平台中哪一台主机维护，以ip:port方式记录。

l “Files” Column Family：该column family下可能包含多个qualifier项，每一项qualifier指示该记录对应tablet（表号为table_id）的一个access group所保存的文件名列表，一个table的access group的个数在table schema中定义，文件名之间用分号隔开。

Table 1: Hypertable metadata table structure

　　在Hypertable中，metadata表的一条记录大小约为1K，如果定一个tablet的大小为128M，那么这样一个三级索引的架构，可以索引的最大Hypertable容量（压缩后）为：(128M/1K)* (128M/1K)*128M，约为2^61bytes。

2.2.2 Tablet存储

Hypertable为用户规划表数据存储提供了一定灵活度，从hypertable的扁平化过程可以看出，它采用面向列的存储模式。Hypertable采用access group方式组织数据存储（在表schema中定义），一个access group包含一个或多个column family。对于一个row range，属于一个access group的所有数据被组织在一起存储，access group是hypertable面向存储的最小访问单位。这样，对于有应用相关性的列，被组织存储在一起，可以有效地提高数据的读写效率。

一个Tablet包含一个表中特定row range的数据，它由系统中一台主机（range server）维护，系统中一台主机可以维护多个表的多个tablet。Tablet在存储前都被扁平化处理，以（key，value）对的形式存储在文件中，实际存储中，（key，value）对中加入了该数据的操作类型，如插入、更新、删除等。Tablet以文件形式存储。如图2-5所示，为一个典型的tablet存储目录结构。