GFS
  • 要点
    • 和其他分布式文件系统进行比较, 这个容易被问到我觉得
    • 实现的时候给出自己的创新, 可以优化某一个部分
    • 要有性能测试, 因为给出了性能的比较才知道自己做的怎么样
    • 关于容错与故障, 这部分应该会很难搞
    • 移动计算, 而不是数据
  • 理解各个部分
    • 单一master特点
    • master日志
    • master的元数据
    • 数据流与控制流
    • 一致性模型
    • 租约lease模式
    • 读写特点 (数据流)
    • 快照
    • master的文件名称空间以及读写锁模式
    • master分配chunk位置
    • 垃圾回收(惰性删除)
    • 版本号与失效检测
    • 高可用性(快速恢复和复制)
    • 数据完整性 checksum
    • master的备份
  • 概述
    • 设计预期
      • 系统由许多廉价的普通组件组成，组件失效是一种常态
      • 系统存储一定数量的大文件 (数G数T大小的文件普遍存在)
      • 系统也必须支持小文件，但是不需要针对小文件做专门的优化。
      • 系统的工作负载主要由两种读操作组成：大规模的流式读取和小规模的随机读取
      • 系统的工作负载还包括许多大规模的、顺序的、数据追加方式的写操作
      • 系统必须高效的、行为定义明确的2实现多客户端并行追加数据到同一个文件里的语意
      • 高性能的稳定网络带宽远比低延迟重要。
    • 对外接口
      • 创建, 删除文件
      • 读, 写文件
      • 打开, 关闭文件
      • 快照
        • 快照以很低的成本创建一个文件或者目录树的拷贝
      • 记录追加操作(原子)
        • 记录追加操作允许多个客户端同时对一个文件进行数据追加操作，同时保证每个客户端的追加操作都是原子性的
        • 这对于实现多路结果合并，以及“生产者-消费者”队列非常有用
        • 多个客户端可以在不需要额外的同步锁定的情况下，同时对一个文件追加数据。
  • 架构
    • GFS重要组件
      • client
        • 与用户交互的组件, 一个系统里支持同时很多client同时运行
        • client需要向master询问它需要联系的chunk server(控制流), 后续直接和server进行读写操作(数据流). 减少master负载
        • client要读取时, 需要传递 "文件名", "文件偏移范围" 给master, master返回***
      • master
        • master保存三种类型的元数据: 文件和 Chunk 的命名空间、文件和 Chunk 的对应关系、每个 Chunk 副本的存放地点
          • namespace
          • filename -> chunk id
          • chunk id -> chunk server 地址 (不会持久保存, 轮询得到)
        • Master 服务器不会持久保存 Chunk 位置信息。
          • Master服务器在启动时，或者有新的 Chunk 服务器加入时，向各个 Chunk 服务器轮询它们所存储的 Chunk 的信息
          • chunk server 的chunk的数据结构是怎么样的, 如何告知master某chunk是属于master的哪个chunk id的
        • Master 服务器能够保证它持有的信息始终是最新的, 因为
          • master控制了所有chunk的分配
          • 而且通过周期性的心跳信息监控 Chunk 服务器的状态
        • master对元数据的操作需要持久化到日志中. 且持久化之后日志才对客户端可见
        • master 如何分配副本的位置?
          • GFS论文中没有提供足够的细节, 需要进一步探索
          • 几个变量
            • chunk的有效副本数量
            • chunk副本的复制因子
            • 当前server存储的chunk数量(磁盘利用率)
            • 一个server上正在进行的复制操作数量(负载均衡)
          • 几个要点
            • 在低于平均硬盘使用率的chunk服务器上存储新副本
            • 当 Chunk 的有效副本数量少于用户指定的复制因数的时候，Master 节点会重新复制它
              • 一个 Chunk 服务器不可用了，Chunk 服务器报告它所存储的一个副本损坏了
              • Chunk 副本的复制因数提高了
            • 先对哪个副本进行复制有优先级
              • Chunk 现有副本数量和复制因数相差多少
              • 优先重新复制活跃（live）文件的 Chunk 而不是最近刚被删除的文件的 Chunk
            • master周期性地对副本进行重新负载均衡
            • 当一个新的chunk服务器来到时, 系统是逐渐填满它, 而不是短时间内填满
              • master需要选择哪个服务器的副本要转移
        • master的文件名称空间
          • 不提供列举目录下文件的数据结构, 而是一个查找表
          • 在逻辑上，GFS 的名称空间就是一个全路径和元数据映射关系的查找表。(hash?)
          • 利用前缀压缩(字典树?)，这个表可以高效的存储在内存中
          • 在存储名称空间的树型结构上，每个节点（绝对路径的文件名或绝对路径的目录名）都有一个关联的读写锁。
          • 每个 Master 节点的操作在开始之前都要获得一系列的锁
            • 如果一个操作涉及/d1/d2/…/dn/leaf
            • 那么操作首先要获得目录/d1，/d1/d2，…，/d1/d2/…/dn 的读锁
            • 以及/d1/d2/…/dn/leaf 的读写锁。
            • 注意，根据操作的不同，leaf 可以是一个文件，也可以是一个目录。
        • 垃圾回收
          • GFS 在文件删除后不会立刻回收可用的物理空间。GFS 空间回收采用惰性的策略
          • 过程
            • 当需要删除一个文件时, 首先记录删除日志
            • 将这个文件改成一个特殊的文件名, 带有删除时间戳, 隐藏的名字
              • 可以将隐藏名字改为正常名字来实现删除的撤销
            • master 节点对文件系统命名空间做常规扫描的时候, 会删除3天前(可设置)的隐藏文件
            • 当隐藏文件名被删除之后, master才会删除它的元数据. 这个时候chunk server并不会删除文件
            • 在对 Chunk 名字空间做类似的常规扫描时，Master 节点找到孤儿 Chunk（不被任何文件包含的 Chunk）并删除它们的元数据。
            • 在chunk server和master心跳的时候, server会报告他所有的chunk子集, 然后master判断哪些chunk已经不存在了.
              • 这时chunk server就可以删除这些文件, 至此这个文件名对应的该副本文件就被删除了
          • 注意
            • 论文中的 "文件元数据"跟"chunk元数据"是不一样的
              • 文件映射多个chunk, 每个chunk映射多个chunk server 位置
              • 先会删除文件元数据, 这样它映射的chunk就变成了孤儿, chunk元数据删除之后, server才可以删除
            • master有两种常规扫描
              • 一种是文件元数据常规扫描
              • 一种是chunk元数据常规扫描
              • 不过论文中没有提到这两种扫描的时间
          • 优点
            • chunk可能在某些chunk服务器上创建失败, 处于无法识别的状态
            • 副本删除的消息可能丢失, 这样master就需要重新发送, 这样会造成一些不可靠
            • 惰性垃圾回收将回收操作合并到 Master 节点规律性的后台活动中, 开销会分散
            • 延缓存储空间回收为意外的、不可逆转的删除操作提供了安全保障。
              • 数据不会马上删除
          • 缺点
            • 延迟回收会阻碍用户调优存储空间的使用，特别是当存储空间比较紧缺的时候。
              • 当应用程序重复创建和删除临时文件时，释放的存储空间不能马上重用。
              • 我们通过显式的再次删除一个已经被删除的文件的方式加速空间回收的速度
        • 版本号与失效(过期)检测
          • 当 Chunk 服务器失效时，Chunk 的副本有可能因错失了一些修改操作而过期失效
          • 只要 Master 节点和 Chunk 签订一个新的租约，它就增加 Chunk 的版本号，然后通知最新的副本
            • 搞清租约原理, 因为我认为每一次写操作都应该递增. 那么一次租约包括多少范围的操作?
          • Master 节点在这个 Chunk 服务器重新启动，并且向 Master 节点报告它拥有的 Chunk 的集合以及相应的版本号的时候，就会检测出它包含过期的 Chunk。
          • 如果 Master 节点看到一个比它记录的版本号更高的版本号，Master 节点会认为它和 Chunk 服务器签订租约的操作失败了，因此会选择更高的版本号作为当前的版本号。
      • chunk server
        • 当需要变更的时候, GFS使用租约(lease)来保证系统复制的一致性
          • master选定一个chunk server来作为主chunk, 减轻master负担
          • 主 Chunk 对 Chunk 的所有更改操作进行序列化。所有的副本都遵从这个序列进行修改操作
          • 租约的初始超时设置为 60 秒。不过，只要Chunk 被修改了，主 Chunk 就可以申请更长的租期，通常会得到 Master 节点的确认并收到租约延长的时间
          • 租约延长请求和批准的信息通常都是附加在 Master 节点和 Chunk 服务器之间的心跳消息中来传递
        • 数据完整性 checksum
          • 每个chunk服务器独立维护checksum
            • GFS允许有歧义的副本存在, 并不保证副本完全相同
          • 校验模式
            • 把每个chunk(64MB)分成64KB大小的块, 每个块对应一个32位(4B)的checksum
              • 一个chunk对应1024*4B = 4KB的总checksum
            • checksum和数据分开, 保存在内存和硬盘上, 同时记录操作日志
              • 保存在内存上意味着查找效率会非常高
              • 硬盘上应该是为了持久化防止崩溃造成数据损失
            • 当要读取chunk时, 服务器会校验该部分块(注意是块而不是chunk)内的checksum
            • 如果某个块的checksum不正确, 那么服务器就会返回给请求者一个错误信息, 然后通知master这个错误
              • 请求者会从其他副本读取数据
              • master则会从其他副本克隆数据进行回复
          • 性能评估: 注意分析checksum带来的代价(证明不怎么会影响性能)
            • checksum的查找和比较不需要IO操作(因为checksum存在内存上)
            • checksum的计算可以和IO操作同时进行, 也就是边读取边在内存上计算与验证
          • checksum的计算针对在chunk尾部追加写入操作做了高度优化(但是优化是啥...)
            • 每次只需要不断对最后一个小块的校验和进行更新
            • 这里也需要先验证吧?
          • 指定偏移量覆盖写来说，在写入前必须先对要写范围对应的首尾小块做验证
            • 因为他们可能是部分写，不经验证直接部分覆盖的话，可能会隐藏原来数据块已经损坏的事实。
          • 在chunk服务器空闲的时候, 他会扫描和校验每个不活动的chunk的内容
            • 所以chunk服务器需要对chunk标记是否活跃的状态吧
            • 这个机制也避免了非活动的、已损坏的 Chunk 欺骗 Master 节点，使 Master 节点认为它们已经有了足够多的副本了。
    • 系统交互
      • 在设计这个系统时，一个重要的原则是最小化所有操作和 Master 节点的交互
      • 租约 lease
        • 目的: 保持多个副本间变更顺序的一致性 (也就是以同一顺序进行变更, 而不是分散的)
          • 进行副本复制时, 是链式结构, 而不是星形结构
        • master选择一个副本建立一个租约，我们把这个副本叫做主 Chunk
        • 主 Chunk 对 Chunk 的所有更改操作进行序列化, 所有的副本都遵从这个序列进行修改操作
        • 租约的状态变化
          • 租约的初始超时设置为 60 秒。
          • 只要Chunk 被修改了，主 Chunk 就可以申请更长的租期，通常会得到 Master 节点的确认并收到租约延长的时间。
          • 这些租约延长请求和批准的信息通常都是附加在 Master 节点和 Chunk 服务器之间的心跳消息中来传递
          • 但是这个细节是怎么样的? chunk的租期什么时候请求延长, master想要续租是每次修改自动附加续租的指令吗?
          • 考虑当一个chunk失效的时候, master里租期的变更问题
        • 使用过程
          • 客户机向 Master 节点询问哪一个 Chunk 服务器持有当前的租约，以及其它副本的位置
          • Master 节点将主 Chunk 的标识符以及其它副本（又称为 secondary 副本、二级副本）的位置返回给客户机。
            • 客户机缓存这些数据以便后续的操作
            • 只有在主 Chunk 不可用，或者主 Chunk 回复信息表明它已不再持有租约的时候，客户机才需要重新跟 Master 节点联系。
            • 我对这里有些疑惑, 因为不需要跟master联系的话, 并发的锁怎么使用呢? 怎么控制并发呢?
          • 操作会先发送到主chunk, 主chunk执行完之后才有序列号, 然后发送给其他二级副本
          • 如果任意阶段执行失败, 则会报告.
          • 跨越了多个chunk的写操作, GFS客户端会把他们分成多个 写操作
      • 数据流
        • 为了提高网络效率，我们采取了把数据流和控制流分开的措施
        • 读
        • 写
      • 原子的记录追加
        • 有一些关于追加size的细节, 比如追加满一个chunk该怎么办
      • 快照
    • 一致性模型
      • 关于 已定义 和 一致的
        • GFS，一致性模型里，“已定义”和“不一致”具体表示的什么含义？ - 郑炜韬的回答 - 知乎 https://www.zhihu.com/question/20485173/answer/37325847
        • consistent（一致的）意思就是所有用户在查询同一个chunk的时候，看到的结果是一样的，不管他是从该chunk的哪一个replica
        • defined包含了consistent，即如果一个chunk是defined，就一定是consistent的；且用户能够看到每一次mutation实际进行了什么操作写了什么数据。
      • GFS保证如下操作与状态
        • 注意表格中记录追加这里, 是一个大框
        • 并行的覆盖写因为会相互影响, 导致未定义
        • 并行的记录追加由于会将追加操作固定序列(保持一个顺序), 所以是已定义的
      • GFS对 Chunk 的所有副本的修改操作顺序一致
      • GFS使用了版本号, 如果某个副本因为机器故障修改失败, 那么其chunk版本号就会落后于最新的版本号, 这个副本是无效的
      • 写入成功一段时间后, master还可以通过和chunk的握手来找到失效的chunk服务器, 并使用checksum来校验数据
      • GFS 的应用程序可以利用一些简单技术实现这个宽松的一致性模型
        • 尽量采用追加写入而不是覆盖，Checkpoint，自验证的写入操作，自标识的记录
    • 高可用性
      • GFS使用两条简单但是有效的策略保证整个系统的高可用性：快速恢复和复制
      • 快速恢复
        • 它们都被设计为可以在数秒钟内恢复它们的状态并重新启动。
        • 但是论文没有详细介绍他们的方法......
      • chunk复制
        • 每个 Chunk 都被复制到不同机架上的不同的 Chunk 服务器上
      • master复制
        • 为了保证 Master 服务器的可靠性，Master 服务器的状态也要复制。Master 服务器所有的操作日志和checkpoint 文件都被复制到多台机器上
        • 对 Master 服务器状态的修改操作能够提交成功的前提是，操作日志写入到 Master 服务器的备节点和本机的磁盘
        • 当master服务器失效的时，几乎可以立刻重新启动。
          • 如果 Master 进程所在的机器或者磁盘失效了，处于 GFS 系统外部的监控进程会在其它的存有完整操作日志的机器上启动一个新的 Master 进程。
          • 客户端使用规范的名字访问 Master（比如 gfs-test）节点 (客户端通过监控程序得到master地址)
          • 这个名字类似 DNS 别名，因此也就可以在 Master 进程转到别的机器上执行时，通过更改别名的实际指向访问新的 Master 节点
        • "影子"master服务器
          • 这些“影子”服务器在“主”Master 服务器宕机的时候提供文件系统的只读访问
          • 它们的数据可能比“主”Master 服务器更新要慢，通常是不到 1 秒
          • “影子”Master 服务器会读取一份当前正在进行的操作的日志副本，并且依照和主 Master 服务器完全相同的顺序来更改内部的数据结构
          • 在主 Master 服务器因创建和删除副本导致副本位置信息更新时，“影子”Master 服务器才和主 Master 服务器通信来更新自身状态。
    • 单一master的优缺点
  • 常见问题
    • 为什么要有GFS?
      • GFS作为集群的分布式文件系统, 实现了扩展的文件系统, 不局限于单个磁盘的大小. 因为在大数据环境下, 单个文件可能超过磁盘大小.
      • GFS对用户隐藏了实现细节, 使得对用户而言就是一个普通的文件系统.
    • 为什么要提供容错?
      • GFS集群中有很多节点, 这使得机器异常成为一种常态.
      • 如果没有容错, 那么数据容易丢失, 为了提供容错, 就需要有副本.
      • 副本是通过复制得到的, 因此会有一致性问题(复制中途失败了怎么办?)
      • 一致性会导致低性能, 怎么权衡这两点?
    • 用户是如何使用GFS的?
      • GFS提供了一系列类POSIX文件系统接口,
      • 比如 read, write, create等
      • 需要区分 大文件和小文
      • 在系统中, write多是追加. 已写入的内容大多都不会被修改
  • MIT6.824-GFS
    • 设计目标
      • 高性能
      • 容错 -> 副本
      • 复制 -> 一致性
      • 一致性 -> 低性能
    • 笔记
      • GFS是弱一致性的, 他会出现数据错误. 但在Google的系统中, 这是可以允许的, 因为人们不会在乎搜索引擎少了一条数据
      • 需要持久化保存的
      • 使用日志(log)是因为日志追加很快(顺序写入)
      • master宕机需要重建它的状态. 平时它需要有副本(CheckoutPoint + log)进行重建
      • 各个API的执行过程与细节
        • READ
        • WRITES
          • 追加写入
      • 减少Master的负载是一个重要任务 (否则瓶颈可能在Master上)
        • GFS的chunk size较大, 这意味着元数据会更少, 会减少master的存储
        • 通过 Chunk Lease(租约) 将控制权限移交给主副本
        • GFS分离数据流和控制流, Master处理控制流, Chunk server 和 client 处理数据流
          • 数据不通过Master, 而只是Client向Master获取chunk的信息, 然后Client向chunk通信, 以及chunk与chunk之间通信(复制)
    • 问题
      • 在GFS上进行MapReduce的话, 大文件分块在边缘处怎么处理? 他们又不合并, 不会得到损失的数据吗?
      • GFS read如果数据在多个块上如何处理?
      • 一个大文件, 如何判断应该将它的块分到哪些chunk server, 如何实现负载均衡
      • 新加入了一个chunk server后, 如何保证平衡?
      • 一个大文件被切分了, 完整性就丢失了, 比如做mapreduce任务的时候, 把一个完整的单词切开了
  • 资料
    • GFS的一致性被认为是存在缺陷的
    • 一个1.5K star的github MIT6.824的项目 (很nice, 值得深入学习的资料)
    • GFS — 取舍的艺术: https://zhuanlan.zhihu.com/p/79746847
      • 作者引用了另一个作者的我觉得总结得很好的总结论
        • 我发现这个博客非常优质, 值得学习一下(https://www.qtmuniao.com/)
        • 简化系统元信息：Master 中维持了两个重要的映射，分别是文件路径到逻辑数据块，逻辑块与其多副本之间的关系。
        • 较大的数据块：选择了当时看来相当大的 64M 作为数据存储的基本单位，以此来减少元信息。
        • 放宽的一致性：允许多副本间内容不一致来简化实现、提高性能，通过读校验来保证损坏数据对用户不可见。
        • 高效副本同步：在多副本同步时分离控制流和数据流，利用网络拓扑提高同步效率(??)。
        • 租约分散压力：Master 通过租约将部分权力下放给某个 Chunkserver ，负责某个块的多副本间的读写控制。
        • 追加并发优化：多客户端对同一文件进行并发追加，保证数据原子性及At Least Once的语义。
        • 快速备份支持：使用 COW 策略实现快照操作，并通过块的引用计数来进行写时拷贝。
        • 逐节点锁控制：对于每个操作，需要沿着文件路径逐节点获取读锁，叶子节点获取读锁或者写锁，当然文件路径会进行前缀压缩。
        • 异步垃圾回收：将数据删除与其他一些主节点的维护操作（损坏块清除，过期数据块移除）统一起来，成为一个定期过程。
        • 版本号标记：帮助客户端识别过期数据。
        • 数据块校验和：针对每 64KB 的小块打上 32 bit 的校验和。
      • 本文 3.3节对副本复制的创建总结得比较好, 包括三种类型的复制
        • 副本创建（creation）
        • 副本补齐（re-replication）
        • 副本平衡（rebalancing）
    • 6.824 2020 视频笔记三：GFS: https://www.qtmuniao.com/2020/03/14/6-824-vidoe-notes-3-gfs/
      • 非常nice的系列笔记, 一定要看一下
    • GFS 相关的问题: https://github.com/chaozh/MIT-6.824/issues/6