[IR] Bigtable: A Distributed Storage System for Semi-Structured Data

良心博文: http://blog.****.net/opennaive/article/details/7532589

这里只是基础简述

---

众人说：

链接：http://blog.****.net/opennaive/article/details/7532589

2006年的OSDI有两篇google的论文，分别是BigTable和Chubby。

• Chubby是一个分布式锁服务，基于Paxos算法；
• BigTable是一个用于管理结构化数据的分布式存储系统，构建在GFS、Chubby、SSTable等google技术之上。

相当多的google应用使用了BigTable，比如Google Earth和Google Analytics，因此它和GFS、MapReduce并称为谷歌技术"三宝"。

链接：https://www.zhihu.com/question/19551534/answer/116874719

Bigtable 论文已经十年了。论文的第一大贡献是编程模型方面，当时大家都还在摸索在这种大 PC 机群环境下存储系统应该提供怎样的编程模型，要简单易理解，满足产品开发需求，又要在实现上能水平扩展支持海量存储。Bigtable 的「排序大表 + Column Family」在当时就不是什么新东西，但被证明了是一个非常成功的设计，能概括从线上到线下很多的业务需求，并且有很好的灵活性和扩展性。到今天 Bigtable 还有极广泛的应用，之后 MegaStore（公开版本是 AppEngine 上的 DataStore） 直接基于 Bigtable 构建，再后来的 Spanner 在单 tablet 上的存储干脆复用了 Bigtable 的版本。

在当时，人们对这种大规模分布式系统环境的认识还并不系统，谈得最多的是 CAP —— CAP (Consistency Availability Partition) 不可兼得是一个定律，但它没有告诉你应该怎么根据业务特点取舍。当时另一个有趣的项目是 Amazon 的 Dynamo, 它基于不同的取舍方向，追求 A 和 P（Bigtable 的 A 并不是特别好），让程序员自己动手解决写冲突问题。从今天看，就不及 Bigtable 的模型成功。（私货：我一直不看好 Cassandra）

在实现上，Bigtable 的另一点贡献是把 LSM (Log-Structured Merge) Tree 这种古老的技术带回前台。它和当时全部机械硬盘的现状以及 GFS 的编程模型极搭。把随机写全部转化为顺序写，实现了非常好的吞吐和即使对线上应用也可以接受的延迟（有坑，论文里就隐藏了坑），只读 SSTable dump 极大简化了设计。用 GFS 解决底层存储备份一系列问题，也大大简化了 Bigtable 自身的实现。SSTable + LSM Tree 这一部分的成果开源在了 LevelDB, 有广泛的应用，也启发了其他的很多开源项目。

Jeff Dean 自己对 Bigtable 最不满意的是没有提供跨行事务支持。这个故事很有趣：跨行事务天生是不可扩展，你没它办法，Bigtable 一开始并没有提供跨行事务就是这个原因。但是，它不可扩展是个实现问题，业务就是需要啊，你不提供官方实现，业务就会在上层企图自己搞事务，不出所料绝大部分分布式事务实现都是错的。Jeff Dean 后来实在看不过去在 Spanner 提供了官方分布式事务支持。

Bigtable 论文出来后不久，国内应该不止一个团队在企图复制它。当时 Bigtable 论文给我的感受倒不是它有多大创新，而是它在有机群管理软件（当时还不知道它叫 borg）有 GFS 有 Chubby 做基础，实现起来并不困难（论文里说了大概就10万行C++），有了 Bigtable 的基础，Google 实现其他的东西可以更快更得心应手。这是拿机群当操作系统做的思路，这种打法，你想要跟着打，会追得很辛苦，你想要走捷径取得局部成果，又必然后劲不足。稍微有点毁三观，这么多年之后我不用翻原文都能记起 Bigtable 等老三篇的细节，就是那时被碾压的印记。

---

Data Model

本质上说，Bigtable是一个键值（key-value）映射。按作者的说法，Bigtable是一个稀疏的，分布式的，持久化的，多维的排序映射。

先来看看多维、排序、映射。

Bigtable的键有三维，分别是行键（row key）、列键（column key）和时间戳（timestamp）。

行键和列键都是字节串，时间戳是64位整型；而值是一个字节串。可以用 (row:string, column:string, time:int64)→string 来表示一条键值对记录。

行键

行键可以是任意字节串，通常有10-100字节。行的读写都是原子性的。

Bigtable按照行键的字典序存储数据。Bigtable的表会根据行键自动划分为片（tablet），片是负载均衡的单元。

最初表都只有一个片，但随着表不断增大，片会自动分裂，片的大小控制在100-200MB。

行是表的第一级索引，我们可以把该行的列、时间和值看成一个整体，简化为一维键值映射，类似于：

table{
  "" : {sth.},//一行
  "aaaaa" : {sth.},
  "aaaab" : {sth.},
  "xyz" : {sth.},
  "zzzzz" : {sth.}
}  

列键

列是第二级索引，每行拥有的列是不受限制的，可以随时增加减少。为了方便管理，列被分为多个列族（column family，是访问控制的单元），一个列族里的列一般存储相同类型的数据。

一行的列族很少变化，但是列族里的列可以随意添加删除。列键按照family:qualifier格式命名的。这次我们将列拿出来，将时间和值看成一个整体，简化为二维键值映射，类似于：

table{
  // ...
  "aaaaa" : { //一行
    "A:foo" : {sth.},//一列
    "A:bar" : {sth.},//一列
    "B:" : {sth.} //一列，列族名为B，但是列名是空字串
  },
  "aaaab" : { //一行
    "A:foo" : {sth.},
    "B:" : {sth.}
  },
  // ...
}  

或者可以将列族当作一层新的索引，类似于：

table{
  // ...
  "aaaaa" : { //一行
    "A" : { //列族A
      "foo" : {sth.}, //一列
      "bar" : {sth.}  //一列
    },
    "B" : { //列族B
      "" : {sth.}
    }
  },
  "aaaab" : { //一行
    "A" : {
      "foo" : {sth.},
    },
    "B" : {
      "" : "ocean"
    }
  },
  // ...
}  

时间戳

时间戳是第三级索引。Bigtable允许保存数据的多个版本，版本区分的依据就是时间戳。时间戳可以由Bigtable赋值，代表数据进入Bigtable的准确时间，也可以由客户端赋值。

数据的不同版本按照时间戳降序存储，因此先读到的是最新版本的数据。我们加入时间戳后，就得到了Bigtable的完整数据模型，类似于：

table{
  // ...
  "aaaaa" : { //一行
    "A:foo" : { //一列
         : "y", //一个版本
         : "m"
      },
    "A:bar" : { //一列
         : "d",
      },
    "B:" : { //一列
         : "w"
         : "o"
         : "w"
      }
  },
  // ...
} 

查询时，如果只给出行列，那么返回的是最新版本的数据；

如果给出了行列时间戳，那么返回的是时间小于或等于时间戳的数据。

查询："aaaaa"/"A:foo"，返回的值是"y"；

查询："aaaaa"/"A:foo"/10，返回的结果就是"m"；　　// 小于10的至于4

查询："aaaaa"/"A:foo"/2，返回的结果是空。　　　　　// 小于2的为null

APIs:

• Metadata operations
　　– Create/delete tables, column families, change metadata
• Writes
　　– Set(): write cells in a row
　　– DeleteCells(): delete cells in a row
　　– DeleteRow(): delete all cells in a row
• Reads
　　– Scanner: read arbitrary cells in a bigtable
　　• Each row read is atomic
　　• Can restrict returned rows to a particular range
　　• Can ask for just data from 1 row, all rows, etc.
　　• Can ask for all columns, just certain column families, or specific columns

Building blocks:

• Google File System (GFS)
　　– stores persistent data (SSTable file format)　　// Sorted String Table
• Scheduler　　// 分配任务
　　– schedules jobs onto machines
• Chubby　　  // lock management
　　– Lock service: distributed lock manager
　　– master election, location bootstrapping
• MapReduce (optional)　　// 分布式计算 --> 当然，spark是its替代品
　　– Data processing
　　– Read/write Bigtable data

Bigtable依赖于google的几项技术：(1) 用GFS来存储日志和数据文件；(2) 按SSTable文件格式存储数据；(3) 用Chubby管理元数据。

• BigTable的数据和日志都是写入GFS的。
• SSTable的全称是Sorted Strings Table，是一种不可修改的有序的键值映射，提供了查询、遍历等功能。每个SSTable由一系列的块（block）组成，Bigtable将块默认设为64KB。在SSTable的尾部存储着块索引，在访问SSTable时，整个索引会被读入内存。BigTable论文没有提到SSTable的具体结构，LevelDb日知录之四： SSTable文件这篇文章对LevelDb的SSTable格式进行了介绍，因为LevelDB的作者JeffreyDean正是BigTable的设计师，所以极具参考价值。每一个片（tablet）在GFS里都是按照SSTable的格式存储的，每个片可能对应多个SSTable。
• Chubby是一种高可用的分布式锁服务，Chubby有五个活跃副本，同时只有一个主要的副本提供服务，副本之间用Paxos算法维持一致性。
  • Chubby提供了一个命名空间（包括一些目录和文件），每个目录和文件就是一个锁。Chubby的客户端必须和Chubby保持会话，客户端的会话若过期则会丢失所有的锁。
  • 关于Chubby的详细信息可以看google的另一篇论文：The Chubby lock service for loosely-coupled distributed systems。Chubby用于片定位，片服务器的状态监控，访问控制列表存储等任务。

Implementation:

Bigtable集群包括三个主要部分：一个供客户端使用的库，一个主服务器（master server），许多片服务器（tablet server）。

正如数据模型小节所说，Bigtable会将表（table）进行分片，片（tablet）的大小维持在100-200MB范围，一旦超出范围就将分裂成符合要求的片，或者合并成更大的片。 --> 下一节

1. 每个片服务器负责一定量的片，处理对其片的读写请求，以及片的分裂或合并。

片服务器可以根据负载随时添加和删除。这里片服务器并不真实存储数据，而相当于一个连接Bigtable和GFS的代理，客户端的一些数据操作都通过片服务器代理间接访问GFS。

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

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

Tablets

• Each Tablet is assigned to one tablet server.
　　– Tablet holds contiguous range of rows
　　　　• Clients can often choose row keys to achieve locality
　　– Aim for ~100MB to 200MB of data per tablet
• Tablet server is responsible for ~100 tablets
　　– Fast recovery:
　　　　• 100 machines each pick up 1 tablet for failed machine
　　– Fine-grained load balancing:
　　　　• Migrate tablets away from overloaded machine
　　　　• Master makes load-balancing decisions

One Tablt server: 100 tablets * 100~200MB = 10~20G

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

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

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

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

可以看出整个定位系统其实只是两部分，一个Chubby文件，一个元数据表。注意元数据表虽然特殊，但也仍然服从前文的数据模型，每个分片也都是由专门的片服务器负责，这就是不需要主服务器提供位置信息的原因。

客户端会缓存片的位置信息，如果在缓存里找不到一个片的位置信息，就需要查找这个三层结构了，包括访问一次Chubby服务，访问两次片服务器。

Tablet Assignment

• Each tablet is assigned to one tablet server at a time.
• Master server keeps track of the set of live tablet servers and current assignments of tablets to servers.
• When a tablet is unassigned, master assigns the tablet to an tablet server with sufficient room.
• It uses Chubby to monitor health of tablet servers, and restart/replace failed servers.

About Chubby:

– Tablet server registers itself by getting a lock in a specific directory chubby
　　• Chubby gives 㵰lease㵱 on lock, must be renewed periodically
　　• Server loses lock if it gets disconnected

– Master monitors this directory to find which servers exist/are alive
　　• If server not contactable/has lost lock, master grabs lock and reassigns tablets
　　• GFS replicates data. Prefer to start tablet server on same machine that the data is already at.

Compression
– Many opportunities for compression
　　• Similar values in the cell at different timestamps  不同的时间序列
　　• Similar values in different columns　　不同的列
　　• Similar values across adjacent rows　 邻接行

片的存储和访问

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

当片服务器收到一个写请求，片服务器首先检查请求是否合法。

如果合法，先将写请求提交到日志去，然后将数据写入内存中的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。遗憾的是，BigTable作者没有介绍memtable和SSTable的详细数据结构。

BigTable和GFS的关系

集群包括主服务器和片服务器，主服务器负责将片分配给片服务器，而具体的数据服务则全权由片服务器负责。

但是不要误以为片服务器真的存储了数据（除了内存中memtable的数据），数据的真实位置只有GFS才知道。

主服务器将片分配给片服务器的意思应该是，

• 片服务器获取了片的所有SSTable文件名，
• 片服务器通过一些索引机制可以知道所需要的数据在哪个SSTable文件，
• 然后从GFS中读取SSTable文件的数据，
• 这个SSTable文件可能分布在好几台chunkserver上。　　// 只有GFS掌管具体的物理存储操作。

Performance - Scaling

Reason: Load Imbalance
– Competitions with other processes
　　• Network
　　• CPU
– Rebalancing algorithm does not work perfectly
　　• Reduce the number of tablet movement
　　• Load shifted around as the benchmark progresses