Bigtable：一张能长到 PB 级的稀疏大表

一句话

Bigtable 是 Google 提出的一套分布式结构化数据存储系统。它把数据组织成一张稀疏、有序、多维的大表——每个单元格由 (行键, 列, 时间戳) 三元组定位，值是一串不被系统解释的字节。这张表能横跨上千台机器、长到 PB 级：它按行键有序地把表切成一段段 tablet 分摊到众多机器，底层用 LSM-tree 式引擎（内存中的 memtable + GFS 上一摞只读 SSTable + 定期合并）读写，用 GFS 存文件、用 Chubby 做协调与选主。它主动放弃了关系数据库的通用事务与 SQL，换来近乎无限的横向扩展，是 Google「老三件套」的第三件，也是宽列 NoSQL（HBase、Cassandra）的直接源头。

Glossary · 术语表

坐标

作者是 Fay Chang、Jeffrey Dean、Sanjay Ghemawat、Mike Burrows 等一众 Google 工程师，论文发表于 OSDI 2006。它是 Google「分布式系统老三件套」的收官之作，站在前两件的肩膀上：数据文件与日志都存在 GFS（Paper 17）上，很多批量数据加工用 MapReduce（Paper 18）完成，协调与选主交给 Chubby（Burrows 正是 Chubby 的作者，也在此列）。它对外启发深远：开源界照它做出 HBase，Facebook 把它的数据模型与 Dynamo 的去中心化分布结合成 Cassandra；它的单机引擎思想后来被 Dean 与 Ghemawat 提炼成开源的 LevelDB，再长成 Facebook 的 RocksDB，成为今天大量数据库的存储底座。Google 自己也在它之上继续演进出 Percolator（加事务）、Spanner（全球一致），并把它作为公有云服务 Cloud Bigtable 对外开放。

问题与动机

2000 年代中期，Google 内部涌现出大量既要存海量数据、又对形态和访问方式有特殊要求的场景：为全网数十亿网页各存一行、每次抓取留一个带时间戳的版本；Google Earth 的 TB 级卫星与地图瓦片；亿级用户的个性化搜索偏好；各种爬虫、分析产生的中间数据。它们的共同点是——

• 规模远超单机、甚至超出传统并行数据库的舒适区：动辄几百亿行、上百 TB，必须摊到成千上万台廉价机器，还要能随时加机器扩容。
• 形态松散、稀疏：不同网页有的字段有、有的没有，列的种类可能极多且不断新增，大部分「格子」其实是空的。用固定 schema 的关系表来存，既别扭又浪费。
• 需要多版本：同一个网页在不同时间被抓到的内容都要留，天然带时间维度。
• 但查询模式其实很简单：绝大多数访问是「按行键读/写一行」或「扫一段行区间」，几乎用不到关系数据库那套复杂的多表关联与通用事务。

关系型数据库为「中等规模 + 复杂查询」而生，硬撑这种「超大规模 + 简单查询 + 松散多版本」的负载既贵又难扩。于是 Google 决定不通用、只解决自己这类问题：设计一个能横向扩到上千台机器、面向稀疏多版本数据、只保留最必要语义的存储系统——用放弃通用性来换极致的规模与简单。

核心思想 / 方法

数据模型：一张稀疏、有序、多维的大表

Bigtable 最漂亮的一步是它的数据模型。论文一句话定义它：一个稀疏的、分布式的、持久化的、多维有序 map（映射表）。这个 map 的「钥匙」是一个三元组、「锁开出来」的是一串字节：

(行键 row, 列 column, 时间戳 timestamp) → 值 value（不被解释的字节串）

拆开看四个维度：

• 行键（row key）：任意字符串（可达 64 KB，通常几十字节）。整张表按行键的字典序排列，且对单行的读写是原子的。这条「有序」是全系统的地基：把逻辑相关的数据编成相邻的行键，它们物理上就挨在一起，扫区间极快。经典技巧——Webtable 把网址按域名反转当行键（maps.google.com/index.html 写成 com.google.maps/index.html），于是同一网站的所有页面排在连续区间里。
• 列族（column family）：列不是随便一列列，而是先归到列族里，列名写成 族:限定词（family:qualifier），如 anchor:cnnsi.com。列族是访问控制、磁盘与内存计量的基本单位，数量要少（几百个以内）、极少变；而族内的列（限定词）可以有无限多、随时新增。这就同时满足了「结构可控」与「字段可无限扩展」。
• 时间戳（timestamp）：同一个单元格可以存多个版本，用 64 位时间戳区分，按时间倒序存放（最新的先被读到）。可设自动垃圾回收：只留最近 N 个版本，或只留最近若干天的版本。Webtable 里，一个网页被抓的每个时点各留一版。
• 稀疏：没写过的格子完全不占空间。所以一张表哪怕逻辑上有几百万列，某一行只用到其中几列也毫不浪费——这正是它能容纳「松散、字段各异」数据的关键。

切片与三级寻址：怎么在上千台机器里定位一行

表按行键有序，于是可以按行键区间横切成一段段 tablet（每个约 100–200 MB），tablet 是分布与负载均衡的基本单位——一台 tablet server 负责若干个 tablet，机器多了就多切几段、摊得更开。系统有三类角色：一个轻量的 master（分配 tablet、监控服务器上下线、均衡负载、回收 GFS 垃圾、处理建表/改列族），众多 tablet server（真正处理读写），和链接进每个应用的客户端库。

难点是：几百亿行切出海量 tablet，客户端怎么快速找到「某一行归哪台服务器管」？Bigtable 借鉴 B+ 树，用三级寻址：

• 第一级：一个固定的 Chubby 文件，存着「根 tablet」的位置。
• 第二级 · 根 tablet：它是一张特殊的 METADATA 表的第一个 tablet，永不分裂，里面记着 METADATA 表其余所有 tablet 的位置。
• 第三级 · METADATA 表：每一行记录一个用户 tablet 的位置（行键 = 表名 + 该 tablet 的末行）。

顺着「Chubby → 根 tablet → METADATA → 用户 tablet」三跳，就能定位任意一行；论文算过，这套结构足以寻址 2³⁴ 个 tablet。客户端还会缓存已查到的位置，绝大多数请求根本不碰 master——这正是 master 能保持轻载、不成瓶颈的原因。tablet 到底归谁，用 Chubby 锁裁定：每台 tablet server 在 Chubby 的一个目录里创建并独占一个锁文件，锁在则活、锁丢则停；master 监视这个目录来发现服务器上线，并靠「能否抢到某台的锁」来判定它是真死还是只是网络隔断，从而安全地把它的 tablet 重新分配。

tablet 怎么读写：memtable + SSTable + 合并（LSM 引擎）

这是全篇工程上最精彩的部分，也是被后世抄得最多的一招。一个 tablet 的持久状态存在 GFS 上，由三样东西构成：

• 提交日志（commit log）：所有更新先追加到一份写在 GFS 上的重做日志里——顺序写、极快，且因在 GFS 上有多副本而丢不了。
• memtable：最近的更新还额外存在内存里一个排好序的缓冲区，读得飞快。
• SSTable：更早的更新则固化成 GFS 上一系列 SSTable 文件。SSTable 是一个只读、有序、不可变的「键→值」文件，内部分块（默认 64 KB）+ 尾部块索引，一次磁盘寻道就能定位一个键。

于是读写路径变成：

• 写：校验合法性与权限（查 Chubby 里的 ACL）→ 把这条改动追加进提交日志（多条攒成一批一起提交，group commit）→ 再插入内存 memtable。写只碰「顺序日志 + 内存」，所以极快。
• 读：把内存 memtable 与磁盘上那一摞 SSTable 拼成一个合并视图（两边都有序，归并即可），在合并结果上取值——新版本自然盖住旧版本。

只往内存和日志里加、从不原地改磁盘，内存迟早会满，于是有三种压实（compaction）来收拾：

• 次压实（minor compaction）：memtable 涨到阈值就冻结它、另起一个新的接着写，把冻结的这份誊清成一个新 SSTable 落到 GFS。既降内存占用，也缩短故障恢复时要重放的日志。
• 合并压实（merging compaction）：读入几个 SSTable + memtable、写出一个新的 SSTable，控制 SSTable 的数量不至无限膨胀（否则读时要合并的文件越来越多、越读越慢）。
• 主压实（major compaction）：把一个 tablet 的所有 SSTable 重写成唯一一个、且丢弃所有已删除标记——被删的数据到此才真正从磁盘消失，回收空间、也让敏感数据得以及时清除。

这套「写只追加、旧文件只读、后台定期合并」正是 LSM-tree（日志结构合并树）的思路：用「顺序写 + 批量整理」换来了极高的写吞吐与简单的容错。为什么这么设计能又快又稳——写不做随机磁盘改写（分布式文件系统上最贵的操作），全是顺序追加；SSTable 一旦生成就不可变，读它无需加锁、并发天然安全，机器坏了直接从 GFS 上重新加载 SSTable + 重放日志即可，恢复干净利落。

让它真正好用的一批精调

光有上面的骨架还不够快，论文用一组务实的优化把性能拉满：

• 局部性组（locality group）：客户端可把几个常一起访问的列族归成一个局部性组，每组单独存成 SSTable。于是只想读网页元数据时，不必把巨大的正文也从磁盘捞出来——把不常同时用的数据物理分开，读得更省。还能把某个组声明为常驻内存（如存 tablet 位置的那个列族），查得飞快。
• 压缩：SSTable 的块可压缩。很多客户端用一种两趟自定义方案（先在大窗口里找长的重复串、再在 16 KB 小窗口里快速压），在 Webtable 上做到约 10:1 的压缩比（远好于通用 Gzip 的约 3:1）——因为同一网页存了多个相近版本，重复极多。
• 布隆过滤器：读一个键时，本要挨个去每个 SSTable 里找。给 SSTable 配布隆过滤器后，能先一口回答「这个 SSTable 一定没有这行这列」，从而省掉大量无谓的磁盘寻道。
• 两级缓存：扫描缓存（Scan Cache，缓存 SSTable 返回的键值对）+ 块缓存（Block Cache，缓存从 GFS 读来的 SSTable 块），分别加速「反复读同一批数据」和「读附近数据」。
• 每台服务器一份提交日志：若每个 tablet 各写一份日志，一台机器上上千个 tablet 就要同时向 GFS 写上千个文件、还丢了 group commit 的好处。于是整台 tablet server 共用一份物理日志，代价是恢复时要按 (表, 行, 日志序号) 把混在一起的日志排个序，让同一 tablet 的记录连成一片、一次读入。
• 利用不可变性：SSTable 永不变，因此读它不需要任何加锁；被删数据靠对 SSTable 的「标记—清除」式垃圾回收真正抹掉；tablet 分裂几乎零成本——两个子 tablet 直接共享父亲的 SSTable 即可。

关键结果

论文在一个 tablet server 数从 1 加到 500 的集群上，用 1000 字节的值测了随机读、随机写、顺序读/写、扫描等负载。几个要点：

• 单台服务器的吞吐（值/秒，1000 字节值）大致是：从磁盘随机读最慢（约 1200），随机写和顺序读写居中（约 8500 上下），内存随机读与扫描最快（约 1 万～1.5 万）。
• 从磁盘随机读为什么最慢：每读一个 1000 字节的值，SSTable 都要从 GFS 拉来一整个 64 KB 的块——绝大部分带宽都花在了「读了 64 KB、只用 1 KB」上。这条也解释了它扩展时随机读的伸缩性最差。
• 整体伸缩性可观但非线性：从 1 台加到 500 台，聚合吞吐大幅上升，但每台的平均吞吐随规模下降（负载不均、GFS 与网络成为共享瓶颈），随机读尤其明显。
• 真实规模：论文发表时，Google 内部已有 388 个生产 Bigtable 集群、共约 24500 台 tablet server 在服务；单表可达数百 TB（如 Google Analytics 的原始点击表约 200 TB 量级），支撑着 Google Earth、个性化搜索、爬虫等一批产品。

这些数字要传达的不是「它是最快的数据库」，而是——在这种超大规模、简单负载下，一套受限但可横向扩展的设计，能把成千上万台廉价机器聚成一个几乎无限大的存储层。

为什么重要 / 影响

Bigtable 的贡献和 MapReduce 一样，主要在抽象与工程取舍，而非某个算法。它证明了一件事：放弃关系数据库的通用性（通用事务、SQL、多表关联），只保留「按行键读写 + 扫区间 + 多版本」这组最必要的语义，就能换来近乎无限的横向扩展。它开创的「宽列（wide-column）」数据模型——行键有序、列族 + 无限限定词、稀疏多版本——成了一整类数据库的范式：开源界的 HBase 几乎是它的直接复刻，Facebook 的 Cassandra 把它的数据模型嫁接到 Dynamo 的去中心化分布上，还有 Hypertable、Accumulo 等。它与 GFS、MapReduce 合成 Google「老三件套」，共同定义了「大数据基础设施」的样貌。更深远的是它普及的一整套心法：用有序行键把逻辑局部性变成物理局部性、LSM 式「顺序写 + 只读文件 + 后台合并」的存储引擎、用不可变数据换免锁并发、把协调/选主外包给一个 Chubby 这样的小而可靠的锁服务——这些都被后来无数系统继承。它的单机引擎更被 Dean 与 Ghemawat 提炼成 LevelDB，再演化出 RocksDB，如今是从 MySQL 的存储引擎到各种 NoSQL 的共同底座。

局限与批评

• 只有单行事务，没有跨行/跨表事务：这是最被诟病的一点。要维护跨多行的一致关系，应用得自己想办法。Google 自己随后用 Percolator 给 Bigtable 加上跨行事务与增量处理，又用 Spanner 做到全球尺度的分布式事务——都是在补 Bigtable 这块短板。
• 没有 SQL、没有二级索引、不做关系查询：只能按行键或行区间访问。想按「非行键的某个字段」查，得自己另建索引表或全表扫。数据建模要反范式、要精心设计行键，学习曲线陡。
• 强依赖 Chubby 与 GFS：Chubby 长时间不可用会直接让 Bigtable 不可用（论文诚实报告过因 Chubby 故障导致的短时不可用）；一切也系于 GFS 的可靠性。
• 调优是门手艺：局部性组怎么分、要不要压缩、布隆过滤器、内存组、行键怎么设计——用好 Bigtable 很吃经验，用不好性能差很多。
• 原版是单数据中心：论文里的 Bigtable 主要在单集群内工作，跨数据中心的复制与全球一致是后来（Megastore、Spanner）才补上的。

要点