Bigtable数据模型和架构

Introduction  简介

Data Model  数据模型

Rows  行

Column Families  列族

Timestamps  时间戳

Bigtable数据模型知识整理

Bigtable架构

---

前言

最近在看Bigtable的论文，其中的数据模型这部分一直没有很好的理解。现在先将论文中的部分原文展示出来，并附上中文翻译。之后是自己对Bigtable数据模型知识的整理。

 

Introduction  简介

In many ways, Bigtable resembles a database: it shares many implementation strategies with databases. Parallel databases and main-memory databases have achieved scalability and high performance, but Bigtable provides a different interface than such systems. Bigtable does not support a full relational data model; instead, it provides clients with a simple data model that supports dynamic control over data layout and format, and allows clients to reason about the locality properties of the data represented in the underlying storage. Data is indexed using row and column names that can be arbitrary strings. Bigtable also treats data as uninterpreted strings,although clients often serialize various forms of structured and semi-structured data into these strings. Clients can control the locality of their data through careful choices in their schemas. Finally, Bigtable schema parameters let clients dynamically control whether to serve data out of memory or from disk.

在很多方面，Bigtable和数据库很类似：它使用了很多数据库的实现策略。并行数据库和内存数据库已经具备可扩展性和很高的性能，但是Bigtable提供了一个和这些系统完全不同的接口。Bigtable不支持完整的关系数据模型；与之相反，Bigtable为客户提供了简单的数据模型，利用这个模型，客户可以动态控制数据的分布和格式，用户也可以自己推测底层存储数据的位置相关性。数据的下标是行和列的名字，名字可以是任意的字符串。Bigtable将存储的数据都视为字符串，但是Bigtable本身不去解析这些字符串，客户程序通常会在把各种结构化或者半结构化的数据串行化到这些字符串里。通过仔细选择数据的模式，客户可以控制数据的位置相关性。最后，可以通过Bigtable的模式参数来控制数据是存放在内存中、还是硬盘上。

 

Data Model  数据模型

A Bigtable is a sparse, distributed, persistent multidimensional sorted map. The map is indexed by a row key, column key, and a timestamp; each value in the map is an uninterpreted array of bytes。(row:string, column:string, time:int64) → string

Bigtable是一个稀疏的、分布式的、持久化存储的多维度排序Map。Map的索引是行关键字、列关键字以及时间戳；Map中的每个value都是一个未经解析的字符串。(row:string, column:string,time:int64)->string

We settled on this data model after examining a variety of potential uses of a Bigtable-like system. As one concrete example that drove some of our design decisions,suppose we want to keep a copy of a large collection of web pages and related information that could be used by many different projects; let us call this particular table the Webtable. In Webtable, we would use URLs as row keys, various aspects of web pages as column names, and store the contents of the web pages in the contents: column under the timestamps when they were fetched, as illustrated in Figure 1.

我们仔细分析了一个类似Bigtable的系统的种种潜在用途之后，决定使用这个数据模型。先举个具体的例子，这个例子促使我们做了很多设计决策；假设我们想要存储海量的网页及相关信息，这些数据可以用于很多不同的项目中，我们称这个特殊的表为Webtable。在Webtable里，我们使用URL作为行关键字，使用网页的某些属性作为列名，网页的内容存在"contents:"列中，并用获取该网页的时间戳作为标识，如图一所示。

Figure 1: A slice of an example table that stores Web pages. The row name is a reversed URL. The contents column family contains the page contents, and the anchor column family contains the text of any anchors that reference the page. CNN’s home page is referenced by both the Sports Illustrated and the MY-look home pages, so the row contains columns named anchor:cnnsi.com and anchor:my.look.ca. Each anchor cell has one version; the contents column has three versions, at timestamps t3, t5, and t6。

图一：Webtable例子中的片断。行名是一个反向URL。contents列族存放的是网页的内容，anchor列族存放引用该网页的锚链接文本。CNN的主页被Sports Illustrater和MY-look的主页引用，因此该行包含了名为"anchor:cnnsi.com"和 "anchor:my.look.ca"的列。每个锚链接只有一个版本（时间戳标识了列的版本，t9和t8分别标识了两个锚链接的版本）；而contents列则有三个版本，分别由时间戳t3，t5，和t6标识。

 

Rows  行

The row keys in a table are arbitrary strings (currently up to 64KB in size, although 10-100 bytes is a typical size for most of our users). Every read or write of data under a single row key is atomic (regardless of the number of different columns being read or written in the row), a design decision that makes it easier for clients to reason about the system’s behavior in the presence of concurrent updates to the same row.

Bigtable maintains data in lexicographic order by row key. The row range for a table is dynamically partitioned.Each row range is called a tablet, which is the unit of distribution and load balancing. As a result, reads of short row ranges are efficient and typically require communication with only a small number of machines. Clients can exploit this property by selecting their row keys so that they get good locality for their data accesses. For example, in Webtable, pages in the same domain are grouped together into contiguous rows by reversing the hostname components of the URLs. For example, we store data for maps.google.com/index.html under the key com.google.maps/index.html. Storing pages from the same domain near each other makes some host and domain analyses more efficient.

表中的行关键字可以是任意的字符串（目前支持最大64KB的字符串，但是对大多数用户，10-100个字节就足够了）。对同一个行关键字的读或者写操作都是原子的（不管读或者写这一行里多少个不同列），这个设计决策能够使用户很容易的理解程序在对同一个行进行并发更新操作时的行为。

Bigtable通过行关键字的字典顺序来组织数据。表中的每个行都可以动态分区。每个分区叫做一个"Tablet"， Tablet是数据分布和负载均衡调整的最小单位。这样做的结果是，当操作只读取行中很少几列的数据时效率很高，通常只需要很少几次机器间的通信即可完成。用户可以通过选择合适的行关键字，在数据访问时有效利用数据的位置相关性，从而更好的利用这个特性。举例来说，在Webtable里，通过反转URL中主机名的方式，可以把同一个域名下的网页聚集起来组织成连续的行。具体来说，我们可以把maps.google.com/index.html的数据存放在关键字com.google.maps/index.html下。把相同的域中的网页存储在连续的区域可以让基于主机和域名的分析更加有效。

 

Column Families  列族

Column keys are grouped into sets called column families, which form the basic unit of access control. All data stored in a column family is usually of the same type (we compress data in the same column family together). A column family must be created before data can be stored under any column key in that family; after a family has been created, any column key within the family can be used. It is our intent that the number of distinct column families in a table be small (in the hundreds at most), and that families rarely change during operation. In contrast,a table may have an unbounded number of columns.

A column key is named using the following syntax:family:qualifier. Column family names must be printable, but qualifiers may be arbitrary strings. An example column family for the Webtable is language, which stores the language in which a web page was written. We use only one column key in the language family, and it stores each web page’s language ID. Another useful column family for this table is anchor; each column key in this family represents a single anchor, as shown in Figure 1. The qualifier is the name of the referring site; the cell contents is the link text.

Access control and both disk and memory accounting are performed at the column-family level. In our Webtable example, these controls allow us to manage several different types of applications: some that add new base data, some that read the base data and create derived column families, and some that are only allowed to view existing data (and possibly not even to view all of the existing families for privacy reasons).

列关键字组成的集合叫做"列族"，列族是访问控制的基本单位。存放在同一列族下的所有数据通常都属于同一个类型（我们可以把同一个列族下的数据压缩在一起）。列族在使用之前必须先创建，然后才能在列族中的任何一列关键字下存放数据；列族创建后，其中的任何一个列关键字下都可以存放数据。根据我们的设计意图，一张表中的列族不能太多（最多几百个），并且列族在运行期间很少改变。与之相对应的，一张表可以有无限多个列。

列关键字的命名语法如下：列族：限定词。 列族的名字必须是可打印的字符串，而限定词的名字可以是任意的字符串。比如，Webtable有个列族language，language列族用来存放撰写网页的语言。我们在language列族中只使用一个列关键字，用来存放每个网页的语言标识ID。Webtable中另一个有用的列族是anchor；这个列族的每一个列关键字代表一个锚链接，如图一所示。Anchor列族的限定词是引用该网页的站点名；Anchor列族每列的数据项存放的是链接文本。

访问控制、磁盘和内存的使用统计都是在列族层面进行的。在我们的Webtable的例子中，上述的控制权限能帮助我们管理不同类型的应用：我们允许一些应用可以添加新的基本数据、一些应用可以读取基本数据并创建继承的列族、一些应用则只允许浏览数据（甚至可能因为隐私的原因不能浏览所有数据）。

 

Timestamps  时间戳

Each cell in a Bigtable can contain multiple versions of the same data; these versions are indexed by timestamp.Bigtable timestamps are 64-bit integers. They can be assigned by Bigtable, in which case they represent "real time" in microseconds, or be explicitly assigned by client applications. Applications that need to avoid collisions must generate unique timestamps themselves. Different versions of a cell are stored in decreasing timestamp order, so that the most recent versions can be read first.

To make the management of versioned data less onerous, we support two per-column-family settings that tell Bigtable to garbage-collect cell versions automatically.The client can specify either that only the last n versions of a cell be kept, or that only new-enough versions be kept (e.g., only keep values that were written in the last seven days).

In our Webtable example, we set the timestamps of the crawled pages stored in the contents: column to the times at which these page versions were actually crawled. The garbage-collection mechanism described above lets us keep only the most recent three versions of every page.

在Bigtable中，表的每一个数据项都可以包含同一份数据的不同版本；不同版本的数据通过时间戳来索引。Bigtable时间戳的类型是64位整型。Bigtable可以用精确到毫秒的"实时"时间给时间戳赋值；用户程序也可以给时间戳赋值。如果应用程序需要避免数据版本冲突，那么它必须自己生成具有唯一性的时间戳。数据项中，不同版本的数据按照时间戳倒序排序，即最新的数据排在最前面。

为了减轻多个版本数据的管理负担，我们对每一个列族配有两个设置参数，Bigtable通过这两个参数可以对废弃版本的数据自动进行垃圾收集。用户可以指定只保存最后n个版本的数据，或者只保存“足够新”的版本的数据（比如，只保存最近7天的内容写入的数据）。

在Webtable的例子里，contents:列存储的时间戳信息是网络爬虫抓取一个页面的时间。上面提及的垃圾收集机制可以让我们只保留最近三个版本的网页数据。

 

Bigtable数据模型知识整理

Bigtable不是关系型数据库，但是却沿用了很多关系型数据库的术语，像table（表）、row（行）、column（列）等。Bigtable用于存储关系较为复杂的半结构化数据。数据大致可以分为以下三类：

非结构化数据：包括所有格式的办公文档、文本、图片、图像、音频和视频信息等。

结构化数据：一般存储在关系数据库中，可以用二维关系表结构来表示。结构化数据的模式(Schema，包括属性、数据类型以及数据之间的联系)和内容是分开的，数据的模式需要预先定义。

半结构化数据：介于非结构化数据和结构化数据之间，HTML文档就属于半结构化数据。它一般是自描述的，与结构化数据最大的区别在于，半结构化数据的模式结构和内容混在一起，没有明显的区分，也不需要预先定义数据的模式结构。

本质上说，Bigtable是一个键值（key-value）映射。按作者的说法，Bigtable是一个稀疏的，分布式的，持久化的，多维的排序映射。Bigtable的键有三维，分别是行键（row key）、列键（column key）和时间戳（timestamp），行键和列键都是字节串，时间戳是64位整型；而值是一个字节串。

与二维关系表结构不同的是，Bigtable的键是三维的。二维表就像日常生活中遇到的普通表格或数据库中的表格，根据行列就能找到信息，而且行列唯一确定一条信息。三维结构更像图书馆里的一个书架，行列可以确定书架上的一个空间(图书馆的书架上相邻空间放的都是一类书，由上文可知，在Bigtable里，"类似的"数据也是放的很近的)，而不能唯一的确定某一本书。时间戳给用户介绍了这些书的"顺序"，用户可以根据顺序拿到自己想要的那本书。例如，图一的t5就可以理解成从左至右第5本书。

行键可以是任意字节串，行的读写都是原子性的。Bigtable按照行键的字典序存储数据。Bigtable的表会根据行键自动划分为片（tablet），片是负载均衡的单元。最初表都只有一个片，但随着表不断增大，片会自动分裂，片的大小控制在100-200MB。Bigtable将多个列组织成列族，这样，列名由两个部分组成：(column family，qualifier)。列族是Bigtable中访问控制的基本单元，也就是说，访问权限的设置是在列族这一级别上进行的。Bigtable中的列族在创建表格的时候需要预先定义好，个数也不允许过多；然而，每个列族包含哪些qualifier是不需要预先定义的。

在看Bigtable相关的知识时，最先让我感到奇怪的就是Bigtable三维结构的键。因为我们一般使用的Map存储一维的数据，就算是数据库里的表也只有二维而已。这种多维的结构让我想起了操作系统中的多级页表(建立索引，优点是不用占据内存太多空间，也能管理足够多的数据，也不用盲目地顺序查找页表项)。

由Bigtable的定义可知，它的行、列和时间戳都是索引。行是表的第一级索引，可以把该行的列、时间戳和value看成一个整体(结构1)，简化为一维键值映射，类似于：

table{
       "11111" : {结构1},//行1
       "aaaaa" : {结构1},//行2
       "bbbbb" : {结构1},//行3
       "asdaa" : {结构1},//行4
       "zzzzz" : {结构1} //行5
}

 

列是第二级索引，每行拥有的列是不受限制的，可以随时增加减少。特点：一个列族里的列一般存储相同类型的数据。一行的列族很少变化，但是列族里的列可以随意添加删除。列键按照family:qualifier格式命名。这次将列拿出来，将时间和value看成一个整体(结构2)，简化为二维键值映射，类似于：

table{
          // ...
          "aaaaa" : {       //行1
          "A:foo" : {结构2},//列1，列族名为A，列名是foo
          "A:bar" : {结构2},//列2，列族名为A，列名是bar
          "B:"    : {结构2} //列3，列族名为B，但列名是空字串
          }，
 
          "bbbbb" : {       //行2
          "A:foo" : {结构2},//列1，列族名为A，列名是foo
          "B:asd" : {结构2} //列2，列族名为B，列名是asd
          }，
          // ...
}

 

时间戳是第三级索引。Bigtable允许保存数据的多个版本，版本区分的依据就是时间戳。数据的不同版本按照时间戳降序存储，因此先读到的是最新版本的数据。加入时间戳后，就得到了Bigtable的完整数据模型，类似于：

table{
         // ...
         "aaaaa" : { //行
                           "A:foo" : { //列1
                                          6 : "y",    //版本1
                                          5 : "m"     //版本2
                           },
                           "A:bar" : { //列2
                                         15 : "d",    //版本1
                           },
                           "B:"  :   { //列3
                                         12 : "w"，   //版本1
                                         10 : "o"，   //版本2
                                          9 : "w"     //版本3
                          }
          },
         // ...
}

查询时，如果只给出行列，那么返回的是最新版本的数据；如果给出了行列时间戳，那么返回的是时间小于或等于时间戳的数据。比如，我们查询 "aaaaa"/"A:foo"/6，返回的值是 "y"；查询 "aaaaa"/"A:foo"/5，返回的结果就是 "m"；查询 "aaaaa"/"A:foo"/2，返回的结果是空。图 1 中 "contents:" 列下保存了网页的三个版本，我们可以用 ("com.cnn.www", "contents:", t5) 来找到 CNN 主页在 t5 时刻的内容。

 

Bigtable架构

Bigtable 构建在 GFS 之上，为文件系统增加了一层分布式索引层。另外，Bigtable 依赖 Google 的 Chubby (分布式锁服务)进行服务器选举及全局信息维护。

如图，Bigtable 将大表划分为大小在 100-200MB 的子表(tablet)，每个子表对应一个连续的数据范围。Bigtable 主要由三个部分组成：客户端程序库(Client)、一个主控服务器(Master)和多个子表服务器(Tablet Server)。

客户端程序库(Client)：提供 Bigtable 到应用程序的接口，应用程序通过客户端程序库对表格的数据单元进行增、删、查、改等操作。客户端通过 Chubby 锁服务获取一些控制信息，但所有表格的数据内容都在客户端与子表服务器之间直接传送；

主控服务器(Master)：管理所有的子表服务器，包括分配子表给子表服务器，指导子表服务器实现子表的合并，接受来自子表服务器的子表分裂消息，监控子表服务器，在子表服务器之间进行负载均衡并实现子表服务器的故障恢复等。

子表服务器(Tablet Server)：实现子表的装载/卸出、表格内容的读和写，子表的合并和分裂。Table Server 服务的数据包括操作日志以及每个子表上的 Sstable 数据，这些数据存储在底层的 GFS 中。

Bigtable 依赖于 Chubby 锁服务完成如下功能：

(1) 选取并保证同一时间内只有一个主控服务器；

(2) 存储 Bigtable 系统引导信息；

(3) 用于配合主控服务器发现子表服务器加入和下线；

(4) 获取 Bigtable 表格的 schema 信息及访问控制信息。

Chubby 是一个分布式锁服务，底层的核心算法为 Paxos。Paxos 算法的实现过程需要一个 "多数派" 就某个值达成一致，进而才能得到一个分布式一致性状态。也就是说，只要一半以上的节点不发生故障，Chubby 就能够正常提供服务。Chubby 服务部署在多个数据中心，典型的部署为两地三数据中心五副本，同城的两个数据中心分别部署两个副本，异地的数据中心部署一个副本，任何一个数据中心整体发生故障都不影响正常服务。

Bigtable 包含三种类型的表格：用户表、元数据表和根表。其中，用户表存储用户实际数据；元数据表存储用户表的元数据；如子表位置信息、Sstable 及操作日志文件编号、日志回放点等，根表用来存储元数据表的元数据；根表的元数据，也就是根表的位置信息，又称为 Bigtable 引导信息，存放在 Chubby 系统中。客户端、主控服务器以及子表服务器执行过程中都需要依赖 Chubby 服务，如果 Chubby 发生故障，Bigtable 系统整体不可用。

 

参考：

《大规模分布式存储系统》

Bigtable论文：A Distributed Storage System for Structured Data

Bigtable论文翻译：https://blog.csdn.net/qq_38289815/article/details/89959074