BigTable是google的一个keyvalue store，和dynamo很像。区别是支持范围查询，而dynamo只是纯hash，所以不能范围查。

数据模型

(row:string, column:string, time:int64) -> string。key由行、列和时间戳构成。对于行的读写是原子性的。列组成了列族，一个列族可以有多个列。

Bigtable 使用GFS存储文件和日志，这些系统往往运行在同一个集群上。

SSTable

类似于B+树的一种可以支持范围查询的Map结构。

Chubby

锁服务，是一个副本状态机，用paxos确保一致性。提供了一个命名空间，包含了目录和小文件，用来充当锁。

介绍

Master服务器、多个tablet服务器。每个tablet大小在100-200MB。如下图所示，是一个类似于B+树或者内存page的管理方式，是一个多层结构。两个metadata就够了。因为一层可以有2^17个表项。

客户端直接通过可以chubby服务器或者metadata 服务器进行通信，本身也会缓存tablet信息。因此没有缓存会有3次读才能确定tablet位置；更坏的情况缓存过期，他会自底向上依次查询，会有6次网络访问；最好情况自己直接有缓存。

tablet的分配

分配是由master来分配的；tablet服务器启动的时候，会在chubby中产生一个唯一命名的文件，并获得该文件的锁；master通过监控该锁是否释放来判断tablet服务器是否宕机了。如果master发现tablet丢失了锁，会试图通讯tablet服务器；如果还失败，说明真宕机了。就会删除该文件，确保tablet服务器不会再提供服务了；同时启动另外一个tablet服务器来替代它。

如果是master自己跪了，就会退出重启。master也有一个文件，用来控制只有一个master能成功运行。

tablet服务

写操作：直接在GFS刷redo log；同时把修改添加到内存的memtable中。
读： 对memtable和sstable进行合并，读取数据。

tablet压缩

前面说的redo log，当大到一定程度，会把memtable变成一个sstable，刷到GFS中。而sstable也会越来越多；后面会有merge的过程，把多个sstable和memtable合成一个sstable。
几个概念：

1. minor compaction
2. merging compaction
3. major compaction