Bigtable：稀疏表、Tablet 与时间戳单元

破除误解#

GFS 是 2003 年的块文件系统：单主节点、约 64 MB 的大块、默认三副本，接口面向几乎只追加的大文件。Bigtable 把单元格映射写在这层文件之上。提交日志和不可变的 SSTable 都是 GFS 文件；tablet server 并不自己扮演一块 POSIX 盘。一次按行键的读，可能只取 1000 字节，却要从 GFS 拉来一块 64 KB 的 SSTable 块。把两者当成同一个对象，就看不见“文件语义”和“单元格语义”之间那层翻译。Webtable 的行是反转后的 URL，列是 contents 与 anchor，时间戳是抓取时刻——这些名字 GFS 一概不认识。

误解二：Bigtable 是 MapReduce 的另一种写法。

MapReduce 消费和产出的是文件。任务失败就换机器重跑，输出写到临时文件再原子改名。Bigtable 提供的是另一条路径：按单个行键查找、按行范围扫描，以及单行上的原子读改写。论文写了一组包装，让一张表既能当 MapReduce 的输入源，也能当输出目标，但那是消费关系，不是身份重合。Google Analytics 的摘要表由定期调度的 MapReduce 从原始点击表抽出来；吞吐上限常常卡在 GFS，而不是卡在 MapReduce 的切分函数。把 Bigtable 写成“会随机访问的 MapReduce”，会把 Tablet 定位、memtable 与压缩从句子里删掉。

误解三：Bigtable 和 Dynamo 都是分布式键值，一致性可以互换。

Dynamo 要的是购物车在部分机器挂掉时仍然能写。它用一致性哈希、松散仲裁和向量时钟，默认永远可写，把对齐推给反熵和业务合并。Bigtable 给每个 Tablet 指定唯一的 tablet server，用 Chubby 保证同一时刻至多一个活着的 master，并把成员资格做成 Chubby 目录里的锁文件。单行读写在这台 server 上是原子的；跨行没有通用事务。Chubby 长时间不可用，整张表也不可用。论文在 14 个集群、11 个 Chubby 实例上量过：因 Chubby 不可用而导致部分数据不可用的时间，平均只占 Bigtable server 小时数的 0.0047%，最惨的一簇是 0.0326%。这是另一种账单：用锁服务换成员的单一真相，而不是用向量时钟把分歧留下来。

误解四：有行有列，所以它是通用的 SQL 事务库。

数据库与事务 通常承诺跨行、跨表的 ACID，以及用 SQL 表达的连接与约束。Bigtable 明确拒绝完整关系模型。它提供动态的布局控制：行键怎么选决定局部性，列族是权限和记账的单位，locality group 决定哪些列物理上挨在一起。事务边界停在单行。团队一度想做通用事务，因为当时没有急用就没做；后来发现多数应用只要单行事务，跨行需求最要紧的是二级索引，他们打算用更专用的机制去满足，而不是补一套完整的提交协议。把 Bigtable 当 PostgreSQL 用，会在第一次跨行扣库存时得到“成功写了半边”的语义。

误解五：读这篇是为了学会怎么跑 HBase。

HBase 后来把稀疏表、region 和 HFile 的外形带进了开源世界，教材常从那里倒着讲 Bigtable。对象仍是 2006 年 Google 内部那组接口，以及网页库、爬虫和分析流水线在生产里的用量。集群怎么装、compaction 阈值怎么选、schema 怎么抄，都是另一篇文章的运维手册。

三元组、列族，以及 Webtable 的行键#

一张 Bigtable 是从 (row, column, timestamp) 到字节串的映射。行键是任意字符串，当时上限 64 KB，典型用户只用 10 到 100 字节。同一行键下的读写是原子的，不论碰了多少列。表按行键的字典序维护，行范围被动态切成 Tablet，这是分布和负载均衡的单位。短范围扫描通常只碰到少数机器。客户端靠选行键来买局部性：Webtable 把主机名倒过来，把 maps.google.com/index.html 存成 com.google.maps/index.html，于是同一域名的页面落在连续行里，主机和域名分析不必满表乱跳。

列键组成列族。列族是权限控制的基本单位，也是压缩时“通常同一类型”的边界。族必须先创建，族内的限定符可以随时出现。论文的意图是：一张表的列族数应当小，最多到数百，而且运行中很少改；列的个数则可以没有上限。列键写法是 family:qualifier。Webtable 的 language 族往往只有一个列，记下页面语言；anchor 族的限定符是来源站点，单元格是锚文本。CNN 主页被 Sports Illustrated 和 MY-look 同时链到，那一行就会出现 anchor:cnnsi.com 和 anchor:my.look.ca。权限、磁盘和内存记账都按列族做，于是同一张网页库可以让有的任务只追加原始页、有的任务写派生列、有的任务只读而且读不到全部族。

每个单元格可以有多个版本，用 64 位时间戳索引。时间戳可由系统填成微秒级的“当前时间”，也可由客户端指定；要避免碰撞的应用必须自己保证唯一。版本按时间戳递减存放，最近的先被读到。列族上可以设垃圾回收：只留最近 n 个版本，或只留足够新的版本，例如七天以内。Webtable 把 contents: 的时间戳设成实际抓取时刻，并只保留每个页面最近三个版本。稀疏的意思是：绝大多数（行、列、时间）三元组根本没有值，系统不为空单元格占位。存储形状更接近有序且带版本的键值，而不是填满的笛卡尔积。

Tablet、三级定位与 Chubby#

实现分成三块：链进每个客户端的库、一台 master、许多 tablet server。tablet server 可随时加减。master 负责把 Tablet 派给 server、发现 server 的增减、做负载均衡、回收 GFS 上的垃圾文件，并处理建表和建列族。数据面不经过 master。客户端直接找 tablet server 读写，定位信息也不靠 master，所以多数客户端从不和 master 说话。每台 tablet server 通常管十到一千个 Tablet。表最初是一个 Tablet，长大后自动分裂，默认大约 100 到 200 MB。

定位是三层、形状像 B+ 树。第一层是 Chubby 里的一个文件，记下 root tablet 在哪。root tablet 是 METADATA 表的第一个 Tablet，里面是所有 METADATA Tablet 的位置；它被规定永不分裂，好让层次不超过三层。METADATA 的行键编码了表标识和该 Tablet 的结束行，每行大约 1 KB 驻内存。把 METADATA Tablet 限制在约 128 MB，三层方案足以寻址 \(2^{34}\) 个 Tablet，按 128 MB 的用户 Tablet 计大约是 \(2^{61}\) 字节。客户端缓存位置。缓存空时定位要三次网络往返，包括一次读 Chubby；缓存过期时最多六次，因为过期项要等未命中才被发现。客户端库读 METADATA 时会多拿几个 Tablet 的位置。

每个 Tablet 同一时刻只派给一台 tablet server。server 启动时在 Chubby 的指定目录里创建唯一文件并抢排他锁；master 监视这个目录。失去锁就停止服务。master 若能抢走那把锁，就删掉该文件，把 Tablet 放回未分配集合。master 自己的 Chubby 会话过期则自杀，以免自己和 Chubby 之间的网络问题把集群置于危险；master 挂了并不会改写已经派出去的 Tablet。启动时 master 先抢唯一的 master 锁，再扫目录、询问活着的 server、扫描 METADATA。root tablet 若还没人认领，就先把它放进未分配集合，扫描才能开始。

Bigtable 把日志和数据文件交给 GFS，把锁、引导位置、schema 和访问控制交给 Chubby。Chubby 是五副本的锁服务，多数派存活才算活着，副本之间用 Paxos。目录和文件都可以当锁，读写原子。客户端会话租约续不上，锁和句柄一起丢。论文把 Chubby 的职责写得很满：保证至多一个活 master、存放数据的引导位置、发现 tablet server 并确认其死亡、存放列族 schema、存放访问控制表。它不是“又一个 GFS”。把成员真相放进锁服务，换来的是一张表在锁服务长时间消失时跟着消失。

memtable、SSTable 与 locality group#

Tablet 的持久状态在 GFS 上。更新先写成提交日志里的 redo，最近提交的放进内存里有序的 memtable，更老的放进一串 SSTable。SSTable 是持久、有序、不可变的键值映射，内部是一串块，块大小通常 64 KB，块索引在文件末尾，打开时载入内存。查找先在内存索引里二分，再读一块，一次磁盘寻道即可；也可以整文件映射进内存。恢复时 server 从 METADATA 读出 SSTable 列表和 redo 点，把索引载入内存，再从日志重放 memtable。

写到达后检查形态和授权，授权名单几乎总是命中 Chubby 客户端缓存。合法变异写入提交日志，小写用 group commit 攒批，提交后再插入 memtable。读在 SSTable 序列和 memtable 的归并视图上执行，因为两边都按字典序排好。分裂合并时读写仍继续。

为了避免每个 Tablet 一份日志把 GFS 打成许多并发小文件，每台 tablet server 只追加一个提交日志，不同 Tablet 的变异混在同一文件里。恢复时 master 协调把日志按键排序，切成 64 MB 段并行排，使同一 Tablet 的记录变得连续。写 GFS 若抖动，server 用两条日志线程切换，靠序号在恢复时丢掉重复项。

memtable 到达阈值就冻结，写成新的 SSTable，这是 minor compaction：减内存，也缩短宕机后要读的日志。后台还会做 merging compaction，把若干 SSTable 与 memtable 合成新文件。把所有 SSTable 重写成恰好一个，叫做 major compaction，产物里不再留删除标记。系统轮转所有 Tablet 做 major compaction，好及时收回已删数据，这对存敏感信息的服务很重要。这些机制是论文里的装置，不是一份给运维调阈值的配方。

客户端可以把多个列族打成 locality group，每个 group 在每个 Tablet 里生成单独的 SSTable。Webtable 把语言、校验和这类元数据放在一组，把页面正文放在另一组，读元数据就不必扫过整页 HTML。某个 group 可以声明为内存驻留，METADATA 表的位置列族就用这一招。

压缩按块做，许多客户端用两遍：先用 Bentley-McIlroy 在大窗口里抓长公共串，再在约 16 KB 的小窗口里抓短重复。编码大约 100 到 200 MB/s，解码 400 到 1000 MB/s。Webtable 在只留每个文档一个版本的实验里得到约 10 比 1 的空间下降，好过 HTML 上常见的 Gzip 三到四倍，因为同一主机的页面彼此靠近，页眉页脚里的套话被第一遍算法看见。Bloom filter 用来问某块 SSTable 是否可能含有指定的行列对，让大量不存在的查找不必碰盘。SSTable 不可变，还让分裂变便宜：子 Tablet 先共享父级文件，而不必立刻重写一套。

论文量到了什么，没量什么#

评测用 N 台 tablet server，每台配 1 GB 内存，写进一个由 1786 台机器组成的 GFS 单元，每机两块 400 GB IDE 盘。客户端数量与 tablet server 相同。机器是两路双核 2 GHz Opteron，千兆以太网，两层树形交换，根上大约 100 到 200 Gbps 聚合带宽，机房内往返小于一毫秒。每个基准大约按每台 tablet server 读写 1 GB、每条 1000 字节来选行数 R；内存随机读把每台数据降到 100 MB，好放进内存。字符串故意做成随机且不可压，所以 Figure 6 量的不是压缩比。

单台 tablet server 上，随机读比其他操作慢一个数量级以上。每次随机读要从 GFS 拉 64 KB 的 SSTable 块，里面只用 1000 字节。大约每秒 1200 次读，折合从 GFS 拉约 75 MB/s，已经够把该机 CPU 和网络链路打满。论文注明：这类访问模式的应用通常把块改到约 8 KB——这是测量里的观察，不是一份调参手册。随机写和顺序写几乎一样快，因为都追加进同一条提交日志。顺序读能吃到块缓存：一块 64 KB 可以伺候接下来 64 次 1000 字节读。扫描更快，因为一次 RPC 带回一串值。

把 tablet server 从 1 台加到 500 台，聚合吞吐上升超过一百倍。内存随机读的瓶颈在单机 CPU，server 数乘 500，性能大约乘 300。大多数基准从 1 台到 50 台时，单机吞吐会掉一截，因为负载不均，也因为同机上还有别的进程在抢 CPU 和网。随机读的扩展最差：机器数乘 500，聚合大约只乘 100，因为每个 1000 字节读都在网上搬 64 KB，共享的千兆链路先饱和。

论文没量的东西同样重要。它没有给出跨行可串行化事务的延迟，因为接口里就没有这种事务。它没有把 Bigtable 当成独立于 GFS 的存储来测：随机读的代价里，很大一块是 GFS 块传输。它也没有声称线性加速是定理。1 到 50 的掉速、随机读的共享链路，都被写进正文。压缩数字出现在 Webtable 和生产表上，而不是出现在那组不可压缩的 1000 字节基准里。

生产快照把对象钉在 2006 年 8 月。当时有 388 个非测试集群、合计约 24500 台 tablet server。14 个忙碌集群共 8069 台 tablet server，聚合超过每秒 120 万次请求，入向 RPC 约 741 MB/s，出向约 16 GB/s。集群规模分布很偏：0 到 19 台的有 259 个，超过 500 台的只有 12 个。爬虫表有一张大约 800 TB、压缩到原文 11%、约一万亿个单元格；另一张大约 50 TB。

Google Analytics 的原始点击表大约 200 TB，行键是站点名加会话创建时间，压缩到 14%；摘要表大约 20 TB，由 MapReduce 定期从点击表抽出，压缩到 29%。Google Earth 预处理表大约 70 TB，影像已经压过，Bigtable 压缩关掉；服务用的索引表大约 500 GB，必须在单数据中心撑住每秒数万查询，于是铺到数百台 tablet server，并使用内存列族。Personalized Search 按用户一行，动作用时间戳记下，列族多达 93 个，后来为此加了配额，免得共享表被某一组产品写满。系统从 2005 年 4 月进入生产，设计实现大约花了七人年。这些数字回答的是 Google 内部的网页库、爬虫和分析在用什么，不是 Hadoop 发行版的安装清单。

教训一节把边界说得更硬。分布式系统会遇到内存和网络损坏、大时钟偏移、僵死机器、不对称分区、Chubby 的 bug、GFS 配额溢出，以及计划内外的硬件维护，而不仅是教材里的停机和对称分区。他们给 RPC 加了校验和，并停止假设 Chubby 只返回某张固定的错误表。更关键的产品决定是：通用事务被推迟，因为当时看不清谁真正需要它。大数据系统 后来常把 Bigtable 写成宽表鼻祖的一句话；那句话成立，前提是记得单行原子、GFS 上的不可变文件，以及 Chubby 把成员资格收成一把锁。

跨域连接#

• 集合论：Bigtable 的数据模型是从三元组集合到字节串的偏函数。稀疏表示定义域里绝大多数点没有像，存储不为空单元格造占位元素。行键的字典序给出全序，Tablet 是这条全序上的区间划分，分裂是把一个区间写成两个相邻区间。列族是列键集合的一个划分，权限在划分的块上定义，而不是在每个限定符上定义。时间戳把同一行列对上的值变成一条链，垃圾回收是对这条链做截断。关系表把笛卡尔积当成默认宇宙；这张映射把“没有的单元格”从宇宙里拿掉，换来的是可以按行区间切开的稀疏函数，而不是可以随便做连接的关系。
• 概率论：Bloom filter 用假阳性换磁盘寻道：它只说“可能有”，从不说“一定有”，假阴性被设计成零。随机读扩展差，是因为 64 KB 块在共享千兆链路上的碰撞，而不是因为行键哈希不够均匀。Chubby 不可用被报成时间比例 0.0047%，这是经验频率，不是独立故障的乘积公式。从 1 台到 50 台的单机吞吐下跌，来自同机争用和再平衡被节流之后仍然存在的负载方差。论文用实验分布说话，没有把“加机器就线性”写成概率意义上的期望定理。
• 可靠性工程：故障单元是“一台 tablet server 加上它持有的锁”，不是“三副本里随便哪一份”。失去 Chubby 锁就停止服务，master 删文件之后才能把 Tablet 交给别人，避免双主同时接受写。major compaction 把删除从标记变成真正消失，这对敏感数据是时效要求，不是空间优化附录。校验和加在 RPC 上，是因为他们见过内存和网络损坏，而不仅是停机。可用性数字绑在 Chubby 上：锁服务长时间消失，表选择不可用，而不是在没有成员真相时继续写。
• 信息不对称：客户端缓存的 Tablet 位置是一份会过期的私有知识，最多六次往返才能爬回 Chubby 里的那份引导文件。tablet server 是否还活着，以它是否仍持有 Chubby 文件上的锁为准，而不是以它自己声明“我还能服务”为准。master 不持久化当前派工表，启动时向活着的 server 询问“你已经在服务哪些 Tablet”，承认现场知识在 server 一边。METADATA 把位置写成可扫描的表，而不是写成每个客户端必须私藏的完整地图。存储接口在这里处理的是谁知道 Tablet 在哪，而不只是单元格里的字节。

参考文献#

• Chang, F., Dean, J., Ghemawat, S., Hsieh, W. C., Wallach, D. A., Burrows, M., Chandra, T., Fikes, A. & Gruber, R. E. Bigtable: A Distributed Storage System for Structured Data. USENIX OSDI, 2006.（本文对象；期刊版 ACM TOCS 26(2), 2008, doi:10.1145/1365815.1365816）
• Ghemawat, S., Gobioff, H. & Leung, S.-T. The Google File System. ACM SOSP, 2003, pp. 29–43. doi:10.1145/945445.945450（日志与 SSTable 所在的块文件系统，非本文对象）
• Dean, J. & Ghemawat, S. MapReduce: Simplified Data Processing on Large Clusters. USENIX OSDI, 2004.（表的批处理消费方，非本文对象）
• Burrows, M. The Chubby Lock Service for Loosely-Coupled Distributed Systems. USENIX OSDI, 2006.（成员、引导位置与 schema 所用的锁服务）
• DeCandia, G. et al. Dynamo: Amazon's Highly Available Key-value Store. ACM SOSP, 2007.（对照另一种放松：永远可写与向量时钟）
• O'Neil, P., Cheng, E., Gawlick, D. & O'Neil, E. The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica 33(4), 1996, pp. 351–385.（论文自承的 memtable/SSTable 前身）

延伸阅读#

• Corbett, J. C. et al. Spanner: Google's Globally-Distributed Database. USENIX OSDI, 2012.（后继系统用时钟换外部一致性，对象已不是 2006 年的 Bigtable）
• 与 数据库与事务 对读：单行原子不是跨行 ACID；推迟通用事务是论文里的产品决定。
• 与 大数据系统 对读：总览里的宽表一句话，对应的是本文拆开的三元组、Tablet 与 Chubby。