Big Table
Big table是一个稀疏、分布式、持久化的key/value数据库
它通过rowid、col和timestamp来定位一条记录
(row:string, column:string, time:int64) → string
value是一个没有类型的字节数组
行row key
big table通过row key的字典序来组织数据，数据被分成一个个小的tablet，每个tablet管理自己的row key对应的数据。
当客户端发起一个通过row key的查询，客户端有可能需要先查询row key对应的tablet服务器，然后在这个tablet中查找对应的value
列族
每个table有列，列族是列的组，不同列族的数据被存储在不同的文件。
时间戳
每个value都有一个时间戳，big table可以通过配置仅保留n个最近的记录。
一般来说获取value，会取时间戳最大的一条记录
时间戳可以通过tablet服务器或者客户端来设置。如果通过客户端来设置，有可能会带来设置的时间戳小于最大的时间戳，导致设置无效
组件
SSTable
SSTable是一个持久化、排序的块，存储在GFS上，保存着big table的key/value的数据。SSTable为了加快检索，会在块的结尾保存着一个对块的索引，当发生检索时，先加载索引，判断key是否在块内，如果存在，再加载整个SSTable来查询。
Chubby
类似于Zookeeper的一个高可用、持久化的一致性分布式锁服务。
Chubby使用Paxos算法来保证数据的一致性。
big table使用Chubby实现以下功能：
- 保证集群中只有一个master
- 保存big table数据的bootstrap的位置
- 发现tablet服务器和和宣布tablet服务器死亡
- 存储每个表的列族信息
如果Chubby变得不可用
big table也会变得不可用
实现细节
Master服务
- 分配tablet
- 检测table服务的增加、删除和负载均衡
- GFS文件的垃圾回收
- 处理schema的变化，如表和列族的创建
定位Tablet位置
bt-tabletloc
- chubby存储着root tablet的位置
- root tablet保存着元数据，是一个稀疏索引，每个元素指向另外一个meta data tablet的位置，root tablet不会裂变
- meta tablet存放着某一row key范围的tablet的位置
- 客户端会缓存meta的信息，如果在范围数据时发现不一致，会更新meta数据，再发起操作
Tablet的分配
- 每个Tablet只会分配到一个tablet服务器，tablet服务器会再chubby中创建一个排他锁，master会监听这个排他锁，一旦这个锁的状态发生释放，master会重新分配一个tablet服务器接替死掉的服务器
- master启动的时候也会向chubby申请一个锁，master会扫描Chubby的目录来确定哪些tablet已经分配出去了，再对比元数据，把没有分配出去的tablet进行分配
- 如果tablet启动的时候发现Chubby对应自己的目录已经存在，则会自动退出
- 由于网络原因，tablet服务器进行tablet分裂的时候，暂时没办法通知master。在往后一点的时间，当网络回归正常，tablet服务器会把分割的信息通知master，master会对比元素据，发现不一致会进行元数据的修正
Tablet服务
bt-tabletser
使用LSM的结构来组织数据，并提供服务。
在写入LSM的内存数据时，会同时写入log。一旦机器崩溃，可以使用log来恢复内存中的数据
LRU
tablet中保存着LRU cache，来提高读性能
布隆过滤器
tablet的内存中，保持着每个SSTable的布隆过滤器，可以快速的判断key是否在SSTable中
Copy-on-write
对memtable进行读写时，为了减少读的冲突，使用copy-on-write的技术来允许读写操作并行执行
