#Bigtable: A Distributed Storage System for Structured Data
##助教提供的考点
- Data model是什么
- Bigtable的构件（Building Blocks）用了什么？——（GFS、SSTable）提供什么功能？
- Refinement讲了什么
- Bigtable的优点和limitation
##概要（包含考点的解答）
- 关系型数据库遵循ACID规则
- NoSQL，指的是非关系型的数据库。NoSQL有时也称作Not Only SQL的缩写，是对不同于传统的关系型数据库的数据库管理系统的统称。NoSQL用于超大规模数据的存储。（例如谷歌或Facebook每天为他们的用户收集万亿比特的数据）。这些类型的数据存储不需要固定的模式，无需多余操作就可以横向扩展。
- （CAP theorem）: 在计算机科学中, CAP定理（CAP theorem）, 又被称作 布鲁尔定理（Brewer's theorem）, 它指出对于一个分布式计算系统来说，不可能同时满足以下三点:
a) 一致性(Consistency) (所有节点在同一时间具有相同的数据)
b) 可用性(Availability) (保证每个请求不管成功或者失败都有响应)
c) 分隔容忍(Partition tolerance) (系统中任意信息的丢失或失败不会影响系统的继续运作) - CAP理论的核心是：一个分布式系统不可能同时很好的满足一致性，可用性和分区容错性这三个需求，最多只能同时较好的满足两个。因此，根据 CAP 原理将 NoSQL 数据库分成了满足 CA 原则、满足 CP 原则和满足 AP 原则三 大类：
a) CA - 单点集群，满足一致性，可用性的系统，通常在可扩展性上不太强大。 例子：RDBMS
b) CP - 满足一致性，分区容忍必的系统，通常性能不是特别高。 例子：MogoDB、BigTabHBase、Redis
c) AP - 满足可用性，分区容忍性的系统，通常可能对一致性要求低一些。 例子：CouchDB，DynamoDB、Riak - NoSQL的优点/缺点
a) 优点:
高可扩展性、分布式计算、低成本、架构的灵活性、半结构化数据、没有复杂的关系
b) 缺点:
没有标准化、有限的查询功能（到目前为止）、最终一致是不直观的程序
BigTable其实主要说了下面两个事情，其它的东西在助教的问题和课后习题有了，看完课这两点，再看看课后习题和助教的问题即可。
1.Table、Tablet、SStable的关系
这个其实在前面助教的问题里已经回答过了，但为了下面数据模型的理解，还是再简单说一下，Tablet是从Table中若干范围的行组成的一个相当于原Table的子表，所以多个Tablet就能组成一个Tablet.
而SSTable是Tablet在GFS文件系统中的持久化存储的形式，即我们平常说的Tablet，在Bigtable中，是存在一个一个SSTable格式的文件中的。
它们的关系可以由下图来总结：
2.数据模型
Bigtable是一个用于存储稀疏的、分布式的、持久化存储的多维度排序Map，这个Map由行关键字、列关键字以及时间戳作为索引。即：
(row:string, column:string,time:int64)->string
结合下面这张Webtable表的存储形式示意图，关于行、列关键字以及时间戳的说明如下：
2.1 行
表中的行关键字可以是任意的字符串（目前支持最大64KB的字符串，但是对大多数用户，10-100个字节就足够了）。对同一个行关键字的读或者写操作都是原子的（不管读或者写这一行里多少个不同列），这个设计决策能够使用户很容易的理解程序在对同一个行进行并发更新操作时的行为。
Bigtable通过行关键字的字典顺序来组织数据。表中的每个行都可以动态分区。每个分区叫做一个"Tablet"，Tablet是数据分布和负载均衡调整的最小单位。这样做的结果是，当操作只读取行中很少几列的数据时效率很高，通常只需要很少几次机器间的通信即可完成。用户可以通过选择合适的行关键字，在数据访问时有效利用数据的位置相关性，从而更好的利用这个特性。举例来说，在Webtable里，通过反转URL中主机名的方式，可以把同一个域名下的网页聚集起来组织成连续的行。具体来说，我们可以把maps.google.com/index.html的数据存放在关键字com.google.maps/index.html下。把相同的域中的网页存储在连续的区域可以让基于主机和域名的分析更加有效。
2.2 列族
列关键字组成的集合叫做“列族“，列族是访问控制的基本单位。存放在同一列族下的所有数据通常都属于同一个类型（我们可以把同一个列族下的数据压缩在一起）。列族在使用之前必须先创建，然后才能在列族中任何的列关键字下存放数据；列族创建后，其中的任何一个列关键字下都可以存放数据。根据我们的设计意图，一张表中的列族不能太多（最多几百个），并且列族在运行期间很少改变。与之相对应的，一张表可以有无限多个列。列关键字的命名语法如下：列族：限定词。 列族的名字必须是可打印的字符串，而限定词的名字可以是任意的字符串。比如，Webtable有个列族language，language列族用来存放撰写网页的语言。我们在language列族中只使用一个列关键字，用来存放每个网页的语言标识ID。Webtable中另一个有用的列族是anchor；这个列族的每一个列关键字代表一个锚链接，如图一所示。Anchor列族的限定词是引用该网页的站点名；Anchor列族每列的数据项存放的是链接文本。访问控制、磁盘和内存的使用统计都是在列族层面进行的。在我们的Webtable的例子中，上述的控制权限能帮助我们管理不同类型的应用：我们允许一些应用可以添加新的基本数据、一些应用可以读取基本数据并创建继承的列族、一些应用则只允许浏览数据（甚至可能因为隐私的原因不能浏览所有数据）。
2.3 时间戳
在Bigtable中，表的每一个数据项都可以包含同一份数据的不同版本；不同版本的数据通过时间戳来索引。Bigtable时间戳的类型是64位整型。Bigtable可以给时间戳赋值，用来表示精确到毫秒的“实时”时间；用户程序也可以给时间戳赋值。如果应用程序需要避免数据版本冲突，那么它必须自己生成具有唯一性的时间戳。数据项中，不同版本的数据按照时间戳倒序排序，即最新的数据排在最前面。为了减轻多个版本数据的管理负担，我们对每一个列族配有两个设置参数，Bigtable通过这两个参数可以对废弃版本的数据自动进行垃圾收集。用户可以指定只保存最后n个版本的数据，或者只保存“足够新”的版本的数据（比如，只保存最近7天的内容写入的数据）。
在Webtable的举例里，contents:列存储的时间戳信息是网络爬虫抓取一个页面的时间。上面提及的垃圾收集机制可以让我们只保留最近三个版本的网页数据。
Bigtable的Data model是一个稀疏的、分布式的、持久化存储的多维度排序Map。Map由key和value组成：Map的索引key是由行关键字、列关键字以及时间戳组成；Map中的每个value都是一个未经解析的byte数组。即(row:string, column:string,time:int64)->string
- GFS
Bigtable使用Google分布式文件系统(GFS)存储日志和数据文件。(GFS提供Raw storage的功能？) - SSTable
BigTable数据在内部使用SSTable文件格式存储。SSTable提供一个从键（key）到值（value）的持久化的、已排序、不可更改的映射（Map),对SSTable提供了如下操作：查询与一个指定key值相关的value，或者遍历指定key值范围内的所有键值对
从内部看，SSTable是一连串的数据块（通常每个块的大小是64KB，但是这个大小是可以配置的）。SSTable使用块索引（通常存储在SSTable 的最后）来定位数据块；在打开SSTable的时候，索引被加载到内存。一次查找可以通过一次磁盘搜索完成：首先执行二分查找在内存索引里找到合适数据块的位置，然后在从硬盘中读取合适的数据块。也可以选择把整个SSTable都映射到内存中，这样就可以在不用访问硬盘的情况下执行查询搜索了。 - Scheduler
BigTable集群往往运行在一个共享的机器池中，池中的机器还会运行其它各种各样的分布式应用程序，BigTable的进程经常要和其它应用的进程共享机器。BigTable依赖集群管理系统在共享机器上调度作业、管理资源、处理机器的故障、以及监视机器的状态。 - 分布式锁服务Chubby
负责master的选举，保证在任意时间最多只有一个活动的Master；存储BigTable数据的引导程序的位置；发现tablet服务器，以及在Tablet服务器失效时进行善后；存储BigTable的模式信息（每张表的列族信息）；以及存储访问控制列表。
- 局部性群组（Locality groups）
客户程序可以将多个列族组合成一个局部性群族。对每个tablet中的每个局部性群组都会生成一个单独的SSTable。将通常不会一起访问的列族分割成单独的局部性群组使读取操作更高效。此外，可以以局部性群组为单位指定一些有用的调整参数。比如，可以把一个局部性群组设定为全部存储在内存中。设定为存入内存的局部性群组的SSTable依照惰性加载的策略装载进tablet服务器内存。加载完成之后，属于该局部性群组的列族的不用访问硬盘即可读取。 - 压缩
客户程序可以控制一个局部性群组的SSTable是否压缩；用户指定的压缩格式应用到每个SSTable的块中（块的大小由局部性群组的调整参数操纵）。尽管为每个分别压缩浪费了少量空间，我们却受益于在只读取小部分数据SSTable的时候就不必解压整个文件了。许多客户程序使用双步（two-pass）定制压缩模式。第一步采用Bentley and McIlroy’s模式，这种模式横跨一个很大窗口压缩常见的长字符串；第二步采用快速压缩算法，即在一个16KB数据的小窗口中寻找重复数据。在Webtable的例子里，我们使用这种压缩方式来存储网页内容，在空间上达到了10:1的压缩比。 - Bloom过滤器
一个读操作必须读取组成tablet状态的所有SSTable的数据。如果这些SSTable不在内存中，那么就需要多次访问硬盘。我们通过允许客户程序对特定局部性群组的SSTable指定Bloom过滤器，来减少硬盘访问的次数。通过bloom过滤器我们可以查询一个SSTable是否包含了特定行/列对的数据。对于某些应用程序，只使用了少量的tablet服务器内粗来存储Bloom过滤器，却大幅度减少了读操作需要的磁盘访问次数。Bloom过滤器的使用也意味着对不存在的行或列的大多数查询不需要访问硬盘。 - 通过缓存提高读操作的性能
为了提高读操作的性能，tablet服务器使用二级缓存的策略。对tablet服务器代码而言，扫描缓存是第一级缓存，其缓存SSTable接口返回的键值对；Block缓存是二级缓存，其缓存从GFS读取的SSTable块。对于趋向于重复读取相同数据的应用程序来说，扫描缓存非常有效；对于趋向于读取刚读过的数据附近的数据的应用程序来说，Block缓存很有用。 - 提交日志的实现
为了避免重复读取日志文件，我们首先把提交日志的条目按照关键字（table，row name，log sequence number）排序。排序之后，对一个特定tablet的修改操作连续存放，因此，随着一次询盘操作之后的顺序读取，修改操作的读取将更高效。为了并行排序，我们将日志文件分割成64MB的段，之后在不同的tablet服务器对每段进行并行排序。这个排序过程由master来协调，并且当一个tablet服务器指出它需要从一些提交日志文件中回复修改时排序被初始化。为了使修改操作免受GFS瞬时延迟的影响，每个tablet服务器实际上有两个日志写入线程，每个线程写自己的日志文件，并且同一时刻，两个线程只有其中之一是活跃的。如果写入活跃日志文件的效率很低，日志文件写入切换到另外一个线程，在提交日志队列中的修改操作就会由新的活跃日志写入线程写入。日志条目包含序列号，这使得恢复进程可以省略掉由于日志进程切换而造成的重复条目。 - Tablet恢复提速
如果master将一个tablet从一个tablet服务器移到另外一个tablet服务器，源tablet服务器会对这个tablet做一次Minor Compaction。这个Compaction操作减少了tablet服务器日志文件中没有压缩的状态的数目，从而减少了恢复的时间。Compaction完成之后，该tablet服务器停止为该tablet提供服务。在真正卸载tablet之前，tablet服务器还会再做一次Minor Compaction，以消除tablet服务器日志中第一次minor compaction执行过程中产生的未压缩的状态残留。当第二次minor compaction完成以后，tablet就在不需要任何日志条目恢复的情况下被装载到另一个tablet服务器上了。 - 利用不变性
因为SSTable是不变的，所以永久移除已被删除数据的问题就转换成对废弃的SSTable进行垃圾收集的问题了。每个tablet的SSTable都在注册在元数据表中。Master将废弃的SSTable作为对SSTable集合的“标记-清除”的垃圾回收而删除，元数据表则保存了root的集合。最后，SSTable的不变性使得分割tablet的操作非常快捷。与为每个子tablet生成新的SSTable集合相反，我们让子tablet共享父tablet的SSTable。
课后题3
##课后题解答
1、What is the relationship between table , tablet and sstable?
Tablet是从Table中若干范围的行组成的一个相当于原Table的子表，所以一个Table可以有很多的Tablet.
而SSTable则是一个持久化了的，有序且不可变的Map键值对文件形式（这个Map的键和值都是string类型的）。对于Table来说，SSTable是它的子表Tablet在GFS文件系统中的持久化存储的形式，即我们平常说的Tablet在Bigtable中，是存在一个一个SSTable格式的文件中的。
2、Describe what will happen when a read operation or write operation arrives.
这部分主要是针对Tablet服务器的，谷歌的Bigtable的读写请求都是通过Tablet服务器进行响应的。
当一个写操作到达时，Tablet服务器首先要检查这个操作格式是否正确、操作发起者是否有执行这个操作的权限。权限验证的方法是通过从一个Chubby文件里读取出来的具有写权限的操作者列表来进行验证（这个文件几乎一定会存放在Chubby客户缓存里）。成功的修改操作会记录在提交日志里。可以采用批量提交方式来提高包含大量小的修改操作的应用程序的吞吐量。当一个写操作提交后，写的内容插入到memtable里面。
当读操作到达时，Tablet服务器会作类似的完整性和权限检查。一个有效的读操作在一个由一系列SSTable和memtable合并的视图里执行，因为内存表和SSTable中都保存了数据。
3、Describe which applications are BigTable suitable for and not suitable for.
Answer:
由于BigTable针对数据存储进行包括压缩等各方面的优化，以及在事务的一致性上做出了让步，BigTable对于那些需要海量数据存储，高扩展性以及大量的数据处理，但又不要求强一致性的应用是十分适合的，比如Google Earth等。
也因此，对于那些需要强一致性，需要同步更改多行数据的应用来说，BigTable是不合适的。