bigtable原理

bigtable原理

数据模型

A Bigtable is a sparse, distributed, persistent multi-dimensional sorted map. The map is indexed by a row key, column key, and a timestamp; each value in the map is an uninterpreted arrays of bytes.

Bigtable是稀疏的、分布式的、持久化的、多维度的、顺序的map，我们可以将Bigtable的数据模型抽象为一系列的键值对，满足的映射关系为：key(row:string, column:string, time:int64) -> value(string)。

Bigtable的Key有三维，分别是行键（row key）、列键（column key）和时间戳（timestamp），行键和列键都是字节串，时间戳是64位整型。

为了方便管理，列又被分为多个列族（column family，是访问控制的单元），列键按照family:qualifier格式命名的。

行键、列键和时间戳分别作为table的一级、二级、三级索引，即一个table包含若干个row key，每个row key包含若干个列族，每个列族又包含若干个列，对于具有相同行键和列键的数据（cell），Bigtable会存储这个数据的多个版本，这些版本通过时间戳来区分。

如下图：

该表包含两个行键u1和u2，每个行键又含两个列族User和Social，User列族包含的列键有name、email、phone；Social列族包含的列键有friend、classmate；

(u1, name, v1)->Ricky 表示一个键值对；

(u1, email, v1)->ricky@gmail.com 和 (u1, email, v2)->ricky@yahoo.com 是两个不同的键值对。

综上，传统的map由一系列键值对组成，在Bigtable中，对应的键是由多个数据复合而成的，即row key，column key和timestamp。

最后：

Bigtable按照行键的字典序存储数据，因为系统庞大且为分布式，所以排序这个特性会带来很大的好处，行的空间邻近性可以确保当我们在扫描表时，我们感兴趣的记录会大概率的汇聚到一起。

Tablet是Bigtable分配和负载均衡的单元，Bigtable的表根据行键自动划分为片。最初表都只有一个tablet，但随着表的不断增大，原始的tablet自动分割为多个tablet，片的大小控制在100-200MB。

支撑技术

Bigtable的实现依托于Google的几个基础组件：

Google File System（GFS），一个分布式文件系统，用于存储日志和文件；

Google Sorted Strings Table（SSTable），一个不可修改的有序键值映射表，提供查询、遍历的功能；

Chubby，一个高可靠用于分布式的锁服务，其目的是解决分布式一致性的问题，通过Paxos算法实现。Chubby用于片定位，片服务器的状态监控，访问控制列表存储等任务。注：Chubby并不是开源的，但 Yahoo！借鉴Chubby的设计思想开发了Zookeeper，并将其开源。

bigtable集群

Bigtable集群包括三个主要部分：

供客户端使用的库，客户端需要读写数据时，直接与片服务器联系。因为客户端并不需要从主服务器获取片的位置信息，所以大多数客户端从来不需要访问主服务器，主服务器的负载一般很轻。

主服务器（master server），主服务器负责将片分配给片服务器，监控片服务器的添加和删除，平衡片服务器的负载，处理表和列族的创建等。注意，主服务器不存储任何片，不提供任何数据服务，也不提供片的定位信息。

片服务器（tablet server），每个片服务器负责一定量的片，处理对片的读写请求，以及片的分裂或合并。每个片实际由若干SSTable文件和memtable组成，而且这些SSTable和memtable都是已排序的。片服务器可以根据负载随时添加和删除。这里片服务器并不真实存储数据，而相当于一个连接Bigtable和GFS的代理，客户端的一些数据操作都通过片服务器代理间接访问GFS。

注意，主服务器负责将片分配给片服务器，而具体的数据服务则全权由片服务器负责。但是不要误以为片服务器真的存储了数据（除了内存中memtable的数据），数据的真实位置只有GFS才知道，主服务器将片分配给片服务器的意思应该是，片服务器获取了片的所有SSTable文件名，片服务器通过一些索引机制可以知道所需要的数据在哪个SSTable文件，然后从GFS中读取SSTable文件的数据，这个SSTable文件可能分布在好几台chunkserver上。

当片服务器启动时，它会在Chubby的某个特定目录下创建并获取一个锁文件（互斥锁），这个锁文件的名称是唯一表示该tablet server的。master server通过监控这个目录获取当前存活着的tablet server的信息。

如果tablet server失去了锁（比如网络问题），那么tablet server也就不再为对应的tablet服务了。

如果锁文件存在，那么tablet server会主动获取锁。

如果锁文件不存在，那么tablet server就永远不会再服务对应的tablet了，所以tablet server就会kill自己。

当tablet server要终止时，它会自己释放占有的锁，master server就会把该tablet server上的tablet分配给其它的tablet server。

那么maser server是如何获知tablet server不再服务了呢？master server会定期轮询每个tablet server的锁状态。如果tablet server报告自己失去了已经失去了锁，或者master server不能获取tablet server的状态，那么master server就会尝试去获取tablet server对应的锁文件。如果master server获取到了锁文件，并且Chubby是处于正常工作的状态的，此时master server就确认tablet server已经无法再提供服务了，master server删除相应的锁文件并把tablet server对应的tablet分配给新的tablet server。

如果master server与Chubby之间出现了网络问题，那么master server也会kill自己。但是这并不会影响tablet与tablet server之间的分配关系。

master server的启动需要经历一下几个阶段。

master server需要从Chubby获取锁，这样可以确保在同一时刻只有一个master server在工作。

master server扫描Chubby下特定的目录（即tablet server创建锁文件的目录），获取存活着的tablet server的信息。

master server与存活着的tablet server通信，获取已被分配到tablet server的tablet信息。

master server扫描METADATA tablet，获取所有的tablet信息，然后把未分配的tablet分配给tablet server。

片的定位

前面提到主服务器不提供片的位置信息，那么客户端是如何访问片的呢？Bigtable使用一个类似B+树的数据结构存储片的位置信息。

定位系统：

Chubby file，保存着root tablet的位置。这个Chubby文件属于Chubby服务的一部分，一旦Chubby不可用，就意味着丢失了root tablet的位置，整个Bigtable也就不可用了。

root tablet，root tablet其实是元数据表（METADATA table）的第一个分片，它保存着元数据表其它片的位置。root tablet很特别，为了保证树的深度不变，root tablet从不分裂。

其它的元数据片，它们和root tablet一起组成完整的元数据表。每个元数据片都包含了许多用户片的位置信息。

可以看出整个定位系统其实只是两部分，一个Chubby文件，一个元数据表。每个分片也都是由专门的片服务器负责，这就是不需要主服务器提供位置信息的原因。客户端会缓存片的位置信息，如果在缓存里找不到一个片的位置信息，就需要查找这个三层结构了，包括访问一次Chubby服务，访问两次片服务器。

元数据表

元数据表（METADATA table）是一张特殊的表，它被用于数据的定位以及一些元数据服务，不可谓不重要。

元数据表的行键=片所属表名的id+片最后一行行键而成，所以每个片在元数据表中占据一条记录（一行），而且行键既包含了其所属表的信息也包含了其所拥有的行的范围；

除了知道元数据表的地址部分是常驻内存以外，还可以发现元数据表有一个列族称为location，我们已经知道元数据表每一行代表一个片，那么为什么需要一个列族来存储地址呢？因为每个片都可能由多个SSTable文件组成，列族可以用来存储任意多个SSTable文件的位置。一个合理的假设就是每个SSTable文件的位置信息占据一列，列名为location:filename。当然不一定非得用列键存储完整文件名，更大的可能性是把SSTable文件名存在值里。获取了文件名就可以向GFS索要数据了。

元数据表不止存储位置信息，也就是说列族不止location，这些数据暂时不是咱们关心的。

客户端会缓存tablet的位置信息，客户端在获取tablet的位置信息时，会涉及到两种情况：

如果客户端没有缓存目标tablet的位置信息，那么就会沿着root tablet定位到最终的tablet，整个过程需要3次网络往返（round-trips）。

如果客户端缓存了目标tablet的位置信息，但是到了目标tablet后发现原来缓存的tablet位置信息过时了，那么会重新从root tablet开始定位tablet，整个过程需要6个network round-trips。

片的存储和读写

片的数据最终还是写到GFS里的，片在GFS里的物理形态就是若干个SSTable文件。下图展示了读写操作基本情况

当片服务器收到一个写请求，片服务器首先检查请求是否合法。如果合法，先将写请求提交到日志去，然后将数据写入内存中的memtable。memtable相当于SSTable的缓存，当memtable成长到一定规模会被冻结，Bigtable随之创建一个新的memtable，并且将冻结的memtable转换为SSTable格式写入GFS，这个操作称为minor compaction。

当片服务器收到一个读请求，同样要检查请求是否合法。如果合法，这个读操作会查看所有SSTable文件和memtable的合并视图，因为SSTable和memtable本身都是已排序的，所以合并相当快。

每一次minor compaction都会产生一个新的SSTable文件，SSTable文件太多读操作的效率就降低了，所以Bigtable定期执行merging compaction操作，将几个SSTable和memtable合并为一个新的SSTable。BigTable还有个更厉害的叫major compaction，它将所有SSTable合并为一个新的SSTable。