首先和论文无关，还是想分享一下来自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，具体在前面的博客中形容。