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的技术来允许读写操作并行执行