Bigtable [OSDI‘06] 论文阅读笔记

原论文：Bigtable: A Distributed Storage System for Structured Data (OSDI’06)

1. Introduction

• Bigtable 是一种用于管理结构化数据的分布式存储系统，可扩展到非常大的规模：数千台服务器上的数据量可达 PB 级别，同时保证可靠性。
• Bigtable的特点：应用范围广、可扩展、高性能、高可用！
• Bigtable不支持完全关系数据模型，而是向clients提供一个支持动态控制数据布局和格式、允许clients推理底层存储中数据的locality属性的单一数据模型。
• 数据使用行名和列名编制索引，Bigtable将数据视为未解释的字符串。
• clients可以通过选择模式来控制数据的locality，Bigtable的模式（schema）参数可以让clients动态控制数据是从内存还是从磁盘读取。

2. Data Model

• Bigtable是一个稀疏的、分布式的、持久的多维有序map，该map是基于row key、column key、timestamp三者建立索引的，map中的每个值都是一个未解释的字节数组。

  • 

• A concrete example: Webtable用于保存大量网页和相关信息的副本，供许多不同项目使用

  • row key: URL

  • column key: various aspects of web page (“contents”)

  • store the contents of the web page in the “contents”: column under the timestamps when they were fetched

  • 

  • anchor 开头的列：存储引用了这个页面的 anchor（HTML 锚点）的文本

• Rows

  • row key是任意长度不超过64KB的字符串，典型的长度是10-100字节
  • 单行上的数据读写是原子性的，使得多个clients并发更新某一行时更容易推断出系统的行为
  • Bigtable 中的数据是根据row key的词典顺序（lexicographic order）组织的，并动态地对行区间（row range）进行切分。每个row range被称作一个tablet，作为数据分布和负载均衡的基本单位读取一个小的row range是高效的，clients可以利用这个特性，通过合理的选择它们的row keys来实现更好的locality。比如以上的例子，将URL的字段倒需序，那么处于同一个域（如.com域）的网页更有可能被连续存储。

• Column Families

  • column keys被组织成一个叫column families的集合，作为访问控制的基本单位。
  • 存储在同一column family内的数据通常具有相同的类型，在存储任何column key的数据之前必须先创建column family；创建column family完成后，family中的任意column key都可以使用。
  • Our intent: column families的数量尽可能少，同时使得families在操作过程中很少发生变化。
  • column key的命名：family:qualifier；column family的命名必须是可打印的
  • 访问控制和磁盘/内存记账都是在column family层面上完成的，这种控制可以允许我们管理不同类型的应用：添加新的基础数据、读取基础数据后创建派生的 column family，只允许查看当前存在的数据。

• Timestamps

  • Bigtable中的每个数据可以存储多个版本，不同版本以时间戳（timestamps）为索引。
  • timestamps为64bits的整数，可以由Bigtable隐式指定，可表示毫秒级别的真实时间；也可以由client显示指定；程序需要保证生成的timestamps的唯一性来避免冲突。
  • 不同版本的数据是基于timestamps降序排序，使得最新版本的数据总是首先被读取。
  • 为了方便管理不同版本的数据，由两种配置方式使得Bigtable自动进行旧版本的垃圾回收：总是保留最新的n个版本，总是保留足够新的若干版本（如过去七天内写入的版本）。在前面Webtable的例子中，以网页被爬取时间为timestamps，仅保留最新的3个版本。

3. API

• API主要包括创建、删除tables和column families的函数，以及修改cluster、table、column family元数据的函数。

• clients程序可以在Bigtable上进行写和删除操作，在单行上查询值以及遍历table的某个子集的数据。

  • Example1，RowMutation对Webtable进行一系列修改更新
    • 
  • Example2，Scanner 对Webtable中一行内的所有 anchor 进行遍历。
    • 

• Bigtable 还提供其他的一些特性，使得用户可以对数据进行更复杂的控制。

  • Bigtable支持单行事务（single-row transactions），可以对单行内的数据执行原子性的读-修改-写序列操作。但目前不支持跨行的通用事务，尽管提供了跨行批量写的接口。
  • Bigtable允许每个cell被用作整数计数器。
  • Bigtable支持在服务器空间执行client提供的脚本，脚本语言是Google开发的Sawzall，这些基于Sawzall的API不支持client将数据写回Bigtable，翻允许多种形式的数据转换、求和等运算。

• Bigtable可以和MapReduce一起使用，Bigtable可以作为MapReduce计算的输入源或者输出目标。

4. Building Blocks

• Bigtable使用分布式的GFS来存储日志和数据文件。
• Bigtable 依赖一个集群管理系统来调度任务、管理共享的机器上的资源、处理机器故障， 以及监控机器状态。
• SSTable
  • Google使用SSTable文件格式来存储Bigtable的数据。
  • SSTable提供一个持久的、有序的、不可变的key-to-value map，键值都是任意字节字符串，同时提供查询指定键的值、在一个key range内遍历所有键值对的操作。
  • 每个SSTable内部都包含一系列的blocks，block size通常为64KB；block的索引被存储在SSTable的尾部用来定位该block，当SSTable被打开后，blocks的索引被加载到内存。
  • 通过单个磁盘寻址过程实现一个查询操作：首先通过二分查找在内存中找到指定的块索引，然后再磁盘中读取相应的块。另外SSTable也可以映射到内存中完成查询而不需要触碰到磁盘。
• Chubby
  • Chubby用于为Bigtable提供高可用和持久的分布式锁服务。
  • 一个 Chubby 服务由 5 个active replicas组成，其中一个会被选举为 master并负责处理请求。只有大多数replica都活着，并且互相之间可以通信时，这个服务才算活着。
  • Chubby基于Paxos算法保持replicas之间的一致性。
  • Chubby提供一个由目录和小文件组成的命名空间，每个目录或文件可以被用作一个锁，所有对文件的读写都是原子性的。
  • Chubby的client library提供Chubby files的缓存一致性，每个client都通过一个会话（session）与Chubby服务保持联系。当一个client的租约（lease）到期并且无法续约（renew）时，这个 session 就失效了。session 失效后会失去它之前的锁和打开的文件句柄（handle）。Chubby 客户端还可以在 Chubby 文件和目录上注册回调函数，当文件/目录有变化或者 session 过期时，就会收到通知。
  • Bigtable可以基于Chubby完成一系列任务：保证任何时间只有一个active master、存储 Bigtable 数据的 bootstrap location、tablet服务器的发现和服务器终止后的清理工作、存储Bigtable模式信息、存储访问控制列表。
  • 如果Chubby不可用超过一定时间后，Bigtable也变成不可用的。

5. Implementation

5.1 Overview

• 三个主要元件：一个可以链接到每个client的库，一个master服务器，多个tablet服务器，其中tablet服务器可以动态地添加或移除以适应workloads的变化。
• master负责将tablets分配给tablet服务器、检测tablet服务器的添加和到期、平衡tablet服务器负载以及 GFS 中文件的垃圾回收。同时处理Bigtable中schema的变化，比如table和column family的创建。
• 每个tablet服务器管理一组tablets（一般是10到1000个tablets），tablet服务器处理对tablets的读写请求，当tablets过大时进行切分。
• client的数据不会通过master，client直接与tablet服务器进行数据交互。Bigtable的client不依靠master来获得tablet的位置信息，大多数client并不与master通信。因此master的负载较轻。
• Bigtable集群会存储很多tables，每个table由很多的tablets组成，每个tablet存储一定的row range内的关联数据。每个tablets默认大小为100-200MB。

5.2 Tablet Location

• 用一个类似于B+树的三层结构来存储tablet的位置信息。

  • 

  • 三层结构：Chubby的一个文件 —— METADATA Table(Root + Other tablets) —— User Tables

    • 第一层是存储在Chubby的一个文件，包含root table的位置信息。root table用一个特殊的METADATA table保存了所有tablets的位置信息。每个METADATA tablet包含一组用户的tablets的位置。root table是METADATA table的第一个tablet，它从来不会被切分以保证存储tablet的位置信息的结构不超过三层。
    • METADATA table的每行数据在内存中大约占 1KB。如果将 METADATA tablet 限制在 128MB ，这种三层结构就可以存储高达 2^34 个 tablets和2^61 bytes。
• client library可以缓存tablet的位置信息，如果client不知道某个tablet的位置或者位置不正确，则通过该以上的三层结构查询。
• 如果client的缓存是空的，location算法需要三次网络往返（round trip），其中包括一次 Chubby 读取。如果client的缓存过期了，位置算法需要最多六次网络往返，因为只会在 cache miss 的时候才会检测缓存是否过期）。
• 虽然 tablet 位置放在内存，不需要 GFS 操作，但是，我们可以通过client预取的方式继续减少开销：每次从 METADATA table 读取的时候，都读取 多个 tablet 的元数据。

5.3 Tablet Assignment

• 每个 tablet 每次只会分配给一个 tablet server。master 会跟踪live tablet server以及当前 tablet 和tablet server 的分配关系， 包括还没有被分配出去的tablets。当一个 tablet 还未分配，并且找到有足够空间的tablet server可用，master 就会向这个 server 发送一个tablet 加载请求，将这个tablet分配给它。
• tablet servers
  • Bigtable使用 Chubby 来跟踪 tablet servers。当一个tablet服务器启动时，它会在特定的 Chubby 目录下创建和获取一个名字唯一的独占锁。 master 通过监听这个目录来发现 tablet servers。当tablet server失去它的独占锁时停止服务它的tablets，此后如果文件还存在，tablet server会尝试重新获得独占锁；如果文件已经丢失，tablet server无法再提供服务并终止和退出。当一个tablet server终止后，它会释放它的独占锁以便master快速重新分配它的tablets给其他servers。
• master
  • master 负责检测 tablet server是否工作正常，以及及时重新分配 tablets。
  • master通过阶段性地询问tablet server的锁的状态来监测tablet server 是否正常工作。当一个 server 报告锁已丢失，或者如果 master 连续多次无法连接到这个 server，master 就会尝试获得server上文件的独占锁。如果可以成功获取，说明Chubby是活着的而该server要么挂了要么和Chubby联系不上了，因此master通过删除server上的文件来保证它不再提供服务。删除后，master 就将原来分配给这个 tablet server 的 tablets 标记为未分配的（unassigned）。
  • 当一个 master 被集群管理系统启动后，它必须先查看当前的 tablet 分配情况，然后才能去修改。
  • master的启动流程
    • 从 Chubby 获取一个唯一的 master 锁，避免并发的master实例；
    • 扫描 Chubby 中的目录以获取live servers列表；
    • 通过和每个live tablet server通信，以了解当前tablets的分配情况；
    • 扫描 METADATA table，了解有哪些tablets；如果扫描过程中发现有还未被分配出去的 tablets，将该tablets加入到未分配 tablets 集合，以便后面进行分配。
  • complication
    • 只有METADATA tablets被分配出去之后才能进行METADATA table的扫描
    • 因此，执行步骤 4之前，如果在步骤 3 中发现 root tablet 还没有被分配出去，那 master 就要先将它加入到未分配 tablets 集合。 从而保证root tablet 将会被分配出去。
  • tablets变化的情况：创建、删除、两个小的tablets合并成一个大的，一个大的分裂成两个小的。master 能够跟踪这些变化，除了 tablet 分裂之外，其他变化都是由 master 处理的，而 tablet 的分裂会由tablet server通过再METADATA table上记录并提交分裂后的信息来实现，信息提交后会通知master。如果通知丢失，master 会在它下次要求tablet server加载 tablets 时获取该变化信息。

5.4 Tablet Serving

• tablet 的持久状态存储在 GFS 中
  

  • 所有的更新会提交到一个 commit log 文件，其中保存了 redo 记录。在这些更新中，最近提交的几次更新会存储在内存中一个有序的缓冲区Memtable，更老的更新则会存储在SSTable序列中。
  • 为了恢复一个tablet，tablet server会从METADATA table中读取相应的元数据，元数据包括组成这个 tablet 的 SSTable 列表，一系列指向 commit log 中 tablet 的数据的redo point。tablet server将 SSTable 索引读到内存，然后应用 redo 点之后提交的所有更新， 就可以重建 memtable。

• 写操作

  • 当tablet server收到一个写请求时，它首先会检查请求的发送者是否具有修改权限（通过从一个Chubby文件中读取允许写操作的写者列表）。
  • 一次有效的写操作会记录到提交日志中。通过允许批量提交可以提高小文件写入的吞吐，写操作被提交后，它的内容会被插入到 memtable。

• 读操作

  • 当tablet server收到一个读请求时，它首先会检查请求的发送者是否具有相应的权限。
  • 一个有效的读操作是在 SSTable 和 memtable 的合并视图上进行的，由于SSTable 和 memtable 都是按词典顺序排序的，因此可以高效地合并视图。

• tablet 分裂或合并时，读或写操作是可以进行的。

5.5 Compactions

• minor compaction
  • 当memtable的大小达到阈值时，memtable被冻结，一个新的memtable被创建，然后被冻结的memtable会转化为一个SSTable并写入到GFS中。
  • 两个目标：减少 tablet server 占用的内存、tablet server 挂掉之后恢复时，减少从 commit log 读取的数据量。
  • 每个minor compaction会创建一个新的SSTable
• merging compaction
  • 定期后台执行，以保证SSTable的数量在一定范围之内。
  • 从少数的SSTables以及memtable中读取内容，写入到一个新的new SSTable；一旦compaction完成后，原来SSTables和memtable中的内容即可以被删除。
• major compaction
  • 把所有SSTables合并成一个SSTable的merging compaction
  • non-major compaction 产生的 SSTable 会包含特殊的deletion entries ，用于标记其中已经被删除的数据但实际上这些数据还没有被真正删除。而 major compaction 产生的 SSTable 不会包含这些删除信息或者已删除的数据。
  • Bigtable 会定期地遍历所有 tablets，执行 major compaction 操作。这使得 Bigtable 可以及时回收已（被标记为）删除的数据占用的资源。

6. Refinement

6.1 Locality groups

• Clients可以将多个column families组成一个locality group，每个tablet中的每个locality group有一个单独的SSTable。
• 将一般不会一起访问的column families划分到不同的locality groups可以提高读性能。
• 在每locality group上还可以对一些有用的参数进行调整。例如，可以声明一个 locality group 是常驻内存的，常驻内存的 locality group 对应的 SSTable 会被惰性加载到 tablet server的内存。 一旦加载，这类 column family 的读操作就不再需要访问磁盘。

6.2 Compression

• 客户端可以控制 SSTable 是否需要压缩，以及用什么格式压缩。
• 压缩的基本单位是 SSTable block（大小可由 locality group 的特定参数控制）。 虽然 block 级别的压缩损失了一些空间，但在只需读取部分内容时，不需要解压整个文件，从而提高了读效率。

6.3 Caching for read performance

• tablet用两层缓存来提高读性能。
  • Scan Cache
    • high-level
    • 缓存SSTable 返回给 tablet server 的 键值对
    • 适用于频繁访问相同数据的场景（时间局部性）
  • Block Cache
    • low-level
    • 缓存从 GFS 读取的 SSTable blocks
    • 适用于趋向于连续访问相邻数据的场景（空间局部性）

6.4 Bloom filters

• 一次读操作需要对组成一个 tablet 状态的所有 SSTable 都进行读取，如果 SSTable 不在内存，必然需要多次磁盘访问。为了减少这种访问，允许clients在一个特殊的 locality group 内指定建立在某些 SSTables 上的Bloom 过滤器。
• Bloom 过滤器可以判断一个 SSTable 是否包含指定行/列对对应的数据。

6.5 Commit-log implementation

• 每个 tablet server 维护一个 commit log，将属于这个 tablet server 的不同tablets的修改操作都以追加的方式写入这个log 文件中。
• 优点：提高性能；缺点：恢复过程变复杂。
• 当一个 tablet server 挂掉后，tablets 会被重新分配给其他（大量）的 tablet servers，其他的tablet server都需要读取整个log文件然后把对应被分配到的一小部分tablets的日志过滤出来。
• 优化
  • 排序，将 commit log 内容以 <table; row name; log sequence number> 为键（key）进行排序，使得每个 tablet 的所有 mutation 都是连续的，从而实现高效的连续读。
  • 每个 tablet server 开两个写线程写commit log：每个线程写到各自的 log 文件，但同时只会有一个线程是活跃的。 如果当前的活跃线程写性能非常差，写操作就会切换到另一个线程，由这个新线程负责之后的写。log 中的记录都有序列号，恢复的时候可以根据序列号过滤由于 log 切换导致的重复数据。

6.6 Speeding up tablet recovery

• 如果 master 将一个 tablet 从一个 tablet server 移动到另一个，source tablet server 会先对 tablet 进行一次 minor compaction， 完成后source tablet server 停止为这个 tablet 提供服务。
• source tablet server 在真正unload这个tablet之前会再进行一次minor compaction，对第一次 minor compaction 到当前时刻内新进来的未压缩状态进行压缩。这次压缩做完之后，这个 tablet 就可以被其他的 tablet server 加载， 而无需恢复任何 log 记录。

6.7 Exploiting immutability

• SSTable是不可变的，从 SSTable 读取数据时，不需要任何同步文件系统的访问。
• 读和写操作涉及的唯一可变数据结构是 memtable。通过将 memtable 的行设计为copy-on-write，来允许读和写并行进行。
• 彻底删除数据实际上是对过期的 SSTable 进行垃圾回收。每个 tablet 的 SSTable 会注册到 METADATA table。master 会对过期的 SSTable 进行mark-and-sweep。
• SSTable 的不可变性可以加速 tablet 的分裂过程。