分布式存储

魔法师LQ

回顾

  • 基于Linux,“table-like”数据操作

  • 命令行操作,正则表达式,awk, sort

  • 单机能力不够,推广到多台服务器

  • 缺陷:需要有管理者。但是我们希望是异步的。

    • 使用常驻进程,agent,每隔一段时间执行若干命令
    • 将以前的controller push变成现在的分布式的pull命令
  • 性能分析

    • 性能瓶颈:IO,计算
    • 分布式IO和计算

大纲

  • 文件系统

  • 布式文件系统

  • GFS 和 HDFS

  • 其他方案

Building Blocks

Type Size Speed
resisters thousands of bytes 1 CPU circle
Cache MB level
Main memory GB level 一般
Disk storage TB level`

功能

  • write
  • read
  • append
  • delete
  • modify

文件系统

准测

  • 能存大量的信息,理论上没有上限
  • information must survive the processed using it
  • concurrent access to multiple processes

文件系统解决方案

  • storage information on disks in units called files
  • files are persistent(持久化)
  • files are managed by the OS

Naming 命名

  • 创建文件并命名

  • 不同OS有不同的规则

Structure 结构

  • 序列结构(遍历),但是Byte Sequence: unstructured

  • 复杂的结构:例如树形结构

    • 变长记录
    • OS specific meaning of each file

文件系统的实现

如何实现文件系统呢?

  • 包含以下方面
    • volumes/partitions(磁盘规划)
    • directories(link filenames to file “structure”)
    • list of blocks
    • 高级需求,例如权限管理等

Structure to data

  • 创建文件
    • find space in the filesystem, add directory entry
  • writing in a file
    • write pointer
  • reading a file
    • read pointer

Data layout

  • file system is stored on disks

    • disk is divided into 1 or more partitions

    • sector 0 of disk called Mater Boot Record(MBR)

    • end of MBR has partition table(start & end address of partitions)

数据存储

  • 连续存储:优点,简单,读写性能比较好;缺点,改动效率不高,碎片太多,用户需要知道文件大小。
  • Linked List Allocation
    • Each file is stored as linked list of blocks
      • first word of each block points to next block
      • rest of disk block is file data
    • 优点
      • 只需要维护第一个block信息
    • 缺点
      • 随机访问开销大
      • overheads of pointers
使用
  • 根据情况使用,永久存储适合连续存储结构
  • 经常变更:列表结构
  • 索引结构:一个指针能够指向多个blocks

Linux 文件系统

Directory Tree

  • /
    • bin
      • pwd, cd, ls
    • sbin: root
      • ifup
      • ifconfig
      • ifdown
    • home
      • home directory
    • var
      • log files
      • spools
    • tmp
      • temp files
    • root
      • root’s home
    • usr
      • user program files
    • opt
      • optional

linux文件系统

Distributed File System

DFS Goals

  • location transparency
  • concurrency(并发性) transparency
  • failure transparency
  • heterogeneity(异构性)
  • scalability(可扩展性)

DFS structure

结构

  • meta server/name node:维护结构,命名
    • data node:负责存储
    • data node
    • ….

File VS. Chunk

  • 对外提供文件名访问
  • 文件对应chunk的id
  • 定义replication(冗余)
  • 整个DFS就是构建映射

可能的过程

  1. client请求
  2. 通过协议,client收到block/chunk信息
  3. client请求要访问的block/chunk
  4. 返回哪些name node的那些地方存在有相应的block/chunk
  5. client请求name node上的block/chunk
  6. 通过网络(socket)返回文件(流)

“Rack” awareness

  • core switch
    • core switch
      • rack switch
      • datanode (最容易访问的位置)
      • datanode
    • core switch

Read

  • 随机读
  • 并行读
  • throughput awareness
  • smart client

删除

  • 删除映射
  • 定期垃圾回收

优点和局限

  • fault tolerance, namenode在线热备份
  • custom designed(例如,定义chunk,减少访问次数)

缺点:只在特定的条件下有用。安全机制。

FS DFS
organized with a structure same as FS
index+data namenode+datanode
smart FS simple DFS+smart client

相当于把FS中的“聪明的”工作搬到client上了。

阅读任务

DHT(分布式哈希表)

GFS

阅读材料。(pipeline, reduplication)