关于nosql:分布式存储论文研读二BigTable

首先和论文无关，还是想分享一下来自 Malte Schwarzkopf 博士毕业论文 Operating System support for warehouse-scale computing 的一张 Google 根底服务架构图：

GFS 和 Bigtable 都在其中，关系高深莫测。

Data Model

Bigtable 从实质上来讲应该相似于一种 NoSQL 数据库，同时又提供了一般的数据库所没有的接口。它的数据模型如下：

(row:string, column:string, time:int64) -> string

之后的一些 NoSQL 数据库如 Cassandra，HBase 等均有相似构造。构造中有以下几个组成部分：

• Row：能够看作每条数据是一行，对一行数据的读写操作是原子的。Bigtable 会对 row key 进行字典序排列，只管每张表的行范畴分区随机，但设计良好的 row key 就能使相干数据相邻间断排列。读取时也只须要拜访多数几台机器。
• Column：column key 会被组织成 column family，语法是 column:qualifier。column family 中几个 key 的取值类型个别雷同，设计心愿 column family 是事后设计好的，比拟固定，且数量不多（但 column 的数量不限）。column family 是访问控制的最小单位。
• Timestamp：工夫戳最重要的性能是记录同一个值的不同版本。同时也能针对 column family 定义管理机制：只保留多久版本的记录，或保留最近几个版本。

API

Bigtable 提供了一系列 API 供用户进行数据操作。有几个要点：

• 容许应用正则匹配列名，对匹配后果加以限度。
• 反对单行的事务。不反对跨行事务。
• Integer 数据可用作计数器。
• 反对在服务器地址空间执行客户端提供的脚本。

反对脚本，但脚本不能写回 Bigtable 是什么意思？脚本不能写入数据，但能进行数据转换，数据过滤，数据汇总等“查问”类操作。

Bigtable 的一大特点就是反对配合 MapReduce 应用。

Building Blocks

Bigtable 作为比拟下层的利用，依赖于一系列 Google 产品。

首先它的数据和日志文件是存储在 GFS 上的。

其次，它存储数据的数据结构是 Google SSTable，这种数据结构将数据分为小块（64KB），并作索引。不便查找和映射到内存空间。

Bigtable 还依赖于分布式锁服务：Chubby。Chubby 具备较高的可用性，通常会维持 5 个分片并选举一个 master。应用 Paxos 算法来保障分片一致性。Chubby 提供一个由目录和文件组成的命名空间（namespace），每个目录或文件都能够作为锁，保障读写一个文件是原子操作。应用 Chubby，Bigtable 能够：

• 保障只有一个 master 节点（Bigtabled 的 master 节点，可持续看下一章）；
• 存储 Bigtable 数据的 bootstrap 地位；
• 存储 Bigtable 的 Schema 信息；
• 存储 Bigtable 的 access control 列表。

Implementation

Bigtable 零碎由三大部分组成：

• 一个所有客户端连贯的 library。
• master 服务器负责调配分片到分片服务器，探测新退出和过期的分片服务器，平衡分片服务器负载，做 GFS 文件的垃圾回收，以及解决 schema 变动。
• 分片服务器治理一系列分片，解决分片的读写申请，数据都不会通过 master 节点。同时分片服务器也会对过大的分片进行切片。最终的分片大小大略在 100-200MB 左右，合乎 GFS 的存储特点。

Table Location

下图是 Bigtable 中 tablet 的分层构造：

第一层的 Chubby 蕴含了 root tablet 的地位，root table 是 METADATA table 的第一个 tablet，存储了其余 MEATADATA tablet 的地位，且不可拆分，保障了整体最多三层的构造。METADATA tablet 存储了各张表的地位，每条记录 1KB 左右，METADATA 总大小限度在 128MB，曾经足够绝大多数零碎应用。

在此架构上，一个 client 进行寻址须要拜访 3 次（从拜访 Chubby 开始），如果缓存过期，则最多须要 6 次访问。且只须要拜访内存数据。同时还会通过一次性读多个 tablet 来预读取进行进一步优化。

为什么缓存生效时须要读 6 次？缓存的具体是什么？这不是意味着不必缓存更好么？

Table Assignment

Bigtable 应用 Chubby 来追踪 tablet server 的在线状况。在线的 tablet server 会继续占有一个特定文件的锁，如果锁被开释则 server 也进入不可用状态。如果有一个 tablet 没有被调配，又有适宜的 server，master 就会向对应的 server 发送 tablet load 申请。

应用锁来断定服务是否存在是一个很乏味的办法，具体的逻辑如下：

1. master 发现有 server 开释了锁，或是某个 server 的最近几次申请均失败。
2. master 尝试申请该 server 占有的锁。
3. 获取锁胜利，阐明 master 和 Chubby 存活，server 宕机，master 删除该 server 信息，进行 tablets 的重新分配

如果 tablet server 意外宕机，并没有被动开释锁，那么锁何时会开释？是否是通过过期工夫？

而如果 master 无奈和 Chubby 通信，本人的 session 过期，就会被动 kill 本人。此时重启一台 master，做如下操作：

1. 向 Chubby 获取一个 master 锁，保障没有其它的 master 节点启动。
2. 扫描 Chubby 中的 server 信息。
3. 和每个 tablet server 交互获取 tablet 调配信息。
4. 扫描 METADATA table，没有被调配的 tablet 放入未调配组，期待进行调配。

tablets 会产生新建，删除，合并和决裂操作，前三者均有 master 发动，最初一点由 tablet server 触发，并会将记录上报给 METADATA table，并告诉 master。

Tablet Serving

Tablet 的工作流大抵如下图：

当写申请来时，会进行权限校验，而后记录到 tablet log 中去。最新的批改存入内存中的 memtable，老的申请写到 GFS 上的 SSTable Files 中去落盘。

如果须要复原一块 tablet，就须要从 METADATA 中读到它的 SSTable 地址，以及一些日志中的 redo points，将 SSTable 读到内存并重做日志记录，重构 memtable。

对于读申请，则在权限校验后，将须要的 SSTable 内容和 memtable 内容组合起来发给 Client。

Compactions

对于上一大节中写操作，具体来说，当 memtable 一直变大并达到肯定阈值时，就会被解冻并由一个新的 memtable 承受输出。被解冻的 memtable 则转化为 SSTable 存入 GFS。此时就能清理 server 的内存，同时也能够缩小 log 中的对应日志。这一操作被称为“minor compaction”。

而因为通过 minor compaction 生成的 SSTable 比拟小，后台任务还会定时合并这些 SSTable 和 memtable 到一个 SSTale 中去，称为“major compaction”。在 minor compaction 中生成 SSTable 可能蕴含已删除的数据，而在通过 major compaction 后就会理论删除数据，回收对应空间。

Refinement

在理论应用过程中，还能够通过很多形式对 Bigtable 进行调优：

• Locality Groups：Client 能够将通常一起应用的 Column family 组织在一起成为一个 locality group，在每个 table 中，不同的 locality group 能够存入不同的 SSTable，晋升读取效率。同时还能够设置 locality group 通过懒加载放入内存，这对小量高频数据是否无效，例如零碎中的 METADATA table。
• Compression：Client 能够设置将 locality group 压缩在一起，并指定压缩格局。能够拆散压缩 locality group，尽管会有一些空间损失，但独自读取某个 group 就不再须要解压了。Client 罕用自定义的两轮压缩：第一遍是 Bentley and McIlroy’s scheme，第二遍是应用疾速压缩算法。对语义相近的数据进行压缩，压缩比会很高。
• Caching for read performance：为了进步读效率，能够进行双重缓存。Scan cache 缓存键值对，Block Cache 缓存读到的 SSTalbe block。Scan cache 有利于一直读取同样的数据，而 Block Cache 则利用局部性疾速读到相邻的数据。
• Bloom filters：应用 Bloom filter 容许操作时过滤掉不蕴含所需行列的 SSTable，从而缩小磁盘读写。
• Commit-log implementation：在实现 commit log 时，每个 tablet server 只读写一个 log 文件。这样会大大优化读写 log 文件的效率，但在 tablet 复原时会比拟苦楚：每复原一个 tablet 都须要读所有的日志。此时会先对日志记录进行按 <table, row name, log sequence number> 的排序。作排序时，会把 log 文件切分成 64MB 的小块，并行进行。为了防止一些网络问题等阻塞，每个 tablet server 写日志会有两个线程，每个线程写本人的 log 文件。同一时间只有一个线程沉闷，在以后沉闷线程性能不佳时进行切换，并通过对日志编号革除反复写入的局部。
• Speeding up tablet recovery：在 tablet 进行转移时，会先作一次 minor compaction，缩小须要从 log 中复原的操作。实现后，server 不再对该 tablet 提供服务，此时再对第一次开始 compaction 后又进入的操作做第二次 minor compaction。这样迁徙到新的 server 后就不须要做任何的从 log 复原的工作。
• Exploiting immutability：在服务过程中，SSTable 是不变的，不须要做并发管制。只有 memtable 是一直变动的。这样了解：存入 SSTable 后数据不变，变动都存在 memtable 中，在 compaction 时才会把变动落盘到 SSTable。

Performance Evaluation

这一章还是一贯的试验验证环节。试验后果当然表明 Bigtable 设计不错，但也有几点值得注意：

• 随机读的性能比其它操作性能都差。或者说读性能（从磁盘）要差于写性能。起因是读操作须要将数据从 GFS 将不同的 SSTable 内容读到 tablet server，每读 1000byte，就须要把整个 64KB 的数据读出。所有的写操作只是写入日志，而后应用批量 commit stream 高效地写给 GFS。而 Scan 操作可能更靠近于咱们平时了解的读操作，其性能也最好。
• 随机写和程序写性能没什么差异，因为它们的操作是统一的。

Real Applications

Google 外部有不少零碎应用了 Bigtable 来进行存储。2006 年 8 月时，就有 388 个 Bigtable cluster，应用了 24,500 台 tablet server。实在利用包含 Google Analytics，Google Earch，Personalized Search 等。

Lessons

在构建分布式系统的过程中，Google 工程师经验了很多种类型的服务生效。分布式服务自身是很软弱的。

另一点教训是工程迭代时，放缓上新特色的速度，把新个性的用处探索分明。

第三点是零碎级别的监控很有必要，可能帮忙疾速定位问题。

而最重要的一点则是简洁的设计很有价值。可能领导整个工程的开发。

而我读完文章的次要感触是：文章中充斥了各种工程设计和优化细节，这些工程细节通常都是最初的 10%，也是把一个不错的零碎变成一个优良零碎的 10%。做任何事都不能漠视最初的 10%。

Six Questions

这个技术呈现的背景、初衷和要达到什么样的指标或是要解决什么样的问题。

相较于比拟底层 GFS 文件存储系统，Bigtable 曾经运行在业务档次，会要求数据进行结构化。其本质靠近于一个分布式的数据库。在有了 GFS 后，Google 工程师面临的一个事实问题就是：如何利用分布式文件系统将结构化的数据存储下来？更明确一些的需要，例如：如何将 Google 将要应用到的宏大的网页索引数据存下来，能做到疾速的拜访，还能很好地做版本保护？另外，Google 还有很多的机器学习工作，须要在后盾拜访十分大的数据集，这部分申请对延时就不太敏感。这些场景能够集成在一个数据库中吗？

这个技术的劣势和劣势别离是什么，或者说，这个技术的 trade-off 是什么。

面对分布式系统，一个必须要谈的 trade-off 就是 CAP。P 是不可避免的，而 Bigtable 更加重视 C，通过 Chubby 来实现一致性。但会就义肯定的可用性 A（当呈现分区时，间接干掉不能通信的节点）。

另外，Bigtable 实现了行的原子性操作，实现了 key-value 模式的 NoSQL 存储，但放弃了跨行的事务操作。

这个技术应用的场景。

如第一问中所述，Bigtable 被理论利用于 Google 的很多产品中，从 Google 搜索引擎的网络索引，到 Google Earth 的地理信息等等。作为一个 NoSQL 的数据库，同时是一个相似于“宽列”数据库，它实用于对“关系”没有强烈要求的利用。且最好是须要大量程序读取数据的场景。

技术的组成部分和关键点。

Bigtable 的组成部分有三个：客户端接入的 library，一台 master server 和许多的 tablet server。

技术的底层原理和要害实现。

Bigtable 自身应用 GFS 来存储文件，同时应用 Chubby 来解决分布式锁。而对于同一个数据的更新，Bigtable 应用了 Log-Structured Merge Tree 来记录。

已有的实现和它之间的比照。

依据论文的相干工作，可比拟的实现包含：Boxwood，CAN，Chord，Tapestry，Pastry，Oracle 的 Real Application Cluster Database，IBM 的 DB2 等。

与 Boxwood 相比，Boxwood 与 Chubby+GFS+Bigtable 的性能有不少重合处。在性能重合的点上，Boxwood 的组件更加底层，其指标是为更高层的服务，例如文件系统或数据库来提供基础设施。而 Bigtable 则是间接反对利用来存储数据。

CAN，Chord，Tapestry 和 Pastry 这些分布式数据存储系统工作在一个不受信赖的网络上，不稳固的变动的带宽，不受信赖的客户端，频繁的配置更改以及拜占庭将军问题等是这些零碎关注的重点。

Real Application Cluster Database 和 DB2 均应用事务实现了残缺的关系模型。

有不少零碎和 Bigtable 一样，应用了列式存储而非基于行存储，包含 C -Store，Sybase IQ，SenSage，KDB+，MonetDB/X100 的 ColumnBM 存储层等。

文中还列举了一些细节实现上的差别，这里还要讲一下在此之后实现的 Amazon DynamoDB，DynamoDB 最大的区别就是更加偏向于实现 AP 而非 CP，具体在前面的博客中形容。