• 时间:
  • 分类:

架构的层次

《The Google File System》

GFS的架构

  1. 小文件（通过索引获取block数据）

    {Disk: Metadata (FileInfo, Index) ——> Blocks}

    注：

    • FileInfo包含硬盘的原始信息，Index为数据位置的索引（例如：Access: (0644/-rw-r--r--) ）
    • 1 block = 1 KB = 1024 Byte

  2. 大文件（增加基本存储单位大小）

    {Disk: Metadata (FileInfo, Index) ——> Chunks}

    注：

    • 1 chunk = 64 MB = 65536 blocks
    • 减少元数据（Index索引少了）、减少流量，但小文件会浪费空间

  3. 超大文件（主从结构多机存储）

    {Master: Metadata (Info, Index)} ——> {ChunkServer: Chunks}

    注：

    • 将单机存储拓展为Master + many ChunkServers主从存储
    • Master的Index为ChunkServer名称及数据地址信息
    • ChunkServer数据的任何改变都需要通知Master

  4. 超大文件（减少Master的数据和流量）

    {Master: Metadata (Info, Index)} ——> {ChunkServer: Index ——> Chunks}

    注：

    • Master的Index为ChunkServer名称（不记录偏移量），ChunkServer的Index记录数据地址信息
    • 减少Master的元数据信息（仅记录所在ChunkServer，不记录偏移量），较少Master和ChunkServer之间的通信（本地数据变动时ChunkServer仅需要修改本地Index）

GFS架构图如下：

MasterServer的所有信息都存储在内存中，启动时信息从ChunkServer中获取。既提高MasterServer的性能和吞吐量，也有利于MasterServer宕机后主备切换。

GFS两大优势：

  1. Client和MasterServer之间只有控制流，没有数据流，降低MasterServer的负载（减少Client与MasterServer的交互）
  2. Client直接与ChunkServer进行通信，传输数据流，并且文件是多Chunk进行分布式存储，可以同时访问多个ChunkServer，从而提高系统I/O并行度。

GFS两大特点：

  1. 采用中心服务器模式

    • 方便增加ChunkServer
    • MasterServer可以掌握系统内所有ChunkServer的情况，方便进行负载均衡
    • 不存在元数据的一致性问题

  2. 不缓存数据（不建立系统缓存）

    • 文件操作大部分是流式读写，不存在大量重复读写，因此使用缓存对系统性能提升不大
    • ChunkServer的数据存储在本地文件系统上，如果频繁存取可以调用本地系统的缓存
    • 若建立系统缓存，则缓存中数据和ChunkServer中数据的一致性难以保证

GFS的机制

发现数据损坏（哈希验证）

Block中保存checksum（检验和，由数据哈希得来），读取数据时对checksum进行验证，如果block数据的再哈希与checksum不一致则说明数据损坏。

注：

  • 1 checksum = 32 bit

减少ChunkServer挂掉的损失（备份）

  1. 复制Chunks，即创建3个副本（Master中Index保存三个ChunkServer名称）

  2. 选择副本的原则

    • 硬盘利用率低
    • 限制最新数据块的写入数量
    • 跨机架跨中心：2+1

恢复损坏的chunk（求助Master）

向Master求助，获得最近的副本

发现ChunkServer挂掉（心跳）

  1. Master记录ChunkServer的心跳（时间戳）
  2. 如果Master与ChunkServer间网络损坏，使用其他ChunkServer去ping未连接ChunkServer

ChunkServer挂掉后恢复数据（修复进程）

当Master发现ChunkServer挂掉后启动修复进程（Working list基于存活副本数的修复策略）

应对热点（热点平衡进程）

热点平衡进程，记录Chunk的热度、服务器的剩余空间和带宽等

  1. 当副本过度繁忙，复制更多的ChunkServer
  2. 基于ChunkServer的硬盘和带宽利用率来选择

GFS写文件过程

当写文件出错时，不采用纠正机制，而是由Client客户端进行通知。

《Bigtable: A Distributed Storage System for Structured Data》

Bigtable的架构

  1. 文件内快速查询（key值排序）

    {Table = a list of sorted <key, value>}

    按照key排序构建表

  2. 保存大表（大表拆分小表）

    {Table = a list of tablets: Metadata} ——> {Tablet = a list of sorted <key, value>}

    将大表按照小表存储

  3. 保存超大表（大表拆分小表，小表拆分小小表）

    {Table = a list of tablets: Metadata} ——> {Tablet = a list of SSTables} ——> {SSTable = a list of sorted <key, value>}

Bigtable架构图如下：

Bigtable的机制

如何写数据（先写内存再写硬盘）

  1. 写入内存（通过写入memTable内存表来加速）

    {Memory: Tablet ——> <memTable, pointer>}

    A tablet = memTable + a list of SSTables

  2. 写入硬盘（当内存表过大时）

    {Memory: Tablet ——> memTable (FULL)} ——> {GFS/Disk: SSTable}

    将memTable导入硬盘，成为一个新的SSTable

避免内存数据丢失（添加log）

{Memory: memTable} ——> {GFS/Disk: tabletLog}

A tablet = memTable + a list of SSTables + log

如何读数据（预加载）

  1. 在所有SSTable和memTable中查找该元素

    注：

    • SSTable内部的数据是有序的，SSTable之间的数据是无序的

  2. 建立索引并加载在内存中

    对memTable和SSTable分别建立索引，并将索引预加载入内存Tablet中。

    A SSTable = a list of sorted <key, value> = a list of blocks + index

  3. 每次查找之前先对bloomfilter进行过滤

    对memTable和SSTable分别建立bloomfilter，并将bloomfilter预加载到内存Tablet中

    A SSTable = a list of sorted <key, value> = a list of blocks + index + bloomfilter

构建Bloomfilter

将key哈希映射到0-1字符串上，查找时将被查找元素先哈希，查看是否在bloomfilter中。虽然有误判，但可以接受

将表存入GFS

Bigtable主要使用内存结构，GFS主要使用硬盘结构。

BigTableServer即内存中会有各种小表Tablet，Tablet会将小小表SSTable和tablelog存储在硬盘上（并且做三份备份）

《MapReduce: Simplified Data Processing on Large Clusters》

Map的本质是拆解，Reduce的本质是组合

Input ——> Split ——> Map ——> Shuffle ——> Reduce ——> Finalize

取数据、切分、把数据归类、组装、交付

Map把一个函数应用于集合中的所有成员，然后返回一个基于这个处理的结果集。Reduce是把两个或更多个Map通过多个线程、进程或者独立系统进行并行执行处理得到的结果集进行分类和归纳（MapReduce封装了并行处理、容错处理、本地化计算、负载均衡等细节，具有简单而强大的接口）。

MapReduce样例

  1. 统计单词出现次数

  2. 建立倒排索引

标签: none

评论已关闭