Google三剑客：设计分布式数据存储系统Bigtable

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

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

如何在文件内快速查询？

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

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

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

如何保存一个很大的表？

那如果是一个很大的表，要怎么办呢？

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

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

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

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

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

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

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

内存表过大时怎么办？

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

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

如何避免丢失内存数据？

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

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

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

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

如何读数据？

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

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

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

如何加速读数据？

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

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

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

如何继续加速读数据？

我们刚才还是进行了大量的硬盘遍历，如何继续加速呢？这里要用到一个新的概念：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兆的数据块，结构可以映射上，非常容易管理。

表的逻辑视图是什么？

刚才我们讲的都是物理视图，只能支持，那表的逻辑视图是什么呢？

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

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

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

那这个数据怎么能够映射为一个物理上的存储呢？左边是一个表，右边是一个的数据库，怎么存呢？

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

这样有什么好处呢？假如把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是用的物理结构存储了超大表。在逻辑上行列都可以表达，甚至Column family都能表达，但在物理上就是简单的的存储方式。

吃内存的Bigtable和吃硬盘的GFS从此幸福地在一起了。

参考文献：

Bigtable: A Distributed Storage System for Structured Data

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