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

时间:2024-08-01 11:37:44

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

这里只是基础简述


众人说:

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

2006年的OSDI有两篇google的论文,分别是BigTableChubby

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

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

链接: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

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

本质上说,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:

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

Bigtable集群包括三个主要部分:一个供客户端使用的库,一个主服务器(master server),许多片服务器(tablet server)。

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

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

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

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

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

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

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+树的数据结构存储片的位置信息。

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

第一层,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展示了读写操作基本情况。
[IR] Bigtable: A Distributed Storage System for Semi-Structured Data

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

如果合法,先将写请求提交到日志去,然后将数据写入内存中的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

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

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