知名的文件管理系统： GFS，HDFS，Facebook Haystack，FastDFS ... ...

GFS是最著名的分布式文件系统，模仿者众多。

文件系统标准接口： （所有文件系统都必须提供）

  • 创建，
  • 删除，
  • 打开，
  • 关闭，
  • 读取，
  • 写入

拓展接口：（不是所有文件系统都提供）

  • 生成快照，便于数据多版本控制管理
  • 修改，节省修改操作效率 （GFS不支持随机修改）
  • 追加，修改的特殊场景，Append修改效率更高；

GFS

GFS, 大规模的分布式文件系统,用来处理分布型数据密集型的应用.

它提供了容错性,可以在廉价的硬件上运行,性能还不错. 与先前的共享文件系统相比, 设计考量。FS满足了当前公司的需要,广泛应用在Google的平台.

GFS也是为MapReduce，BigTable提供存储基础，是分布式框架的最底层依赖。

关键字: Design, reliability, performance, measurement

Introduction

数据增长, 处理需求的增长,

遇到了一些问题:

  • 组件故障(component failures)
  • 单个文件的尺寸越来越大, 超过GB级的文件成为常态.
  • 多数文件的修改是以追加方式的,像整个覆盖的场景相对少.

设计的Overview

文件系统需要有监测能力和自探能力,容错,可恢复
会存储大文件块, 平均大小估算是100MB或更大. 小文件也会支持, 不重点讨论.

能支持多个客户端并发在对同一文件进行追加写入,高带宽低延迟

单机文件系统过滤到分布式文件系统，再升级为GFS的过程，要解决的问题：

  1. 文件怎样分散在多台服务器上， 怎样实现多台机器间的负载均衡，自动扩容和缩容？

  2. 怎样知道一个文件在哪台节点机器上？

  3. 怎样保证服务器在故障时文件系统的可用性可选性？（CAP）

  4. 如果使用多个副本，怎样保证一致性？ （CAP）

  5. 性能要求，怎么支持大型文件（单个文件过GB）的存储

  6. 机器集群规模庞大时，怎样实现监控、容错与恢复。

  7. 怎样实现快速的顺序读和追加写？

    接口

基本操作是必要的, 如前面所述的六个标准接口：
create, delete | open close | read write

GFS 又提供了两个拓展接口： snapshot 和 append

架构

Master 设计

怎样知道一个文件存储在哪台机器上？ 文件位置即为文件的元数据之一，想象有一台NameNode是专门用来管理文件元空间的。
那么设计GFS集群是使用单Master还是多节点？

单中心节点的优点是实现成本低，一致性容易保证，缺点也极明显，单点容易导致单点故障，性能也极容易造成瓶颈。 优化策略是元数据的数据设计，减少单Master的压力。

多中心节点（分布式中心节点）
实现成本高，一致性难保证，系统可靠性难验证；
优点是解决了单点性能瓶颈问题，扩展性极强。

GFS选择的是单中心节点。

Files 被划分为 固定尺寸的 chunks ,每个chunk是全局唯一的(分配一个64bit编号).

Metadata存什么?
  • file 和 chunk 的 namesapces （持久化）
  • file到chunks的映射 （持久化）
  • chunk副本和节点Node的映射， 不持久化

所以可推断出GFS读一个文件的过程要有：
客户端提供文件名 -> 根据文件名获得chunk列表 -> 获取所有chunk的node location list -> 设计策略建立起到这些node lsit 的通信pipeline。

Chunkserver 就是记录这些chunk地址， 由chunkserver 向MetaServer通信，所以Meta不用持久化Chunk地址。

Chunk size, 主要的设计参数, 64MB. 它的元数据是小于64bit的， 假设一个文件有三个副本。
1TB的元数据有多大？
3TB副本总大小 除以 64MB * 64B 即只有3MB；
如果1PB数据，只有3GB元数据， 完全可以用内存管理。

太大,或者太小会怎样?
可见如果chunk太小，那么chunk数量将会增大， 对master内存会是不小的影响。
如果chunk太大，又会牺牲读取和写入数据的性能。

In-Memory 数据结构

metadata存储在内存中,便于master周期性的扫描全体chunk的状态.
扫描过程中,要实现chunk的垃圾回收, 副本拷贝, chunk平衡

Chunk 位置

Master对一份chunk,不会一直保存它的信息.
它只是在启动时向chunk server轮询, 此后master让自己保持最新状态,通过HeartBeat message机制.
GFS的所有数据流不经过master，而是直接由client和chunkserver交互。

Operation Log

操作日志存什么, 元数据变动的记录. Op Log非常重要,不能直接交给Client访问.
除了访问控制,还要对其进行多副本,

Master恢复文件状态,要借助于Op Log的replay.
为了缩短重启的时间,要尽量保持op log的尺寸不要太大.

所以这里还另设计了checkpoint, 当op log过大, 先从硬盘上的checkpoint 读取最新的一个快照, 并且重放日志也只重放这个cehckpoint之后的操作.

checkpoint 是以一种B树形式,建立一个cp会花一点时间,master希望是在不延迟的前提下完成创建.
master 切换到一个新日志文件,并在一个单独线程创建新cp, 恢复只需要最新的完整的cp和后续日志文件.

一致性模型 Consistency Model

GFS 的保证

File Namespace变动(创建文件,删除)是原子的, 由master排它性操作. (有锁)
master的Op Log定义了这些操作的全局有序性.

尽量避免master内存成为系统瓶颈，GFS采用一系列手段节省master内存，包括增大chunk大小，节省chunk数量，对元数据进行定制化压缩。

BigTable

A Distributed Storage System for Structured Data

Bigtable 是分布式存储系统，管理超大规模的数据 —— PB级+上千个节点。 在Google有诸多项目使用到了BigTable， 网页索引，Google Earth， Google Fiance。 对于BigTable不同应用服务有各自的需求，覆盖不同量级的数据尺度，既有延迟查询也有实时服务。 在这篇文章中，将会介绍Bigtable的数据模型，满足不同客户的动态控制数据格式和Schema。

Introduction

  1. BigTable历经2.5年的光阴，设计果成。
  2. 用于结构化数据， 格式后面说。
  3. 达成目的，应用范围广泛，扩展能力强，高性能，高可用
  4. 成果， BigTable在Google内部已经在几十个项目应用了，如摘要所述。
    4.2. 支撑离线任务 上千个
  5. 实现上，Bigtable类似一个数据库，又与常规的分布数据库和内存数据库不同
    5.2Bigtable 不支持全面的关系数据模型
    5.3 数据索引非常灵活
  • Section2: 介绍Data Model
  • Section3: 客户端的API
  • Section4: 对Google infrastructure的依赖
  • Section5: Bigtable实现的基础
  • Section6: 提升Bigtable性能的设计
  • Section7: 性能衡量
  • Section8: Google的应用案例
  • Section9: 踩过的坑
  • Section10: 相关工作
  • Section11:总结

Data Model

数据模型上， Bigtable是一个稀疏的、分布式的、持久化的多维度有序map。

map的索引： row key, column key + 时间戳； value，未被翻译的 bytes array

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

  • row key, 表中的row key 可以是任意字符串， 上限为64KB，一般来说约10-100个byte；

  • sorted， 基于row key的字典序

  • partition, row range 动态分区

  • tablet, 每段row range 称为 tablet, BigTable的分布单元，读小段的row ranges只需要和几台节点通信，效率很高。

  • URL的组织技巧，类似于Java中的 package 包名， maps.google.com/index.html 会转为 com.google.maps/htmls, 存储更有效率

  • Column Families， column keys被分组，编成column families，提供了最基础的访问控制。

  • 同一Column Families存储的列是相同数据类型（便于压缩）

  • CF的创建时机，要在数据存入之前创建

  • 设计意图： 一个表中的CF应控制在几百之内

  • CF中的列key命名规则， family:qualifier

  • 访问控制，在硬盘和内存级别，按CF进行控制：添加新数据、读取数据、创建衍生的CF.

Timestamps

在BigTable中每个Cell都有版本的概念，BigTable用Timestamps -- 用Int64来存储，在现实世界中精度可达毫秒级时间(Sample format 2002-11-15 14:10:13.123456)

API

BigTable 提供了一系列的操作表和CF的API，以及修改和更新集群的操作。举例：

RowMutation 是指行级的更新操作。

Table *T = OpenOrDie("/bigtable/web/webtable");
RowMutation r1(T, "com.cnn.www");
r1.Set("anchor:www.c-span.org", "CNN")
r1.Delete("anchor:www.abc.com");
Operation op;
Apply(&op, &r1);

Bigtable也能执行MapReduce的应用。
我们已经实现了一系列的基于Bigtable输入或输出的MR Job。

Building Blocks

Bigtable 用到了Google的GFS来存储日志和数据文件。
Bigtable需要 集群管理系统，能满足任务调度，资源管理及机器状态监控的需要。

Google SSTable是用来存储Bigtable数据文件的文件格式， SSTable是持久化的，有序的不可变map（key和value 均不可变）。 SSTable是由 block sequence 组成， 每个block是64KB（可配置），并且另外设置了Index 文件，用来定位和寻址block。当SSTable被打开时，内存将会加载到内存。

内存遍历会使用对block索引的二分查找，然后将block从磁盘进行读取。
可选地，SSTable也能被完全的加载到内存，可以在不经磁盘的情况下进行查询。

Bigtable用的高可用的分布式服务称为Chubby， Chubby的一篇paper为 The Chubby lock service for loosely-coupled distributed systems . 我会在未来适当的时机再去拜读。

Chubby服务由五个活跃的副本组成：一个用来选举成为master，提供需求承接。 整体服务只要有半数活着即为可用。 Chubby使用了共识性算法Paxos，以保证一致性。

每个目录或者每个文件，都可视作是一个锁，对文件的读和写都得是原子操作。

Chubby可视作是zookeeper的前身。

Bigtable用Chubby完成一系列任务：

  • 确保任何时刻只有一个活跃的master；
  • 存储Bigtable bootstrap的位置
  • 存储Bigtable schema信息（每个表的CF）
  • 存储访问控制列表

如果Chubby不可用，Bigtable也将不可用。

Implementation

Bigtable由这三个部分组成：

  • client library，与外部的client连接，缓存一些表的位置
  • master server，负责将表分配到tablet server,监控tablet server数据的新增、过期废弃，tablet-server的平衡，GFS文件的GC。 除此之外，还负责处理table和CF的元数据变更。
  • 若干tablet servers， 支持动态扩展。 每台tablet server管理一系列的表，处理客户端对table的读和写请求，当table增长得过大时，也负责拆表，每个表控制在100-200MB。

Bigtable的客户端不直接和master做数据层面的通信交换，而是和tablet server进行数据的读和写。

Tablet Location

🤓

Tablet的存储第一级是在Chubby， 包含root tablet(根表)位置；
第二级 根表 包含所有tablets, 用一张特殊的表来存储，即 METADATA table; 每个元数据表存储 user table 分表的所在位置。 METADATA 表 永远不会被拆分（以保证中间层不会裂变）。
第三级 用户表 即用户取用的表。

当client library 查询时发现缓存中没目标表，或者发现缓存位置失效，将会递归向上移动这个表的location。cache空或者信息过期了，有对应的刷新策略。

Tablet Assignment

每个Tablet在同一时间只会分配给一个tablet server.
Master会时刻跟踪tablet server的状态，当前tablets的分配情况、未分配状态。
如果一个tablet未被分配，某个tablet server拥有充足的空间，master 会将这个tablet分配给它。

Bigtable用Chubby来跟踪tablet节点， 当一台tablet启动，会获得一个排它性的锁。

这个分布式锁即为tablet Chubby目录下的一个全局唯一的目录。

Master通过监控这个目录来洞察tablet server。
如果tablet server 失去了锁，也就停止对表的服务。
（Chubby提供了能够快速查验当前节点是否还持有这个锁的机制）

Tablet节点如果发现自己手上还有锁文件，也会进行重试请求。
当tablet server终止服务，也会放弃锁。

如果Master发现这台Tablet server不能再为某表提供服务，会执行reassign (重分配)。

Master会周期性的底部和绐Tablet节点的锁状态。

当集群系统启动Master，它需要发现当前tablet分配，以便更新它们。
Master会在启动时执行以下步骤：

  • master 在Chubby 获得一个唯一的 master lock , 防止并发的master实例化
  • master 扫描Chubby中servers目录，以找到正在活跃的server
  • master与每台活跃的server通信，以发现哪些tablet已经被分配了
  • master扫描METADATA表，来掌握table集合

每当遇到尚未分配的tablet时，master就会将tablet添加到未分配的tablet。

只有在创建或删除一个表时，现有tablet集合才会发生变化，两个现有的tablet合并成为一个大表，或者一个大表拆分成两个小表。

Table Serving

tablet的状态持久化使用GFS， 更新的操作写到提交日志（redo records), 近期修改使用内存表memtable， 老的操作则使用 SSTables。

当还原一个Tablet时，tablet server从METADATA表读取这个表的元数据，元数据中包含一系列SSTable，将SSTable内存读到内存，从redo 点位进行重建memtable.

当Tablet server收到写操作时，server先检查格式的有效性。
有效的写操作会被提到的commit log，将很多小型的操作commit编组能提升性能。

当Tablet server收到读操作，会进行类似的格式检查。
对操作作用于 SSTable和memtable的合并视图（mergedview ）。 因为SSTable和memtable是按字典序排序的，所以mergeview是很容易形成。

Compactions 规整

minor compaction

因为写操作会造成memtable的增长，当这个内存表达到阈值，需要进行先frozen 冻结， 创建一个新memtable， Frozen memtable再被写到磁盘（GFS的SSTable）。
这样做有两个目的，减少tablet server中内存消耗； 当server挂的时候降低还原的成本。

每个这样的minor compaction 都会创建一个新的SSTable。 如果这种操作不进行限制，读操作可能需要合并来自任意数量的SSTable。 因此我们限制了此类文件的数量 —— 通过执行 merging compaction。
合并的compaction 会对所有SSTable写到一个SSTable， 这个过程称为**major compaction **。
(这个过程很像 MapReduce Mapoutput 的过程)
Non-major压缩产生的SSTable可能产生特定的文件，这些文件包含了被删除的条目信息。 而Major-压缩不会包含这些删除信息。 Bigtable会循环遍历所有tablet，并定期对它们使用major-压缩。 这些major-压缩允许Bigtable回收被删除数据使用的资源，也允许它确保被删除的数据及时从系统中消失，这对于存储敏感数据的服务非常重要。

Refinements

为了提供高性能的服务，需要进行一些特殊设计。

Locality groups

Client侧对CF成组，称为locality group.

Compression

Client可以控制 对于locality group 的对应SSTable是否要压缩。

Caching for read performance

提升读的性能。 引入二级缓存机制。

Scan缓存： 高级别缓存，提供Key-value的键值对，返回SSTable接口。

Block缓存：低级别缓存，保存SSTable block的读信息。

Bloom filters

使用Bloom过滤器，用于判定SStable是否包含特定数据。

Commit-log implementation

Performance Evaluation