欢迎回看本文原始视频

 

我们上一篇讲了Google三剑客的第一篇:Google File System。今天我们来解读第二篇:Bigtable: A Distributed Storage System for Structured Data。建议大家先看看上一篇Google File System,这样有助于深刻理解今天的Bigtable。

 

 

我们首先回顾一下架构的层次:最底层是文件,再上层是数据模型,再上层是算法,再上层是应用。今天我们讲的Bigtable是一个数据模型。

 

 

如何在文件内快速查询?

上篇我们已经讲到了文件,那如果我们要在文件里快速查询该怎么做呢?

 

 

方法的核心就是,对文件内的很多数据,我们需要找到他的一个Key,然后按照这个Key排序。比如,上图左边可以拿第一列作为Key,然后进行排序。这时你就可以用很多查找方式,比如可以进行Binary search,找到一个起点,之后继续遍历就可以进行范围查找,这就是点射和扫射的概念。

因此,关键点在于,左边是个文件,右边是个表。表就是一系列排好序的<key, value>串。这也是我们经常在NoSQL里面碰到的一个概念。

 

如何保存一个很大的表?

那如果是一个很大的表,要怎么办呢?

 

 

结合上一篇我们讲的方法,我们可以把一个大表拆成很多小表,这样每个小表的内部是一些排好序的<key, value>串。而我们可以用Metadata,也就是元数据的方法保存每个小表的存储位置。这样就相当于大表拆成了很多小表,小表是排序的关键词。

那如何保存一个更大的超大表呢?

 

 

方法就是把我们的表再拆一层,大表变成小表,小表变成小小表。这样就能保证一定能存储下这些很大的表。

我们已经有表了,如何向其中写数据呢?

 

 

最基本的方法就是:比如我们有一个Key是b,数据是yeah的数据,而在整个系统架构中,有内存和硬盘两个部分,硬盘也可以认为是底层GFS。我们在内存里可以存放每个小表的小小表的位置。所以内存里有小表的索引,而硬盘(即GFS)上有小小表的两个表。

为了加快速度,我们其实并不是一开始写就立刻往硬盘上写的,因为这样速度太慢,实际上我们会在内存中建一个表。

在内存中建表还有一个好处,每次写到硬盘上的小表和小小表都是排过序的,而我们不断修改这个排序是很难的,而我们在内存中排序很简单,因为它是随机存储的,性能是非常好的。因此关键点是,通过向内存表写来进行加速,一个小表就变成了一个内存表(临时写的)和很多小小表。

内存表过大时怎么办?

内存表不可能无限地写下去,当内存表过大时怎么办呢?

 

 

大家回忆上一篇文章可以知道,硬盘中的一个块其实是64兆,所以一个表一般也就是64兆。内存表写到64兆的时候,我们往往会把它存到我们的硬盘上。也就是说,我们会把内存表,重新写成一个新的小小表,进行持久性保存,也就是将内存表导入硬盘。

如何避免丢失内存数据?

在这个过程中,实际上还是会丢失数据的。因为你在写入硬盘之前,内存表可能就挂掉了。所以我们还需要一种最传统的方法,就是Log。

 

 

当我们添加<b, yeah>的时候,我们首先在硬盘上写下一个添加<b, yeah>的Log。这样再在内存中写就不会发生丢失数据的情况。大家可能会问,为什么这个时候往硬盘写不会减速呢?

肯定会减速,但这往往是一个顺序的存储方式,所以系统会很快。而且可能不是在本地,而在远程,所以不会有太大影响。

因此现在我们的一个小表,就变成了一个内存表、一些小小表以及一个Log,他们一起构成了一个小表的数据。

如何读数据?

现在我们的数据写到小表和硬盘里了,那如何读数据呢?

 

比如我们现在要查找b,那就需要在所有的表里找。因为在每个小小表内部是有序的,而在小小表之间是无序的,所以我们需要找到每一个表,在里面进行线性查找,直到找到它的位置,当然也可以进行Binary查找。总之,内存里可以很快查到,但是在硬盘上就会需要用各种遍历,性能是非常慢的,直到找到才会返回来。

总结一下,之前的写策略导致小小表的内部是有序的,但小小表之间是无序的,所以每次查找需要查找所有的小小表和内存表,性能是很差的。而且在硬盘中还需要用各种遍历或二叉查找的方式来找,是非常慢的。

如何加速读数据?

 

最好的方法就是建立索引。实际上,我们在写入每个小小表的时候,它往往是固化在那里的。所以我们可以固化一个索引在这里,然后这些索引可以预先加载到内存里,每次查找的时候这个索引就会告诉我们,b在硬盘上的哪个位置,这样可以减少我们遍历的次数和时间,所以性能更优。

大家可以看到这里的一个小小表就拆成了很多很多的数据块,每个块后面会放一个索引的结构,来进行保存。

这里的关键点就是,小小表变成很多的<key, value>,并加了一个索引。索引会预先加载到内存里进行加速,快速找到硬盘的位置。

如何继续加速读数据?

 

我们刚才还是进行了大量的硬盘遍历,如何继续加速呢?这里要用到一个新的概念:Bloomfilter。Bloomfilter是一个很好的架构,它是一个数据结构,能够以很少的空间和很大的正确率告诉我们一个东西在不在里面。所以每次我们找之前,可以先通过Bloomfilter过滤一下,那些肯定不在的数据就不用管,只有那些可能在的数据,才会去遍历,最后找到它。所以这样可以进一步加速整个过程。

总结一下,也就是小小表变成了数据块、索引和Bloomfilter。Bloomfilter会加载到内存中,通过Bloomfilter来预先判断我们找的数据是否存在其中。

如何构建Bloomfilter?

 

 

简单来说,它是一个0,1的Binary串,每当有一个关键词Key过来时,它会通过多个哈希的方式,把Key映射到串上的位置,映射到的位置会标注为1。如果要存两个,第二个单词也会映射到串上的位置,然后标注为1,最终标注成一个0和1的串。

那怎么查找呢?

比如查找“foo”,我们还是用同样的哈希方法,因为以前存过,所以一定会在同样的位置上找到1的,它就一定是存在的。

 

 

那怎么找“cat”这个单词呢?它通过哈希,可能有一个撞上了,是1,但另外一个很可能没有撞上,就是0,只要有一个是no,就一定不在里面。所以Bloomfilter会有一定的误判,但误判率很低,是完全可以接受的,并且它的加速效果非常好。

如何将表存入GFS?

 

 

我们首先来看,上层是在Bigtable的Server。Bigtable用的是内存的结构,而GFS用的是硬盘的结构,他们俩反而能够愉快的在一起,因为一个是内存,一个是硬盘。在内存中会有各种小表,这个小表会存在硬盘上,那在硬盘上存什么数据呢?

其实它会将它的小小表全部存到硬盘上,也会将Log存在硬盘上。所以它其实在本地存的都是各种各样的小小表,以及Log,每个存三份,这是我们之前讲过的备份策略。

因此,Bigtable就能和GFS愉快地在一起,他们都是64兆的数据块,结构可以映射上,非常容易管理。

 

表的逻辑视图是什么?

刚才我们讲的都是物理视图,只能支持<key, value>,那表的逻辑视图是什么呢?

 

 

实际上,在Google的需求里,也需要一个逻辑上很有表达能力的表结构,不然用起来很不方便。

举个例子,比如我们想存一个数据Sangpo,存上Steve Jobs和Tiger这几个人。可以存Steve不同时期的照片,这相当于在搜索引擎里抓取到不同页面的不同版本。还可能存入Steve不同时间的身高,体重,而身高体重可以一起作为一个Column family,它们都是关于body的。

 

如何将逻辑视图转换为物理存储?

 

 

那这个数据怎么能够映射为一个物理上的存储呢?左边是一个表,右边是一个<key, value>的数据库,怎么存呢?

一个简单的方法就是找到一个Key的规则,就是将行、列和时间戳作为Key。我们可以看到,Steve是行,Body和Height是一个Column family,那2011是一个具体的版本号,也就是时间戳,这些放在一起存储成一个值6.2,这就是他的身高。我们可以连续存下去,最后所有数据都存储到里面了。

这样有什么好处呢?如果大家回顾之前我们关于NoSQL的文章(面试高频:SQL vs NoSQL)就会了解,假如把Steve作为一个Key,这样就相当于把数据放在一起,这是NoSQL数据库的一个经典做法,有时可以称之为NoSQL更有效的表达方法。因为他把关于一个东西的数据全都放到一起了,便于快速查找。因此很多NoSQL天然不支持Join操作,这也规避了为什么MySQL里面出现的各种各样的问题。

 

Bigtable的架构是什么?

 

 

首先我们可以用Client进行连接,为了连接它就需要一个Library,相当于提供库函数访问以及各种操作的控制。在连接之前需要获得一些锁服务,还需要获得各种表的元数据。Chubby服务可以提供相关的这些东西。

它获得这个请求的能力以后,就能够去到特定的Tablet Server,即小表的服务器上获得小表的数据。Tablet Server在底层其实是通过GFS来获得数据的,在上面还有一个Master负责处理各个原始信息,以及进行Load balance之间的协调。它能够指定一些Tablet之间的存放,以及调整Load balance,包括多放几个或少放几个,或一些修复的工作。

而底层GFS提供了小小表格,Log的存储方式,并且提供了多种Replicas的方式,保证数据不会丢失,当然还有Cluster scheduling system来监控整个系统服务的过程。

 

总结

  • Bigtable是用<key, value>的物理结构存储了超大表。在逻辑上行列都可以表达,甚至Column family都能表达,但在物理上就是简单的<key, value>的存储方式。
  • 吃内存的Bigtable和吃硬盘的GFS从此幸福地在一起了。

参考文献:

Bigtable: A Distributed Storage System for Structured Data

https://static.googleusercontent.com/media/research.google.com/en//archive/bigtable-osdi06.pdf