Bigtable阶段性总结（版本1）

Bigtable的角色：为大规模的结构化数据提供高效的存储、管理与查询。

Bigtable的针对性：

大规模数据需要大规模集群支持，带来了存储、管理、查询、容错上的复杂性。
关系型数据库在数据规模较大时复杂性迅速上升，效率大幅下降。

Bigtable的特点：

只支持简单的数据模型，所有key和value都是字符串，具体含义由用户自行解释。
运行时可单独为每行调整布局。
根据key排序，且相近的key处于相近的位置，用户可由此推断局部性。
底层存储平台为GFS，无须担心数据的存储问题。用户也可指定将数据存储在内存中。
由Chubby提供分布式环境下的锁机制，对Chubby有依赖性。

Bigtable的逻辑结构：

数据按行key排序，相近的行数据也相近。行中的每个读/写操作都是原子的。
每个table可分为若干个行范围，每个范围称为一个tablet，是数据分布与均衡的单位。
行内的列可分为若干个列族。列族需要在列之前创建，数量不能太多，而列的数量则没有限制。
列的标识符格式为“列族：标识名”。列族也是访问控制、资源统计的单位。
每个列族可单独设定最多保存的版本数或时间长度。
查找时的key可为行或行+列，等等（猜测）。

Bigtable的组织结构：

Bigtable与GFS处于同一集群内，也是单master的结构。
master负责：
1. 给tablet server指定tablet。
2. 追踪所有加入和退出的tablet server。
3. 针对tablet server平衡负载。
4. 进行GFS的垃圾回收。
5. 建立表或列族等改变表模式的操作。
tablet server：
1. 可在运行时动态加入或退出。
2. 负责管理若干tablet，在tablet太大时将其分裂。
client：
1. 读写操作直接与tablet server通信，不经过master。
2. 会缓存tablet的位置信息。

Bigtable的存储结构：

所有tablet的位置信息存储在METADATA表中。查找一个tablet的位置需要通过一个3层的类似B+树的结构：
1. 首层是Chubby中的一个文件，它储存METADATA的第一个tablet即root tablet的位置。
2. root tablet永远不会分裂，以保持3层结构。它保存后面的所有tablet的元信息，如位置、行key范围等（此句不确定，自己的猜测）。
3. METADATA的其它tablet负责保存用户tablet的元数据（位置、范围、日志等）。tablet的位置信息都在内存中。
4. client发起的一次成功的查找需要3次网络通信，而若缓存失效，则最多需要6次（前3次发现缓存失效）。
每个tablet会维持若干个memtable（猜测：每个列族一个memtable），对tablet的读写操作会先反映到memtable上。memtable会在某些条件触发时（猜测：体积或更新次数达到阈值）将内容写入GFS。
tablet在GFS中的基本存储单位是SSTable，它提供一种不可改且排序的key/value映射。每个SSTable由多个排序的block组成，SSTable的最后就是各block的索引，在SSTable打开时索引就在内存中，查找时先在内存中定位到block。
tablet内的各SSTable间为乱序，查找时需要依次查找每个SSTable，因此在SSTable数量达到阈值后要分裂。

master对tablet server的追踪：

每个tablet server都会在Chubby的指定文件夹下持有一个唯一的文件并上锁。在失去锁后，若文件存在，则尝试重上锁；若文件不存在或上锁失败若干次，则放弃对tablet的管理并自杀。tablet server退出前也会释放锁。
在生命期中master会监视Chubby文件夹中的文件。若新增文件，则表明有新tablet server。若master获得了已有文件的锁，说明对应的tablet server错误，则master会删除此文件并将其管理的tablet标记为未分配。
master在运行中也会定期询问tablet server的状态，若无回应若报告失去锁，则视其为错误。

master对tablet的追踪

master在启动后会试图获取Chubby中唯一的master锁。随后master扫描Chubby指定文件夹下的文件，获取当前活跃的tablet server的列表，并询问每个tablet server所管理的tablet列表。
master随后查找root tablet的位置，并将其加入未分配的tablet集合。从root tablet开始，master扫描整个METADATA，并记录所有未分配的tablet。
在tablet server分裂tablet时，tablet server首先修改METADATA，然后通知master。若master丢失此通知，则会在与tablet server通信时发现分裂的tablet（这里不太懂）。

日志：

对tablet的写操作会首先检查操作的完整性，并对比Chubby中有写权限的用户列表来检查合法性，再写入日志。
新的更新会存在memtable中，memtable会定期写入SSTable，其中包含当时日志的指针。
每个tablet server的所有tablet共用一个日志，可以减少产生的文件数，但在恢复时需要的操作比较多。
每个tablet server有两个写日志的线程，同时只有一个活跃，在活跃线程写性能低于阈值时切换为另一个。

tablet数据管理：

memtable的大小达到阈值时会冻结memtable，创建新的memtable，并将旧memtable的内容写入SSTable，称为minor compaction。目的是减少内存使用和恢复数据时需要读取的日志量。
master定期会发起major compaction，即将若干个SSTable和memtable中的有效记录合并为一个SSTable，并丢弃输入的旧SSTable。可以回收资源，还能保证已删除数据的存活时间不会太长。
多个列族可合并成一个局部组，每个局部组会生成单独的SSTable，也可以单独设定为存放在内存中（如METATABLE中的位置信息）。
每个SSTable可以单独指定压缩。常用的是一种两段压缩方案。
tablet server使用了两段cache：scan cache缓存由SSTable接口返回的kv对；block cache缓存由block从GFS中读出的数据。
在tablet中查找时，先通过bloom filter来检查某个SSTable是否可能包含目标数据。
恢复tablet时，tablet server首先读一系统SSTable，再将最后一个SSTable后写入日志的更新依次redo到memtable中。
有tablet server死掉时，它管理的大量tablet都需要恢复。为了避免重复读取日志，master首先将日志进行排序，之后可以顺序读取。排序时在不同的tablet server上并行排序。
有tablet要移到新的tablet server上时，旧tablet server首先对它进行minor compaction，再冻结，在卸载前再进行一次minor compaction，这样移动完成后不需要再读取日志。
因为SSTable中的数据不可变，对它的读取可并行进行，且在tablet分裂时，新的2个tablet共享原有的所有SSTable。

Chubby的职责：

为master提供singlon服务。
为master提供动态的tablet server状态追踪。
为tablet位置的查询提供唯一的入口。
存储每个tablet的模式信息。
存储访问权限列表。