1.数据模型
2.Bigtable的实现
Bigtable的实现主要包括三哥主要部分：
- 一个链接到每个客户端的库，
- 一个master服务器，
- 许多tablet服务器。
master服务器负责把tablets分配到tablet服务器上，检测tablet服务器的增加和超期，平衡tablet服务器负载，对GFS进行垃圾收集。此外，还能处理模式改变，例如列族的创建和删除。
每一个tablet服务器都管理一组tablets(一般每个tablet服务器上有10-1000个tablets)。tablet服务器处理对该服务器上tablets的读写请求，也能够将特别大的tablets分成几个。
一个Bigtable集群存储了大量的tables。每一个表都由一组tablets构成，每一个tablet包含一个行范围内的数据。初始情况下，每个表仅包含一个tablet。随着表大小的增长，它会自动分裂成多个tablets，默认每个表可以达到1GB。
3.Tablet定位
第一层是存储在Chubby的一个文件，它包含了root tablet的位置。Root tablet将所有tablet的位置包含在一个特殊的METADATA表中。每个METADATA tablet包含一系列的用户tablet位置。Root tablet只是METADATA表的第一个tablet，但是特殊之处在于其永远不会分裂，以此确保tablet位置层级不会超过3层。
在METADATA表中，每个tablet的位置信息都存放在一个行关键字下面，而这个关键字是由tablet所在的表的标示符和它的最后一行编码形成的。每个METADATA行在内存中存储了大约1KB的数据。通过限制tablets的大小为128MB，三层定位方案可以满足定位234个tablets（或者是261字节，按着每个tablet有128MB数据）。
客户端库会缓存tablet位置。如果客户端不知道一个tablet的位置，或者它发现缓存的位置信息不正确，则它会递归查询tablet的位置信息。如果客户端的缓存是空的，定位算法需要3次网络交互更新数据，包括一次Chubby文件的读取。如果客户端缓存过时，则定位算法需要6次网络交互才能更新数据，因为过时的客户端缓存条目只有在没有查到数据的时候才能发现数据过期（假设METADATA tablets移动的不频繁）。尽管tablet的位置信息存在内存中，不需要访问GFS，但是我们会通过客户端库预取tablet位置的方式来减少这种消耗：无论何时读取METADATA表都读取不止一个的METADATA tablets。
我们在METADATA表中还存储了次要的信息，包含与每个tablet有关的所有事件（如：什么时候一个服务器开始为该tablet提供服务）。这些信息对debugging和性能分析很有帮助。
4 Tablet分配
每个tablet只能分配给一个tablet服务器。Master记录了正常运行的tablet服务器、tablet服务器当前的tablet任务和没有被分配的tablet。当一个tablet没有被分配，并且有tablet服务器对于这个tablet有足够的空间可用时，master会通过向这个tablet服务器发送一个tablet载入请求分配这个tablet。
Bigtable使用Chubby跟踪tablet服务器的状态。当一个tablet服务器启动时，它在指定的Chubby目录下创建一个命名唯一的文件并获取一个互斥锁。Master监控这个目录（服务器目录）来检测tablet服务器。如果一个tablet服务器丢失了它的互斥锁，则停止它的tablet服务：例如，由于网络终端，造成了服务器丢失了它的Chubby会话。（Chubby提供了一个高效的机制使tablet服务器在不引入网络流量的情况下，能够检测它是否仍然持有它的锁。）只要文件依然存在，一个tablet服务器试图再次在这个文件上获取一个互斥锁。如果文件不存在了，则tablet服务器将不能再次提供服务，进而会kill掉自己。一个tablet服务器无论何时结束，它都会试图释放它的锁，以使master能够更加快速的重新分配它上面的tablets。
Master负责检测一个tablet服务器何时不能继续为它的tablets服务，并尽快将这些tablets重新分配。Master通过周期性的询问每个tablet服务器的状态来检测一个tablet服务器何时不能继续工作。如果一个tablet服务器报告它失去了它的锁，或者如果master在最近的几次尝试都不能到达一个服务器，则master会尝试获取这个服务器文件的互斥锁。如果master能够获取这个锁，则Chubby运行正常， tablet要么是宕机了，要么就是不能与Chubby正常通信了，因此master通过删除这个tablet服务器的服务器文件来确保这个服务器不能再次进行服务。一旦一个服务器文件被删除，master将之前分配到这个tablet服务器上的所有tablets移动到未被分配的tablets集合里面。为了确保Bigtable集群不易受到master和Chubby之间的网络问题的影响，master将会在它的Chubby会话超时后kill掉自己。然而，如上所说，master失败不会改变tablet服务器上的tablet分布。
当一个master被集群管理系统启动时，它需要在改变tablet分布之前先发现当前的分布。Master在启动时执行下面的步骤。
（1） master从Chubby中抢占一个唯一的master锁，用来阻止其它的master实例化。
（2） master扫描Chubby中的服务器目录，来查找哪些服务器正在运行。
（3） master与每个正常运行的tablet服务器通信，获取每个tablet服务器上tablet的分配信息。
（4） master扫描METADATA表获取所有的tablets的集合。在扫描的过程中，如果遇到一个tablet没有被分配，则将其放入到未被分配的tablets集合中，并可以进行分配。
一种复杂的情况是，在METADATA tablets被分配之前，不能扫描METADATA表。因此在开始扫描之前（第4步），如果在第三步发现root tablet没有分配，则master将root tablet加入到未被分配的tablet集合中。这个附加的操作确保了root tablet将会被分配。因为root tablet包含了所有的METADATA tablets的名字，所以在扫描完root tablet之后，master会得到所有METADATA tablet的名字。
已存在的tablet集合只有在创建或删除表、两个已存在的tablet合并成一个更大的tablet，或者一个已存在的tablet分裂成两个较小的tablet时才会改变。Master会记录所有的这些变化，因为上面几种情况除了最后一个都是它发起的。tablet分裂是比较特殊的，因为它是由tablet服务器发起的。Tablet服务器为METADATA表中记录新tablet的信息提交这次分裂操作。当分裂操作提交后，它会通知master。如果分裂通知丢失（因为tablet服务器或者master宕机），master在询问一个tablet器载入那个分裂的tablet时会检测到新的tablet。
5. Tablet服务
一个tablet的持久状态存储在GFS中，如图5中的描述。更新操作提交到REDO日志中。在这些更新中，最近提交的那些操作存储在一块名为memtable的有序缓存中；较老的更新存放在一系列的SSTable中。为了恢复这个tablet，一个tablet服务器会从METADATA表中读取它的元数据（metadata），这个元数据包含了组成这个tablet的SSTable的列表，以及一系列redo点，这些点指向可能含有该Tablet数据已提交的日志记录。服务器将SSTable的索引读入到内存，并通过执行从redo点开始的所有已提交的更新操作重构memtable。
当一个写操作到达一个tablet服务器时，服务器检查其是否符合语法要求，并验证发送者是否有权限执行这个操作。验证是通过读取一个Chubby文件（这个文件几乎会存在客户端的缓存中）中的可写用户的列表完成的。一个有效的写操作会写入到操作日志中。批处理方式可以提高大量细小操作的吞吐量。在写操作提交后，它的内容被写入到memtable中。
当一个读操作到达一个tablet服务器时，同样会检查是否符合语法要求和本身的权限。一个有效的读操作会在一系列SSTable和memtable合并视图上执行。由于SSTable和memtable是按字典序排序的数据，所以能够高效的生成合并视图。
当tables进行分裂和合并时，进来的读和写操作能够继续执行。
6.合并压缩
随着写操作的执行，memtable的大小会增加。当memtable的大小达到一个门限值时，这个memtable会被冻结，创建一个新的memtable，并将冻结的memtable转换成一个SSTable写入到GFS中。这里的次压缩（minor compaction）过程有两个目标：减少tablet服务器的内存使用，减少操作日志中在恢复tablet服务器时需要读取的数据总量。当压缩发生时，进来的读和写操作能够继续执行。
每次次压缩（minor compaction）都会创建一个新的SSTable。如果这种行为不停的进行下去，则读操作可能需要合并来自任意数量的SSTable的更新。否则，我们通过在后台周期性的执行合并压缩来限制这些文件的数量。一个合并压缩读取一些SSTable和memtable中的内容，并写入到一个新的SSTable中。输入SSTable和memtable可以在压缩完成后立即丢弃。
一个将所有SSTables写入到一个SSTable中的合并压缩称为主压缩（major compaction）。非主压缩产生的SSTable能够包含特定的删除条目，它阻止在仍然活着的旧SSTable中删除数据。另一方面，主压缩产生的SSTable不会包含删除信息或已删除的数据。Bigtable循环扫描所有的tablets，并定期的对它们执行主压缩。这些主压缩可以回收删除数据所使用的资源，并尽快的确保删除的数据在系统内彻底消失，对于存储的敏感数据，这是十分重要的.
二、优化
在前面章节所描述的实现需要一些优化来满足我们用户的高性能、高可用和高可靠性需求。这一章通过对这些实现更加细节的描述来强调这些优化。
局域性群组
客户端能将多个列族聚集成一个局域性群组。对Tablet中每个局域性群组都会产生一个单独的SSTable。将通常不会被一起访问的列族分隔成不同的局域性群组能够提高读取效率。例如，Webtable中的页面元数据（如语言和校验和）作为一个局域性群组，而页面的内容作为另外一个局域性群组：一个想要读取元数据的应用不需要读取所有的页面内容。
此外，可以针对于每个局域性群组设定一些有用的调整参数。例如，一个局域性群组可以声明为存储在内存中。Tablet服务器采用惰性加载的策略对设定为内存中存储的局域性群组的SSTable进行内存加载。一旦加载过，则属于这些局域性群组的列族能够直接被读取，而不需要访问硬盘。这个功能对一些经常访问的小片数据很有用：在内部，我们使用它存放METADATA表中的位置信息列族。
压缩
客户端能够控制作为局域性群组的SSTable是否被压缩，如果压缩，选定什么样的压缩格式。每个SSTable块（它的大小能够通过局域性群组特定的调整参数来控制）都会按着用户指定的格式进行压缩。尽管由于对每个块分开压缩而浪费了一些空间，但是我们能够受益于在不需要解压整个文件的情况下能够访问部分SSTable。许多客户端使用两遍定制的压缩方式。第一遍使用了Bentley和Mcllroy方式，它通过在一个很大的窗口中对常见的长字符串进行压缩；第二遍使用了一种快速压缩算法，它在16KB大小的窗口内查找重复的数据。两种压缩都很快，在当前的机器上，它们压缩速度为100MB-200MB/s，解压速度为400-1000MB/s。
虽然在选择压缩算法时我们更看重速度而不是减少的空间，但是这种两遍的压缩方式对空间上的压缩也出奇的好。例如，在Webtable中，我们使用了这种压缩方式存储web页面内容。在一个实验中，我们在一个局域性群组中存储大量的文档。针对这个实验的目的，我们没有存储文档的所有版本，而是只存了一份，这种方式实现了10:1的空间压缩率。这比对HTML页面的压缩率为3:1或4:1的常用的Gzip压缩更好，原因在于Webtable存放行的方式：一个域名下的所有页面会存储在临近的地方。这使Bentley-Mcllroy算法能够将相同域名下的大量页面的共同部分识别出来。很多应用，不只是Webtable，选择他们行名以至于所有相似的数据聚集到一起，因此实现了很好的压缩率。当我们在Bigtable中存储相同值的多个版本时，压缩率会更好。
读操作的缓存
为了读操作的性能，tablet服务器使用双层缓存。扫描缓存是高层缓存，它缓存了tablet服务器代码使用SSTable接口获取的key-value对；块缓存是底层缓存，它缓存了从GFS上读取的SSTables块。扫描缓存主要用于倾向重复访问相同数据的应用。块缓存主要用于倾向读取近期数据附近数据的应用（如：顺序读取或随机读取同一个局域性群组的一个频繁访问行的不同列）。
Bloom过滤器
如5.3中描述的，一个读操作必须从所有的组成tablet的SSTable中读取数据。如果这些SSTable没有在内存中，则我们最终会多次访问硬盘。我们通过允许客户端对特定局域性群组的SSTable指定Bloom过滤器来降低访问次数。一个Bloom过滤器允许我们查询一个SSTable是否含有特定的行/列对的数据。对于某些特定应用，虽然存储Bloom过滤器占用了tablet服务器少量的内存，但能够彻底的减少读操作对磁盘的查询次数。我们使用Bloom过滤器也可以隐式的达到了当查询的行和列不存在时，不需要访问磁盘。
操作日志实现
如果我们为每个tablet保存一份单独的日志，那么我将会在GFS中并发的写大量的文件。取决于每个GFS服务器的底层系统实现，这些写操作会引起大量的磁盘查找，用来将数据写入到不同的物理日志文件中。此外，由于批操作通常较小，每个tablet分开保存日志文件会影响批操作所带来的优化。针对这些问题，对于每个tablet服务器我们将修改追加到一份操作日志中，不同的tablet修改混合存储在一个物理日志文件中。
在进行一般的操作时，使用一个日志可以提供很好的性能，但是会使恢复复杂化。当一个tablet服务器宕机，其上的tablets会被移动到大量其它的tablet服务器上：每个tablet服务器通常只负载原始tablet服务器上的一小部分tablets。为了恢复一个tablet的状态，新的tablet服务器需要重新执行原始tablet服务器上操作日志中针对这个tablet的修改。然而，这些tablets的修改混合存在同一个物理日志文件中。一种方式是每个新tablet的服务器会读取整个操作日志文件，然后只执行对于需要恢复的tablet的修改。然而，在这种方式下，如果100台机器每个都从失败的tablet服务器上分配了一个tablet，那么日志文件将被读取100次。
我们通过对日志文件条目以key<table, row name, log sequence number>进行排序，来避免这种重复的文件读取。在排序输出中，对于一个指定的tablet的所有修改将会是连续的，并因此能够通过一次硬盘查询和顺序读取进行高效的操作。为了并行排序，我们先将日志文件分成64MB大小的片段，在不同的tablet服务器上对每个片段并行的进行排序。这个排序过程由master协同处理，并在当一个tablet服务器声明它需要从一些操作日志中恢复修改时启动。
向GFS中写日志文件有时会由于各种原因引起性能波动（如：写操作进行时，一个GFS服务器宕机了，或者连接三个GFS副本服务器所在的网络发生拥塞或过载）。为了确保在GFS高负载时修改能够正常进行，每个tablet服务器实际有两个写日志线程，每个线程写自己的日志文件，同一时刻，两个线程中只有一个是工作的。如果一个写日志的线程效率很差，则会切换到另一个线程，修改操作的日志就会写在这个线程下的日志文件中。每个日志记录都有一个序列号，以此使tablet服务器在恢复时忽略掉线程切换所产生的重复的条目。
Tablet恢复提速
如果master将一个tablet从一个tablet服务器移动到另一个服务器，源tablet服务器会在本地先进行一个次压缩。这个压缩通过减少了tablet服务器日志中没有归并的记录的数量来缩短恢复时间。压缩完成后，tablet服务器停止对该tablet的服务。在卸载tablet之前，源服务器还会再做一次次压缩（通常很快），以消除第一次次压缩过程中新进入的未归并到SSTable中的修改。在这次次压缩完成后，tablet能够被载入到另一个tablet服务器上，而无需通过任何的日志条目恢复。
利用不变性
除了SSTable缓存，实际中我们产生的其它部分的SSTable都是不变的，我们可以通过这个事实来简化Bigtable系统。例如，当从SSTable读取数据时，我们不需要对文件系统访问操作进行任何同步。这样，就可以非常高效的实现对行的并行操作。Memtable是唯一一个能被读和写操作同时访问的可变数据结构。为了减少在读操作时的竞争，我们对内存采用了copy-on-write机制，这样就允许读写操作同时进行了。
因为SSTable是不可修改的，所以我们将永久移除要删除的数据问题转换为对废弃的SSTable进行垃圾回收的问题。Tablet的每个SSTable都在METADATA表中注册过。Master通过标记-删除的方式移除SSTable集合中废弃的SSTable，METADATA表中包含了ROOT集合。
最后，SSTable的不可变性使我们能够快速的分裂tablet。我们让子tablet（分裂后的tablet）共享父tablet（分裂前的tablet）的SSTables，而不是为每个子tablet创建新的SSTable集合。
